CodeforcesRound#550(Div. 3)(ABCDF题解)

http://codeforces.com/contest/1144/problem/A

题意：对于给定字符串，是否符合所有字母都只出现了一次并且排序后是连续的。

　　　比如 "adfceb" 就是合法的，"az" 和 "aab" 是不合法的。

思路：排序字符串后比较邻近的即可。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n,m,k;
 5 
 6 int main()
 7 {
 8     char in[105];
 9     int vis[105];
10     cin >> n;
11     while(n --){
12         memset(vis,0,sizeof(vis));
13         scanf("%s",in);
14         int L = strlen(in);
15         if(L == 1){cout << "YES" << endl;continue;}
16         for(int i = 0;i < L;i ++){
17             vis[i] = (int)(in[i] - 'a');
18         }
19         sort(vis,vis + L);
20         int a = vis[0];
21         int f = 0;
22         for(int i = 1;i < L;i ++){
23             if(vis[i] == a + 1){
24                 a ++;
25             }
26             else{f = 1;break;}
27         }
28         if(f){cout << "NO" << endl;}
29         else{cout << "YES" << endl;}
30     }
31 
32     return 0;
33 }

http://codeforces.com/contest/1144/problem/B

题意：对于给定数列，每次可以删掉一个某个数字，但是必须与上一个删去数字的奇偶性不同，否则无法删去。

　　　第一个删去的数字是任意的。无法继续删除后，统计数列的和作为答案，要求输出最小可能的答案。

思路：统计奇偶数字即可。排序后从小的贪心。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n,m,k;
 5 
 6 int main()
 7 {
 8     int a[2005];
 9     cin >> n;
10     int t1 = 0,t2 = 0;
11     for(int i = 0;i < n;i ++){
12         cin >> a[i];
13         if(a[i] % 2){t1 ++;}
14         else{t2 ++;}
15     }
16     if(abs(t1 - t2) <= 1){
17         cout << "0" << endl;
18         return 0;
19     }
20     sort(a,a + n);
21     if(t1 > t2){
22         int ans = 0;
23         int p = t1 - t2 - 1;
24         for(int i = 0;i < n;i ++){
25             if(!p){break;}
26             if(a[i] % 2){ans += a[i];p --;}
27         }
28         cout << ans << endl;
29     }
30     else{
31         int ans = 0;
32         int p = t2 - t1 - 1;
33         for(int i = 0;i < n;i ++){
34             if(!p){break;}
35             if(a[i] % 2 == 0){ans += a[i];p --;}
36         }
37         cout << ans << endl;
38     }
39 
40     return 0;
41 }

http://codeforces.com/contest/1144/problem/C

题意：对于给定数列，是否可以将其拆分成一个严格单调递增，一个严格单调递减序列。空序列也算是严格单调的。

思路：数列中不能出现多于两个的同种数，否则就是NO。

　　　对于合法数列，排序后按奇偶位置分成两个即可。

#include <bits/stdc++.h>
using namespace std;

int n,m,k;
int a[200005];
int a1[200005];
int a2[200005];
int vis[200005];
int main()
{
    int n;
    cin >> n;
    memset(vis,0,sizeof(vis));
    for(int i = 0;i < n;i ++){
        cin >> a[i];
        vis[a[i]] ++;
    }
    for(int i = 0;i <= 200000;i ++){
        if(vis[i] >= 3){
            cout << "NO" << endl;
            return 0;
        }
    }
    sort(a,a + n);
    int cnt1 = 0,cnt2 = 0;
    for(int i = 0;i < n;i ++){
        if(i % 2){a1[cnt1 ++] = a[i];}
        else{a2[cnt2 ++] = a[i];}
    }
    cout << "YES" << endl;
    cout << cnt1 << endl;
    for(int i = 0;i < cnt1;i ++){
        if(i != 0){cout << " ";}
        cout << a1[i];
    }cout << endl;
    cout << cnt2 << endl;
    for(int i = cnt2 - 1;i >= 0;i --){
        if(i != cnt2 - 1){cout << " ";}
        cout << a2[i];
    }cout << endl;

    return 0;
}

