ABC370 A-F題解 (AtCoder Beginner Contest 370)
感覺ABC中間1-2道題，經?？紨祿Y構，vector、set、map這些。
A
這類簡單題，看清楚這個位置，作為檢查，可以有效減低出錯可能性：
Output
Print Yes, No, or Invalid according to the instructions in the problem statement.
B
無
C
std，這樣寫（0->n-1，n-1->0），可以少寫一個vector
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int main() { 5 string s, t; 6 cin >> s >> t; 7 vector<string> ans; 8 vector<int> v; 9 int n = s.size(); 10 for (int i = 0; i < n; i++) { 11 if (s[i] > t[i]) v.push_back(i); 12 } 13 for (int i = n - 1; i >= 0; i--) { 14 if (s[i] < t[i]) v.push_back(i); 15 } 16 int sz = v.size(); 17 for (int i = 0; i < sz; i++) { 18 s[v[i]] = t[v[i]]; 19 ans.push_back(s); 20 } 21 cout << sz << '\n'; 22 for (string e : ans) cout << e << '\n'; 23 }
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define ULL unsigned long long 5 6 const LL mod_1=1e9+7; 7 const LL mod_2=998244353; 8 9 const double eps_1=1e-5; 10 const double eps_2=1e-10; 11 12 const int maxn=2e5+10; 13 14 vector<int> v1,v2; 15 16 int main() 17 { 18 int i,cnt=0; 19 string s1,s2; 20 cin>>s1>>s2; 21 for (i=0;i<s1.size();i++) 22 if (s1[i]>s2[i]) 23 v1.emplace_back(i), cnt++; 24 else if (s1[i]<s2[i]) 25 v2.emplace_back(i), cnt++; 26 cout<<cnt<<endl; 27 for (auto d:v1) 28 { 29 s1[d] = s2[d]; 30 cout<<s1<<endl; 31 } 32 reverse(v2.begin(),v2.end()); 33 for (auto d:v2) 34 { 35 s1[d] = s2[d]; 36 cout<<s1<<endl; 37 } 38 39 return 0; 40 }
D
我比賽的時候，就感覺找一個數的pre、next和存在修改，感覺很眼熟。感覺有很多題是這樣的思路。
首先，它有刪除操作。然后刪除后的序列，和尋找刪除的位置，很容易讓人聯想到需要排序（lower_bound），才能找相鄰的位置。
但是，vector刪除挺耗時的。然后想到set。
另外要注意的是，lower_bound(srow[i].begin(), srow[i].end(), j); 超時，srow[i].lower_bound(j); AC了
題解的set操作，就寫得很精簡。up、down操作都用"auto it = g2[C].lower_bound(R);"，首先up，刪除一個數，它不影響down中"auto it = g2[C].lower_bound(R)"的結果。有的刪除兩個數，如果分別刪除 prev(it,1)、it，應該會因為刪除一個數后，it的位置發生變動，然后刪除第二個數這個操作是錯誤的。
這種題，代碼有規律性的，用vscode自動補全，很爽。
it位置前/后幾個數：prev(it) next(it) prev(it,g) next(it,g)
set的lower_bound：set1.lower_bound(i)
vector< set<int> > srow(row+1), scol(col+1)
set1.count(i)： set::count()是C++ STL中的內置函數，它返回元素在集合中出現的次數。由于set容器僅包含唯一元素，因此只能返回1或0
1 #include <cassert> 2 #include <iostream> 3 #include <set> 4 #include <vector> 5 using namespace std; 6 7 int main() { 8 cin.tie(nullptr); 9 ios::sync_with_stdio(false); 10 11 int H, W, Q; 12 cin >> H >> W >> Q; 13 14 vector<set<int>> g1(H), g2(W); 15 for (int i = 0; i < H; i++) { 16 for (int j = 0; j < W; j++) { 17 g1[i].insert(j); 18 g2[j].insert(i); 19 } 20 } 21 22 auto erase = [&](int i, int j) { g1[i].erase(j), g2[j].erase(i); }; 23 24 while (Q--) { 25 int R, C; 26 cin >> R >> C; 27 --R, --C; 28 29 if (g1[R].count(C)) { 30 erase(R, C); 31 continue; 32 } 33 34 // up 35 { 36 auto it = g2[C].lower_bound(R); 37 if (it != begin(g2[C])) erase(*prev(it), C); 38 } 39 // down 40 { 41 auto it = g2[C].lower_bound(R); 42 if (it != end(g2[C])) erase(*it, C); 43 } 44 // left 45 { 46 auto it = g1[R].lower_bound(C); 47 if (it != begin(g1[R])) erase(R, *prev(it)); 48 } 49 // right 50 { 51 auto it = g1[R].lower_bound(C); 52 if (it != end(g1[R])) erase(R, *it); 53 } 54 } 55 56 int ans = 0; 57 for (int i = 0; i < H; i++) ans += g1[i].size(); 58 cout << ans << "\n"; 59 }
1 /* 2 TODO 想別人是怎么寫pre、next和修改后的處理的。這類題，遇到多次。1 怎么簡潔 2 多種方法 3 4 5 6 up down都，auto it = g2[C].lower_bound(R);，先up，然后刪除一個數，不影響down中，auto it = g2[C].lower_bound(R)的結果 7 */ 8 #include <bits/stdc++.h> 9 using namespace std; 10 #define LL long long 11 #define ULL unsigned long long 12 13 const LL mod_1=1e9+7; 14 const LL mod_2=998244353; 15 16 const double eps_1=1e-5; 17 const double eps_2=1e-10; 18 19 const int maxn=2e5+10; 20 21 int main() 22 { 23 int row,col,q,i,j,value1,value2,cnt=0; 24 cin>>row>>col>>q; 25 26 set<int> *srow,*scol; 27 srow = new set<int>[row+1]; 28 scol = new set<int>[col+1]; 29 for (i=1;i<=row;i++) 30 for (j=1;j<=col;j++) 31 srow[i].insert(j); 32 for (j=1;j<=col;j++) 33 for (i=1;i<=row;i++) 34 scol[j].insert(i); 35 36 set<int>::iterator k; 37 38 while (q--) 39 { 40 /* 41 for (i=1;i<=row;i++) 42 { 43 for (auto d:srow[i]) 44 cout<<d<<" "; 45 cout<<endl; 46 } 47 cout<<endl; 48 */ 49 50 cin>>i>>j; 51 if (!srow[i].empty()) 52 { 53 54 //begin()有數字，是第一個數；end()沒有數字 55 //prev(it,g) next(it,g) 56 //srow[i].lower_bound(j); ac ; lower_bound(srow[i].begin(), srow[i].end(), j);過不了 57 58 //k = lower_bound(srow[i].begin(), srow[i].end(), j); 59 k = srow[i].lower_bound(j); 60 if (k!=srow[i].end() && (*k)==j) 61 { 62 srow[i].erase(j); 63 scol[j].erase(i); 64 continue; 65 } 66 } 67 68 if (!srow[i].empty()) 69 { 70 /* 71 for (auto d:srow[i]) 72 cout<<d<<" "; 73 cout<<endl; 74 */ 75 76 //k = lower_bound(srow[i].begin(), srow[i].end(), j); 77 k = srow[i].lower_bound(j); 78 value1 = value2 = -1; 79 if (k!=srow[i].begin()) 80 value1 = * prev(k,1); 81 if (k!=srow[i].end()) 82 value2 = * k; 83 if (value1!=-1) 84 { 85 srow[i].erase(value1); 86 scol[value1].erase(i); 87 } 88 if (value2!=-1) 89 { 90 srow[i].erase(value2); 91 scol[value2].erase(i); 92 } 93 } 94 95 if (!scol[j].empty()) 96 { 97 //k = lower_bound(scol[j].begin(), scol[j].end(), i); 98 k = scol[j].lower_bound(i); 99 value1 = value2 = -1; 100 if (k!=scol[j].begin()) 101 value1 = * prev(k,1); 102 if (k!=scol[j].end()) 103 value2 = * k; 104 if (value1!=-1) 105 { 106 scol[j].erase(value1); 107 srow[value1].erase(j); 108 } 109 if (value2!=-1) 110 { 111 scol[j].erase(value2); 112 srow[value2].erase(j); 113 } 114 } 115 } 116 117 for (i=1;i<=row;i++) 118 cnt+=srow[i].size(); 119 cout<<cnt<<endl; 120 121 return 0; 122 }
我按照std，自己照葫蘆畫瓢寫一下：
1 /* 2 TODO 想別人是怎么寫pre、next和修改后的處理的。這類題，遇到多次。1 怎么簡潔 2 多種方法 3 4 5 6 up down都，auto it = g2[C].lower_bound(R);，先up，然后刪除一個數，不影響down中，auto it = g2[C].lower_bound(R)的結果 7 */ 8 #include <bits/stdc++.h> 9 using namespace std; 10 #define LL long long 11 #define ULL unsigned long long 12 13 const LL mod_1=1e9+7; 14 const LL mod_2=998244353; 15 16 const double eps_1=1e-5; 17 const double eps_2=1e-10; 18 19 const int maxn=2e5+10; 20 21 int main() 22 { 23 int row,col,q,i,j,v,cnt=0; 24 cin>>row>>col>>q; 25 26 vector< set<int> > srow(row+1),scol(col+1); 27 28 for (i=1;i<=row;i++) 29 for (j=1;j<=col;j++) 30 srow[i].insert(j); 31 for (j=1;j<=col;j++) 32 for (i=1;i<=row;i++) 33 scol[j].insert(i); 34 35 set<int>::iterator k; 36 37 while (q--) 38 { 39 cin>>i>>j; 40 if (srow[i].count(j)) 41 { 42 srow[i].erase(j); 43 scol[j].erase(i); 44 continue; 45 } 46 47 k = srow[i].lower_bound(j); 48 if (k!=srow[i].begin()) 49 { 50 v = * prev(k,1); 51 srow[i].erase(v); 52 scol[v].erase(i); 53 } 54 55 k = srow[i].lower_bound(j); 56 if (k!=srow[i].end()) 57 { 58 v = * k; 59 srow[i].erase(v); 60 scol[v].erase(i); 61 } 62 63 k = scol[j].lower_bound(i); 64 if (k!=scol[j].begin()) 65 { 66 v = * prev(k,1); 67 scol[j].erase(v); 68 srow[v].erase(j); 69 } 70 71 k = scol[j].lower_bound(i); 72 if (k!=scol[j].end()) 73 { 74 v = * k; 75 scol[j].erase(v); 76 srow[v].erase(j); 77 } 78 79 } 80 81 for (i=1;i<=row;i++) 82 cnt+=srow[i].size(); 83 cout<<cnt<<endl; 84 85 return 0; 86 }
E
s(i,j) 表示位置i到位置j的數字的和。
對于位置i，滿足條件數目為f[i]，f[i]=sum{f[j]} 。j<i，s(j+1,i)!=k（數的和為k不被允許）。
以位置i結尾，子串j+1~i的選擇有i種情況。需要記錄f[0]~f[i-1]的情況。
如果暴力做，遍歷所有j的位置，O(n^2)。
用map進行統計，統計s(1,j)數字和為u時的滿足條件數目。
因為數字和范圍比較大，所以用map。
對于這些j，只要它們數字和s(1,j)一樣，都等于u，那么都可以歸為一類，因為都滿足j<i的條件，沒有j的大小區別。它們可以用map進行合并（數值相加）。
對于位置i，s(1,i)=ans，只要s(1,j)!=ans-k，那么即可滿足s(j+1,i)!=k。
用一個變量保存當前所有滿足條件數目的和。統計f[i]的時候，剔除s(1,j)=ans-k對應的滿足條件數目即可。
map，如果一個數值v不存在，那么mp[v]=0，可以直接用mp[v]獲得數值，不用額外寫if mp.find(v)!=mp.end()。
好短代碼，很快能寫完。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define ULL unsigned long long 5 6 const LL mod=998244353; 7 8 const double eps_1=1e-5; 9 const double eps_2=1e-10; 10 11 const int maxn=2e5+10; 12 13 map<LL, LL> mp; 14 15 int main() 16 { 17 LL n,k,a,i,ans=0,sum=0, exc_ans, exc_sum; 18 mp[0]=1; 19 sum=1; 20 cin>>n>>k; 21 for (i=1;i<=n;i++) 22 { 23 cin>>a; 24 ans+=a; 25 26 exc_ans = ans-k; 27 exc_sum = (sum - mp[exc_ans] + mod) % mod; 28 29 (mp[ans] += exc_sum) %= mod; 30 (sum += exc_sum) %= mod; 31 32 if (i==n) 33 cout << exc_sum % mod; 34 } 35 36 return 0; 37 }
F
其實這道題，二分答案很容易想出來，關鍵是有n個起始位置，next(i,K)想一會也能想出來。關鍵是，100分鐘，時間不太夠了。D這類數據結構，set題，平時要多熟練一點。其實A-E能切題得很快，F其實也是emmm……
二分答案
記錄前綴和，用lower_bound尋找下一個位置，中間段的和第一次大于等于w的位置
next(x)=y。next(x,k)等于多少[next()執行k次] next(k) k 二進制 next(1)+next(2)+next(4)+...
lower_bound，對于每個點都做：n*log(n)
next，對于每個點都做：n*log(k)
二分答案：log(A)
log(n) = log(k) = 17
A=2e5*1e4/2=1e9
log(A) = 30
n*log(n or k)*log(A)
17*2e5*30=1e8
一個位置能不能從來不被用：從這里開頭，不行
從i開頭(i=1~n)都處理的優勢：可以統一處理
1 /* 2 關鍵是一個圓弧形的問題。如果要把所有開始位置都遍歷一次，那么需要n次 3 n個數多展開一次，2n 4 5 多少個位置從來沒有被切一刀，就是多少位置不能從它這開始 6 7 二分答案 8 記錄前綴和，用lower_bound尋找下一個位置，中間段的和第一次大于等于w的位置 9 10 next(x)=y。next(x,k)等于多少[next()執行k次] next(k) k 二進制 next(1)+next(2)+next(4)+... 11 12 lower_bound，對于每個點都做：n*log(n) 13 next，對于每個點都做：n*log(k) 14 15 二分答案：log(A) 16 17 log(n) = log(k) = 17 18 A=2e5*1e4/2=1e9 19 log(A) = 30 20 21 n*log(n or k)*log(A) 22 23 17*2e5*30=1e8 24 25 一個位置能不能從來不被用：從這里開頭，不行 26 27 從i開頭(i=1~n)都處理的優勢：可以統一處理 28 */ 29 #include <bits/stdc++.h> 30 using namespace std; 31 #define LL long long 32 #define ULL unsigned long long 33 34 const LL mod_1=1e9+7; 35 const LL mod_2=998244353; 36 37 const double eps_1=1e-5; 38 const double eps_2=1e-10; 39 40 const int maxn=4e5+10; 41 const int siz_max = 20; //30 42 43 LL a[maxn],presum[maxn], nex[maxn][siz_max]; 44 map<LL,LL> mp; 45 46 int main() 47 { 48 LL n,K,i,j,l,r,mid,siz,u,vis; 49 cin>>n>>K; 50 presum[0]=0; 51 for (i=1;i<=n;i++) 52 { 53 cin>>a[i]; 54 presum[i]=presum[i-1]+a[i]; 55 } 56 57 for (i=n+1;i<=n*2;i++) 58 { 59 a[i]=a[i-n]; 60 presum[i]=presum[i-1]+a[i]; 61 } 62 63 l=1,r=presum[n]/K; 64 //l=1,r=1e9; 65 for (siz=0;siz<siz_max;siz++) 66 { 67 nex[n*2+1][siz]=n*2+1; 68 nex[n*2+2][siz]=n*2+1; 69 } 70 71 while (l<=r) 72 { 73 mid=(l+r)/2; 74 for (i=1;i<=n*2;i++) 75 nex[i][0] = lower_bound(presum+1, presum+n*2+1, mid+presum[i-1]) - (presum+1) + 1 + 1; 76 77 for (j=1,siz=2;siz<=K;j++,siz*=2) 78 for (i=1;i<=n*2;i++) 79 nex[i][j] = nex[ nex[i][j-1] ][j-1]; 80 vis=0; 81 for (i=1;i<=n;i++) 82 { 83 j = K; 84 siz = 0; 85 u=i; 86 while (j) 87 { 88 if (j&1) 89 u = nex[u][siz]; 90 siz++; 91 j>>=1; 92 } 93 if (u<=i+n) 94 { 95 vis++; 96 //break; 97 } 98 } 99 mp[mid]=vis; 100 101 if (vis) 102 l=mid+1; 103 else 104 r=mid-1; 105 } 106 cout<<r<<" "<<n-mp[r]; 107 108 109 return 0; 110 }
G
浙公網安備 33010602011771號