@Dmaxiya
2018-08-17T10:24:43.000000Z
字数 6999
阅读 1092
Codeforces
Contests 链接:Educational Codeforces Round 24
过题数:2
排名:902/5771
总共有 个学生,有一部分学生获得了 ,有另一部分学生获得了 ,而其他学生什么都没有获得,其中获得 与 的学生称为 ,问在保证 人数不超过 且 的条件下,获得使 最大的情况。
输入包含两个整数 。
分别输出获得 、 和什么都没获得的人数。
输入 | 输出 |
---|---|
18 2 | 3 6 9 |
9 10 | 0 0 9 |
1000000000000 5 | 83333333333 416666666665 500000000002 |
1000000000000 499999999999 | 1 499999999999 500000000000 |
只要确定获得 的人数就可以确定另外两个人数,。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#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
LL n, k, ans;
int main() {
#ifdef Dmaxiya
freopen("test.txt", "r", stdin);
#endif // Dmaxiya
ios::sync_with_stdio(false);
while(scanf("%I64d%I64d", &n, &k) != EOF) {
ans = n / 2 / (k + 1);
printf("%I64d %I64d %I64d\n", ans, ans * k, n - ans * (k + 1));
}
return 0;
}
构造一个 的排列 ,使得对于一个长度为 的序列 ,当 时,总是满足 ,当 大于 时,将结果减去 。
第一行为两个整数 ,第二行为 个整数 。
如果无法构造出满足条件的序列,则输出 ,否则输出 个整数,如果有多解输出任意一组解。
输入 | 输出 | 提示 |
---|---|---|
4 5 2 3 1 4 4 |
3 1 2 4 | 从 开始: |
3 3 3 1 2 |
-1 |
首先根据 先生成一个 序列,先计算这个序列中每个数字出现的次数,如果某个数字出现的次数大于 ,则这个序列是非法的,接着将这个序列中没有被用到的数据放进去,使得 序列成为一个 的排列,最后再扫一遍 序列,判断是否对于每个 都满足题给条件。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#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 = 100 + 100;
int n, m;
int num[maxn], ans[maxn], cnt[maxn];
int main() {
#ifdef Dmaxiya
freopen("test.txt", "r", stdin);
#endif // Dmaxiya
ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &m) != EOF) {
memset(cnt, 0, sizeof(cnt));
memset(ans, 0, sizeof(ans));
for(int i = 1; i <= m; ++i) {
scanf("%d", &num[i]);
}
for(int i = 1; i < m; ++i) {
int tmp = num[i + 1] - num[i];
tmp = (tmp % n + n) % n;
if(tmp == 0) {
tmp = n;
}
ans[num[i]] = tmp;
}
bool flag = true;
for(int i = 1; i <= n; ++i) {
if(ans[i] == 0) {
continue;
}
++cnt[ans[i]];
if(cnt[ans[i]] == 2) {
flag =false;
break;
}
}
if(!flag) {
printf("-1\n");
continue;
}
for(int i = 1; i <= n; ++i) {
if(ans[i] == 0) {
for(int j = 1; j <= n; ++j) {
if(cnt[j] == 0) {
++cnt[j];
ans[i] = j;
break;
}
}
}
}
for(int i = 1; i < m; ++i) {
int tmp = num[i] + ans[num[i]];
tmp = (tmp % n + n) % n;
if(tmp == 0) {
tmp = n;
}
if(tmp != num[i + 1]) {
flag = false;
break;
}
}
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;
}
在一个 的仓库里,有 个沙发,每个沙发占两个相邻的位置,用两个坐标 表示,对于两个沙发 和 ,如果存在 ,则表示 沙发在 沙发的左边,如果存在 ,则表示 沙发在 沙发的右边,如果存在 ,则表示 沙发在 沙发的上面,如果存在 ,则表示 沙发在 沙发的下面,其中 分别属于沙发 与沙发 的其中一个横坐标或纵坐标。注意对于两个沙发, 可能既在 的左边也在 的右边。
现在给出某个沙发的左边、右边、上面、下面各有多少个沙发,找出满足条件的沙发。
第一行包含一个整数 ,第二行为两个整数 ,接下去 行,每行四个整数 ,表示每个沙发的坐标,数据保证任意两个坐标都不会相同,且对同一个沙发的坐标描述一定是相邻的。最后一行为四个整数 ,表示要找的沙发需要符合的四个方向的沙发数量。数据保证最多只有一个沙发符合条件。
如果不存在满足条件的沙发,就输出 ,否则输出满足条件的沙发编号,沙发编号按照输入顺序从 到 编号。
输入 | 输出 | 提示 |
---|---|---|
2 3 2 3 1 3 2 1 2 2 2 1 0 0 1 |
1 | |
3 10 10 1 2 1 1 5 5 6 5 6 4 5 4 2 1 2 0 |
2 | · 第一个沙发的左边没有任何沙发,右边有两个沙发,上面没有沙发,下面有两个沙发; · 对于第二个沙发:; · 对于第三个沙发:; 因此第 个沙发满足给出的条件。 |
2 2 2 2 1 1 1 1 2 2 2 1 0 0 0 |
-1 | · 对于第一个沙发:; · 对于第二个沙发:; 没有沙发满足 。 |
假设第 个沙发的 ,由于上下左右四个方向的判定是类似的,因此这里只讨论左边的情况,可以推广到另外三个方向的情况:
由左边的判定方法可知:第 个沙发左边的沙发个数等于满足 的沙发个数(一个沙发只要有一个点满足条件,就能计入答案),我们可以通过对每个沙发的贡献做前缀和来 求出 。对于第 个沙发,它对所有满足 的沙发都有贡献,因此可以在 处标记一个 ,最后做一个前缀和即可查询到任意一个沙发左边的沙发个数。
对其他三个方向也做同样的判断。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#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 = 100000 + 100;
int d, n, m, ans;
int node[maxn][4], cnt[4];
int Sum[4][maxn], Ends[4][2], dx[4];
int main() {
#ifdef Dmaxiya
freopen("test.txt", "r", stdin);
#endif // Dmaxiya
ios::sync_with_stdio(false);
while(scanf("%d", &d) != EOF) {
ans = -1;
memset(Sum, 0, sizeof(Sum));
scanf("%d%d", &n, &m);
dx[0] = dx[2] = 1;
dx[1] = dx[3] = -1;
Ends[0][1] = n + 1;
Ends[1][0] = n - 1;
Ends[2][1] = m + 1;
Ends[3][0] = m - 1;
Ends[1][1] = Ends[3][1] = 0;
Ends[0][0] = Ends[2][0] = 2;
for(int i = 1; i <= d; ++i) {
for(int j = 0; j < 4; ++j) {
scanf("%d", &node[i][j]);
}
swap(node[i][1], node[i][2]);
if(node[i][0] < node[i][1]) {
swap(node[i][0], node[i][1]);
}
if(node[i][2] < node[i][3]) {
swap(node[i][2], node[i][3]);
}
++Sum[0][node[i][1] + 1];
++Sum[1][node[i][0] - 1];
++Sum[2][node[i][3] + 1];
++Sum[3][node[i][2] - 1];
}
for(int i = 0; i < 4; ++i) {
for(int j = Ends[i][0]; j != Ends[i][1]; j += dx[i]) {
Sum[i][j] += Sum[i][j - dx[i]];
}
}
for(int i = 0; i < 4; ++i) {
scanf("%d", &cnt[i]);
}
for(int i = 1; i <= d; ++i) {
bool flag = true;
for(int j = 0; j < 4; ++j) {
int tmp = Sum[j][node[i][j]];
if(node[i][j] != node[i][j ^ 1]) {
--tmp;
}
if(tmp != cnt[j]) {
flag = false;
break;
}
}
if(flag) {
ans = i;
break;
}
}
printf("%d\n", ans);
}
return 0;
}
和 两个人在车里可以看到窗外一辆辆行驶过的车,每辆车都有一个颜色 , 和 最开始分别选一种颜色 和 ,每经过一辆车,就统计到目前为止颜色为 的车的数量 和颜色为 的车的数量 ,对于经过的每一辆车:
- 如果 ,则 获胜;
- 如果 ,则 获胜;
- 否则两人平局。
知道将要经过的每一辆车的颜色,现在 已经选择了一种颜色 ,问 应该选择什么颜色才能获胜?
第一行包含两个整数 ,第二行包含 个整数 。
如果 可以获胜,则输出他应该选择的颜色 ,否则输出 。数据保证如果 可以获胜,那么在 内一定存在一种颜色可以使 获胜,如果有多解输出任意一组。
输入 | 输出 |
---|---|
4 1 2 1 4 2 |
2 |
5 2 2 2 4 5 3 |
-1 |
3 10 1 2 3 |
4 |
首先将所有颜色都作为可能的答案,每出现一种颜色,就将这种颜色的出现次数 ,接着将所有出现次数小于 的数字删除,最后剩下来的的颜色就是答案,如果最后没有数字留下,则输出 。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#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 = 1000000 + 100;
struct Node {
int cnt, num;
Node() {}
Node(int c, int n) {
cnt = c;
num = n;
}
};
bool operator<(const Node &a, const Node &b) {
return (a.cnt == b.cnt? a.num < b.num: a.cnt > b.cnt);
}
int n, A, c;
bool vis[maxn];
int cnt[maxn];
set<Node> st;
set<Node>::iterator it;
vector<set<Node>::iterator> vct;
int main() {
#ifdef Dmaxiya
freopen("test.txt", "r", stdin);
#endif // Dmaxiya
ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &A) != EOF) {
st.clear();
memset(cnt, 0, sizeof(cnt));
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= 1000000; ++i) {
st.insert(Node(0, i));
}
for(int i = 0; i < n; ++i) {
scanf("%d", &c);
if(vis[c]) {
continue;
}
it = st.find(Node(cnt[c], c));
st.erase(it);
++cnt[c];
st.insert(Node(cnt[c], c));
it = st.upper_bound(Node(cnt[A] - 1, 0));
vct.clear();
for(; it != st.end(); ++it) {
vct.push_back(it);
}
int len = vct.size();
for(int i = 0; i < len; ++i) {
vis[vct[i]->num] = true;
st.erase(vct[i]);
}
}
st.erase(Node(cnt[A], A));
if(st.empty()) {
printf("-1\n");
continue;
}
it = st.begin();
printf("%d\n", it->num);
}
return 0;
}