Link:
A:
按值大小插入后用树状数组统计两边个数
#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define pb push_back typedef double db; typedef long long ll; typedef pair<int,int> P; const int MAXN=1e5+10; P dat[MAXN]; int n,bit[MAXN],dsp[MAXN],l[MAXN],r[MAXN],res,tot; void Update(int x) {while(x<=n) bit[x]++,x+=x&(-x);} int Query(int x) { int ret=0; while(x) ret+=bit[x],x-=x&(-x); return ret; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&dat[i].X),dsp[++tot]=dat[i].X,dat[i].Y=i; sort(dsp+1,dsp+n+1);tot=unique(dsp+1,dsp+n+1)-dsp-1; for(int i=1;i<=n;i++) dat[i].X=lower_bound(dsp+1,dsp+tot+1,dat[i].X)-dsp; sort(dat+1,dat+n+1,greater<P>()); for(int i=1;i<=n;i++) { l[i]=Query(dat[i].Y-1); r[i]=i-1-l[i];Update(dat[i].Y); if(max(l[i],r[i])>min(l[i],r[i])*2) res++; } printf("%d",res); return 0; }
B:
$dp[i][j][k]$表示前$i$项换$j$次末状态为$k$的最优解
每次分换或不换转移即可
#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define pb push_back typedef double db; typedef long long ll; typedef pair<int,int> P; const int MAXN=1e5+10; char s[10];int res=0; int n,m,dat[MAXN],dp[MAXN][25][5]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%s",s+1); if(s[1]=='H') dat[i]=0; else if(s[1]=='P') dat[i]=1; else dat[i]=2; } dp[1][0][dat[1]]=1; for(int i=1;i<n;i++) for(int j=0;j<=m;j++) for(int k=0;k<3;k++) { dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]+(k==dat[i+1])); for(int l=0;l<3;l++) if(l!=k) dp[i+1][j+1][l]=max(dp[i+1][j+1][l],dp[i][j][k]+(l==dat[i+1])); } for(int i=0;i<=m;i++) for(int j=0;j<3;j++) res=max(res,dp[n][i][j]); printf("%d",res); return 0; }
C:
一开始看到数据范围$n<20$感觉就是暴力……
最后发现用一个6维数组记录当前两点位置和朝向$bfs$就行了……
注意：
1、一个点到终点后就不再移动了！
2、学会用函数返回引用来简化代码，这样就不用每次写6维的数了……
#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define pb push_back typedef double db; typedef long long ll; typedef pair<int,int> P; const int MAXN=25; char s[MAXN]; struct node{int x1,y1,d1,x2,y2,d2;}; queue<node> q;int res=1<<30; int n,dat[MAXN][MAXN],d[25][25][4][25][25][4]; int dx[]={-1,0,1,0}; int dy[]={0,1,0,-1}; int nxt(int x){return (x+1)%4;} int pre(int x){return (x+3)%4;} void update(node x,node y) { int &a=d[x.x1][x.y1][x.d1][x.x2][x.y2][x.d2]; int &b=d[y.x1][y.y1][y.d1][y.x2][y.y2][y.d2]; if(a>b+1) a=b+1,q.push(x); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",s+1); for(int j=1;j<=n;j++) dat[i][j]=(s[j]=='E'); } memset(d,0x3f,sizeof(d)); //注意一个点到终点后就不动了 d[n][1][0][n][1][1]=0; q.push((node){n,1,0,n,1,1}); while(!q.empty()) { node t=q.front();q.pop(); node a=t,b=t,c=t; if(!(t.x1==1&&t.y1==n)) a.d1=nxt(a.d1),b.d1=pre(b.d1); if(!(t.x2==1&&t.y2==n)) a.d2=nxt(a.d2),b.d2=pre(b.d2); update(a,t);update(b,t); int fx1=c.x1+dx[c.d1],fx2=c.x2+dx[c.d2]; int fy1=c.y1+dy[c.d1],fy2=c.y2+dy[c.d2]; if(fx1>=1&&fy1<=n&&dat[fx1][fy1]&&!(c.x1==1&&c.y1==n)) c.x1=fx1,c.y1=fy1; if(fx2>=1&&fy2<=n&&dat[fx2][fy2]&&!(c.x2==1&&c.y2==n)) c.x2=fx2,c.y2=fy2; update(c,t); } for(int i=0;i<4;i++) for(int j=0;j<4;j++) res=min(res,d[1][n][i][1][n][j]); printf("%d",res); return 0; }