D - Odd or Even
假设 \(A_1\) 到 \(A_{k-1}\) 的和是偶数。那么通过 \(n\) 次询问可以得到所有数是 \(0\) 还是 \(1\)。如果将 \(A_1\) 到 \(A_{k-1}\) 代入检验发现和不是偶数，由于 \(k\) 是奇数，反转所有数，可以使它合法。
#include <bits/stdc++.h>
using namespace std;
const int maxn=2005;
int n,k,a[maxn],tval[maxn];
int query(vector<int> S)
{
printf("? ");
for(int v:S)printf("%d ",v);
putchar('\n');
fflush(stdout);
int x;scanf("%d",&x);
return x;
}
int tx=0;
int main()
{
scanf("%d%d",&n,&k);
if(k==1)
{
vector<int> now;
for(int i=1;i<=n;i++){now.clear();now.push_back(i);tval[i]=query(now);}
printf("! ");for(int i=1;i<=n;i++)printf("%d ",tval[i]);putchar('\n');
return 0;
}
vector<int> tS;
for(int i=1;i<k;i++)tS.push_back(i);
for(int i=k;i<=n;i++)
{
tS.push_back(i);
tval[i]=query(tS);
//printf("%d %d\n",i,tval[i]);
tS.pop_back();
}
int bp=tval[k]^tval[k+1];
for(int i=k-1;i>=1;i--)
{
tS.clear();
tS.push_back(k);tS.push_back(k+1);
for(int j=1;j<k;j++)if(i!=j)tS.push_back(j);
int x=query(tS);
tval[i]=bp^x;
//printf("%d %d",i,tval[i]);putchar('\n');
}
bp=0;
int x=1;
for(int i=2;i<k;i++)bp^=tval[i];
if(bp!=tval[1])for(int i=1;i<=n;i++)tval[i]^=1;
printf("! ");
for(int i=1;i<=n;i++)printf("%d ",tval[i]);
putchar('\n');
fflush(stdout);
return 0;
}
E - Duplicate
考虑什么时候删不成 \(1\)，发现如果有连续两个大于 \(1\) 的就寄了。那么现在数列只有可能是 \(A_1 \ 1 \ 1 \ 1\dots \ 1 \ 1 \ A_2 \ 1 \ 1 \dots\) 这种样子，从后往前扫，计算删到这个数所需要几轮，然后你就可以看它在这么多轮里复制了多少个 \(1\) 出来，累加进当前的轮数里。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10,mod=998244353;
int n;
char s[maxn];
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
cin>>s+1;
int now=1;
for(int i=1;i<n;i++)
if(s[i]!='1'&&s[i+1]!='1')
{
puts("-1");
return 0;
}
int nowt=1;
for(int i=n-1;i>=1;i--)
{
int x=s[i+1]-'0';
nowt=(1ll*nowt+1+1ll*(x-1)*nowt%mod)%mod;
}
cout<<nowt-1<<endl;
return 0;
}
F - Flip Machines
我们并不关心一个牌可能会被翻几次，只有最后一次和它相关的翻转决定它是正还是反。（注意因为这点你要特判 \(X_i = Y_i\) 的情况）。所以我们只关心这张牌会不会被翻，即如果 \(\exists i\in S,X_i = j \lor Y_i=j\)，则 \(j\) 这张牌的贡献为 \(\frac{|A_j+B_j|}{2}\)，否则为 \(A_j\)。
令 \(D_i=\frac{B_i-A_i}{2}\)。我们相当于要从那些边中选一些出来，使这些边相关的 \(D_i\) 之和最大。这里导出了一个 \(\mathcal{O}(2^nm)\) 的状压dp。但是 \(n\) 规模到了 \(40\)，想要减少这个规模，就得考虑类似于mid in middle的思路。我们将牌按 \(D_i\) 的正负性分成两组，那么必有一组的大小 \(\leq20\)。如果我们将这组拿来状压，另一组直接遍历一遍。
这样dp的复杂度降低到了 \(\mathcal{O}(m+{n}2^{\frac{n}{2}-1})\)。
#include <bits/stdc++.h>
using namespace std;
const int maxn=44;
int n,m,X[100005],Y[100005];
double dp[maxn][(1<<21)];
double a[maxn],b[maxn],d[maxn];
int tp[maxn],idp[maxn],plen,tq[maxn],idq[maxn],qlen;
vector<int> G[maxn];
bool tag[maxn],pnt[maxn];
int main()
{
// freopen("data.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i],d[i]=abs(a[i]-b[i])/2;
for(int i=1;i<=m;i++)
cin>>X[i]>>Y[i],G[X[i]].push_back(Y[i]),G[Y[i]].push_back(X[i]);
for(int i=1;i<=m;i++)
if(X[i]==Y[i]&&a[X[i]]<b[X[i]])swap(a[X[i]],b[X[i]]);
for(int i=1;i<=n;i++)
if(a[i]>=b[i])tp[idp[i]=plen++]=i,pnt[i]=0;
else tq[idq[i]=qlen++]=i,pnt[i]=1;
//printf("%d %d\n",plen,qlen);
for(int i=1;i<=m;i++)
if(pnt[X[i]]==1&&pnt[Y[i]]==1)tag[X[i]]=tag[Y[i]]=1;
if(plen<qlen)
{
//puts("!");
for(int j=0;j<=plen;j++)for(int i=0;i<(1<<plen);i++)dp[j][i]=-1e18;
dp[0][0]=0;
for(int i=0;i<qlen;i++)
{
int u=tq[i];
for(int S=0;S<(1<<plen);S++)
{
if(dp[i][S]==-1e18)continue;
dp[i+1][S]=max(dp[i+1][S],dp[i][S]+(tag[u]?d[u]:0));
for(int v:G[u])
dp[i+1][S|(1<<idp[v])]=max(dp[i+1][S|(1<<idp[v])],dp[i][S]+d[u]);
}
}
double ans=-1e18,sum=0;
for(int i=1;i<=n;i++)sum+=a[i];
for(int i=0;i<(1<<plen);i++)
if(dp[qlen][i]==-1e18)continue;
else
{
double now=dp[qlen][i];
for(int j=0;j<plen;j++)if((i>>j)&1)now-=d[tp[j]];
ans=max(ans,now+sum);
}
cout<<fixed<<setprecision(6)<<ans<<endl;
}
else
{
//puts("@");
for(int j=0;j<=plen;j++)for(int i=0;i<(1<<qlen);i++)dp[j][i]=-1e18;
dp[0][0]=0;
for(int i=0;i<plen;i++)
{
int u=tp[i];
for(int S=0;S<(1<<qlen);S++)
{
if(dp[i][S]==-1e18)continue;
dp[i+1][S]=max(dp[i+1][S],dp[i][S]);
int T=0;
for(int v:G[u])
if(pnt[v])T|=(1<<idq[v]);
dp[i+1][S|T]=max(dp[i+1][S|T],dp[i][S]-d[u]);
}
}
double ans=-1e18,sum=0;
for(int i=1;i<=n;i++)sum+=a[i];
for(int i=0;i<(1<<qlen);i++)
if(dp[plen][i]==-1e18)continue;
else
{
double now=dp[plen][i];
for(int j=0;j<qlen;j++)if(((i>>j)&1)||(tag[tq[j]]))now+=d[tq[j]];
ans=max(ans,now+sum);
}
cout<<fixed<<setprecision(6)<<ans<<endl;
}
}
G - Redistribution of Piles
为了不重不漏的计数，考虑枚举所有可能的相对大小。
一点一点的往下减，发现如果出现了 \(0\) 则接着减的所有情况都会出现新的相对大小（因为那个 \(0\) 不变了，其他不是 \(0\) 的还在减，和这个 \(0\) 的大小关系肯定会变嘛），知道所有数都变成 \(0\) 了为止。对于每个相对大小关系，它对答案的贡献为 \(\lfloor \frac{sum-now}{n}+1 \rfloor\)。\(sum-now\) 其实就是当前包里有多少石子。我们按照当前数列中还有多少个不是 \(0\) 分段计算。先将 \(a\) 排序，每次将当前还不是零的最小的 \(a_i\) 取成 \(0\) 并计算取成 \(0\) 过程中所有相对大小关系的贡献，设包里当前有 \(now\) 个石子，那贡献为 \(\sum\limits_{j=1}^{a_i-a_{i-1}}{\lfloor \frac{(now-i+1)\times j}{n}+1 \rfloor }\)。用类欧计算即可。
#include <bits/stdc++.h>
#include <atcoder/all>
#define int long long
using namespace atcoder;
using namespace std;
const int maxn=2e5+10,mod=998244353;
int a[maxn],n;
pair<int,int> p[maxn];
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],p[i]={a[i],i};
sort(p+1,p+1+n);
int nowsum=p[1].first*n,nowbot=p[1].first,ans=p[1].first+1;
for(int i=2;i<=n;i++)
{
int lim=p[i].first-nowbot;
if(lim==0)continue;
int val=floor_sum(lim,n,n-i+1,n-i+1+nowsum+n)%mod;
//cout<<val<<endl;
ans=(ans+val)%mod;
nowsum+=1ll*(p[i].first-nowbot)*(n-i+1);
nowbot=p[i].first;
}
ans%=mod;
cout<<ans<<endl;
}
Ex - Group Photo
我们先将 \(A\) 和 \(B\) 从小到大排序。
我们从小到大依次加入 \(A_i\)，根据它与当前已经加入的 \(i-1\) 之间的位置关系，它可能会新增 \(0/1/2\) 个大小为 \(A_i\) 的位置，我们拿当前最小的 \(B\) 去跟这些位置匹配，如果到了最后可以使所有匹配满足条件，则这个 \(A\) 的排列可行（打乱 \(B\) 的顺序显然不影响答案）。那我们dp，设 \(dp_{i,j}\) 表示已经从小到大放了 \(i\) 个数，当前有 \(j\) 个连续段，知道当前的 \(i+j\) 个匹配都合法的方案数。那么有三种转移：
- \(A_i\) 夹在两个放过的数之间，那 \(A_i\) 不会出现，系数为 \(j-1\)，转移到 \(dp_{i+1,j-1}\)。
- \(A_i\) 在一个放过的数左边或右边，那 \(A_i\) 出现一次，系数为 \(2j\)，转移到 \(dp_{i+1,j}\)。
- \(A_i\) 不与之前放的数相邻，那 \(A_i\) 出现两次。系数为 \(j+1\)（排列dp只考虑相对关系），转移到 \(dp_{i+1,j+1}\)。
答案就是 \(dp_{n,1}\)。
#include <bits/stdc++.h>
using namespace std;
const int maxn=5005,mod=998244353;
int n,a[maxn],b[maxn],dp[maxn][maxn];
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n+1;i++)cin>>b[i];
sort(a+1,a+1+n);
sort(b+1,b+1+n+1);
dp[0][0]=1;
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++)
{
if(!dp[i][j])continue;
if(j>=2&&i+j<=n+1)dp[i+1][j-1]=(dp[i+1][j-1]+1ll*dp[i][j]*(j-1)%mod)%mod;
if(j>=1&&i+j+1<=n+1&&a[i+1]<b[i+j+1])dp[i+1][j]=(dp[i+1][j]+1ll*dp[i][j]*2%mod*j%mod)%mod;
if(i+j+2<=n+1&&a[i+1]<b[i+j+1]&&a[i+1]<b[i+j+2])dp[i+1][j+1]=(dp[i+1][j+1]+1ll*dp[i][j]*(j+1)%mod)%mod;
}
cout<<dp[n][1]<<endl;
}