B题没想到被坑了两次,极端情况明明也很好想,硬是WA了两发。
C题很想之前做过的经典蚂蚁题,但是又不太一样,
但分析之后,发现之后奇偶性相同才可能碰撞,那么分开处理,
假如已经有相向而行,肯定是最快碰撞的,用一个栈维护即可,最后就是剩下的肯定是
L L L ... R R R将它们配对即可。
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef long long ll;
const ll mo=1e9+7;
const int N=3e5+5;
struct node{
int x,d,id;
};
node a[N],b[N],c[N],s[N],t[N];
int n,ans[N],m,tot,top,cnt,x,y;
char ch;
bool cmp(node a,node b){
return a.x<b.x;
}
void work(){
top=0;
cnt=0;
sort(b+1,b+tot+1,cmp);
fo(i,1,tot){
if (b[i].d) {
s[++top]=b[i];
}
else{
if (top){
ans[s[top].id]=ans[b[i].id]=(b[i].x - s[top].x)/2;
top--;
}
else {
t[++cnt]=b[i];
}
}
}
fo(i,1,cnt/2) {
x=2*i-1; y=2*i;
ans[t[x].id]=ans[t[y].id]=(t[x].x+t[y].x)/2;
}
fo(i,1,top/2) swap(s[i],s[top-i+1]);
fo(i,1,top/2) {
x=2*i-1; y=2*i;
ans[s[x].id]=ans[s[y].id]=(m-s[x].x + m-s[y].x)/2;
}
if (cnt%2==1 && top%2==1) {
ans[t[cnt].id]=ans[s[top].id]=(m+t[cnt].x+m-s[top].x)/2;
}
}
int main() {
// freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
while (T--){
scanf("%d %d",&n,&m);
fo(i,1,n) ans[i]=0;
fo(i,1,n) {
scanf("%d",&a[i].x);
a[i].id=i;
}
fo(i,1,n) {
scanf("%c",&ch);
scanf("%c",&ch);
a[i].d=(ch=='R');
}
tot=0;
fo(i,1,n) {
if (a[i].x&1) b[++tot]=a[i];
}
work();
tot=0;
fo(i,1,n) {
if (a[i].x%2==0) b[++tot]=a[i];
}
work();
fo(i,1,n) {
if (ans[i]) printf("%d ",ans[i]);
else printf("%d ",-1);
}
printf("\n");
}
return 0;
}
D题很明显是N^2dp,首先我们注意到,1的相对顺序不可能改变,否则肯定不是最优的。
\(f[i][j]\)表示第i个1放在j位置的最小值,转移即可。
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef long long ll;
const ll mo=1e9+7;
const ll inf=1e9;
const int N=5005;
int f[N][N],g[N];
int a[N],p[N],tot,n,ans;
void cmin(int &x,int y){
x=min(x,y);
}
int main() {
// freopen("data.in","r",stdin);
scanf("%d",&n);
tot=0;
fo(i,1,n) {
scanf("%d",&a[i]);
if (a[i]==1) p[++tot]=i;
}
if (!tot) {
printf("%d",0);
return 0;
}
fo(i,0,n) fo(j,0,n) f[i][j]=inf;
fo(i,0,n) g[i]=0;
fo(i,1,tot) {
fo(j,1,n) {
if (!a[j]) cmin(f[i][j], g[j-1]+abs(p[i]-j));
}
g[0]=inf;
fo(j,1,n) g[j]=min(g[j-1], f[i][j]);
}
ans=inf;
fo(i,1,n) ans=min(ans, f[tot][i]);
printf("%d\n",ans);
return 0;
}
标签:Educational,Rated,const,int,Codeforces,tot,ans,include,fo
From: https://www.cnblogs.com/ganking/p/17653416.html