C.Darkness I
题意：有一个n*n的方格，最开始全是白色，如果白色周围4格有两个黑色格子，1秒后这个白色格子会变成黑色，问如果要使全部格子都变为黑色，最开始最少需要涂黑几个格子
Solution
对于两个黑色格子，只有当满足
\[|x_1-x_2|+|y_1-y_2|≤2 \]才能涂黑以这两个格子为顶点的矩形的所有黑色格子，所以答案就是将两条边间隔涂黑，也可以是先铺对角线，再隔一列放一个，答案就是
\[[\frac{abs(n-m)}{2}]+min(n,m) \]void solve() //另一种AC写法
{
int n,m;cin>>n>>m;
if(n>m)swap(n,m);
if(n==1)cout<<m/2+1<<'\n';
else
{
int flag1=n&1,flag2=m&1;
if(flag1&&flag2)cout<<(n+1)/2+(m+1)/2-1<<"\n";
else if(flag1&&!flag2)cout<<(n+1)/2+m/2<<'\n';
else if(!flag1&&flag2)cout<<(m+1)/2+n/2<<'\n';
else cout<<m/2+n/2<<'\n';
}
}
M. Different Billing
题意：Once upon a time，有一个比赛（笑），A类队伍不收钱，B类队伍收1000，C类队伍收2500，一共有x个队伍，收了y元，构造出一个可能的答案
Solution
暴力枚举b类队伍即可
void solve()
{
int x,y;cin>>x>>y;
for(int i=0;i<=x;i++)
{
int z=y-1000*i;
if(z%2500==0&&z/2500+i<=x)
{
cout<<x-i-z/2500<<" "<<i<<" "<<z/2500<<"\n";
return;
}
}
cout<<"-1\n";
}
H.Binary Craziness
题意：给出一个有自环和重边的图，令sum有
\[sum=\sum\limits_{i=1}^{n}\sum\limits_{j=i}^{n}f(deg[i],deg[j]) \]其中
\[f(i,j)=(i⊕j)(i|j)(i\&j) \]求sum的值
Solution
也是暴力，因为最终的度数的种类不会很多，直接unordered_map暴力
int deg[N];
int f(int i,int j)
{
return (((i^j)*(i&j))%mod*(i|j))%mod;
}
void solve()
{
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;cin>>u>>v;
deg[u]++;
deg[v]++;
}
unordered_map<int,int>mp;
for(int i=1;i<=n;i++)mp[deg[i]]++;
int ans=0;
for(auto x:mp)
{
for(auto y:mp)
{
if(x==y)continue;
int xa=x.first,xb=x.second;
int ya=y.first,yb=y.second;
ans=((ans+(f(xa,ya)*xb)%mod*yb)%mod)%mod;
}
}
cout<<(ans*ksm(2,mod-2))%mod<<"\n";
}
J.Expansion
题意：有长为n的一行树，每个树都有能量，小马在第1s开始到达第一格，并且小马在每1s的开始可以走到下一格或者不动，在每1s的末尾可以获得已经走过的树的所有能量之和，要求任何时刻甚至是走到最末尾的位置并且在以后无限的时间内能量都不小于0，问在这种情况下第几秒走到最末尾的位置
Solution
贪心的思想，用前缀和表示停留在每个位置每秒所得到的能量，走路花的时间固定不变，那么变化的就是停留的时间，我们贪心地去想就是找到比停留在当前位置每秒所得到的能量更多的位置，再模拟一遍这个过程即可
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
if(s[1]<0)//特判
{
cout<<"-1\n";
return;
}else if(s[1]>=0)
{
int pos=1;
for(int i=1;i<=n;i++)
{
pos=i;
if(s[i]!=0)break;
}
if(s[pos]<0)
{
cout<<"-1\n";
return;
}
}
int last=-1;
for(int i=1;i<=n;i++) //把从第一个大于0的位置和接下来大于上一个位置的都计入
{
if(last==-1&&s[i]>0)
{
last=s[i];
tar[++cnt]=i;
}else if(last!=-1&&s[i]>last)
{
last=s[i];
tar[++cnt]=i;
}
}
int ans=n;
int now=s[1];
int pos=1;
for(int i=1;i<=cnt;i++)
{
if(pos==tar[i])continue;
int l=pos,r=tar[i];
for(int i=l+1;i<=r;i++)
{
now+=s[i];
if(now<0)
{
int t=(abs(now)+s[pos]-1)/s[pos];
ans+=t;
now+=t*s[pos];
}
}
pos=tar[i];
}
if(pos!=n)
{
int l=pos,r=n;
for(int i=l+1;i<=r;i++)
{
now+=s[i];
if(now<0)
{
int t=(abs(now)+s[pos]-1)/s[pos];
ans+=t;
now+=t*s[pos];
}
}
pos=n;
}
if(s[n]>=0)cout<<ans<<'\n';
else cout<<"-1\n";
}
F. Inverse Manacher
题意：有一个ab组成的字符串，在每个字符的中间和首字符左边以及末尾字符的右边加入字符'|',然后首字符的左边加入字符'&'，对于每个i，a[i]表示以i为正中间字符的最长回文字符串的长度除以二向上取整，构造出原字符串
Solution
比较简单，直接把第一位构造成a，然后根据每一个字母位上的值来构造出回文字符串，根据末尾的'|'的值来判断下一个是否和上一个字母相同
char c[N];
int a[N];
void solve()
{
int n;cin>>n;
for(int i=0;i<=2*n+1;i++)cin>>a[i];
c[0]='&';
c[1]='|';
c[2]='a';
for(int i=2;i<=2*n+1;i++)
{
if(!(i&1))
{
int cnt=(a[i]-1)/2;
for(int j=1;j<=cnt;j++)
{
c[i+j*2]=c[i-j*2];
}
int p=c[i+a[i]-2]-'a';
if(a[i+a[i]-1]==1)p^=1;
c[i+a[i]]=p+'a';
i=i+a[i]-1; //跳到下一个字母位
}
}
for(int i=2;i<=2*n+1;i+=2)cout<<c[i];
}
K.Dice Game
题意：有n+1个人丢一个m面骰子，丢出最小的一面的人会输，如果多个人丢出最小的一面，则这些人重丢，第1个人会只会丢出i，求i=1,2,..,m的时候，第一个人输的概率
很显然啊答案就是
\[ans=(\sum\limits_{i=1}^{+∞}\frac{1}{m^i}*\frac{m-i}{m})^n \]即
\[ans=(\frac{m-i}{m-1})^n \]void solve()
{
int n,m;cin>>n>>m;
int inv=ksm(m-1,mod-2);
for(int i=1;i<=m;i++)
{
if(i==1)
{
cout<<1<<' ';
continue;
}else if(i==m)
{
cout<<0<<" ";
continue;
}
cout<<((ksm(m-i,n)%mod)*ksm(inv,n))%mod<<" ";
}
}
I.Step
题意：给出n个环，每个环的位置1都有一个pony，每个pony在第i天会走距离i，问除了第0天以外最少需要几天才能使所有pony都在位置1
Solution
变相的问使得t*(t+1)/2是LCM(a[1],a[2],...,a[n])的倍数的最小的t
对2*LCM进行分解质因数，因为t与t+1是互质的，所以每个质因数只能属于其中一个，对其进行枚举，然后令t=ax,t+1=by，有ax+1=by
即求-ax+by=1成立的最小的ax，这里用扩展欧几里得可以算出
int a[N];
int s[N]; //数量
int num[N];//质数
int cnt=0;
int exgcd(int a, int b, int &x, int &y) {
if(!b)
{
x = 1;
y = 0;
return a;
}
int ans = exgcd(b, a%b, x, y);
int t = x;
x = y;
y = t - a / b * y;
return ans;
}
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int ans=a[1];
for(int i=2;i<=n;i++)ans=lcm(ans,a[i]);
int xx=ans*2;
for(int i=2;i*i<=xx;i++) //分解只因数
{
if(xx%i==0)
{
int cnt1=0;
while(xx%i==0)
{
xx/=i;
cnt1++;
}
s[++cnt]+=cnt1;
num[cnt]=i;
}
}
if(xx>1)
{
s[++cnt]++;
num[cnt]=xx;
}
int res=1e18;
for(int i=0;i<=(1<<cnt)-1;i++) //枚举
{
int tp=i;
int a=1,b=1;
for(int j=1;j<=cnt;j++)
{
if(tp&1)for(int k=1;k<=s[j];k++)a*=num[j];
else for(int k=1;k<=s[j];k++)b*=num[j];
tp>>=1;
}
int x,y;
int pp=gcd(a,b);
if(pp!=1)continue;
exgcd(a,b,x,y);
//cout<<"a , b = "<<a<<","<<b<<"\n";
//cout<<"x , y = "<<x<<","<<y<<"\n";
x=-x;
if(x<=0)x+=b;
res=min(res,a*x);
}
//cout<<ans<<"\n";
cout<<res<<"\n";
}