• ShanDong Multi-University Training #3

    Ant colony

    题意大体就是一堆蚂蚁，有个战斗力值，如果某个蚂蚁的战斗力值是某个区间内其他蚂蚁的约数，那么这个蚂蚁就可以流放掉，最后就是问l到r区间内还剩下多少蚂蚁，其实就是一个线段树维护区间问题，维护的信息就是这个区间内的最大公约数、最小值以及最小值的个数，因此如果某个区间内的最大公约数和最小值相同，那么战斗力值等于最小值的蚂蚁都会被流放掉，减去就是剩下的蚂蚁，如果不相同，那区间内所有蚂蚁都是剩下的

    AC代码：

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. using i64 = long long;
    4.  
    5. int a[100010];
    6. struct node {
    7.     int gd, minn, cnt;
    8. };
    9. node Segtree[100010 << 2];
    10. int gcd(int a, int b) {
    11.     return b == 0 ? a : gcd(b, a % b);
    12. }
    13. node merge(node a, node b) {
    14.     node c;
    15.     c.gd = gcd(a.gd, b.gd);
    16.     c.minn = min(a.minn, b.minn);
    17.     if (a.minn == b.minn) {
    18.         c.cnt = a.cnt + b.cnt;
    19.     }
    20.     else if (a.minn < b.minn) {
    21.         c.cnt = a.cnt;
    22.     }
    23.     else {
    24.         c.cnt = b.cnt;
    25.     }
    26.     return c;
    27. }
    28.  
    29. inline void buildtree(int i, int l, int r) {
    30.     if (l == r) {
    31.         Segtree[i].gd = Segtree[i].minn = a[l];
    32.         Segtree[i].cnt = 1;
    33.         return;
    34.     }
    35.     int mid = l + r >> 1;
    36.     buildtree(i << 1, l, mid);
    37.     buildtree(i << 1 | 1, mid + 1, r);
    38.     Segtree[i] = merge(Segtree[i << 1], Segtree[i << 1 | 1]);
    39. }
    40.  
    41. node query(int i, int l, int r, int x, int y) {
    42.     if (l > y || r < x) {
    43.         return {0, (int)1e9, 0};
    44.     }
    45.     if (l >= x && r <= y) {
    46.         return Segtree[i];
    47.     }
    48.     int mid = l + r >> 1;
    49.     return merge(query(i << 1, l, mid, x, y), query(i << 1 | 1, mid + 1, r, x, y));
    50. }
    51. int main() {
    52.     ios::sync_with_stdio(false);
    53.     cin.tie(nullptr);
    54.     
    55.     int n, q;
    56.     cin >> n;
    57.     for (int i = 1; i <= n; i++) {
    58.         cin >> a[i];
    59.     }
    60.     buildtree(1, 1, n);
    61.     cin >> q;
    62.     while (q--) {
    63.         int l, r;
    64.         cin >> l >> r;
    65.         node c = query(1, 1, n, l, r);
    66.         if (c.minn == c.gd) {
    67.             cout << r - l + 1 - c.cnt << '\n';
    68.         }
    69.         else {
    70.             cout << r - l + 1 << '\n';
    71.         }
    72.     }
    73.     
    74.     return 0;
    75. }

    New String

    重新定义a到z的字典序，然后按照新定义排序，问第k小的字符串

    AC代码：

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. using i64 = long long;
    4. map<char, int> mp;
    5. bool cmp(string a, string b) {
    6.     int len1 = a.size(), len2 = b.size();
    7.     for (int i = 0; i < min(len1, len2); i++) {
    8.         if (mp[a[i]] < mp[b[i]]) {
    9.             return true;
    10.         }
    11.         else if (mp[a[i]] > mp[b[i]]) {
    12.             return false;
    13.         }
    14.     }
    15.     if (len1 > len2) {
    16.         return false;
    17.     }
    18.     else if (len1 < len2) {
    19.         return true;
    20.     }
    21.     else {
    22.         return true;
    23.     }
    24. }
    25.  
    26. int main() {
    27.     ios::sync_with_stdio(false);
    28.     cin.tie(nullptr);
    29.     
    30.     string s;
    31.     cin >> s;
    32.     int n, k;
    33.     cin >> n;
    34.     vector<string> a(n);
    35.     for (int i = 0; i < n; i++) {
    36.         cin >> a[i];
    37.     }
    38.     cin >> k;
    39.     k--;
    40.     for (int i = 0; i < 26; i++) {
    41.         mp[s[i]] = i;
    42.     }
    43.     sort(a.begin(), a.end(), cmp);
    44.     cout << a[k] << '\n';
    45.     
    46.     return 0;
    47. }

    Problem - E - Codeforces

    题意大体是一张图里有a，b两个点，'.'可以走，'*'不可以走，每一秒a和b做相同的动作，问a和b能否相遇，如果相遇就输出最小步数，这样就bfs搜索+记录步数，注意边界问题以及下一个如果是'*‘原地不动，a和b的坐标相等就输出步数

    AC代码：

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. using i64 = long long;
    4.  
    5. int n;
    6. string mp[55];
    7. bool vis[55][55][55][55];
    8. struct node {
    9.     int xa, xb, ya, yb, cnt;
    10. };
    11. int mov[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    12. queue<node> qu;
    13. int main() {
    14.     ios::sync_with_stdio(false);
    15.     cin.tie(nullptr);
    16.     
    17.     cin >> n;
    18.     for (int i = 0; i < n; i++) {
    19.         cin >> mp[i];
    20.     }
    21.     node now;
    22.     for (int i = 0; i < n; i++) {
    23.         for (int j = 0; j < n; j++) {
    24.             if (mp[i][j] == 'a') {
    25.                 now.xa = i;
    26.                 now.ya = j;
    27.                 mp[i][j] = '.';
    28.             }
    29.             if (mp[i][j] == 'b') {
    30.                 now.xb = i;
    31.                 now.yb = j;
    32.                 mp[i][j] = '.';
    33.             }
    34.         }
    35.     }
    36.     now.cnt = 0;
    37.     vis[now.xa][now.ya][now.xb][now.yb] = true;
    38.     qu.push(now);
    39.     while (!qu.empty()) {
    40.         node nxt;
    41.         nxt = now = qu.front();
    42.         qu.pop();
    43.         if (now.xa == now.xb && now.ya == now.yb) {
    44.             cout << now.cnt << '\n';
    45.             return 0;
    46.         }
    47.         now.cnt = nxt.cnt + 1;
    48.         for (int i = 0; i < 4; i++) {
    49.             now.xa = nxt.xa + mov[i][0];
    50.             now.ya = nxt.ya + mov[i][1];
    51.             now.xb = nxt.xb + mov[i][0];
    52.             now.yb = nxt.yb + mov[i][1];
    53.             if (now.xa >= 0 && now.ya >= 0 && now.xa < n && now.ya < n && mp[now.xa][now.ya] == '.') {
    54.                 
    55.             }
    56.             else {
    57.                 now.xa = nxt.xa;
    58.                 now.ya = nxt.ya;
    59.             }
    60.             if (now.xb >= 0 && now.yb >= 0 && now.xb < n && now.yb < n && mp[now.xb][now.yb] == '.') {
    61.                 
    62.             }
    63.             else {
    64.                 now.xb = nxt.xb;
    65.                 now.yb = nxt.yb;
    66.             }
    67.             if (!vis[now.xa][now.ya][now.xb][now.yb]) {
    68.                 vis[now.xa][now.ya][now.xb][now.yb] = true;
    69.                 qu.push(now);
    70.             }
    71.         }
    72.     }
    73.     cout << "no solution\n";
    74.     return 0;
    75. }

    Maximum Value

    题意就是求ai%aj的最大值，其中ai要大于等于aj，那先保证序列有序的情况下，如果直接遍历会TLE，这里考虑二分找最大可能值，可知ai大于等于aj，那么ai=n*aj+mod，因此，最大可能值一定出现在n倍和n+1倍之间最后一个值，直接lower_bound二分得到n+1倍的第一个值，它的前一个就是要找的最大可能值

    AC代码：

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3.  
    4.  
    5.  
    6. int main() {
    7.     ios::sync_with_stdio(false);
    8.     cin.tie(nullptr);
    9.     
    10.     int n;
    11.     cin >> n;
    12.     vector<int> a(n);
    13.     for (int i = 0; i < n; i++) {
    14.         cin >> a[i];
    15.     }
    16.     sort(a.begin(), a.end());
    17.     int ans = 0;
    18.     for (int i = 0; i < n; i++) {
    19.         if (a[i] != a[i + 1] && i + 1 < n) {
    20.             int x = lower_bound(a.begin(), a.end(), 2 * a[i]) - a.begin();
    21.             for (int j = 2; j * a[i] <= a[n - 1]; j++) {
    22.                 x = lower_bound(a.begin(), a.end(), j * a[i]) - a.begin();
    23.                 ans = max(ans, a[x - 1] % a[i]);
    24.             }
    25.             ans = max(ans, a[n - 1] % a[i]);
    26.             ans = max(ans, a[x - 1] % a[i]);
    27.         }
    28.     }
    29.     cout << ans << '\n';
    30.     
    31.     return 0;
    32. }

    Prefix Equality

    判断集合a和集合b的前缀是否相等，集合哈希即可

    AC代码：

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. using i64 = long long;
    4. const i64 mod = 1e9 + 7;
    5. i64 n, q;
    6. i64 a[200010], b[200010];
    7. set<i64> se;
    8. int main() {
    9.     ios::sync_with_stdio(false);
    10.     cin.tie(nullptr);
    11.     
    12.     cin >> n;
    13.     i64 s = 0;
    14.     for (int i = 1; i <= n; i++) {
    15.         i64 x;
    16.         cin >> x;
    17.         if (se.find(x) == se.end()) {
    18.             s = (s + x * (x + 137) % mod * (x + 997) % mod) % mod;
    19.         }
    20.         a[i] = s;
    21.         se.insert(x);
    22.     }
    23.     se.clear();
    24.     s = 0;
    25.     for (int i = 1; i <= n; i++) {
    26.         i64 x;
    27.         cin >> x;
    28.         if (se.find(x) == se.end()) {
    29.             s = (s + x * (x + 137) % mod * (x + 997) % mod) % mod;
    30.         }
    31.         b[i] = s;
    32.         se.insert(x);
    33.     }
    34.  
    35.     cin >> q;
    36.  
    37.     while (q--) {
    38.         int x, y;
    39.         cin >> x >> y;
    40.         if (a[x] == b[y]) {
    41.             cout << "Yes\n";
    42.         }
    43.         else {
    44.             cout << "No\n";
    45.         }
    46.     }
    47.  
    48.     return 0;
    49. }

    Problem - H - Codeforces

    线性dp，可以发现手中的金币数量最大值是非常小的，求最小的步行距离就是求最大的骑行距离，那就可以提前处理出我当次花费多少钱能走到的最远距离，每次肯定是选取最远的那个车站，这样就不需要额外考虑最后一个车站和总路程的关系，因为骑行一定是在两个车站之间，不可能就一个车站以至于走不到下一个车站就到终点了

    AC代码：

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. using i64 = long long;
    4.  
    5. int dp[1000010][6];
    6. int a[1000010];
    7.  
    8. int main() {
    9.     ios::sync_with_stdio(false);
    10.     cin.tie(nullptr);
    11.     
    12.     int n, p, s;
    13.     cin >> n >> p >> s;
    14.     for (int i = 1; i <= n; i++) {
    15.         cin >> a[i];
    16.     }
    17.     int k;
    18.     cin >> k;
    19.     int ans = 0;
    20.     for (int i = 1; i <= n; i++) {
    21.         for (int j = 0; j <= k; j++) {
    22.             dp[i][j] = max(dp[i][j], dp[i - 1][j]);
    23.             ans = max(ans, dp[i][j]);
    24.             for (int l = 1; l + j <= k; l++) {
    25.                 int dis = l * s + a[i];
    26.                 int now = upper_bound(a + 1, a + 1 + n, dis) - a;
    27.                 now--;
    28.                 dp[now][l + j] = max(dp[now][l + j], dp[i][j] + a[now] - a[i]);
    29.                 if (dis > a[n]) {
    30.                     break;
    31.                 }
    32.             }
    33.         }
    34.     }
    35.     cout << p - ans << '\n';
    36.  
    37.     return 0;
    38. }

    250-like Number

    埃式筛筛出所有质数，然后暴力求和即可

    AC代码：

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. using i64 = long long;
    4. using u64 = unsigned long long;
    5. #define M 10000000
    6. int cnt = 0;
    7. i64 a[M + 5];
    8. bool is_prime[M + 5];
    9. void init(){
    10.     is_prime[0] = is_prime[1] = false;
    11.     for (int i = 2; i <= M; i++) {
    12.         if (is_prime[i]) {
    13.             a[++cnt] = i;
    14.             for (int j = 2; j * i <= M; j++) {
    15.                 is_prime[i * j] = false;
    16.             }
    17.         }
    18.     }
    19. }
    20.  
    21. int main() {
    22.     ios::sync_with_stdio(false);
    23.     cin.tie(nullptr);
    24.     
    25.     memset(is_prime, true, sizeof(is_prime));
    26.     i64 n, ans = 0;
    27.     init();
    28.     cin >> n;
    29.     for (int i = 1; i <= cnt; i++) {
    30.         for (int j = i + 1; j <= cnt; j++) {
    31.             if (a[j] * a[j] > n / a[i] / a[j]) {
    32.                 break;
    33.             }
    34.             ans++;
    35.         }
    36.     }
    37.     cout << ans << "\n";
    38.     
    39.     return 0;
    40. }

    Endless Walk

    问有多少个点不是通向环的，反向图+拓扑排序，图反着建，入度为0的一定是不能通向环的，因为正图一定是只有入度没有出度，反图才能只有出度没有入度的，这样的点一定不可以，然后根据这些点进行拓扑排序，从它走向的所有的其他的入度为0的也一定都是不能通向环的点

    AC代码：

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. using i64 = long long;
    4.  
    5. vector<int> G[200010];
    6.  
    7. int main() {
    8.     ios::sync_with_stdio(false);
    9.     cin.tie(nullptr);
    10.     
    11.     int n, m;
    12.     cin >> n >> m;
    13.     vector<int> deg(n + 1);
    14.     for (int i = 0; i < m; i++) {
    15.         int u, v;
    16.         cin >> u >> v;
    17.         G[v].push_back(u);
    18.         deg[u]++;
    19.     }
    20.     queue<int> qu;
    21.     for (int i = 1; i <= n; i++) {
    22.         if (deg[i] == 0) {
    23.             qu.push(i);
    24.         }
    25.     }
    26.     int ans = n;
    27.     while (!qu.empty()) {
    28.         int u = qu.front();
    29.         qu.pop();
    30.         ans--;
    31.         for (auto it : G[u]) {
    32.             if (--deg[it] == 0) {
    33.                 qu.push(it);
    34.             }
    35.         }
    36.     }
    37.     cout << ans << '\n';
    38.  
    39.     return 0;
    40. }

  • 相关阅读:
    springboot球类运动教学网站的设计与实现271611
    TcpServerChannel 类服务
    一本专业130+总分400+上海交通大学819考研经验上交电子信息与通信工程上岸，真题，大纲，参考书。
    计算机毕业设计php+vue基于微信小程序的房屋租赁小程序
    （十二） 共享模型之无锁【原子整数、原子引用、原子数组】
    【软件测试】（北京）字节跳动科技有限公司二面笔试题
    初识Java 14-1 测试
    线性规划学习
    Windows开启监控
    java计算机毕业设计销售人员绩效管理系统源码+系统+数据库+lw文档(1)
  • 原文地址：https://blog.csdn.net/eyuhaobanga/article/details/125523118