这把真不在状态，麻了，看来还得再练
A. A-characteristic
题意：给出n和k，要求构造只含1和-1数组a，存在k对(i,j)（i≠j），有a[i]*a[j]=1
Solution
令构造的数组有x个1和y个-1，那么其对于答案的贡献有
又因为有x+y=n，所以可以转化成关于x的一元二次方程
化简后有
接下来根据求根公式写即可
void solve()
{
int n,k;cin>>n>>k;
//x*(x-1)/2+y*(y-1)/2==k
//x+y=n;
int t=4*n*n-8*(-n-2*k+n*n);
if(t<0)
{
cout<<"NO\n";
return;
}
int l=sqrt(t);
if(l*l==t)
{
if((2*n-l)%4==0)
{
int oo=(2*n-l)/4;
if(oo>n||oo<0)
{
cout<<"NO\n";
return;
}
cout<<"YES\n";
for(int i=1;i<=oo;i++)cout<<"1 ";
for(int i=oo+1;i<=n;i++)cout<<"-1 ";
cout<<"\n";
}else if((2*n+l)%4==0)
{
int oo=(2*n+l)/4;
if(oo>n||oo<0)
{
cout<<"NO\n";
return;
}
cout<<"YES\n";
for(int i=1;i<=oo;i++)cout<<"1 ";
for(int i=oo+1;i<=n;i++)cout<<"-1 ";
cout<<"\n";
}else
{
cout<<"NO\n";
}
}else
{
cout<<"NO\n";
}
}
B. Sort with Step
题意：给出长为n且由[1,2,...,n]组成的数组a和一个数c
可以进行无数次操作：选择i和j使得|i-j|=c，交换a[i]和a[j]
可以进行一次且只能进行一次操作：选择任意的i和j，交换a[i]和a[j]
问是否能使得交换后的数组按升序排列
Solution
显然在第i位上的数要满足a[i]%n==i%n，所以直接统计不符合的数的个数，看是否为2，有解的情况必定为2或者0
void solve()
{
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
int res=0;
for(int i=1;i<=n;i++)
{
if((a[i]%k)!=(i%k))
{
res++;
}
}
if(res>2)
{
cout<<"-1\n";
}else if(res==2)
{
cout<<"1\n";
}else
{
cout<<"0\n";
}
}
C. Strongly Composite
题意：定义一个合数，其约数中，素数的个数小于或等于合数的个数，这样的合数为强合数，现在给出一个数组a，要求构造出数组b，使得a中元素之积等于b中元素之积，并且b中元素均为强合数，求构造出的数组b的最大长度
Solution
通过找规律可以发现，至少有3个不同的素数或者2个相同的素数的合数是强合数，那么我们可以对a中的所有元素进行分解质因数，然后统计一下成对的素数对数以及不同的素数个数
先全部乘起来再分解质因数居然会t，不理解
void solve()
{
int nn;cin>>nn;
map<int,int>mp;
map<int,int>::iterator it;
for(int i=1;i<=nn;i++)
{
int x;
cin>>x;
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
{
while(x%i==0)
{
mp[i]++;
x/=i;
}
}
}
if(x>1)mp[x]++;
}
int ans=0;
int res=0;
for(it=mp.begin();it!=mp.end();it++)
{
ans+=it->second/2;
res+=it->second%2;
}
cout<<ans+res/3<<"\n";
}
D. Unique Palindromes
题意：构造一个长为n的字符串，给出k个要求，其中第i个要求由s(1,x[i])(s从1开始)组成的字符串有c[i]个不同的回文子串
Solution
k给的比较小，在有要求的时候直接加入连续的下一个字母即可
其他的要求没有回文子串的地方用abcabcabc....这样子填补
void solve()
{
int n,k;cin>>n>>k;
for(int i=1;i<=k;i++)cin>>x[i];
for(int i=1;i<=k;i++)cin>>c[i];
string s;
int pos=3;
int last=0;
string tp;
int len=0;
while(len<n)
{
len+=3;
tp+="abc";
}
for(int i=1;i<=k;i++)
{
if(i==1&&c[i]<=x[i])
{
s="ab";
s+=string(c[i]-2,'c');
int z=x[i]-c[i];
s+=tp.substr(last,z);
last+=z;
}
else if(c[i]>x[i]||c[i]-c[i-1]>x[i]-x[i-1])
{
cout<<"NO\n";
return;
}else
{
int p=x[i]-x[i-1];
int z=c[i]-c[i-1];
s+=tp.substr(last,p-z);
last+=p-z;
s+=string(z,(char)('a'+pos));
pos++;
}
//cout<<s<<"\n";
}
cout<<"YES\n";
cout<<s<<"\n";
}
E. Removing Graph
题意：给出一个无向图和一个区间[l,r]，无重边和自环，其中所有的点度数均为2，Alice和Bob轮流进行以下操作：
选择一个有[l,r]个点连通子图，删去这些点和其所连的边
谁最后无法进行操作谁就输了
Solution
经典nim游戏，但是有坑，因为要选连通子图，把原图可以用并查集找到cnt个连通分量，因为所有点的度数均为2，那么每个连通分量都是一个环，在一次操作完后，原来是环的连通分量会变成一条链状连通分量，而链状连通分量在一次操作完后最多会变成两条链状连通分量
写出对应的sg函数后可以打表找出规律，发现对于i<l和i>l+r-1的sg函数都为0，其余的为i/l向下取整，后面的不用我多说了
debug一下午找不出为什么wa了，才发现要选连通子图.......
sg函数以及打表
int mex(set<int>&st)
{
for(int i=0;;i++)
{
if(st.find(i)==st.end())return i;
}
}
int sg(int x)
{
if(x<l)return 0;
if(dp[x]!=-1)return dp[x];
set<int>st;
for(int i=l;i<=r;i++)
{
for(int j=0;j<=x-i;j++)
{
st.insert(sg(j)^sg(x-i-j));
}
}
dp[x]=mex(st);
return dp[x];
}
void _table()
{
for(int i=1;i<=n;i++)
{
set<int>st;
for(int j=l;j<=min(i,r);j++)
{
st.insert(sg(i-j));
}
cout<<mex(st)<<"\n";
}
}
AC代码
int t[N];
int p[N];
int find(int x)
{
return t[x]==x?x:t[x]=find(t[x]);
}
int cnt=0;
int g[N];
int l,r,n;
int dp[N];
int mex(set<int>&st)
{
for(int i=0;;i++)
{
if(st.find(i)==st.end())return i;
}
}
int sg(int x)
{
if(x<l)return 0;
if(dp[x]!=-1)return dp[x];
set<int>st;
for(int i=l;i<=r;i++)
{
for(int j=0;j<=x-i;j++)
{
st.insert(sg(j)^sg(x-i-j));
}
}
dp[x]=mex(st);
return dp[x];
}
void solve()
{
memset(dp,-1,sizeof(dp));
cin>>n>>l>>r;
for(int i=1;i<=n;i++)
{
t[i]=i;
p[i]=1;
}
for(int i=1;i<=n;i++)
{
int x,y;cin>>x>>y;
int a=find(x),b=find(y);
if(a!=b)
{
t[a]=b;
p[b]+=p[a];
}
}
for(int i=1;i<=n;i++)
{
if(t[i]==i)g[++cnt]=p[i];
}
int ans=0;
for(int i=1;i<=cnt;i++)
{
int x=g[i]/l;
if(g[i]<l||g[i]>l+r-1)x=0;
ans^=x;
}
if(ans)cout<<"Alice\n";
else cout<<"Bob\n";
/*for(int i=1;i<=n;i++)
{
set<int>st;
for(int j=l;j<=min(i,r);j++)
{
st.insert(sg(i-j));
}
cout<<mex(st)<<"\n";
}*/
}