2021-03-24

2020 China Collegiate Programming Contest, Weihai Site

字数统计: 2.6k字 | 阅读时长: 14分

solved	A	B	C	D	E	F	G	H	I	J	K	L
5 / 12	O	·	·	O	·	·	Ø	O	·	·	·	Ø

O：比赛时通过
Ø：赛后通过
!：比赛时尝试了未通过
·：比赛时未尝试

比赛链接

A. Golden Spirit

Solved by Sstee1XD & Tryna. 0:24(+1)

题意： 给你一座桥，桥的两边都有 $n$ 个人，他们都想到桥的另一边呆至少 $x$ 分钟，然后再回来，但是他们不能自己过桥，需要你进行帮助。你从桥的一边到另一边需要 $t$ 分钟，每次可以带一个人，问你最短需要多长时间完成目标。

思路： 肯定是先马不停蹄地把人都搬到对岸去，然后判断下何时能开始搬人回去。注意此时第一个人和你并不在同一边，分类讨论下即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;

typedef long long ll;

ll n, x, t;

void run () {
    scanf("%lld%lld%lld", &n, &x, &t);
    ll ans = 0;
    ans = 2 * n * t;
    ll last = x - (2 * n - 2) * t;
    if (last <= 0) {
        ans += 2 * n * t;
    } else {
        if (last <= t) {
            ans += last;
            ans += 2 * n * t;
        } else {
            ans += t;
            last = x - (2 * n) * t;
            if (last <= 0) last = 0;
            ans += last;
            ans += 2 * n * t;
        }
    }
    printf("%lld\n", ans);
}

int main () {
    int t = 1;
    scanf("%d", &t);
    while (t--) run();
    return 0;
}

D - ABC Conjecture

solved by Tryna & Sstee1XD.1:36(+)

题意给出一个数 $c$ ，问你能否找到一个 $a$ 和 $b$ 满足 $a + b = c$ 并且 $a * b * c$ 所有不同的素因子相乘小于 $c$

题解： 不难发现如果 $c$ 中有一个质因子出现的次数不止一次，那么就满足 $yes$ ，否则是 $no$ 。思路很简单，但 $c$ 很大，所以我们这里需要用到大整数质因数分解，这里用的是 $kuangbin$ 模板。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 10;
const int S = 8;
long long mult_mod(ll a, ll b, ll c) {
	a %= c;
	b %= c;
	ll ret = 0;
	ll tmp = a;
	while(b) {
		if(b & 1) {
			ret += tmp;
			if(ret > c) ret -= c;
		}
		tmp <<= 1;
		if(tmp > c) tmp -= c;
		b >>= 1;
	}
	return ret;
}

ll pow_mod(ll a, ll n, ll mod) {
	ll ret = 1;
	ll temp = a % mod;
	while(n) {
		if(n & 1) ret = mult_mod(ret, temp, mod);
		temp = mult_mod(temp, temp, mod);
		n >>= 1;
	}
	return ret;
}

bool check(ll a, ll n, ll x, ll t) {
	ll ret = pow_mod(a, x, n);
	ll last = ret;
	for(int i = 1; i <= t; i++) {
		ret = mult_mod(ret, ret, n);
		if(ret == 1 && last != 1 && last != n - 1) return true;
		last = ret; 
	}
	if(ret != 1) return true;
	else return false;
}

bool Miller_Rabin(ll n) {
	if(n < 2) return false;
	if(n == 2) return true;
	if((n & 1) == 0) return false;
	ll x = n - 1;
	ll t = 0;
	while((x & 1) == 0) {
		x >>= 1;
		t++;
	}
	srand(time(NULL));
	for(int i = 0; i < S; i++) {
		ll a = rand() % (n - 1) + 1;
		if(check(a, n, x, t)) return false;
	}
	return true;
}

ll factor[100];
int tol;
ll gcd(ll a, ll b) {
	ll t;
	while(b) {
		t = a;
		a = b;
		b = t % b;
	}
	if(a >= 0) return a;
	else return -a;
}

ll pollard_rho(ll x, ll c) {
	ll i = 1, k = 2;
	srand(time(NULL));
	ll x0 = rand() % (x - 1) + 1;
	ll y = x0;
	while(1) {
		i++;
		x0 = (mult_mod(x0, x0, x) + c) % x;
		ll d = gcd(y - x0, x);
		if(d != 1 && d != x) return d;
		if(y == x0) return x;
		if(i == k) {
			y = x0;
			k += k;
		}
	}
}