http://codeforces.com/contest/1144/problem/D

题意：对于给定数列，你可以对任意一个数字进行以下两种操作：

　　　1、将这个数字 a[i] 改成 a[i] + | a[i] - a[j] |，并且 | i - j | == 1，竖线是绝对值符号。

　　　2、将这个数字 a[i] 改成 a[i] - | a[i] - a[j] |，并且 | i - j | == 1，竖线是绝对值符号。

　　　问你在最少多少次操作后，这个数列的所有数字都相等。题目保证所给数列可以变成要求的数列。

思路：明显最小操作数应该是数列长度减去数列中最多数字的数量，因为一定能转化成要求数列，所以对于任意两个相邻数，一定能将他们两个变为相等。

　　　所以只需要找到任意一个众数，然后向两边模拟即可。

　　　虽然题目不难，但还是错了好几发。。。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n,m,k;
 5 int a[200005];
 6 int vis[200005];
 7 int main()
 8 {
 9     int n;
10     cin >> n;
11     memset(vis,0,sizeof(vis));
12     int maxx = 0,s = 0;
13     for(int i = 1;i <= n;i ++){
14         cin >> a[i];
15         vis[a[i]] ++;
16         if(vis[a[i]] > maxx){
17             maxx = vis[a[i]];
18             s = a[i];
19         }
20     }
21     cout << n - maxx << endl;
22     int st = -1;
23     for(int i = 1;i <= n;i ++){
24         if(a[i] == s){st = i;break;}
25     }
26     for(int i = st - 1;i >= 1;i --){
27         if(a[i] < a[i + 1]){
28             printf("1 %d %d
",i,i + 1);
29         }
30         else if(a[i] > a[i + 1]){
31             printf("2 %d %d
",i,i + 1);
32         }
33         a[i] = a[i + 1];
34     }
35     for(int i = st + 1;i <= n;i ++){
36         if(a[i] < a[i - 1]){
37             printf("1 %d %d
",i,i - 1);
38         }
39         else if(a[i] > a[i - 1]){
40             printf("2 %d %d
",i,i - 1);
41         }
42         a[i] = a[i - 1];
43     }
44 
45     return 0;
46 }

http://codeforces.com/contest/1144/problem/F

题意：给你一个无向图，你要将所有的边都变成有向边，问是否存在一种策略，使得所有的点都只有入度或者出度。

思路：裸的图上搜索，依照题意模拟即可。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n,m,k;
 5 vector<int> V[200005];
 6 int vis[200005];
 7 int ans[200005];
 8 int flag = 0;
 9 struct Edge{
10     int f,t;
11 }e[200005];
12 
13 void dfs(int x){
14     vis[x] = 1;
15     for(int i = 0;i < V[x].size();i ++){
16         if(vis[V[x][i]] == 0){
17             ans[V[x][i]] = 3 - ans[x];
18             dfs(V[x][i]);
19         }
20         else{
21             if(ans[V[x][i]] == ans[x]){
22                 flag = 1;
23             }
24         }
25     }
26 }
27 
28 int main()
29 {
30     memset(vis,0,sizeof(vis));
31     memset(ans,-1,sizeof(ans));
32     int n,m;
33     cin >> n >> m;
34     for(int i = 1;i <= m;i ++){
35         cin >> e[i].f >> e[i].t;
36         V[e[i].f].push_back(e[i].t);
37         V[e[i].t].push_back(e[i].f);
38     }
39     ans[1] = 1;
40     dfs(1);
41     if(flag){cout << "NO" << endl;return 0;}
42     cout << "YES" << endl;
43     for(int i = 1;i <= m;i ++){
44         cout << (ans[e[i].f] - 1);
45     }
46 
47     return 0;
48 }