ARC156
A
简单分类讨论
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
char s[MAXN];
int T;
int n;
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
scanf("%s",s+1);
int Cnt=0;
for(int i=1;i<=n;i++)
{
if(s[i]=='1')
{
++Cnt;
}
}
if(Cnt&1)
{
printf("-1\n");
}
else
{
if(Cnt==2)
{
int f=0;
for(int i=1;i<n;i++)
{
if(s[i]=='1'&&s[i+1]=='1')
{
f=i;
}
}
if(f)
{
if(n==3||n==2)
{
printf("-1\n");
}
else if(n==4)
{
if(f==2)
{
printf("3\n");
}
else
{
printf("2\n");
}
}
else
{
printf("2\n");
}
}
else
{
printf("1\n");
}
}
else
{
printf("%d\n",Cnt/2);
}
}
}
}
B
考虑枚举我填的数最\(i\)是多少,然后用剩下的次数填到小于\(i\)的数
#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+5;
const int MOD=998244353;
int n,k;
int a[MAXN];
int fac[MAXN];
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int inv_fac[MAXN];
int inv(int a,int p)
{
return Pow(a,p-2,p);
}
int C(int n,int m)
{
if(m<0||n<m)
{
return 0;
}
if(m==0||n==m)
{
return 1;
}
return ((((long long)fac[n]*inv_fac[m])%MOD)*(inv_fac[n-m]))%MOD;
}
int Vis[MAXN];
int main()
{
fac[0]=1;
for(int i=1;i<=MAXN-5;i++)
{
fac[i]=((long long)fac[i-1]*i)%MOD;
}
inv_fac[MAXN-5]=inv(fac[MAXN-5],MOD);
for(int i=MAXN-5-1;i>=0;i--)
{
inv_fac[i]=((long long)inv_fac[i+1]*(i+1))%MOD;
}
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
Vis[a[i]]=1;
}
int Res=0;
for(int i=0;i<=MAXN-5;i++)
{
// printf("%d %d?\n",i,=);
if(Vis[i])
{
continue;
}
// printf("%d?\n",i);
if(k)
{
Res=((long long)Res+(C(i-1+k,k)))%MOD;
// printf("%d %d?\n",i-1+k,k);
k--;
}
else
{
Res++;
break;
}
}
printf("%d",Res);
}
C
智慧题?
大胆猜想答案是\(1\)
具体构造是每次选叶子然后交换\(P_i,P_j\)之后删去
证明的话考虑我们实际上就是想让\((i,P_i)\)是交叉的,而这样构造后一条链的\((i,j)\)前面的肯定不会产生贡献,而后面的因为交错了也不会有贡献
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n;
int x,y;
int Rd[MAXN];
vector<int>g[MAXN];
int P[MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
Rd[x]++;
Rd[y]++;
}
queue<int>q;
for(int i=1;i<=n;i++)
{
P[i]=i;
if(Rd[i]==1)
{
q.push(i);
}
}
while(q.size()>=2)
{
int t1=q.front();
q.pop();
int t2=q.front();
q.pop();
swap(P[t1],P[t2]);
for(int i=0;i<g[t1].size();i++)
{
int v=g[t1][i];
Rd[v]--;
if(Rd[v]==1)
{
q.push(v);
}
}
for(int i=0;i<g[t2].size();i++)
{
int v=g[t2][i];
Rd[v]--;
if(Rd[v]==1)
{
q.push(v);
}
}
}
for(int i=1;i<=n;i++)
{
printf("%d ",P[i]);
}
}
D
首先我们构造函数\(F(x)=(\sum x^{A_i})\),我们要求的就是\(F^k(x)\)中奇数次项的异或和
注意到\(F^2(x)=(\sum x^{2A_i})\)(对系数\(\bmod 2\))
可以发现\(2\)的次幂的次数相当于是对每个\(A_i\times2^k\)
如果我们对\(k\)二进制拆分,于是我们可以将次数缩减为\(log\)级别
然后考虑对这些物品\(dp\),设\(dp_{i,x}\)为前\(i\)位,\(sum\bmod 2^{i}=x\)的方案数\(\bmod 2\)
注意到这样不会影响到前面的位置,所以我们只用计算前一个二进制位哪些\(x\)能被算贡献即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2005;
int n;
long long k;
int a[MAXN];
int dp[MAXN];
int Tmp[MAXN];
int Rtm[MAXN];
int main()
{
scanf("%d %lld",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int Cnt=0;
int last=0;
long long Res=0;
dp[0]=1;
while(k)
{
if(k&1ll)
{
long long Po=(1<<(Cnt-last));
for(int i=0;i<=MAXN-5;i++)
{
Tmp[i]=dp[i];
dp[i]=0;
Rtm[i]=0;
}
for(int i=0;i<=MAXN-5;i++)
{
if(Tmp[i])
{
for(int j=1;j<=n;j++)
{
Rtm[i%Po]^=1;
dp[(i/Po)+a[j]]^=1;
}
}
}
int Rp=0;
for(int i=0;i<=MAXN-5;i++)
{
if(Rtm[i])
{
Rp^=i;
}
}
Res=(Res+(1ll<<last)*Rp);
last=Cnt;
}
k>>=1ll;
Cnt++;
}
int Rp=0;
for(int i=0;i<=MAXN-5;i++)
{
if(dp[i])
{
Rp^=i;
}
}
Res=(Res+(1ll<<last)*Rp);
printf("%lld\n",Res);
}
E
太难了/kk