更新至E,I,K,F,D…
题E
题意：题目给定一个 $x$, 要求我们找出一个 $y$ 要求满足 $\frac{y^2}{10^k} = x$， 其中 $k$ 可以为任意数，例如 $y = 123, x = 1512$, (其中 $\frac{y^2}{10^k} = \frac{15129}{10^1}=1512= x$。其中 $1<=x,y<=1e9$)。
解：由于要求 $y^2$ 的前几位数有 $x$， 那么显然我们可以对 $x$ 后面加若干个 $0$，使得其 $sqrt()$ 满足 $y$ 的平方并逼近答案。枚举加 $0$ 的个数即可。
(tips : 这里注意 $sqrt()$ 的精度问题， 需要同时判断 $sqrt()$ 和 $sqrt() + 1$, 我多加了个$sqrt() - 1$ 就一直wawawa。)
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define PII pair<int, int>
#define int long long
#define ll long long
using namespace std;
const int N = 2e5 + 10, MOD = 1e9 + 7;
string get(ll x){
string s = "";
while(x){
char c = x % 10 + '0';
s = c + s;
x /= 10;
}
return s;
}
bool ok(int k, int n){
string s = get(k * k);
int ans = 0;
string ss = get(n); int len = ss.size();
for(int i = 0; i < len; ++ i){
ans = ans * 10 + (s[i] - '0');
}
if(ans == n) return 1;
return 0;
}
void solve(){
ll n; cin >> n;
ll m = n;
while(n <= 1e18){
ll k = sqrt(n);
if(ok(k, m)) {cout << k << '\n'; return ;}
if(ok(k + 1, m)) {cout << k + 1<< '\n'; return ;}
n *= 10;
}
cout << -1 << '\n';
}
signed main(){
//ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
while(n--) solve();
return 0;
}
题I
题意：两人轮流玩棋盘大小为 $n * m$ 的五子棋，要求构造一个平局的情况，其中先手为 $’x’$, 另一个人为 $’o’$ ，（$1 <= n, m <= 1000$）。
解：首先可以构造这样的局面
xoxoxoxoxo...
oxoxoxoxox...
xoxoxoxoxo...
oxoxoxoxox...
xoxoxoxoxo...
oxoxoxoxox...
此时只会出现斜对角五着连线， 这时将每三行的二三行对换，形成如下局面
xoxoxoxoxo...
xoxoxoxoxo...
oxoxoxoxox...
oxoxoxoxox...
oxoxoxoxox...
xoxoxoxoxo...
这时候如果我们直接输出 $n * m$, $’x’$ 和 $’o’$ 的差值会有 $0$、$1$ 和 $2$ 两种情况， 由于 $’x’$ 是先手，所以多一个无妨，除此以外，对于其他不相等的情况修改一步棋即可。
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define PII pair<int, int>
#define ll long long
using namespace std;
const int N = 2e3 + 10;
char s[N][N];
void solve(){
int n, m; cin >> n >> m;
int a = 0, b = 0;
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= m; ++ j){
if(s[i][j] == 'x') a ++;
else b ++;
}
}
if(b > a) s[3][1] = 'x';
else if(a > b + 1) s[1][1] = 'o';
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= m; ++ j){
cout << s[i][j];
}
cout << '\n';
}
if(b > a) s[3][1] = 'o';
else if(a > b + 1) s[1][1] = 'x';
}
int main(){
//ios::sync_with_stdio(0); cin.tie(0);
for(int i = 1; i <= N - 10; ++ i){
for(int j = 1; j <= N - 10; ++ j){
if((i + j) & 1) s[i][j] = 'o';
else s[i][j] = 'x';
}
}
for(int i = 3; i <= N - 10; i += 3) swap(s[i], s[i - 1]);
int n; cin >> n;
while(n--) solve();
return 0;
}
题K
题意：有长度 $n$ 的数组 $a$ 和 $b$, 其中 $a_i$ 表示一个盒子里的分数， $b_i$ 表示盒子有没有盖子，这里 $b_i$用 $0$ 和 $1$ 表示有没有盖子。 对于每一个盖子，我们可以将其左移或右移一个单位，也可以不移动。求我们可以获得的最大分数是多少（$0 <= a_i 1e9$ , $0 <= b_i <= 1$）。
解：我们用 $dp[i][1/2/3]$ 分别表示前 $i$ 个 $box$ 及当前盖子的 $左移/不动/右移$ 三种状态。
可以理解当前 $i$ 位置有盖子时，如果我们将其左移，那么左边那个位置原本就是没有盖子的，也就是对前面的 $dp[i - 1][1]$ 进行状态转移$dp[i][1] = dp[i - 1][1] + a[i - 1];$ ，另外两种状态依此类推。
当此位置没有盖子时，我们考虑将空盖子左移时是对前一个没有影响的情况，即 $dp[i - 1][1]$ 和 $dp[i - 1][2]$； 当前盖子不动时则是对前一状态的三种状态进行转移。
代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1 << 30
const int N = 1e6 + 10;
int a[N], b[N];
ll dp[N][4];
int main(){
int n; cin >> n;
for(int i = 1; i <= n; ++ i) cin >> a[i];
for(int i = 1; i <= n; ++ i) cin >> b[i];
for(int i = 1; i <= n; ++ i){
if(b[i]){
dp[i][1] = dp[i - 1][1] + a[i - 1];
dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]) + a[i];
dp[i][3] = max({dp[i - 1][1], dp[i - 1][2], dp[i - 1][3]}) + a[i + 1];
}else {
dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
dp[i][2] = max({dp[i - 1][1], dp[i - 1][2], dp[i - 1][3]});
}
}
cout << max({dp[n][1], dp[n][2], dp[n][3]});
}
(擦擦擦擦，我开始将连续盖子分块，然后取最小的$1/2/3$个罐子扔了，然后模拟了两个小时还是通过$0.27$，心态整崩了、、、)
题F
题意：给定一个 $n$，表示有一个长度为 $n$ 的链，其中结点下标为 $1<=i<=n$，且每个相邻的结点差值为 $1$，题目给定 $R、G、B$ 三种颜色的初始位置下标， $A$ 和 $B$ 二人轮流操作，每次移动一个颜色到一个相邻的结点，当一个人移动后三种颜色的坐标 $(R,G,B)$ 重复出现时 $lose$。
解：因为每次操作仅能使得一个颜色的 $+1$ 或 $-1$， 我们可以构造一个边长为 $n$ 的正方体，当且仅当棋子走到走过的位置点时 $lose$，这里联系到二分图博弈模型：当且仅当起始点位于最大匹配上时先手必胜。
当 $n$ 为偶数时，任何起始点开始走完所有点时都是先手必胜。
当 $n$ 为奇数时，当 $(R,G,B)$ 三点坐标和为奇数时，无法走完全部的点，此时先手必败。 反之坐标和为偶数时能在奇数步内走完全部点， 先手必胜。
#include<iostream>
using namespace std;
int main(){
int T; cin >> T;
while(T --){
int n, a, b, c; cin >> n >> a >> b >> c;
if(n & 1){
if((a + b + c) & 1) cout << "Bob\n";
else cout << "Alice\n";
}else cout << "Alice\n";
}
}
题D
题意：共有 $n$ 个人，$m$ 道菜，$n$ 个人要轮流共点 $k$ 道菜。每个人对每道菜的满意度不同，给定 $n*m$ 个满意度，如何选菜使得总满意度最大
（$1<=n<=2000$,$1<=k<=m<=2000$,$1<=A_{i,j}(满意度)<=1e9$，每个菜最多点一次，升序输出答案）。
解：如果从前往后贪心，对当前的人来说后面的人可能选择自己最喜欢的菜，所以他应该选择后面的人没选过的菜中自己最喜欢的。因此我们倒着选菜，每个人选择自己最喜欢的菜，这样对于正序的某个人 $i$ 来说，自己应该选择除去 $k-(i+1)$ 个菜之后自己最喜欢的菜，$n,m$ 的范围不超过 $2000$, $O(n * m)$ 暴力即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1 << 30
const int N = 2e3 + 10;
int a[N][N], st[N];
void solve(){
int n, m, k; cin >> n >> m >> k;
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= m; ++ j){
cin >> a[i][j];
}
}
for(int i = 1; i <= m; ++ i) st[i] = 0;
vector<int> ans;
for(int i = k - 1; i >= 0; -- i){
int x = i % n + 1, k = -1;
for(int j = 1; j <= m; ++ j){
if(st[j]) continue;
if(k == -1 || a[x][j] > a[x][k]) k = j;
}
st[k] = 1; ans.push_back(k);
}
sort(ans.begin(), ans.end());
for(auto i: ans) cout << i << ' ';
cout << '\n';
}
int main(){
int T; cin >> T;
while(T --) solve();
}
题G
题意：给定一个字符串 $s$， 判断其是否为对称字符串 $S$， 其中 $S$ 的定义如下
1、S是空字符串。
2、S由'o','s','x','z'等若干个组成。
3、S由若干个形如bSq,dSp,qSb,nSu,uSn,oSo...组成
若干个 $S$ 直接拼接在一起也为 $S$。
解：马拉车，会了再写。