构造好题
CF1270G Subset with Zero Sum
这是一道很好的图论构造题。
题目中的 \(i-n\le a_i\le i-1\) 经过调换改为 \(1\le i-a_i\le n\)，可以发现 \(\sum a_i=0\) 与 \(\sum i=\sum i-a_i\) 等价。此时便可以从 \(i\) 向 \(i-a_i\) 连一条边，由于是 \(n\) 个点，\(n\) 条边的图，因此至少有一个环。对这个环上的节点编号求和，便会得到之前的等式，因此就找见了一个满足的解。
此题的妙处在于通过确定 \(a_i\) 的范围想到连边，再想到是通过求和的方式转换为找环。
code
#include
using namespace std;
const int N=1e6+5;
int t;
int n,a[N],to[N],flag[N],d[N],u,cnt;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
to[i]=i-a[i];
flag[i]=0;
}
for(int i=1;i<=n;i++)
{
u=i,cnt=0;
while(u&&!flag[u])
{
flag[u]=1;
d[to[u]]=d[u]+1;
u=to[u];
}
if(u)
{
printf("%d\n%d ",d[u]-d[to[u]]+1,u);
break;
}
}
flag[u]=0;
u=to[u];
while(flag[u]) printf("%d ",u),u=to[u];
printf("\n");
}
return 0;
}
CF1427E Xum
这是一道很好的数学构造题。
首先容易发现一个偶数与它后面的那个奇数异或和为 \(1\)，那么只需要找到这样的两个数即可。
设其中的偶数为 \(m\)，奇数为 \(n\)，则只需 \(n-m=1\)，思考如何与 \(x\) 产生联系。
不妨设 \(n\) 为 \(x\) 的倍数，\(m\) 为 \(y\) 的倍数，即转为 \(ax-by=1\)，成为了扩展欧几里德的模版，由裴蜀定理得，对于一对 \(x,y\)，当且仅当 \((x,y)=1\) 时，必能找到一对正数解 \(a,b\)，并且 \(b\) 为偶数。
问题转化为找到一个数 \(y\)，使得 \((x,y)=1\)。
一个神奇的操作：设 \(2^e\le x<2^{e+1}\)，那么令 \(y=2^ex\oplus x=2^ex+x-2\times 2^e=(2^e+1)x-2^{e+1}\)，此时 \((x,y)=(x,(2^e+1)x-2^{e+1})=(x,2^{e+1})=1\)，满足要求，并且可以通过和与异或的方式实现。
code
#include
using namespace std;
#define int long long
int x,y;
int e,f,g;
int u,v;
int xt,yt;
int xf,yg;
int c[1000005][3],cnt;
int lowbit(int a)
{
return a&(-a);
}
void add(int a,int b,int opt)
{
c[++cnt][0]=a;
c[cnt][1]=b;
c[cnt][2]=opt;
}
void print(int a,int b,int opt)
{
if(opt==0) printf("%lld + %lld\n",a,b);
else printf("%lld ^ %lld\n",a,b);
return;
}
void exgcd(int a,int b)
{
if(b==0)
{
xt=1;
yt=0;
return;
}
exgcd(b,a%b);
int z=xt;
xt=yt;
yt=z-a/b*yt;
return;
}
void mul(int a,int b)
{
u=lowbit(a);
int sum=u*b;
a-=u;
for(;a;a-=lowbit(a))
{
u=lowbit(a);
add(sum,u*b,0);
sum+=u*b;
}
}
signed main()
{
scanf("%lld",&x);
e=log2(x),y=x;
for(int i=1;i<=e;i++) add(y,y,0),y<<=1;
xf=y;
add(x,y,1),y^=x;
yg=y;
exgcd(x,y);
yt=-yt;
while(xt<0||yt<0||yt%2==1) xt+=y,yt+=x;
while(xt>2*y&&yt>2*x) xt-=2*y,yt-=2*x;
f=log2(xt),g=log2(yt);
for(int i=e+1;i<=f;i++) add(xf,xf,0),xf<<=1;
for(int i=1;i<=g;i++) add(yg,yg,0),yg<<=1;
mul(xt,x),mul(yt,y);
add(xt*x,yt*y,1);
printf("%lld\n",cnt);
for(int i=1;i<=cnt;i++) print(c[i][0],c[i][1],c[i][2]);
return 0;
}