@Dmaxiya
2019-01-16T16:47:11.000000Z
字数 7550
阅读 1166
Codeforces
Contests 链接:Educational Codeforces Round 58
过题数:4
排名:985/6146
输出不在范围 内的最小的正整数 ,要求 是 的整数倍。
第一行为一个整数 ,接下去有 行,第 行的三个整数分别为 。
对于每一行询问,输出对应的答案。
输入 |
---|
5 2 4 2 5 10 4 3 10 1 1 2 3 4 6 5 |
输出 |
6 4 1 3 10 |
若 在 范围内,则输出 ,否则输出 。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
int T;
int l, r, x;
int main() {
#ifdef Dmaxiya
freopen("test.txt", "r", stdin);
#endif // Dmaxiya
ios::sync_with_stdio(false);
scanf("%d", &T);
while(T--) {
scanf("%d%d%d", &l, &r, &x);
if(x >= l && x <= r) {
printf("%d\n", r / x * x + x);
} else {
printf("%d\n", x);
}
}
return 0;
}
用一个字符串来表示一个手风琴,其必须要满足的格式为:由
[
开头,接着是一个:
,往后是连续的多个或零个|
,接着是一个:
和]
。给定一个字符串,问能否通过删除一些字符,使得最终剩下的字符串可以表示成一个手风琴,若能,求最长剩余字符串长度。
输入仅包含一个字符串 ,其中只包含小写字母以及
[
、]
、:
、|
这几种符号。
如果无法满足题意,则输出 ,否则输出能表示成手风琴的最长的字符串。
输入 |
---|
|[a:b:|] |
输出 |
4 |
输入 |
---|
|]:[|:] |
输出 |
-1 |
先找出最左边的
[
下标 以及最右边的]
的下标 ,要求 ,接着找在[l,r]
范围内最左边的:
以及最右边的:
,最后将这两个冒号间所有的|
个数统计出来,答案就是|
的个数 。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 500000 + 100;
int len;
char str[maxn];
int main() {
#ifdef Dmaxiya
freopen("test.txt", "r", stdin);
#endif // Dmaxiya
ios::sync_with_stdio(false);
while(scanf("%s", str + 1) != EOF) {
len = strlen(str + 1);
int l = -1;
int r = -1;
for(int i = 1; i <= len; ++i) {
if(str[i] == '[') {
l = i;
break;
}
}
for(int i = len; i >= 1; --i) {
if(str[i] == ']') {
r = i;
break;
}
}
if(l == -1 || r == -1 || r <= l) {
printf("-1\n");
continue;
}
int ll = -1;
int rr = -1;
for(int i = l + 1; i < r; ++i) {
if(str[i] == ':') {
if(ll == -1) {
ll = i;
}
rr = i;
}
}
if(ll == -1 || rr == -1 || ll >= rr) {
printf("-1\n");
continue;
}
int ans = 4;
for(int i = ll + 1; i < rr; ++i) {
if(str[i] == '|') {
++ans;
}
}
printf("%d\n", ans);
}
return 0;
}
给定 条线段,第 条线段的两个端点分别为 ,将这 条线段分别放入两个非空集合中,要求从这两个集合中分别任意取一条线段出来,这两条线段没有任何公共部分。
第一行为一个整数 ,接下去有 组数据,每组数据第一行为一个整数 ,数据保证所有数据的 的总和不超过 ,接下去 行每行两个整数 。
对于每组数据输出一行,若某组数据无解,则输出 ,否则输出 个整数 , 表示第 条线段被分到第 个集合中, 表示第 条线段被分到第 个集合中,若有多解则输出任意一个。
输入 |
---|
3 2 5 5 2 3 3 3 5 2 3 2 3 3 3 3 4 4 5 5 |
输出 |
2 1 -1 1 1 2 |
提示 |
在第一组数据中,两条线段应被放到不同的集合中,但答案并不一定必须是 2 1,也可以是 1 2。 在第二组数据中,第三条线段与前两条线段相交,因此它们应该被分在同一个集合中,这样另一个集合就会为空,不满足题意,因此答案为 。 在第三组数据中,我们可以以任意方式将三条线段分配到两个不同的集合中,只要这两个集合非空就是合法的,因此总共有 种合法的答案。 |
将每条线段的两个端点拆开,左区间 标为 ,右区间 标为 ,以端点大小为主关键字从小到大、以下标为此关键词从小到大排序,最后对整个数组扫一遍,遇到左端点则放入集合中,遇到右端点则从集合中删除,最后用并查集维护相互覆盖的线段,只要存在至少两个连通块,就存在答案,将其中一个连通块中的线段放到集合 中,其他的连通块放入集合 中。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
struct Node {
int Index, x;
};
bool operator<(const Node &a, const Node &b) {
return a.x == b.x? a.Index < b.Index: a.x < b.x;
}
int T, n, l, r;
Node node[maxn << 1];
set<int> st;
int fa[maxn], ans[maxn];
void Init() {
for(int i = 1; i <= n; ++i) {
fa[i] = i;
}
}
int Find(int x) {
return x == fa[x]? x: fa[x] = Find(fa[x]);
}
void unit(int x, int y) {
int xx = Find(x);
int yy = Find(y);
fa[xx] = yy;
}
int main() {
#ifdef Dmaxiya
freopen("test.txt", "r", stdin);
#endif // Dmaxiya
ios::sync_with_stdio(false);
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
st.clear();
Init();
for(int i = 1; i <= n; ++i) {
scanf("%d%d", &l, &r);
node[i].Index = i;
node[i].x = l;
node[i + n].Index = -i;
node[i + n].x = r + 1;
}
sort(node + 1, node + 1 + 2 * n);
for(int i = 1; i <= 2 * n; ) {
while(i <= 2 * n && node[i].Index < 0) {
st.erase(-node[i].Index);
++i;
}
if(i == 2 * n + 1) {
break;
}
int f;
if(st.empty()) {
f = node[i].Index;
} else {
f = *st.begin();
}
while(i <= 2 * n && node[i].Index > 0) {
st.insert(node[i].Index);
unit(node[i].Index, f);
++i;
}
}
bool flag = false;
int f = Find(1);
for(int i = 1; i <= n; ++i) {
if(Find(i) == f) {
ans[i] = 1;
} else {
flag = true;
ans[i] = 2;
}
}
if(!flag) {
printf("-1\n");
continue;
}
for(int i = 1; i <= n; ++i) {
if(i != 1) {
printf(" ");
}
printf("%d", ans[i]);
}
printf("\n");
}
return 0;
}
给定一棵 个节点的树,树上的每个点都有一个权值 ,定义 表示从节点 到节点 的路径上所有节点(包括 两点)权值的 ,定义 表示从节点 到节点 的路径上所有节点的数量,对于任意一个节点有 。求在 的 对中, 的最大值。
第一行为一个整数 ,第二行为 个整数 ,接下去 行每行两个整数 ,表示节点 与节点 之间有一条连边,数据保证所有的边可以构成一棵树。
如果不存在满足条件的答案,输出 ,否则输出满足条件的 的最大值。
输入 |
---|
3 2 3 4 1 2 2 3 |
输出 |
1 |
输入 |
---|
3 2 3 4 1 3 2 3 |
输出 |
2 |
输入 |
---|
3 1 1 1 1 2 2 3 |
输出 |
0 |
定义 表示以第 个节点为根,从其任意一个子节点往下的一条链,这条链上所有节点权值的 为 的倍数的最长长度,则可以得到 递推式:
其中 为节点 的所有子节点, 为 的所有质因子,答案为:
其中 表示序列中的次大值。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
int n, ans, u, v;
int num[maxn];
vector<int> G[maxn];
vector<int> fac[maxn];
map<int, int> dp[maxn];
map<int, int>::iterator it;
int cnt;
int prime[maxn];
bool vis[maxn];
void Prime(int n) {
for(int i = 2; i <= n; ++i) {
if(!vis[i]) {
prime[cnt++] = i;
}
for(int j = 0; j < cnt && i <= n / prime[j]; ++j) {
int k = i * prime[j];
vis[k] = true;
if(i % prime[j] == 0) {
break;
}
}
}
}
void dfs(int f, int x) {
int len = G[x].size();
for(int i = 0; i < len; ++i) {
int pos = G[x][i];
if(pos == f) {
continue;
}
dfs(x, pos);
}
len = fac[num[x]].size();
for(int i = 0; i < len; ++i) {
int ffac = fac[num[x]][i];
int MMax = 0;
int Max = 0;
int llen = G[x].size();
for(int j = 0; j < llen; ++j) {
int pos = G[x][j];
if(pos == f) {
continue;
}
it = dp[pos].find(ffac);
if(it == dp[pos].end()) {
continue;
}
if(it->second >= Max) {
MMax = Max;
Max = it->second;
} else if(it->second > MMax) {
MMax = it->second;
}
}
ans = max(ans, 1 + Max + MMax);
dp[x][ffac] = 1 + Max;
}
}
int main() {
#ifdef Dmaxiya
freopen("test.txt", "r", stdin);
#endif // Dmaxiya
ios::sync_with_stdio(false);
Prime(maxn - 1);
for(int i = 0; i < cnt; ++i) {
for(int j = prime[i]; j < maxn; j += prime[i]) {
fac[j].push_back(prime[i]);
}
}
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &num[i]);
}
for(int i = 1; i < n; ++i) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 1);
printf("%d\n", ans);
return 0;
}
给定两种操作:
- 从一个初始为空的集合中加入一张大小为 的票据;
- 询问大小为 的钱包是否能装下所有票据。
对于所有已经被加入集合的票据,满足以下任意一个条件,则钱包能够装下所有票据:
- 且 ;
- 且 。
对于每次询问,输出钱包是否能够装下集合中所有的票据。
第一行包含一个整数 ,接下去有 次操作,每次操作格式为以下两个之一:
- ,表示加入一张大小为 的票据;
- ,询问大小为 的钱包能否放下集合中的所有票据。
数据保证在第一个询问 之前至少存在一个询问 ,并且至少存在一个询问 。
对于每次询问,输出 或 ,表示答案。
输入 |
---|
9 + 3 2 + 2 3 ? 1 20 ? 3 3 ? 2 3 + 1 5 ? 10 10 ? 1 5 + 1 1 |
输出 |
NO YES YES YES NO |
对于每次放入的票据,每次取短边的最大值和长边的最大值,对于每次询问,只要短边的最大值小于等于钱包的短边,长边的最大值小于等于钱包的长边即可。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
int n, l, r, maxl, maxr;
char ch[2];
int main() {
#ifdef Dmaxiya
freopen("test.txt", "r", stdin);
#endif // Dmaxiya
ios::sync_with_stdio(false);
while(scanf("%d", &n) != EOF) {
maxl = 0;
maxr = 0;
for(int i = 0; i < n; ++i) {
scanf("%s%d%d", ch, &l, &r);
if(l > r) {
swap(l, r);
}
if(ch[0] == '+') {
maxl = max(maxl, l);
maxr = max(maxr, r);
} else {
if(l >= maxl && r >= maxr) {
printf("YES\n");
} else {
printf("NO\n");
}
}
}
}
return 0;
}