AtCoder Beginner Contest 286 解题报告
\(\text{By DaiRuiChen007}\)
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;
}
