2014最难赛区
7146 贪心这道题是考验STL的. 我们按照一个顺序排序(我方攻击力升序,敌方防御力升序), 此时因为要全部歼灭,优先考虑如何干掉敌方防御力最高的,此时将所有攻击力比它高的我方都放入multiset中维护,然后选择一个”最合适”的匹配(如果有我方防御力大于此时敌方攻击力的元素就使用,若没有就牺牲.首要任务是全部歼灭,此时能够消灭这个敌方的人都已经在multiset中了,若能够不牺牲却让其牺牲是不必要的,因为后面的元素已经保证能够歼灭后面的敌方)
;struct P{int d,a;bool operator <(const P &x) const{return a>x.a;}}A[maxn],B[maxn];int main(){int T,cas=1;scanf(“%d”,&T);while(T–){int N,M;scanf(“%d”,&N);scanf(“%d”,&M);for(int i = 1;i<=N;i++)scanf(“%d%d”,&A[i].a,&A[i].d);for(int i = 1;i<=M;i++)scanf(“%d%d”,&B[i].d,&B[i].a);sort(A+1,A+N+1);sort(B+1,B+M+1);int ans = N;multiset<int> st;for(int i = 1,p=1;i<=M;i++){while(p<=N && B[i].a<=A[p].a)st.insert(A[p++].d);(st.empty()) {ans=-1;break;}auto it = st.upper_bound(B[i].d);if(it==st.end()){st.erase(st.begin());ans–;}else st.erase(it);}printf(“Case #%d: %d\n”,cas++,ans);}return 0;}/**103 210 1011 1120 2010 1020 203 240 4012 830 1010 1020 202 210 1020 2010 520 53 25 77 31 24 42 22 13 41 105 62 212 830 1010 1020 20**/
7147 PS:我不会证明这个贪心,因为还要考虑另一堆在XX情况反而会大于这堆呢 仍旧贪心.题目意思是有N个人,按比赛分数高低选取M个.选不上的最大分数和选上的最小分数.
if( A < C) swap(A,C);选不上,此时将人分为两堆.M+1,N-M-1, 要让M+1分数尽量多 则 ans1 += (M+1)*max(A,B); 接下来对于M+1内部来说,要尽量平均,两种情况都是平局,或一胜一负对半. ans1 += M/2 *max(A+C,B+B); 如果M是奇数,那么不会对半,定有一个为多输一局或仍是平局 if(M&1) ans1 += max(C,B); 同理可知选上的最小分数就是分为M-1,N-M+1 两堆, ans2 += min(C,B)*(M-1) 接下来对于N-M+1内部来说,尽量平均,则 ans2 += (N-M)/2 *min(A+C,B+B); 如果N-M是奇数,那么不会对半,定有一个为多输一局或仍是平局 if( N-M &1) ans2 += min(A,B);
;int main(){int T,N,M,A,B,C;int cas = 1;for(scanf(“%d”,&T);T;T–) {scanf(“%d%d”,&N,&M);scanf(“%d%d%d”,&A,&B,&C);if(A<C) swap(A,C);long long ans1=0,ans2=0;ans1 += (N-M-1) * max(A,B);ans1 += M/2 * max(A+C,B+B);if(M & 1)ans1 += max(C,B);ans2 += (M-1) * min(B,C);ans2 += (N-M)/2 * min(A+C,B+B);if(N – M & 1)ans2 += min(A,B);printf(“Case #%d: %lld %lld\n”,cas++,ans1,ans2);}return 0;}
7139 这个题就是模拟题,但是性质很深. 观察可得到一个结论:对于一个方格中的人来说,如果要有一个完整的时针旋转,则必然是一边走下去,一边走上去,且”包含”所以不用考虑R,L. 若车在人的正左方下降了X次，上升了Y次，那么那个人的旋转圈数便是abs(X-Y)。 然后暴力模拟车的移动： 在车向下移动的时候，我们就要给车影响右方的一个矩阵加上1。 在车向上移动的时候，我们就要给车影响右方的一个矩阵减去1。 这里用Vector进行建图,因为只给了NXM的范围…
;char *str = “UDLR”;int fx[4][2] = {-1,0, 1,0, 0,-1, 0,1};vector<vector<int> > C;void add(int r1,int r2,int c,int val){C[r1][c] += val;C[r2][c] -= val;}int main(){int T;int cas = 1;for(scanf(“%d”,&T);T;T–) {int N,M,K;scanf(“%d%d%d”,&N,&M,&K);C = vector<vector<int> >(N+2,vector<int>(M+2,0));int r=1,c=1;for(int i = 0;i<K;i++){char op;int step;scanf(” %c%d”,&op,&step);if(op==’U’) add(r-step,r,c,-1);if(op==’D’) add(r,r+step,c,1);int f = strchr(str,op)-str;r += step*fx[f][0];c += step*fx[f][1];}long long ans = 0;for(int i = 1;i<=N;i++)for(int j = 1;j<=M;j++){C[i][j] = C[i][j] + C[i-1][j] + C[i][j-1] -C[i-1][j-1];ans += C[i][j] * C[i][j];}printf(“Case #%d: %lld\n”,cas++,ans);}return 0;}
，一切都在发展变化，不断地向昨天告别，满怀信心地投入每一个崭新的今天。
