学习了“叙利亚”这个单词；比较温和的一场；几何的板子eps太小了，坑了几发。
A .Hello SCPC 2018!
题意：给定一个排列，问它是否满足，前面4个是有序的，而且前面4个比后面的都小。
思路：数据比较小，可以暴力，也可以用前面4个的最大值和后面的数字的最小值比较。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int a[maxn];
int main()
{
int T,N;
scanf("%d",&T);
while(T--){
rep(i,,) scanf("%d",&a[i]);
bool F=true;
rep(i,,) if(a[i]>a[i+]) F=false;
rep(i,,)
rep(j,,)
if(a[i]>a[j]) F=false;
if(F) puts("yes");
else puts("no");
}
return ;
}
B .Binary Hamming
题意：给定两个01串，让你重排，使得对应位置不同的个数最多。
思路：有点像那个石头剪刀布的题，答案是min(A的石头，B的剪刀)+min（A的布，B的石头）+min（A的剪刀，B的布）。 所以这个题就是min(A的0，B的1)+min（A的1，B的0）；
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
char c[maxn];
int main()
{
int T,N;
scanf("%d",&T);
while(T--){
int A,B,C,D;
scanf("%d",&N); A=B=C=D=;
scanf("%s",c+);
rep(i,,N) if(c[i]=='') A++; else B++;
scanf("%s",c+);
rep(i,,N) if(c[i]=='') C++; else D++;
printf("%d\n",min(A,D)+min(B,C));
}
return ;
}
C.Portals
题意：给定N个格子...问，至少使多少格子阻断，使得个s和t不连通。
思路：大讨论，自己写挂了。 by罗。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=;
const int maxn=2e6+;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
char s[maxn];
int dx[]={,-};
int n;
int S,T;
int dfs(int x,int i){
if(x==n+)return ;
if(x==)return ;
if(s[x]=='#')return ;
if(s[x]=='o')return ;
if(s[x]=='s'||s[x]=='e')return ;
return dfs(x+dx[i],i);
}
int main()
{
freopen("portals.in","r",stdin);
int t;
cin>>t;
while(t--){
cin>>n;
for(int i=;i<=n+;i++)s[i]='#';
cin>>s+;
int len=strlen(s+);
for(int i=;i<=n;i++){
if(s[i]=='s')S=i;
if(s[i]=='e')T=i;
}
if(abs(S-T)==){
cout<<"-1"<<endl;continue;
}
if((s[S-]=='o'||s[S+]=='o')&&(s[T-]==''||s[T+]=='o')){
cout<<"-1"<<endl;continue;
}
int neds=dfs(S+,)+dfs(S-,);
int nedt=dfs(T+,)+dfs(T-,);
int ans=1e9;
if(s[S-]=='o'||s[S+]=='o')neds=1e9;
if(s[T-]=='o'||s[T+]=='o')nedt=1e9;
ans=min(neds,nedt);
if(ans==1e9)cout<<-<<endl;
else cout<<ans<<endl;
}
return ;
}
D .Carnival Slots
题意：给定N*M的矩阵，现在1到M分别有numi个球向下掉，一个球掉到第j列的收益的moneyj； 一个格子如果是‘.'，那么它只能向下掉， 否则可以向下，左下，右下掉。问最大收益是多少。
思路：和数字三角形的那个dp有点像，从下到上跟新dp值，表示单个球经过它能向下到达的最大收益是多少。 主要是考虑到球和球是独立的，所以不用想太多。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
ll dp[maxn][maxn],num[maxn],ans;int N,M;
char c[maxn][maxn];
void solve()
{
for(int i=N;i>=;i--){
rep(j,,M){
dp[i][j]=dp[i+][j];
if(c[i][j]!='.'){
if(j->=) dp[i][j]=max(dp[i][j],dp[i+][j-]);
if(j+<=M) dp[i][j]=max(dp[i][j],dp[i+][j+]);
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
ans=;
scanf("%d%d",&N,&M);
rep(i,,M) scanf("%lld",&num[i]);
rep(i,,N) scanf("%s",c[i]+);
rep(i,,M) scanf("%lld",&dp[N+][i]);
solve();
rep(i,,M) ans+=num[i]*dp[][i];
printf("%lld\n",ans);
}
return ;
}
G .Is Topo Logical?
题意：
思路：
比赛的时候看错题意了，样例没看懂，感觉可以做。待会补。
H .Bugged System
题意：反正就是问是否有向图存在欧拉回路。
思路：入度=出度。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int ind[maxn],oud[maxn],L[maxn]; ll ans;
int main()
{
int T,N,M,x,y;
scanf("%d",&T);
while(T--){
ans=; scanf("%d%d",&N,&M);
rep(i,,N) scanf("%d",&L[i]),ind[i]=oud[i]=;
rep(i,,M) {
scanf("%d%d",&x,&y);
ans+=abs(L[x]-L[y]);
ind[y]++; oud[x]++;
}
rep(i,,N) if(ind[i]!=oud[i]) ans=-;
printf("%lld\n",ans);
}
return ;
}
I. Rise of the Robots
题意：给定一个大圆，起点未知，然后给你一个小圆的路径，让你求一个起点，使得它走到的点都在大圆里。 一定有解。
思路：一定有解，那么我们可以不考虑大圆和小圆，我们只关心小圆的圆心即可。我们求个这个路径的圆心，满足以它的相反数为为起点，一定可以满足题意。
所以就是求最小圆覆盖，对应的圆心。 可以用模拟退火贪心，也可以三分套三分（我不会）。
误区：最开始我也是想的去求这样一个中心，但是我想的是用旋转卡壳去求最长的边对应的中心，这样是错的。
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
typedef long long ll;
const double inf=1e200;
const double eps=1e-;
const double pi=*atan(1.0);
struct point{
double x,y;
point(double a=,double b=):x(a),y(b){}
};
int dcmp(double x){ return fabs(x)<eps?:(x<?-:);}
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)==&&dcmp(a.y-b.y)==;
}
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))<) return length(v2);
else if(dcmp(dot(v1,v3))>) return length(v3);
return fabs(det(v1,v2)/length(v1));
}
double Ployarea(vector<point>p)
{
//多边形面积
double ans=; int sz=p.size();
for(int i=;i<sz-;i++) ans+=det(p[i]-p[],p[i+]-p[]);
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)<&&dcmp(c3)*dcmp(c4)<;
}
bool isPointOnSegment(point p,point a1,point a2)
{
//点是否在线段上
return dcmp(det(a1-p,a2-p)==&&dcmp(dot(a1-p,a2-p))<);
}
int isPointInPolygon(point p,vector<point>poly)
{
//判断点与多边形的位置关系
int wn=,sz=poly.size();
for(int i=;i<sz;i++){
//在边上
if(isPointOnSegment(p,poly[i],poly[(i+)%sz])) return -;
int k=dcmp(det(poly[(i+)%sz]-poly[i],p-poly[i]));
int d1=dcmp(poly[i].y-p.y); int d2=dcmp(poly[(i+)%sz].y-p.y);
if(k>&&d1<=&&d2>) wn++;
if(k<&&d2<=&&d1>) wn--;
}
if(wn!=) return ;//内部
return ; //外部
}
double seg(point O,point A,point B){
if(dcmp(B.x-A.x)==) return (O.y-A.y)/(B.y-A.y);
return (O.x-A.x)/(B.x-A.x);
}
pair<double,int>s[*];
double polyunion(vector<point>*p,int N){ //有多个才加*,单个不加，有改变的加&
//求多边形面积并
double res=;
for(int i=;i<N;i++){
int sz=p[i].size();
for(int j=;j<sz;j++){
int m=;
s[++m]=mp(,);
s[++m]=mp(,);
point a=p[i][j],b=p[i][(j+)%sz];
for(int k=;k<N;k++){
if(i!=k){
int sz2=p[k].size();
for(int ii=;ii<sz2;ii++){
point c=p[k][ii],d=p[k][(ii+)%sz2];
int c1=dcmp(det(b-a,c-a));
int c2=dcmp(det(b-a,d-a));
if(c1==&&c2==){
if(dcmp(dot(b-a,d-c))){
s[++m]=mp(seg(c,a,b),);
s[++m]=mp(seg(c,a,b),-);
}
}
else{
double s1=det(d-c,a-c);
double s2=det(d-c,b-c);
if(c1>=&&c2<) s[++m]=mp(s1/(s1-s2),);
else if(c1<&&c2>=) s[++m]=mp(s1/(s1-s2),-);
}
}
}
}
sort(s+,s+m+);
double pre=min(max(s[].first,0.0),1.0),now,sum=;
int cov=s[].second;
for(int j=;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/);
}
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)/; //ad中点
point q=(a+c)/; //ac中点
point v=rotate(b-a,pi/2.0),w=rotate(c-a,pi/2.0); //中垂线的方向向量
if (dcmp(length(det(v,w)))==) //平行
{
if(dcmp(length(a-b)+length(b-c)-length(a-c))==) return (a+c)/;
if(dcmp(length(b-a)+length(a-c)-length(b-c))==) return (b+c)/;
if(dcmp(length(a-c)+length(c-b)-length(a-b))==) return (a+b)/;
}
return jiaopoint(p,v,q,w);
}
point MinCircular(point *P,int n)
{
//最小圆覆盖 ,看起来是O(N^3)，期望复杂度为O(N)
random_shuffle(P+,P+n+); //随机化
point c=P[]; double r=; //c 圆心,,//r 半径
for (int i=;i<=n;i++)
if (dcmp(length(c-P[i])-r)>) //不在圆内
{
c=P[i],r=;
for (int j=;j<i;j++)
if (dcmp(length(c-P[j])-r)>)
{
c=(P[i]+P[j])/2.0;
r=length(c-P[i]);
for (int k=;k<j;k++)
if (dcmp(length(c-P[k])-r)>)
{
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=;
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+,a+n+,cmp); top=;
for(int i=;i<=n;i++){ //求下凸包
while(top>=&&det(ch[top-],ch[top],a[i])<=) top--;
ch[++top]=a[i];
}
int ttop=top;
for(int i=n-;i>=;i--){ //求上凸包
while(top>ttop&&det(ch[top-],ch[top],a[i])<=) top--;
ch[++top]=a[i];
}
}
void P(double x)
{
//if(fabs(x)<0.000001) puts("0.00000000"); else
printf("%.9lf",x);
}
int main()
{
freopen("robots.in","r",stdin);
int T,N,tot,top;
scanf("%d",&T);
while(T--){
double R,r;
scanf("%d%lf%lf",&N,&R,&r);
double x=0.0,y=0.0;
f[tot=]=point(x,y);
for(int i=;i<=N+;i++){
scanf("%lf%lf",&f[i].x,&f[i].y);
x+=f[i].x; y+=f[i].y;
f[++tot]=point(x,y);
}
convexhull(f,tot,top);
point res=MinCircular(ch,top);
//cout<<res.x<<" "<<res.y<<endl;
//res.x=-res.x; res.y=-res.y;P(res.x); putchar(' '); P(res.y); putchar('\n');
printf("%.6lf %.6lf\n",-res.x,-res.y);
}
return ;
}
K .Tourists' Tour
题意：给定N个数，每个位置分别和左右第一个大于它的值的位置连边。 然后给这些位置然后，有边相邻的两个点的颜色不能相同，问最小的颜色数，以及输出一个方案。
思路：首先猜到颜色数应该很小，所以最后可以用mex来求颜色。 我们可以用单调队列O(N)或者线段树O(NlogN)求边。 那么现在就是需要按一定顺序来染色即可。
我们可以把边变为有向边，即只从值大的连向小的。 那么它一定是个DAG，我们就可以topo了。
不难证明：颜色数=max(入度+1)； 而入度最大为2，所以颜色最大值是3。
#include<bits/stdc++.h>
#define rep2(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
const int maxn=;
int Next[maxn<<],Laxt[maxn<<],To[maxn<<],ind[maxn];
int a[maxn],q[maxn],vis[maxn],col[maxn],head,tail,ans,cnt,top;
vector<int>G[maxn];
void add(int u,int v)
{
Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; ind[v]++;
G[v].push_back(u);
}
int main()
{
int T,N;
freopen("tour.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
head=tail=ans=cnt=;
rep(i,,N) Laxt[i]=ind[i]=vis[i]=,G[i].clear();
rep(i,,N) scanf("%d",&a[i]); top=;
rep(i,,N){
while(top&&a[i]>=a[q[top]]) top--;
if(top) add(q[top],i);
q[++top]=i;
}
top=;
rep2(i,N,){
while(top&&a[i]>=a[q[top]]) top--;
if(top) add(q[top],i);
q[++top]=i;
}
rep(i,,N) if(!ind[i]) q[++head]=i;
while(tail<head){
int u=q[++tail],v;
for(int i=Laxt[u];i;i=Next[i]){
v=To[i]; ind[v]--;
if(!ind[v]) q[++head]=v;
}
for(int i=;i<G[u].size();i++){
vis[col[G[u][i]]]=u;
}
rep(i,,) if(vis[i]!=u) {col[u]=i; break;}
ans=max(ans,col[u]);
}
printf("%d\n",ans);
rep(i,,N-) printf("%d ",col[i]);
printf("%d\n",col[N]);
}
}