二试画风清奇
T1普及组水题 BZOJ4500
T2原题 BZOJ4919
前两天加起来1h-
T3毒瘤题 肛了3h+得到0分的好成绩
省选rank44->rank24
T1
#include<cstdio> #include<algorithm> #define rep(i,s,t) for(register int i=s;i<=t;++i) using namespace std; #define gc getchar() const int N=2e6+11,inf=(1<<30); inline int read(){ char c;while(c=gc,c==' '||c==' ');int data=0,f=1; if(c=='-')f=-1;else data=c-48; while(c=gc,c>='0'&&c<='9')data=(data<<1)+(data<<3)+c-48;return data*f; } int T,n,m,k,tot,x,y,z; int nxt[N],las[4011],to[N],w[N],ans[4011]; inline void add(int x,int y,int z){ nxt[++tot]=las[x], las[x]=tot, to[tot]=y, w[tot]=z; } inline void init(){ rep(i,1,n+m)las[i]=0,ans[i]=-inf; tot=0; } inline bool bfs(int x){ for(register int e=las[x];e;e=nxt[e]){ if(ans[to[e]]==-inf){ ans[to[e]]=w[e]-ans[x]; if(!bfs(to[e])) return 0; } else if(ans[to[e]]+ans[x]!=w[e]) return 0; } return 1; } int main(){ freopen("solo.in","r",stdin); freopen("solo.out","w",stdout); T=read(); while(T--){ n=read(),m=read(),k=read(); init(); rep(i,1,k){ x=read(),y=read()+n,z=read(), add(x,y,z),add(y,x,z); } rep(i,1,n+m) if(ans[i]==-inf){ ans[i]=0; if(!bfs(i)){ puts("No"); goto end; } } puts("Yes"); end:; } return 0; }
T2
#include<cstdio> #include<algorithm> #include<set> #define rep(i,s,t) for(register int i=s;i<=t;++i) using namespace std; const int N=4e5+11,M=2e5+11; int nxt[N],las[N],to[N]; int val[N]; multiset<int>s[M]; multiset<int>::iterator it; int n,fa,tot; inline void add(int x,int y){ nxt[++tot]=las[x]; las[x]=tot; to[tot]=y; } inline void merge(int x,int y){ if(s[x].size()<s[y].size())swap(s[x],s[y]); for(it=s[y].begin();it!=s[y].end();++it) s[x].insert(*it); s[y].clear(); } inline void dfs(int x=1){ for(register int e=las[x];e;e=nxt[e]){ dfs(to[e]); merge(x,to[e]); } it=s[x].upper_bound(val[x]);if(it!=s[x].end())s[x].erase(it); s[x].insert(val[x]); } #define gc getchar() inline int read(){ char c;while(c=gc,c==' '||c==' ');int data=0,f=1; if(c=='-')f=-1;else data=c-48; while(c=gc,c>='0'&&c<='9')data=(data<<1)+(data<<3)+c-48;return data*f; } int main(){ freopen("boss.in","r",stdin); freopen("boss.out","w",stdout); n=read(); rep(i,1,n){ val[i]=read(), val[i]=-val[i]; } rep(i,2,n){ fa=read(), add(fa,i); } dfs(); printf("%d ",(int)s[1].size()); return 0; }
T3 毒瘤题弃疗
#include<cstdio> #include<algorithm> #include<queue> #include<cmath> #define rep(i,s,t) for(register int i=s;i<=t;++i) using namespace std; typedef double db; const int N=1e5+11; db S,T,X,Y; inline db sqr(db x){ return x*x; } struct point{ db x,y; inline bool operator<(point A)const{ return sqr(x-S)+sqr(y-T)>sqr(A.x-S)+sqr(A.y-T); } }p[2][N],now; priority_queue<point>heap; int n,m; int a,b,c,d; int mark[2][N]; db ans,h,minn; inline void init(){ rep(i,1,n){ if(!mark[0][i])heap.push(p[0][i]); if(mark[0][i]==1)S=0,T=p[0][i].y; if(mark[0][i]==2)X=0,Y=p[0][i].y; } rep(i,1,m){ if(!mark[1][i])heap.push(p[1][i]); if(mark[1][i]==1)S=h,T=p[1][i].y; if(mark[1][i]==2)X=h,Y=p[1][i].y; } } int main(){ freopen("post.in","r",stdin); freopen("post.out","w",stdout); scanf("%d%d%d%d%d%d%lf",&n,&m,&a,&b,&c,&d,&h); mark[a][b]=1,mark[c][d]=2; rep(i,1,n) scanf("%lf",&p[0][i].y); rep(i,1,m){ scanf("%lf",&p[1][i].y); p[1][i].x=h; } init(); while(!heap.empty()){ now=heap.top();heap.pop(); ans+=1.*sqrt(1.*sqr(now.x-S)+1.*sqr(now.y-T)); S=now.x,T=now.y; } ans+=1ll*sqrt(sqr(X-S)+sqr(Y-T)); minn=ans;ans=0.; init(); swap(X,S),swap(Y,T); while(!heap.empty()){ now=heap.top();heap.pop(); ans+=1.*sqrt(1.*sqr(now.x-S)+1.*sqr(now.y-T)); S=now.x,T=now.y; } ans+=1ll*sqrt(sqr(X-S)+sqr(Y-T)); minn=min(minn,ans); printf("%.2lf ",minn); return 0; }