void findfac(ll n, int k) {
	if(n == 1) return ;
	if(Miller_Rabin(n)) {
		factor[++tol] = n;
		return ;
	}
	ll p = n; 
	int c = k;
	while(p >= n) {
		p = pollard_rho(p, c--);
	}
	findfac(p, k);
	findfac(n / p, k);
}

void run () {
	ll c;
	scanf("%lld", &c);
	map<ll, int>mp;
	tol = 0;	
	findfac(c, 107);
	for(int i = 1; i <= tol; i++) {
		mp[ factor[i] ]++;
	}
	int flag = 0;
	for(auto v : mp) {
		if(v.second != 1) {
			flag = 1;
			break;
		}
	}
	if(!flag) puts("no");
	else puts("yes");
}

int main () {
	int t = 1;
	scanf("%d", &t);
	while(t--)
		run();
	return 0;
}

G. Caesar Cipher

题意：
给你一段序列，有两种操作。

$1$ $l$ $r$ ，对 $[l, r]$ 区间内所有数 $+1$ 并 $mod\ 65536$
$2$ $x$ $y$ $l$ ，询问 $[x, x + l]$ 是否与 $[y, y + l]$ 相等

题解：
考虑线段树。需要 $mod\ 65536$ ，看似不是很好操作，但其实你要从 $0$ 加到 $65536$ 的周期是比较长的，不会很频繁地更新很多点，所以我们就可以暴力去 $mod\ 65536$ 。对于询问区间是否相等，我们可以用线段树来维护区间哈希值，最后取出来比较哈希值即可。

题目卡自然溢出。卡哈希最重要的不是 $base$ 值，而是模数，我们手动取模一下就能过了。保险的话也可以用双哈希维护，判断两种哈希值是否都相同。

AC代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;
const int M = 65536;
const ll bas = 131;
const int N = 5e5 + 7;

ll gap[N];
int n, q, a[N], ql, qr, len, op;

struct Seg{
    ll t[N << 2], base[N << 2], maxx[N << 2], lazy[N << 2];
    
    void up(int id) {
        base[id] = (base[id << 1] + base[id << 1| 1]) % mod;
        t[id] = (t[id << 1] + t[id << 1 | 1]) % mod;
        maxx[id] = max(maxx[id << 1], maxx[id << 1 | 1]);
    }
    
    void build(int id, int l, int r) {
        t[id] = maxx[id] = base[id] = lazy[id] = 0;
        if (l == r) {
            base[id] = gap[l - 1];
            maxx[id] = a[l];
            t[id] = (ll)a[l] * base[id] % mod;
            return;
        }
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        up(id);
    }
    
    void down(int id) {
        if (!lazy[id]) return;
        ll tmp = lazy[id];
        lazy[id] = 0;
        lazy[id << 1] += tmp;
        lazy[id << 1 | 1] += tmp;
        maxx[id << 1] += tmp;
        maxx[id << 1 | 1] += tmp;
        t[id << 1] = (t[id << 1] + (base[id << 1] * tmp) % mod) % mod;
        t[id << 1 | 1] = (t[id << 1 | 1] + (base[id << 1 | 1] * tmp) % mod) % mod;
    }
    
    void modify(int id, int l, int r, int ql, int qr) {
        if (l >= ql && r <= qr) {
            lazy[id]++;
            maxx[id]++;
            t[id] = (t[id] + base[id]) % mod;
            return;
        }
        down(id);
        int mid = l + r >> 1;
        if (ql <= mid) modify(id << 1, l, mid, ql, qr);
        if (qr > mid) modify(id << 1 | 1, mid + 1, r, ql, qr);
        up(id);
    }
    
    ll query(int id, int l, int r, int ql, int qr) {
        if (l >= ql && r <= qr) return t[id];
        down(id);
        ll res = 0;
        int mid = l + r >> 1;
        if (ql <= mid) res = (res + query(id << 1, l, mid, ql, qr)) % mod;
        if (qr > mid) res = (res + query(id << 1 | 1, mid + 1, r , ql ,qr)) % mod;
        return res;
    }
    
    void work(int id, int l, int r) {
        if (maxx[id] < M) return;
        if (l == r) {
            maxx[id] %= M;
            t[id] = base[id] * maxx[id] % mod;
            return;
        }
        down(id);
        int mid = l + r >> 1;
        if (maxx[id << 1] >= M) work(id << 1, l, mid);
        if (maxx[id << 1 | 1] >= M) work(id << 1 | 1, mid + 1, r);
        up(id);
    }
}seg;

