二、AcWing 1249. 亲戚（简单）

题目描述

或许你并不知道，你的某个朋友是你的亲戚。
他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。
如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。
在这种情况下，最好的帮手就是计算机。
为了将问题简化，你将得到一些亲戚关系的信息，如 Marry 和 Tom 是亲戚，Tom 和 Ben 是亲戚，等等。
从这些信息中，你可以推出 Marry 和 Ben 是亲戚。
请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。

输入格式

输入由两部分组成。
第一部分以 N,MN,MN,M 开始。NNN 为问题涉及的人的个数。这些人的编号为 1,2,3,…,N1,2,3,…,N1,2,3,…,N。下面有 MMM 行，每行有两个数 ai,bia_{i},b_{i}ai​,bi​，表示已知 aia_{i}ai​ 和 bib_{i}bi​ 是亲戚。
第二部分以 QQQ 开始。以下 QQQ 行有 QQQ 个询问，每行为 ci,dic_{i},d_{i}ci​,di​，表示询问 cic_{i}ci​ 和 did_{i}di​ 是否为亲戚。

输出格式

对于每个询问 ci,dic_{i},d_{i}ci​,di​，输出一行：若 cic_{i}ci​ 和 did_{i}di​ 为亲戚，则输出 Yes，否则输出 No。

数据范围

1≤N≤200001≤N≤200001≤N≤20000
1≤M≤1061≤M≤10^{6}1≤M≤106
1≤Q≤1061≤Q≤10^{6}1≤Q≤106

输入样例

10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9

输出样例

Yes
No
Yes

具体实现

1. 实现思路

• 第一个操作可以理解为合并两个集合，第二个操作可以理解为判断两个点是否在同一个集合当中。

2. 实现代码

#include 
using namespace std;
const int N = 20010;
int n, m;
int p[N];
int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}
int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ) p[i] = i;while (m -- ){int a, b;scanf("%d%d", &a, &b);p[find(a)] = find(b);}scanf("%d", &m);while (m -- ){int a, b;scanf("%d%d", &a, &b);if (find(a) == find(b)) puts("Yes");else puts("No");}return 0;
}

三、AcWing 2058. 笨拙的手指（简单）

题目描述

奶牛贝茜正在学习如何在不同进制之间转换数字。
但是她总是犯错误，因为她无法轻易的用两个前蹄握住笔。
每当贝茜将数字转换为一个新的进制并写下结果时，她总是将其中的某一位数字写错。
例如，如果她将数字 141414 转换为二进制数，那么正确的结果应为 111011101110，但她可能会写下 011001100110 或 111111111111。
贝茜不会额外添加或删除数字，但是可能会由于写错数字的原因，写下包含前导 000 的数字。
给定贝茜将数字 NNN 转换为二进制数字以及三进制数字的结果，请确定 NNN 的正确初始值（十进制表示）。

输入格式

第一行包含 NNN 的二进制表示，其中一位是错误的。
第二行包含 NNN 的三进制表示，其中一位是错误的。

输出格式

输出正确的 NNN 的值。

数据范围

0≤N≤1090≤N≤10^{9}0≤N≤109 ，且存在唯一解。

输入样例

1010
212

输出样例

14

样例解释

141414 在二进制下的正确表示为 111011101110，在三进制下的正确表示为 112112112。

具体实现

1. 实现思路

• 这个题是给我们一个数在二级制下表示的结果和在三进制下表示的结果，但是这两个表示方法都只有一位是写错的。
• 这道题对时间的要求比较低，可以直接使用暴力枚举进行求解，但是正向枚举到 10910^{9}109 容易出现超时问题，因此，我们需要反向枚举一下。
• n 在二进制表示下最多有 30 位，并且恰好只有一位是错位的，因此，每位就只有一种情况，一共有 30 种情况。
• 同理，三进制每一位写错也都枚举一遍，但三进制每一位有两种选择，因此，一共有 60 种情况。
• 二进制集合和三进制集合的交集就是我们求解的答案。
• 这里需要注意的是，写错的二进制数和三进制数是可能出现前导 0 的，但正确的二进制数和三进制数是绝对不会出现前导 0 的。
• 小技巧：
• 当奇数异或 1 时，就相当于这个奇数减去 1。
• 当偶数异或 1 时，就相当于这个偶数加上 1。

2. 实现代码

#include 
using namespace std;
int base(string s,int b)  //将b进制的数转换成10进制 
{int res=0;for(int i=0;ires=res*b+s[i]-'0';}return res;
}
int main()
{//x是二进制表示的结果 //y是三进制表示的结果 string x,y; cin>>x>>y; unordered_sethash; for(int i=0;istring s=x;s[i]^=1;  //0，1互相转换 if(s.size()>1&&s[0]=='0'){continue;}hash.insert(base(s,2));}for(int i=0;ifor(int j=0;j<3;j++){if(y[i]-'0'!=j){string s=y;s[i]=j+'0';// 0，1，2相互转换 if(s.size()>1&&s[0]=='0'){continue;}int n=base(s,3);if(hash.count(n)){cout<

#include 
#include 
#include 
#include using namespace std;typedef long long LL;const int N = 100010;int n;
LL m;
int w[N], q[N];
LL f[N];
multiset S;void remove(LL x)
{auto it = S.find(x);S.erase(it);
}int main()
{scanf("%d%lld", &n, &m);for (int i = 1; i <= n; i ++ ){scanf("%d", &w[i]);if (w[i] > m){puts("-1");return 0;}}int hh = 0, tt = -1;LL sum = 0;for (int i = 1, j = 1; i <= n; i ++ ){sum += w[i];while (sum > m){sum -= w[j ++ ];if (hh <= tt && q[hh] < j){if (hh < tt) remove(f[q[hh]] + w[q[hh + 1]]);hh ++ ;}}while (hh <= tt && w[q[tt]] <= w[i]){if (hh < tt) remove(f[q[tt - 1]] + w[q[tt]]);tt -- ;}q[ ++ tt] = i;if (hh < tt) S.insert(f[q[tt - 1]] + w[q[tt]]);f[i] = f[j - 1] + w[q[hh]];if (S.size()) f[i] = min(f[i], *S.begin());}printf("%lld\n", f[n]);return 0;
}

#include 
using namespace std;
const int N = 1000010;
int n;
char s[N];
int ne[N];
int main()
{int T=1;while(scanf("%d",&n),n){scanf("%s",s+1);for(int i=2,j=0;i<=n;i++){while(j&&s[i]!=s[j+1]){j=ne[j];}if(s[i]==s[j+1]){j++ ;}ne[i]=j;}printf("Test case #%d\n",T);T++;for(int i=1;i<=n;i++){int t=i-ne[i];if(i%t==0&&i/t>1){printf("%d %d\n",i,i/t);}                }puts("");}return 0;
}