codechef September Challenge 2018 Division 2 A-F
程序员文章站
2022-05-04 13:52:08
比赛链接 上紫啦hhh，好开心 每个题里面都有中文翻译，我就不说题意了。。 A 直接模拟即可 #include #include #define int long long using namespace std; const int MAXN = 1e5 + ......
比赛链接
上紫啦hhh，好开心
每个题里面都有中文翻译，我就不说题意了。。
a
直接模拟即可
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int t;
int a[maxn], pos, q, n;
main() {
t = read();
while(t--) {
n = read(); pos = read(); q = read();
for(int i = 1; i <= n; i++) a[i] = i;
while(q--) {
int x = read(), y = read();
swap(a[x], a[y]);
}
for(int i = 1; i <= n; i++)
if(pos == a[i]) {
printf("%d\n", i); break;
}
}
}
b
这题我交了五遍没过,捂脸，然而并不知道自己哪里错了
跟lyq说了说还被婊了一顿。。。。最后换了个写法a了。。
直接大力特判就行，至于哪个share什么玩意儿就让n-1，m-1，然后判是否可行
#include<cstdio>
using namespace std;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int n, m, x, y;
int pd(int n, int m) {
/*if(n == 0 && m == 0) return 1;
else if((n < x) || (m < y)) return 0;
else if(n % x == 0 && m % y == 0) return 1;
else return 0;*/
if(n < 0 || m < 0) return 0;
return n % x == 0 && m % y == 0;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
n = read(), m = read(), x = read(), y = read();
n--; m--;
if(pd(n, m)) {puts("chefirnemo"); continue;}
n--; m--;
if(pd(n, m)) {puts("chefirnemo"); continue;}
puts("pofik");
}
return 0;
}
c
这题就有点厉害了！
结论：哥德巴赫猜想在信息学奥赛的范围内是成立的！
也就是说，任意一个$>=4$的偶数都是合法的。
然后把奇数和$0$判掉，维护出$0, 1$的个数即可
#include<cstdio>
#define ll long long
using namespace std;
const int maxn = 1e6 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int t;
int n;
int a[maxn];
ll tim[maxn];
ll calc(ll x) {
return x * (x - 1) / 2;
}
int main() {
// printf("%d", 2 ^ 4);
t = read();
while(t--) {
n = read();
for(int i = 1; i <= n;i ++) a[i] = read(), tim[a[i]]++;
ll ans = 0, ze = 0, on = 0;
/*for(int i = 1; i <= n; i++) {
for(int j = i + 1; j <= n; j++) {
int x = (a[i] ^ a[j]);
if((!(x & 1)) && (x != 2) && (x != 0)) ans++;
}
}*/
for(int i = 1; i <= n; i++)
if(a[i] & 1) on++;
else ze++;
ans = calc(ze) + calc(on);
//printf("%d\n", ans);
ll a1 = 0;
for(int i = 1; i <= n; i++)
a1 += tim[a[i] ^ 2];
ans -= a1 / 2;
for(int i = 1; i <= n; i++) {
ans -= (tim[a[i]] * (tim[a[i]] - 1)) / 2, tim[a[i]] = 0;
}
printf("%lld\n", ans);
}
return 0;
}
d
爆搜打出前$8$的表，不难找到规律：
最小的一定是$n, 1, 2, 3, \dots n - 1$
最大的是：$2, 3, 4, 5, n / 2, 1, 2 + n / 2, 3 + n / 2, 4 + n /2 ...$
奇数的话还要特殊考虑一下倒数第二位
#include<cstdio>
#include<map>
#include<iostream>
#define ull unsigned long long
#define ll long long
using namespace std;
const int maxn = 1e6 + 10, inf = 1e9 + 7;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int n;
int ans[maxn], num;
int main() {
// freopen("a.out", "w", stdout);
n = read();
for(int i = 2; i <= n / 2; i++) ans[++num] = i;
ans[++num] = 1;
for(int i = 2; i <= n / 2; i++) ans[++num] = n / 2 + i;
ans[++num] = 1 + n / 2;
for(int i = 1; i <= num - 1; i++)
printf("%d ", ans[i]);
if(n & 1) printf("%d ", n);
printf("%d\n", ans[num]);
printf("%d ", n);
for(int i = 1; i <= n - 1; i++)
printf("%d ",i);
return 0;
}
e
首先考虑暴力怎么打，我们把给出的初始行列的01取反，这样$0$的时候对应的是必胜态，$1$对应的是必败态。
然后按博弈论的定义推，$(i, j)$若是必胜态，那么至少有$(i - 1, j)$是必败态 或者 $(i, j - 1)$是必败态。
然后暴力枚举一遍就行了，复杂度$o(nm)$
接下来的操作就比较神仙了，，打表 或 直接观察式子可得，若第$(i, j)$个点是必败点，那么它所在的对角线往后的点，都是必败点！
这样我们就把状态降到了$2 * m$
那最开始的必败点怎么求呢？
直觉告诉我们 稍加证明不难得到，这种点一定是出现在前两行 或者前两列。
然后就做完了。
暴力推前两行 前两列即可。
保险起见我推了三行三列。
#include<cstdio>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
inline ll read() {
char c = getchar(); ll x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int t;
int a[4][maxn], b[maxn][4], n, m, f[maxn], g[maxn];
char a[maxn], b[maxn];
int main() {
//- freopen("a.out", "w", stdout);
int t = read();
while(t--) {
scanf("%s", a + 1);
scanf("%s", b + 1);
m = strlen(a + 1);
n = strlen(b + 1);
for(int i = 1; i <= m; i++) a[0][i] = (a[i] == '1' ? 0 : 1);
for(int i = 1; i <= 3; i++) a[i][0] = (b[i] == '1' ? 0 : 1);
for(int i = 1; i <= 3; i++) b[0][i] = (a[i] == '1' ? 0 : 1);
for(int i = 1; i <= n; i++) b[i][0] = (b[i] == '1' ? 0 : 1);
memset(f, 0x7f, sizeof(f));
memset(g, 0x7f, sizeof(g));
for(int i = 1; i <= 3; i++) {
for(int j = 1; j <= m; j++) {
if(a[i - 1][j] == 1 || a[i][j - 1] == 1) a[i][j] = 0;//能到达必败节点的
else a[i][j] = 1;
if(a[i][j] == 1) f[j - i + 1] = min(f[j - i + 1], i);
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 3; j++) {
if(b[i - 1][j] == 1 || b[i][j - 1] == 1) b[i][j] = 0;
else b[i][j] = 1;
if(b[i][j] == 1) g[i - j + 1] = min(g[i - j + 1], j);
}
}
vector<int> ans;
int q = read();
while(q--) {
int x = read(), y = read();
int dy = y - x + 1,
dx = x - y + 1;
if(dy >= 1) {
if(x >= f[dy]) ans.push_back(0);
else ans.push_back(1);
} else {
if(y >= g[dx]) ans.push_back(0);
else ans.push_back(1);
}
}
for(int i = 0; i < ans.size(); i++) printf("%d", ans[i]);
puts("");
}
return 0;
}
f
这个题我就不说啥了，challenge题嘛，xjb乱搞。
但是！！！
我tm辛辛苦苦写了半天的贪心324分？？
直接输出$1$有400+？？？？？？？？？？？？