A
签到
#include<bits/stdc++.h>
using namespace std;
int n,m,s[],t[],ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=,x;i<=n;i++)scanf("%d",&x),s[x&]++;
for(int i=,x;i<=m;i++)scanf("%d",&x),t[x&]++;
ans=min(s[],t[])+min(s[],t[]);
printf("%d",ans);
}
B
要求40次，而log(1e6)≈20，也就是说最多20个二进制位，可以每次翻转最高的“0”位，然后再+1即可。证明：若为11...10...00，则翻转最高0位后直接结束；若为全1，也是直接结束；若后面存在1，翻转后必然存在0，使得最高位向后走。
#include<bits/stdc++.h>
using namespace std;
int n,m,tim,a[];
bool judge(int x)
{
int flag=;
for(int i=;i>=;i--)
if(x&(<<i))flag=;
else if(!flag)return ;
return ;
}
int main()
{
cin>>n;
while(!judge(n))
{
tim++;
if(tim&)
{
int flag=;
for(int i=;i>=;i--)if(n&(<<i))flag=;else if(!flag){a[++m]=i+;break;}
n^=(<<a[m]+)-;
}
else n++;
}
printf("%d\n",tim);
for(int i=;i<=m;i++)printf("%d ",a[i]);
}
C
签到，开始还看成了最大公约数，自闭。其实就是枚举差值的每个因数，暴力加一下即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,d,ans,mn;
void work(ll x)
{
ll t=(x-a%x)%x,A=a+t,B=b+t,g=A/__gcd(A,B)*B;
if(g<mn)mn=g,ans=t;
else if(g==mn&&t<ans)ans=t;
}
int main()
{
cin>>a>>b;
if(a==b){cout<<;return ;}
if(a>b)d=a-b;else d=b-a;
mn=a/__gcd(a,b)*b;
for(ll i=;i*i<=d;i++)
if(d%i==)work(i),work(d/i);
cout<<ans;
}
D
被这题搞自闭了，看到什么最大值对1e9+7取模以为是个神仙题，后来才发现是个SB贪心题，其实就是能选的边尽量选，后来证明了一下：只有一个儿子显然，有两个儿子可以证明：如果自己能选没选，那么两个儿子的边也只能选1个，还会影响后面，如果自己不能选，随机选一个是也是对的。然后可以f[i][j][0/1]表示走了i步，前缀和为j，该点与父亲的边是否被选的节点数有几个，直接暴力转移即可。
#include<bits/stdc++.h>
using namespace std;
const int N=,mod=1e9+;
int n,ans,f[*N][N][];
void add(int&x,int y){x=(x+y)%mod;}
int main()
{
scanf("%d",&n);
f[][][]=;
for(int i=;i<=*n;i++)
for(int j=;j<=n;j++)
{
int lc=n+,rc=n+;
if(j+<=*n-i-)lc=j+;
if(j)rc=j-;
if(lc>n&&rc>n)continue;
if(f[i][j][])
{
if(lc<=n&&rc<=n)add(f[i+][lc][],f[i][j][]),add(f[i+][rc][],f[i][j][]);
else if(lc<=n)add(f[i+][lc][],f[i][j][]);
else add(f[i+][rc][],f[i][j][]);
}
if(f[i][j][])
{
if(lc<=n)add(f[i+][lc][],f[i][j][]);
if(rc<=n)add(f[i+][rc][],f[i][j][]);
}
}
for(int i=;i<=*n;i++)
for(int j=;j<=n;j++)
if(f[i][j][])add(ans,f[i][j][]);
printf("%d",ans);
}
E
被D搞自闭了，E也不会了。其实这道题有一种很神奇的做法：首先当然把b[i]>c[i]的判掉，然后不难发现相邻2个值中一定一个是最大值，另一个是最小值，然后连接(n-1)条(b[i],c[i])的无向边，然后跑一遍欧拉路，若存在长度为n的欧拉路就可以输出解了。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+;
int n,m,cnt,tot,a[N],b[N],c[N],w[N],hd[N],v[N<<],nxt[N<<],vis[N],du[N];
map<int,int>id;
void add(int x,int y)
{
v[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt,du[x]++;
v[++cnt]=x,nxt[cnt]=hd[y],hd[y]=cnt,du[y]++;
}
int getid(int x)
{
if(!id[x])w[id[x]=++tot]=x;
return id[x];
}
void euler(int u)
{
for(int &i=hd[u];i;i=nxt[i])
if(!vis[i>>])vis[i>>]=,euler(v[i]);
a[++m]=u;
}
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)scanf("%d",&b[i]);
for(int i=;i<n;i++)scanf("%d",&c[i]);
cnt=;
for(int i=;i<n;i++)
if(b[i]>c[i]){puts("-1");return ;}
else add(getid(b[i]),getid(c[i]));
int S=,num=;
for(int i=;i<=tot;i++)if(du[i]&)S=i,num++;
if(num&&num!=){puts("-1");return ;}
euler(S);
if(m!=n){puts("-1");return ;}
for(int i=;i<=n;i++)printf("%d ",w[a[i]]);
}
F
神仙题，看某AC代码写了F1，大概是f[i][j][k]表示长为i，走j步，后面覆盖集合为k的方案数，直接根据题意转移状态。后来发现F2也没意思就是一样的做法，加个矩阵快速幂就行了，不过懒得写了。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+,mod=1e9+;
int n,k,m,ans,sz[],f[N][][];
int main()
{
scanf("%d%d%d",&n,&k,&m);
for(int i=;i<<<m;i++)sz[i]=sz[i>>]+(i&);
f[][][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<k;j++)
for(int S=;S<<<m;S++)
if(f[i][j][S])
{
int nS=((S<<)&((<<m)-));
f[i+][j][nS]=(f[i+][j][nS]+f[i][j][S])%mod;
f[i+][j+][nS|]=(f[i+][j+][nS|]+1ll*f[i][j][S]*(sz[S]+))%mod;
}
int sum=;
for(int S=;S<(<<m);S++)sum=(sum+f[i][k][S])%mod;
ans=(ans+1ll*sum*(n-i+))%mod;
}
printf("%d",ans);
}
新号打的，初始语言默认C差评，被卡了十几分钟CE不知道，十分不爽。
result：rank95 rating+=225 now_rating=1725