Codeforces Round #641 (Div. 2)
A.Orac and Factors
题意:
为的第二小因数,询问执行次 后的结果
题解:
如果为偶数接下来的数全为偶数,因此即可。如果为奇数就去找第二小因数,一直找次或者为奇数即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 8e3 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { ll n, k; scanf("%lld%lld", &n, &k); while (k) { if (n % 2 == 0) break; for (ll i = 2; i <= n; i++) if (n % i == 0) { n += i; break; } k--; } n = n + k * 2; printf("%lld\n", n); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
B.Orac and Models
题意:
给定一个序列,找出一个最长的子串满足,其中为字串中第个元素在原序列中的下标,输出最长字串的长度
题解:
计算出每个数当因子的长度,用维护,最后取最大值即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int a[maxn], dp[maxn]; void solve() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]), dp[i] = 1; for (int i = 1; i <= n; i++) { for (int j = 2; j * i <= n; j++) if (a[i * j] > a[i]) dp[i * j] = max(dp[i * j], dp[i] + 1); } int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, dp[i]); printf("%d\n", ans); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
C.Orac and LCM
题意:
给定一个序列,求出,即所有的
题解:
根据两个整数的最大公因子和最小公倍数中的分配律:。可以求得。
gcd百度百科
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 998244353; ll a[maxn], t[maxn]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); t[n] = 0; for (int i = n - 1; i >= 1; i--) t[i] = __gcd(t[i + 1], a[i + 1]); ll ans = 0; for (int i = 1; i <= n; i++) ans = __gcd(ans, a[i] * t[i] / __gcd(a[i], t[i])); printf("%lld\n", ans); return 0; }
D.Orac and Medians
题意:
给定一个序列和,每次操作可以选择一段区间,将均变为,询问最终能否使得整个序列都变为
题解:
首先判断区间内是否有存在一个,再判断是否存在一段长度的区间满足其中存在两个数。当存在两个数时,只需要每次取三个数组成的连续区间就能将区间的所有值变为;当存在两个数时,可以将三个数组成的连续区间变为全,那么只需要在区间中留一个,其他的全部变为,那么每次取和一个的值,就能将的数变为
特判只有一个数的情况。
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; ll a[maxn]; void solve() { int n, k; scanf("%d%d", &n, &k); int f1 = 0, f2 = 0; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] == k) f1 = 1; } int last = -10; for (int i = 0; i < n; i++) { if (a[i] >= k) { if (i - last <= 2) f2 = 1; last = i; } } if (f1 && (f2 || n == 1)) puts("yes"); else puts("no"); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
E.Orac and Game of Life
题意:
给定一个的棋盘,棋盘一开始有两种颜色:白色(0)和黑色(1)。
有一种操作,每次操作:
- 若该格子有相邻格子的颜色与之相同,则颜色翻转
- 若该格子没有相邻格子的颜色与之相同,则颜色不变
有次询问,每次询问都有, , ,询问第行第列格子经过次操作后的颜色
题解:
先判断哪些格子一开始就会翻转,在通过这些点向四周一开始不会翻转的格子辐射。所以最终只要判断辐射到那个节点所需要的时间是否,如果是再判断是否需要翻转即可。本质是道多源bfs
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e3 + 5; const int INF = 0x3f3f3f3f; const int mod = 998244353; char c[maxn][maxn]; int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; ll vis[maxn][maxn]; struct node { int x, y; ll d; }; bool check(int x, int y) { for (int i = 0; i < 4; i++) if (c[x][y] == c[x + dir[i][0]][y + dir[i][1]]) return true; return false; } int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int n, m, t; cin >> n >> m >> t; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> c[i][j], vis[i][j] = -1; queue<node> q; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (check(i, j)) q.push({i, j, 0ll}), vis[i][j] = 0; while (!q.empty()) { node u = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int x = u.x + dir[i][0], y = u.y + dir[i][1]; if (x >= 1 && y >= 1 && x <= n && y <= m && vis[x][y] == -1) { q.push(node{x, y, u.d + 1ll}); vis[x][y] = u.d + 1ll; } } } while (t--) { ll i,j,p; cin >> i >> j >> p; ll ans = (c[i][j] - '0'); if (vis[i][j] >= 0 && p > vis[i][j] && (p - vis[i][j]) & 1) ans ^= 1; cout << ans << "\n"; } return 0; }