bool ok() {
    seg.work(1, 1, n);
    scanf("%d %d %d", &ql, &qr, &len);
    if (qr < ql) swap(ql, qr);
    ll va = seg.query(1, 1, n, ql, ql + len - 1);
    ll vb = seg.query(1, 1, n, qr, qr + len - 1);
    va = va * gap[qr - ql] % mod;
    return va == vb;
}

void solve() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    seg.build(1, 1, n);
    for (int i = 1; i <= q; ++i) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d", &ql, &qr);
            seg.modify(1, 1, n, ql, qr);
        } else {
            if (ok()) puts("yes");
            else puts("no");
        }
    }
}

int main() {
    gap[0] = 1;
    for (int i = 1; i < N; ++i) {
        gap[i] = gap[i - 1] * bas % mod;
    }
    solve();
    return 0;
}

/*
5 6
1 2 1 2 1
2 1 2 2
2 1 3 3
1 1 1
1 3 5
2 1 2 4
2 1 2 2
*/

H. Message Bomb

Solved by all. 1:02(+)

题意： 现有 $n$ 个群聊， $m$ 个人， $s$ 个操作，刚开始群聊里没有人，每次操作有三个正整数 $op$ ， $u$ ， $v$ ，操作对应如下：

$1$ $u$ $v$ ， $u$ 这个人加入了 $v$ 群聊
$2$ $u$ $v$ ， $u$ 退出了 $v$
$3$ $u$ $v$ ， $u$ 向自己所在的群聊 $v$ 发消息，即除了 $u$ 以外， $v$ 中所有人都会收到一条消息

问最终每个人各收到了多少消息。

思路： 正着来的话怎么想怎么 $T$ ，那么能否考虑反着来呢？我们考虑 $p_i$ 代表第 $i$ 个人的权值， $g_i$ 代表第 $i$ 个群聊的权值，当 $u$ 在 $v$ 中发出消息后，我们对 $g_v$ 的权值 $+1$ ，同时对 $p_u$ 的权值 $-1$ 。当 $u$ 加入 $v$ 时，现在 $g_v$ 的权值对 $p_u$ 的权值有贡献，那么 $p_u$ 的权值应该加上 $g_v$ 的权值。当 $u$ 退出 $v$ 时，这些权值则不能被纳入计算范围，所以要减去。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int Q = 1e6 + 10;
const int N = 2e5 + 7;

int qt[Q], qx[Q], qy[Q];
int g[N];
int p[N];
int n, m, s;


int main () {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= s; ++i) {
        scanf("%d%d%d", &qt[i], &qx[i], &qy[i]);
    }
    for (int i = s; i >= 1; --i) {
        if (qt[i] == 3) {
            p[ qx[i] ]--;
            g[ qy[i] ]++;
        }
        if (qt[i] == 2) {
            p[ qx[i] ] -= g[ qy[i] ];
        }
        if (qt[i] == 1) {
            p[ qx[i] ] += g[ qy[i] ];
        }
    }
    for (int i = 1; i <= m; ++i) {
        printf("%d\n", p[i]);
    }
    return 0;
}

L - Clock Master

solved by Tryna.(-)

题意： 把 $n$ 拆分成若干个数的和，使这些数的 $lcm$ 最大，输出 $ln^{lcm}$

题解： 为了使得 $lcm$ 最大，所以我们要使选中的数字尽可能互质，所以我们考虑分组背包，将一个素数的不同幂次划分为一组，现在问题就变成了在每组中选一个数，求乘积的最大值，因为相乘可能会很大，所以我们提前预处理出 $ln$ ，因为 $ln^{a * b} = ln^a + ln^b$ ，所以可以大大降低数字的大小。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//#define LL __int128;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define PAUSE system("pause");
const int maxn = 3e4 + 10;
const int mod = 998244353;
int n, vis[maxn], prime[maxn], cnt;
double dp[maxn], Log[maxn];
void init(int n) {
	for(int i = 2;i <= n; i++){
        if(!vis[i]) prime[++cnt] = i;
        for(int j = 1; j <= cnt && i * prime[j] <= n; j++){
            vis[i * prime[j]] = true;
            if(i % prime[j] == 0)break;
        }
    }
	for(int i = 1; i <= n; i++) 
		Log[i] = log(i);
	for (int i = 1; i <= cnt; ++i) {
		for (int j = n; j >= prime[i]; --j) {
			for (int k = prime[i]; k <= j; k *= prime[i]) {
				dp[j] = max(dp[j], dp[j - k] + Log[k]);
			}
		}
	}
}
void solve() {
    scanf("%d", &n);
	printf("%.9f\n", dp[n]);
}
int main() {
	init(maxn);
	int t = 1;
	scanf("%d", &t);
	while(t--)
		solve();
	return 0;
}