A. Two 0-1 Sequences 大致翻譯： 兩個長度為n和m的二進位序列a和b（題目保證n >= m） 兩個操作： op1: 改變a(2) 為min(a(1), a(2)),並且移除a（1） op2: 改變a(2) 為max(a(1), a(2)),並且移除a（1） 每次操作後，原先的a( ...
A. Two 0-1 Sequences
大致翻譯：
兩個長度為n和m的二進位序列a和b（題目保證n >= m）
兩個操作：
op1: 改變a(2) 為min(a(1), a(2)),並且移除a（1）
op2: 改變a(2) 為max(a(1), a(2)),並且移除a（1）
每次操作後，原先的a(i)變成a(i + 1), 長度減少1，即前移。
a二進位序列能否通過這兩個操作變成b二進位序列？
解題思路：剛開始想的是判斷a2尾碼跟a1尾碼是否相同，再判斷，a1前面有沒有1和0（因為有1和0，就表示op1和op2可以隨意完成）。寫的時候又陸陸續續發現需要幾個特判，想a1長度為1等。
於是就debug，慢慢發現只要前面有a2的第一個數字，並且尾碼相同就可以對了。最終寫出來了。
不過我寫的查找是自己造輪子，我發現大佬就是用stl中的count()來寫的，就拿過來改進了改進自己的code
#include <iostream> #include <vector> #include <string> #include <set> #include <map> #include <stdio.h> #include <algorithm> using namespace std; #define rep(i,x,n) for(int i = x; i <= n; i++) typedef long long LL; typedef pair<int,int> PII; const int N = 10021; void solve() { int n, m; cin>>n>>m; string a, b; cin>>a>>b; if(a.substr(n-m+1) == b.substr(1) && count(a.begin(), a.begin() +n - m + 1, b[0])) { puts("YES"); } else puts("NO"); } void test(); int main() { int n; cin>>n; while(n--) solve(); return 0; }
B. Luke is a Foodie
大致翻譯：
對於a數組中的每一個元素，滿足 |v−ai|≤x， （x是固定的值，由題目給出， v是可以變化調動的值）
問最少需要調動幾次v，才能使得a數組中所有元素滿足|v−ai|≤x
解題思路：
用數組的話存不下1e9+21的int型，而且題目是要找改了幾次v。由|v- ai| <= x這個可以發現，區間差的最大值小於二倍的x範圍內，v就不會改。因此發現存max，min，每次相減，判斷是否滿足在範圍內，滿足不改，不滿足將max，min賦值為k(讀入值）
#include <iostream> #include <vector> #include <string> #include <set> #include <map> #include <stdio.h> #include <algorithm> using namespace std; #define rep(i,x,n) for(int i = x; i <= n; i++) typedef long long LL; typedef pair<int,int> PII; //const LL N = 1e9+21; //LL arr[N]; void test(); int main() { //test(); LL t; cin>>t; while(t--) { LL n,x; scanf("%lld %lld", &n, &x); LL cnt = 0; LL ma, mi; scanf("%d", &ma); mi = ma; rep(i,2,n) { LL k; scanf("%lld", &k); if(mi > k) mi = k; if(ma < k) ma = k; if(abs(ma - mi) <= 2*x) {;} else { cnt++; ma = k; mi = k; } } printf("%lld\n",cnt); } return 0; }
C. Virus
大致翻譯：
一個圓圈內有n個房子（編號為：1、 2、 3 …… n 、 1），最初，其中的m個房子被感染了，每天被感染的房子會感染其相鄰的房子（該房子未被感染或未被保護）.Cirno每天可以選擇一個房子保護，使他永久免疫。問Cirno在最合理的操作下，使房子感染數量最少， 輸出最終房屋感染的數量。
解題思路：n跟m較大，即開n數組會溢出，那麼就先從m下手。由於是形成一個 ⚪ ，第幾個第幾個房子就不是那麼重要，誰都可以從第一個開始。想一想，要想求最小感染房子，那反過來就是最大未感染房子（正難反易）。最大未感染房子個數，這個... 。 由於每一天房子都會有被感染的可能，怎麼就最大未感染房子個數( •̀ ω •́ )y，當然是從兩個感染房子間隔最大的先開始咯，從兩個感染房子間隔最大的先開始，堵住一個後，第二天感染，未堵住的會向內(當然還有外）感染，然後堵住那個未堵住的房子，一個間隔用兩天。通過遞增減去4倍的i，可以得到到它時，還有幾個未被感染。
裡面有一些細節，例如怎麼得到第一個跟最後一個的間隔，怎麼讓間隔由大到小去計算。
#include <iostream> #include <vector> #include <string> #include <set> #include <map> #include <stdio.h> #include <algorithm> using namespace std; #define rep(i,x,n) for(int i = x; i <= n; i++) typedef long long LL; typedef pair<int,int> PII; const int N = 100021; int arr[N]; int diff[N]; void test(); int main() { test(); int t; scanf("%d", &t); while(t--) { int n,m; scanf("%d %d", &n, &m); rep(i,1,m) { scanf("%d", &arr[i]); } sort(arr+1, arr+m+1); diff[1] = arr[1] - 1 + n - arr[m]; rep(i,2,m) diff[i] = arr[i] - arr[i-1] - 1; sort(diff+1, diff+m+1, greater<int>()); int ans = 0; rep(i,1,m) { diff[i] -= 4*(i-1); // 每次兩天，一前一後，形成永久隔離,那麼裡面的自然而然就是不會被感染的了 if(diff[i]) { n -= (diff[i] == 1?1:(diff[i]-1)); } } cout<<n<<endl; } return 0; } void test() { #define mytest #ifdef mytest freopen("ANSWER.txt", "w",stdout); #endif }
D. Magical Array
大致翻譯：
定義一個特殊行，執行操作2，其它行執行操作1（執行次數都至少有一次）
給出這些行，讓你輸出那個是特殊行，以及特殊行操作2的次數。
解題思路：首碼和和差分，思路簡單。
學到了 min_element() max_element()
#include <iostream> #include <vector> #include <string> #include <set> #include <map> #include <stdio.h> #include <algorithm> #include <cstdlib> #include <memory.h> using namespace std; #define rep(i,x,n) for(int i = x; i <= n; i++) typedef long long LL; typedef pair<int,int> PII; const int N = 100021; LL arr[N]; void test(); int main() { //test(); int t; cin>>t; while(t--) { int n, m; scanf("%d %d", &n, &m); for(int i = 0; i < n; ++i) { LL pre = 0; for(int j = 1; j <= m; ++j) { LL x; scanf("%lld", &x); pre += x; arr[i] += pre; } } LL mx = *max_element(arr+0, arr+n); LL mi = *min_element(arr+0, arr+n); cout<< min_element(arr+0, arr+n) - arr + 1<<" " <<mx - mi<<endl; memset(arr, 0, sizeof(arr)); } return 0; } void test() { #define mytest #ifdef mytest freopen("ANSWER.txt", "w",stdout); #endif }
總結：學了幾個stl
count() -- 返回個數 max_element() min_element() -- 返回迭代器或地址（數組）。
第一次做codeforces，寫的時候太著急了，有些題沒理解透徹或者複雜化了，A題用時較長。
加油！！！
