A Subsequence Permutation

题目大意

给你一个长度为n的字符串，确定一个最小数字k，将k个字符重新排列后字符串有序

主要思路

记录原字符串，记录排序后的字符串，遍历如果有一个字符不相等ans++，输出ans

AC代码

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. typedef long long ll;
  6. const int N = 200010;
  7. int n, a[N];
  8. char s[N], s1[N];
  10. int main()
  11. {
  12.     int T;
  13.     cin >> T;
  14.     while(T--)
  15.     {
  16.         cin >> n;
  17.         for(int i = 0; i < n; i++)
  18.         {
  19.             cin >> s[i];
  20.             s1[i] = s[i];
  21.         }
  23.         sort(s, s + n);
  25.         int res = 0;
  26.         for(int i = 0; i < n; i++)
  27.         {
  28.             if(s[i] != s1[i]) res++;
  29.         }
  30.         cout << res << endl;
  31.     }
  32.     return 0;
  33. }

B Running for Gold

题目大意

给你n个运动员，每个运动员有5场比赛排名，当x运动员至少有3场比赛比y运动员排名低时说明x运动员优于y运动员，请找出n个运动员中比其他运动员都优秀的运动员，如果不存在输出-1

主要思路

先从1n遍历，假如有比当前运动员更优秀的输出-1

AC代码

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. typedef long long ll;
  6. const int N = 50010;
  7. int n, a[N][10];
  9. bool check(int x, int y)
  10. {
  11.     int cnt = 0;
  12.     for(int i = 1; i <= 5; i++)
  13.     {
  14.         if(a[x][i] < a[y][i]) cnt++;
  15.     }
  16.     if(cnt >= 3) return true;
  17.     return false;
  18. }
  20. int main()
  21. {
  22.     int T;
  23.     cin >> T;
  24.     while(T--)
  25.     {
  26.         cin >> n;
  27.         for(int i = 1; i <= n; i++)
  28.         {
  29.             for(int j = 1; j <= 5; j++)
  30.             {
  31.                 cin >> a[i][j];
  32.             }
  33.         }
  35.         int res = 1;
  36.         for(int i = 2; i <= n; i++)
  37.         {
  38.             if(check(i, res)) res = i;
  39.         }
  40.         int t = res;
  41.         for(int i = 1; i <= n; i++)
  42.         {
  43.             if(i == res) continue;
  44.             if(check(res, i)) ;
  45.             else t = -1;
  46.         }
  47.         cout << t << endl;
  48.     }
  49.     return 0;
  50. }

C Maximize the Intersections

题目大意

给你一个数n，圆上有顺时针的2 * n个点，给你了n条线段，问剩下的点怎么连使得线段交点最多，每个点只能被用一次。

主要思路

首先考虑两线段之间有交点满足什么条件，(x1, y1) (x2, y2) (x1 < y1, x2 < y2)当两线段相交时，一定满足x1 < x2 < y1 < y2或者x2 < x1 < y2 < y1，那么我们把剩余没被用过的点排序，想办法构成最多的相交序列，于是我们可以将排序后的数组前半段和后半段分开，每次从前半段和后半段按顺序取一个数凑成一条线段，这样构造出来的线段交叉最多，也就是交点最多

AC代码

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. #define x first
  6. #define y second
  7. typedef long long ll;
  8. const int N = 1010;
  9. int n, k;
  10. pair<int, int> p[N];
  11. bool st[N];
  12. int num[N];
  14. bool check(int a, int b)
  15. {
  16.     if(p[a].x < p[b].x && p[a].y < p[b].y && p[b].x < p[a].y || p[b].x < p[a].x && p[b].y < p[a].y && p[a].x < p[b].y) return true;
  17.     else return false;
  18. }
  20. int main()
  21. {
  22.     int T;
  23.     cin >> T;
  24.     while(T--)
  25.     {
  26.         memset(st, 0, sizeof(st));
  27.         cin >> n >> k;
  28.         for(int i = 0; i < k; i++)
  29.         {
  30.             int a, b;
  31.             cin >> a >> b;
  32.             if(a > b) swap(a, b);
  33.             p[i] = {a, b};
  34.             st[a] = st[b] = true;
  35.         }
  37.         int cnt = 0;
  38.         for(int i = 1; i <= 2 * n; i++)
  39.         {
  40.             if(!st[i]) num[cnt++] = i;
  41.         }
  44.         for(int i = 0; i < cnt / 2; i++)
  45.         {
  46.             p[k++] = {num[i], num[i + cnt / 2]};
  47.         }
  49.         //for(int i = 0; i < n; i++) cout << p[i].x << ' ' << p[i].y << endl;
  51.         ll res = 0;
  52.         for(int i = 1; i < n; i++)
  53.         {
  54.             for(int j = 0; j < i; j++)
  55.             {
  56.                 if(check(i, j)) res++;
  57.             }
  58.         }
  59.         cout << res << endl;
  60.     }
  61.     return 0;
  62. }

D Array Differentiation

题目大意

给定一个长度为n的a数组，问你能否构造出一个长度为n的数组b，满足b中存在两个数的差为a数组中的元素，且a数组中的元素必须都出现

主要思路

先考虑如何构造数组b，假设b中存在一个数x，根据与a数组的关系，我们必然构造下一个数为x + a[i]，那么当我们遍历到a数组的第n - 1位时，b数组已经长度为n，那么如何才能构造出数组b呢，可以想到，如果a中的一个数能被其他数表示出来，也就是a数组中任意个元素能凑出的数中存在重复元素，那么一定能构造出数组b，n的数据范围为10，所以我们用2进制枚举a数组选与不选的所有状态，找到所有可能的值，如果存在重复元素输出YES，否则输出NO

AC代码

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. #define x first
  6. #define y second
  7. typedef long long ll;
  8. const int N = 500010;
  9. int n, k;
  10. ll a[N];
  12. int main()
  13. {
  14.     int T;
  15.     cin >> T;
  16.     while(T--)
  17.     {
  18.         cin >> n;
  19.         for(int i = 0; i < n; i++)
  20.         {
  21.             cin >> a[i];
  22.         }
  24.         set<int> s;
  25.         for(int i = 0; i < 1 << n; i++)
  26.         {
  27.             int sum = 0;
  28.             for(int j = 0; j < n; j++)
  29.             {
  30.                 if((i >> j) & 1) sum += a[j];
  31.             }
  32.             s.insert(sum);
  33.         }
  34.         if(s.size() < 1 << n) puts("YES");
  35.         else puts("NO");
  36.     }
  37.     return 0;
  38. }