首页 > 其他分享 >Educational Codeforces Round 109 (Rated for Div. 2)

Educational Codeforces Round 109 (Rated for Div. 2)

时间:2023-08-24 10:11:42浏览次数:44  
标签:Educational Rated const int Codeforces tot ans include fo

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

相关文章

  • 「题解」Codeforces 825G Tree Queries
    点权转边权,把边权设为两个端点的\(\min\),然后发现询问\(x\)的答案,就是询问\(x\)与所有黑点的虚树,边权的\(\min\)是多少。假设要判定答案是否\(\geqk\),那么就是询问\(x\)只经过\(\geqk\)是否能到达所有黑点,于是想到建立Kruskal重构树,那么\(x\)与所有黑点的LCA......
  • 「题解」Codeforces 1063F String Journey
    先reverse一下。不难看出选出的字符串长度为\(1,2,\cdots,k\)一定不劣,仅考虑这种形式的。然后考虑一手dp,设\(f_{i}\)表示最后一个子串是\(i\)为结尾,最长长度是多少。这样转移就是\(f_i\getsf_{j}+1,iff\s[j-f_j+1,j]\text{is}s[i-f_j,i]\text{'ssubstring}\)......
  • Educational Codeforces Round 153 (Rated for Div. 2)
    Preface最近CF状态烂得一批,已经连续两场被D题腐乳了,再这样下去就真成抱队友大腿的混子了但没想到因为D题比赛时贪心过的人太多了,后面一波叉掉了比赛时过的\(\frac{1}{3}\)的人导致竟然还能上分我是没想到的没抓住暑假大好的上分机会,等开学后再想冲分就难咯A.NotaSubstring......
  • Codeforces Round 893 (Div. 2) A-C题解
    CF893(Div.2)A.Buttons签到题。两人会优先选择c中的按钮来,避免自己的按钮消耗同时减少对方可选择的按钮。所以c%2==1等价于a的按钮数+1,c%2==0时相当于c按钮不存在,比较ab按钮的数量来得出答案即可。#include<iostream>usingnamespacestd;typedeflonglong......
  • Codeforces EduRound153 Editorial
    A如果有\(()\)那么肯定是不合法的有两种很简单的构造,()()()()...()和((((...)))),如果一个串是第一种构造的子串那么一定不是第二种构造的子串,反之亦然。使用python取之B把\(m\%k\)的余数补齐,再把多出来的\(1\)价格regularcoins\(m\)个一组f使用python取之C......
  • Educational Codeforces Round 153 (Rated for Div. 2)
    EducationalCodeforcesRound153(RatedforDiv.2)A-NotaSubstring思路:找到串中最大的层数,若层数为1,构造层数大于1的即可;若层数大于1,构造层数为1的即可#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#defineint__int128#definedoublel......
  • Educational Codeforces Round 153 (Rated for Div. 2)
    EducationalCodeforcesRound153(RatedforDiv.2)这次的div2有点难度,当时b题思路对了,但是没有写好A题传送门A题意:给你一个只包含'('和')'的字符串,要求你将他的长度扩大一倍,并且使得所有括号匹配且组成的序列当中不能存在原序列的子序列A思路:这道题一开始写的时候没有注......
  • Codeforces Round 881 (Div. 3)
    比赛链接:https://codeforces.com/contest/1843A.SashaandArrayColoring题意:一个数组,可以任意分成任意组,每组的贡献是组最大值减最小值,求最大总贡献思路:一组内只有最大值和最小值有用,所以每组只由两个数组成即可,用贪心的思路,依次取出原数组的最大和最小值成组即可B.LongL......
  • Codeforces Round 893 (Div. 2)
    Preface最战俘的一场,B题写挂一发后整个人脑子就不清醒了,放着D不写去写E1,然后忘了可持久化栈有一个经典的倍增写法,最主要当时暑假前集训我还上去讲了这个东西然后比赛的时候还没想起来后面目送徐神爆切5题成功完成两场从蓝上橙,狠狠地把我这个在紫卡了半年的废物羞辱了一波不过确......
  • Educational Codeforces Round 109 (Rated for Div. 2)
    EducationalCodeforcesRound109(RatedforDiv.2)A-Potion-making思路:求最小操作数即药水最简比#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#defineint__int128#definedoublelongdoubletypedefpair<int,int>PII;typedefpair......