A. 回文
经典 \(dp\) ，两边同时走，三维状态表示走了几步，左上出发走到哪行，右下出发走到哪行
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 505;
const int mod = 993244853;
int f[2][maxn][maxn], n, m, nt, zt;
char mp[maxn][maxn];
void add(int &x, int y){
x += y; x = x >= mod ? x - mod : x;
}
bool check(int x, int y){return x > 0 && y > 0 && x <= n && y <= m;}
bool can(int x, int y, int xx, int yy){
// printf("chk : %d %d %d %d\n", x, y, xx ,yy);
return check(x, y) && check(xx, yy) && mp[x][y] == mp[xx][yy];
}
void upd(int x, int y, int xx, int yy){
if(xx < x || yy < y)return;
if(can(x, y + 1, xx, yy - 1))add(f[nt][x][xx], f[zt][x][xx]);
if(can(x, y + 1, xx - 1, yy))add(f[nt][x][xx - 1], f[zt][x][xx]);
if(can(x + 1, y, xx, yy - 1))add(f[nt][x + 1][xx], f[zt][x][xx]);
if(can(x + 1, y, xx - 1, yy))add(f[nt][x + 1][xx - 1], f[zt][x][xx]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; ++i)scanf("%s",mp[i] + 1);
f[0][1][n] = mp[1][1] == mp[n][m];
int c = (n + m - 1) / 2;
if((n + m) % 2 == 0)++c;
for(int i = 1; i < c; ++i){
nt = i & 1, zt = 1 - nt;
int sum = i + 1;
int up = min(n, sum - 1);
for(int d1 = 1; d1 <= up; ++d1)
for(int d2 = 1; d2 <= up; ++d2){
int x = d1, y = sum - d1;
int xx = n - d2 + 1, yy = m + n - i - xx + 1;
if(x <= xx && y <= yy && f[zt][x][xx])upd(x, y, xx, yy);
f[zt][x][xx] = 0;
}
}
int ans = 0;
nt = c & 1;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
int x = i, y = c - i + 1;
int xx = n - j + 1, yy = m + n - c - xx + 1;
// printf("%d %d %d %d\n",x, y, xx, yy);
if(x <= xx && y <= yy && check(x, y) && check(xx, yy))add(ans, f[1 - nt][x][xx]);
}
}
printf("%d\n",ans);
return 0;
}
B. 快速排序
你如果像我一样一直考虑如何优化他的代码，别想了，没救
发现就是把数移到前面比他大的数前面，整体还是有序的
那么每次二分一下就行了
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 500005;
const int inf = 2147483647;
int n;
char c[15];
int a[maxn], b[maxn];
bool vis[maxn];
void solve(){
scanf("%d",&n);
for(int i = 1; i <= n; ++i){
a[i] = 0;
scanf("%s", c + 1);
if(c[1] == 'n')a[i] = inf;
else{
int s = strlen(c + 1);
for(int j = 1; j <= s; ++j){
a[i] = (a[i] << 3) + (a[i] << 1) + (c[j] ^ 48);
}
}
}
int p = 0;
for(int i = 1; i <= n; ++i)if(a[i] != inf)b[++p] = a[i];
sort(b + 1, b + p + 1);
int mx = 0;
int l = 1;
for(int i = 1; i <= n; ++i){
if(a[i] == inf)printf("nan ");
else{
if(mx <= a[i]){
int now = lower_bound(b + l, b + p + 1, a[i]) - b;
for(int j = l; j <= now; ++j)printf("%d ",b[j]);
l = now + 1;
}
mx = max(a[i], mx);
}
}
// for(int i = 1; i <= n; ++i)if(a[i] == inf)printf("nan "); else printf("%d ",a[i]);
printf("\n");
}
int main(){
int t; scanf("%d",&t);
for(int i = 1; i <= t; ++i)solve();
return 0;
}
C. 混乱邪恶
奇妙构造
题解讲的很好，我就不废话了
关于 \(\sum d_i\) 那个式子，其实就是 \([l,r]\) 有 \(r - l + 1\) 个数，但是 \(d_i = r - l\) 两个数就会少一个，一共少 \(n/ 2\)
右边式子是题目保证
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000005;
int n, m, a[maxn], now[maxn << 2 | 1];
int ans[maxn], id[maxn];
int cnt;
struct node{int idx, idy, val;}d[maxn << 2 | 1];
struct note{
int val, id;
friend bool operator < (const note &x, const note &y){
return x.val < y.val;
}
};
multiset<note>s;
queue<int>Q;
int main(){
cin >> n >> m;
for(int i = 1; i <= n; ++i)cin >> a[i];
for(int i = 1; i <= n; ++i)id[a[i]] = i;
sort(a + 1, a + n + 1);
int p = 0;
for(int i = n; i >= 1; i -= 2){
d[++p].val = a[i] - a[i - 1];
d[p].idx = a[i]; d[p].idy = a[i - 1];
}
for(int i = 1; i <= p; ++i)s.insert({d[i].val, i});
int q = p;
for(int i = 1; i < p; ++i){
auto be = s.begin(), en = --s.end();
d[++q].idx =(*en).id;
d[q].idy = (*be).id;
d[q].val = (*en).val - (*be).val;
s.erase(be); s.erase(en);
s.insert({d[q].val, q});
}
int root = (*s.begin()).id;
now[root] = 1; Q.push(root);
while(!Q.empty()){
int x = Q.front(); Q.pop();
if(x <= p)continue;
now[d[x].idx] = now[x];
now[d[x].idy] = -now[x];
Q.push(d[x].idx);
Q.push(d[x].idy);
}
for(int i = 1; i <= p; ++i)ans[id[d[i].idx]] = now[i], ans[id[d[i].idy]] = -now[i];
printf("NP-Hard solved\n");
for(int i = 1; i <= n; ++i)printf("%d ",ans[i]);
return 0;
}
D. 校门外歪脖树上的鸽子
咕咕咕
code