A And Then There Were K

题目大意

给一个n，求最大的k满足
n & (n−1) & (n−2) & (n−3) & … (k) = 0

主要思路

当n的二进制位数-1时必然会经过1xxxx -> 10000 这时把前面的数都&起来，由于第一位1无法消除，所以最大的数一定是10000 - 1是第一个能把n的第一位1消除的，所以答案就为n的二进制位的个数减1个1组成的数

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. using namespace std;
  11. #define int long long
  12. #define debug(a) cout << #a << " = " << a << endl;
  13. #define x first
  14. #define y second
  15. typedef pair<int, int> P;
  17. signed main(void)
  18. {
  19.     int T;
  20.     cin >> T;
  21.     while(T--)
  22.     {
  23.         int n;
  24.         cin >> n;
  25.         int res = 0;
  26.         while(n)
  27.         {
  28.             res <<= 1;
  29.             res++;
  30.             n >>= 1;
  31.         }
  32.         res >>= 1;
  33.         cout << res << endl;
  34.     }
  35.     return 0;
  36. }

B Palindrome Game (easy version)

题目大意

给一个回文串，先手和后手有两种操作：

  1. 把一个0，变成一个1，花费1的代价
  2. 如果前一次操作不是2操作并且当前串不是个回文串，把当前串反转，不花费代价

ALICE先手，BOB后手

主要思路

由于是回文串，ALICE先手只能把0变为1。

  • 考虑0的个数为偶数时，BOB的最优操作是在对称位置将0变成1，在仅有2个0的时候，还是回文串ALICE只能把0变为1，此时BOB翻转字符串，下次操作ALICE不能翻转，那么BOB必胜
  • 考虑0的个数为奇数时，那么ALICE先手把中间的0变为1，此时相当于BOB先手，ALICE必胜

考虑特殊情况

  • 当场上开始没有0时，为平局
  • 当场上仅有1个0时，BOB必胜
  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. using namespace std;
  11. #define int long long
  12. #define debug(a) cout << #a << " = " << a << endl;
  13. #define x first
  14. #define y second
  15. typedef pair<int, int> P;
  17. signed main(void)
  18. {
  19.     int T;
  20.     cin >> T;
  21.     while(T--)
  22.     {
  23.         int n;
  24.         cin >> n;
  25.         string t;
  26.         cin >> t;
  27.         int cnt0 = 0;
  28.         for(int i = 0; i < t.size(); i++)
  29.         {
  30.             if(t[i] == '0') cnt0++;
  31.         }
  33.         if(cnt0 == 0) puts("DRAW");
  34.         else if(cnt0 % 2 == 0 || cnt0 == 1) puts("BOB");
  35.         else puts("ALICE");
  36.     }
  37.     return 0;
  38. }

C Palindrome Game (hard version)

题目大意

跟上题相同，不过给的串不一定是回文串

主要思路

  • 回文串情况与上题相同，接下来仅考虑不是回文串情况

  • 由于不是回文串，ALICE开局翻转即可，那么BOB的最佳操作就必须将0改为1，且向回文串靠近，这样ALICE才能不翻转，但在BOB将串改为回文串之前，ALICE可以讲串提前改为回文串，那么BOB必须修改(ALICE真的太坏了)，ALICE必胜。

考虑特殊情况

  • 当场上开始没有0时，为平局

  • 当开局场上仅将一个0变为1就能修改为回文串时，必平局

    • ALICE修改为回文串，BOB也必须修改
    • ALICE翻转，BOB修改为回文串，ALICE修改
  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <unordered_map>
  8. #include <set>
  9. #include <queue>
  10. using namespace std;
  12. #define int long long
  13. #define debug(a) cout << #a << " = " << a << endl;
  14. #define x first
  15. #define y second
  16. typedef pair<int, int> P;
  19. signed main(void)
  20. {
  21.     ios::sync_with_stdio(false);
  22.     int T;
  23.     cin >> T;
  24.     while(T--)
  25.     {
  26.         int n;
  27.         cin >> n;
  28.         string t;
  29.         cin >> t;
  30.         bool flag = true;
  31.         int cnt0 = 0;
  32.         for(int i = 0; i < t.size(); i++)
  33.         {
  34.             if(t[i] != t[t.size() - 1 - i]) flag = false;
  35.             if(t[i] == '0') cnt0++;
  36.         }
  38.         if(flag)
  39.         {
  40.             if(cnt0 == 0) puts("DRAW");
  41.             else if(cnt0 % 2 == 0 || cnt0 == 1) puts("BOB");
  42.             else puts("ALICE");
  43.         }
  44.         else
  45.         {
  46.             if(cnt0 == 2 && t[t.size() / 2] == '0' && t.size() % 2) puts("DRAW");
  47.             else puts("ALICE");
  48.         }
  49.     }
  50.     return 0;
  51. }

C Sequence Pair Weight

题目大意

定义sum为一个数列中相同的数在不同位置的对数，问对于一个数列，它的串及其所有子串的sum和为多少

主要思路

经典套路！

我们先考虑一个数对对答案的贡献。

假设a1, a2, a3, …., ai, 中a3与ai相同，那么这个数对对答案的贡献首先a3可以向前拓展2个位置，ai可以向后拓展到n位置，也就是字串除必须有a3~ai外，a3也可以为，a2，a3或者a1，a2，a3一共3种情况，ai向后拓展同理，所以这个数对对答案的贡献为3 * (n - i + 1)。

接下来考虑多个数对情况

假设a1, a2, a3, …., ai，中a1，a3与ai相同，那么ai可以与前两个数凑成数对，也就是(1 + 3) * (n - i + 1)，所以我们只需要维护前i个数中，a[i]的下标和即可

如果求所有的数的贡献，只要记录相同数出现的下标之和，每次结果加上 （当前数出现过的下标之和）*（n-i+1）

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. using namespace std;
  12. #define int long long
  13. #define debug(a) cout << #a << " = " << a << endl;
  14. #define x first
  15. #define y second
  16. typedef pair<int, int> P;
  18. const int N = 100010;
  19. int n, a[N];
  21. signed main(void)
  22. {
  23.     std::ios::sync_with_stdio(false);
  24.     unordered_map<int, int> mp;
  25.     int T;
  26.     cin >> T;
  27.     while(T--)
  28.     {
  29.         mp.clear();
  30.         int res = 0;
  31.         int n;
  32.         cin >> n;
  33.         for(int i = 1; i <= n; i++)
  34.         {
  35.             cin >> a[i];
  36.             res += mp[a[i]] * (n - i + 1);
  37.             mp[a[i]] += max((int)1, i);
  38.         }
  39.         cout << res << endl;
  40.     }
  41.     return 0;
  42. }