DreamW1ngs 阅读(22) 评论(0)

比赛地址

A(水题)

题目链接

题目:
给出指定\(n\),求解出一段区间\([l,r]\)使得\(\sum\limits_{i=l}^ri=n\)

解析:
从点0,1两点作为起点分别向左右延伸长度,每次延伸单位长度时,这段区间和也加1,因此答案为\([1-n,n]\)

#include<bits/stdc++.h>
using namespace std;

int main() {
	int T;
	long long t;
	scanf("%d", &T);
	while (T--) {
		scanf("%lld", &t);
		printf("%lld %lld\n", 1 - t, t);
	}
}

B(水题)

题目链接

题目:
给出底数\(n\),由若干不同的\(n^i(i\ge0)\)组成的数中,第\(k\)大的数是多少

解析:
\(n^i\)只有出现或者不出现两种可能,也就是说它的系数只能是0或1,这样第\(k\)大对应的系数即为\(k\)对应的二进制形式

#include<bits/stdc++.h>
using namespace std;

long long n, k, mod = 1e9 + 7;


int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld", &n, &k);
		long long t = 1, ans = 0;
		while (k) {
			if (k & 1) ans = (ans + t) % mod;
			k >>= 1;
			t = t * n % mod;
		}
		printf("%lld\n", ans);
	}
}

C(埃筛)

题目链接

题目:
给出一组下标\(a(a_i\le n)\),每次可以指定一个\(x\),将\(x\nmid a_i\)则消除\(a_i\),问最少指定几个\(x\)

解析:

  • 对于特殊情况如果\(a\)的长度为\(0\),则直接输出\(0\)
  • 考虑如何一次清除,可以用类似埃筛的思想,对于任意一个不在\(a\)中的下标,考虑它小于\(n\)的倍数是否在数组中,如果均不在数组中,则输出这个值
    优化: 考虑证明结论如果n的后一半数中,存在某个值不在下标序列中,则这个值可以作为答案。充分性显然成立,必要性考虑\(n\)的前一半数如果作为答案,则一定有一个它的倍数属于\(n\)的后一半数,且不在下标序列中
  • 上述情况都不满足时,输出\(n,n-1\)即可消除所有的数(因为\(x=n\)时,无法消除\(n\)
#include<bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 5;
char str[maxn];

int main() {
	int T;
	int n;
	char ch;
	scanf("%d", &T);
	while (T--) {
		scanf("%d %c%s", &n, &ch, str);
		bool ok = 0;
		for (int i = 0; i < n; ++i)
			if (str[i] != ch) {
				ok = true;
				break;
			}
		if (ok) {
			for (int i = n / 2; i < n; ++i) {
				if (str[i] == ch) {
					ok = false;
					printf("1\n%d\n", i + 1);
					break;
				}
			}
			if (ok)
				printf("2\n%d %d\n", n - 1, n);
		}
		else printf("0\n");
	}
}

D(带权并查集)

题目链接
⭐⭐

题目:
现在有\(n\)个人,有诚实的人也有撒谎的人。诚实的人只说真话,撒谎的人只说假话,他们共说了\(m\)句话,以\(i\quad j\quad identity\)的形式给出,代表\(i\)认为\(j\)是什么身份,如果言语不合法则输出-1,否则输出最多的撒谎者个数

解析:
这道题与UVA 10158非常类似,如果\(i\)认为\(j\)是诚实的人,则\(i,j\)同真同假,反之一真一假,设\([1,n]\)代表1\(\sim n\)是诚实的人的情况,\([n+1,2n]\)代表是撒谎者的情况,初始时对于所有撒谎情况赋予权重1

  • 如果属于同真同假,则判断是否二者已处于一真一假的状态,如果是则集合加入失败,反之将\((i,j)\)\((i+n,j+n)\)加入同一集合
  • 如果属于一真一假,则判断是否二者已处于同真同假的状态,如果是则集合加入失败,反之将\((i,j+n)\)\((i+n,j)\)加入同一集合

最后统计答案时,考虑遍历所有人,如果未加入答案集合中,则添加\(\max\{sz_{撒谎者},sz_{诚实的人}\}\),并将其本身与连带关系加入答案集合

注意:
由于已有关系仍然可能出现,而在建立关系过程中更改了\(sz\)数组,所以此时要对建立关系的步骤进行忽略

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m;
const int maxn = 4e5 + 5;
int p[maxn], sz[maxn];

int find(int x) {
	if (p[x] == x) return x;
	return p[x] = find(p[x]);
}

bool set2(int x, int y) {
	int x1 = find(x), x2 = find(y), y1 = find(x + n), y2 = find(y + n);
	if (x1 == x2) return false;
	if (x1 == y2 || x2 == y1) return true;
	sz[x1] += sz[y2];
	sz[y1] += sz[x2];
	p[y2] = x1;
	p[x2] = y1;
	return true;
}

bool set1(int x, int y) {
	int x1 = find(x), x2 = find(y), y1 = find(x + n), y2 = find(y + n);
	if (x1 == y2 || x2 == y1) return false;
	if (x1 == x2) return true;
	sz[x1] += sz[x2];
	sz[y1] += sz[y2];
	p[x2] = x1;
	p[y2] = y1;
	return true;
}

char str[1000];
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (int i = 0; i <= n; ++i)
			sz[i] = 0, p[i] = i;
		for (int i = n + 1; i <= 2 * n; ++i)
			sz[i] = 1, p[i] = i;
		int a, b;
		bool ok = true;
		while (m--) {
			scanf("%d%d%s", &a, &b, str);
			if (str[0] == 'i')
				ok &= set2(a, b);
			else ok &= set1(a, b);
		}
		for (int i = 1; i <= n; ++i)
			if (find(i) && find(i + n)) {
				sz[0] += max(sz[find(i)], sz[find(i + n)]);
				p[find(i)] = p[find(i + n)] = 0;
			}
		if (ok)
			printf("%d", sz[0]);
		else
			printf("-1");
		printf("\n");
	}
}

