@Dmaxiya
2018-08-17T10:28:48.000000Z
字数 5669
阅读 1177
Codeforces
Contests 链接:Codeforces Round #458 (Div. 1 + Div. 2)
过题数:2
排名:1691/8398
给定一个长度为 的序列 ,找到这个序列中最大的开方不是整数的数字。
按照题意跑一遍。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
int n;
LL tmp;
bool judge(LL x) {
if(x < 0) {
return true;
}
LL xx = sqrt(x);
if(xx * xx == x) {
return false;
}
return true;
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d", &n) != EOF) {
LL ans = INT_MIN;
for(int i = 0; i < n; ++i) {
scanf("%I64d", &tmp);
if(judge(tmp)) {
ans = max(ans, tmp);
}
}
printf("%I64d\n", ans);
}
return 0;
}
柯南和阿笠博士玩一场博弈游戏,给定 张卡片,每张卡片上的数字为 ,对于每次操作,一方可以选择一张卡片,然后将其他所有小于该数字的卡片拿掉,最后无法进行操作的一方失败。柯南先手,如果两人都采取最优策略,问谁会获胜。
如果最大的数字有 个,如果 为偶数,则先拿最大的数字的人必败,否则必胜,所以如果最大的数字有偶数个,则双方肯定尽量不先拿最大的数字,对于次大的数字也是如此,一直往小了找,如果某个数字出现的次数为奇数,则先拿到这个数字的一方必胜,所以先手一定会直接取这个个数为奇数的数字。所以只要存在个数为奇数的数字,先手必胜,否则必败。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
int n, tmp;
bool flag;
map<int, int> mp;
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d", &n) != EOF) {
mp.clear();
for(int i = 0; i < n; ++i) {
scanf("%d", &tmp);
++mp[tmp];
}
flag = false;
map<int, int>::iterator it;
for(it = mp.begin(); it != mp.end(); ++it) {
if(it->second % 2 == 1) {
flag = true;
break;
}
}
if(flag) {
printf("Conan\n");
} else {
printf("Agasa\n");
}
}
return 0;
}
定义一个操作,对于数字 ,进行一次操作后, 变为 对应的二进制数中,数字 的个数,例如, 进行一次操作后变为 ,再进行一次操作后变为 。现在,对于数字 ,询问从 到 中,最少进行 次操作后变为 的数字有多少个,输出对 后的答案, 以二进制形式给出。
对于 以内的数字,进行一次操作后,必然变成 以内的数字,所以可以先预处理出 以内的数字,至少进行多少次操作后变为 ,然后对 到 的数字,询问哪些数字最少可以经过 次操作变为 ,若数字 可以经过 次操作变为 ,则用数位 算出从 到 之间有多少个二进制中含有 个 的数字,加到答案上。注意特判 和 的情况。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
const int MOD = 1000000000 + 7;
char n[maxn];
int k, len, ans;
int step[maxn];
int dp[maxn][maxn][2];
int dfs(int pos, int r, int limit) {
if(r < 0) {
return 0;
}
if(pos == len) {
if(r == 0) {
return 1;
} else {
return 0;
}
}
if(!limit && dp[pos][r][limit] != -1) {
return dp[pos][r][limit];
}
int up = limit? (n[pos] - '0'): 1;
int ans = 0;
for(int i = 0; i <= up; ++i) {
if(i == 1) {
ans += dfs(pos + 1, r - 1, limit && i == n[pos] - '0');
ans %= MOD;
} else {
ans += dfs(pos + 1, r, limit && i == n[pos] - '0');
ans %= MOD;
}
}
if(!limit) {
dp[pos][r][limit] = ans;
}
return ans;
}
int get_one(int x) {
int ret = 0;
while(x != 0) {
if(x % 2 == 1) {
++ret;
}
x /= 2;
}
return ret;
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
// ios::sync_with_stdio(false);
step[1] = 0;
for(int i = 2; i < maxn; ++i) {
step[i] = step[get_one(i)] + 1;
}
while(scanf("%s%d", n, &k) != EOF) {
if(k == 0) {
printf("1\n");
continue;
}
ans = 0;
len = strlen(n);
memset(dp, -1, sizeof(dp));
for(int i = 1; i < maxn; ++i) {
if(step[i] == k - 1) {
ans += dfs(0, i, 1);
ans %= MOD;
// printf("dfs(%d) = %d\n", i, dfs(0, i, 1));
}
}
if(k == 1) {
--ans;
ans = (ans + MOD) % MOD;
}
printf("%d\n", ans);
}
return 0;
}
给定 个数字的序列 ,进行 次操作,每次操作有两种形式:
- 询问能否在区间 上最多修改一个数字,使得该区间上所有数字都是 的倍数;
- 将第 个数字修改为 。
对于每次询问,输出 或者 。
用线段树存区间 ,对于每次询问,判断区间 上不是 的倍数的数字是否多于一个,若多于 个,则不是。判断的时候注意剪枝,若左子节点已经有多于两个数字不是 的倍数,则不必判断右子节点。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 500000 + 100;
int n, q, command, l, r, x, Index, y;
int ans;
int Gcd[maxn << 2];
int gcd(int x, int y) {
if(y == 0) {
return x;
}
return gcd(y, x % y);
}
void push_up(int rt) {
Gcd[rt] = gcd(Gcd[rt << 1], Gcd[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
if(l == r) {
scanf("%d", &Gcd[rt]);
return ;
}
int m = (l + r) >> 1;
build(l, m, rt << 1);
build(m + 1, r, rt << 1 | 1);
push_up(rt);
}
void update(int Index, int tmp, int l, int r, int rt) {
if(l == r) {
Gcd[rt] = tmp;
return ;
}
int m = (l + r) >> 1;
if(Index <= m) {
update(Index, tmp, l, m, rt << 1);
} else {
update(Index, tmp, m + 1, r, rt << 1 | 1);
}
push_up(rt);
}
int query(int L, int R, int tmp, int l, int r, int rt) {
if(L <= l && r <= R) {
if(Gcd[rt] % tmp == 0) {
return 0;
}
}
if(l == r) {
return (Gcd[rt] % tmp != 0);
}
int m = (l + r) >> 1;
int ret = 0;
if(L <= m) {
ret += query(L, R, tmp, l, m, rt << 1);
}
if(ret >= 2) {
return 2;
}
if(R > m) {
ret += query(L, R, tmp, m + 1, r, rt << 1 | 1);
}
if(ret >= 2) {
ret = 2;
}
return ret;
}
void Print() {
for(int i = 1; i <= 10; ++i) {
printf("Gcd[%d] = %d\n", i, Gcd[i]);
}
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
// ios::sync_with_stdio(false);
while(scanf("%d", &n) != EOF) {
build(1, n, 1);
scanf("%d", &q);
for(int i = 0; i < q; ++i) {
scanf("%d", &command);
if(command == 1) {
scanf("%d%d%d", &l, &r, &x);
// printf("l = %d r = %d x = %d\n", l, r, x);
ans = query(l, r, x, 1, n, 1);
// printf("ans = %d\n", ans);
if(ans <= 1) {
printf("YES\n");
} else {
printf("NO\n");
}
} else {
scanf("%d%d", &Index, &y);
update(Index, y, 1, n, 1);
// Print();
}
}
}
return 0;
}