【比賽記錄】2025CSP-S模擬賽18
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 100 | 15 | 25 | 240 | 6/21 |
A. flandre
數據過弱放過一批錯解。包括我的
正解：一個結論是選擇的序列一定是原數組排序后的一段后綴。具體的證明是，如果 \(a_i\) 互不相同那么可以將區間一直往右移，如果相同那么一定可以不斷插入進去，答案一定不劣。于是對每一段后綴都求出答案求最大值即可。
放個 UKE 造的 Hack 數據（也就是 Hack 掉我的那組）
Input:
11 4
-38 -37 1 2 3 4 5 6 7 8 9
Output:
190 11
1 2 3 4 5 6 7 8 9 10 11
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lwrb lower_bound
#define pii pair<int,int>
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace asbt{
const int maxn=1e6+5;
int n,m,lsh[maxn],tot,tong[maxn];
pii a[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].fir;
a[i].sec=i;
lsh[++tot]=a[i].fir;
}
sort(a+1,a+n+1);
sort(lsh+1,lsh+tot+1);
tot=unique(lsh+1,lsh+tot+1)-lsh-1;
for(int i=1;i<=n;i++){
a[i].fir=lwrb(lsh+1,lsh+tot+1,a[i].fir)-lsh;
}
int ans=0,pos=n+1;
for(int i=n,res=0;i;i--){
int t=a[i].fir;
res+=lsh[t];
res+=m*(n-i-tong[t]);
tong[t]++;
if(ans<res){
ans=res,pos=i;
}
}
cout<<ans<<" "<<n-pos+1<<"\n";
for(int i=pos;i<=n;i++){
cout<<a[i].sec<<" ";
}
return 0;
}
}
signed main(){return asbt::main();}
B. meirin
設 \(f_i\) 為 \(a\) 數組中所有包含 \(i\) 位置的區間的和，那么一個在 \(i\) 位置增加 \(k\) 對答案的貢獻就是 \(f_i\times k\)。問題變為求 \(f\)。
考慮一個區間 \([l,r]\)，設其區間和為 \(sum\)，則會對所有 \(i\in[l,r]\) 的 \(f_i\) 產生 \(sum\) 的貢獻。這提示我們做差分，也就是在 \(f_l\) 加 \(sum\)，在 \(f_{r+1}\) 減 \(sum\)，之后再做一遍前綴和即可。
考慮對于一個右端點 \(r\)，其對應的 \(r\) 個左端點 \(l\in[1,r]\)，\(f_l\) 要加上 \(sa_r-sa_{l-1}\)，同時 \(f_{r+1}\) 要加上 \(sa_{l-1}-sa_r\)。其中 \(sa\) 是 \(a\) 的前綴和。設 \(i=l\)，則有 \(f_i\) 要加上 \(sa_j- sa_{i-1}\)，其中 \(j\in[i,n]\)；設 \(i=r+1\)，則 \(f_i\) 要加上 \(sa_j-sa_{i-1}\)，其中 \(j\in[0,i-2]\)。于是：
\[\begin{aligned}
f_i&=\sum_{j\in[0,i-2]\cup[i,n]}(sa_j-sa_{i-1})\\
&=(\sum_{j=0}^{n}sa_j)-(n+1)\times sa_{i-1}
\end{aligned}
\]
時間復雜度線性，似乎需要卡常。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace IO{
const int bufsz=1<<20;
char ibuf[bufsz],*p1=ibuf,*p2=ibuf;
char obuf[bufsz],*p3=obuf,stk[50];
#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,bufsz,stdin),p1==p2)?EOF:*p1++)
#define flush() (fwrite(obuf,1,p3-obuf,stdout),p3=obuf)
#define putchar(ch) (p3==obuf+bufsz&&flush(),*p3++=(ch))
il int read(){
bool fu=0;
char ch=getchar();
while(ch<'0'||ch>'9'){
fu^=ch=='-';
ch=getchar();
}
int x=0;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return fu?-x:x;
}
il void write(int x){
int top=0;
do{
stk[++top]=x%10|48;
x/=10;
}while(x);
while(top){
putchar(stk[top--]);
}
putchar('\n');
}
struct FL{
~FL(){
flush();
}
}fl;
#undef getchar
#undef putchar
#undef flush
}
using IO::read;
using IO::write;
const int maxn=5e5+5,mod=1e9+7;
il int qum(int x){
return x<0?x+mod:x;
}
il int pls(int x,int y){
return x+y<mod?x+y:x+y-mod;
}
il int mns(int x,int y){
return x>=y?x-y:x-y+mod;
}
int n,m,a[maxn],f[maxn];
int main(){
// system("fc 2.out my.out");
// freopen("B.in","r",stdin);
// freopen("my.out","w",stdout);
n=read(),m=read();
int sum=0;
for(int i=1;i<=n;i++){
a[i]=pls(a[i-1],qum(read()));
sum=pls(sum,a[i]);
}
for(int i=1;i<=n;i++){
f[i]=pls(f[i-1],mns(sum,(n+1)*1ll*a[i-1]%mod));
}
int ans=0;
for(int i=1;i<=n;i++){
ans=pls(ans,f[i]*1ll*qum(read())%mod);
}
for(int i=1;i<=n;i++){
f[i]=pls(f[i-1],f[i]);
}
while(m--){
int l=read(),r=read();
ans=pls(ans,mns(f[r],f[l-1])*1ll*qum(read())%mod);
write(ans);
}
return 0;
}
// :-| <:-#
C. sakuya
設 \(a\) 序列中 \(i\) 和 \(j\) 相鄰出現的次數為 \(\operatorname{cnt}(i,j)\)，那么答案即為 \(\frac{\sum\operatorname{dis}(i,j)\times\operatorname{cnt}(i,j)}{m!}\)。顯然 \(\operatorname{cnt}(i,j)=2\times(m-1)!\)，于是問題變為求 \(\sum\operatorname{dis}\)。
然而這個是好求的，算出每一條邊兩端的關鍵點數即可算出它出現的次數 \(num\)。對于修改，求出每個點相鄰的所有邊的 \(num\) 之和就好了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
namespace asbt{
const int maxn=5e5+5,mod=998244353;
int n,m,sz[maxn],dep[maxn],dp[maxn],ans,q;
vector<pii> e[maxn];
il void dfs1(int u,int fa){
dep[u]=dep[fa]+1;
for(pii i:e[u]){
int v=i.fir;
if(v==fa){
continue;
}
dfs1(v,u);
sz[u]+=sz[v];
}
}
il int calc(int u,int v){
if(dep[u]<dep[v]){
swap(u,v);
}
return sz[u]*1ll*(m-sz[u])%mod;
}
il void dfs2(int u,int fa){
for(pii i:e[u]){
int v=i.fir,w=i.sec;
int t=calc(u,v);
(dp[u]+=t)%=mod;
if(v==fa){
continue;
}
(ans+=t*1ll*w%mod)%=mod;
dfs2(v,u);
}
}
il int qpow(int x,int y=mod-2){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
x=x*1ll*x%mod,y>>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
e[u].pb(mp(v,w));
e[v].pb(mp(u,w));
}
for(int i=1,x;i<=m;i++){
cin>>x;
sz[x]++;
}
dfs1(1,0),dfs2(1,0);
int tms=qpow(m)*2%mod;
cin>>q;
while(q--){
int u,k;
cin>>u>>k;
(ans+=dp[u]*1ll*k%mod)%=mod;
cout<<ans*1ll*tms%mod<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
D. 紅樓 ~ Eastern Dream
考慮根號分治。對于 \(x\le\sqrt{n}\) 的修改，我們可以記錄 \(b_{i,j}\) 表示所有 \(p\equiv j\pmod{i}\) 的 \(p\) 的增量。于是在修改時只需要改變 \(b\) 數組即可。查詢時枚舉模數 \(i\)，計算 \(l\) 和 \(r\) 所在的循環節，使用前綴和即可 \(O(1)\) 計算 \(i\) 的貢獻。這一部分單次修改和查詢時間復雜度都為 \(O(\sqrt{n})\)。
對于 \(x>\sqrt{n}\) 的修改，循環節只有 \(O(\sqrt{n})\) 個，我們可以分塊維護增量的差分數組 \(d\)，在修改時每段區間修改就都是 \(O(1)\) 的。查詢時，我們要查的其實就是這個式子：
\[\begin{aligned}
\sum_{i=l}^{r}\sum_{j=1}^{i}d_j&=\sum_{i=1}^{l-1}d_i\times(r-l+1)+\sum_{i=l}^{r}d_i\times(r-i+1)\\
&=(r-l+1)\times\sum_{i=1}^{l-1}d_i+(r+1)\times\sum_{i=l}^{r}d_i-\sum_{i=l}^{r}d_i\times i
\end{aligned}
\]
于是我們用分塊維護 \(d_i\) 和 \(d_i\times i\) 即可。這部分復雜度也是 \(O(\sqrt{n})\)。
硬卡是能卡爆 long long 的，但是數據沒卡 std 也沒有，那就不管它了吧??
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5,B=450;
int n,m;
ll a[maxn],b[505][505],sb[505][505];
struct{
int bn,L[505],R[505],bel[maxn];
ll d[maxn],sd[505],di[maxn],sdi[505];
il void build(){
bn=(n+B-1)/B;
for(int i=1;i<=bn;i++){
L[i]=R[i-1]+1;
R[i]=min(R[i-1]+B,n);
for(int j=L[i];j<=R[i];j++){
bel[j]=i;
}
}
}
il void add(int p,ll x){
if(p>n){
return ;
}
d[p]+=x,sd[bel[p]]+=x;
di[p]+=x*p,sdi[bel[p]]+=x*p;
}
il ll queryd(int l,int r){
if(l>r){
return 0;
}
int pl=bel[l],pr=bel[r];
ll res=0;
if(pl==pr){
for(int i=l;i<=r;i++){
res+=d[i];
}
}
else{
for(int i=l;i<=R[pl];i++){
res+=d[i];
}
for(int i=L[pr];i<=r;i++){
res+=d[i];
}
for(int i=pl+1;i<pr;i++){
res+=sd[i];
}
}
return res;
}
il ll querydi(int l,int r){
if(l>r){
return 0;
}
int pl=bel[l],pr=bel[r];
ll res=0;
if(pl==pr){
for(int i=l;i<=r;i++){
res+=di[i];
}
}
else{
for(int i=l;i<=R[pl];i++){
res+=di[i];
}
for(int i=L[pr];i<=r;i++){
res+=di[i];
}
for(int i=pl+1;i<pr;i++){
res+=sdi[i];
}
}
return res;
}
}BL;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
// cout<<cplx::usdmem();
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]+=a[i-1];
}
BL.build();
while(m--){
int opt;
cin>>opt;
if(opt==1){
int x,y;
ll k;
cin>>x>>y>>k;
y=min(y,x-1);
if(x<=B){
for(int i=0;i<=y;i++){
b[x][i]+=k;
}
sb[x][0]=b[x][0];
for(int i=1;i<x;i++){
sb[x][i]=sb[x][i-1]+b[x][i];
}
}
else{
for(int i=1;i<=n;i+=x){
BL.add(i,k),BL.add(i+y+1,-k);
}
}
}
else{
int l,r;
cin>>l>>r;
ll ans=a[r]-a[l-1];
for(int i=1;i<=B;i++){
int zl=(l-1)/i,zr=(r-1)/i;
int sl=(l-1)%i,sr=(r-1)%i;
if(zl==zr){
ans+=sb[i][sr]-(sl?sb[i][sl-1]:0);
}
else{
ans+=sb[i][i-1]-(sl?sb[i][sl-1]:0)+sb[i][sr];
ans+=sb[i][i-1]*(zr-zl-1);
}
}
ans+=(r-l+1)*BL.queryd(1,l-1);
ans+=(r+1)*BL.queryd(l,r);
ans-=BL.querydi(l,r);
cout<<ans<<"\n";
}
}
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號