牛客多校2
I.Link with Gomoku
题意：
两个人下五子棋，给出棋盘大小，构造一种方案，使得平局。
思路：
考虑这样构造
xxxxo
oxxxx
xxxxo
oooox
以五一个为一个循环，多出来的部分也以这种方式构造，唯一的问题就是当有奇数行时会导致先手的棋子太多，因此当n为奇数时，让最后一行这样填充
xoxoxox......
#include<bits/stdc++.h>
using namespace std;
int n, m;
const int maxn = 1e3 + 10;
char ans[maxn][maxn];
void print(){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cout<<ans[i][j];
}
cout<<"\n";
}
}
void solve(){
cin>>n>>m;
if(n < 5){
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(i % 2 == 1){
ans[j][i] = 'x';
}
else{
ans[j][i] = 'o';
}
}
}
if(m % 2 == 1){
for(int i = (n + 1) / 2 + 1; i <= n; i++){
ans[i][m] = 'o';
}
}
}
else if(m < 5){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(i % 2 == 1){
ans[i][j] = 'x';
}
else ans[i][j] = 'o';
}
}
if(n % 2 == 1){
for(int i = (m + 1) / 2 + 1; i <= m; i++){
ans[n][i] = 'o';
}
}
}
else{
int t1 = m / 5;
for(int k = 1; k <= t1; k++){
for(int i = 1; i <= n; i++){
for(int j = (k - 1) * 5 + 1; j <= k * 5 - 1; j++){
if(i % 2 == 1){
ans[i][j] = 'x';
}
else ans[i][j] = 'o';
}
if(i % 2 == 1) ans[i][k * 5] = 'o';
else ans[i][k * 5] = 'x';
}
}
int t2 = m % 5;
for(int i = 1; i <= n; i++){
for(int j = t1 * 5 + 1; j <= m; j++){
if(i % 2 == 1) ans[i][j] = 'x';
else ans[i][j] = 'o';
}
}
if(n % 2 == 1){
for(int i = 1; i <= m; i ++){
if(i % 2 == 1) ans[n][i] = 'x';
else ans[n][i] = 'o';
}
}
}
print();
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int T = 1;
cin>>T;
while(T--){
solve();
}
return 0;
}
E.Square
题意：
给出x，找到y满足\(y^2/10^k =x\)成立，找不到则输出-1，考虑二分答案。
D. The Game of Eating
题意：
有n个人、m道菜，每个人对每道菜都有一个评价，要选k次菜，让每个人的对菜喜爱值的和尽量大。
思路：
首先考虑正着贪心，因为我后面的人可能选到我最喜欢的菜，而我把这道菜选了后面的人的选择就可能不是最优，因此可以发现，当最后一个人选的时候，它不需要考虑后面是否会有人选到我最喜欢的菜，以此类推，倒着贪心一定是最优的。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e3 + 10;
int n, m, k;
ll a[maxn][maxn];
void solve(){
cin>>n>>m>>k;
vector<int>vis(m + 5, 0);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin>>a[i][j];
}
}
vector<int>ans;
for(int i = k; i >= 1; i--){
int s = i % n;
if(s == 0) s = n;
vector<pair<int, int>>tmp(m + 1);
for(int j = 1; j <= m; j++){
tmp[j].first = a[s][j];
tmp[j].second = j;
}
sort(tmp.begin() + 1, tmp.begin() + 1 + m);
for(int j = m; j >= 1; j--){
if(!vis[tmp[j].second]){
vis[tmp[j].second] = 1;
ans.push_back(tmp[j].second);
break;
}
}
}
sort(ans.begin(), ans.end());
for(int i = 0; i < k; i++){
cout<<ans[i]<<" \n"[i == k -1];
}
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int T = 1;
cin>>T;
while(T--){
solve();
}
return 0;
}
F. Link with Chess Game
题意：
博弈论、两个人对三元组进行操作，当谁操作到之前被操作到的一个位置时，谁就输了
思路：
二分图博弈，当n为偶数时先手一定可以完全匹配，当n为奇数时只有初始位置的和为奇数时后手才能赢。
#include<bits/stdc++.h>
using namespace std;
int n, x, y, z;
void solve(){
cin>>n>>x>>y>>z;
int sum = (x + y + z);
if(sum % 2 == 1){
if(n % 2 == 1)
cout<<"Bob\n";
else cout<<"Alice\n";
}
else cout<<"Alice\n";
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int T = 1;
cin>>T;
while(T--){
solve();
}
return 0;
}
G.Link with Centrally Symmetric Strings
题意：
给出一个字符串，判断其能否分成若干个中心对称字符串。
一个字符串被称为中心对成字符串的条件是
思路：
首先中心对称这个概念和回文这个概念是很像的，那么能否用类似Manacher算法的思想做呢。
首先，题目本身的要求是分成若干个中心对成串，那么贪心的去想，假设一个字符串的左端点为l，右端点为r。那么如果[l,r]恰好是一个中心对称串，那么我就在r的位置断开，这样子得到的字符串一定是符合条件的并且按照这样分的策略，也一定能够判断初始的串是否满足条件。可以发现这个过程确实是和manacher类似的。
考虑p[i] 为以i为中心的最长中心对称半径。假设我当前的位置小于我前一个最长中心对称半径的右端点，令其为R，再令左端点为L。那么我就要再判断我的镜像位置的左端点是否小于L。以此来求得我这个位置的最长中心对称半径。如果大于R，那么就需要暴力更新，但是因为更新的过程中i是随着中心一起增加的（参考manacher），因此复杂度是线性的。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int n;
char s[maxn + 5];
char t[2 * maxn + 5];
char mp[256];
void init(){
mp['b'] = 'q';
mp['d'] = 'p';
mp['p'] = 'd';
mp['q'] = 'b';
mp['n'] = 'u';
mp['u'] = 'n';
mp['o'] = 'o';
mp['s'] = 's';
mp['x'] = 'x';
mp['z'] = 'z';
mp['#'] = '#';
}
void solve(){
cin>>(s + 1);
n = strlen(s + 1);
int m = 0;
t[0] = '$';
t[++m] = '#';
for(int i = 1; i <= n; i++){
t[++m] = s[i], t[++m] = '#';
}
t[m + 1] = '\0';
vector<int>p(m + 1);
int M = 0, R = 0;
int start = 1;
for(int i = 1; i <= m; i++){
if(i > R) p[i] = -1;
else p[i] = min(p[2 * M - i], R - i + 1);
while(t[i - p[i] - 1] == mp[t[i + p[i] + 1]]){
++p[i];
}
if(i + p[i] > R){
M = i;
R = i + p[i];
}
if(p[i] > 0 && i - p[i] <= start){
t[i + p[i] - 1] = '$';
start = i + p[i];
i = i + p[i] - 1;
}
}
if(start == m) cout<<"Yes\n";
else cout<<"No\n";
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int T = 1;
init();
cin>>T;
while(T--){
solve();
}
return 0;
}