2021-04-04

The 14th Jilin Provincial Collegiate Programming Contest

字数统计: 3.5k字 | 阅读时长: 19分

solved	A	B	C	D	E	F	G	H	I	J	K	L	M	N
10 / 14	O	O	O	·	O	O	O	Ø	Ø	·	·	O	O	!

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

比赛链接

A - Chord

solved by lllllan. 00:56(+)

题解： 根据题意模拟

AC代码

#include <bits/stdc++.h>

using namespace std;

string tem[] = {"A", "A#", "B", "C", "C#", "D", "D#", "E", "F", "F#", "G", "G#"};

void run () {
	int k[4] = {0};
	string s[4];
	
	for (int i = 1; i <= 3; ++i) {
		cin >> s[i];
		for (int j = 0; ; ++j) {
			if (s[i] == tem[j]) {
				k[i] = j;
				break;
			}
		}
		if (i > 1 && k[i] <= k[i - 1]) k[i] += 12;
	}
	
	if (k[2] - k[1] == 4 && k[3] - k[2] == 3) {
		cout << "Major triad\n";
	} else if (k[2] - k[1] == 3 && k[3] - k[2] == 4) {
		cout << "Minor triad\n";
	} else {
		cout << "Dissonance\n";
	}
}

int main () {
	int _; cin >> _;
	while (_--) run();
	return 0;
}

B. Problem Select

Solved by Sstee1XD. 0:22(+)

思路： 签到。

AC代码

#include <bits/stdc++.h>

using namespace std;

int n, k;
int a[3000];

int rd() {
	int tot = 0;
	int n;
	while (tot < 4) {
		char ch = getchar();
		if (ch == '/') tot++;
	}
	scanf("%d", &n);
	return n;
}

int main() {
	int t = 1;
	scanf("%d", &t);
	while (t--) {
		int tot = 0;
		scanf("%d %d", &n, &k);
		for (int i = 1; i <= n; ++i) {
			a[i] = rd();
		}
		sort(a + 1, a + 1 + n);
		for (int i = 1; i <= k; ++i) {
			printf("%d%c", a[i], " \n"[i == k]);
		}
	}
	return 0;
} 

/*
2
3 2
http://acm.hit.edu.cn/pro/1003
http://acm.hit.edu.cn/pro/1002
http://acm.hit.edu.cn/pro/1001
4 1
http://acm.hit.edu.cn/pro/1001
http://acm.hit.edu.cn/pro/2001
http://acm.hit.edu.cn/pro/3001
http://acm.hit.edu.cn/pro/501
*/

C. String Game

Solved by Sstee1XD. 0:29(+)

题意： 求模式串在模式串在文本串中出现了多少次，字母之间可不连续。

思路： 很明显的dp。 $dp[i][j]$ 表示文本串前i位匹配模式串前j位的方案数。懒得想递推方程直接写了记忆化搜索。

AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 5e4 + 7;
const int mod = 1e9 + 7;

void chmod(int &x) {
	if (x >= mod) x -= mod;
}

int dp[N][1024];
char s[N], ss[N];
int lens, lenss;

int dfs(int pos, int had) {
	if (~dp[pos][had]) return dp[pos][had];
	dp[pos][had] = 0;
	if (had > lenss) return 1;
	if (pos > lens) return 0;
	dp[pos][had] += dfs(pos + 1, had);
	chmod(dp[pos][had]);
	if (s[pos] == ss[had]) dp[pos][had] += dfs(pos + 1, had + 1);
	chmod(dp[pos][had]);
	return dp[pos][had];
}

int main() {
	while (~scanf("%s", s)) {
		scanf("%s", ss);
		memset(dp, -1, sizeof(dp));
		lens = strlen(s) - 1;
		lenss = strlen(ss) - 1;
		printf("%d\n", dfs(0, 0));
	}
	return 0;
}
/*
eeettt
et
eeettt
te
*/

E. Shorten the Array

Solved by Sstee1XD & Tryna. 2:27(+5)

题意： 相邻两个正整数可以合并成一个数对另一个数取模后的数，问序列最短为多少。

