a. rewards
水题
#include<cstdio>#include<iostream>#include<cstring>using namespace std;int main(){ int a1,a2,a3,b1,b2,b3,s,t1,t2,sum1,sum2; while(scanf("%d%d%d",&a1,&a2,&a3)!=EOF) { scanf("%d%d%d",&b1,&b2,&b3); scanf("%d",&s); sum1 = a1+a2+a3; sum2 = b1+b2+b3; if(sum1>=5) { t1 = sum1/5; if(sum1%5) t1++; } else if(sum1>0) t1 = 1; else t1 = 0; if(sum2>=10) { t2 = sum2/10; if(sum2%10) t2++; } else if(sum2>0) t2 = 1; else t2 = 0; if(t1+t2>s) puts("NO"); else puts("YES"); } return 0;} B. Suffix Structures
立即学习“前端免费学习笔记（深入）”；
题意：给你两个字符串，要把a串变为b串，如果只需要删除某些字符就能达到目的就输出automaton
如果只通过交换某些字符就输出array,如果两种操作都需要才能达到目的就输出both，如果两种操作
同时使用都不行则输出need tree.
算法：
这个其实情况很复杂的，必须保持头脑清晰清晰清晰~
1、首先如果两个串是相同的则输出array。
2、如果a串长度小于b串长度或者b串中的对应字母在a串中个数不够或者种类不够都是need tree.
3、如果a串长度等于b串长度，且a串中能找到对应的b串中的字母则输出array.
4、如果a串长度大于b串长度，b串中的字母在a串中依次出现则输出automaton.如果虽然都出现了但是
顺序不一样，则输出both。
#include<cstdio>#include<iostream>#include<cstring>#include<vector>using namespace std;char s1[110],s2[110];vector<int> c;int cnt1[30],cnt2[30];int main(){ int flag1,flag2,d,flag; while(scanf("%s%s",s1,s2)!=EOF) { if(strcmp(s1,s2)==0) { printf("array\n"); continue; } flag1 = flag2 = flag = 0; c.clear(); memset(cnt1,0,sizeof(cnt1)); memset(cnt2,0,sizeof(cnt2)); int len1 = strlen(s1); int len2 = strlen(s2); if(len1>len2) flag1 = 1; for(int i=0;i<len2;i++) cnt2[s2[i]-'a']++; for(int j=0;j<len1;j++) cnt1[s1[j]-'a']++; for(int i=0;i<len2;i++) { if(cnt2[s2[i]-'a'] > cnt1[s2[i]-'a']) { flag = 1; break; } } if(flag || len1<len2) { printf("need tree\n"); continue; } for(int i=0;i<len1;i++) { if(s1[i]==s2[0]) c.push_back(i); } for(int i=0;i<c.size();i++) { int t = 1; for(int j=c[i]+1;j<len1;j++) { if(s1[j]==s2[t]) t++; } if(t == len2) { flag2 = 1; break; } } if(flag1 && flag2) printf("automaton\n"); else if(flag1 && !flag2) printf("both\n"); else if(!flag1 && !flag2) printf("array\n"); } return 0;}C. Painting Fence
题意：有n个长度为ai的木条。然后有一个油漆刷，木条宽度和油漆刷的宽度都为1，要把
木条都涂色。且油漆刷刷到的地方都要有木块。问最少需要刷多少次。
算法：记忆化搜索
1、横向刷的下面一定是横向刷。
2、刷完了下面共同的长度后会把木条分成断开的几截，每一截由若干木条的上半部分未刷油漆的组成。
每一部分要么就是竖着刷要么就是横着刷，这时比较两种刷法的次数，取小者。[l，r]的部分竖着刷要刷
r-l+1下，横着刷还是先刷公共部分，再看上面分成几截，于是又出现了相同的子问题。用dfs递归解决。
#include<cstdio>#include<iostream>#include<cstring>#define maxn 5010using namespace std;typedef long long ll;ll a[maxn];ll min(ll x,ll y){ return x<y?x:y;}ll work(int l,int r,int cen){ ll mi = a[l]; for(int i=l+1;i<=r;i++) mi = min(mi,a[i]); ll sum = mi-cen,s = r-l+1; int last = l; for(int i=l;i<=r;i++) { if(a[i]==mi) { if(last<i) sum+=work(last,i-1,mi); last = i+1; } } if(last<=r) sum+=work(last,r,mi); return min(sum,s);}int main(){ int n; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%I64d",&a[i]); ll ans = work(1,n,0); printf("%I64d\n",ans); } return 0;}D. Multiplication Table
题意：n行m列的乘法表，为第k大的数是哪个。
比如：2*3的乘法表为 1 2 3
2 4 6
算法：二分查找。
由于最大的数为n*m=25*10^10，想到二分。第k大的数就是说有k个小于等于他的数（这种说法也不准确），
反正就是第一个找到的这样的最小的数。
充分利用乘法表的特点，每一行都是行数乘以1-m。所以找比小于等于x的数就是min(m,x/i)。
P.S 。。。反正我是没想到这个解法啦。。。o(?□?)o。。。学习了。。。
#include<cstdio>#include<iostream>#include<cstring>#include<queue>using namespace std;typedef long long ll;ll k,n,m;ll min(ll x,ll y){ return x<y?x:y;}ll check(ll x){ ll sum = 0; for(int i=1;i<=n;i++) sum += min(m,x/i); return sum;}int main(){ ll ans; while(scanf("%I64d%I64d%I64d",&n,&m,&k)!=EOF) { ll l = 1,r = n*m; while(l<=r) { ll mid = (l+r)>>1; if(check(mid)>=k) { ans = mid; r = mid-1; } else l = mid+1; } printf("%I64d\n",ans); } return 0;}
