cf-edu-round-49解题记录

罚时太长

Posted by ethan-zhou on July 17, 2020

注:这个解题主要详细讲T3,T4

T1

只需要找到每个位置对称的字符,看他们是否相差 +-2 或 0 即可。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,l;
char tmp[105];
int main(){
	scanf("%d",&n);
	while(n--){
		scanf("%d%s",&l,tmp+1);
		bool f=1;
		for(int i=1;(i<<1)<=l;i++)
			if(abs(tmp[i]-tmp[l-i+1])>2 || abs(tmp[i]-tmp[l-i+1])&1){
				f=0;
				break;
			}
		printf(f?"YES\n":"NO\n");
	}
	return 0;
}

T2

分类讨论即可,有点麻烦,需要细心

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long n,q;
int main(){
	scanf("%lld%lld",&n,&q);
	while(q--){
		long long x,y;
		scanf("%lld%lld",&x,&y);
		x--;
		long long res=0;
		long long l1=(n+1)>>1;
		long long l2=n>>1;
		if(!((x+y)&1)){
			res+=(n*n+1)>>1;
			swap(l1,l2);
		}
		res+=(l1+l2)*(x>>1)+(x&1?l1:0)+((y+1)>>1);
		printf("%lld\n",res);
	}
	return 0;
}

T3

\[\begin{aligned} S&=&ab,P=a+b\\ \frac{P^2}{S}&=&\frac{a^2+b^2}{ab}+2\\ &=&\frac a b+\frac b a+2\\ \end{aligned}\]

这一函数在ab越接近时取值越大,所以我们只需要讲所有的小棍按照长短排序,从头到尾扫一遍,找到长度相邻,且都有两个及以上的小木棍,计算他们的 P^2/S 即可。

注意:这个矩形可能是正方形

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int NR=1e6+5;
int t,n,arr[NR];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",arr+i);
		sort(arr+1,arr+1+n);
		int last=-1,cur=-1,curcnt=0;
		int mnlast,mncur;
		long long minfz=1e9,minfm=1;
		for(int i=1;i<=n;i++){
			if(curcnt==2 || arr[i]!=cur){
				if(curcnt>=2)last=cur;
				cur=arr[i];
				curcnt=1;
			}
			else if(++curcnt==2)
				if(last!=-1&&minfz*last*cur>minfm*(last+cur)*(last+cur)){
						minfz=(last+cur)*(last+cur);
						minfm=last*cur;
						mncur=cur;
						mnlast=last;
				}
		}
		printf("%d %d %d %d\n",mnlast,mnlast,mncur,mncur);
		
	}
	return 0;
}

T4

给你一个图,其中每个节点的出度都为 1,并要求从每个结点出发最终都能到达一个标记点,求所有标记点的权值的最小值。 首先经过分析,我们知道从任意一个点出发,其必定先经过一段链,再进入一个环。为了使这个环上的所有点符合题目要求,我们只需在这整个环上取个权值最小的一点即可,而只要取了这个点,那么之前链上的所有点也就符合要求了。

代码:(树状数组没啥必要)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int NR=2e5+5;
int n;
int c[NR],a[NR];
bool ins[NR];
long long res=0;
struct tarr{
	int arr[NR];
	int place[NR];
	int ind;
#define lbt(x) ((x)&(-x))
	tarr(){
		memset(arr,999999,sizeof(arr));
		memset(place,-1,sizeof(place));
		ind=n+1;
	}
	void mod(int x,int d){for(;x<=n;x+=lbt(x))arr[x]=min(arr[x],d);}
	bool hasvis(int p){return place[p]!=-1;}
	int calmin(int x){
		int ans=1e9;
		for(;x;x-=lbt(x))ans=min(ans,arr[x]);
		return ans;
	}
	void addp(int p){
		place[p]=--ind;
		mod(ind,c[p]);
	}
	int on_circle(int p){return calmin(place[p]);}

}t;
void dfs(int p){
	if(ins[a[p]]){
		res+=t.on_circle(a[p]);
		return;
	}
	if(t.hasvis(a[p]))return;
	ins[a[p]]=1;
	t.addp(a[p]);
	dfs(a[p]);
	ins[a[p]]=0;
}
int main(){
	scanf("%d",&n);
	t.ind=n+1;
	for(int i=1;i<=n;i++)scanf("%d",c+i);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	for(int i=1;i<=n;i++)
		if(!t.hasvis(i)){
			t.addp(i);
			ins[i]=1;
			dfs(i);
			ins[i]=0;
		}
	printf("%lld",res);
	

	return 0;
}

作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接


阅读量:


icon