C-Constructive Problems Never Die_"蔚来杯"2022牛客暑期多校训练营7 (nowcoder.com)
容易知道，只要A中的数不是全部相同，就一定有解。
我们思考如何构造：
- 如果A中的数是一个排列，即其中的数两两不相同，最好的方法是把整个排列往右边错开一位。
- 因此可以找到A中每个数出现的第一个位置，只考虑这些位置，把它们向右错开一位排列下去。剩下的待填的数直接乱填就可以了，一定不会出现矛盾。
#define x first
#define y second
const int N=1e5+5;
typedef pair<int,int>PII;
int T;
vector<int>pos[N];
vector<PII>num;
int n;
int a[N],b[N],has[N];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++)pos[i].clear();
num.clear(); memset(has,0,sizeof(has));
int flag=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(i>1 && a[i-1]!=a[i])flag=1;
pos[a[i]].push_back(i); has[a[i]]=1;
}
if(!flag){ cout<<"NO"<<endl; continue;}
for(int i=1;i<=n;i++)
if(pos[i].size())num.push_back({i,pos[i][0]});
int len=num.size()-1;
b[num[0].y]=num[len].x;
for(int i=0;i<len;i++){
b[num[i+1].y]=num[i].x;
}
int k=1;
for(int i=1;i<=n;i++){
for(int j=1;j<pos[i].size();j++){
while(has[k])k++;
b[pos[i][j]]=k++;
}
}
printf("YES\n");
for(int i=1;i<=n;i++)printf("%d ",b[i]);
printf("\n");
}
return 0;
}
F-Candies_"蔚来杯"2022牛客暑期多校训练营7 (nowcoder.com)
可以发现两种删数的情况是一样的，所以我们遇到一对删掉一对就可以。
这样的操作很像括号匹配，考虑开一个栈来做。
由于是一个环，最后还需要对栈中的数首尾匹配。
const int N=1e5+5;
int n,x;
int a[N];
int stk[N],top;
int main(){
scanf("%d%d",&n,&x);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int res=0;
for(int i=1;i<=n;i++){
if(!top)stk[++top]=a[i];
else{
while(top && i<=n && (stk[top]==a[i] || stk[top]+a[i]==x)){
res++;
top--;
i++;
}
if(i<=n)stk[++top]=a[i];
}
}
int i=1,j=top;
while((stk[i]==stk[j] || stk[i]+stk[j]==x) && i<j){
res++;
i++; j--;
}
cout<<res<<endl;
return 0;
}
J-Melborp Elcissalc_"蔚来杯"2022牛客暑期多校训练营7 (nowcoder.com)
对于一个子序列\([l,r]\)，当满足\((sum[r]-sum[l-1])\%k=0\)，即\(sum[r]\%k=sum[l-1]\%k\)时，我们说这个子序列是好的。
由于数组中的数都在\([0,k-1]\)范围内，因此通过前缀和数组可以唯一得出原数组，所以我们只需要考虑前缀和数组就可以了。
如何计算出good区间的数量(goodness)？假设有\(sum[i]\%k=x\)，cnt[x]表示x出现的次数，则可以得出good区间的数量即为\(\sum_{x=0}^{k-1} C_{cnt[x]}^2\)。
所以问题转化成：构造出一个\(sum[]\)数组，\(cnt[x]\)表示每个\(sum[i]\%k\)的出现次数，满足\(\sum_{x=0}^{k-1} C_{cnt[x]}^2=t\)。但是直接考虑构造sum数组会很难维护cnt和上述和式，所以我们考虑构造cnt。
构造出的cnt只需要满足\(\sum cnt[i]=n\)即可。
设数组f[i][j][p]表示考虑到了第i种数，当前选择数的总个数为j个，当前的goodness值是p的所有方案，属性是构造出的数组种类数。
可以得出转移方程f[i][j][p]+=f[i-1][x][y]*C[n-x][j-x], p=y+C[j-x][2]
C[n-x][j-x]表示剩下还有n-x个位置需要选数，我们把其中的j-x个选成i的方案数。C[j-x][2]表示当前选择j-x个i能够贡献的goodness。
可以写成正推的形式：
ll &v=f[i][j+num][u+C[num+(i==1)][2]];
v=(v+f[i-1][j][u]*C[n-j][num]%p)%p;
其中，当i==1时，表示正在考虑数“0”，由于前缀和s[0]==0，所以我们实际上要多考虑一个0，可以写成num+(i==1)
const int N=72,p=998244353;
typedef long long ll;
int n,k,t;
ll f[N][N][N*N];
int C[N][N];
int main(){
C[0][0]=1;
for(int i=1;i<=N-3;i++){
for(int j=0;j<=i;j++){
if(i==j || j==0)C[i][j]=1;
else C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
}
}
scanf("%d%d%d",&n,&k,&t);
f[0][0][0]=1;
for(int i=1;i<=k;i++){
for(int j=0;j<=n;j++){
for(int u=0;u<=t;u++){//实际上u和num循环顺序可以对调，为了可以做下面的剪枝，我们把u循环放在前面
if(f[i-1][j][u]==0)continue;//剪
for(int num=0;num+j<=n;num++){
if(u+C[num+(i==1)][2]>t)break;
ll &v=f[i][j+num][u+C[num+(i==1)][2]];
v=(v+f[i-1][j][u]*C[n-j][num]%p)%p;
}
}
}
}
cout<<f[k][n][t]<<endl;
return 0;
}
K-Great Party_"蔚来杯"2022牛客暑期多校训练营7 (nowcoder.com)
如果只有1堆石头，肯定是先手必胜。
如果有2堆石头：
- 两堆石头都是1个，那么先手必败。
- 一堆是1个，另一堆是x个，先手可以拿x-1个后把必败局留给后手，先手必胜。
- 两堆都是两个。如果先手拿一个石头且不合并，后手也拿一个留下1，1的必败局给先手；如果先手拿一个石头且合并，后手直接拿完；如果先手拿一堆，后手直接拿完。所以这种情况先手必败。
- 如果两堆都是x个。无论先手拿多少个，后手可以做对称操作，最后一定会变成上述[1],[2]的局面，先手必输。
- 如果两堆数量不同。先手可以拿到两堆数量相同，所以后手就面临了[4]的必败局面，此时先手必胜。
如果有三堆石头：
-
如果是1，1，1：先手必胜。
-
如果是2，2，2：先手拿走一堆，后手面临2，2必败
-
如果2，2，3：同理，先手必胜
-
如果4，5，6：先手拿5个，剩下一个合进4，后手面临5，5必败
总的来说，先手赢麻了。
如果有四堆石头：没有人会做合并操作，否则就会把必胜的局面留给对方，所以最后石子一定是1，1，1，1....的情况。
在奇数堆的情况下，推广结论可知：先手必胜。（不知道怎么推的......）
在偶数堆的情况下：没有人会做合并操作把奇数的情况让给对方，因此偶数一定不合并。那么最后拿来拿去一定会变成每堆石子只有1个的情况，因为有偶数堆，因此谁当前面对这个情况谁就死。考虑如何计算最后谁面对这个情况。考虑每堆石子的数量为\(a[i]-1\)，把它们拿完后最后拿不了的人面临的就是全1的情况，这可以套经典nim，即看区间异或和是否为0。
考虑莫队离线处理每个询问，以右端点r增加1为例，增加的区间数目只需要考虑以r+1结尾的子区间的不满足条件的数目的偶数区间即可，即看\([l-1,r]\)中有多少个\(S[i]\ xor\ S[r+1]=0\)，这是可以\(O(1)\)维护的，最后的结果就是区间所有子区间减去这些不满足条件的偶区间的数目。
const int N=1e5+5,S=1e6+5;
typedef long long ll;
int n,m;
int a[N],s[N];
int f[2*S],g[2*S];//f记录奇数位置、g记录偶数位置
int len,idx[N];
ll ans[N];
struct que{
int id,l,r;
}q[N];
void add(int p,int &res){
if(p&1){
res+=f[s[p]];//因为我们记录的左端点都是l-1，所以奇偶要换一下
f[s[p]]++;
}
else{
res+=g[s[p]];
g[s[p]]++;
}
}
void del(int p,int &res){
if(p&1){
f[s[p]]--;
res-=f[s[p]];
}
else{
g[s[p]]--;
res-=g[s[p]];
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]--;
s[i]=s[i-1]^a[i];
}
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
q[i]={i,x-1,y};//区间应该是[l-1,r]
}
len=sqrt(n);
for(int i=0;i<=n;i++)idx[i]=i/len;
sort(q+1,q+m+1,[](struct que a,struct que b){
if(idx[a.l]!=idx[b.l])return idx[a.l]<idx[b.l];
return a.r<b.r;
});
int res=0;
for(int k=1,i=1,j=0;k<=m;k++){
int id=q[k].id, l=q[k].l, r=q[k].r;
int tl=r-l;
while(j<r)add(++j,res);
while(j>r)del(j--,res);
while(i<l)del(i++,res);
while(i>l)add(--i,res);
ans[id]=(ll)(tl+1)*tl/2-res;
}
for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}