比赛链接:AtCoder Beginner Contest 254 - AtCoder
各题题目请看原题链接。
A - Last Two Digits
代码 / Code
//Copyright (C) Eriktse 2022 #include <bits/stdc++.h> #define int long long using namespace std; signed main() { int n;cin >> n; printf("%02lld\n", n % 100); return 0; }
B - Practical Computing
代码 / Code
//Copyright (C) Eriktse 2022 #include <bits/stdc++.h> #define int long long using namespace std; int a[50]; signed main() { int N;cin >> N; a[1] = 1; for(int i = 1; i <= N; ++ i) { for(int j = i;j >= 1; -- j)a[j] = a[j] + a[j - 1]; for(int j = 1;j <= i; ++ j)printf("%lld ",a[j]); puts(""); } return 0; }
C - K Swap
因为每次只能交换间隔为K的,其实就可以将整个数组分为K个类(组),每个类都是“对K取模相等”的。
比如N = 7,K = 3,那么0 3 6为一组,1 4为一组,2 5为一组。
每一组中,可以按照任意顺序排列,因为可以任意交换位置。
用一点贪心的想法,为了使得整个序列不降序,那么也就是每一组都要不降序,如果当每一组都不降的时候,序列也不降,那么就可以被排列,反之则不行。
可以使用优先队列来维护每一组的最小值,当然你进行K次排序也可以,时间复杂度都一样。
//Copyright (C) Eriktse 2022 #include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 2e5 + 9; int a[maxn]; priority_queue<int, vector<int>, greater<int> > pq[maxn]; bool isok(int K,int N) { for(int i = 0, last = 0;i < N; ++ i) { int x = pq[i % K].top();pq[i % K].pop(); if(x < last)return 0; last = x; } return 1; } signed main() { int N, K;scanf("%lld %lld", &N, &K); for(int i = 0;i < N; ++ i) { int x;scanf("%lld", &x); pq[i % K].push(x); } printf("%s\n", isok(K, N) ? "Yes" : "No"); return 0; }
D - Together Square
这道题卡了我好久。
在做题之前我们需要有个前置知识,假如L * R = 一个平方数,那么对L和R分别质因数分解,其中相同的质因数个数之和应该为偶数。借此,我们可以枚举L,算出最小的R,再算一下能把多少个平方数乘到R里面去,就有多少种方案。
因为一开始L和算出的R保证了相同质因数个数之和为偶数,那么再往R里面乘上平方数,也就是偶数个质因子,可以保证新产生的数字也是平方数,为了保证L,R<=N,所以乘上的平方数是有限的,可以用二分或者直接数学算出来。
代码 / Code
//Copyright (C) Eriktse 2022 #include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 9; vector<int> v;//存放素数 void initPrimes(int N) {//求N以内所有素数 bitset<maxn> pri; pri[0] = pri[1] = 1; for(int i = 1;i <= N / i; ++ i) if(!pri[i])for(int j = i * i;j <= N; j += i)pri[j] = 1; for(int i = 1;i <= N; ++ i)if(!pri[i])v.push_back(i); } void solve(int N) { initPrimes(N); int ans = 0; for(int L = 1;L <= N; ++ L) { int R = 1, tmp = L; for(auto &i : v) { if(i * i > tmp)break; int cnt = 0; while(tmp % i == 0)tmp /= i, cnt ^= 1; if(cnt & 1)R *= i; } R *= tmp; ans += (int)sqrt(N * 1.0/ R); } cout << ans << '\n'; } signed main() { int N;cin >> N; solve(N); return 0; }
E - Small d and k
感觉这题比D简单,就是单纯地dfs,但是注意判重不能直接认为“走过的点就不走了”,因为可能出现环,然后导致走过的点后面可能还有可以走的点。
所以判重的规则是res = vis[x] ? 0 : x;
只是走过的点不再计算贡献,但是依然要往下拓展。
代码 / Code
//Copyright (C) Eriktse 2022 #include <bits/stdc++.h> #define pb push_back using namespace std; const int maxn = 2e5 + 9; vector<int> g[maxn]; int dfs(int dep, int x, int k, bitset<maxn>& vis) { if(dep > k)return 0; int res = vis[x] ? 0 : x;//如果走过就不加贡献,但是要往下拓展 vis[x] = 1; for(auto &i : g[x])res += dfs(dep + 1, i, k, vis); return res; } signed main() { int N, M;scanf("%d %d", &N, &M); while(M --) { int x, y;scanf("%d %d", &x, &y); g[x].pb(y), g[y].pb(x); } int Q;scanf("%d", &Q); while(Q --) { int x, k;scanf("%d %d", &x, &k); bitset<maxn> vis;//这里用vis.reset()也可以,速度也不慢 printf("%d\n",dfs(0, x, k, vis)); } return 0; }
文章评论