ShanDong Multi-University Training ＃3

Ant colony

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

AC代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int a[100010];
struct node {
    int gd, minn, cnt;
};
node Segtree[100010 << 2];
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
node merge(node a, node b) {
    node c;
    c.gd = gcd(a.gd, b.gd);
    c.minn = min(a.minn, b.minn);
    if (a.minn == b.minn) {
        c.cnt = a.cnt + b.cnt;
    }
    else if (a.minn < b.minn) {
        c.cnt = a.cnt;
    }
    else {
        c.cnt = b.cnt;
    }
    return c;
}

inline void buildtree(int i, int l, int r) {
    if (l == r) {
        Segtree[i].gd = Segtree[i].minn = a[l];
        Segtree[i].cnt = 1;
        return;
    }
    int mid = l + r >> 1;
    buildtree(i << 1, l, mid);
    buildtree(i << 1 | 1, mid + 1, r);
    Segtree[i] = merge(Segtree[i << 1], Segtree[i << 1 | 1]);
}

node query(int i, int l, int r, int x, int y) {
    if (l > y || r < x) {
        return {0, (int)1e9, 0};
    }
    if (l >= x && r <= y) {
        return Segtree[i];
    }
    int mid = l + r >> 1;
    return merge(query(i << 1, l, mid, x, y), query(i << 1 | 1, mid + 1, r, x, y));
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    buildtree(1, 1, n);
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        node c = query(1, 1, n, l, r);
        if (c.minn == c.gd) {
            cout << r - l + 1 - c.cnt << '\n';
        }
        else {
            cout << r - l + 1 << '\n';
        }
    }
    
    return 0;
}

New String

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

AC代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
map<char, int> mp;
bool cmp(string a, string b) {
    int len1 = a.size(), len2 = b.size();
    for (int i = 0; i < min(len1, len2); i++) {
        if (mp[a[i]] < mp[b[i]]) {
            return true;
        }
        else if (mp[a[i]] > mp[b[i]]) {
            return false;
        }
    }
    if (len1 > len2) {
        return false;
    }
    else if (len1 < len2) {
        return true;
    }
    else {
        return true;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    int n, k;
    cin >> n;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cin >> k;
    k--;
    for (int i = 0; i < 26; i++) {
        mp[s[i]] = i;
    }
    sort(a.begin(), a.end(), cmp);
    cout << a[k] << '\n';
    
    return 0;
}

Problem - E - Codeforces

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

AC代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int n;
string mp[55];
bool vis[55][55][55][55];
struct node {
    int xa, xb, ya, yb, cnt;
};
int mov[4][2] = {
    {1, 0}, {0, 1}, {-1, 0}, {0, -1}};
queue<node> qu;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> mp[i];
    }
    node now;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (mp[i][j] == 'a') {
                now.xa = i;
                now.ya = j;
                mp[i][j] = '.';
            }
            if (mp[i][j] == 'b') {
                now.xb = i;
                now.yb = j;
                mp[i][j] = '.';
            }
        }
    }
    now.cnt = 0;
    vis[now.xa][now.ya][now.xb][now.yb] = true;
    qu.push(now);
    while (!qu.empty()) {
        node nxt;
        nxt = now = qu.front();
        qu.pop();
        if (now.xa == now.xb && now.ya == now.yb) {
            cout << now.cnt << '\n';
            return 0;
        }
        now.cnt = nxt.cnt + 1;
        for (int i = 0; i < 4; i++) {
            now.xa = nxt.xa + mov[i][0];
            now.ya = nxt.ya + mov[i][1];
            now.xb = nxt.xb + mov[i][0];
            now.yb = nxt.yb + mov[i][1];
            if (now.xa >= 0 && now.ya >= 0 && now.xa < n && now.ya < n && mp[now.xa][now.ya] == '.') {
                
            }
            else {
                now.xa = nxt.xa;
                now.ya = nxt.ya;
            }
            if (now.xb >= 0 && now.yb >= 0 && now.xb < n && now.yb < n && mp[now.xb][now.yb] == '.') {
                
            }
            else {
                now.xb = nxt.xb;
                now.yb = nxt.yb;
            }
            if (!vis[now.xa][now.ya][now.xb][now.yb]) {
                vis[now.xa][now.ya][now.xb][now.yb] = true;
                qu.push(now);
            }
        }
    }
    cout << "no solution\n";
    return 0;
}

Maximum Value

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

AC代码：

#include <bits/stdc++.h>
using namespace std;



int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] != a[i + 1] && i + 1 < n) {
            int x = lower_bound(a.begin(), a.end(), 2 * a[i]) - a.begin();
            for (int j = 2; j * a[i] <= a[n - 1]; j++) {
                x = lower_bound(a.begin(), a.end(), j * a[i]) - a.begin();
                ans = max(ans, a[x - 1] % a[i]);
            }
            ans = max(ans, a[n - 1] % a[i]);
            ans = max(ans, a[x - 1] % a[i]);
        }
    }
    cout << ans << '\n';
    
    return 0;
}

Prefix Equality

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

