这个题目感觉略简单，但是后两题还是一个没做出来╮(╯_╰)╭

A. A and B and Chess

就是比较一下棋盘上两边的权重。

1 #include 
      
        2 using namespace std; 3  4 const int maxn = 10; 5  6 char s[maxn][maxn]; 7  8 int weight(char c) 9 {10     if(c == 'Q' || c == 'q') return 9;11     if(c == 'R' || c == 'r') return 5;12     if(c == 'B' || c == 'b') return 3;13     if(c == 'N' || c == 'n') return 3;14     return 1;15 }16 17 int main()18 {19     //freopen("in.txt", "r", stdin);20 21     for(int i = 0; i < 8; i++) scanf("%s", s[i]);22 23     int W = 0, B = 0;24     for(int i = 0; i < 8; i++)25         for(int j = 0; j < 8; j++)26         {27             if(s[i][j] == '.' || s[i][j] == 'K' || s[i][j] == 'k') continue;28             if(s[i][j] >= 'a') B += weight(s[i][j]);29             else W += weight(s[i][j]);30         }31 32     if(W > B) puts("White");33     else if(W < B) puts("Black");34     else puts("Draw");35 36     return 0;37 }
      

 

B. A and B and Compilation Errors

有一个数组，每次会减少一个数，把这个数找出来。

先排序然后比较即可。

1 #include 
      
        2 using namespace std; 3  4 const int maxn = 100000 + 10; 5  6 int a[maxn], b[maxn], c[maxn]; 7  8 int main() 9 {10     //freopen("in.txt", "r", stdin);11 12     int n;13     scanf("%d", &n);14     for(int i = 0; i < n; i++) scanf("%d", &a[i]);15     for(int i = 0; i < n-1; i++) scanf("%d", &b[i]);16     for(int i = 0; i < n-2; i++) scanf("%d", &c[i]);17 18     sort(a, a + n);19     sort(b, b + n - 1);20     sort(c, c + n - 2);21 22     int i;23     for(i = 0; i < n - 1; i++) if(a[i] != b[i]) { printf("%d\n", a[i]); break; }24     if(i == n - 1) printf("%d\n", a[n-1]);25 26     for(i = 0; i < n - 2; i++) if(b[i] != c[i]) { printf("%d\n", b[i]); break; }27     if(i == n - 2) printf("%d\n", b[n-2]);28 29     return 0;30 }
      

 

C. A and B and Team Training

有新队员和老队员，有两种组队方式：一老带两新、两老带一新。

一直新老队员的数量，求能组的最多的队伍。

贪心：哪方人数多哪方就出两个队员，另一方出一个队员组队。

1 #include 
      
        2 using namespace std; 3  4 const int maxn = 500000 + 10; 5  6 int main() 7 { 8     //freopen("in.txt", "r", stdin); 9 10     int n, m, ans = 0;11     scanf("%d%d", &n, &m);12     while(n + m >= 3 && n && m)13     {14         if(n > m) { n -= 2; m--; ans++; }15         else { m -= 2; n--; ans++; }16     }17 18     printf("%d\n", ans);19 20     return 0;21 }
      

 

D. A and B and Interesting Substrings

题意：

给26个字母一个权重，还有一个字符串，统计满足这些条件的子串的个数：

• 首尾字母相同
• 除了首尾字母，其他字母的权值之和为0
• 子串的长度至少为2

群里的巨巨提示说用map乱搞，也还是没想出来。但一看代码就马上明白了。

首先，计算连续子串的和可以通过计算前缀和预处理一下，注意到可能会溢出，所以要用long long来存。

然后从左往右扫描：

用一个map<long, int> cnt[26]; 其中cnt[x][sum]记录第i个字母(a是第0个)结尾的、和为sum的前缀子串。

扫描到当前位置p是第i个字母，累加之前有多少个前缀子串也是以第i个字母结尾，且前缀和为sum_p-1，因为这对应着这两个字母之间的子串和为0.

1 #include 
      
        2 using namespace std; 3 typedef long long LL; 4 const int maxn = 100000 + 10; 5  6 int w[30]; 7 char s[maxn]; 8 LL sum[maxn]; 9 map
       
         cnt[30];10 11 int main()12 {13     //freopen("in.txt", "r", stdin);14 15     for(int i = 0; i < 26; i++) scanf("%d", &w[i]);16     scanf("%s", s + 1);17     int l = strlen(s + 1);18     LL ans = 0;19     for(int i = 1; i <= l; i++)20     {21         int x = s[i] - 'a';22         sum[i] = sum[i - 1] + w[x];23         ans += cnt[x][sum[i-1]];24         cnt[x][sum[i]]++;25     }26 27     printf("%I64d\n", ans);28 29     return 0;30 }