思路： 划分成多个子序列的子问题。可知序列中的最小值唯一，那么序列的长度能直接到 $1$ ；如果不唯一，也能一路找到所有比它大的数，只要这个数不是最小值的倍数，取模之后就能产生一个比最小值还要小的数字，又变成了第一种情况。如果不能出现最小值唯一，设数量为 $num$ ，序列的最小长度为 $(num + 1) / 2$ 。注意最小值是 $1$ 的情况。

AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 7;
const int inf = 0x3f3f3f3f;

int a[N], n;

int main() {
    int t = 1;
    scanf("%d", &t);
    while (t--) {
        int ans = 0;
        int minn = inf;
        int minm = 0;
        int maxx = -inf;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
        }
        for (int i = 1; i <= n; ++i) {
            if (a[i] <= 0) {
                ans++;
                continue;
            }
            minn = a[i];
            maxx = a[i];
            minm = 1;
            int pos = i;
            i++;
            while (i <= n && a[i] > 0) {
                if (a[i] < minn) {
                    minn = a[i];
                    minm = 1;
                } else if (a[i] == minn) {
                    minm++;
                }
                if (a[i] > maxx) {
                    maxx = a[i];
                }
                i++;
            }
            i--;
            if (minn != maxx && minn > 1) {
//				ans++;
                for (int j = pos; j <= i; ++j) {
                    if (a[j] % minn) {
                        ans++;
                        break;
                    }
                    if (j == i) {
                        ans += (minm + 1) / 2;
                    }
                }
            } else {
                ans += (minm + 1) / 2;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
/*
2
4
1 1 1 1
4
2 3 4 5


100
4
0 0 0 1
4
0 0 1 1
4
0 0 1 2
4
-12 -23 0 1
4
-12 -23 0 0
4
-12 -23 1 2
5
-1 2 0 2 -3
6
-1 2 0 2 2 -3
11
-1 2 1 4 -1 5 6 1 0 3 0
*/

F - Queue

solved by Tryna & SsteeXD1. 4:53(+12)

题意： 给出一个序列和每次交换的两个数的位置，求在交换的过程中出现次数最少的逆序对。

题解： 发现每次交换的位置距离不超过 $100$ ，那么就可以考虑暴力枚举这个区间计算交换这两个数对答案总贡献的影响。需要用树状数组先求出刚开始的逆序对个数。这题坑有点多，首先可以在 $0$ 位置，树状数组处理不了 $0$ 的情况，所以需要将所有值 $+1$ ，其次可能会有位置相同的情况出现。

AC代码

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int maxn = 1e5 + 7;

ll n, m, a[maxn];
ll sum[maxn];

inline int rd() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while ('0' <= ch && ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}

int lowbit(int x) {
	return x & -x;
}

void add(int i) {
	while (i < maxn) {
		sum[i] += 1ll;
		i += lowbit(i);
	}
}

ll query(int i) {
	ll res = 0;
	while (i) {
		res += sum[i];
		i -= lowbit(i);
	}
	return res;
}

void solve() {
	cin >> n;
	memset(sum, 0, sizeof(sum));
	ll tot = 0;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i]++;
		tot += query(maxn - 1) - query(a[i]);
		add(a[i]);
	}
	cin >> m;
	ll res = tot;
	for(int i = 1; i <= m; i++) {
		int l, r;
		cin >> l >> r;
		if(l == r) continue;
		for(int j = l + 1; j < r; j++) {
			if(a[j] > a[r]) tot--;
			else if (a[j] < a[r]) tot++;
			if(a[j] < a[l]) tot--;
			else if(a[j] > a[l])tot++;			
		}
		if(a[r] < a[l]) tot--;
		else if(a[r] > a[l])tot++;
        ll tmp = a[l];
        a[l] = a[r];
        a[r] = tmp;
		res = res < tot? res : tot;
	}
	cout << res << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--) 
		solve();
	return 0;
}

G - Matrix

solved by Tryna.1:30(+)

题解: 打表找规律，规律为$\sqrt{n} * \sqrt{m} $

AC代码

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int maxn = 1e6 + 7;

ll n, m;

