首页 > 其他分享 >Codeforces Round 910 (Div. 2)

Codeforces Round 910 (Div. 2)

时间：2023-11-29 20:44:20浏览次数：45  
标签：lc puts int Codeforces fo Div include 910 define

https://codeforces.com/contest/1898

C题可以造一个大小为4的环，然后再造一个来回，这样就解决了%4=0,%4=2的情况，而奇数的情况显然无解。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
#define R printf("%c ",'R')
#define B printf("%c ",'B')
#define BL puts("")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (ll (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))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll inf=1ll<<60;
const int N=1e6+5;
ll n,m,k,t;
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%lld %lld %lld",&n,&m,&k);
		t=(k-n-m+2);
		if (t<0 || (t%4)&1) {
			puts("NO"); continue;
		}
		
		puts("YES");
		fo(i,1,n-1) {
			fo(j,1,m-1) if (j&1) R; else B;
			BL;
		}
		if (n==3) {
			fo(j,1,m-1) if (j&1) R; else B; 
			BL;
		}
		else {
			fo(j,1,m-1) if ((n+j)&1) B; else R;
			BL;
		}

		
		
		B; B; fo(j,3,m) if (j&1) R; else B;
		BL;
		B; B; fo(j,3,m) if (j&1) B; else R;
		BL;
		
		fo(i,3,n-1) {
			fo(j,1,m) {
				if ((i+j)&1) B; else R;
			}
			BL;
		}
		
		
	}
	
	return 0;
}

D题显然应该是找两个不相交的区间才能增大。
设li<ri<lj<rj
则答案为2(lj-ri) 那么我们按l从小到大排序，维护最小的r就行。

感觉比c简单。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#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))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll mo=998244353;
const int inf=1<<30;
const int N=2e5+5;
struct node{
	ll x,y;
};
node a[N];
ll ans,n,mx;
bool cmp(node a,node b){
	return a.x<b.x;
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	
	int T;
	scanf("%d",&T);
	while (T--){
		ans=0;
		scanf("%lld",&n);
		fo(i,1,n) scanf("%lld",&a[i].x);
		fo(i,1,n) scanf("%lld",&a[i].y);
		fo(i,1,n) {
			ans+=abs(a[i].x-a[i].y);
			if (a[i].x>a[i].y) swap(a[i].x, a[i].y);
		}
		mx=0;
		
		sort(a+1,a+n+1,cmp);
		
		ll r=inf;
		fo(i,1,n) {
			r=min(r, a[i].y);
			mx=max(mx, 2ll*max(a[i].x-r,0ll)); 
		}
		
		printf("%lld\n",ans+mx);
	}

	return 0;
}

E
对于t，假设当前到第i位
我们需要在s中找到一个sj=ti，显然这个j应该越小越好，并假设我们已经s的前l的字符已经全部匹配或者删除。
然后我们考虑我们这个j这个位置对[l+1,j-1]这些字符的影响，对于排在ti之后的显然没有影响，小于ti的需要直接删除。
那么我们维护26个指针即可，记录每个字符当前的位置，检查是否有字符小于当前字符的指针在后面就行。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#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))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll inf=1ll<<60;
const int N=1e6+5;
char s[N],t[N];
int p[N],nex[N],n,m,c,r[30];
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d %d",&n,&m);
		scanf("%s",s+1);
		scanf("%s",t+1);
		
		memset(r,0,sizeof(r));

		fo(i,0,25) p[i]=n+1;
		
		fd(i,n,1) {
			c=s[i]-'a';
			nex[i]=p[c];
			p[c]=i;
		}
		
		bool flag=1;
		
		fo(i,1,m) {
			c=t[i]-'a';
			while (p[c]<=r[c] && p[c]!=n+1) {
				p[c]=nex[p[c]];
			}
			
			if (p[c]==n+1)  {
				flag=0;
				break;
			}
			else {
				fo(i,0,c-1) r[i]=max(r[i], p[c]);
				p[c]=nex[p[c]];
			}
		}
		
		if (flag) A;
		else B;
	}
	
	
	return 0;
}

