8.7 CSP 模拟 15
只因你太美 - 蔡徐坤
> 只因你太美 baby 只因你太美 baby > > 只因你实在是太美 baby 只因你太美 baby > > 迎面走来的你让我如此蠢蠢欲动 > > 这种感觉我从未有 > > Cause I got a crush on you who you > > 你是我的我是你的谁 > > 再多一眼看一眼就会爆炸 > > 再近一点靠近点快被融化 > > 想要把你占为己有baby bae > > 不管走到哪里都会想起的人是你 you you > > 我应该拿你怎样 > > uh 所有人都在看着你 > > 我的心总是不安 > > oh 我现在已病入膏肓 > > eh eh 难道真的因为你而疯狂吗 > > 我本来不是这种人 > > 因你变成奇怪的人 > > 第一次呀变成这样的我 > > 不管我怎么去否认 > > 只因你太美 baby 只因你太美 baby > > 只因你实在是太美 baby 只因你太美 baby > > oh eh oh现在确认地告诉我 > > oh eh oh 你到底属于谁 > > oh eh oh现在确认地告诉我 > > oh eh oh 你到底属于谁 就是现在告诉我 > > 跟着这节奏 缓缓 make wave > > 甜蜜的奶油 it's your birthday cake > > 男人们的 game call me 你恋人 > > 别被欺骗愉快的 I wanna play > > 我的脑海每分每秒只为你一人沉醉 > > 最迷人让我神魂颠倒是你身上香水 > > oh right baby I'm fall in love with you > > 我的一切你都拿走只要有你就已足够 > > 我到底应该怎样 > > uh 我心里一直很不安 > > 其他男人们的视线 > > Oh 全都只看向你的脸 > > Eh eh 难道真的因为你而疯狂吗 > > 我本来不是这种人 > > 因你变成奇怪的人 > > 第一次呀变成这样的我 > > 不管我怎么去否认 > > 只因你太美 baby 只因你太美 baby > > 只因你实在是太美 baby 只因你太美 baby > > 我愿意把我的全部都给你 > > 我每天在梦里都梦见你还有我闭着眼睛也能看到你 > > 现在开始我只准你看我 > > I don’t wanna wake up in dream 我只想看你这是真心话 > > 只因你太美 baby 只因你太美 baby > > 只因你实在是太美 baby 只因你太美 baby > > oh eh oh现在确认的告诉我 > > oh eh oh 你到底属于谁 > > oh eh oh现在确认的告诉我 > > oh eh oh 你到底属于谁就是现在告诉我\(\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
之前写过闲话，这是 链接。
第一部分暴力做，考虑第二部分。
\[\begin{aligned} &\sum_{i=1}^n i^k\dbinom{n}{i}\\ =&\sum_{i=1}^n\dbinom{n}{i}\sum_{j=0}^k \begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom{i}{j}\\ =&\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum_{i=1}^n\dbinom{n}{i}\dbinom{i}{j}\\ =&\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum_{i=1}^n\dbinom{n}{j}\dbinom{n-j}{i-j}\\ =&\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}n^{\underline{j}}\sum_{i=0}^{n-j}\dbinom{n-j}{i}\\ =&\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}n^{\underline{j}}2^{n-j} \end{aligned} \]复杂度 \(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\)，那么答案是：
\[\sum_{i=1}^n \mathrm{popcount}(x+a_n-a_i)=\sum_{i=1}^n \mathrm{popcount}(x+b_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 离场。
赛时考虑到二分答案以及一个前缀是否被删去，但没有意识到此时每次具体删去什么并不重要。打表的手玩数据也不够强力，找到接近正确的结论之后也没判断单调性之类直接乱冲，耽误大把时间。
标签：考后,oh,int,sum,太美,baby,CSP,模拟,eh From： https://www.cnblogs.com/SoyTony/p/Simulation_Problems_of_CSP-S_in_August_2.html