link
D.[R44D]好玩的游戏
link
构造。异或前缀和套路题。
计apiadux选的数异或和为\(SA\),jiangly选的数异或和为\(SB\)。
首先可以发现，对于\(t_i=0\)的限制，就是要让\(SA\)和\(SB\)相等。
等价于令\(SA \oplus SB=0\)。
即\(a_l \oplus a_{l+1} \oplus .... \oplus a_r=0\)
写成前缀异或和的形式即为$sum_r \oplus sum_{l-1}=0 $。
可以用并查集维护相等关系。
对于\(t_i=1\)的限制，即为\(sum_r \oplus sum_{l-1} \neq 0\)。
检查\(sum_r\)和\(sum_{l-1}\)是否相等（在同一联通快内）。
若相等即无解。
最后把前缀异或和转为\(a\)数组即可。
但要求权值在\([1,10^9]\)之间，则若\(a_i=0\)也不合法。
code
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 2e15
#define eps 1e-9
#define endl "\n"
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=3e5+5,M=1e3+5;
const int mod=998244353;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
int n,q,f[N],siz[N],colour[N],s[N],a[N];
struct query{ int l,r,t; }game[N];
map<pair<int,int>,bool>mp;
inline int find(int x){if(f[x]==x) return x;return f[x]=find(f[x]);
}
inline void merge(int x,int y){int xx=find(x),yy=find(y);if(xx==yy) return ;if(siz[xx]>siz[yy]) swap(xx,yy);f[xx]=yy,siz[yy]+=siz[xx];return ;
}
signed main(){int T=read();while(T--){n=read(),q=read();mp.clear();for(int i=1;i<=q;i++) game[i].l=read(),game[i].r=read(),game[i].t=read(),mp[{game[i].l,game[i].r}]=game[i].t;bool wj=0;for(int i=0;i<=n;i++) f[i]=i,siz[i]=1,colour[i]=0;for(int i=1;i<=q;i++)if(!game[i].t) merge(game[i].l-1,game[i].r);for(int i=1;i<=q;i++)if(game[i].t && find(game[i].l-1)==find(game[i].r)) wj=1;if(wj){puts("-1");continue;}int cnt=0;for(int i=0;i<=n;i++){if(!colour[find(i)]) s[i]=++cnt,colour[(find(i))]=cnt;else s[i]=colour[(find(i))];}for(int i=1;i<=n;i++) a[i]=s[i]^s[i-1];for(int i=1;i<=n;i++) if(!a[i]) wj=1;if(wj){puts("-1");continue;}for(int i=1;i<=n;i++) cout<<a[i]<<" \n"[i==n];}return 0;
}
/*
t=0 => sum[r]^sum[l-1]=0
t=1 => sum[r]^sum[l-1]!=0
*/
E.[R44E]路径数为K
link
依旧构造。
发现\(n \leq 50\),在\(log_{2}{k}\)和\(2log_{2}{k}\)之间，所以尝试\(1log\)的构造方案。
先考虑对\(k\)进行二进制拆分。
考虑如何构造这样的图。
令\(v_i\)表示\(2^i\)。
则有如下构造：
即对于每一个\(v_i\)都将它与\(v_{0} \sim v_{i-1}\)以及\(n\)连边。
这样对于每一个\(v_i\)点，它到\(n\)号点的路径数量均为\(2^i\)。
而\(k\)的二进制中第\(i\)位为1,1号点就向\(v_i\)连边。
例如\(k=5\)时的连边状态：
code
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 2e8
#define eps 1e-9
#define endl "\n"
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=4e5+5,M=1e3+5;
const int mod=998244353;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
int k,n,m,a[N],top;
signed main(){int T=read();while(T--){k=read();if(k==1){printf("2 1\n1 2\n");continue;}int now=0;top=0;while(k){if(k&1) a[++top]=now+1;++now,k>>=1;}n=a[top]+2;m=1;for(int i=3;i<=n-1;i++)for(int j=2;j<i;j++)++m;m+=(n-3+top);cout<<n<<' '<<m<<'\n';cout<<2<<' '<<n<<'\n';for(int i=3;i<=n-1;i++){for(int j=2;j<i;j++)cout<<i<<' '<<j<<'\n'; cout<<i<<' '<<n<<'\n';}for(int i=1;i<=top;i++)cout<<1<<' '<<a[i]+1<<'\n';}return 0;
}