E hard version(搜索+状态转移+组合)

题目链接
⭐⭐⭐

题目:
给出一个高度为\(k\)的满二叉树,编号按层次遍历,现要给每个节点染色,其中相邻节点不能均为(红、橙)(白、黄)(绿、蓝)三对中某一对,且有些节点色彩已被指定,问染色方案数

解析:
根据Easy Version的结论,对于每个节点来说,如果父节点颜色已被确定,则该节点有4种方案,所以当某些节点(假设总个数未\(cnt_{else}\))未被指定颜色节点影响时,贡献为\(4^{cnt_{else}}\)
对于那些被影响的节点,考虑使用\(map\)存储每个节点的颜色属于的对,并且对他的所有父节点进行标记(被影响),\(cnt_{else}=2^k-1-map_{size}\),考虑进行搜索(假设\(v[0,1,2]\)分别代表当前节点取某个颜色对中的颜色时,可行的方案数)不难得到以下转移式

\[\text{init} :v=\{2,2,2\}\ or\ \{x_0,x_1,x_2\}\ \text{x is depend on its color}\\ v[0]=v[0]*(v_{son}[1]+v_{son}[2]) \\ v[1]=v[1]*(v_{son}[0]+v_{son}[2]) \\ v[2]=v[2]*(v_{son}[0]+v_{son}[1]) \]

最后答案即为\((v_1[0]+v_1[1]+v_1[2])\times 4^{cnt_{else}}\)

注意:
博主也不知道为什么,这里使用\(map\)可以AC,但使用\(unordered\_map\)会TLE在第9个样例(若有同学知晓,可否评论区指点一二)

#include<bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 5;
char str[maxn];

map<long long, int> m;
int k, n;
const long long mod = 1e9 + 7;

long long ksm(long long a, long long b) {
	long long ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return ans;
}

vector<long long> dfs(long long x) {
	vector<long long> t = { 2,2,2 };
	if (m.count(x) && ~m[x]) {
		for (int i = 0; i < 3; ++i)
			t[i] = i == m[x];
	}
	for (long long i : {x << 1, x << 1 | 1}) {
		if (!m.count(i)) continue;
		vector<long long> s = dfs(i);
		t[0] = (t[0] * (s[1] + s[2]) % mod) % mod;
		t[1] = (t[1] * (s[0] + s[2]) % mod) % mod;
		t[2] = (t[2] * (s[0] + s[1]) % mod) % mod;
	}
	//printf("%lld:%lld %lld %lld\n", x, t[0], t[1], t[2]);
	return t;
}

int main() {
	long long v;
	char ch;
	scanf("%d%d", &k, &n);
	while (n--) {
		scanf("%lld %c%*s", &v, &ch);
		switch (ch) {
		case 'r':
		case 'o': m[v] = 0; break;
		case 'w':
		case 'y': m[v] = 1; break;
		default: m[v] = 2;
		}
		v >>= 1;
		while (v) {
			if (!m.count(v))
				m[v] = -1;
			else break;
			v >>= 1;
		}
	}
	vector<long long> ans = dfs(1);
	printf("%lld", (ans[0] + ans[1] + ans[2]) % mod * ksm(4, (1ll << k) - 1 - m.size()) % mod);
}

F(构造)

题目链接
⭐⭐⭐

题目:
\(s\)个物品分为\(n\)堆,每堆编号从\(1\sim n\),且保证每堆至少有一个物品,问是否对于任意一种物品分发方式都存在一个连续区间\([l,r]\)使得,这段区间内对应堆中物品数量和为\(k\)

解析:
\(s=k\)时,即每次取所有堆的情况,显然成立
\(s<k\)时,取所有物品也到不了\(k\),显然不成立
对于\(s>k\)的情况,考虑构造一个所用物品最小,且不满足条件的分配方式

\[\underbrace{1, 1, 1, \dots}_{k-1},\ k+1,\ \underbrace{1,1,1,\dots}_{k-1},\ k+1,\ \dots \]

不难发现这样的构造方式下,需要对每个堆分发一个物品,剩下的物品数量为\(s-n\),而下标为\(k\)的倍数的位置,需要再多分配\(k\)个物品,总计为\(\lfloor \frac{n}{k}\rfloor k\)个物品,那么当\(s-n<\lfloor \frac{n}{k}\rfloor k\)时无法构造

#include<bits/stdc++.h>
using namespace std;

int main() {
	int T;
	long long s, n, k;
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld%lld", &s, &n, &k);
		if (s == k) printf("YES\n");
		else if (s < k) printf("NO\n");
		else printf("%s\n", n / k * k > s - n ? "YES" : "NO");
	}
}