2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 2) 【部分题解】
生活随笔
收集整理的這篇文章主要介紹了
2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 2) 【部分题解】
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
A：因為刪除是不計入操作次數的，所以轉化一下就是求最長上升子序列，簡單dp。
? ? ?設dp[i]表示前i個字符能湊成上升子序列的最大長度，dp[i] = max(dp[j]+1, dp[i]) 【j < i && s[j] < s[i]】
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define rep(i,a,b) for(int i = a;i <= b;++ i) 4 #define per(i,a,b) for(int i = a;i >= b;-- i) 5 #define mem(a,b) memset((a),(b),sizeof((a))) 6 #define FIN freopen("in.txt","r",stdin) 7 #define IO ios_base::sync_with_stdio(0),cin.tie(0) 8 #define pb push_back 9 typedef long long LL; 10 typedef pair<int, LL> PIR; 11 const int N = 1e6+5; 12 13 string s; 14 int dp[105]; 15 16 int main() 17 { 18 //FIN; 19 cin >> s; 20 int len = s.size(), maxn = 0; 21 rep(i, 1, len){ 22 dp[i] = 1; 23 rep(j, 1, i-1){ 24 if(s[j-1] < s[i-1]) dp[i] = max(dp[j]+1, dp[i]); 25 } 26 maxn = max(maxn, dp[i]); 27 } 28 cout << 26-maxn << endl; 29 return 0; 30 } View Code?
B：可以看出題目其實就是讓你求有多少對啞鈴片，每一片啞鈴只能用一次且這一對重量相同。
? ? ?最多只可能有14個啞鈴片，因此我們可以用二進制進行枚舉，假設二進制是 101011(高->低)，那么表示1,2,4,6號啞鈴片被選中了；
? ? ?這樣的話最多 2^14種重量，接下來我們只需要判斷一下相同重量的方案是不是滿足每種啞鈴片只用了一次。
? ? ?eg: 假設 1001和1100構成的重量是相同的，但是它們都選擇了4號啞鈴片，所以這種情況是不滿足題意的，只有 1001和 0110這種情況滿足；
? ? ?可見判斷標準就是看兩個方案的二進制數的按位與操作的結果是不是0，是的話表示滿足，不是的話表示有重復使用，則不滿足。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define rep(i,a,b) for(int i = a;i <= b;++ i) 4 #define per(i,a,b) for(int i = a;i >= b;-- i) 5 #define mem(a,b) memset((a),(b),sizeof((a))) 6 #define FIN freopen("in.txt","r",stdin) 7 #define IO ios_base::sync_with_stdio(0),cin.tie(0) 8 #define pb push_back 9 typedef long long LL; 10 typedef pair<int, LL> PIR; 11 const int N = (1<<16); 12 13 int n, m; 14 LL a[20], b[20]; 15 vector <LL> ans, ANS; 16 map <LL, bool> vis, VIS; 17 struct Node{ 18 int bt; 19 LL val; 20 bool operator < (const Node &r) const { return val < r.val; } 21 }node[N]; 22 23 bool judge(int i, int j){ 24 int a = node[i].bt, b = node[j].bt; 25 if(a&b) return false; 26 return true; 27 } 28 int main() 29 {IO; 30 //FIN; 31 cin >> n >> m; 32 rep(i, 1, n) cin >> a[i]; 33 rep(i, 1, m) cin >> b[i]; 34 35 rep(i, 0, ((1<<m)-1)){ 36 int bit = i, p = 1; 37 LL res = 0; 38 while(bit){ 39 if(bit&1) res += b[p]; 40 p++; bit >>= 1; 41 } 42 node[i].val = res; 43 node[i].bt = i; 44 } 45 sort(node, node+(1<<m)); 46 int i = 0; 47 while(i < (1<<m)){ 48 int j = i+1; 49 if(vis[node[i].val]) { i++; continue; } 50 while(j < (1<<m)){ 51 if(node[i].val != node[j].val) break; 52 if(judge(i, j)){ 53 if(!vis[node[i].val]) ans.pb(node[i].val); 54 vis[node[i].val] = true; 55 } 56 j++; 57 } 58 i++; 59 } 60 //rep(i, 0, (int)ans.size()-1) cout << ans[i] << " "; 61 rep(i, 1, n){ 62 if(!VIS[a[i]]) ANS.pb(a[i]); 63 VIS[a[i]] = true; 64 rep(j, 0, (int)ans.size()-1){ 65 LL res = a[i]+ans[j]*2; 66 if(!VIS[res]) ANS.pb(res); 67 VIS[res] = true; 68 } 69 } 70 sort(ANS.begin(), ANS.end()); 71 rep(i, 0, (int)ANS.size()-1) cout << ANS[i] << endl; 72 return 0; 73 } View Code?
C：貌似還沒補。。。。。。
D：這是一道貪心題，我們可以從左往右貪心。假設當前位置是pos，那么我們可以看一下pos往右的長度為r的區間內有幾個攝像機，
? ? ?如果大于2，那么不需要放，否則需要放1個或2個。我們為了使攝像機充分利用，那么我們盡可能把攝像機給右邊放，也就是說，
? ? ?我們從 pos+r-1 的位置往左掃，碰到沒有攝像機的位置給它放就行了，知道 [pos, pos+r-1]這個區間的攝像機不少于2個就好。
? ? ?快速判斷 [pos, pos+r-1]的攝像機個數，有的位置標記1，沒有的標記0，那么區間求和就是攝像機個數；
? ? ?快速求區間和操作可以看看樹狀數組，當然可以用前綴和以及特殊的處理也可以搞定這個題。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define rep(i,a,b) for(int i = a;i <= b;++ i) 4 #define per(i,a,b) for(int i = a;i >= b;-- i) 5 #define mem(a,b) memset((a),(b),sizeof((a))) 6 #define FIN freopen("in.txt","r",stdin) 7 #define IO ios_base::sync_with_stdio(0),cin.tie(0) 8 #define pb push_back 9 typedef long long LL; 10 typedef pair<int, LL> PIR; 11 const int N = 1e5+5; 12 13 LL n, k, r, x, c[N]; 14 bool vis[N]; 15 16 int lowbit(int x) { return x&-x; } 17 void add(int id, int p){ 18 while(id <= n){ 19 c[id] += p; 20 id += lowbit(id); 21 } 22 } 23 LL sum(int id){ 24 LL ans = 0; 25 while(id >= 1){ 26 ans += c[id]; 27 id -= lowbit(id); 28 } 29 return ans; 30 } 31 int main() 32 {IO; 33 //FIN; 34 cin >> n >> k >> r; 35 rep(i, 1, k) { cin >> x; vis[x] = true; add(x, 1); } 36 LL ans = 0; 37 rep(i, 1, n-r+1){ 38 LL res = sum(i+r-1)-sum(i-1); 39 if(res < 2){ 40 per(j, i+r-1, i){ 41 if(res >= 2) break; 42 if(!vis[j]){ 43 add(j, 1); 44 vis[j] = true; 45 ans++; 46 res++; 47 } 48 } 49 } 50 } 51 cout << ans << endl; 52 return 0; 53 } View Code?
E：按照題意，我們每次是從長度為k的序列中找罰時最小的來處理的，那么只需要用個優先隊列，每次把最小的pop出來，然后按照題意進行模擬就行了。
? ? ?關于優先隊列的用法請出門右拐百度 "STL 優先隊列"
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define rep(i,a,b) for(int i = a;i <= b;++ i) 4 #define per(i,a,b) for(int i = a;i >= b;-- i) 5 #define mem(a,b) memset((a),(b),sizeof((a))) 6 #define FIN freopen("in.txt","r",stdin) 7 #define IO ios_base::sync_with_stdio(0),cin.tie(0) 8 #define pb push_back 9 typedef long long LL; 10 typedef pair<int, LL> PIR; 11 const int N = 1e6+5; 12 13 int n, k, a[305]; 14 priority_queue<int, vector<int>, greater<int> > Q; 15 16 int main() 17 { 18 //FIN; 19 cin >> n >> k; 20 rep(i, 1, n) cin >> a[i]; 21 LL ans = 0, pre = 0, tol = 0; 22 rep(i, 1, k) Q.push(a[i]); 23 24 int id = k+1; 25 while(!Q.empty()){ 26 ans = pre+Q.top(); Q.pop(); 27 pre = ans; 28 tol += ans; 29 if(id <= n) { Q.push(a[id]); id++; } 30 } 31 cout << tol << endl; 32 return 0; 33 } View Code?
F：簽到題，判斷a + b = c，處理讀入可以簡化操作。
?
G：蘋果下落，按照題意模擬就行了。把每個蘋果往下掉，直到不能掉為止。注意有坑點，有可能上下是多個蘋果相連，
? ? ?那么如果判斷條件不合理的話，最后結果只是最底下的一層掉落了。因此我們可以從下往上模擬就不會出現這個問題了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define rep(i,a,b) for(int i = a;i <= b;++ i) 4 #define per(i,a,b) for(int i = a;i >= b;-- i) 5 #define mem(a,b) memset((a),(b),sizeof((a))) 6 #define FIN freopen("in.txt","r",stdin) 7 #define IO ios_base::sync_with_stdio(0),cin.tie(0) 8 #define pb push_back 9 typedef long long LL; 10 typedef pair<int, LL> PIR; 11 const int N = 1e6+5; 12 13 int n, m, G[55][55]; 14 string s; 15 16 int main() 17 { 18 //FIN; 19 cin >> n >> m; 20 rep(i, 1, n){ 21 cin >> s; 22 rep(j, 0, m-1){ 23 if(s[j] == 'o') G[i][j+1] = 0; 24 if(s[j] == '#') G[i][j+1] = -1; 25 if(s[j] == '.') G[i][j+1] = 1; 26 } 27 } 28 per(i, n, 1){ 29 rep(j, 1, m){ 30 if(G[i][j] == 0){ 31 int id = i+1; 32 while(id <= n && G[id][j] == 1) id++; 33 swap(G[i][j], G[id-1][j]); 34 } 35 } 36 } 37 rep(i, 1, n){ 38 rep(j, 1, m){ 39 if(G[i][j] == 0) cout << 'o'; 40 if(G[i][j] == 1) cout << '.'; 41 if(G[i][j] == -1) cout << '#'; 42 } 43 cout << endl; 44 } 45 return 0; 46 } View Code?
H：題意是讓你求L的聯通塊個數，C可以代表L或者W。這是個簡單的搜索題，試想一下，如果我當前有個位置是L，那么我肯定這個聯通塊是存在的，
? ? ?那么往下搜索碰到C時，我如果把C當成L處理，對于我最后聯通塊的數目是只可能減少，不可能增加的。因為剛開始已經是一個L往下搜索，肯定是有一個聯通塊了，
? ? ?碰到C的，我可以吧 LCL這種連在一起，因此只減不增。
? ? ?使用到的技巧：可以每次dfs完了之后把經過的點變成W，這樣以后就不用再走了。注意第一樣例這種特殊判斷的情況。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define rep(i,a,b) for(int i = a;i <= b;++ i) 4 #define per(i,a,b) for(int i = a;i >= b;-- i) 5 #define mem(a,b) memset((a),(b),sizeof((a))) 6 #define FIN freopen("in.txt","r",stdin) 7 #define IO ios_base::sync_with_stdio(0),cin.tie(0) 8 #define pb push_back 9 typedef long long LL; 10 typedef pair<int, LL> PIR; 11 const int N = 1e6+5; 12 13 int n, m, res, G[55][55], dir[4][2] = {0,1,0,-1,1,0,-1,0}; 14 string s; 15 16 bool judge(int x, int y){ 17 if(x < 1 || x > n || y < 1 || y > m || G[x][y] == -1) return false; 18 return true; 19 } 20 void dfs(int x, int y){ 21 rep(i, 0, 3){ 22 int xi = x+dir[i][0], yi = y+dir[i][1]; 23 if(judge(xi, yi)){ 24 G[xi][yi] = -1; 25 dfs(xi, yi); 26 } 27 } 28 return ; 29 } 30 int main() 31 { 32 //FIN; 33 cin >> n >> m; 34 rep(i, 1, n){ 35 cin >> s; 36 rep(j, 0, m-1){ 37 if(s[j] == 'C') G[i][j+1] = 0; 38 if(s[j] == 'W') G[i][j+1] = -1; 39 if(s[j] == 'L') G[i][j+1] = 1; 40 } 41 } 42 int ans = 0; 43 rep(i, 1, n){ 44 rep(j, 1, m){ 45 if(G[i][j] == 1){ 46 ans++; 47 dfs(i, j); 48 } 49 } 50 } 51 cout << ans << endl; 52 return 0; 53 } View Code?
I： 我們貪心的想一下，就可以發現，我能配對多少對襪子是和我的maxn和tol有關的。
? ? ?如果 tol/2 >= maxn,結果就是 tol/2, 否則的話結果就是 tol-maxn；具體可以多試幾組數據畫一畫理解一下。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define rep(i,a,b) for(int i = a;i <= b;++ i) 4 #define per(i,a,b) for(int i = a;i >= b;-- i) 5 #define mem(a,b) memset((a),(b),sizeof((a))) 6 #define FIN freopen("in.txt","r",stdin) 7 #define IO ios_base::sync_with_stdio(0),cin.tie(0) 8 #define pb push_back 9 typedef long long LL; 10 typedef pair<int, LL> PIR; 11 const int N = (1<<16); 12 13 int n; 14 LL x; 15 16 int main() 17 {IO; 18 //FIN; 19 cin >> n; 20 LL tol = 0, maxn = 0; 21 rep(i, 1, n) { cin >> x; maxn = max(maxn, x); tol += x; } 22 cout << (tol >= maxn*2 ? tol/2 : tol-maxn) << endl; 23 return 0; 24 } View Code?
J：這也是一道貪心題，我們需要把位置大于0和小于0分開處理。對于每種情況，因為我們一趟所帶的信封是固定的，
? ? 所以我們肯定是想要把最遠的位置跑的趟數盡可能少，那么只需要從遠及近派送信封即可，每次送完信封還有剩余的時候，我們可以把它送給下一個位置。
? ? 這樣正負兩種情況都處理一下就可以解決了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define rep(i,a,b) for(int i = a;i <= b;++ i) 4 #define per(i,a,b) for(int i = a;i >= b;-- i) 5 #define mem(a,b) memset((a),(b),sizeof((a))) 6 #define FIN freopen("in.txt","r",stdin) 7 #define IO ios_base::sync_with_stdio(0),cin.tie(0) 8 #define pb push_back 9 typedef long long LL; 10 typedef pair<int, LL> PIR; 11 const int N = (1<<16); 12 13 int n; 14 LL k; 15 16 struct Node{ 17 int pos; 18 LL c; 19 bool operator < (const Node &r) const { return pos < r.pos; } 20 }node[1005]; 21 22 int main() 23 {IO; 24 //FIN; 25 cin >> n >> k; 26 rep(i, 1, n) cin >> node[i].pos >> node[i].c; 27 sort(node+1, node+n+1); 28 LL ans = 0, res = 0; 29 int i = n; 30 while(i >= 1){ 31 if(node[i].pos < 0) break; 32 LL cnt = (node[i].c+k-1)/k; 33 ans += node[i].pos*cnt; 34 LL sum = cnt*k; 35 while(i >= 1 && sum && node[i].pos >= 0){ 36 if(node[i].c <= sum) { sum -= node[i].c; i--; } 37 else { node[i].c -= sum; break; } 38 } 39 } 40 i = 1; 41 while(i <= n){ 42 if(node[i].pos >= 0) break; 43 LL cnt = (node[i].c+k-1)/k; 44 ans -= node[i].pos*cnt; 45 LL sum = k*cnt; 46 while(i <= n && sum && node[i].pos < 0){ 47 if(node[i].c <= sum) { sum -= node[i].c; i++; } 48 else { node[i].c -= sum; break; } 49 } 50 } 51 cout << ans*2 << endl; 52 return 0; 53 } View Code?
K：擲骰子判斷a贏的概率，總共只有6*6=36種情況，最后的結果 ans = a贏 / (36 - 平局)；高中簡單概率計算題
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define rep(i,a,b) for(int i = a;i <= b;++ i) 4 #define per(i,a,b) for(int i = a;i >= b;-- i) 5 #define mem(a,b) memset((a),(b),sizeof((a))) 6 #define FIN freopen("in.txt","r",stdin) 7 #define IO ios_base::sync_with_stdio(0),cin.tie(0) 8 #define pb push_back 9 typedef long long LL; 10 typedef pair<int, LL> PIR; 11 const int N = 1e6+5; 12 13 int a[10], b[10]; 14 15 int main() 16 { 17 //FIN; 18 rep(i, 1, 6) cin >> a[i]; 19 rep(i, 1, 6) cin >> b[i]; 20 double cnt1 = 0, cnt2 = 0; 21 rep(i, 1, 6){ 22 rep(j, 1, 6){ 23 if(a[i] > b[j]) cnt1++; 24 if(a[i] == b[j]) cnt2++; 25 } 26 } 27 printf("%.5lf\n", cnt1*1.0/(36-cnt2)); 28 return 0; 29 } View Code?
L：可以知道，只有三種矩形，那么無論怎么拼，其中的最長邊才有可能是最后正方形的邊長的，基于這一點，可以分類討論一下。
1 #include<bits/stdc++.h> 2 #define IO ios_base::sync_with_stadio(0);cin.tie(0); 3 using namespace std; 4 int a[55][55]; 5 int main() 6 { 7 int a1, b1, a2, b2, a3, b3; 8 while(cin >> a1 >> b1 >> a2 >> b2 >> a3 >> b3){ 9 int a = max(a1, b1); 10 int b = max(a2, b2); 11 int c = max(a3, b3); 12 int d = a, flag = 1; 13 if(b > d){d = b; flag = 2;} 14 if(c > d){d = c; flag = 3;} 15 if(flag == 1){ 16 int e = a2 + a3; 17 int f = a2 + b3; 18 int g = b2 + a3; 19 int h = b2 + b3; 20 if(e == d){ 21 if(b2 == b3 && (b2 + a1 == d || b2 + b1 == d)){ cout << "YES" << endl; continue;} 22 } 23 if(f == d){ 24 if(b2 == a3 && (b2 + a1 == d || b2 + b1 == d)) { cout << "YES" << endl; continue;} 25 } 26 if(g == d){ 27 if(a2 == b3 && (a2 + a1 == d || a2 + b1 == d)) { cout << "YES" << endl; continue;} 28 } 29 if(h == d){ 30 if(a2 == a3 && (a2 + a1 == d || a2 + b1 == d)) { cout << "YES" << endl; continue;} 31 } 32 } 33 else if(flag == 2){ 34 int e = a1 + a3; 35 int f = a1 + b3; 36 int g = b1 + a3; 37 int h = b1 + b3; 38 if(e == d){ 39 if(b1 == b3 && (b1 + a2 == d || b1 + b2 == d)){ cout << "YES" << endl; continue;} 40 } 41 if(f == d){ 42 if(b1 == a3 && (b1 + a2 == d || b1 + b2 == d)) { cout << "YES" << endl; continue;} 43 } 44 if(g == d){ 45 if(a1 == b3 && (a1 + a2 == d || a1 + b2 == d)) { cout << "YES" << endl; continue;} 46 } 47 if(h == d){ 48 if(a1 == a3 && (a1 + a2 == d || a1 + b2 == d)) { cout << "YES" << endl; continue;} 49 } 50 } 51 else if(flag == 3){ 52 int e = a2 + a1; 53 int f = a2 + b1; 54 int g = b2 + a1; 55 int h = b2 + b1; 56 if(e == d){ 57 if(b2 == b1 && (b1 + a3 == d || b1 + b3 == d)){ cout << "YES" << endl; continue;} 58 } 59 if(f == d){ 60 if(b2 == a1 && (b2 + a3 == d || b2 + b3 == d)) { cout << "YES" << endl; continue;} 61 } 62 if(g == d){ 63 if(a2 == b1 && (b1 + a3 == d || b1 + b3 == d)) { cout << "YES" << endl; continue;} 64 } 65 if(h == d){ 66 if(a2 == a1 && (a1 + a3 == d || a1 + b3 == d)) { cout << "YES" << endl; continue;} 67 } 68 } 69 cout << "NO" << endl; 70 } 71 } View Code?
M：題意是讓你找最長交錯子序列，這個序列是上升下降或者下降上升交錯出現的。其實這個題的本質和A的最長上升子序列是一樣的，
? ? ?最長上升是在每個位置i我們找的是i之前的最長上升，這道題換成了兩種情況
? ? ?一種情況是假設當前要上升的話，我們找i之前的最長下降。另一種是假設當前下降，我們找i之前的最長上升，用兩個dp數組就可以解決了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define rep(i,a,b) for(int i = a;i <= b;++ i) 4 #define per(i,a,b) for(int i = a;i >= b;-- i) 5 #define mem(a,b) memset((a),(b),sizeof((a))) 6 #define FIN freopen("in.txt","r",stdin) 7 #define IO ios_base::sync_with_stdio(0),cin.tie(0) 8 #define pb push_back 9 typedef long long LL; 10 typedef pair<int, LL> PIR; 11 const int N = 1e6+5; 12 13 int n, a[55], dp[55][2]; 14 15 int main() 16 { 17 //FIN; 18 cin >> n; 19 rep(i, 1, n) cin >> a[i]; 20 int maxn = 1; 21 rep(i, 1, n){ 22 dp[i][0] = dp[i][1] = 1; 23 rep(j, 1, i-1){ 24 if(a[j] > a[i]) dp[i][0] = max(dp[i][0], dp[j][1]+1); 25 if(a[j] < a[i]) dp[i][1] = max(dp[i][1], dp[j][0]+1); 26 } 27 maxn = max(maxn, max(dp[i][0], dp[i][1])); 28 } 29 cout << maxn << endl; 30 return 0; 31 } View Code?
? ? ?
?
轉載于:https://www.cnblogs.com/Jstyle-continue/p/6662413.html
總結
以上是生活随笔為你收集整理的2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 2) 【部分题解】的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 小豆包的学习之旅：里程计运动模型
- 下一篇： IOS8 PUSH解决方法