首页 > 代码库 > Codeforces 258 Div2
Codeforces 258 Div2
A题，n*m根木棍，相交放置，轮流取走相交的两根，最后谁不能行动，则输掉。
min(n,m)&1 为1则先取者赢。
B题，给定一个长度为n，且各不相同的数组，问能否通过交换连续一段L....R使得变成单调递增。
如果一开始就是递增的，那么直接输出L。。。R就是1 1，交换一个就行了；否则判断中间是否有且一段单调递减，且两端交换后使得数组递增。
代码：
1 //Template updates date: 20140718 2 #include <iostream> 3 #include <sstream> 4 #include <cstdio> 5 #include <climits> 6 #include <ctime> 7 #include <cctype> 8 #include <cstring> 9 #include <cstdlib> 10 #include <string> 11 #include <stack> 12 #include <set> 13 #include <map> 14 #include <cmath> 15 #include <vector> 16 #include <queue> 17 #include <algorithm> 18 #define esp 1e-6 19 #define inf 0x3f3f3f3f 20 #define pi acos(-1.0) 21 #define pb push_back 22 #define lson l, m, rt<<1 23 #define rson m+1, r, rt<<1|1 24 #define lowbit(x) (x&(-x)) 25 #define mp(a, b) make_pair((a), (b)) 26 #define bit(k) (1<<(k)) 27 #define iin freopen("pow.in", "r", stdin); 28 #define oout freopen("pow.out", "w", stdout); 29 #define in freopen("solve_in.txt", "r", stdin); 30 #define out freopen("solve_out.txt", "w", stdout); 31 #define bug puts("********))))))"); 32 #define Inout iin oout 33 #define inout in out 34 35 #define SET(a, v) memset(a, (v), sizeof(a)) 36 #define SORT(a) sort((a).begin(), (a).end()) 37 #define REV(a) reverse((a).begin(), (a).end()) 38 #define READ(a, n) {REP(i, n) cin>>(a)[i];} 39 #define REP(i, n) for(int i = 0; i < (n); i++) 40 #define VREP(i, n, base) for(int i = (n); i >= (base); i--) 41 #define Rep(i, base, n) for(int i = (base); i < (n); i++) 42 #define REPS(s, i) for(int i = 0; (s)[i]; i++) 43 #define pf(x) ((x)*(x)) 44 #define mod(n) ((n)) 45 #define Log(a, b) (log((double)b)/log((double)a)) 46 #define Srand() srand((int)time(0)) 47 #define random(number) (rand()%number) 48 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a) 49 50 using namespace std; 51 typedef long long LL; 52 typedef unsigned long long ULL; 53 typedef vector<int> VI; 54 typedef pair<int,int> PII; 55 typedef vector<PII> VII; 56 typedef vector<PII, int> VIII; 57 typedef VI:: iterator IT; 58 typedef map<string, int> Mps; 59 typedef map<int, int> Mpi; 60 typedef map<int, PII> Mpii; 61 typedef map<PII, int> Mpiii; 62 63 const int maxn = 100000 + 100; 64 int a[maxn]; 65 66 int main() { 67 68 int n; 69 Rep(i, scanf("%d", &n), n+1) scanf("%d", a+i); 70 int l = 0, r = 0; 71 int ok = 0; 72 a[n+1] = inf; 73 Rep(i, 1, n+2) { 74 if(a[i] > a[i-1]) { 75 if(!l) 76 continue; 77 else { 78 if(ok && !r) 79 r = i-1; 80 } 81 } else if(a[i] < a[i-1]) { 82 if(!ok) 83 ok = 1, l = i-1; 84 if(r) { 85 cout<<"no"<<endl; 86 return 0; 87 } 88 } else { 89 cout<<"no"<<endl; 90 return 0; 91 } 92 } 93 if(l) { 94 if(a[l] < a[r+1] && a[r] > a[l-1]) { 95 cout<<"yes"<<endl; 96 cout<<l <<‘ ‘<<r<<endl; 97 } else { 98 cout<<"no"<<endl; 99 }100 } else {101 cout<<"yes"<<endl;102 cout<<1<<‘ ‘<<1<<endl;103 }104 return 0;105 }
写得挫。
C题，3个球队，总共n场比赛，已进行k场，知道两个球队之间赢得场数的绝对值，如|x1-x2| = d1, |x2-x3| = d2, 问剩下的比赛中是否存在一种可能使得三个队伍赢得场数相等。
分析：题意知道每场比赛只用知道谁赢就行 ，不用顾忌各种规则，前k场中分别可能情况：
令x = x2;
x+d1, x, x+d2;
x+d1, x, x-d2;
x-d1, x, x+d2;
x-d1, x, x-d1;
对应4种情况求出x，在求出x1,x2,x3,判断满足0<=xi<=n/3 && xi <= k;
就可以了。
代码：
1 //Template updates date: 20140718 2 #include <iostream> 3 #include <sstream> 4 #include <cstdio> 5 #include <climits> 6 #include <ctime> 7 #include <cctype> 8 #include <cstring> 9 #include <cstdlib>10 #include <string>11 #include <stack>12 #include <set>13 #include <map>14 #include <cmath>15 #include <vector>16 #include <queue>17 #include <algorithm>18 #define esp 1e-619 #define inf 0x3f3f3f3f20 #define pi acos(-1.0)21 #define pb push_back22 #define lson l, m, rt<<123 #define rson m+1, r, rt<<1|124 #define lowbit(x) (x&(-x))25 #define mp(a, b) make_pair((a), (b))26 #define bit(k) (1<<(k))27 #define iin freopen("pow.in", "r", stdin);28 #define oout freopen("pow.out", "w", stdout);29 #define in freopen("solve_in.txt", "r", stdin);30 #define out freopen("solve_out.txt", "w", stdout);31 #define bug puts("********))))))");32 #define Inout iin oout33 #define inout in out34 35 #define SET(a, v) memset(a, (v), sizeof(a))36 #define SORT(a) sort((a).begin(), (a).end())37 #define REV(a) reverse((a).begin(), (a).end())38 #define READ(a, n) {REP(i, n) cin>>(a)[i];}39 #define REP(i, n) for(int i = 0; i < (n); i++)40 #define VREP(i, n, base) for(int i = (n); i >= (base); i--)41 #define Rep(i, base, n) for(int i = (base); i < (n); i++)42 #define REPS(s, i) for(int i = 0; (s)[i]; i++)43 #define pf(x) ((x)*(x))44 #define mod(n) ((n))45 #define Log(a, b) (log((double)b)/log((double)a))46 #define Srand() srand((int)time(0))47 #define random(number) (rand()%number)48 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a)49 50 using namespace std;51 typedef long long LL;52 typedef unsigned long long ULL;53 typedef vector<int> VI;54 typedef pair<int,int> PII;55 typedef vector<PII> VII;56 typedef vector<PII, int> VIII;57 typedef VI:: iterator IT;58 typedef map<string, int> Mps;59 typedef map<int, int> Mpi;60 typedef map<int, PII> Mpii;61 typedef map<PII, int> Mpiii;62 63 LL n, k, d1, d2;64 int a[][2] = {{-1, 1} ,{-1, -1}, {1, 1}, {1, -1}};65 66 int main() {67 int T;68 for(int t = scanf("%d", &T); t <= T; t++) {69 scanf("%I64d%I64d%I64d%I64d", &n, &k, &d1, &d2);70 if(n%3) {71 puts("no");72 continue;73 }74 int ok = 0;75 LL nn;76 REP(i, 4) {77 nn = k;78 LL tmp = (LL)a[i][0]*d1+(LL)a[i][1]*d2;79 nn -= tmp;80 if(nn < 0 || nn%3)81 continue;82 nn /= 3;83 if(nn > n/3 || nn > k)84 continue;85 LL x1 = nn+(LL)a[i][0]*d1;86 LL x2 = nn+(LL)a[i][1]*d2;87 if(x1 < 0 || x1 > n/3 || x2 < 0 || x2 > n/3 || x1 > k || x2 > k)88 continue;89 ok = 1;90 break;91 }92 puts(ok ? "yes" : "no");93 }94 return 0;95 }
D题，给定仅有‘a‘，‘a‘组成的字符串，定义一种子串：通过合并连续的字母最后可以得到一个回文串。如”aaabbaaa"最后得到"aba"。
很容易想到一个字串首尾字符相等时就为这样的要求的特殊字串。
题目要求奇数长度和偶数长度这样的字串个数，统计每个字符分别用dp[0][s[i]-‘a‘], dp[1][s[i]-‘a‘],表示位于i及之前的奇数位置和偶数位置的s[i]字符个数，
这样偶数长度ans0 += dp[!(i&1)][s[i]-‘a‘], 奇数长度ans1 += dp[i&1][s[i]-‘a‘];
代码：
1 //Template updates date: 20140718 2 #include <iostream> 3 #include <sstream> 4 #include <cstdio> 5 #include <climits> 6 #include <ctime> 7 #include <cctype> 8 #include <cstring> 9 #include <cstdlib>10 #include <string>11 #include <stack>12 #include <set>13 #include <map>14 #include <cmath>15 #include <vector>16 #include <queue>17 #include <algorithm>18 #define esp 1e-619 #define inf 0x3f3f3f3f20 #define pi acos(-1.0)21 #define pb push_back22 #define lson l, m, rt<<123 #define rson m+1, r, rt<<1|124 #define lowbit(x) (x&(-x))25 #define mp(a, b) make_pair((a), (b))26 #define bit(k) (1<<(k))27 #define iin freopen("pow.in", "r", stdin);28 #define oout freopen("pow.out", "w", stdout);29 #define in freopen("solve_in.txt", "r", stdin);30 #define out freopen("solve_out.txt", "w", stdout);31 #define bug puts("********))))))");32 #define Inout iin oout33 #define inout in out34 35 #define SET(a, v) memset(a, (v), sizeof(a))36 #define SORT(a) sort((a).begin(), (a).end())37 #define REV(a) reverse((a).begin(), (a).end())38 #define READ(a, n) {REP(i, n) cin>>(a)[i];}39 #define REP(i, n) for(int i = 0; i < (n); i++)40 #define VREP(i, n, base) for(int i = (n); i >= (base); i--)41 #define Rep(i, base, n) for(int i = (base); i < (n); i++)42 #define REPS(s, i) for(int i = 0; (s)[i]; i++)43 #define pf(x) ((x)*(x))44 #define mod(n) ((n))45 #define Log(a, b) (log((double)b)/log((double)a))46 #define Srand() srand((int)time(0))47 #define random(number) (rand()%number)48 #define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a)49 50 using namespace std;51 typedef long long LL;52 typedef unsigned long long ULL;53 typedef vector<int> VI;54 typedef pair<int,int> PII;55 typedef vector<PII> VII;56 typedef vector<PII, int> VIII;57 typedef VI:: iterator IT;58 typedef map<string, int> Mps;59 typedef map<int, int> Mpi;60 typedef map<int, PII> Mpii;61 typedef map<PII, int> Mpiii;62 63 64 const int maxn = 100000 + 100;65 char s[maxn];66 LL dp[2][2];67 int main() {68 69 scanf("%s", s);70 LL ans1 = 0, ans2 = 0;71 REPS(s, i) {72 int x = s[i]-‘a‘;73 int y = i&1;74 dp[y][x]++;75 ans1+=dp[y][x];76 ans2+=dp[y^1][x];77 }78 cout<<ans2<<‘ ‘<<ans1<<endl;79 return 0;80 }
E题，n个箱子装有fi朵花，箱子内花完全一样，箱子之间花看做不同，求从中选出s朵花，有多少选法？
我也不会数论，不过还是硬着头皮看懂了。以后要慢慢积累啊
分析： 设第i个箱子选出xi朵花。得到x1+x2+x3.....xn = s, 且0<=xi<=fi.
那么选花方案数就是解的组数，即（1+x+x^2+x^3+.....x^f1)*................(1+x+x^2+x^3+x^4.........x^fn)
= (1-x^(f1+1))******(1-x^(fn+1)) *(1-x)^(-n)（等比数列）中x^s系数
然后就是求里面x^s的系数了。
这个先算出前面部分各次幂的系数诚意后面(1-x)^(-n)相应系数，使得总系数为s。
其中（1-x)^(-n)幂为k的系数为C(n+k-1, k) = C(n+k-1, n-1)由于n很小（n<=20).
所以可以通过枚举法求前面的系数，然后C(n+k-1,n-1)利用逆元公式。
代码：
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。