2021-03-13

HZNU Training 2 for Zhejiang Provincial Competition2021

字数统计: 3.1k字 | 阅读时长: 15分

solved	A	B	C	D	E	F	G	H	I
8 / 9	O	!	O	Ø	O	O	O	O	O

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

比赛链接

A Bonuses on a Line

Solve by Sstee1XD. (1:04)

题意： 给你一个 $x$ 轴， $n$ 个小球的坐标和你能移动的时间，你目前在 $0$ 点，每次可以移动一个单位，问你最多能收集多少小球。

思路： 很明显最多折返一次是最优选择，两边分开讨论，二分一下即可。

AC代码

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, t;
int a[N], b[N];

int gao(int a[]) {
	int pos = 1;
	int to = 0;
	while (pos <= n && a[pos] < 0) pos++;
	if (pos > n) {
		return 0;
	}
	int maxx = 0;
	to = lower_bound(a + 1, a + 1 + n, t) - a;
	if (to > n || a[to] > t) maxx = to - 1 - pos + 1;
	else maxx = to - pos + 1;
	for (int i = pos - 1; i >= 1; --i) {
		int tt = t + 2 * a[i];
		if (tt < 0) break;
		to = lower_bound(a + 1, a + 1 + n, tt) - a;
		if (to > n || a[to] > tt) to -= 1;
		maxx = max(maxx, to - pos + 1 + pos - i);
//		printf("%d %d\n", tt, to - pos + 1 + pos - i);
	}
	return maxx;
}

int main ()  {
	scanf("%d %d", &n, &t);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	    b[i] = -a[i];
	}
	sort(b + 1, b + 1 + n);
	printf("%d\n", max(gao(a), gao(b)));
	return 0;
}

C Lexicographically Minimal Shortest Path

solved by lllllan & Setee1XD. 02:02(+2)

题意： n点m边的无向图，每条边上都有字符c。求从点1到点n的最短路，如果存在多条最短路，选择字典序最小的路径。

题解： 相较于朴素的最短路题目，多一个字典序最小的条件 ——》则可以在Dijkstra的优先队列里增加一个字典序的比较。——》但一定不能记录每条路径的字符串，会MLE的。 ——》那怎么办，貌似只能记录路径的最后一条边的字符 ——》但是字典序的比较需要从第一位开始比较，单比较最后一位也是有问题的。 ——》反向遍历，求点n到点1的最小字典序的最短路，此时记录的最后一条边反倒是正常路径的最前面一条边。——》当最后一个字符相同时，又怎么比较前面一段字符串的字典序呢？ ——》记录进入优先队列的顺序，先进入优先队列的点一定是距离和字典序兼优的路径。

AC代码

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

int n, m;

int cnt, head[maxn];
struct edge { int v, c, next; } e[maxn << 1];
void add (int u, int v, int c) {
	e[++cnt] = {v, c, head[u]}; head[u] = cnt;
	e[++cnt] = {u, c, head[v]}; head[v] = cnt;
}

struct node {
	int id, dis, c, pre;
	ll cnt;
	bool operator <(const node a) const {
		if (a.dis == dis) {
			if (a.c == c) return a.cnt < cnt;
			return a.c < c;
		}
		return a.dis < dis;
	}
};

int pre[maxn];
int wri[maxn];
int vis[maxn];

void dfs (int u) {
	printf("%d ", u);
	if (u != n) dfs (pre[u]);
}

void DFS (int u) {
	if (u != n) {
		printf("%c", wri[u] + 'a');
		DFS (pre[u]);
	}
}

void BFS () {
	ll tot = 0;
	priority_queue<node> Q;
	Q.push({n, 0, 0, -1, ++tot});
	
	while (Q.size()) {
		node u = Q.top(); Q.pop();
		if (vis[u.id]) continue;
		vis[u.id] = 1;
		pre[u.id] = u.pre;
		wri[u.id] = u.c;
		
		if (u.id == 1) return (void)(
			printf("%d\n", u.dis),
			dfs(1), puts(""),
			DFS(1)
		);
		
		for (int i = head[u.id]; i; i = e[i].next) {
			int v = e[i].v;
			if (vis[v]) continue;
			Q.push({v, u.dis + 1, e[i].c, u.id, ++tot});
		}
	}
}

int main ()  {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		int u, v; char c;
		scanf("%d%d %c", &u, &v, &c);
		add(u, v, c - 'a');
	}
//	for (int i = 1; i <= cnt; ++i) printf(" -> %d = %c\n", e[i].v, e[i].c + 'a');
	
	BFS();
	return 0;
}

D Nuts and Bolts

Solved by Sstee1XD. (-)

题意： 现有 $n$ 个大小分别为 $1$ ~ $n$ 的螺母和螺栓，但是他们的大小顺序被打乱了。你每次可以询问 $i$ 螺母和 $j$ 螺栓的大小关系，要求在 $5nlogn$ 次询问内找到每个螺母对应的螺栓。

