Codeforces Round #747 (Div. 2)
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]\)分别代表当前节点取某个颜色对中的颜色时，可行的方案数）不难得到以下转移式
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\)的情况，考虑构造一个所用物品最小，且不满足条件的分配方式
\]
不难发现这样的构造方式下，需要对每个堆分发一个物品，剩下的物品数量为\(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");
}
}
最新文章
- front-end plugin, generate pdf with html5 and jquery
- (转)jquery easyui treegrid使用小结 （主要讲的是如何编辑easyui中的行信息包括添加 下拉列表等）
- NSDateFormatter 根据时间戳求出时间
- css中li、a、span行内强制不换行
- homework07
- C++必备知识
- poj 3308 (最大流)
- ReentrantLock 以及 AQS 实现原理
- vue-cli 脚手架目录结构说明
- S7-200以太网通信
- 带BOM头文件解析
- call apply bind 区别？
- Virtual DOM 和 diff 算法
- 028 -bash-4.1$ 出现故障的原理及解决办法？
- 20165211 预备作业3 Linux安装与学习
- ajax发送post请求遇到的坑
- Javascript执行效率总结
- mysql pdo事务
- 在lua中正确使用uuid的方法：
- 关于使用java开发Mis系统的相关内容。