int main() {
	int t = 1;
	scanf("%d", &t);
	while (t--) {
		scanf("%lld %lld", &n, &m);
		ll a = (ll)sqrt(n);
		ll b = (ll)sqrt(m);
		ll c = a * b;
		printf("%lld\n", c);
	}
	return 0;
}

H - Curious

solved by Tryna.(-)

题意： 计算$$\sum_{i = 1}^n\sum_{j = 1}^n[gcd(a_i,a_j)=x]$$

题解： 设 $g(d) = \sum_{i = 1}^n\sum_{j = 1}^n[gcd(a_i,a_j)=d]$

构造一个 $f(d) = g * I = \sum_{d|x}g(x) = \sum_{i = 1}^n\sum_{j = 1}^n\sum_{d|x}[gcd(a_i,a_j)=x]$

可以发现 $a_i, a_j$ 的 $gcd$ 是 $d$ 的倍数当且仅当 $a_i, a_j$ 都是 $d$ 的倍数

所以 $f(d) = \sum_{i = 1}^n\sum_{j = 1}^n[(d|a_i) \& (d|a_j)]$

所以我们设 $h(x)$ 为 $a[n]$ 序列中 $x$ 的倍数的个数。

所以 $f(d) = h^2(x)$

然后套用反演公式 $g(d) = \sum_{d|x}f(x)\mu(\frac{x}{d})$

然后预处理 $h(x) 和 g(x)$ 就好了，然后就可以离线处理了。

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 double eps = 1e-8;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7; 
ll prime[maxn], mu[maxn], check[maxn];
ll a[maxn], num[maxn], h[maxn];
ll ans[maxn];
void init() {
	mu[1] = 1;
	int tot = 0;
	for(int i = 2; i <= maxn; i++) {
		if(!check[i]) {
			prime[tot++] = i;
			mu[i] = -1;
		}
		for(int j = 0; j < tot; j++) {
			if(i * prime[j] > maxn) break;
			check[i * prime[j]] = true;
			if(i % prime[j] == 0) {
				mu[i * prime[j]] = 0;
				break;
			}
			else{
				mu[i * prime[j]] = -mu[i];
			}
		}
	}
}
void solve(){
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	memset(num, 0, sizeof(num));
	memset(h, 0, sizeof(h));
	memset(ans, 0, sizeof(ans));
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		num[ a[i] ]++;
	}

	for(int i = 1; i <= m; i++) {
		for(int j = 1;  j * i <= m; j++) {
			h[i] += num[j * i];
		}
	}

	for(int i = 1; i <= m; i++) {
		for(int j = 1; j * i <= m; j++) {
			ans[i] += h[j * i] * h[j * i] * mu[j];
		}
	}

	while(k--) {
		int x;
		scanf("%d", &x);
		printf("%lld\n", ans[x]);
	}
	
}
int main() {
	init();
	int t = 1;
	scanf("%d", &t);
	// cin>>t;
	while(t--)
		solve();
	return 0;
}

I - World Tree

solved by lllllan. (-)

题意： 一棵树上，每个点都有两个权值 $a_,b_i$ ，从根节点1开始遍历整棵树，到达点i时能过获得权值 $a_i*\sum剩下所有还没遍历的点b$ 。要求确立一个遍历顺序，使得能够获得的权值和最大。

题解：

对于一棵子树，到达这棵子树的根节点时，能过获得的权值是根节点的 $a_i$ 乘以子树中除了根节点的 $\sum{b_k}$ 。
对于同个根节点下的两棵子树 $i,j$ ，忽略子树内部获得的权值，遍历这两个整体能够获得的权值应为max( $\sum{a_i} * \sum{b_j}$ , $\sum{a_j} * \sum{b_i}$ )。对于这个权值，无论两棵子树内部的遍历顺序如何，都不会影响这个结果。
当同个根节点下有多棵子树（多个子节点）时，依然是先遍历 $a_i / b_i$ 较大的子树能过获得更大的权值

AC代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10;

int n;

ll a[maxn], A[maxn];
ll b[maxn], B[maxn];
ll dp[maxn];

vector<int> G[maxn];
bool cmp (int a, int b) { return A[a] * B[b] > A[b] * B[a]; }

