总结：做了3道，补题1道
A. Juicer
题意：水题
#include <iostream> #include <cstdio> #include <algorithm> #define maxn 100005 using namespace std; int a[maxn]; int main() { int n,b,d; cin >> n >> b >> d; for(int i = 0;i < n;i ++) scanf("%d",&a[i]); int sum = 0; int ans = 0; for(int i = 0;i < n;i ++){ if(a[i] > b) continue; else{ sum += a[i]; if(sum > d){ ans ++; sum = 0; } } } cout << ans << endl; return 0; }
B. Checkpoints
题意：水题
#include <iostream> #include <cstdio> #include <algorithm> #include <map> #include <cstring> #define maxn 100005 using namespace std; typedef long long ll; int main() {int left[maxn]; int right[maxn]; int lcnt,rcnt; map<int,int> mmap; int n,a; cin >> n >> a; ll ans; lcnt = rcnt = 0; for(int i = 0;i < n;i ++){ int d; scanf("%d",&d); mmap[d] ++; if(d < a){ left[lcnt++] = d; } else if(d > a){ right[rcnt++] = d; } } sort(left,left+lcnt); sort(right,right+rcnt); if(lcnt + rcnt <= 1) cout << "0" << endl; else if(lcnt == 0 || rcnt == 0){ if(lcnt == 0){ if(mmap[right[rcnt-1]] > 1) ans = right[rcnt-1] - a; else ans = right[rcnt-2] - a; } else{ if(mmap[left[0]] > 1) ans = (a-left[0]); else ans = (a-left[1]); } cout << ans << endl; } else{ if(mmap[left[0]] > 1 && mmap[right[rcnt-1]] > 1) { ans = max(a-left[0],right[rcnt-1]-a) + 2*min(a-left[0],right[rcnt-1]-a); } else if(mmap[left[0]] > 1 && mmap[right[rcnt-1]] == 1){ ll t1,t2; t1 = (a-left[0]) + 2*(right[rcnt-2] - a); t2 = 2*(a-left[0]) + (right[rcnt-2] - a); ans = min(t1,t2); } else if(mmap[left[0]] == 1 && mmap[right[rcnt-1]] > 1){ ll t1,t2; t1 = 2*(a-left[1]) + (right[rcnt-1] - a); t2 = (a-left[1]) + 2*(right[rcnt-1] - a); ans = min(t1,t2); } else{ ll t1,t2,t3,t4; if(rcnt > 1){ t1 = (a-left[0]) + 2*(right[rcnt-2] - a); t3 = 2*(a-left[0]) + (right[rcnt-2] - a); } else{ t1 = (a-left[0]) + 0; t3 = 2*(a-left[0]) + 0; } if(lcnt > 1){ t2 = 2*(a-left[1]) + (right[rcnt-1] - a); t4 = (a - left[1]) + 2*(right[rcnt-1] - a); } else{ t2 = 0 + (right[rcnt-1] - a); t4 = 0 + 2*(right[rcnt-1] - a); } t1 = min(t1,t2); t3 = min(t3,t4); ans = min(t1,t3); } cout << ans << endl; } return 0; }
C. Letters Cyclic Shift
水题
#include <iostream> #include <string> using namespace std; int main() { string s; int i,k,t; cin >> s; for(k = 0;k < s.length();k ++){ if(s[k] != 'a') break; } for(t = k;t < s.length();t ++){ if(s[t] == 'a') break; } for(i = k;i < t;i ++){ if(s[i] == 'a') s[i] = 'z'; else s[i] --; } if(k == s.length()) s[k-1] = 'z'; cout << s << endl; return 0; }
D. Recover the String
题意：给出四个数a0，a1，a2，a3，求一个只有0、1的数字串，其子串（不一定连续）“00”的个数是a0，“01”的个数是a1，以此类推。
思路:首先由a0,a3可以推出数字串中0,1的个数分别为s0，s1，则a0+a1+a2+a3=c(s0+s1,2)。如果初始为所有0在所有1前面，将一个1左移到一个0前面，则10增加1,01减少1。
#include <iostream> #include <cstdio> #include <algorithm> #include <map> #include <cstring> using namespace std; typedef long long ll; #define maxn 1000005 ll c[maxn]; void init(){ c[0] = c[1] = 0; for(ll i = 2;i < maxn;i ++){ c[i] = (i * (i - 1)) / 2; } } int main() { ll a0,a1,a2,a3; cin >> a0 >> a1 >> a2 >> a3; if(a0 + a1 + a2 + a3 == 0) { cout << "0" << endl; return 0; } init(); int s0,s1; //代表0,1的个数 bool flag1,flag2; flag1 = flag2 = false; for(int i = 0;i < maxn;i ++){ if(c[i] == a0){ s0 = i; flag1 = true; break; } } for(int i = 0;i < maxn;i ++){ if(c[i] == a3){ s1 = i; flag2 = true; break; } } if(!flag1 || !flag2){ cout << "Impossible" << endl; } else{ if(s1 == 0){ if(a1 || a2) s1 = 1; } if(s0 == 0){ if(a1 || a2) s0 = 1; } if((a1+a2+a3+a0) != c[s1+s0]) cout << "Impossible" << endl; else if(!s0 || !s1){ if(s0) for(int i = 0;i < s0;i ++) cout << "0"; if(s1) for(int i = 0;i < s1;i ++) cout << "1"; cout << endl; } else{ int s = a2; int cc = s/s0; int dd = s0 - s % s0; //s0可能是0，所以前面分类讨论要把s0==0 || s1 == 0的case单独讨论 for(int i = 0;i < cc;i ++) cout << "1"; for(int i = 0;i < dd;i ++) cout << "0"; if(s%s0) cout << "1"; for(int i = 0;i < s % s0;i ++) cout << "0"; int ee = s1-s/s0; ee = s%s0 == 0? ee : ee - 1; for(int i = 0;i < ee;i ++) cout << "1"; cout << endl; } } return 0; }