#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; }