AC代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 mod = 1e9 + 7;
i64 n, q;
i64 a[200010], b[200010];
set<i64> se;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    i64 s = 0;
    for (int i = 1; i <= n; i++) {
        i64 x;
        cin >> x;
        if (se.find(x) == se.end()) {
            s = (s + x * (x + 137) % mod * (x + 997) % mod) % mod;
        }
        a[i] = s;
        se.insert(x);
    }
    se.clear();
    s = 0;
    for (int i = 1; i <= n; i++) {
        i64 x;
        cin >> x;
        if (se.find(x) == se.end()) {
            s = (s + x * (x + 137) % mod * (x + 997) % mod) % mod;
        }
        b[i] = s;
        se.insert(x);
    }

    cin >> q;

    while (q--) {
        int x, y;
        cin >> x >> y;
        if (a[x] == b[y]) {
            cout << "Yes\n";
        }
        else {
            cout << "No\n";
        }
    }

    return 0;
}

Problem - H - Codeforces

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

AC代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int dp[1000010][6];
int a[1000010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, p, s;
    cin >> n >> p >> s;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int k;
    cin >> k;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            ans = max(ans, dp[i][j]);
            for (int l = 1; l + j <= k; l++) {
                int dis = l * s + a[i];
                int now = upper_bound(a + 1, a + 1 + n, dis) - a;
                now--;
                dp[now][l + j] = max(dp[now][l + j], dp[i][j] + a[now] - a[i]);
                if (dis > a[n]) {
                    break;
                }
            }
        }
    }
    cout << p - ans << '\n';

    return 0;
}

250-like Number

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

AC代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
#define M 10000000
int cnt = 0;
i64 a[M + 5];
bool is_prime[M + 5];
void init(){
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= M; i++) {
        if (is_prime[i]) {
            a[++cnt] = i;
            for (int j = 2; j * i <= M; j++) {
                is_prime[i * j] = false;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    memset(is_prime, true, sizeof(is_prime));
    i64 n, ans = 0;
    init();
    cin >> n;
    for (int i = 1; i <= cnt; i++) {
        for (int j = i + 1; j <= cnt; j++) {
            if (a[j] * a[j] > n / a[i] / a[j]) {
                break;
            }
            ans++;
        }
    }
    cout << ans << "\n";
    
    return 0;
}

Wrapping Chocolate

题意就是给定长宽的巧克力然后把它们都放进给定长宽的盒子里，能否全部放进去，一个盒子只能放一个巧克力，而且长对长，宽对宽，贪心地去想肯定是能更合适的放进盒子肯定就得更合适地放进盒子里，这就需要定长或者定宽排序，然后去二分另一个边，恰好就是multiset特性，自动排序+不去重

AC代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;



int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> a(n), b(m);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first;
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i].second;
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i].first;
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i].second;
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    multiset<int> ms;
    for (int i = n - 1, j = m - 1; i >= 0; i--) {
        while (j >= 0 && b[j].first >= a[i].first) {
            ms.insert(b[j].second);
            j--;
        }
        multiset<int>::iterator x;
        x = ms.lower_bound(a[i].second);
        if (x == ms.end()) {
            cout << "No\n";
            return 0;
        }
        ms.erase(x);
    }
    cout << "Yes\n";
    
    return 0;
}

Endless Walk

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

AC代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

vector<int> G[200010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<int> deg(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[v].push_back(u);
        deg[u]++;
    }
    queue<int> qu;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) {
            qu.push(i);
        }
    }
    int ans = n;
    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();
        ans--;
        for (auto it : G[u]) {
            if (--deg[it] == 0) {
                qu.push(it);
            }
        }
    }
    cout << ans << '\n';

    return 0;
}

Problem - 86D - Codeforces

普通莫队题，分块思想

AC代码：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

i64 s;
struct query {
    i64 l, r, idx;
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    i64 n, m;
    cin >> n >> m;
    s = sqrt(n) + 1;
    vector<i64> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<query> q(m);
    vector<i64> v(m);
    for (int i = 0; i < m; i++) {
        i64 L, R;
        cin >> L >> R;
        L--, R--;
        q[i].l = L, q[i].r = R, q[i].idx = i;
    }
    sort(q.begin(), q.end(), [&](query a, query b) {
        pair<i64, i64> x = {a.l / s, a.r};
        pair<i64, i64> y = {b.l / s, b.r};
        return x < y;
    });
    vector<i64> cnt(1000010, 0);
    i64 ans = 0;
    i64 l = 0, r = 0;
    cnt[a[0]] = 1;
    ans = a[0];
    for (int i = 0; i < m; i++) {
        i64 L = q[i].l, R = q[i].r, I = q[i].idx;
        while (l > L) {
            l--;
            ans -= cnt[a[l]] * cnt[a[l]] * a[l];
            cnt[a[l]]++;
            ans += cnt[a[l]] * cnt[a[l]] * a[l];
        }
        while (l < L) {
            ans -= cnt[a[l]] * cnt[a[l]] * a[l];
            cnt[a[l]]--;
            ans += cnt[a[l]] * cnt[a[l]] * a[l];
            l++;
        }
        while (r > R) {
            ans -= cnt[a[r]] * cnt[a[r]] * a[r];
            cnt[a[r]]--;
            ans += cnt[a[r]] * cnt[a[r]] * a[r];
            r--;
        }
        while (r < R) {
            r++;
            ans -= cnt[a[r]] * cnt[a[r]] * a[r];
            cnt[a[r]]++;
            ans += cnt[a[r]] * cnt[a[r]] * a[r];
        }
        v[I] = ans;
    }
    for (int i = 0; i < m; i++) {
        cout << v[i] << '\n';
    }
    
    return 0;
}