#628 DIV2 题解
- 2020 年 4 月 8 日
- 筆記
组样例，每组样例给一个，构造一组，使得。
2 2 14
1 1 6 4
直接输出和。
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ int t = 0; scanf("%d", &t); while(t--) { ll x = 0; scanf("%lld", &x); printf("1 %lldn", x - 1); } return 0; }
组样例，每组给一个和个数 。将同一个序列重复次得到一个新序列，问可以从新序列中严格最长上升子序列长度为多少。
2 3 3 2 1 6 3 1 4 1 5 9
3 5
重复次，对于原序列就有次选择的机会。每次按照从小到大的选，只要没有重复的数，总是能得到一个长度的上升子序列，所以就是求去重之后的长度。
#include <bits/stdc++.h> using namespace std; int a[maxn]; map<int, int> mii; int main(){ int t = 0; scanf("%d", &t); while(t--) { mii.clear(); int n = 0, cnt = 0; scanf("%d", &n); for(int i = 1;i <= n;i++) { scanf("%d", a + i); if(mii.count(a[i]) == 0) cnt++; mii[a[i]]++; } printf("%dn", cnt); } return 0; }
给一颗个点的树，用到给每条边编号，每个编号只能用一次，，表示到的简单路径上最小未出现过的编号，为使最大的尽可能小，输出一种编号的方案。
6 1 2 1 3 2 4 2 5 5 6
0 3 2 4 1
首先如果是一条链的话，怎么编号都是无所谓的，这样所有的编号都会出现。
若不是链，则一定会出现下图的结果。
这样从任意点去其他一个点时，总是有一条边是无法经过，如果把最下的三个编号放上去，则这三个数中总是有一个数是，而数又是最小的三个，所以这就是一种合法的方案。
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int maxn = 1e5+5; pii E[maxn]; int deg[maxn], flag[maxn]; int main(){ int n = 0, tag = 0; memset(flag, -1, sizeof(flag)); scanf("%d", &n); for(int i = 1;i < n;i++) { int u, v; scanf("%d %d", &u, &v); E[i] = {u, v}; deg[u]++, deg[v]++; } for(int i = 1;i <= n;i++) { if(deg[i] >= 3) { tag = i; break; } } if(tag == 0) { for(int i = 1;i < n;i++) { printf("%dn", i - 1); } } else { int cnt = 0, num = 0; for(int i = 1;i <= n;i++) { if(E[i].first == tag || E[i].second == tag) { flag[i] = cnt++; } if(cnt == 3) break; } for(int i = 1;i < n;i++) { if(flag[i] == -1) { printf("%dn", cnt++); } else { printf("%dn", flag[i]); } } } return 0; }
给一个和，构造一个最短的数组，使得数组所有元素的异或和为，和为。若没有输出-1。
in: 2 4
out: 2 3 1
in: 1 3
out: 3 1 1 1
首先记，显然不行，当只考虑二进制最低位时，异或和加法等价，所以，的奇偶性应该相同，所以时也不行。
然后开始构造合法的情况，考虑让数组第一个数，显然，但不一定等于，我们知道对于任意，有。考虑让，而总是偶数，这样用三个数，总是能构造出来异或和为，和为。
考虑能不能把数组个数减小一点，可以把不加在上(去掉)，而是直接加在上，但是这里是不能随便加的，当的二进制表示的所有是1的地方，在的二进制表示中恰好是0，这样加进去不会不会产生进位，同时和异或时会重新得到。这样的情况下长度被我们缩短到了。
之后考虑一点细节，到时，，直接输出即可。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100; int flag[maxn]; int main(){ ll u, v; scanf("%lld %lld", &u, &v); ll d = v - u; if(v == u && v != 0) { puts("1"); printf("%lldn", u); } else if(v == 0 && u == 0) { puts("0"); } else if(d % 2 == 1 || d < 0) { puts("-1"); } else { ll tmp = u, ans = 0; int cnt = 0, f = 0; while(tmp) { flag[cnt++] = tmp % 2; tmp /= 2; } cnt = 0, tmp = d / 2ll; while(tmp) { flag[cnt++] += tmp % 2; tmp /= 2; } for(int i = 0;i < 64;i++) { if(flag[i] >= 2) { f = 1; break; } } if(f == 1) { puts("3"); printf("%lld %lld %lldn", u, d / 2ll, d / 2ll); } else { puts("2"); printf("%lld %lldn", u + d / 2ll, d / 2ll); } } return 0; }
给一个和个数，，，，每个不超过7个因子，找一个长度最小的非空子序列，使得序列中的所有数的积是一个完全平方数，输出序列长度。
3 1 4 6
1
4 2 3 6 6
2
因为因子个数不超过7个，所以最多能有两个不相同的质因数。考虑形式的数，它要凑成一个完全平方数，我们期待的是有一个，注意到和，都是需要一个来凑成平方数，所以次数是偶数的质因子是没有作用，这个时候对于每个，把其中的次数是偶数的质因子全部拿掉，所有的数都可以表示为
当存在1时，答案很显然就是这个1，所以长度就为1。
当遇到时，将和0号点连边。
当遇到时，将和连边。
之后的问题就是寻找一个最小环，输出最小环长度即可。
固定一个点找最小环的话直接可以做到，边权都是1，所以需要的时间，但这里再移动固定的点的话就会是平方的复杂度肯定会超时。
注意到连边的时候中有一个一定是，也就是，所以只需要移动以下的质数来寻找最小环即可，若没找到则输出-1。
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; const int maxn = 1e6+5; #define INF 0x3f3f3f3f int a[maxn], prime[maxn], pp[maxn], pos[maxn]; pii pr[maxn]; bool is_prime[maxn]; int sieve(int n){ int p = 0; for(int i = 0;i <= n;i++) is_prime[i] = true; is_prime[0] = is_prime[1] = false; for(int i = 2;i <= n;i++){ if(is_prime[i]) prime[p++] = i; for(int j = 0;j < p;j++){ if(prime[j] * i > n) break; is_prime[prime[j] * i] = false; if(i % prime[j] == 0) break; } } return p; } vector<int> G[maxn]; int dis[maxn], vis[maxn], flag[maxn], pre[maxn]; int bfs(int u) { queue<int> q; memset(vis, 0, sizeof(vis)); dis[u] = 0, vis[u] = 1; q.push(u); while(q.size()) { int v = q.front(); q.pop(); for(int i = 0;i < G[v].size();i++) { int to = G[v][i]; if(vis[to] == 0) { vis[G[v][i]] = 1; dis[to] = dis[v] + 1; pre[to] = v; q.push(to); } else { if(to == pre[v]) continue; return dis[v] + dis[to] + 1; } } } return INF + 5; } int main(){ int n; scanf("%d", &n); int cnt = sieve(1000000 + 5); for(int i = 0;i < cnt;i++) { pos[prime[i]] = i; } for(int i = 0;i < 200;i++) { pp[i] = prime[i] * prime[i]; } for(int i = 1;i <= n;i++) { scanf("%d", a + i); for(int j = 0;j < 200;j++) { while(a[i] % pp[j] == 0) { a[i] /= pp[j]; } if(a[i] < prime[j]) break; } if(is_prime[a[i]]) flag[a[i]] = 1; else { flag[a[i]] = 2; for(int j = 0;j < 200;j++) { if(a[i] % prime[j] == 0) { pr[a[i]] = {prime[j], a[i] / prime[j]}; break; } } } } for(int i = 1;i <= n;i++) { if(a[i] == 1) { puts("1"); return 0; } else { if(flag[a[i]] == 1) { int u = pos[a[i]] + 1; G[u].push_back(0), G[0].push_back(u); } else { int u = pos[pr[a[i]].first] + 1, v = pos[pr[a[i]].second] + 1; G[u].push_back(v), G[v].push_back(u); } } } int ans = INF; for(int i = 0;i < 200;i++) { ans = min(ans, bfs(i)); } if(ans == INF) { puts("-1"); return 0; } printf("%dn", ans); return 0; }
给一张个点条边的图，问图中存不存在大小为的独立集，或者长度大于的简单环。输出其中一种可以，若要输出独立集，先输出1，再输出独立集中元素， 若要输出简单环先输出2再输出环的长度，再输出环中元素。
6 6 1 3 3 4 4 2 2 6 5 6 5 1
1 1 6 4
6 8 1 3 3 4 4 2 2 6 5 6 5 1 1 4 2 5
2 4 1 5 2 4
首先直接,利用一个栈来保存过的路径，当一个点产生回边时，检查这条回边的两个端点在原树上距离是否大于等于（因为环的长度还需要再加上1)。有则直接找到了环。没有则记录下到该点的深度。
之后可以将每个点的深度模一个，
当
若，之间有一条回边。则在第一步的时候就会被判环了，因为两者之间的距离等于。所以在模数相同的情况下，，可以放在一个独立集之中，而由于，是任意的，所以所有模结果相同的数都可以放在一个独立集中，而因为模数是，一共有个点，所以总存在一个独立集中元素个数是符合条件的。找到一个符合条件的输出即可。
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5+5; vector<int> G[maxn]; vector<int> st; vector<int> ans[maxn]; int res, vis[maxn], ins[maxn], dep[maxn]; int fun(int n) { for(int i = 1; i <= n;i++) { if(1ll * i * i >= n) return i; } } void dfs(int u) { st.push_back(u); ins[u] = 1; for(int i = 0;i < G[u].size();i++) { int v = G[u][i]; if(dep[v] == 0) { dep[v] += dep[u] + 1; dfs(v); } else { if(dep[u] - dep[v] + 1 >= res) { puts("2"); printf("%dn", dep[u] - dep[v] + 1); int len = st.size(), cnt = 0;//assert(len - 1 >= dep[v] - 1); for(int i = len - 1;i >= 0;i--) { cnt++; printf("%d", st[i]); if(cnt == dep[u] - dep[v] + 1) { puts(""); break; } else { printf(" "); } } exit(0); } } } st.pop_back(); ins[u] = 0; } void dfs2(int u, int num) { if(vis[u]) return; vis[u] = 1; ans[num % (res - 1)].push_back(u); for(int i = 0;i < G[u].size();i++) { int v = G[u][i]; dfs2(v, num + 1); } } int main(){ int n, m; scanf("%d %d", &n, &m); res = fun(n); for(int i = 1;i <= m;i++) { int u, v; scanf("%d %d", &u, &v); G[u].push_back(v), G[v].push_back(u); } dep[1] = 1; dfs(1); dfs2(1, 1); puts("1"); for(int i = 0;i < res;i++) { if(ans[i].size() >= res) { int len = ans[i].size(), cnt = 0; for(int j = 0;j < res;j++) { printf("%d%c", ans[i][j], j == res - 1 ? 'n' : ' '); } exit(0); } } return 0; }
