首页 > 其他分享 >AtCoder Beginner Contest 286 解题报告

AtCoder Beginner Contest 286 解题报告

时间：2023-01-22 18:44:13浏览次数：67  
标签：AtCoder const Beginner Contest int hull Vector MAXN double

AtCoder Beginner Contest 286 解题报告

\(\text{By DaiRuiChen007}\)

Contest Link

A. Range Swap

直接模拟交换过程即可

时间复杂度 \(\Theta(n)\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=101;
int a[MAXN];
signed main() {
	int n,p,q,r,s;
	scanf("%d%d%d%d%d",&n,&p,&q,&r,&s);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int l=0;l<=q-p;++l) swap(a[p+l],a[r+l]);
	for(int i=1;i<=n;++i) printf("%d ",a[i]);
	puts("");
	return 0;
}

B. Cat

利用 STL string 容器中的 find 与 insert 函数进行模拟即可

时间复杂度 \(\Theta(n^2)\)

#include<bits/stdc++.h>
using namespace std;
signed main() {
	int n;
	string S;
	cin>>n>>S;
	while(true) {
		if(S.find("na")==string::npos) break;
		S.insert(S.find("na")+1,"y");
	}
	cout<<S<<"\n";
	return 0;
}

C. Rotate and Palindrome

枚举 \(S\) 的每个循环同构串，对每个循环同构串用 \(\Theta(n)\) 的时间暴力扫描每一对相对的字符，如果不相等就用 \(b\) 的代价修改其中的一个即可

时间复杂度 \(\Theta(n^2)\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,b;
inline int calc(string S) {
	int ret=0,n=(int)S.length();
	for(int i=0;i<n;++i) if(S[i]==S[n-i-1]) ++ret;
	return(n-ret)/2;
}
signed main() {
	string S;
	cin>>n>>a>>b>>S;
	int ans=b*calc(S);
	S=S+S;
	for(int i=1;i<n;++i) ans=min(ans,a*i+b*calc(S.substr(i,n)));
	cout<<ans<<"\n";
	return 0;
}

D. Money in Hand

多重背包模板题，直接暴力 dp 转移即可

时间复杂度 \(\Theta(x\sum b_i)\)

#include<bits/stdc++.h>
const int MAXN=1e4+1;
int a[MAXN];
bool dp[MAXN];
signed main() {
	int n,m=0,x;
	scanf("%d%d",&n,&x);
	for(int i=1;i<=n;++i) {
		int cnt,val;
		scanf("%d%d",&val,&cnt);
		while(cnt--) a[++m]=val;
	}
	dp[0]=true;
	for(int i=1;i<=m;++i) {
		for(int j=x;j>=a[i];--j) {
			dp[j]|=dp[j-a[i]];
		}
	}
	puts(dp[x]?"Yes":"No");
	return 0;
}

E. Souvenir

对每条路径按长度为第一关键字，权值和为第二关键字升序排序，Floyd 全源最短路维护即可

时间复杂度 \(\Theta(n^3)\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=301,INF=1e18;
struct node {
	int dist,val;
	node() { dist=val=0; }
	node(int _dist,int _val) { dist=_dist,val=_val; }
	inline friend bool operator <(const node &A,const node &B) {
		if(A.dist==B.dist) return A.val>B.val;
		return A.dist<B.dist;
	}
	inline friend node operator +(const node &A,const node &B) {
		return node(A.dist+B.dist,A.val+B.val);
	}
}	f[MAXN][MAXN];
inline node better(const node &A,const node &B) {
	return A<B?A:B;
}
int a[MAXN];
char ch[MAXN][MAXN];
signed main() {
	int n;
	scanf("%lld",&n);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	for(int i=1;i<=n;++i) {
		scanf("%s",ch[i]+1);
		for(int j=1;j<=n;++j) {
			if(i==j) f[i][j]=node(0,0);
			else if(ch[i][j]=='Y') f[i][j]=node(1,a[j]);
			else f[i][j]=node(INF,0);
		}
	}
	for(int k=1;k<=n;++k) {
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=n;++j) {
				f[i][j]=better(f[i][j],f[i][k]+f[k][j]);
			}
		}
	}
	int q;
	scanf("%lld",&q);
	while(q--) {
		int u,v;
		scanf("%lld%lld",&u,&v);
		if(f[u][v].dist==INF) puts("Impossible");
		else printf("%lld %lld\n",f[u][v].dist,a[u]+f[u][v].val);
	}
	return 0;
}

F. Guess The Number 2

考虑把 \(\{a_i\}\) 写成若干个置换环的形式，对于一个大小为 \(k\) 的置换环，根据 \(\{b_i\}\) 中的置换环的形态，我们能够得到 \(n\bmod k\) 的余数的值

构造一组互质的模数 \(\{p_i\}\)，使 \(\prod p_i\ge 10^9,\sum p_i\le 110\)，用 CRT 求解即可

