结果还没出 记录一下我的答案
A
略
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;int main()
{printf("%d\n", 2 + 2 * 9 + 2 * 9 * 9 * 9);return 0;
}B
跑出来是14
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;int year, month, day; void add()
{int m[20] = {0};_for(i, 1, 12) m[i] = 31;m[4] = m[6] = m[9] = m[11] = 30;m[2] = 28;day++;if(day == m[month] + 1){day = 1;month++;if(month == 13) year++;}
}bool check()
{string a, b, c;a = "2022";if(month < 10) b = "0" + to_string(month);else b = to_string(month);if(day < 10) c = "0" + to_string(day);else c = to_string(day);string cur = " " + a + b + c;cout << cur << endl;_for(i, 1, 8){if(i + 2 > 8) break;if(cur[i] + 1 == cur[i + 1] && cur[i + 1] + 1 == cur[i + 2]) {puts("!@#!@#");return true;}}return false;
}int main()
{year = 2022;month = 1;day = 1;int ans = check();while(1){add();if(year != 2022) break;ans += check();}printf("%d\n", ans);return 0;
}C
模拟即可 注意开long long
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
ll a, b, n;
ll day[10];int main()
{scanf("%lld%lld%lld", &a, &b, &n);_for(i, 1, 5) day[i] = a;_for(i, 6, 7) day[i] = b;ll week = n / (5 * a + 2 * b);ll ans = 7 * week;ll cur = n % (5 * a + 2 * b);int i = 1;while(cur > 0){cur -= day[i];i++;ans++;}printf("%lld\n", ans);return 0;
}D
找一下规律就可以了，可以发现一个位置的高度，要不是在人在左边的时候长的，要不是在人在右边的时候长的，取个max即可
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;int main()
{int n; scanf("%d", &n);_for(i, 1, n){int l = i - 1, r = n - i;printf("%d\n", 2 * max(l, r));}return 0;
}E
看半天没看懂这个进制到底是怎么转换的……跳了 后面再回来看把题目看懂了
十进制转换成X进制就除相应的进制取余，就类似十进制转二进制
X进制转十进制的话，每一位的权重是前面所有进制的乘积
比如第三位的权重就是第一位进制和第二位进制的乘积
这样的话，我的想法是贪心，每一位都尽量取最小（样例也是这样），这样a-b是最小的，这个结论可以通过反证法证一下。
比如已经是每一位最小了，然后其中某一位变大，可以发现这个时候A-B是变大的
因为这一位变大，会使得后面所有位的权重变大，然而A和B的前面部分，A一定是大于B的（题目说A>=B）因此A和B的前面部分相减为正，然后权重又变大，那么差就变大。
所以输入的那个最大进制其实没有用。
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int mod = 1000000007;
const int N = 1e5 + 7;
int a[N], b[N], lena, lenb, mx;int main()
{scanf("%d%d", &mx, &lena);_for(i, 1, lena) scanf("%d", &a[i]);scanf("%d", &lenb);_for(i, 1, lenb) scanf("%d", &b[i]);reverse(a + 1, a + lena + 1);reverse(b + 1, b + lenb + 1);ll ans = 0, cur = 1;ll A = 0, B = 0;_for(i, 1, max(lena, lenb)){A = (A + a[i] * cur % mod) % mod;B = (B + b[i] * cur % mod) % mod;cur = cur * max(2, max(a[i], b[i]) + 1) % mod;}printf("%lld\n", (A - B + mod) % mod);return 0;
}F
这70%的数据就直接暴力枚举加二维前缀和
最后30%的数据是500，这显然要n^3
再优化的话，我只能想到最后一层循环可以改成二分，从而由n^4变成n^3logn
感觉会T，就交了70分的代码。
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 500 + 10;
ll a[N][N], s[N][N];
int n, m, k;ll cal(int x1, int y1, int x2, int y2)
{return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}int main()
{scanf("%d%d%d", &n, &m, &k);_for(i, 1, n)_for(j, 1, m)scanf("%lld", &a[i][j]);_for(i, 1, n)_for(j, 1, m)s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];int ans = 0;_for(x1, 1, n)_for(y1, 1, m)_for(x2, x1, n)_for(y2, y1, m){ll cur = cal(x1, y1, x2, y2);if(cur <= k) ans++;else break;}printf("%d\n", ans);return 0;
}G
在以前的ACM区域赛做过类似的题，但比这个难得多。这个题一看就是递推+矩阵快速幂
但是我看那个数据范围只有1e7，不需要矩阵快速幂，可能省赛不会考到这个难度。
递归式就枚举一下各种情况就可以推了，可以看代码。
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int mod = 1000000007;
const int N = 1e7 + 10;
ll dp[N];
int n;int main()
{scanf("%d", &n);dp[0] = 1;_for(i, 1, n){ll a = dp[i - 1];ll b = (i - 2 >= 0) ? dp[i - 2] : 0;ll c = (i - 3 >= 0) ? dp[i - 3] : 0;ll d = (i - 4 >= 0) ? dp[i - 4] : 0;dp[i] = (a + b + 2 * c + 2 * d) % mod;}printf("%lld\n", dp[n]);return 0;
}H
这题的关键在于r<=10 因此枚举一个点周围的点不需要很久。算了一下复杂度感觉比较极限。
我的做法是unordered_map + 并查集
考后发现这题g了
因为这道题是单向边，不是双向边，所以要建图bfs，不能并查集
建图bfs反而还容易写一些，我写复杂了也写错了……
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef unsigned long long ull;
unordered_map<ull, int> mp;
const int N = 5e4 + 10;
int f[N], siz[N], x[N], y[N], r[N], n, m;int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }void Union(int x, int y)
{int fx = find(x), fy = find(y);if(fx == fy) return;f[fx] = fy;siz[fy] += siz[fx];siz[fx] = 0;
}ull id(int xx, int yy)
{return (ull)1e10 * xx + yy;
}void add(int xx, int yy, int i)
{if(!mp[id(xx, yy)]) mp[id(xx, yy)] = i;else Union(i, mp[id(xx, yy)]);
}bool check(int xx, int yy, int x1, int y1, int r)
{return (xx - x1) * (xx - x1) + (yy - y1) * (yy - y1) <= r * r;
}int main()
{scanf("%d%d", &n, &m);_for(i, 1, n) f[i] = i, siz[i] = 1;_for(i, 1, n){scanf("%d%d%d", &x[i], &y[i], &r[i]);add(x[i], y[i], i);}_for(i, 1, n)_for(xx, x[i] - r[i], x[i] + r[i])_for(yy, y[i] - r[i], y[i] + r[i]){if(!check(xx, yy, x[i], y[i], r[i])) continue;if(xx == x[i] && yy == y[i]) continue;if(mp[id(xx, yy)]) Union(i, mp[id(xx, yy)]);}int ans = 0;_for(i, 1, m){int xx, yy, rr;scanf("%d%d%d", &xx, &yy, &rr);_for(x1, xx - rr, xx + rr)_for(y1, yy - rr, yy + rr){if(!check(x1, y1, xx, yy, rr)) continue;if(mp[id(x1, y1)]) {ans += siz[find(mp[id(x1, y1)])];siz[find(mp[id(x1, y1)])] = 0;}}}printf("%d\n", ans);return 0;
}I
这题一看就是数位dp啊，直接记忆化搜索
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int mod = 1000000007;
const int N = 100 + 10;
ll dp[N * 2][N][N];
int n, m;ll dfs(int pos, int cur, int cnt) //位置 当前酒 剩下遇到多少次花
{if(cur > 105 || cur < 0) return 0; //喝不完或者不合法 if(pos == n + m) return cur == 1 && cnt == 1; //最后一次喝酒 剩下一次if(dp[pos][cur][cnt] != -1) return dp[pos][cur][cnt]; //记忆化 ll res = 0;res += dfs(pos + 1, cur * 2, cnt); //乘以2 if(cnt) res += dfs(pos + 1, cur - 1, cnt - 1); //减1 res %= 1000000007;dp[pos][cur][cnt] = res;return res;
}int main()
{memset(dp, -1, sizeof dp);scanf("%d%d", &n, &m);printf("%lld\n", dfs(1, 2, m));return 0;
}J
猜了一个结论，不是很确定。
先不管多个数变化的情况来统计
然后看相邻的数，如果各自下降的过程中有重复的，答案就可以减一
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 2e5 + 10;
unordered_map<ll, int> mp1, mp2;
ll a[N];
int n;ll f(ll x)
{return sqrt(x / 2 + 1);
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%lld", &a[i]);int ans = 0;while(a[1] > 1){mp1[a[1]] = 1;a[1] = f(a[1]);ans++;}_for(i, 2, n){while(a[i] > 1){if(mp1[a[i]]) ans--;mp2[a[i]] = 1;a[i] = f(a[i]);ans++;}mp1 = mp2;mp2.clear();}printf("%d\n", ans);return 0;
}