void DFS (int u, int fa) {
	A[u] = a[u], B[u] = b[u], dp[u] = 0;
	
	ll sum = 0;
	for (int v : G[u]) {
		if (v == fa) continue;
		DFS(v, u);
		A[u] += A[v], B[u] += B[v];
		dp[u] += dp[v];
		sum += B[v];
	}
	dp[u] += a[u] * sum;
	sort(G[u].begin(), G[u].end(), cmp);
	for (int v : G[u]) {
		if (v == fa) continue;
		sum -= B[v];
		dp[u] += A[v] * sum;
	}
}

void run () {
	scanf("%d", &n);
	
	for (int i = 1; i <= n; ++i) G[i].clear();
	
	for (int i = 1; i <= n; ++i) scanf("%lld", b + i);
	for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
	
	for (int i = 1; i <  n; ++i) {
		int u, v; scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	DFS(1, 0);
	printf("%lld\n", dp[1]);
}

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

L - Swimmer

solved by lllllan. 00:32(+)

题意： n个游泳选手，m长的泳池，选手以不同速度在泳池里来回游泳，问p时刻k选手的位置。

AC代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e6 + 10;

ll n, m, q;
ll x[maxn];

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> q;
	
	for (int i = 1; i <= n; ++i) {
		cin >> x[i];
	}
	
	while (q--) {
		ll p, k;
		cin >> p >> k;
		ll tem = (p * x[k]) % (m * 2);
		if (tem > m) tem = 2 * m - tem;
		cout << tem << "\n";
	}
	
	return 0;
}

M. Upanishad

Solved by Sstee1XD. 3:26(+)

题意： 求区间出现次数为偶数次的数的异或和。

题解： 出题人说卡了莫队的做法，但是 $CF$ 机子太好了，直接冲过去了，就当我过了吧。

正解是利用前缀异或和来求出区间异或和，然后异或上区间有出现的数字的异或和，这样就能让奇偶数量翻转，得到我们想要的答案。按照区间左端点进行从小到大处理，用树状数组来维护。 $vj$ 有大佬的码，偷下懒。

AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 7;

int n, q, ans;
int a[N], b[N], cor[N], pos[N], res[N];
int num[N];

inline int rd() {
    int s = 0, w = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) {
        if (ch == '-') w = -1;
    }
    for (; isdigit(ch); ch = getchar()) {
        s = (s << 1) + (s << 3) + ch - '0';
    }
    return s * w;
}

struct Node{
	int l, r, id;
}node[N];

bool cmp(Node a, Node b) {
	if (pos[a.l] == pos[b.l]) {
		if (pos[a.l] & 1) return a.r < b.r;
		else return a.r > b.r;
	} else {
		return pos[a.l] < pos[b.l];
	}
}

void ins(int j) {
	if (num[cor[j]]) ans ^= a[j];
	num[cor[j]]++;
}

void del(int j) {
	if (num[cor[j]] != 1) ans ^= a[j];
	num[cor[j]]--;
}

void solve() {
	int pre = -1, pl = 1, pr = 0;
	for (int i = 1; i <= q; ++i) {
		int l = node[i].l, r = node[i].r, id = node[i].id;
		while (l > pl) del(pl++);
		while (l < pl) ins(--pl);
		while (r > pr) ins(++pr);
		while (r < pr) del(pr--);
		res[id] = ans;
	}
	for (int i = 1; i <= q; ++i) {
		printf("%d\n", res[i]);
	}
}

int main() {
	n = rd();
    q = rd();
	for (int i = 1; i <= n; ++i) {
		a[i] = rd();
		b[i] = a[i];
	}
	sort(b + 1, b + 1 + n);
	int tot = unique(b + 1, b + 1 + n) - b - 1;
	for (int i = 1; i <= n; ++i) {
		cor[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;
	}
	int len = sqrt(n);
	for (int i = 1; i <= n; ++i) {
		pos[i] = (i + len - 1) / len;
	}
	for (int i = 1; i <= q; ++i) {
        node[i].l = rd();
        node[i].r = rd();
		node[i].id = i;
	}
	sort(node + 1, node + 1 + q, cmp);
	solve();
	return 0;
}