思路： $logn$ 会往二分和分治去想。二分想不到好的办法，所以考虑一下分治。我们可以选择类似于快排的分治，每次在螺母中随机选取一个，然后 $O(n)$ 询问每个螺栓，将比它大和比它小的螺栓分开，记录相等的螺栓。用相等的螺栓 $O(n)$ 遍历螺母，也将螺母分开大小，大概能在 $2nlogn$ 次询问解决。

AC代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1e3 + 7;

int ans[N];
int n;
char ch;

void query(int l, int r) {
	printf("? %d %d\n", l, r);
	fflush(stdout);
	getchar();
	ch = getchar();
}

void pt() {
	printf("!");
	for (int i = 1; i <= n; ++i) {
		printf(" %d",ans[i]);
	}
}

void solve(vector<int> a, vector<int> b) {
    if (a.empty()) return;
	srand(time(0));
	int id = rand() % (int)a.size();
    id = a[id];
	int idb;
    vector<int> la, lb, ra, rb;
    for (auto v : b) {
        query(id, v);
		if (ch == '=') ans[id] = v, idb = v;
		if (ch == '<') rb.push_back(v);
		if (ch == '>') lb.push_back(v);
	}
	for (auto v : a) {
		if (v == id) continue;
		query(v, idb);
		if (ch == '<') la.push_back(v);
		if (ch == '>') ra.push_back(v);
	}
	solve(la, lb);
	solve(ra, rb);
}

int main ()  {
	scanf("%d", &n);
    vector<int> a, b;
	for (int i = 1; i <= n; ++i) {
        a.push_back(i);
		b.push_back(i);
	}
	solve(a, b);
	pt();
	return 0;
}

E Tree Painting

solved by lllllan. 00:31(+)

题意： 一棵n节点的树，从一点出发到另一点将路径上所有的点和边都收纳起来。问最少需要多少条路径可以将整棵树都收纳起来。

题解： 咋一看还没啥思路，仔细一想其实只要求这棵树一共有多少个度数为1的点罢了。

AC代码

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

int n, ans;
int deg[maxn];

void run () {
	scanf("%d", &n);
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d%d", &u, &v);
		deg[u]++, deg[v]++;
	}
	for (int i = 1; i <= n; ++i) {
		if (deg[i] == 1) ans++;
	}
	printf("%d\n", (ans + 1) / 2);
}

int main ()  {
	run();
	return 0;
}

F Sorting Colored Array

solved by lllllan. 00:22(+1)

题意： 一个数列，每个数字都有自己的颜色。用类似于冒泡排序的规则让这个数列从小到大排序（即必须相邻的两个数才可以交换位置），只有两个不同颜色的数字才可以交换位置。判断这个序列是否可以从小到大排序。

题解： 暴力遍历这个序列，一旦存在某个颜色下，较大的数字出现在较小的数字前面，则不能从小到大排序。

AC代码

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

int n;

int a[maxn];
int c[maxn];

int col[maxn];

void run () {
	scanf("%d", &n);
	
	for (int i = 1; i < maxn; ++i) col[i] = -inf;
	for (int i = 1; i <= n; ++i) scanf("%d%d", a + i, c + i);
	for (int i = 1; i <= n; ++i) {
		if (col[ c[i] ] > a[i]) return (void)(printf("NO\n"));
		if (a[i] > col[ c[i] ]) col[ c[i] ] = a[i];
	}
	printf("YES\n");
}

int main ()  {
	run();
	return 0;
}

G The Battle of Mages

Solved by Sstee1XD & Tryna. 1:43(+1)

题意： 两个法师有一些元素，每个元素都有一定的力量。现在他们要对波，每次选取一个k，然后随机地在自己的元素中选取k个，谁的力量和大谁赢。要求你构造出他们拥有的元素，使得当k = 1或者k = 3时，第一个法师胜率高，k = 2时第二个法师胜率高。

思路： 瞎构造，可打表。

AC代码

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

int main ()  {
	puts("3\n3 4 10\n3\n1 7 8");
	return 0;
}

H Nezzar and Board

solved by Tryna.1:18(+)

题意： 每次操作可以在序列中任取两个数 $x$ 、 $y$ ，将 $2x - y$ 放入数组中， $x$ , $y$ 仍保留，询问是否可以凑出 $k$ 。

