A：
题目：
给出一个 n， 让你求出最小的合法的不包含相同数字的数字。
思路：
n == 1， 为 1
n > 1 时候，第二位为 0 其他从 2 开始。
因为数字只有 10 个数字，所以 > 10 都是不合法的。
代码
int main()
{
int n;
cin >> n;
if(n == 1)
{
cout << 1;
return 0;
}else if(n <= 10)
{
cout << "10";
int x = n - 2;
for(int i = 3; i <= n; i++)
{
cout << i - 1;
}
}else cout << -1;
return 0;
}
E:
题目：
给出一个字符串 s， 在 s 中的子序列找出一个俳句。
俳句： 前五个字符 ， 中间七个字符， 后面五个字符都各自为同一个字符，并且他们之间也可以为同一个字符。
思路：
从子序列中，所以不妨每次统计一下每个字符出现的次数，第一个出现 5 次的字符就可以作为俳句的前五个字符，
然后清零统计，因为是找出子序列，已经确定了前面字符，那么前面统计的字符也不能作为后面的使用。
这样统计三次即可
代码
int main()
{
int n;
cin >> n;
string s;
cin >> s;
int cnt = 0;
string ans;
for(int i = 0; i < s.size(); i++)
{
int x = s[i] - 'a';
w[x]++;
if(w[x] == 5 && ans.size() == 0)
{
ans += s[i];
memset(w, 0, sizeof w);
}
if(w[x] == 7 && ans.size() == 1)
{
ans+= s[i];
memset(w, 0, sizeof w);
}
if(w[x] == 5 && ans.size() == 2)
{
ans+= s[i];
memset(w, 0, sizeof w);
}
}
if(ans.size() != 3)cout << "none";
else
{
for(int i = 0; i < 3; i++)
{
int k = 0;
if(i == 0) k = 5;
else if(i == 1) k = 7;
else if(i == 2)k = 5;
for(int j = 0; j < k; j++) cout << ans[i];
}
}
return 0;
}
F:
已知一个集合， A， 我们定义集合之间的加法 A + B，为 A中任意一个元素和 B 任意一个元素 相加组成的集合，且无重复数字。
给出一个 n， 请找出一个 集合 A， 使得 A + A 之后集合里的数字个数为 n;
思路：
不难发现，如果存在重复的数字才能使得 A里面元素的个数变小。 那么毫无疑问连续的数字组成的集合 A，进行加法之后数字个数最小。
枚举前几位 n，观察当 A中为
12 - {2 , 3 , 4}， 123 - {2, 3, 4, 5 ,6}， 1234 - {2, 3, 4, 5 ,6, 7, 8} 不难发现，奇数的情况，都可以由连续数字组成来构造。
那么偶数情况考虑变动最后一位数字，使得元素的个数增加。
13 - {2, 4, 6}, 124 - {2, 3, 4, 5, 6, 8}， 1235 -{2, 3, 4 , 5, 6, 7, 8, 10,} 不难发现，改变最后一个数字后使得元素个数增加，那么偶数情况也构造出。
所以发现 只有 2, 4 的情况是不能构造出的，其他按照上述即可
int main()
{
int n;
cin >> n;
if(n == 1)
{
cout << 1 << endl;
cout << 1 << endl;
return 0;
};
if(n == 2 || n == 4)
{
cout << -1 << endl;
return 0;
}
if(n % 2 != 0)
{
cout << n / 2 + 1 << endl;
for(int i = 1; i <= n / 2 + 1; i++)
{
cout << i << " ";
}
}else
{
cout << n / 2 << endl;
for(int i = 1; i < n / 2; i++)
{
cout << i << " ";
}
cout << n / 2 + 1;
}
return 0;
}
G：
题目：
给出一些 01 串，给出一些操作，每次操作，都会有概率改变两个串相与的结果。
问你经过一些操作后，所有串再相与后，1的个数
思路：
因为最终我们都要将所有的串相与，那么之前的操作同样是相与，相与的操作是不会改变对应位上 0 的个数，只会减小1的个数。
那么最终按位相与，只要原串中存在一个 0， 那么最终相与结果毫无疑问是 0 ， 所以概率的操作是（诈骗, 判断位置上是否有0 即可
代码
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i = 0; i < n; i++)
{
string a;
cin >> a;
for(int j = 0 ; j < m; j++)
{
if(a[j] == '0') num[j] = 1;
}
}
int q;
cin >> q;
for(int i = 0; i < q; i++)
{
int a;
cin >> a >> a >> a >> a >> a;
}
int ans = 0 ;
for(int i =0 ; i < m ;i++)
{
if(num[i] == 0)
{
ans++;
}
}
cout << ans ;
return 0;
}
J：
题目：
给出一棵树，并且每棵树上的点都有相应的权值。
现在给出 k 为 0 - n ，找到一个子图，满足子图中的所有点权值的 mex 恰好为 k，并且子图中点数最多。
思路：
首先考虑 k 为 0 的情况，那么只要不包含 0点的最大子图即可。
考虑 k 为 1的情况，我们选择一个不包含 1的子图，但必须包含 0。
剩下 k 同理， 那么最终除了 k 为 0 的点，我们都要包含 0 这个点，然后再依次找其他小于 k 的点。
那么不妨从 0点出发，找到当前权值为 k 的点，那么走过的这个子图就是权值为 k 这个点，把整棵树一分为二的其中一片图。
两片图考虑其中一片的合法性即可。因为我们是从 权值为 0 的点开始dfs， 要判断当前图的合法性要统计当前子图是否全部包含
0 - k - 1 的所有点。dfs不方便统计，所以不妨判断反过来思考统计另一片图是否包含一个 0 - k - 1 其中的点即可。
只需要回溯时统计当前子图的最小权值即可。
因为要输出点数，所以同时统计一下当前点子树的点的个数。如果当前子图是合法的，那么 n - 当前子树点的个数就是答案。
对于 k为0特判，因为不包含 0 点子图最大点数，就是 0点子树点数最大的那棵树。
代码
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int mii[N];
int size1[N];
int pp[N];
void dfs(int u, int fa)
{
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
dfs(j, u);
mii[u] = min(mii[u], mii[j]);
size1[u] += size1[j];
}
}
int main()
{
memset(h, -1, sizeof h);
memset(mii, 0x3f, sizeof mii);
int n;
scanf("%d", &n);
for(int i = 0 ; i <= n; i++) size1[i] = 1;
int root = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d", &w[i]);
if(w[i] == 0) root = i;
pp[w[i]] = i;
mii[i] = w[i];
}
for(int i = 2; i <= n; i++)
{
int b;
scanf("%d", &b);
add(b, i), add(i, b);
}
dfs(root, -1);
for(int i = 0; i < n; i++)
{
if(i == 0)
{
int mxx = 0;
for(int j = h[root]; j != -1; j = ne[j])
{
int k = e[j];
mxx = max(mxx, size1[k]);
}
printf("%d ", mxx);
}else
{
int j = pp[i];
if(mii[j] < w[j])
{
printf("0 ");
}else
{
printf("%d ", n - size1[j]);
}
}
}
printf("%d ", n);
return 0;
}
H：
题目：
略
思路：
因为每个水管都有不同的方向，所以 dfs来考虑每个水管的转向。
思考复杂度，因为对于当前水管来说，要根据它是从哪里流过来的，来找到下一个流向，如果说当前是 I 管，那么流向是不会改变的。
如果是 L管，那么会向两个方向流出。
所以对于每个管来说状态是很少的，还会受到流向的影响，复杂度是够的。
dfs 时候要统计从哪个方向流出，然后判断流出的方向。
记得标记走过的管，然后回复现场。
代码
bool dfs(int x, int y, int fx)
{
if(x == 4 && y == ed)
{
return true;
}
if(x < 1 || x > 4 || y < 1 || y > m || (mp[x][y] == '0'))
{
return false;
}
if(st[x][y]) return false;
st[x][y] = true;
char type = mp[x][y];
if(type == 'I')
{
bool flag;
if(fx == 1)
{
flag = dfs(x + 1, y, 1);
}else if(fx == 2)
{
flag = dfs(x, y - 1, 2);
}else if(fx == 3)
{
flag = dfs(x -1, y, 3);
}else flag = dfs(x, y + 1, 4);
st[x][y] = false;
return flag;
}else
{
int t;
if(fx == 2 || fx == 4)
{
t = dfs(x - 1, y, 3) | dfs(x + 1, y, 1);
}
if(fx == 3 || fx == 1)
{
t = dfs(x, y +1, 4) | dfs(x, y - 1, 2);
}
st[x][y] = false;
return t;
}
}
void solved()
{
int x, y;
cin >> m >> x >> ed;
for(int i = 1; i <= 4; i++) for(int j = 1; j <= m; j++) mp[i][j] = '0';
for(int i = 2; i <= 3; i++) for(int j = 1; j <= m; j++) cin >> mp[i][j];
mp[1][x] = 'I';
if(dfs(2, x, 1)) cout << "YES" << endl;
else cout << "NO" << endl;
}
