@Dmaxiya
2018-08-17T10:18:52.000000Z
字数 5331
阅读 1076
Codeforces
Contests 链接:Educational Codeforces Round 37
过题数:3
排名:763/9623
有 个花圃排成一排,从 到 编号,有 个喷头放在这 个花圃中的 处,这个喷头开启后第 秒会将 处的花圃淋湿,第 秒会将区间 内的所有花圃淋湿,且只有整数秒时才会淋湿一个花圃,问所有喷头同时开启,最少多少秒可以将所有花圃淋湿。
第一行为一个整数 ,接下来有 组数据,每组数据的第一行为两个整数 ,第二行有 个整数 ,表示第 个喷头的位置为 。
输出最少让所有花圃淋湿的时间。
输入 | 输出 | 提示 |
---|---|---|
3 5 1 3 3 3 1 2 3 4 1 1 |
3 1 4 |
1.在第一组数据中,第 秒的时候第 个花圃会被淋湿,第 秒的时候区间 内的花圃会 被淋湿,第 秒的时候所有的花圃都会被淋湿; 2.在第二组数据中,每一个花圃上都有一个喷头,因此在第 秒的时候所有的花圃就都会被淋湿; 3.在第三组数据中,只有第 个花圃有喷头,所以需要 秒时间将所有花圃淋湿。 |
计算所有相邻喷头中间位置的花圃被淋到的时间,以及边缘的花圃会被淋到的时间,取最大值。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 200 + 100;
int T, n, k, ans;
int num[maxn];
int main() {
#ifdef Dmaxiya
freopen("test.txt", "r", stdin);
#endif // Dmaxiya
ios::sync_with_stdio(false);
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &k);
ans = 0;
for(int i = 1; i <= k; ++i) {
scanf("%d", &num[i]);
}
for(int i = 2; i <= k; ++i) {
ans = max(ans, (num[i] - num[i - 1]) / 2 + 1);
}
ans = max(ans, num[1]);
ans = max(ans, n - num[k] + 1);
printf("%d\n", ans);
}
return 0;
}
有 个学生,第 个学生将会在第 秒来等待接茶水,每个人接茶水消耗的时间为 ,如果两个学生同时到达,则编号小的同学排在队伍的前面,如果某个同学到达时前面有同学在等待,他也会排队等待,如果超过 秒仍然没有轮到他接茶水,他就会马上离开,求每个同学接到茶水的时间。
第一行为一个整数 ,接下去有 组数据,每组数据第一行为一个整数 ,接下去有 行,每一行有两个整数 ,对于所有的 ,都有 。且所有数据的 的和不超过 。
每一组数据输出一行 个整数,第 个整数代表第 个学生接到茶水的时间,如果某个学生没有接到茶水直接离开,则输出 。
输入 | 输出 | 提示 |
---|---|---|
2 2 1 3 1 4 3 1 5 1 1 2 3 |
1 2 1 0 2 |
1.对于第 组数据, 个学生同时到达,第 个学生在第 秒接到茶水, 第 个学生在第 秒接到茶水。 2.对于第 组数据,第 个和第 个学生同时到达,第 个学生在第 秒接到茶水,第 秒结束第二个学生没有接到茶水就离开了,第 秒时 第 个学生到达,并接到茶水。 |
按照题意模拟。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
int T, n, l, r;
int main() {
#ifdef Dmaxiya
freopen("test.txt", "r", stdin);
#endif // Dmaxiya
ios::sync_with_stdio(false);
scanf("%d", &T);
while(T--) {
int now = 0;
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d%d", &l, &r);
now = max(now, l);
if(i != 0) {
printf(" ");
}
if(now > r) {
printf("0");
} else {
printf("%d", now);
++now;
}
}
printf("\n");
}
return 0;
}
给定一个长度为 的序列,在这个序列中的某些位置 可以和第 个位置的数字进行交换,问能否通过任意次合法的交换,使得这个数列成为一个递增数列。
第一行为一个整数 ,第二行为 个整数 ,第三行为一个字符串 ,字符串的第 位为 表示序列中的第 个数字可以和第 个数字交换位置。
如果可以在给定的条件下,通过任意次交换得到一个递增的数列,则输出 ,否则输出 。
输入 | 输出 | 提示 |
---|---|---|
6 1 2 5 3 4 6 01110 |
YES | 可以通过交换 和 ,使数列成为一个递增的数列。 |
6 1 2 5 3 4 6 01010 |
NO |
能否通过交换使数列有序,即询问所有数字能否通过交换从排序前的下标移动到排序后的下标,即排序前后所有数字的下标都必须由 连通,就可以用并查集来判了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
int n;
int num[maxn], Index1[maxn], Index2[maxn];
int fa[maxn];
char str[maxn];
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);
while(scanf("%d", &n) != EOF) {
for(int i = 1; i <= n; ++i) {
scanf("%d", &num[i]);
fa[i] = i;
Index1[num[i]] = i;
}
sort(num + 1, num + 1 + n);
for(int i = 1; i <= n; ++i) {
Index2[num[i]] = i;
}
scanf("%s", str + 1);
for(int i = 1; i < n; ++i) {
if(str[i] == '1') {
unit(i, i + 1);
}
}
bool flag = true;
for(int i = 1; i <= n; ++i) {
if(Find(Index1[num[i]]) != Find(Index2[num[i]])) {
flag = false;
break;
}
}
if(flag) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}
一个 个节点的无向图的补图上有 条边,输出原图上所有连通块中节点的数量。
第一行为两个整数 ,接下去 行每行两个整数 ,表示原图上 与 之间没有连边。
第一行输出一个整数 ,表示连通块的个数,第二行按照非递减的顺序输出每个连通块内的节点数量。
输入 | 输出 |
---|---|
5 5 1 2 3 4 3 2 4 2 2 5 |
2 1 4 |
用一个 来存所有没有被访问过的节点,每访问一个节点就从 中删去,直到所有节点都被访问( 为空),就可以得到所有连通块的信息,用 判连通块。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
int n, m, u, v, cnt;
set<int> st;
set<int> G[maxn];
int ans[maxn];
queue<int> que;
set<int>::iterator it;
vector<set<int>::iterator> vct;
int bfs(int x) {
int ret = 1;
while(!que.empty()) {
que.pop();
}
que.push(x);
st.erase(x);
while(!que.empty()) {
if(st.empty()) {
return ret;
}
vct.clear();
int tmp = que.front();
que.pop();
for(it = st.begin(); it != st.end(); ++it) {
if(G[tmp].find(*it) == G[tmp].end()) {
que.push(*it);
vct.push_back(it);
++ret;
}
}
int len = vct.size();
for(int i = 0; i < len; ++i) {
st.erase(vct[i]);
}
}
return ret;
}
int main() {
#ifdef Dmaxiya
freopen("test.txt", "r", stdin);
#endif // Dmaxiya
ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &m) != EOF) {
cnt = 0;
st.clear();
for(int i = 1; i <= n; ++i) {
G[i].clear();
st.insert(i);
}
for(int i = 0; i < m; ++i) {
scanf("%d%d", &u, &v);
G[u].insert(v);
G[v].insert(u);
}
while(!st.empty()) {
ans[cnt++] = bfs(*(st.begin()));
}
sort(ans, ans + cnt);
printf("%d\n", cnt);
for(int i = 0; i < cnt; ++i) {
if(i != 0) {
printf(" ");
}
printf("%d", ans[i]);
}
printf("\n");
}
return 0;
}