A:Rewards：
题目链接：
题意：Bizon有a1个一等奖奖杯，a2个二等奖奖杯，a3个三等奖奖杯，b1个一等奖奖牌，b2个二等奖奖牌，b3个三等奖奖牌，和一个有n个架子的橱柜。如今Bizon想把这些奖牌和奖杯放在橱柜里，可是要遵循以下的规则：一个架子上不能同一时候放奖杯和奖牌；一个架子上的奖杯数量不能超过5个。奖牌数量不能超过10个。
问能不能把这些奖杯和奖牌所有放进去。
分析：依照贪心原则。一个架子上放尽可能多的奖杯和奖牌，求出须要多少个架子，与n比較大小就可以。
#include#include #include #include #include #include using namespace std;int main(){ int a1, a2, a3, b1, b2, b3, n; while(~scanf("%d%d%d%d%d%d%d",&a1, &a2, &a3, &b1, &b2, &b3, &n)) { int suma = a1 + a2 + a3; int sumb = b1 + b2 + b3; int cnta = suma / 5, cntb = sumb / 10; if(suma % 5 != 0) cnta++; if(sumb % 10 != 0) cntb++; if(cnta + cntb <= n) printf("YES\n"); else printf("NO\n"); } return 0;}
B:Suffix Structures
题目链接：
假设仅仅用到suffix automaton，输出“automaton“；假设仅仅用到”suffix array“，输出”array“；假设两种都用到，输出”both“；
假设变不成。输出“need tree”。分析：直接模拟就可以。
#include#include #include #include #include #include #include using namespace std;int main(){ string s, t; int a[30], b[30]; while(cin >> s >> t) { memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); if(s.length() < t.length()) { cout << "need tree" << endl; continue; } int ls = s.length(), lt = t.length(); if(ls == lt) { for(int i = 0; i < ls; i++) { a[s[i] - 'a']++; b[t[i] - 'a']++; } int flag = 1; for(int i = 0; i < 26; i++) if(a[i] != b[i]) { flag = 0; break; } if(flag) cout << "array" << endl; else cout << "need tree" << endl; } else { //cout << "s = " << s << ", t = " << t << endl; for(int i = 0; i < ls; i++) a[s[i] - 'a']++; for(int i = 0; i < lt; i++) b[t[i] - 'a']++; int flag = 1, ok = 0; for(int i = 0; i < 26; i++) if(a[i] < b[i]) { flag = 0; break; } if(flag) { int j, k = 0; for(int i = 0; i < ls; i++) { if(s[i] == t[k]) k++; if(k == lt) { ok = 1; break; } } //t中的字符在s中不一定连续出现，比如ababa abb，应是 aruomaton。比赛时一直Wa在这。
} if(flag && ok) cout << "automaton" << endl; else if(flag && !ok) cout << "both" << endl; else cout << "need tree" << endl; } } return 0; }
C.Painting Fence题目链接：
题意：Bizon要粉刷他的栅栏。栅栏由n块木板组成，每一块有个高度，每次stroke时必须一直接触着栅栏。问最少须要stroke多少次，能够把栅栏刷好。
分析：分治法。
把栅栏从最低处分成左右两部分，每一部分再这样分下去，直到仅仅剩下一块木板。然后往上返回最小值就可以。
#includeD:Multiplication Table#include using namespace std;const int MAXN = 5005;int a[MAXN];int solve(int l, int r, int h){ int k = l, mmin = a[l]; if(l > r) return 0; if(l == r) return a[l] > h; for(int i = l; i <= r; i++) if(a[i] < mmin) { k = i; mmin = a[i]; } return min(r-l+1, solve(l, k-1, mmin) + solve(k+1, r, mmin) + (mmin - h));}int main(){ int n; scanf("%d",&n); for(int i = 0; i < n; i++) scanf("%d",&a[i]); printf("%d\n", solve(0, n-1, 0)); return 0;}#include #include using namespace std;const int MAXN = 5005;int a[MAXN];int solve(int l, int r){ int k = l; if(l > r) return 0; for(int i = l; i <= r; i++) if(a[i] < a[k]) k = i; int tmp = a[k]; for(int i = l; i <= r; i++) a[i] -= tmp; return min(r-l+1, solve(l, k-1) + solve(k+1, r) + tmp);}int main(){ int n; scanf("%d",&n); for(int i = 0; i < n; i++) scanf("%d",&a[i]); printf("%d\n", solve(0, n-1)); return 0;}
题目链接：
题意：给出一个n行m列的乘法表，第i行第j列的值为i*j，把这些值从小到大排序，问第k个数是多少。
分析：二分。
#includeusing namespace std;typedef long long LL;LL solve(LL n, LL m, LL k){ LL l = 0, r = n * m; while(r - l > 1) { LL mid = (r + l) / 2; LL sum = 0; for(int i = 1; i <= n; i++) { LL tmp = mid / i; if(tmp > m) tmp = m; sum += tmp; //sum为不大于mid的值的个数 } if(sum >= k) r = mid; else l = mid; } return r;}int main(){ LL n, m, k; while(cin >> n >> m >> k) { cout << solve(n, m, k) << endl; } return 0;}
E:Divisors（dfs）
题目链接：
题意：给出一个数n，把这个数的因子从小到大写出来，然后对这个数的因子运行k次同样的操作，问最后的结果是什么。假设结果超过100000位。仅仅输出前100000位。
分析：由于对每一个数运行的是同样的操作。所以能够用递归写，当运行到不能分解时，输出一个数，直到运行完k次或者个数已经达到了100000个结束。
#include#include #include using namespace std;typedef __int64 LL;const int MAXN = 100000;LL divisor[MAXN], num;LL cnt = 0;void get_divisor(LL x){ num = 0; LL tmp = (LL)sqrt(x); for(int i = 1; i <= tmp; i++) { if(x % i == 0){ divisor[num++] = i; if(x / i != i) divisor[num++] = x / i; } } sort(divisor, divisor + num);}void dfs(LL x, LL k){ //cout << "x = " << x << ", k = " << k << endl; if(cnt >= 100000) return ; if(k == 0 || x == 1) { cout << x << " "; cnt++; return ; } for(LL i = 0; i < num && divisor[i] <= x; i++) { if(x % divisor[i] == 0) { dfs(divisor[i], k-1); if(cnt >= 100000) return ; } }}int main(){ LL x, k; while(cin >> x >> k) { get_divisor(x); dfs(x, k); cout << endl; } return 0;}