F
首先特判type1，type2，
type3最后一定是剩下两个出口，对于一个点，
d1(i,j)+d2(i,j)+d(i,j)
d1，d2分别表示到两个出口的距离，然后d表示到v的距离，也就是两条路在这之后合并了。

那么bfs即可，每个点只会进入两次。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
//#define A puts("YES")
//#define B puts("NO")
#define A puts("Yes")
#define B puts("No")
#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))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const int inf=1<<30;
const int N=1005;
int n,m,sx,sy,a[N][N],d1[N][N],dis[N][N],f[N][N];
int x,y,xx,yy,z,d;
char s[N];
bool vis[N][N];
int w[4][2]={
	1,0,
	-1,0,
	0,1,
	0,-1
};
struct node{
	int x,y,z,d;
};
queue<node> q;
bool pd(int x,int y){
	return (1<=x && x<=n && 1<=y && y<=m && a[x][y]);
}
bool isborder(int x,int y){
	return (x==1 || x==n || y==1 || y==m);
}
void work(int x,int y){
	if (!pd(x,y)) return;
	f[x][y]=(x-1)*n+y;
	q.push((node){x,y,(x-1)*n+y});
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);

	int T;
	scanf("%d",&T);
	while (T--){
		int sum=0;
		
		scanf("%d %d",&n,&m);
		fo(i,1,n){
			scanf("%s",s+1);
			fo(j,1,m) {
				if (s[j]=='#') a[i][j]=0;
				else a[i][j]=1,sum++;
				
				if (s[j]=='V') {
					sx=i; sy=j;
				}
			}
		}

		while (!q.empty()) q.pop();
		fo(i,1,n) fo(j,1,m) {
			vis[i][j]=0;
			d1[i][j]=inf;
		}
		
		vis[sx][sy]=1;
		d1[sx][sy]=0;
		q.push((node){sx,sy});
		
		int cnt=0,dm=inf;
		if (isborder(sx,sy)) {
			cnt++;
			dm=0;
		}
	
		while (!q.empty()) {
			x=q.front().x;
			y=q.front().y;
			q.pop();
			
			fo(i,0,3){
				xx=x+w[i][0];
				yy=y+w[i][1];
				
				if (!pd(xx,yy) || vis[xx][yy]) continue;
				d1[xx][yy]=d1[x][y]+1;
				
				if (isborder(xx,yy)) {
					cnt++;
					dm=min(dm,d1[xx][yy]);
				}
				vis[xx][yy]=1;
				q.push((node){xx,yy});
			}
		}
		if (!cnt) {
			printf("%d\n",sum-1);
			continue;
		}
		if (cnt==1) {
			printf("%d\n",sum-dm-1);
			continue;
		}
	
		fo(i,1,n) fo(j,1,m) {
			vis[i][j]=0;
			f[i][j]=dis[i][j]=0;
		}
		
		fo(i,1,m) {
			work(1,i);
			work(n,i);
		}
		
		fo(i,1,n) {
			work(i,1);
			work(i,m);
		}
		
		while (!q.empty()) {
			x=q.front().x; y=q.front().y;  z=q.front().z; d=q.front().d;
			q.pop();
			
			fo(i,0,3) {
				xx=x+w[i][0];
				yy=y+w[i][1];
				
				if (!pd(xx,yy) || vis[xx][yy]) continue;
				
				if (!f[xx][yy]) {
					f[xx][yy]=z;
					dis[xx][yy]=d+1;
					q.push((node){xx,yy,z,d+1});
				}
				else {
					if (f[xx][yy]!=z) {
						f[xx][yy]=z;
						dis[xx][yy]+=d+1;
						vis[xx][yy]=1;
						q.push((node){xx,yy,z,d+1});
					}
				}
			}
		}
		
		int ans=0;
		fo(i,1,n) fo(j,1,m) {
			if (d1[i][j]!=inf) {
				ans=max(ans, sum-dis[i][j]-d1[i][j]-1);
				
				
				
				if (dis[i][j]+d1[i][j]==0) printf("%d %d\n",i,j);
			}
		}
		
		printf("%d\n",ans);
		

		
	}
	return 0;
}

标签：lc,puts,int,Codeforces,fo,Div,include,910,define
From： https://www.cnblogs.com/ganking/p/17865789.html

