首页 > 代码库 > Codeforces Round #260 (Div. 2)
Codeforces Round #260 (Div. 2)
A. Laptops
题目意思：
给定n台电脑，第i台电脑的价格是ai ，质量是bi ，问是否存在一台电脑价格比某台电脑价格底，但质量确比某台电脑的质量高，即是否存在ai < aj 且 bi > bj ?
解题思路：
这题一定要看题目，a都是1~n的不同数，b也是1~n的不同数，此题只需要判断ai 是否等于bi ,如果ai != bi 的话，则输出“Happy Alex”，如果所有的ai == bi 则输出“Poor Alex”
证明：先将a按照从小到大排序，当i<j时ai < aj
假设不存在ai < aj 且 bi > bj ，即对所有的bi <= bj
又不b的各个数都不同，所有b也应该从1到n从小到大排序，即此时ai == bi ，
即当ai == bi 时才输出“Poor Alex”
否则肯定输出 “Happy Alex”
#include <iostream>using namespace std;int main(){ int n,a,b; cin >> n; bool flag = false; for(int i = 0; i < n; ++i){ cin >> a >> b; if(a!=b) flag=true; } if(flag) cout<<"Happy Alex"<<endl; else cout<<"Poor Alex"<<endl;}
B. Fedya and Maths
题目的意思：
给定一个非常大的n，求(1^n + 2^n + 3^n + 4^n) mod 5
解题思路是：
通过将前面几个数打出来，然后找规律，发现当n是4的倍数时输出4，其他输出的时0，所以此题判断n是不是4的倍数。
第一种方法是将n当成一个字符串，然后判断n是不是能被4整除
#include <iostream>#include <string>using namespace std;int main(){ string n; cin >>n; int left = 0; for(int i = 0 ; i < n.size(); ++i){ left=(left*10+(n[i]-‘0‘))%4; } if(left) cout<<0<<endl; else cout<<4<<endl;}
第二种方法是，由于大数会溢出，根据一个数表示成二进制，当溢出时，截取溢出的位，所以地位的二进制保持不变
#include <stdio.h>using namespace std;int main(){ long long n; scanf("%I64d",&n); if(n%4 == 0) printf("4\n"); else printf("0\n");}
C. Boredom
题目的意思：
给定一个含有n个整数的数组，你可以进行多次操作，每次操作从数组选一个数ak，然后将其删除，然后删除与ak -1和ak +1相等的数，则可以得到ak 分，求进行多次操作后得到的最多的分
解题思路：
利用动规，设dp[i]表示到达第i个数得到的最大的分, cnt[i] 表示第i个数的个数
则dp[i] = max(dp[i-1], dp[i-2]+cnt[i]*i) , 2≤i≤n
dp[1] = cnt[1];
dp[0] = 0
#include <iostream>#include <algorithm>using namespace std;int main(){ int n,a; cin >> n; int cnt[100001]={0}; for(int i = 0 ; i < n;++ i){ cin>>a;cnt[a]++; } long long dp[100001]={0}; dp[0] = 0,dp[1]=cnt[1]; for(int i = 2; i <= 100000;++ i){ dp[i] = max(dp[i-1],dp[i-2]+(long long)cnt[i]*i); } cout<<dp[100000]<<endl;}