T1 happy2
David 的朋友中有 \(n\) 个男生和 \(m\) 个女生, 还有 \(k\) 个跨性别者，方便起见，将他们分别编号为 \(0, ...n -1\) 和 \(0, ...m -1\), \(0 .. k- 1\)，在第 \(i\) 天，David会邀请编号为 \((i \bmod n)\) 的男生和编号为 \((i \bmod m)\) 的女生还有 \((i \bmod k)\)的跨性别者共进晚餐（因为 David 同时是程序员，所以从这个计划从第 \(0\)天开始）。共进晚餐的三个人只要至少有有一个是快乐的人，另外的人也会变得快乐起来。否则大家的状态不会改变（一旦一个人是快乐的，他就会永远快乐下去）。
现在问题来了，David 想知道他是否能通过这个计划使得所有人都快乐起来呢？
\(b,g,t 分别表示快乐的男生女生跨性别者快乐的个数\)
solution
emmm，考试的时候一点思路都没有，打了个暴力还写挂了。 呜呜呜。
正解：数论加找性质。
很显然我们会发现一个事情 \(lcm(n,lcm(m,k))\) 为一个周期，因此我们只需要考虑这一个周期中是否能使所有人快乐。
我们可以试一试打表，先考虑 \(k=0\) 的情况。
假设 \(n=6,m=9\) ,把每个男生会和那些女生吃饭打出来。
- 0 号男生和 0, 6, 3 号女生吃饭；
- 1 号男生和 1, 7, 4 号女生吃饭；
- 2 号男生和 2, 8, 5 号女生吃饭；
- 3号男生和 3, 0, 6 号女生吃饭；
- 4号男生和 4, 1, 7 号女生吃饭；
这时候你会发现 \(0\) 号男生和 \(4\) 号男生吃饭的对象是一样的，同时可以推测出 \(1\) 号和 \(5\) 号男生吃饭的对象是一样的。
同时还可以看出 0, 3, 6 号女生的吃饭对象也是一样的，1,4,7 号女生的吃饭对象也一样！
看到这里我们可以有一个大胆的猜测：编号之差为 \(gcd(n, m) = 3\) 的倍数的男/女生的吃饭对象是一样的，
且他们的吃饭对象与他们的编号之差也一定为 \(gcd\) 的倍数即对 \(gcd\) 取模的结果相同！
这样我们就得到了一种算法，首先求出 \(gd(n,m)\) ，然后根据每个男生/女生的编号按 模以 \(gcd\) 的模数分为 \(gcd\) 个等价类。
然后就会发现在每一等价类中只要有一个同学是快乐的，那么整个等价类都是快乐的。所以统计一下每个快乐的男生女生的编号。
看他们模以 \(gcd\) 的余数是否把 \(0-gcd-1\) 全部覆盖。
对于 \(k!=0\) 的情况，和上面同理。
复杂度（我不会算）
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e7+10;
int T,n,m,k,num1,num2,num3,flag;
bool vis[N];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
int gcd(int a,int b)
{
if(b == 0) return a;
else return gcd(b,a%b);
}
int main()
{
freopen("happy2.in","r",stdin);
freopen("happy2.out","w",stdout);
T = read();
while(T--)
{
memset(vis,0,sizeof(vis)); flag = 0;
n = read(); m = read(); k = read();
if(k == 0)
{
int Gcd = gcd(n,m);
num1 = read();
for(int i = 1; i <= num1; i++) vis[read() % Gcd] = 1;
num2 = read();
for(int i = 1; i <= num2; i++) vis[read() % Gcd] = 1;
num3 = read();
for(int i = 0; i < Gcd; i++)
{
if(!vis[i]) {flag = 1; break;}
}
}
else
{
int Gcd = gcd(gcd(n,m),k);
num1 = read();
for(int i = 1; i <= num1; i++) vis[read() % Gcd] = 1;
num2 = read();
for(int i = 1; i <= num2; i++) vis[read() % Gcd] = 1;
num3 = read();
for(int i = 1; i <= num3; i++) vis[read() % Gcd] = 1;
for(int i = 0; i < Gcd; i++)
{
if(!vis[i]) {flag = 1; break;}
}
}
if(!flag) printf("Yes\n");
else printf("No\n");
}
fclose(stdin); fclose(stdout);
return 0;
}
T2 嫌疑人
最近公司里的代码中发现了一个极其严重的 \(bug\) ，小组长 David 决定找出这个嫌疑人并惩罚他！为了找出嫌疑人，David 开了一个会。会上有 \(n\) 个程序员，每个程序员都发表了如下言论：“不是 \(x\) 干的就是 \(y\) 干的！”（不同程序员言语中的 \(x\) 与 \(y\) 不一定相同）David 决定选出两个嫌疑人，并请他们去他的办公室喝茶。当然 David 的选取方案会参考所有程序员们的建议。他想让他的选取方案至少有 \(p\) 个人支持。一个程序员会支持一个方案当且仅当至少有一个该程序员认定的嫌疑人被请去喝茶了。注意：假如某个程序员被选为两个嫌疑人之一，他甚至可能支持这个选取方案，只要选取的另一是他说的两个嫌疑人之一即可。
问你有多少种满足条件的方案，\((2,1)\) 和 \((1,2)\) 算一种。同时保证每个人的 \(x_i ！= i， y_i！=i，x_i !=y_i\)。
\(n\leq 3\times 10^5,p\leq n\)
solution
考试的时候想到了正解，但在树状数组处理的时候写挂了，挂到和暴力老哥同分，难受。
首先我们对于每个人的 \(x_i,y_i\) 分别连一条边，那么我们会得到一个 \(n\) 个点 \(2*n\) 条边的无向图。
然后我们的问题就转化为一个让你选两个点，满足与这两个相连的边的数量大于等于 \(p\) ,重复的边只算一次。
与每个点相连的边其实就是每个点相连的度数，考虑计算出选每个点的答案。
如果选 \(i,j\) 则需要满足 \(du[i] + du[j] \geq p\) 。
枚举一下 \(i\) , 那么 \(j\) 要满足 \(du[j] \geq p-du[i]\) ，那个树状数组维护一下 度数为 \(i\) 的点的个数的前缀和就可以。
合法方案就是 \(n-query(p-du[i]-1)\) . 然后你会发现你少考虑的好几种情况。
- 重边的情况，这时候我们不能直接算，加一减一的话处理起来很麻烦，（窝当时就这样写的，WA成三十分）。重边时候答案为 \(du[i] + du[j] - 1 \geq q\) , 如果\(du[i] + du[j] > p\) ，减去 \(1\) 之后大于 \(p\)的, 但 若\(du[i] + du[j] == p\) 则 \(du[i] + du[j]-1 == p-1\) 这时候他被我们多算了要减去，只需要遍历一遍出边，判断 \(du[i] + du[j] == p\) 是否成立就行。
- \(i\) 这个点被算上的情况， 按 \(i\) 度数的大小考虑， 如果 \(du[i] < p-du[i]\) 则在树状数组统计的时候我们会把他算进去。 \(du[i] \geq p-du[i]\) 的情况 特判一下就行
树状数组的值域是 \(1-n\) 所以要额外用 \(tr[0]\) 表示 \(0\) 度数点的个数。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N = 3e5+10;
int n,p,ans,x,y,tot;
int head[N],tr[N],du[N];
struct node
{
int to,net;
}e[N<<1];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
void add(int x,int y)
{
e[++tot].to = y;
e[tot].net = head[x];
head[x] = tot;
}
int lowbit(int x){ return x & -x;}
void chenge(int x,int val)
{
if(x == 0) tr[0] += val;
else for(; x <= n; x += lowbit(x)) tr[x] += val;
}
int query(int x)
{
int res = 0;
for(; x; x -= lowbit(x)) res += tr[x];
return res + tr[0];
}
signed main()
{
freopen("suspect.in","r",stdin);
freopen("suspect.out","w",stdout);
n = read(); p = read();
for(int i = 1; i <= n; i++)
{
x = read(); y = read();
add(x,y); add(y,x);
du[x]++; du[y]++;
}
for(int i = 1; i <= n; i++) chenge(du[i],1);
for(int i = 1; i <= n; i++)
{
if(du[i] >= p) { ans += n-1; continue;}//防止出现负下标
int sum = n - query(p-du[i]-1);//合法的方案数
for(int j = head[i]; j; j = e[j].net)
{
int to = e[j].to;
if(du[to] == p - du[i]) sum--;//特判重边的情况
du[to]--
}
for(int j = head[i]; j; j = e[j].net)
{
int to = e[j].to;
if(du[to] == p - du[i]) sum--;//特判重边的情况
du[to]--
}
for(int j = head[i]; j; j = e[j].net)//判断i-to有多条边的情况，这时候只能算一次
{
int to = e[j].to;
du[to]++
}
if(du[i] >= p - du[i]) sum--;//判断自己是否被算进去
ans += sum;
}
printf("%lld\n",ans>>1);
fclose(stdin); fclose(stdout);
return 0;
}
T3 xor
给你一个序列，让你求一段区间内出现次数为偶数的数的异或和。\(n,q\leq 3e5\)
solution
CF 上的原题。
显然我们的答案可以转化为 一段区间出现过的数字的异或和 ^ 出现次数为奇数的数异或和。为什么呢？
举个例子： \(1,1,2,4,3,4\) 。 出现过的数字的异或和为 1 ^ 2 ^ 3 ^ 4 = 4, 出现次数为奇数的数有 \(2，3\) ，异或和为 \(1\) ,出现偶数的异或和 恰好等于 1 ^ 4.
简单证明一下：一个区间出现过的数字的异或和，把每个数字按出现次数的奇偶性分类，等价于 出现次数为奇数的数的异或和 ^ 出现次数为偶数的异或和。
根据亦或的自反性可得 出现次数为偶数的异或和 = 一段区间出现过的数字的异或和 ^ 出现次数为奇数的数异或和。出现次数为奇数的数的异或和处理一下前缀和就可以得到。现在问题转化为怎么求 一段区间出现过的数字的异或和。
我们先对每个位置求出下一次 \(a_i\) 出现的位置。 然后把询问按左端点从小到大来处理。用线段树处理异或和。
一开始把所有的元素第一次出现的位置都赋为 $a_i $ ，如果要删除 \(i\) 这个位置即询问的左端点大于 \(i\) ,直接把 \(a_i\) 下一次出现的位置赋为 \(a_i\) 就行。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1e6+10;
int n,m,l = 1;
int a[N],b[N],last[N],net[N],sum[N<<2],ans[N],pre[N];
struct node
{
int l,r,id;
}q[N];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
bool comp(node a,node b)
{
return a.l < b.l;
}
void up(int o)
{
sum[o] = sum[o<<1] ^ sum[o<<1|1];
}
void chenge(int o,int l,int r,int x,int val)
{
if(l == r)
{
sum[o] = val;
return;
}
int mid = (l + r)>>1;
if(x <= mid) chenge(o<<1,l,mid,x,val);
if(x > mid) chenge(o<<1|1,mid+1,r,x,val);
up(o);
}
int query(int o,int l,int r,int L,int R)
{
int res = 0;
if(L <= l && R >= r) return sum[o];
int mid = (l + r)>>1;
if(L <= mid) res ^= query(o<<1,l,mid,L,R);
if(R > mid) res ^= query(o<<1|1,mid+1,r,L,R);
return res;
}
int main()
{
// freopen("xor.in","r",stdin);
// freopen("xor.out","w",stdout);
n = read();
for(int i = 1; i <= n; i++)
{
a[i] = b[i] = read();
pre[i] = pre[i-1] ^ a[i];
}
sort(b+1,b+n+1);
int num = unique(b+1,b+n+1)-b-1;
for(int i = 1; i <= n; i++) a[i] = lower_bound(b+1,b+num+1,a[i])-b;
for(int i = n; i >= 1; i--)
{
net[i] = last[a[i]];
last[a[i]] = i;
}
m = read();
for(int i = 1; i <= m; i++)
{
q[i].l = read();
q[i].r = read();
q[i].id = i;
}
sort(q+1,q+m+1,comp);
for(int i = 1; i <= num; i++) chenge(1,1,n,last[i],b[i]);
for(int i = 1; i <= m; i++)
{
while(l < q[i].l)
{
chenge(1,1,n,net[l],b[a[l]]);
l++;
}
ans[q[i].id] = pre[q[i].r] ^ pre[q[i].l-1] ^ query(1,1,n,q[i].l,q[i].r);
}
for(int i = 1; i <= m; i++) printf("%d\n",ans[i]);
fclose(stdin); fclose(stdout);
return 0;
}