Codeforces Round #316 div2

一场充满血腥hack之战！！！

Problem_A：

题意：

　　n个候选人在m个城市进行投票，每个城市选出票数最多的一个候选人为城市候选人，如果票数相同，则取编号小的候选人。

　　再从这m个城市候选人中选出重复次数最多的，如果有相同的，则取编号小的候选人。

思路：

　　选出每个城市的最高票数，然后找出重复次数最多的即可。

代码：

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 110
22 #define MAXM 100
23 #define dd cout<<"debug"<<endl
24 #define pa {system("pause");}
25 #define p(x) printf("%d
", x)
26 #define pd(x) printf("%.7lf
", x)
27 #define k(x) printf("Case %d: ", ++x)
28 #define s(x) scanf("%d", &x)
29 #define sd(x) scanf("%lf", &x)
30 #define mes(x, d) memset(x, d, sizeof(x))
31 #define do(i, x) for(i = 0; i < x; i ++)
32 #define dod(i, x, l) for(i = x; i >= l; i --)
33 #define doe(i, x) for(i = 1; i <= x; i ++)
34 int n, m;
35 int f[MAXN];
36 
37 int main()
38 {
39     scanf("%d %d", &n, &m);
40     mes(f, 0);
41     int x;
42     int ans_i = 0;
43     int ans_max = 0;
44     for(int j = 0; j < m; j ++)
45     {
46         int ans_x = 1;
47         int max_x = 0;
48         for(int i = 1; i <= n; i ++)
49         {
50             scanf("%d", &x);
51             if(x > max_x)
52             {
53                 max_x = x;
54                 ans_x = i;
55             }
56         }
57         f[ans_x] ++;
58         if(f[ans_x] > ans_max || (f[ans_x] == ans_max) && ans_i > ans_x)
59         {
60             ans_max = f[ans_x];
61             ans_i = ans_x;
62         }
63     }
64     printf("%d
", ans_i);
65     return 0;
66 }

View Code

Problem_B：

题意：

　　在一个长为n的数轴上，两个人玩游戏，Misha 和 Andrew 分别在这数轴上随机选取两个点m， a，再随机选一个点 c。

　　如果 m 到 c 的距离小于等于 a 到 c 的距离，则Misha获胜，否则Andrew获胜。

　　现在已知n, m，求使得Andrew获胜几率最大的点是哪个。

思路：

　　已知m, 那么点m 就将数轴分成了两个部分，左边和右边。

　　如果左边点的数目大于右边，那么当取点 m - 1 时， Andrew的胜率最大（因为如果取点c 在左边，有m - 1种选择，右边则有n - m种， c 点在左边的话， Andrew都是胜利的，而m - 1 > n - m）所以此时概率是最大的，同理右边也可以这么分析。

代码：

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 1000000
22 #define MAXM 100
23 #define dd cout<<"debug"<<endl
24 #define pa {system("pause");}
25 #define p(x) printf("%d
", x)
26 #define pd(x) printf("%.7lf
", x)
27 #define k(x) printf("Case %d: ", ++x)
28 #define s(x) scanf("%d", &x)
29 #define sd(x) scanf("%lf", &x)
30 #define mes(x, d) memset(x, d, sizeof(x))
31 #define do(i, x) for(i = 0; i < x; i ++)
32 #define dod(i, x, l) for(i = x; i >= l; i --)
33 #define doe(i, x) for(i = 1; i <= x; i ++)
34 int n, m;
35 
36 int main()
37 {
38     scanf("%d %d", &n, &m);
39     int r = n - m;
40     int l = m - 1;
41     int ans = r > l ? m + 1 : m - 1;
42     if(n == 1 && m == 1) ans = 1;
43     printf("%d
", ans);
44     return 0;
45 }

View Code

Problem_C：

题意：

　　给一个长度为n的字符串，m次操作。

　　每次操作将第x为的字符变成给定的字符。

　　每次操作后，输出连续的 . 的区间的长度，这里区间的长度 = . 的数量 - 1

思路：

　　先将未修改之前的长度算出来，每次修改后，对修改的地方进行判断是增加了还是减少了即可。

　　如果将一个字母变成 . 那么如果这个 . 之前是. 那么数量就加一，后面也是一样。

　　如果 . 变成字母，前后相邻的如果是 . 那么数量就减一。

代码：

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 500000
22 #define MAXM 100
23 #define dd cout<<"debug"<<endl
24 #define pa {system("pause");}
25 #define p(x) printf("%d
", x)
26 #define pd(x) printf("%.7lf
", x)
27 #define k(x) printf("Case %d: ", ++x)
28 #define s(x) scanf("%d", &x)
29 #define sd(x) scanf("%lf", &x)
30 #define mes(x, d) memset(x, d, sizeof(x))
31 #define do(i, x) for(i = 0; i < x; i ++)
32 #define dod(i, x, l) for(i = x; i >= l; i --)
33 #define doe(i, x) for(i = 1; i <= x; i ++)
34 char str[MAXN];
35 int n, m;
36 void solve()
37 {
38     int count = 0,tmp = 0;
39     for(int i = 1; i <= n; i ++)
40     {
41         if(str[i] == '.') tmp ++;
42         else
43         {
44             if(tmp > 1) count += (tmp - 1);
45             tmp = 0;
46         }
47     }
48     if(tmp > 1) count += (tmp - 1);
49     while(m --)
50     {
51         int pos;
52         string stemp;
53         cin >> pos;
54         cin >> stemp;
55         if((stemp[0] == '.' && str[pos] == '.') || (stemp[0]!='.'&&str[pos]!='.'))
56         {
57             cout << count << endl;
58             continue;
59         }
60         if(stemp[0] == '.' && str[pos] != '.')
61         {
62             if(pos-1 >= 1 && str[pos-1] == '.') count++;
63             if(pos+1 <= n && str[pos+1] == '.') count++;
64             str[pos] = '.';
65         }
66         if(stemp[0] != '.' && str[pos] == '.')
67         {
68             if(pos-1 >= 1&&str[pos-1] == '.') count--;
69             if(pos+1 <= n&&str[pos+1] == '.') count--;
70             str[pos] = stemp[0];
71         }
72         cout << count << endl;
73     }
74 }
75 
76 int main()
77 {
78     cin>>n>>m;
79     cin>>str+1;
80     solve();
81     return 0;
82 }

View Code