• 2022CCPC威海补题：A C E G J

    A 

    ​​​​​​A - Dunaihttps://codeforces.com/gym/104023/problem/A

    签到题，分别记录每个位置所有出现的选手数量，另外处理一个每个位置的冠军数量。

    贪心地每队分配一个冠军选手，看是否可行，如果不可行，则可以直接输出所有位置中最小选手数量（木桶效应）

    可以模拟，也可以直接推理出答案

    ACcode

    1. #include 
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #define endl '\n'
    12. #define int unsigned long long 
    13. #define lowbit(x) (x &-x)
    14. #define mh(x) memset(x, -1, sizeof h)
    15. #define debug(x) cerr << #x << "=" << x << endl;
    16. #define brk exit(0);
    17. using namespace std;
    18. void inline TLE() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }
    19. const int N = 2e6 + 50;
    20. const int M = 2 * N;
    21. const int mod = 998244353;
    22. const double esp = 1e-6;
    23. const double pi = acos(-1);
    24. typedef pair<int, int> PII;
    25. typedef long long ll;
    26. setst;
    27. int cnt1[N], cnt2[N];
    28. signed  main()
    29. {
    30.     int n;
    31.     cin >> n;
    32.     for (int i = 1;i <= n;i++) {
    33.         for (int j = 1;j <= 5;j++) {
    34.             string s;cin >> s;
    35.             st.insert(s);
    36.         }
    37.     }
    38.     int m;
    39.     cin >> m;
    40.     while (m--) {
    41.         string s;int x;
    42.         cin >> s >> x;
    43.         cnt1[x]++;
    44.         if (st.count(s)) {
    45.             cnt2[x]++;
    46.         }
    47.     }
    48.     int max1 = cnt2[1] + cnt2[2] + cnt2[3] + cnt2[4] + cnt2[5];//贪心地让每个冠军选手分配到不同队伍
    49.     int max2 = min({ cnt1[1],cnt1[2],cnt1[3],cnt1[4],cnt1[5] });
    50.     cout << min(max1, max2) << endl;
    51.     return 0;
    52. }

     模拟

    ACcode

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. const int N = 1e5 + 10;
    8.  
    9. using namespace std;
    10. struct node {
    11.     int m, id;
    12. };
    13. vector v;
    14. int a[10], b[N];
    15. set mp;
    16. typedef pair<int, int> PII;
    17. int main() {
    18.     int n;
    19.     cin >> n;
    20.     for (int i = 1; i <= n; i++) {
    21.         for (int j = 1; j <= 5; j++) {
    22.             string x;
    23.             cin >> x;
    24.             mp.insert(x);
    25.         }
    26.     }
    27.     int m;
    28.     cin >> m;
    29.     for (int i = 1; i <= m; i++) {
    30.         string s;
    31.         int x;
    32.         cin >> s >> x;
    33.         if (!mp.count(s))
    34.             a[x]++;
    35.         else
    36.             b[x]++;
    37.     }
    38.     for (int i = 1; i <= 5; i++) {
    39.         int mi = b[i];
    40.         for (int j = 1; j <= 5; j++) {
    41.             if (j == i) continue;
    42.             mi = min(mi, a[j]);
    43.         }
    44.         v.push_back({ mi, i });
    45.     }
    46.     sort(v.begin(), v.end(), [](node a, node b) { return a.m > b.m; });
    47.     int res = 0;
    48.     for (int i = 0; i < 5; i++) {
    49.         while (b[v[i].id] > 0) {
    50.             b[v[i].id]--;
    51.  
    52.             int f = 0;
    53.             for (int j = 1; j <= 5; j++) {
    54.                 if (j == v[i].id) continue;
    55.                 if (a[j] == 0) {
    56.                     if (b[j] != 0)
    57.                         b[j]--;
    58.                     else {
    59.                         f = 1;
    60.                         break;
    61.                     }
    62.                 }
    63.                 else
    64.                     a[j]--;
    65.             }
    66.             if (f == 1) break;
    67.             res++;
    68.         }
    69.     }
    70.     cout << res << endl;
    71. }

    C

    C - Grassicon-default.png?t=M85Bhttps://codeforces.com/gym/104023/problem/C先固定4个点，O（n）寻找一个和他们不共线的点，如果找不到则必然没有可行解，如果找到，则判断一下哪一个点是中心点。这里注意用pair来保存分子分母以防止double精度损失使答案错误。

    Accode

    1. #include 
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #define endl '\n'
    12. #define int long long 
    13. #define lowbit(x) (x &-x)
    14. #define mh(x) memset(x, -1, sizeof h)
    15. #define debug(x) cerr << #x << "=" << x << endl;
    16. #define brk exit(0);
    17. using namespace std;
    18. void inline TLE() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }
    19. const int N = 2e6 + 50;
    20. const int M = 2 * N;
    21. const int mod = 998244353;
    22. const double esp = 1e-6;
    23. const double pi = acos(-1);
    24. typedef pair<int, int> PII;
    25. typedef long long ll;
    26. struct node {
    27.     int x, y;
    28. };
    29. void solve()
    30. {
    31.     int n;cin >> n;
    32.     vectora(n + 1);
    33.     for (int i = 1;i <= n;i++) {
    34.         int x, y;
    35.         cin >> x >> y;
    36.         a[i].x = x;a[i].y = y;
    37.     }
    38.     auto check = [&](int j) {
    39.         setK;
    40.         for (int i = 1;i <= 4;i++) {
    41.             int x = a[i].x - a[j].x;
    42.             int y = a[i].y - a[j].y;
    43.             int t = __gcd(x, y);
    44.             x /= t;y /= t;
    45.             K.insert({ x,y });
    46.         }
    47.         return K.size() > 1;
    48.     };
    49.     auto find = [&]() {
    50.         for (int i = 1;i <= 5;i++) {
    51.             setK;
    52.             for (int j = 1;j <= 5;j++) {
    53.                 if (i == j)continue;
    54.                 int x = a[i].x - a[j].x;
    55.                 int y = a[i].y - a[j].y;
    56.                 int t = abs(__gcd(x, y));
    57.                 x /= t;y /= t;
    58.                 K.insert({ x,y });
    59.             }
    60.             if (K.size() == 4)return i;
    61.         }
    62.         return 1ll;
    63.     };
    64.     for (int i = 5;i <= n;i++) {
    65.         if (check(i)) {
    66.             swap(a[i], a[5]);
    67.             int t = find();
    68.             cout << "YES" << endl;
    69.             cout << a[t].x << " " << a[t].y << endl;
    70.             for (int i = 1;i <= 5;i++) {
    71.                 if (i == t)continue;
    72.                 cout << a[i].x << " " << a[i].y << endl;
    73.             }
    74.             return;
    75.         }
    76.     }
    77.     cout << "NO" << endl;
    78.  
    79. }
    80. signed  main()
    81. {
    82.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    83.     int t;t = 1;
    84.     cin >> t;
    85.     while (t--) {
    86.         solve();
    87.     }
    88.     return 0;
    89. }
    90. /*
    91. 101010
    92. 010101
    93. */

    E 

    Python Will be Faster than C++https://codeforces.com/gym/104023/problem/E签到

    ACcode

    1. #include 
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11.  
    12. #define endl '\n'
    13. #define lowbit(x) (x &-x)
    14. #define mh(x) memset(x, -1, sizeof h)
    15. #define debug(x) cerr << #x << "=" << x << endl;
    16. #define brk exit(0);
    17. using namespace std;
    18. void inline TLE(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);}
    19. const int N = 2e5 + 10;
    20. const int M = 2 * N;
    21. const int mod = 998244353;
    22. const double esp = 1e-6;
    23. const double pi = acos(-1);
    24. typedef pair<int, int> PII;
    25. typedef long long ll;
    26. int a[N];
    27. int cnt[2];
    28. void solve() {
    29.     int n, k;
    30.     cin >> n>>k;
    31.     for (int i = 1;i <= n;i++)cin >> a[i];
    32.     for (int i = 1;i <= n;i++) {
    33.         if (a[i] < k) {
    34.             cout << "Python 3." << i << " will be faster than C++" << endl;
    35.             return;
    36.         }
    37.     }
    38.     int i = n;
    39.     int res = n+1;
    40.     int x = a[n], y = a[n - 1];
    41.     while (2 * x - y >= k) {
    42.         if (2 * x - y >= x) {
    43.             cout << "Python will never be faster than C++" << endl;
    44.             return;
    45.         }
    46.         int t = x;
    47.         x = 2 * x - y;
    48.         y = t;
    49.         res++;
    50.     }
    51.     cout << "Python 3." << res << " will be faster than C++" << endl;
    52. }
    53.  
    54.  
    55. signed main() {
    56.     int t = 1;
    57.     while (t--)
    58.     {
    59.         solve();
    60.     }
    61.  
    62.     return 0;
    63. }
    64.

    G

    G - Grade 2https://codeforces.com/gym/104023/problem/G通过打表找规律会发现对于每个x的结果是不断循环的，循环节长度是大于等于x的2的倍数。

    通过前缀和统计循环节内gcd为1的个数，然后找到所给区间含有的循环节个数，再处理一下两个边界的值，即可O（1）获取答案。

    1. #include 
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #define endl '\n'
    12. #define int unsigned long long 
    13. #define lowbit(x) (x &-x)
    14. #define mh(x) memset(x, -1, sizeof h)
    15. #define debug(x) cerr << #x << "=" << x << endl;
    16. #define brk exit(0);
    17. using namespace std;
    18. void inline TLE() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }
    19. const int N = 2e6 + 50;
    20. const int M = 2 * N;
    21. const int mod = 998244353;
    22. const double esp = 1e-6;
    23. const double pi = acos(-1);
    24. typedef pair<int, int> PII;
    25. typedef long long ll;
    26. int n, m;
    27. int a[N], sum[N];
    28. void solve()
    29. {
    30.     int x, m;
    31.     cin >> x>>m;
    32.     int y = 1;
    33.     while (y < x) {
    34.         y *= 2;
    35.     }
    36.     int cnt = 0;
    37.     for (int i = 1;i <= y;i++) {
    38.         if (__gcd(i * x ^ x, x) == 1) {
    39.             a[i] = 1;
    40.         }
    41.         sum[i] = sum[i - 1] + a[i];
    42.     }
    43.     while (m--) {
    44.         int l, r;
    45.         cin >> l >> r;
    46.         l--;
    47.         int res1 = sum[l % y] + 1ll * (l / y) * sum[y];
    48.         int res2 = sum[r % y] + 1ll * (r / y) * sum[y];
    49.         cout << res2-res1 << endl;
    50.     }
    51. }
    52. signed  main()
    53. {
    54.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    55.     int t;t = 1;
    56.     while (t--) {
    57.         solve();
    58.     }
    59.     return 0;
    60. }
    61. /*
    63. 101010
    64. 010101
    66. */

    J

    J - Eat, Sleep, Repeathttps://codeforces.com/gym/104023/problem/J

    只需统计一下所有可以进行的操作数是奇数还是偶数即可得到答案。用map统计每个数的限制，将数组排序，从前想后扫，每个数可以减小的空间是第一个小于等于它的无限制或者是个数未达到上限的值，用一个小根堆去维护所有可行位置。（如果x限制数为0（map[x]=0），则可行位置是x+1）

    1. #include 
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #define int long long
    12. #define endl '\n'
    13. #define lowbit(x) (x &-x)
    14. #define mh(x) memset(x, -1, sizeof h)
    15. #define debug(x) cerr << #x << "=" << x << endl;
    16. #define brk exit(0);
    17. using namespace std;
    18. void inline TLE(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);}
    19. const int N = 2e5 + 10;
    20. const int M = 2 * N;
    21. const int mod = 998244353;
    22. const double esp = 1e-6;
    23. const double pi = acos(-1);
    24. typedef pair<int, int> PII;
    25. typedef long long ll;
    26. int a[N];
    27. void solve() {
    28.     map<int, int>mp;
    29.     int n, k;
    30.     cin >> n >> k;
    31.     priority_queue<int, vector<int>, greater<int>>q;
    32.     q.push(0);
    33.     for (int i = 1;i <= n;i++)cin >> a[i];
    34.     while (k--) {
    35.         int x, y;cin >> x >> y;
    36.         if (y == 0)
    37.             q.push(x + 1);
    38.         else mp[x] = y;
    39.     }
    40.     int res = 0;
    41.     sort(a + 1, a + 1 + n);
    42.     int t = 0;
    43.     for (int i = 1;i <= n;i++) {
    44.         while (q.size() && q.top() <= a[i]) {
    45.             t = q.top();
    46.             q.pop();
    47.         }
    48.         res ^= (a[i] - t)&1;//只需统计奇偶即可
    49.         mp[t]--;
    50.         if (mp[t] == 0)q.push(t + 1);
    51.     }
    52.     if (res)cout << "Pico" << endl;
    53.     else cout << "FuuFuu" << endl;
    54. }
    55.  
    56.  
    57. signed main() {
    58.     int t;t = 1;
    59.     cin >> t;
    60.     while (t--)
    61.         solve();
    62.     return 0;
    63. }

  • 相关阅读:
    时间同步产品（NTP北斗时钟服务器）如何完成网络同步的？
    【微服务】Nacos通知客户端服务变更以及重试机制
    紧急事件，停电导致安森美韩国厂全线停工 | 百能云芯
    系列一、堆里面的分区：Eden、From、To、老年代各自的特点
    XJAR 混淆加密
    Ubuntu 实现shell文件的开机运行
    C++ IO流
    ubuntu20.04+ROS noetic在线运行单USB双目ORB_SLAM
    Databricks 收购 Tabular 的意义：数据开放框架的胜利
    剑指 Offer 24. 反转链表
  • 原文地址：https://blog.csdn.net/Bookerbobo/article/details/127771581