相关文章

  • Codeforces Round 829 (Div. 1)A1. Make Nonzero Sum (easy version)(思维找规律)
    先考虑无解的情况：当n为奇数时无解相邻的两个元素一定可以变成0\[a[i]!=a[i+1]时，分成[i,i],和[i+1,i+1]\]\[a[i]=a[i+1]时，分成[i,i+1]\]这两种情况对答案的贡献都是0，当n为奇数时我们总会有一个没办法凑成0.#include<bits/stdc++.h>#definelsp<<1#......
  • Educational Codeforces Round 158 (Rated for Div. 2)
    A.LineTripThereisaroad,whichcanberepresentedasanumberline.Youarelocatedinthepoint\(0\)ofthenumberline,andyouwanttotravelfromthepoint\(0\)tothepoint\(x\),andbacktothepoint\(0\).Youtravelbycar,whichs......
  • CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
    看到B官方题解写了一堆，而如果能注意到一些性质，几行就写完了题意：给一个A，B构成的字符串，可以将“AB”翻转成"BA",问最多可以进行多少次翻转？实际上在手动模拟以后发现，由于题目限制了每个位置只能翻转一次，所以情况简单了不少。只要还没过最后一个B，那么最后一个B之前的所有A就会被反......
  • Codeforces Round 911 (Div. 2) D
    CodeforcesRound911(Div.2)DD.SmallGCD题意定义\(f(a,b,c)\)为\(a,b,c\)中较小两个数的\(gcd\),给定数组\(a_{1...n}\),求\(\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n}\sum\limits_{k=j+1}^{n}f(a_i,a_j,a_k)\)题解显然可以先排序,不会影响结果,排完序后\(a_k\)就......
  • CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
    CodeTONRound7(Div.1+Div.2,Rated,Prizes!)A-JaggedSwaps思路：a2到an的数只要相邻为逆序都可以交换，只需要判断a1是否为1即可#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#defineint__int128#definedoublelongdoubletypedefpai......
  • Codeforces Round 903 (Div. 3)
    CodeforcesRound903(Div.3)A.Don'tTrytoCount大概题意给你两个字符串a,b。a串可进行的操作为将整个a串复制到之前的a串后面（直接用a+a即可），然后看操作多少次可以让b串变为a串的子串如果不能就输出-1。#include<iostream>usingnamespacestd;stringa,b;voidsolve()......
  • Codeforces Round 894 (Div. 3)
    CodeforcesRound894(Div.3)A.GiftCarpet题意：判断一列一个字母有没有“vika”思路：挨个枚举每一列#include<bits/stdc++.h>usingnamespacestd;charmp[25][25];charx[]={'v','i','k','a'};voidsolve(){intm,n;cin>>......
  • Codeforces Round 911 (Div. 2) D. Small GCD
    题目链接：https://codeforces.com/contest/1900/problem/D对于已经排序好的数组\(a\)，我们需要计算：\[\sum_{i=1}^n\sum_{j=i+1}^ngcd(a_i,a_j)*(n-j)\]由于\(\sum_{d|n}\phi(d)=n\)，因此：\[\gcd(a_i,a_j)=\sum_{d|a_i,d|a_j}\psi(d)\]代入可得：\[\sum_{i=1}^n\su......
  • CodeforcesDS1
    CodeforcesDS1CF387EGeorgeandCards（2200）Problem给出一个\(1\)到\(n\)的排列（输入中的数组\(p\)），并给出一个长为\(k\)的数组\(b\)，要求从\(p\)中删去\(n-k\)个元素后得到数组\(b\)。删除操作的定义：选取一个区间\([l,r]\)，删去其中最小的元素，并获得\(r-l......
  • CodeforcesDP1
    CodeforcesDP1CF833BTheBakery（2200）Problem将一个长度为\(n\)的序列\(a\)分为\(k\)段，使得总价值最大。一段区间的价值表示为区间内不同数字的个数。\(n\leq35000,k\leqmin(n,50),1\lea_i\len\)。Solution记\(f_{i,l,j}\)表示考虑前\(i\)个数，划分成\(......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99