给一组合法的构造：\(\{p_i\}=\{4,9,5,7,11,13,17,19,23\},\sum p_i=108,\prod p_i\approx 1.3\times 10^9\)

时间复杂度 \(\Theta(m)\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int B=1338557220;
const int p[9]={4,9,5,7,11,13,17,19,23};
const int MAXN=111;
vector <int> id[9];
int a[MAXN],b[MAXN],x[9];
signed main() {
	for(int i=0;i<9;++i) {
		int d=B/p[i];
		for(int j=1;j<p[i];++j) {
			if((d*j)%p[i]==1) {
				x[i]=d*j;
				break;
			}
		}
	}
	int m=0;
	for(int i=0;i<9;++i) {
		for(int j=0;j<p[i];++j) {
			id[i].push_back(++m);
		}
		for(int j=0;j<p[i];++j) {
			a[id[i][j]]=id[i][(j+1)%p[i]];
		}
	}
	cout<<m<<endl;
	for(int i=1;i<=m;++i) cout<<a[i]<<" ";
	cout<<endl;
	for(int i=1;i<=m;++i) cin>>b[i];
	int ans=0; 
	for(int i=0;i<9;++i) {
		for(int r=0;r<p[i];++r) {
			if(b[id[i][0]]==id[i][r]) {
				ans=(ans+x[i]*r%B)%B;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

G. Unique Walk

删除所有 \(\mathbf S\) 中的边然后缩点，可以证明原问题就等价于在新图上判断欧拉通路的存在性，用并查集维护连通块然后计算点的度数奇偶性判断即可

时间复杂度 \(\Theta(n\alpha(n))\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1;
int dsu[MAXN],ver[MAXN][2],e[MAXN],deg[MAXN];
bool inq[MAXN];
inline int find(int x) {
	if(dsu[x]==x) return x;
	return dsu[x]=find(dsu[x]);
}
signed main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) dsu[i]=i;
	for(int i=1;i<=m;++i) scanf("%d%d",&ver[i][0],&ver[i][1]);
	int k;
	scanf("%d",&k);
	for(int i=1;i<=k;++i) scanf("%d",&e[i]),inq[e[i]]=true;
	for(int i=1;i<=m;++i) {
		if(inq[i]) continue;
		int x=find(ver[i][0]),y=find(ver[i][1]);
		if(x!=y) dsu[x]=y;
	}
	for(int i=1;i<=k;++i) {
		++deg[find(ver[e[i]][0])],++deg[find(ver[e[i]][1])];
	}
	int cnt=0;
	for(int i=1;i<=n;++i) if(deg[i]%2==1) ++cnt;
	puts((cnt==0||cnt==2)?"Yes":"No");
	return 0;
}

Ex. Don't Swim

将 \(n+2\) 个点求一遍凸包，若 \(S\) 或 \(T\) 不在凸包里，答案直接是两个点的距离，如果都在凸包里，答案就是两侧的两条路径中较短的一条

维护一个二维凸包即可

时间复杂度 \(\Theta(n\log n)\)

#include<bits/stdc++.h>
#define double long double
using namespace std;
const double eps=1e-15;
struct Point {
	double x,y;
	Point() { x=0,y=0; }
	Point(double _x,double _y) { x=_x,y=_y; }
};
typedef Point Vector;
inline Vector operator +(const Vector &A,const Vector &B) {
	return Vector(A.x+B.x,A.y+B.y);
}
inline Vector operator -(const Point &A,const Point &B) {
	return Vector(A.x-B.x,A.y-B.y);
}
inline Vector operator *(const Vector &A,const double &k) {
	return Vector(A.x*k,A.y*k);
}
inline Vector operator /(const Vector &A,const double &k) {
	return Vector(A.x/k,A.y/k);
}
inline int sign(const double &x) {
	if(fabs(x)<eps) return 0;
	return (x>0)?1:-1;
}
inline bool operator <(const Vector &A,const Vector &B) {
	if(sign(A.x-B.x)==0) return A.y<B.y;
	return A.x<B.x;
}
inline bool operator ==(const Vector &A,const Vector &B) {
	return sign(A.x-B.x)==0&&sign(A.y-B.y)==0;
}
inline double Dot(const Vector &A,const Vector &B) {
	return A.x*B.x+A.y*B.y; 
}
inline double Length(const Vector &A) {
	return sqrt(Dot(A,A));
}
inline double Angle(const Vector &A,const Vector &B) {
	return acos(Dot(A,B)/(Length(A)*Length(B)));
}
inline double Cross(const Vector &A,const Vector &B) {
	return A.x*B.y-A.y*B.x;
}
inline Vector Rotate(const Vector &A,const double &ang) {
	return Vector(A.x*cos(ang)-A.y*sin(ang),A.x*sin(ang)+A.y*cos(ang));
}
inline double PolyArea(vector <Point> poly) {
	double area=0;
	int n=(int)poly.size();
	for(int i=1;i<n;++i) area+=Cross(poly[i]-poly[0],poly[i+1]-poly[0])/2;
	return area;
}
inline vector<Point> ConvexHull(vector <Point> p) {
	int n=(int)p.size();
	sort(p.begin(),p.end());
	int k=0;
	vector <Point> hull(2*n);
	for(int i=0;i<n;++i) {
		while(k>1&&Cross(hull[k-1]-hull[k-2],p[i]-hull[k-2])<=0) --k;
		hull[k++]=p[i];
	}
	int m=k;
	for(int i=n-2;i>=0;--i) {
		while(k>m&&Cross(hull[k-1]-hull[k-2],p[i]-hull[k-2])<=0) --k;
		hull[k++]=p[i];
	}
	hull.resize((n>1)?(k-1):k);
	return hull;
}
signed main() {
	int n;
	scanf("%d",&n);
	Point s,t;
	vector <Point> p(n+2);
	for(int i=0;i<n;++i) scanf("%Lf%Lf",&p[i].x,&p[i].y);
	scanf("%Lf%Lf%Lf%Lf",&s.x,&s.y,&t.x,&t.y);
	p[n]=s,p[n+1]=t;
	int ids=-1,idt=-1;
	vector <Point> hull=ConvexHull(p);
	int m=hull.size();
	for(int i=0;i<m;++i) {
		if(hull[i]==s) ids=i;
		if(hull[i]==t) idt=i;
	}
	if(ids==-1||idt==-1) {
		printf("%.12Lf\n",Length(s-t));
		return 0;
	}
	double dist1=0,dist2=0;
	for(int i=ids;i!=idt;i=(i+1)%m) dist1+=Length(hull[i]-hull[(i+1)%m]);
	for(int i=idt;i!=ids;i=(i+1)%m) dist2+=Length(hull[i]-hull[(i+1)%m]);
	printf("%.12Lf",min(dist1,dist2));
	return 0;
}

标签：AtCoder,const,Beginner,Contest,int,hull,Vector,MAXN,double
From： https://www.cnblogs.com/DaiRuiChen007/p/17064565.html

相关文章

  • AtCoder Beginner Contest 286
    A-RangeSwap(abc286a)题目大意给定长度为\(n\)的数组\(a\)和\(p,q,r,s\)，交换\(a[p..q]\)和\(a[r..s]\)并输出交换后的数组\(a\)。解题思路模拟即可。神奇......
  • D - Change Usernames -- ATCODER
    D-ChangeUsernameshttps://atcoder.jp/contests/abc285/tasks/abc285_d 思路DFS深度遍历图。需要注意的是，整个大图中可能有很多小的连通子图，每个子图需要确定起......
  • #0030. 「JOI Open Contest 2021」Crossing
    题目大意题目给了三个仅包含J,O,I三个字母的长度为\(N\)的字符串及某种crossing的规则。另外还给了一个相同长度的字符串\(N\),且有\(Q\)次更新，每次把该字符串一个区间......
  • #0029. 「JOI Open Contest 2021」Financial Report
    碎碎念1：是的时隔两年多笨人又想开始更博客了碎碎念2：另外今年就要AFO了希望能给自己的oi生涯画上一个完美的句号！题目大意给定\(N\)个数字和\(D\)需要从中选择一些数字......
  • AtCoder Beginner Contest 043
    A-ChildrenandCandies(ABCEdit)n=int(input())print(n*(n+1)//2)B-UnhappyHacking(ABCEdit)用栈模拟一下？但是栈的遍历比较麻烦这里用vector实现#......
  • AtCoder Beginner Contest 047
    A-FightingoverCandies签到#include<bits/stdc++.h>usingnamespacestd;intread(){...}constintN=1e6+5;intmain(){inta=read(),b=read(......
  • Atcoder ABC 285 题解
    E-WorkorRest题意​ 一周有\(n\)天，给出一个长度为\(n\)的数组\(A\)。你可以决定一周中的休息日与工作日的分布，请问如何选择能够使总贡献最大。​ 如何计算贡献......
  • AtCoder Beginner Contest 285 E(背包dp)
    E-WorkorRest题目大意：给定一周有n天，其中至少有1天为休息日，其余为工作日。同时给定一个长度为n的整型数组A，对于一个工作日，它能产生的工作值为A\(_{min(x,y)}\),其中x......
  • AtCoder Beginner Contest 282(G 填坑dp)
    G-SimilarPermutation题目大意：如果两个排列A=(A\(_1\),A\(_2\),A\(_3\)....A\(_N\)),B=(B\(_1\),B\(_2\),B\(_3\)....B\(_N\))满足：(A\(_i\)-A\(_{i+1}\))(B\(_......
  • AtCoder Regular Contest 153（持续更新）
    PrefaceB题粗糙了改了好几个版本，最后索性从头理了一遍思路才过然后剩下40min想C又歪了（构造题精通的被动消失了），还剩25min的时候忍不住了看LPL去了话说现在的ARC感觉和以......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99