T1 里群
题解
阴间第一题
题目中有一个很明显的建图方法就是对于第 \(i\) 天入群的人在第 \(j\) 天退群
那么就在 \(i,j\) 之间连一条边
首先有一个结论，管理员个数不大于 \(3\)
对于这个结论，证明如下：
首先第一次删除出现后就一定需要两个管理员了
如果某次删除只删掉了某一个管理员添加的，那么另一个管理员当天值班就行
如果两个都删掉了，就需要第三个管理员
如果这时候某个管理员删的有三种，那么一定有一个管理的值班可以被替代
要删的区间内不可能每个管理都是天天删另外两个管理的人
因为这样的删除是必定会删除一天多一点或者两天的加入量的
在这段区间内的加入量赶不上删除量，总会有空出来可以替代的
自己多举点例子手模一下就可以了，不好描述清楚
所以无论如何都可以用三个管理员处理完所有情况
所以只需要分类讨论一下三种情况
如果只要一个管理就不能有删除
如果要两个管理那么按最上面的方法建的图就是一个二分图，判断是否为二分图即可
两种都不是那就是需要三个管理
对于任意两条边，每条边的两个端点分别组成一个区间
对于这两个区间只有不相交和包含两种关系，那么可以建一棵树来处理
每一个叶子节点就是一条边构成的区间，对于父节点来说，限制最紧的情况如下：
\([l,x_1],[x_1,x_2],[x_2,x_3],\cdots,[x_k-1,x_k],[x_k,r]\)
当然有可能中间的区间并没有拼接在一起
如果两端 \(l,r\) 分别是 \(1,2\) ，那么中间就可以用 \(3,1,3,1,3,1,\ldots\) 的方式拼接
算法就构建完了
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int n,a[N],b[N],prea[N],preb[N],col[N],mx = 0,stk[N],top = 0;
vector<int>e[N],g[N];
bool flag = 0,tag = 1;
void pb(int x,int y){
flag = 1;
e[x].push_back(y);
e[y].push_back(x);
return ;
}
void dfs(int x,int c){
col[x] = c;c^=1;
for(int i : e[x]){
if(col[i]!=-1){
if(col[i]!=c){
tag = 0;
return ;
}
continue;
}
dfs(i,c);
if(!tag) return ;
}
}
int main(){
freopen("group.in","r",stdin);
freopen("group.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--){
cin>>n;
for(int i = 1;i<=n;i++){
e[i].clear();
g[i].clear();
col[i] = -1;
}
for(int i = 1;i<=n;i++)
cin>>a[i]>>b[i];
flag = 0,tag = 1;top = 0;
for(int i = 1;i<=n;i++)
prea[i] = a[i],preb[i] = b[i];
for(int i = 1;i<=n;i++){
if(a[i]){
while(b[stk[top]]<=a[i]&&a[i]>0){
pb(stk[top],i);
a[i]-=b[stk[top]];
top--;
}
if(a[i]){
b[stk[top]]-=a[i];
pb(stk[top],i);
}
}
if(b[i]) stk[++top] = i;
}
for(int i = 1;i<=n;i++)
if(col[i]==-1) dfs(i,0);
if(!flag){
cout<<"1\n";
for(int i = 1;i<=n;i++)
cout<<"1 ";
cout<<"\n";
continue;
}
if(tag){
cout<<"2\n";
for(int i = 1;i<=n;i++)
cout<<col[i]+1<<" ";
cout<<"\n";
continue;
}
for(int i = 1;i<=n;i++)
a[i] = prea[i],b[i] = preb[i];
top = 0;
for(int i = 1;i<=n;i++){
if(a[i]){
while(b[stk[top]]<=a[i]&&a[i]>0){
g[i].push_back(stk[top]);
a[i]-=b[stk[top]];
top--;
}
if(a[i]) b[stk[top]]-=a[i];
}
stk[++top] = i;
}
for(int i = 1;i<=n;i++) col[i] = 0;
for(int i = 1;i<=top;i++)
col[stk[i]] = (i&1);
for(int i = n;i>=1;i--){
int u = col[stk[top]];top--;
int v = col[stk[top]],pos = 0,tmp = 0;
if(u==v) v++;
for(int j = 0;j<=2;j++)
if(j!=u&&j!=v) pos = j;
if(!g[i].size()) continue;
int idx[2] = {pos,v};
for(int j = g[i].size()-1;j>=0;j--){
int x = g[i][j];
stk[++top] = x;
col[x] = idx[tmp];
tmp^=1;
}
}
cout<<"3\n";
for(int i = 1;i<=n;i++)
cout<<col[i]+1<<" ";
cout<<"\n";
}
return 0;
}
有亿点点长
T2 xormex
题解
打表特判题，恶心吐了
通过打表可以发现强制 \(0\) 在最开头
这样可以使 \(xormex\) 变成了所有前缀 \(mex\) 的异或和，不是区间 \(mex\) 了，因为其他区间都为 \(0\)
不过需要特判一下 \(3 \ 2\) 的情况
再说判断无解
对于 \(n = 2^m,k<n\) 的情况一定无解，因为没有办法消除掉最高位的 \(1\) 而 \(k\) 最高位为 \(0\)
设数组 \(b_i\) 表示\([1,i]\) 的前缀 \(mex\) 和，明显有 \(b_1 = 1,b_n = n\)
设 $t = n \oplus 1 \oplus k $ , 只需要让 \((1,n)\) 区间内的 \(b\) 的异或和等于 \(t\) 就行了
大多数情况下，直接把 \(t\) 二进制拆位，然后把每一位从小到大放在 \(b\) 的最后几个位置即可。
问题在于对于前面几个贡献只有 \(1\) 的位置，如果有奇数个这样的位置, 就会导致异或和有 \(1\) 的差距
只需将第一个贡献不为 \(1\) 的位置改为 \(x \oplus 1\) 即可
对于最后一位是 \(n+1\) 的情况也需要特判，将最后三位改为 \(2,3,n\)
这道题总之就是特判就完了
对于 \(b\) 数组的还原就很简单了
#include<bits/stdc++.h>
#define N 140010
using namespace std;
int n,k,mex[N],b[N],a[N];
int popcount(int u){
u = (u&0x55555555)+((u>>1)&0x55555555);
u = (u&0x33333333)+((u>>2)&0x33333333);
u = (u&0x0f0f0f0f)+((u>>4)&0x0f0f0f0f);
u = (u&0x00ff00ff)+((u>>8)&0x00ff00ff);
u = (u&0x0000ffff)+((u>>16)&0x0000ffff);
return u;
}
int main(){
freopen("xormex.in","r",stdin);
freopen("xormex.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--){
cin>>n>>k;
int mx = 1;
while(mx*2<=n) mx*=2;
if(k>2*mx-1){
cout<<"-1\n";
continue;
}
if(popcount(n)==1&&k<n){
cout<<"-1\n";
continue;
}
if((n==2&&k==2)||(n==3&&k==2)){
cout<<"-1\n";
continue;
}
if(n==3&&k==1){
cout<<"1 0 2\n";
continue;
}
if((n%4==0&&k==n)||(n%4==1&&k==1)){
for(int j = 0;j<n;j++)
cout<<j<<" ";
cout<<"\n";
continue;
}
if(n%4==2&&k==n){
for(int j = 0;j+2<n;j++)
cout<<j<<" ";
cout<<n-1<<" "<<n-2<<"\n";
continue;
}
for(int i = 1;i<n;i++)
mex[i] = 1;
mex[n] = n;b[0] = 0;
int u = (n^1^k);
while(u){
b[++b[0]] = (u&-u);
u-=(u&-u);
}
for(int i = b[0];i;i--)
mex[n-b[0]+i-1] = b[i];
if(n>=5&&n%2==1&&k==n-1)
mex[n-1] = 3,mex[n-2] = 2;
int t = 0;
for(int i = 1;i<=n;i++) t^=mex[i];
if(t!=k){
for(int i = 2;i<=n;i++){
if(mex[i]!=1){
mex[i]^=1;
break;
}
}
}
for(int i = 1;i<=n;i++)
a[mex[i]] = 1;
cout<<"0 ";
for(int i = 2,j = 1;i<=n;i++){
if(mex[i]==1){
while(a[j]) j++;
cout<<j<<" ";
j++;
}else cout<<mex[i-1]<<" ";
}
cout<<"\n";
for(int i = 0;i<=n;i++) a[i] = 0;
}
return 0;
}
T3 可重集计数
题解
不是很会，直接贴题解
主要不是很明白容斥中 \(f\) 数组的表示
#include<bits/stdc++.h>
#define N 4010
using namespace std;
int n,m,k,mod,f[N][N],g[N][N],mx[N];
int getans(int m,int k){
if(k>mx[m]) return 0;
if(k<=m) return f[k][n];
int ans = 0,fl = 1;
for(int j = 0;j*(m+1)<=k;j++){
for(int x = j*(j+1)/2;x*(m+1)<=n;x++)
if(j&1) ans = (ans+1ll*(mod-g[j][x])*f[k-j*(m+1)][n-x*(m+1)])%mod;
else ans = (ans+1ll*g[j][x]*f[k-j*(m+1)][n-x*(m+1)])%mod;
fl = mod-fl;
}
return ans;
}
int main(){
freopen("multiset.in","r",stdin);
freopen("multiset.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>mod;
f[0][0] = g[0][0] = 1;
for(int i = 1;i<=n;i++)
for(int j = i;j<=n;j++)
f[i][j] = (f[i-1][j-1]+f[i][j-i])%mod;
for(int i = 1;i<=n;i++)
for(int j = i*(i+1)/2;j<=n;j++)
g[i][j] = (g[i-1][j-i]+g[i][j-i])%mod;
for(m = 1;m<=n;m++){
int tmp = 0,ti = 0;
for(int i = 1;i<=n&&tmp<=n;i++)
for(int j = 1;j<=m&&tmp<=n;j++)
tmp+=i,ti++;
if(tmp<=n) ti = n;
mx[m] = ti;
}
long long sum = 0;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
sum+=getans(i,j);
cout<<sum;
return 0;
}
T4
照例，不会，前三题都那样了还想T4？
标签：校内,int,top,cin,stk,--,231009,col From： https://www.cnblogs.com/cztq/p/17755866.html