不忘初心
时刻前行

滚粗场

貌似只做了一个小时左右,之后又滚去颓了 = =

总分 110,rk 61,25 分钟 AC C 题(好象是 fb?)

A 序列

给出一个互不相同的非负整数序列 a 与一个质数 p,求有多少个有序整数对 (i, j) 使得 (a_i^2 + a_j^2)^2 \equiv (a_i^2 - a_j^2)^2 + 1 \mod p

数学,逆元


进行一些简单的运算后会发现,上式等价与找到有序整数对,使得

4a_i^2a_j \equiv 1 \mod p

这意味着 a_j4a_i^2 的逆元,那么我们枚举 a_i,利用 map 查询是否有 a_j4a_i^2 的逆元即可

时间复杂度 O(n \log n)

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
int n;
ll P, a[maxn], ans;

map<ll, int> mp;

ll qpower(ll a, ll x) {
    ll res = 1;
    while (x) {
        if (x & 1) res = res * a % P;
        a = a * a % P, x >>= 1;
    }
    return res % P;
}

int main() {
    scanf("%d %lld", &n, &P);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        a[i] %= P;
        if (a[i]) mp[a[i]] ++;
    }
    for (int i = 1; i <= n; ++i) {
        ll x = a[i];
        if (x == 0) continue;
        ll y = qpower(4 * x % P * x % P, P - 2);
        if (y == x) ans += mp[y] - 1;
        else ans += mp[y];
    }
    printf("%lld\n", ans);
    return 0;
}

B 汽水

k 种无限的糖浆,浓度为 \frac{a_1}{m}, \frac{a_2}{m} \cdots \frac{a_k}{m},求是否可以将整数毫升的若干种糖浆混合在一起,使得最后浓度为 \frac{n}{m},可以则输出最小毫升数,不行则输出 -1

bfs,图论


设每种糖浆使用 b_i 毫升

题面即为求 \sum b_i * a_i = n * \sum b_i,且使 \sum b_i 最小

我们考虑构造出一种有向图,节点当前方案的 \sum b_i * a_i,并向所有能够到达的节点,即 (\sum b_i * a_i) + a_j 连一条边权为 1 的边

那么题目则转化为求 0\frac{n}{\sum b_i} 的最短路

注意到这仍然和 b 有关,那么这里有一个小 trick:

将所有 a_i 都减去 n,那么原式变为求 00 的最短环的环长

还有一个问题,注意到这样连边的话是有无数条边的,那么当节点到什么程度我们就可以不连了呢?

考虑当到这个点时,已经花费了超过 m 毫升了,那么一定是不优的了

bfs 即可

时间复杂度 O(nk)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10, maxm = 1000 + 10;
int k, n, m, a[maxn], mp[maxn];
queue<int> q;

void bfs() {
    q.push(0), mp[0] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (mp[u] > 1000) { puts("-1"); return ; }
        for (int i = 1; i <= k; ++i) {
            int v = u + a[i];
            if (v == 0) { printf("%d\n", mp[u] + 1); return ; }
            if (!mp[v]) { mp[v] = mp[u] + 1, q.push(v); }
        }
    }
}

int main() {
    scanf("%d %d %d" , &k, &n, &m);
    for (int i = 1; i <= k; ++i) scanf("%d", &a[i]), a[i] -= n;
    bfs();
    return 0;
}

C 树

给出 n 个节点与 fa_1, fa_2 \cdots fa_nfa_i 代表在 ifa_i 之间连一条无向边,有可能有自环,求至少更改多少的 fa_i 使得整个图为一棵数

图论,并查集


一血还行

由于上次 cf 的失利,貌似我这次比较快地反应过来是并查集?

由于在原图上,一共只有 n 条边,那么我们的任务就是:

  • 只有且一个自环

那么会出现一下需要调整情况:

  • 出现环(不包括自环)
  • 不连通

那么我们只需要记录有多少条环(不包括自环),多少个连通块即可,具体看代码吧

时间复杂度 O(\alpha(n))

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 10;
int n, a[maxn], fa[maxn], cnt, ans;
void init() { for (int i = 1; i <= n; ++i) fa[i] = i; }
int gf(int x) { return fa[x] == x ? x : fa[x] = gf(fa[x]); }
int main() {
    scanf("%d", &n);
    init();
    for (int i = 1; i <= n; ++i) { int u;
        scanf("%d", &u);
        if (gf(u) != gf(i) || u == i) fa[gf(u)] = gf(i);
        else cnt ++;
    }
    for (int i = 1; i <= n; ++i) if (fa[i] == i) ans ++;
    if (ans == cnt) printf("%d\n", ans);
    else printf("%d\n", ans - 1);
    return 0;
}

D DAG

不会

做的好的地方

  • 一血

做的不好的地方

  • 又去颓了!我再颓我直播口也羊羽!
  • A 式子都推出来了,却没有任何思想,感觉还是题做少了

OI-数学-数论 OI-图论 OI-搜索-bfs OI-数据结构-并查集

弱智图论复习笔记
上一篇 «
入门级字符串复习笔记
» 下一篇
© 2019 - 2019 bwt's blog.
...... visits · ...... visitors