题解： $2x - y = x + (x - y)$ ，也就是说每次操作都是 $x$ 加上任意的差值,又因为不相邻的两个数的差值可以通过相邻的两个数的差值得到，所以我们只需要求相邻两个数的差值。
我们考虑 $n$ 个数的裴蜀定理：设 $a_1,a_2,a_3...a_n$ 为 $n$ 个整数， $d$ 是他们的 $gcd$ ，那么存在整数 $x_1,x_2...x_n$ 使得 $x_1*a_1 + x_2*a_2 + x_3*a_3...x_n*a_n = d$
由此可以知道这 $n - 1$ 个差值能组合出的数一定是它们 $gcd$ 的倍数，即 $k - a_i$ 一定是 $gcd$ 的倍数。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
#define ll long long
ll gcd(ll a, ll b) {
    return a == 0 ? b : gcd(b % a, a);
}
int t, n;
ll a[maxn], k;
void solve() {
    scanf("%d %lld", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    ll ans = a[2] - a[1];
    for(int i = 3; i <= n; i++) ans = gcd(ans, a[i] - a[i - 1]);
    int f = 0;
    for(int i = 1; i <= n; i++) {
        if((a[i] - k) % ans == 0) {
            f = 1;
            break;
        }
    }
    puts(f?"YES":"NO");
}
int main() {
    scanf("%d", &t);
    while(t--)
        solve();
    return 0;
}

I Nezzar and Binary String

Solved by Sstee1XD. 3:06(+2)

题意： 现有一个 $01$ 串，有 $q$ 天，每天都会选择一个区间，如果这个区间既有 $0$ 又有 $1$ ，直接失败。在这天晚上，你可以在这个区间内选择严格小于它大小一半的元素，修改它们的值。问你在第 $q+1$ 天能否获得特定的 $01$ 串。

题解： 正着来不太好考虑后续的要求，所以要反着来。因为要严格小于一半，所以每次修改的操作是可以确定的。我们可以建一棵线段树，每次询问区间内的 $1$ 的数量，如果 $1$ 的数量大于一半，就将其全部修改成 $1$ ；如果 $1$ 的数量小于一半，就将其全部修改成 $0$ ；如果等于，直接失败。最后再判断一下是否与最开始的字符串相等就行了。

AC代码

#include<bits/stdc++.h>

using namespace std;

#define mid (l + r >> 1)
#define ls (id << 1)
#define rs (id << 1 | 1)

const int N = 2e5 + 10;

int a[N], b[N], ql[N], qr[N];
int n, q;

struct {
	int t[N << 2];
	int lazy[N << 2];
	
	void up(int id) {
		t[id] = t[ls] + t[rs];
	}
	
	void down(int id, int sz) {
		if (lazy[id] == -1) return;
		lazy[ls] = lazy[id];
		t[ls] = lazy[id] * (sz - (sz >> 1));
		lazy[rs] = lazy[id];
		t[rs] = lazy[id] * (sz >> 1);
		lazy[id] = -1;
	}
	
	void build(int id, int l, int r) {
		t[id] = 0;
		lazy[id] = -1;
		if (l == r) {
			t[id] = b[l];
			return;
		}
		build(ls, l, mid);
		build(rs, mid + 1, r);
		up(id);
	}
	
	void modify(int id, int l, int r, int ql, int qr, int v) {
		if (ql <= l && qr >= r) {
			t[id] = v * (r - l + 1);
			lazy[id] = v;
			return;
		}
		down(id, r - l + 1);
		if (ql <= mid) modify(ls, l, mid, ql, qr, v);
		if (qr > mid) modify(rs, mid + 1, r, ql, qr, v);
		up(id);
	}
	
	int query(int id, int l, int r, int ql, int qr) {
		if (ql <= l && qr >= r) return t[id];
		down(id, r - l + 1);
		int res = 0;
		if (ql <= mid) res += query(ls, l, mid, ql, qr);
		if (qr > mid) res += query(rs, mid + 1, r, ql, qr);
		return res;
	}
}seg;

void run () {
	scanf("%d %d", &n, &q);
	for (int i = 1; i <= n; ++i) {
		scanf("%1d", &a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%1d", &b[i]);
	}
	seg.build(1, 1, n);
	for (int i = 1; i <= q; ++i) {
		scanf("%d %d", &ql[i], &qr[i]);
	}
	
	for (int i = q; i >= 1; --i) {
		int sum = seg.query(1, 1, n, ql[i], qr[i]);
		int sz = qr[i] - ql[i] + 1;
		if (sz == 1) continue;
		
		if (sz & 1) {
			if (sum > sz / 2) seg.modify(1, 1, n, ql[i], qr[i], 1);
		    else seg.modify(1, 1, n, ql[i], qr[i], 0);
		} else {
			if (sum > sz / 2) seg.modify(1, 1, n, ql[i], qr[i], 1);
			else if (sum < sz / 2)seg.modify(1, 1, n, ql[i], qr[i], 0);
			else {
				puts("NO");
				return;
			}
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		if (seg.query(1, 1, n, i, i) != a[i]) {
			puts("NO");
			return;
		}
	}
	puts("YES");
}

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