回归了原本的 ABC 难度，可惜我很久没打没有手速被打爆了。
https://atcoder.jp/contests/abc218/tasks
A
直接模拟
#include<bits/stdc++.h>
using namespace std;
int n;
char s[10];
int main(){
scanf("%d%s",&n,s+1);
if(s[n]=='o')puts("Yes");
else puts("No");
return 0;
}
B
直接模拟
#include<bits/stdc++.h>
using namespace std;
int main(){
for(int i=1;i<=26;i++){
int x;
scanf("%d",&x);
printf("%c",x+'a'-1);
}
return 0;
}
C
考虑将第二图的第一个位置放到第一个第一个位置上，然后比较，较小的模拟
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
struct node{
char mp[1005][1005];
}s,t,tmp;
int n;
void print(node a){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)printf("%c",a.mp[i][j]);
puts("");
}puts("");
}
bool check(node a,node b){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a.mp[i][j]!=b.mp[i][j]){
return 0;
}
}
}
return 1;
}
void work(node &a,int x0,int y0){
node b;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)b.mp[i][j]='.';
int x=0,y=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a.mp[i][j]=='#'){
x=i,y=j;
break;
}
}
if(x||y)break;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a.mp[i][j]=='#'){
b.mp[x0+i-x][y0+j-y]='#';
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a.mp[i][j]=b.mp[i][j];
}
}
}
void rotate(node &a){
node b;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
b.mp[n-j+1][i]=a.mp[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a.mp[i][j]=b.mp[i][j];
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%s",s.mp[i]+1);
for(int i=1;i<=n;i++)scanf("%s",t.mp[i]+1);
int cnts=0,cntt=0;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cnts+=s.mp[i][j]=='#';
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cntt+=t.mp[i][j]=='#';
if(cnts!=cntt){
puts("No");
return 0;
}
int x=0,y=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(s.mp[i][j]=='#'){
x=i,y=j;
break;
}
}
if(x||y)break;
}
for(int T=1;T<=4;T++){
rotate(t);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)tmp.mp[i][j]=t.mp[i][j];
work(tmp,x,y);
if(check(s,tmp)){
puts("Yes");
return 0;
}
}
puts("No");
return 0;
}
D
枚举两个点作为左下角，右上角，然后用map判断即可。
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
struct node{
int x,y;
}p[2005];
int n;
map<pair<int,int>,int>m;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y),m[mp(p[i].x,p[i].y)]++;
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
if(p[i].x<p[j].x&&p[i].y<p[j].y){
if(m.find(mp(p[i].x,p[j].y))!=m.end()&&m.find(mp(p[j].x,p[i].y))!=m.end()){
ans++;
}
}
}
}
printf("%d
",ans);
return 0;
}
E
求出最小生成树，其中正权边不能选，取剩下所有正确边。
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=200005;
struct edge{
int u,v,w;
friend bool operator<(edge a,edge b){return a.w<b.w;}
}e[maxn];
int n,m,fa[maxn];
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
inline void Merge(int x,int y){fa[Find(x)]=Find(y);}
ll ans;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w),ans+=e[i].w>0?e[i].w:0;
sort(e+1,e+1+m);
for(int i=1;i<=m;i++){
if(Find(e[i].u)!=Find(e[i].v)){
if(e[i].w>0)ans-=e[i].w;
Merge(e[i].u,e[i].v);
}
}
printf("%lld
",ans);
return 0;
}
F
求出最短路径树，只有在最短路径树上的路径上的边才有可能改变最短路，去掉暴力bfs即可，复杂度 (O(nm))。
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=405;
int n,m,g[maxn][maxn],s[maxn*maxn],t[maxn*maxn],dis[maxn],pre[maxn],d[maxn];
queue<int> q;
bool vis[maxn],mark[maxn];
int bfs(int x,int y){
for(int i=1;i<=n;i++)vis[i]=0,dis[i]=-1;
q.push(1);
vis[1]=1;
dis[1]=0;
while(!q.empty()){
int u=q.front();q.pop();
for(int v=1;v<=n;v++){
if(u==x&&v==y)continue;
if(g[u][v]&&!vis[v]){
dis[v]=dis[u]+1;
vis[v]=1;
q.push(v);
}
}
}
return dis[n];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d%d",s+i,t+i),g[s[i]][t[i]]=1;
for(int i=1;i<=n;i++)vis[i]=0,d[i]=-1;
q.push(1);
vis[1]=1;d[1]=0;
while(!q.empty()){
int u=q.front();q.pop();
for(int v=1;v<=n;v++){
if(g[u][v]&&!vis[v]){
d[v]=d[u]+1;
pre[v]=u;
vis[v]=1;
q.push(v);
}
}
}
if(d[n]==-1){
for(int i=1;i<=m;i++)puts("-1");
return 0;
}
int x=n;
while(x!=1){
mark[x]=1;
x=pre[x];
}
for(int i=1;i<=m;i++){
if(!mark[t[i]])printf("%d
",d[n]);
else{
if(s[i]!=pre[t[i]])printf("%d
",d[n]);
else{
printf("%d
",bfs(s[i],t[i]));
}
}
}
return 0;
}
G
博弈，然后瞎转移，用数据结构维护中位数即可。
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=100005;
struct node{
int val,key,son[2],sz;
}tr[maxn*40];
int tot,rt,dep[maxn];
int new_node(int v){
tr[++tot]=node{v,rand(),0,0,1};
return tot;
}
void pushup(int p){
tr[p].sz=tr[tr[p].son[0]].sz+tr[tr[p].son[1]].sz+1;
}
int merge(int u,int v){
if(!u||!v)return u|v;
if(tr[u].key<tr[v].key){
tr[u].son[1]=merge(tr[u].son[1],v);
pushup(u);
return u;
}else{
tr[v].son[0]=merge(u,tr[v].son[0]);
pushup(v);
return v;
}
}
void split(int p,int &x,int &y,int k){
if(!p)x=y=0;
else{
if(tr[p].val<=k){
x=p;
split(tr[p].son[1],tr[x].son[1],y,k);
}else{
y=p;
split(tr[p].son[0],x,tr[y].son[0],k);
}
pushup(p);
}
}
void ins(int &p,int v){
int x,y;
split(p,x,y,v);
p=merge(merge(x,new_node(v)),y);
}
void del(int &p,int v){
int x,y,z;
split(p,x,z,v);
split(x,x,y,v-1);
y=merge(tr[y].son[0],tr[y].son[1]);
p=merge(merge(x,y),z);
}
int ath(int p,int a){
if(tr[tr[p].son[0]].sz>=a)return ath(tr[p].son[0],a);
else{
a-=tr[tr[p].son[0]].sz;
if(a==1)return tr[p].val;
return ath(tr[p].son[1],a-1);
}
}
int n,a[maxn],f[maxn];
vector<int> vec[maxn];
void dfs(int u,int fa){
int cnt=0;
ins(rt,a[u]);
if(dep[u]&1)f[u]=0;
else f[u]=1e9+1;
for(auto v:vec[u]){
if(v==fa)continue;
dep[v]=dep[u]+1;
dfs(v,u);
if(dep[u]&1)f[u]=max(f[u],f[v]);
else f[u]=min(f[u],f[v]);
cnt++;
}
if(cnt==0){
if(dep[u]&1)f[u]=ath(rt,(dep[u]+1)/2);
else f[u]=(ath(rt,dep[u]/2)+ath(rt,dep[u]/2+1))/2;
del(rt,a[u]);
return;
}
del(rt,a[u]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",a+i);
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
vec[u].pb(v);vec[v].pb(u);
}
dep[1]=1;dfs(1,0);
printf("%d
",f[1]);
return 0;
}
H
显然这东西有凸性，于是 wqs 二分+普及组dp即可。
/*
Author : Flying_Bird (ZCR)
url : https://nmsl.com
Time : 2021/09/01
*/
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
const ll maxn=200005;
ll n,R,a[maxn];
ll dp[maxn][2],cnt[maxn][2];
bool check(ll m){
dp[1][1]=m;cnt[1][1]=1;
for(ll i=2;i<=n;i++){
if(dp[i-1][0]<dp[i-1][1]+a[i-1]){
dp[i][0]=dp[i-1][1]+a[i-1];
cnt[i][0]=cnt[i-1][1];
}else{
dp[i][0]=dp[i-1][0];
cnt[i][0]=cnt[i-1][0];
}
if(dp[i-1][1]>dp[i-1][0]+a[i-1]){
dp[i][1]=dp[i-1][1]+m;
cnt[i][1]=cnt[i-1][1]+1;
}else{
dp[i][1]=dp[i-1][0]+a[i-1]+m;
cnt[i][1]=cnt[i-1][0]+1;
}
}
if(dp[n][0]>dp[n][1]){
return cnt[n][0]>R;
}else{
return cnt[n][1]>R;
}
}
int main(){
scanf("%lld%lld",&n,&R);
for(ll i=1;i<n;i++)scanf("%lld",a+i);
ll l=-4e9,r=4e9,ans=-4e9;
while(l<=r){
ll mid=(l+r)>>1;
check(mid);
if(check(mid)){
r=mid-1;
}else{
ans=mid;
l=mid+1;
}
}
check(ans);
if(dp[n][0]>dp[n][1]){
printf("%lld
",dp[n][0]-ans*R);
}else{
printf("%lld
",dp[n][1]-ans*R);
}
return 0;
}