【考后总结】8 月 CSP-S 模拟赛 2
8.7 CSP 模拟 15
世界が终るまでは - WANDS
大都会に 仆はもう一人で
孤身一人 彷徨在大都市投げ舍てられた 空カンのようだ
就像被人丢弃的 空啤酒罐互いのすべてを 知りつくすまでが
如果非要探究 彼此的一切爱ならば いっそ 永久(とわ)に眠ろうか
才叫爱的话 还不如永久长眠世界が终るまでは 离れる事もない
直到世界的尽头 也不愿与你分离そう愿っていた 几千の夜と
曾在千万个夜晚许下心愿戻らない时だけが 何故辉いては
一去不回的时光 为何却如此耀眼やつれ切った 心までも 壊す
对憔悴不堪的心 落井下石はかなき想い このTragedy Night
渺茫的思念 在这个悲剧的夜そして人は 形(こたえ)を求めて
而人们 总是追求表面答案かけがえのない 何かを失う
结果错失 无可取代的宝物欲望だらけの 街じゃ
在这充斥着欲望的街头夜空の 星屑も 仆らを 灯せない
就连夜空繁星 也难以照亮我们世界が终る前に 闻かせておくれよ
在世界结束之前 谁愿给我讲一个満开の花が 似合いのCatastrophe
与繁花盛开 最贴切的不幸谁もが望みながら 永远を信じない
谁都满怀着期望 又不相信永远なのに きっと 明日を梦见てる
可是也一定 梦想着明天はかなき日々と このTragedy Night
短暂的时光 在这悲剧的夜晚世界が终るまでは 离れる事もない
直到世界的尽头 也不愿与你分离そう愿っていた 几千の夜と
曾在千万个夜晚 许下心愿戻らない时だけが 何故辉いては
一去不回的时光 为何却如此耀眼やつれ切った 心までも 壊す
对憔悴不堪的心 落井下石はかなき想い このTragedy Night
渺茫的思念 在这悲剧的夜晚このTragedy Night
这悲剧的夜晚
\(\text{sitiy round}\)
T2 CE，身败名裂！
T1 The Morning Star
原题：CodeForces-1850G The Morning Star *1500
直接 map 维护。
点击查看代码
int n;
map<int,int> mpx,mpy,mp1,mp2;
ll ans;
int main(){
n=read();
for(int i=1;i<=n;++i){
int x=read(),y=read();
ans+=(mpx[x]+mpy[y]+mp1[x+y]+mp2[x-y])*2;
++mpx[x],++mpy[y],++mp1[x+y],++mp2[x-y];
}
printf("%lld\n",ans);
return 0;
}
T2 Ntarsis' Set
原题：CodeForces-1852A Ntarsis' Set *1800
考虑二分一个位置 \(x\)，判断 \([1,x]\) 的数能不能都删去。
这时并不关心删去了什么，\(x\) 可以视作前 \(x\) 个数而不是 \([1,x]\)。模拟每次删除操作，每次找到最大的 \(i\) 满足 \(a_i\le x\)，这样就会删去 \([1,x]\) 中的 \(i\) 个数，于是 \(x\leftarrow x-i\)，如果最终 \(x=0\) 则可以全部删去。
复杂度 \(O(k\log nk)\)。
点击查看代码
int n,k;
int a[maxn];
ll ans;
inline bool check(ll x){
for(int i=1;i<=k;++i){
int p=upper_bound(a+1,a+n+1,x)-a-1;
x-=p;
}
if(x) return true;
else return false;
}
int main(){
n=read(),k=read();
for(int i=1;i<=n;++i) a[i]=read();
ll L=1,R=1ll*n*k+1;
while(L<=R){
ll mid=(L+R)>>1;
if(check(mid)) ans=mid,R=mid-1;
else L=mid+1;
}
printf("%lld\n",ans);
return 0;
}
T3 Team Work
原题：CodeForces-932E Team Work *2400
之前写过闲话，这是 链接。
第一部分暴力做，考虑第二部分。
复杂度 \(O(k^2)\)。
点击查看代码
inline int q_pow(int A,int B,int P){
int res=1;
while(B){
if(B&1) res=1ll*res*A%P;
A=1ll*A*A%P;
B>>=1;
}
return res;
}
int n,k;
int ans;
namespace Subtask1{
int fact[maxn],inv_fact[maxn];
inline int C(int N,int M){
return 1ll*fact[N]*inv_fact[M]%mod*inv_fact[N-M]%mod;
}
int main(){
fact[0]=1;
for(int i=1;i<=n;++i) fact[i]=1ll*fact[i-1]*i%mod;
inv_fact[0]=1,inv_fact[n]=q_pow(fact[n],mod-2,mod);
for(int i=n-1;i>=1;--i) inv_fact[i]=1ll*inv_fact[i+1]*(i+1)%mod;
for(int i=1;i<=n;++i) ans=(ans+1ll*C(n,i)*q_pow(i,k,mod)%mod)%mod;
printf("%d\n",ans);
return 0;
}
}
namespace Subtask2{
int S[2][maxk],dpw[maxk],pw2[maxk];
int main(){
S[0][0]=1,dpw[0]=1,pw2[0]=q_pow(2,n,mod);
for(int i=1;i<=k;++i){
S[i&1][0]=0,S[i&1][i]=1;
for(int j=1;j<i;++j){
S[i&1][j]=(1ll*j*S[i&1^1][j]%mod+S[i&1^1][j-1])%mod;
}
dpw[i]=1ll*dpw[i-1]*(n-i+1)%mod,pw2[i]=1ll*pw2[i-1]*inv2%mod;
}
for(int i=0;i<=k;++i){
ans=(ans+1ll*S[k&1][i]*dpw[i]%mod*pw2[i]%mod)%mod;
}
if(!k) ans=(ans-1+mod)%mod;
printf("%d\n",ans);
return 0;
}
}
int main(){
n=read(),k=read();
if(n<=lim) return Subtask1::main();
else return Subtask2::main();
return 0;
}
T4 Make Equal
原题：CodeForces-1188D Make Equal *3100
把 \(a\) 升序排序，那么最终结果一定是 \(x+a_n\)，设 \(b_i=a_n-a_i\)，那么答案是：
按位考虑，则贡献要考虑三部分：\(x,b_i\) 在这一位的值以及是否从上一位有进位。
有无进位可以按 \(b_i\bmod 2^k\) 降序，这样一定是一个前缀有进位（加同样的数越大越有可能进位）。
设 \(f_{k,i}\) 表示考虑到 \(2^k\)，且有 \(i\) 个进位的最小操作次数。
讨论上面的三部分得出产生多少操作数以及产生多少进位，即可转移。
复杂度 \(O(n\log n\log a)\)。
点击查看代码
int n;
ll a[maxn];
int id[maxn];
int f[maxlg][maxn],sum[maxn][2];
int main(){
n=read();
for(int i=1;i<=n;++i) a[i]=read();
sort(a+1,a+n+1);
for(int i=1;i<=n;++i) a[i]=a[n]-a[i];
memset(f,0x3f,sizeof(f));
int cnt1=0;
for(int i=1;i<=n;++i) cnt1+=(a[i]&1);
f[0][0]=min(f[0][0],cnt1),f[0][cnt1]=min(f[0][cnt1],n-cnt1);
for(int k=1;k<=61;++k){
for(int i=1;i<=n;++i) id[i]=i;
sort(id+1,id+n+1,[&](int x,int y){
return (a[x]&((1ll<<k)-1))>(a[y]&((1ll<<k)-1));
});
sum[0][0]=0,sum[0][1]=0;
for(int i=1;i<=n;++i){
sum[i][0]=sum[i-1][0],sum[i][1]=sum[i-1][1];
if(a[id[i]]&(1ll<<k)) ++sum[i][1];
else ++sum[i][0];
}
for(int i=0;i<=n;++i){
int now=sum[i][0]+sum[n][1]-sum[i][1],cnt=sum[i][1];
f[k][cnt]=min(f[k][cnt],f[k-1][i]+now);
now=sum[i][1]+sum[n][0]-sum[i][0],cnt=n-(sum[n][0]-sum[i][0]);
f[k][cnt]=min(f[k][cnt],f[k-1][i]+now);
}
}
printf("%d\n",f[61][0]);
return 0;
}
反思
一个多小时写完两个正解和 T4 暴力以后，乱冲 T2 正解，没有写暴力，最后 CE 离场。
赛时考虑到二分答案以及一个前缀是否被删去，但没有意识到此时每次具体删去什么并不重要。打表的手玩数据也不够强力，找到接近正确的结论之后也没判断单调性之类直接乱冲，耽误大把时间。