layout: post
title: (寒假开黑gym)2018 ACM-ICPC, Syrian Collegiate Programming Contest
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
Hello SCPC 2018! (签到)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct node{
int value,id;
}a[maxn];
int cmp(node a,node b){
return a.value<b.value;
}
int f[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("hello.in","r",stdin);
int t;
cin>>t;
while(t--){
for(int i=1;i<=12;i++)cin>>a[i].value,a[i].id=i;
sort(a+1,a+1+12,cmp);
memset(f,0,sizeof(f));
for(int i=1;i<=4;i++)f[a[i].id]=i;
int flag=0;
for(int i=1;i<=4;i++){
if(f[i]!=i){
flag=1;
}
}
if(flag)cout<<"no"<<endl;
else cout<<"yes"<<endl;
}
return 0;
}
Binary Hamming (签到)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
char s[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("hamming.in","r",stdin);
int t;
cin>>t;
while(t--){
int n,a1=0,b1=0,a2=0,b2=0;
cin>>n;
cin>>s;
for(int i=0;i<n;i++)if(s[i]=='1')a1++;else b1++;
cin>>s;
for(int i=0;i<n;i++)if(s[i]=='1')a2++;else b2++;
cout<<min(a1,b2)+min(b1,a2)<<endl;
}
return 0;
}
Portals (模拟,分类讨论)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
char s[maxn];
int dx[2]={1,-1};
int n;
int S,T;
int dfs(int x,int i){
if(x==n+1)return 0;
if(x==0)return 0;
if(s[x]=='#')return 0;
if(s[x]=='o')return 1;
if(s[x]=='s'||s[x]=='e')return 1;
return dfs(x+dx[i],i);
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("portals.in","r",stdin);
int t;
cin>>t;
while(t--){
cin>>n;
for(int i=0;i<=n+10;i++)s[i]='#';
cin>>s+1;
int len=strlen(s+1);
for(int i=1;i<=n;i++){
if(s[i]=='s')S=i;
if(s[i]=='e')T=i;
}
int neds=dfs(S+1,0)+dfs(S-1,1);
int nedt=dfs(T+1,0)+dfs(T-1,1);
int ans=1e9;
if(s[S-1]=='o'||s[S+1]=='o'||s[S-1]=='e'||s[S+1]=='e')neds=1e9;
if(s[T-1]=='o'||s[T+1]=='o'||s[T-1]=='s'||s[T+1]=='s')nedt=1e9;
ans=min(neds,nedt);
if(ans==1e9)cout<<-1<<endl;
else cout<<ans<<endl;
}
return 0;
}
Carnival Slots （DP，记忆化搜索）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
char mp[550][550];
ll dp[505][505];
ll num[550];
ll value[550];
int r,c;
ll dfs(int x,int y){
if(x==r+1){
return value[y];
}
if(dp[x][y]!=-1)return dp[x][y];
ll ans=0;
ans=dfs(x+1,y);
if(y-1>=1&&mp[x][y]!='.')ans=max(ans,dfs(x+1,y-1));
if(y+1<=c&&mp[x][y]!='.')ans=max(ans,dfs(x+1,y+1));
return dp[x][y]=ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("balls.in","r",stdin);
int t;
cin>>t;
while(t--){
cin>>r>>c;
for(int i=1;i<=c;i++)cin>>num[i];
for(int i=1;i<=r;i++){
cin>>mp[i]+1;
}
for(int i=1;i<=c;i++)cin>>value[i];
ll ans=0;
memset(dp,-1,sizeof(dp));
for(int i=1;i<=c;i++){
ans+=dfs(1,i)*num[i]*1LL;
}
cout<<ans<<endl;
}
return 0;
}
Bugged System (模拟)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int x[maxn];
struct node{
int s,d;
}my[maxn];
int in[maxn];
int out[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("bugged.in","r",stdin);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>x[i];
ll ans=0;
for(int i=1;i<=m;i++){
cin>>my[i].s>>my[i].d;
in[my[i].s]++;
out[my[i].d]++;
ans+=abs(x[my[i].s]-x[my[i].d]);
}
bool f=0;
for(int i=1;i<=n;i++){
if(in[i]!=out[i])f=1;
in[i]=out[i]=0;
}
if(f)cout<<"-1"<<endl;
else cout<<ans<<endl;
}
return 0;
}
Tourists' Tour (染色问题，拓扑)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
vector<int>ve[maxn];
void add(int u,int v){
ve[v].push_back(u);
ve[u].push_back(v);
}
int color[maxn];
int vis[10];
int mx;
void dfs(int now){
// cout<<"now="<<now<<endl;
memset(vis,0,sizeof(vis));
for(int i=0;i<ve[now].size();i++){
vis[color[ve[now][i]]]=1;
}
for(int i=1;i<10;i++){
if(!vis[i]){
color[now]=i;
break;
}
}
mx=max(mx,color[now]);
for(int i=0;i<ve[now].size();i++)if(!color[ve[now][i]])dfs(ve[now][i]);
}
int a[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("tour.in","r",stdin);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],ve[i].clear();
stack<int>pq;
pq.push(1);
for(int i=2;i<=n;i++){
while(!pq.empty()&&a[pq.top()]<a[i])pq.pop();
if(!pq.empty()){
add(pq.top(),i);
}
pq.push(i);
}
stack<int>q;
q.push(n);
for(int i=n-1;i>=1;i--){
while(!q.empty()&&a[q.top()]<a[i])q.pop();
if(!q.empty()){
add(q.top(),i);
}
q.push(i);
}
for(int i=1;i<=n;i++)reverse(ve[i].begin(),ve[i].end());
for(int i=1;i<=n;i++)color[i]=0;
mx=0;
for(int i=1;i<=n;i++)if(color[i]==0)dfs(i);
cout<<mx<<endl;
for(int i=1;i<=n;i++)cout<<color[i]<<" ";
cout<<endl;
}
return 0;
}
Is Topo Logical? (模拟)
Rise of the Robots (最小圆覆盖)
思路
首先感谢付队的模板！太快了
这题可以把题意转化成求点到所有直线距离的最短距离,然后为什么答案要取反呢，因为我们一开始是以原点为起点的
然后答案给出的是圆心为起点的，所以我们要把这个起点缩回原点。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
#define mp make_pair
const double eps=1e-8;
const double pi=4*atan(1.0);
struct point{
double x,y;
point(double a=0,double b=0):x(a),y(b){}
};
int dcmp(double x){ return fabs(x)<eps?0:(x<0?-1:1);}
point operator +(point A,point B) { return point(A.x+B.x,A.y+B.y);}
point operator -(point A,point B) { return point(A.x-B.x,A.y-B.y);}
point operator *(point A,double p){ return point(A.x*p,A.y*p);}
point operator /(point A,double p){ return point(A.x/p,A.y/p);}
point rotate(point A,double rad){
return point(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}
bool operator ==(const point& a,const point& b) {
return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double dot(point A,point B){ return A.x*B.x+A.y*B.y;}
double det(point A,point B){ return A.x*B.y-A.y*B.x;}
double dot(point O,point A,point B){ return dot(A-O,B-O);}
double det(point O,point A,point B){ return det(A-O,B-O);}
double length(point A){ return sqrt(dot(A,A));}
double angle(point A,point B){ return acos(dot(A,B)/length(A)/length(B));}
double distoline(point P,point A,point B)
{
//点到直线距离
point v1=B-A,v2=P-A;
return fabs(det(v1,v2)/length(v1));
}
double distoseg(point P,point A,point B)
{
//点到线段距离
if(A==B) return length(P-A);
point v1=B-A,v2=P-A,v3=P-B;
if(dcmp(dot(v1,v2))<0) return length(v2);
else if(dcmp(dot(v1,v3))>0) return length(v3);
return fabs(det(v1,v2)/length(v1));
}
double Ployarea(vector<point>p)
{
//多边形面积
double ans=0; int sz=p.size();
for(int i=1;i<sz-1;i++) ans+=det(p[i]-p[0],p[i+1]-p[0]);
return ans/2.0;
}
bool SegmentProperIntersection(point a1,point a2,point b1,point b2) {
//规范相交
double c1=det(a2-a1,b1-a1),c2=det(a2-a1,b2-a1);
double c3=det(b2-b1,a1-b1),c4=det(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
bool isPointOnSegment(point p,point a1,point a2)
{
//点是否在线段上
return dcmp(det(a1-p,a2-p)==0&&dcmp(dot(a1-p,a2-p))<0);
}
int isPointInPolygon(point p,vector<point>poly)
{
//判断点与多边形的位置关系
int wn=0,sz=poly.size();
for(int i=0;i<sz;i++){
//在边上
if(isPointOnSegment(p,poly[i],poly[(i+1)%sz])) return -1;
int k=dcmp(det(poly[(i+1)%sz]-poly[i],p-poly[i]));
int d1=dcmp(poly[i].y-p.y); int d2=dcmp(poly[(i+1)%sz].y-p.y);
if(k>0&&d1<=0&&d2>0) wn++;
if(k<0&&d2<=0&&d1>0) wn--;
}
if(wn!=0) return 1;//内部
return 0; //外部
}
double seg(point O,point A,point B){
if(dcmp(B.x-A.x)==0) return (O.y-A.y)/(B.y-A.y);
return (O.x-A.x)/(B.x-A.x);
}
pair<double,int>s[110*60];
double polyunion(vector<point>*p,int N){ //有多个才加*,单个不加，有改变的加&
//求多边形面积并
double res=0;
for(int i=0;i<N;i++){
int sz=p[i].size();
for(int j=0;j<sz;j++){
int m=0;
s[++m]=mp(0,0);
s[++m]=mp(1,0);
point a=p[i][j],b=p[i][(j+1)%sz];
for(int k=0;k<N;k++){
if(i!=k){
int sz2=p[k].size();
for(int ii=0;ii<sz2;ii++){
point c=p[k][ii],d=p[k][(ii+1)%sz2];
int c1=dcmp(det(b-a,c-a));
int c2=dcmp(det(b-a,d-a));
if(c1==0&&c2==0){
if(dcmp(dot(b-a,d-c))){
s[++m]=mp(seg(c,a,b),1);
s[++m]=mp(seg(c,a,b),-1);
}
}
else{
double s1=det(d-c,a-c);
double s2=det(d-c,b-c);
if(c1>=0&&c2<0) s[++m]=mp(s1/(s1-s2),1);
else if(c1<0&&c2>=0) s[++m]=mp(s1/(s1-s2),-1);
}
}
}
}
sort(s+1,s+m+1);
double pre=min(max(s[1].first,0.0),1.0),now,sum=0;
int cov=s[0].second;
for(int j=2;j<=m;j++){
now=min(max(s[j].first,0.0),1.0);
if(!cov) sum+=now-pre;
cov+=s[j].second;
pre=now;
}
res+=det(a,b)*sum;
}
}
return -(res/2);
}
point jiaopoint(point p,point v,point q,point w)
{ //p+tv q+tw，点加向量表示直线，求直线交点
point u=p-q;
double t=det(w,u)/det(v,w);
return p+v*t;
}
point GetCirPoint(point a,point b,point c)
{
point p=(a+b)/2; //ad中点
point q=(a+c)/2; //ac中点
point v=rotate(b-a,pi/2.0),w=rotate(c-a,pi/2.0); //中垂线的方向向量
if (dcmp(length(det(v,w)))==0) //平行
{
if(dcmp(length(a-b)+length(b-c)-length(a-c))==0) return (a+c)/2;
if(dcmp(length(b-a)+length(a-c)-length(b-c))==0) return (b+c)/2;
if(dcmp(length(a-c)+length(c-b)-length(a-b))==0) return (a+b)/2;
}
return jiaopoint(p,v,q,w);
}
point MinCircular(point *P,int n)
{
//最小圆覆盖 ,看起来是O(N^3)，期望复杂度为O(N)
random_shuffle(P+1,P+n+1); //随机化
point c=P[1]; double r=0; //c 圆心,,//r 半径
for (int i=2;i<=n;i++)
if (dcmp(length(c-P[i])-r)>0) //不在圆内
{
c=P[i],r=0;
for (int j=1;j<i;j++)
if (dcmp(length(c-P[j])-r)>0)
{
c=(P[i]+P[j])/2.0;
r=length(c-P[i]);
for (int k=1;k<j;k++)
if (dcmp(length(c-P[k])-r)>0)
{
c=GetCirPoint(P[i],P[j],P[k]);
r=length(c-P[i]);
}
}
}
//cout<<r<<":"<<c.x<<" "<<c.y<<endl;
return c;
}
const int maxn=400010;
bool cmp(point a,point b){ return a.x==b.x?a.y<b.y:a.x<b.x; }
point f[maxn],c[maxn],ch[maxn];
void convexhull(point *a,int n,int &top)
{
//水平序的Andrew算法求凸包。
sort(a+1,a+n+1,cmp); top=0;
for(int i=1;i<=n;i++){ //求下凸包
while(top>=2&&det(ch[top-1],ch[top],a[i])<=0) top--;
ch[++top]=a[i];
}
int ttop=top;
for(int i=n-1;i>=1;i--){ //求上凸包
while(top>ttop&&det(ch[top-1],ch[top],a[i])<=0) top--;
ch[++top]=a[i];
}
}
void P(double x)
{
//if(fabs(x)<0.000001) puts("0.00000000"); else
printf("%.9lf",x);
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("robots.in","r",stdin);
int t;
cin>>t;
while(t--){
int n,R,r;
cin>>n>>R>>r;
int tot=1;
f[tot].x=0;f[tot].y=0;
for(int i=1;i<=n;i++){
int a,b;cin>>a>>b;
tot++;
f[tot].x=f[tot-1].x+a;
f[tot].y=f[tot-1].y+b;
}
point anw=MinCircular(f,tot);
cout<<fixed<<setprecision(9);
cout<<-anw.x<<" "<<-anw.y<<endl;
}
return 0;
}