2022ACM四川省赛

K

题意：

一个钟表，三个指针都是连在一起的，问某一时刻的位置。

做法：

模拟一下就好

int len1, len2, len3;
int t1, t2, t3;
double pi = acos(-1);
void slove() {
    int T; cin >> T;
    cin >> len1 >> len2 >> len3;
    cin >> t1 >> t2 >> t3;
    double du1 = 0, du2 = 0, du3 = 0;
    du1 = (1.0 * T / t1) - (T/t1);
    du2 = (1.0 * T / t2) - (T / t2);
    du3 = (1.0 * T / t3) - (T / t3);
    du1 *= 2 * pi;
    du2 *= 2 * pi;
    du3 *= 2 * pi;
    double x = 0, y = 0;
    double ansx = 0, ansy = 0;
    ansx += sin(du1) * len1;
    ansy += cos(du1) * len1;
    ansx += sin(du2) * len2;
    ansy += cos(du2) * len2;
    ansx += sin(du3) * len3;
    ansy += cos(du3) * len3;
    cout << fixed << setprecision(10) << ansx << " " << ansy << endl;

H

题意：

给定 m个长度为n 的 数组，问有多少对数组是完全相同的。保证n×m≤1e6

做法：

诈骗题，直接就map里面套一个vector即可。

void slove() {
    map<vector<int>, int>mp;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= m; i++) {
        vector<int>b(n);
        for (int& x : b)cin >> x;
    }
    ll ans = 0;
    for (auto p : mp) {
        ll cnt = p.second;
        ans += (cnt) * (cnt - 1) / 2;
    }
    cout << ans << endl;
}

F

题意：

给定一个数字 ,请你找到最小的一个数字 x满足。

x是个正数
x至少有8个因子
x的每个因子之间的差都大于等于n

分析：

关键点在于 c可以是a×a这个点很难想到

void slove() {
    cin >> n;
    auto a = *lower_bound(prime.begin(), prime.end(), n + 1);
    auto b = *lower_bound(prime.begin(), prime.end(), n + a);
    auto c = *lower_bound(prime.begin(), prime.end(), n + b);
    if (a * a < c) {
        cout << a * a * a * b << endl;
    }
    else {
        cout << a * b * c << endl;
    } 
}

B

题意：

给定一个页面，对于每个页面，你有一定的概率去点击另外的页面。

做法

直接模拟拓扑就好

vector<pair<int, double>>g[N];
double p[N];
void slove() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)g[i].clear();
    for (int i = 1; i <= n; i++)p[i] = 0;
    for (int i = 1; i <= n - 1; i++) {
        scanf("%d", &k);
        while (k--) {
            int v; double w;
            scanf("%d %lf", &v, &w);
            g[i].push_back({ v,w });
        }
    }
    p[1] = 1;
    for (int i = 1; i <= n; i++) {
        double x = p[i];
        for (auto& ed : g[i]) {
            int v = ed.first;
            double w = ed.second;
            p[v] += x * w;
            p[i] -= x * w;
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%.10lf ", p[i]);
    }
    printf("\n");
}

A

题意：

给定一个长度为 n（1e5）的字符串 s。你可以交换相邻的两个字符。

问最少移动多少次可以把 s变成形如 xx 的字符串（ x是个字符串）

例如abbcdcad我们需要移动成bacdbacd

保证一定可以

做法

最后的形式一定是 pre+suf 并且pre=suf

如果有4个a 那么前两个a一定在pre中 后两个a一定在suf中

考虑如何计算分pre和suf的贡献

实际上 我们只需要求 需要移动到pre的字符移动到pre中 剩下的自然就到suf中了

所以我们只需要计算当前字符与需要移动到pre的位置之差

for (int i = 1; i <= n; i++) {
    cnt[s[i]]++;
    if (cnt[s[i]] <= cot[s[i]] / 2) {
        pre.push_back(s[i]);
        ans += i - pre.length();
    }
    else {
        suf.push_back(s[i]);
    }
}

剩下的任务就是使得pre=suf

一个比较经典的求逆序对

int tree[N];
int lowbit(int x) {
    return (x) & (-x);
}
void add(int id, int x) {
    for (int i = id; i < N; i += lowbit(i)) {
        tree[i] += x;
    }
}
int que(int id) {
    if (id <= 0)return 0;
    int res = 0;
    for (int i = id; i >= 1; i -= lowbit(i)) {
        res += tree[i];
    }
    return res;
}
int que(int L, int R) {
    return que(R) - que(L - 1);
}
int n;
string s;
int cot[128];
int cnt[128];
string pre;
string suf;
int a[N];
void slove() {
    cin >> n;
    cin >> s; s = "?" + s;
    for (int i = 1; i <= n; i++)cot[s[i]]++;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        cnt[s[i]]++;
        if (cnt[s[i]] <= cot[s[i]] / 2) {
            pre.push_back(s[i]);
            ans += i - pre.length();
        }
        else {
            suf.push_back(s[i]);
        }
    }
    pre = "?" + pre;
    suf = "?" + suf;
    vector<int>ch[128];
    for (int i = 1; i <= n / 2; i++)
        ch[pre[i]].push_back(i);
    for (int i = 1; i < 128; i++)
        reverse(ch[i].begin(), ch[i].end());
    for (int i = 1; i <= n / 2; i++) {
        a[i] = ch[suf[i]].back();
        ch[suf[i]].pop_back();
    }
    for (int i = 1; i <= n / 2; i++) {
        ans += que(a[i], n / 2);
        add(a[i], 1);
    }
    cout << ans << endl;
}