• “蔚来杯“2022牛客暑期多校训练营5 B、C、F、G、H、K

    B

    二分答案+排序，时间复杂度O(nlognlogn)

    AC代码：

    1. #include 
    2. #define rep(i,a,n) for(int i=a;i
    3. using namespace std;
    4. using LL = long long;
    5.  
    6. struct node {
    7.     LL cost, id;
    8. }a[100010], b[100010];
    9. int n, m;
    10. bool check(LL mid) {
    11.     LL cnt = 0;
    12.     for (int i = 0; i < mid; i++) {
    13.         cnt += b[i].cost;
    14.     }
    15.     return cnt > m;
    16. }
    17. bool cmp(node a, node b) {
    18.     if (a.cost != b.cost) {
    19.         return a.cost < b.cost;
    20.     }
    21.     return a.id < b.id;
    22. }
    23. int main() {
    24.     ios::sync_with_stdio(false);
    25.     cin.tie(nullptr);
    26.  
    27.     
    28.     while (cin >> n >> m) {
    29.     for (int i = 0; i < n; i++) {
    30.         cin >> a[i].cost;
    31.         a[i].id = i + 1;
    32.     }
    33.     LL l = 0, r = n;
    34.     while (l + 1 < r) {
    35.         LL mid = (l + r) >> 1;
    36.         for (int i = 0; i < n; i++) {
    37.             b[i] = a[i];
    38.             b[i].cost += mid * b[i].id;
    39.         }
    40.         sort(b, b + n, cmp);
    41.         if (check(mid)) {
    42.             r = mid;
    43.         }
    44.         else {
    45.             l = mid;
    46.         }
    47.     }
    48.     cout << l << '\n';
    49.     }
    50.  
    51.     return 0;
    52. }

    C

    按照题意模拟，有没访问到的地方、YES\NO个数都大于1、YES\NO个数相同、出现>1个YES和NO都出现过的位置、假如没有YES和NO都出现过的位置，但有某个位置YES和NO只出现了一次，因为错误的地方至多出现一个，无法判断这里是1还是0----以上均输出-1，否则输出ans，

    AC代码：

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. #include 
    12. #include 
    13. #include 
    14. #include 
    15. #include 
    16. #include 
    17. #define rep(i,a,n) for(int i=a;i
    18. using namespace std;
    19. using LL = long long;
    20. //head
    21.  
    22.  
    23.  
    24. int main() {
    25.     ios::sync_with_stdio(false);
    26.     cin.tie(nullptr);
    27.  
    28.     int n;
    29.     while (cin >> n) {
    30.         vectorint, int>> a(n);
    31.         for (int i = 0; i < 3 * n; i++) {
    32.             int x;
    33.             string s;
    34.             cin >> x >> s;
    35.             if (s == "YES") {
    36.                 a[x].first++;
    37.             }
    38.             else {
    39.                 a[x].second++;
    40.             }
    41.         }
    42.         bool ok = true;
    43.         string ans = "";
    44.         int cnt = 0, cnt1 = 0;
    45.         for (int i = 0; i < n; i++) {
    46.             if (a[i].first == 0 && a[i].second == 0) {
    47.                 ok = false;
    48.                 break;
    49.             }
    50.             else if (a[i].second > 1 && a[i].first > 1) {
    51.                 ok = false;
    52.                 break;
    53.             }
    54.             else if (a[i].first == a[i].second) {
    55.                 ok = false;
    56.                 break;
    57.             }
    58.         }
    59.         if (ok) {
    60.             for (int i = 0; i < n; i++) {
    61.                 if (a[i].first && a[i].second) {
    62.                     cnt++;
    63.                 }
    64.                 if (a[i].first + a[i].second == 1) {
    65.                     cnt1++;
    66.                 }
    67.                 if (a[i].first > a[i].second) {
    68.                     ans += '1';
    69.                 }
    70.                 else {
    71.                     ans += '0';
    72.                 }
    73.             }
    74.             if (cnt > 1) {
    75.                 cout << "-1\n";
    76.             }
    77.             else if (cnt == 1) {
    78.                 cout << ans << '\n';
    79.             }
    80.             else {
    81.                 if (cnt1) {
    82.                     cout << "-1\n";
    83.                 }
    84.                 else {
    85.                     cout << ans << '\n';
    86.                 }
    87.             }
    88.         }
    89.         else {
    90.             cout << "-1\n";
    91.         }
    92.     }
    93.  
    94.     return 0;
    95. }

    F

    贪心

    AC代码：

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. using namespace std;
    9. const double PI = acos(-1);
    10. const double PI2 = PI * 2;
    11. const int MAXN = 2010;
    12. const double eps = 1e-6;
    13. int n;
    14. double xs[MAXN], ys[MAXN], rs[MAXN];
    15. typedef std::pair<double, double> PDD;
    16. PDD cover[MAXN]; int bak;
    17. inline double pows(double x) { return x * x; }
    18. inline double absx(double x) { return x < 0 ? -x : x; }
    19. inline double reduce(double x) { x += PI2, x = x - (int) (x / PI2) * PI2; return x; }
    20. int main() {
    21. 	while (cin >> n) {
    22.         double ans = 0;
    23.         for (int i = 1; i <= n; ++i)
    24.             scanf("%lf%lf%lf", xs + i, ys + i, rs + i);
    25.         for (int i = 1; i <= n; ++i) {
    26.             bak = 0;
    27.             for (int j = i + 1; j <= n; ++j) {
    28.                 double D = sqrt(pows(xs[i] - xs[j]) + pows(ys[i] - ys[j]));
    29.                 if (D >= absx(rs[i] + rs[j]) - eps) continue;
    30.                 if (D <= absx(rs[i] - rs[j]) + eps) {
    31.                     if (rs[j] > rs[i])
    32.                         cover[++bak] = PDD(0, PI2);
    33.                     continue;
    34.                 }
    35.                 double y = (D - (pows(rs[j]) - pows(rs[i])) / D) / 2;
    36.                 double angle = acos(y / rs[i]);
    37.                 double oa = reduce(atan2(xs[i] - xs[j], ys[i] - ys[j]) + PI / 2);
    38.                 double L = reduce(oa - angle), R = reduce(oa + angle);
    39.                 if (L - eps > R) cover[++bak] = PDD(L, PI2), cover[++bak] = PDD(0, R);
    40.                 else cover[++bak] = PDD(L, R);
    41.             }
    42.             std::sort(cover + 1, cover + 1 + bak);
    43.             ans += PI2 * rs[i];
    44.             double lstl = 0, lstr = 0;
    45.             for (int j = 1; j <= bak; ++j) {
    46.                 const double fx = cover[j].first, sx = cover[j].second;
    47.                 if (fx > lstr) {
    48.                     ans -= (lstr - lstl) * rs[i];
    49.                     lstl = fx;
    50.                 }
    51.                 lstr = std::max(lstr, sx);
    52.             }
    53.             ans -= (lstr - lstl) * rs[i];
    54.         }
    55.         printf("%.7lf\n", ans);
    56.     }
    57. 	return 0;
    58. }

    G

    马拉车或者pam求以‘k’或‘f’或‘c'为结尾的回文串的个数

    AC代码：

    1. #include 
    2. #define rep(i,a,n) for(int i=a;i
    3. using namespace std;
    4. using LL = long long;
    5.  
    6. char s[2000001];
    7. int len[2000001], n, num[2000001], fail[2000001], last, cur, pos, trie[2000001][26], tot = 1;
    8. int getfail(int x, int i) {
    9. 	while (i - len[x] - 1 < 0 || s[i - len[x] - 1] != s[i]) {
    10.         x = fail[x];
    11.     }
    12. 	return x;
    13. }
    14. int main() {
    15.     ios::sync_with_stdio(false);
    16.     cin.tie(nullptr);
    17.     
    18.     while (cin >> n) {
    19.         cin >> s;
    20.         vector<int> v;
    21.         fail[0] = 1;
    22.         len[1] = -1;
    23.         for(int i = 0; i <= n - 1; i++) {
    24.             pos = getfail(cur, i);
    25.             if (!trie[pos][s[i] - 'a']) {
    26.                 fail[++tot] = trie[getfail(fail[pos], i)][s[i] - 'a'];
    27.                 trie[pos][s[i] - 'a'] = tot;
    28.                 len[tot] = len[pos] + 2;
    29.                 num[tot] = num[fail[tot]] + 1;
    30.             }
    31.             cur = trie[pos][s[i] - 'a'];
    32.             last = num[cur];
    33.             v.push_back(last);
    34.         }
    35.         map<char, int> mp;
    36.         for (int i = 0; i < n; i++) {
    37.             mp[s[i]] = mp[s[i]] + v[i];
    38.         }
    39.         cout << mp['k'] << " " << mp['f'] << " " << mp['c'] << '\n';
    40.     }
    41. 	return 0;
    42. }

    H

     面积为圆的面积+阴影多边形圆外面的面积，即整个圆的面积+（四个三角形面积-半圆的面积）

    AC代码：

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. #include 
    12. #include 
    13. #include 
    14. #include 
    15. #include 
    16. #include 
    17. #define rep(i,a,n) for(int i=a;i
    18. using namespace std;
    19. using LL = long long;
    20. //head
    21.  
    22.  
    23.  
    24. int main() {
    25.     ios::sync_with_stdio(false);
    26.     cin.tie(nullptr);
    27.  
    28.     int n;
    29.     while (cin >> n) {
    30.         double r = 1.0 * n / 2;
    31.         const double PI = acos(-1.0);
    32.         cout << fixed << setprecision(9) << r * r * PI / 2 + 2 * r * r << '\n';
    33.     }
    34.  
    35.     return 0;
    36. }

    K

    可知一共有N对蓝牙耳机，Yasa拿走了k对耳机，那么剩下了N-k对耳机=2*（N-k）个耳机，如果要组成k+1对耳机，那么根据鸽巢原理，需要拿N-k+k+1->N+1个耳机保证能组成k+1对耳机，那么最少能组成k+1对耳机的条件就是剩下的耳机对数起码要有k+1对

    AC代码：

    1. #include 
    2. using namespace std;
    3.  
    4.  
    5. int main() {
    6.     ios::sync_with_stdio(false);
    7.     cin.tie(0);
    8.     int n, k;
    9.     while (cin >> n >> k) {
    10.         if (n >= 2 * k + 1) {
    11.             cout << n + 1 << '\n';
    12.         }
    13.         else {
    14.             cout << "-1\n";
    15.         }
    16.     }
    17.     return 0;
    18. }

  • 相关阅读:
    java实现http/https请求
    开发笔记 —— Centos7 在急救模式下修改密码
    labelme标注的json数据集转换成coco数据集
    如何使用jsDelivr+Github 实现免费CDN加速?
    AWS Cloudformation入门项目实践
    Vue3速成
    MTK手机平台充电原理
    js笔试题(6)
    1375. 二进制字符串前缀一致的次数-前序遍历法
    【愚公系列】2022年11月 .NET CORE工具案例-CSRedis执行Lua脚本实现商品秒杀
  • 原文地址：https://blog.csdn.net/eyuhaobanga/article/details/126115523