本文最后更新于 281 天前,其中的信息可能已经有所发展或是发生改变。
寻找ACMer
思想:
- 签到题
- 按照题意遍历字符串,不断向后寻找包含 ACMer 完整字符串的数量即可
std标程:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define re register #define fi first #define se second #define endl '\n' typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; const int N = 1e6 + 3; const int INF = 0x3f3f3f3f, mod = 1e9 + 7; const double eps = 1e-6, PI = acos(-1); void solve(){ string s; cin >> s; int idx = 0; int ans = 0; while(s.find("ACMer", idx) != -1) { ans ++; idx = s.find("ACMer", idx) + 1; } cout << ans << endl; } int main(){ IOS; int _ = 1; // cin >> _; while(_ --){ solve(); } return 0; }
欧拉幻树苗
思想:
- 树形DP
- 始化每一个节点为独立的连通分量,即每个节点自身就是一个树的根。
- 读取树的结构,确保我们可以通过 g 数组访问到每个节点的孩子节点。
- 读取特殊边,并使用并查集合并特殊边的两个端点。由于题目保证特殊边的两个端点深度相同,合并这些端点不会导致环的出现。
- 然后开始广度优先搜索。从根节点(节点1)开始,用队列来记录接下来需要访问的节点。
- 对于当前节点 t,如果它是叶子,将 find(t) 的路径数加到答案中(即cnt[find(t)]),因为从叶子节点可以直接走到根节点。
- 遍历当前节点t的所有孩子节点,将父节点到当前节点的路径数累加到孩子节点上(需要通过find函数找到孩子节点所在的连通分量),然后将这些孩子节点加入队列中以进行下一轮搜索。
- 当队列为空时,所有节点都被访问过,搜索结束。最后输出计算的答案 ans。
std标程:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define re register #define fi first #define se second #define endl '\n' typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; const int N = 1e6 + 3; const int INF = 0x3f3f3f3f, mod = 1e9 + 7; const double eps = 1e-6, PI = acos(-1); int f[N], cnt[N]; // f数组用于并查集,cnt数组用于记录路径数 vector<int> g[N]; // g数组用来存储树的结构 int find(int x){ return f[x] == x ? x : f[x] = find(f[x]); } void solve() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i ++) f[i] = i; // 初始化 for(int i = 1; i < n; i ++){ int x, y; cin >> x >> y; // 读取树的结构 g[y].push_back(x); // 假设每条边是从子节点指向父节点 } for(int i = 1; i <= m; i ++){ int x, y; cin >> x >> y; // 输入特殊边 f[find(x)] = find(y); // 合并特殊边的端点 } queue<int> q; q.push(1); cnt[1] = 1; // 根节点的路径数为1 int ans = 0; // 结果变量 while(!q.empty()){ int t = q.front(); q.pop(); if(g[t].empty()) (ans += cnt[find(t)]) %= mod; // 如果t是叶子节点,累加路径数 for(auto i:g[t]){ (cnt[find(i)] += cnt[find(t)]) %= mod; // 将当前节点的路径数累加到其孩子节点 q.push(i); // 将孩子节点加入队列 } } cout << ans; } int main(){ IOS; int _ = 1; //cin >> _; while(_ --){ solve(); } return 0; }
疯狂蓝桥杯
本题主要考察四舍五入,C语言中是四舍六入,但是需要四舍五入,则在结果后面加上0.001即可。
std标程:
#include<bits/stdc++.h> using namespace std; #define int long long signed main() { int T; cin>>T; while(T--) { int n,m,x,y; cin>>n>>m>>x>>y; int z=n*y,zz=m*x; int zzz=z*zz/__gcd(z,zz); int i=zzz/z,j=zzz/zz; double s=sqrt(n*n*i*i+m*m*j*j) * 2; s+=0.001; printf("%.2lf\n",s); } return 0; }
Inception Ⅰ
用数组(如st)记录每个数字出现的次数,从1枚举到 (m + 1)/ 2 (不含),所有 st[i] * st[m - i]的和,注意要开long long~
std标程:
#include <iostream> using namespace std; const int N = 1e6 + 20; int n, m, st[N]; long long ans; int main() { int x; cin >> n >> m; for(int i = 1; i <= n; i ++) { cin >> x; st[x] ++; } for(int i = 0; i < m - i; i ++) { ans += (long long)st[i] * st[m - i]; } cout << ans; return 0; }
Inception Ⅱ
循环枚举判断是否存在连续三个字母/四个元素组成的回文数组,(易证所有长度大于2的回文都包含这两种回文之一),定义数组记录下标为 i 的元素向后找最近的回文数组右端点的距离,如 1 1 2 2 1,对应记录数组应为 4,3,0,0,0。对每次查找的时间复杂度缩小到O(1)。
std标程:
#include <iostream> using namespace std; const int N = 1e6 + 20; int n, q[N], s[N]; int main() { int t; scanf("%d %d", &n, &t); for (int i = 1; i <= n; i ++) { scanf("%d", &q[i]); } for (int i = 1; i <= n; i ++) { //偶数回文 if (i + 3 <= n) { if(q[i] == q[i + 3] && q[i + 1] == q[i + 2]) s[i] = 3; } //奇数回文 if (i + 2 <= n) { if (q[i] == q[i + 2]) s[i] = 2; } } int f = 0; for (int i = n; i > 0; i --) { if (s[i] && !f) f = 1; if (f && !s[i]) s[i] = s[i + 1] + 1; } int l, r; while(t --) { scanf("%d %d", &l, &r); if (!s[l]) printf("NO\n"); else if (l + s[l] <= r) printf("YES\n"); else printf("NO\n"); } return 0; }
Inception Ⅲ
易证,当 n == 1 或 n == 2 时,图腾陀螺可一步取胜,除此之外,Belinra均可胜利(想什么呢,这可是Belinra的主场,给你先手是客套,怎么可能让你轻易取胜)
std标程:
#include <iostream> using namespace std; int main() { int n; cin >> n; if (n == 1 || n == 2) cout << "None life is but a dream ."; else cout << "Wake up now !"; return 0; }
憧憬成为AK大神
思想:
- 贪心
- 有题目可知,到了某一个点都不能可能再往回走(回头一定不是最优解,否则在原来就已经进去AK了)
- 先对页面编号排序,然后用一个大根堆来维护从起始页面切换到当前这个页面的已AK的场次所消耗的时间
- 如果所有的时间消耗(切换界面的时间+对应场次让出的时间)已大于规定的时间,则该方向上的时间不可避免
- 所以只能少切换界面,因为每一场比赛都AK一次,即将让出时间最大的页面跳过即可
std标程:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define re register #define fi first #define se second #define endl '\n' typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; const int N = 1e6 + 3; const int INF = 0x3f3f3f3f, mod = 1e9 + 7; const double eps = 1e-6, PI = acos(-1); priority_queue<LL> q; PLL a[N]; bool cmp(PLL &a, PLL b) { return a.fi < b.fi; } LL n, m, ans, res, sum, idx; void solve(){ cin >> n >> m; for (int i = 0; i <= n; i ++) { LL x, y; cin >> x >> y; a[++ idx].fi = x; a[idx].se = y; } sort(a + 1, a + n + 1, cmp); for(int i = 1; i <= n; i ++) { res += a[i].fi - a[i - 1].fi; //切换到 i 页面所用时间 q.push(a[i].se); // sum 的欲望 sum ++; res += a[i].se; while(!q.empty() && res > m) //如果用的时间多于m,直接ak掉 { sum --; res -= q.top(); q.pop(); } if(res > m) break; ans = max(ans, sum); } cout << ans << endl; } int main(){ IOS; int _ = 1; // cin >> _; while(_ --){ solve(); } return 0; }
高精度拼接
由于每添加一个数都需要满足 a % b == 0,故第一次从 0 到 9 枚举,如果存在满足条件的数直接输出即可,紧接着输出 n - 1 个 0,否则输出 -1
std标程:
#include <stdio.h> int main() { int a, b, c, ans = -1; scanf("%d %d %d", &a, &b, &c); for (int i = 0; i <= 9; i ++) { if ((a * 10 + i) % b == 0) { ans = a * 10 + i; break; } } if (ans != -1) { printf("%d", ans); for (int i = 1; i <= c - 1; i ++) printf("0"); } else { printf("-1"); } return 0; }
逆矩阵
- 签到题,模拟
std标程:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) #define re register #define fi first #define se second #define endl '\n' typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; const int N = 1e6 + 3; const int INF = 0x3f3f3f3f, mod = 1e9 + 7; const double eps = 1e-6, PI = acos(-1); void solve(){ int n; cin >> n; int size = n; n *= n; vector<vector<int>> ans(size, vector<int>(size, 0)); int num = 1; int top = 0, st = size - 1, left = 0, right = size - 1; while(num <= n) { for(int i = top; i <= st && num <= n; i++) { ans[i][left] = num++; } left++; for(int i = left; i <= right && num <= n; i++) { ans[st][i] = num++; } st--; for(int i = st; i >= top && num <= n; i--) { ans[i][right] = num++; } right--; for(int i = right; i >= left && num <= n; i--) { ans[top][i] = num++; } top++; } for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if (ans[i][j] != 0) { cout << ans[i][j] << " "; } } cout << endl; } } int main(){ IOS; int _ = 1; // cin >> _; while(_ --){ solve(); } return 0; }