由于我天天被虐，模拟考还老是考的极差，感觉有必要开个博客记录一下每场考试
由于懒得加美元符所以这篇博客不用 latex
由于要弄代码折叠我还特意换掉了 Markdown 编辑器
由于我没话说了，前言就这么多吧
2018.7.13
开场看 T1 发现不会顿时贼虚，思路明明马上就是正解了但是死活没想出来。把点权放到边上求出来最大生成树之后立马敲了个树剖(我只是生来码农) 然后跟暴力一样 n^2 求的两点边权最小值
看 T2 也是发现性质可以开两个树状数组做但是死活没想出来答案从哪找，结果发现莫队一脸可做码了个带修莫队还把块大小设成根号 n 了。(我果然菜到连前一天刚讲过的板子都不会敲了
结果 T2 被卡但是还是比暴力多 20 分
T3 更不可做 直接30分爆搜走人
总分 50+50+30=130 本部 rank3/16
T1 这东西应该能发现可以从大到小加边合并集合啊这不跟走廊泼水节一样么
#include<cstdio> #include<cctype> #include<algorithm> #define N 100005 #define int long long #define min(A,B) ((A)<(B)?(A):(B)) #define max(A,B) ((A)>(B)?(A):(B)) #define swap(A,B) ((A)^=(B)^=(A)^=(B)) int val[N]; int father[N]; int d[N],fa[N]; int n,m,cnt,tot; int cme[N],fs[N]; int sze[N],son[N]; int dfn[N],top[N]; int head[N],mn[N<<2]; struct Edge{ int to,nxt,dis; }edge[N<<1]; void add(int x,int y,int z){ edge[++cnt].to=y; edge[cnt].nxt=head[x]; edge[cnt].dis=z; head[x]=cnt; } struct Node{ int x,y,dis; friend bool operator<(Node a,Node b){ return a.dis>b.dis; } }node[N*10]; int getint(){ int x=0,f=0;char ch=getchar(); while(!isdigit(ch)) f|=ch==‘-‘,ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return f?-x:x; } int find(int x){ if(father[x]==x) return x; return father[x]=find(father[x]); } void file(){ freopen("zoo.in","r",stdin); freopen("zoo.out","w",stdout); } signed main(){ file(); n=getint(),m=getint(); for(int i=1;i<=n;i++){ father[i]=i; sze[i]=1; val[i]=getint(); } for(int i=1;i<=m;i++){ node[i].x=getint(); node[i].y=getint(); node[i].dis=min(val[node[i].x],val[node[i].y]); } int now=0; std::sort(node+1,node+1+m); for(int i=1;i<=m;i++){ int x=find(node[i].x); int y=find(node[i].y); if(x==y) continue; father[x]=y; now+=sze[x]*sze[y]*node[i].dis; sze[y]+=sze[x]; } printf("%lld\n",now<<1); return 0; }
T2 可以开两个树状数组分别存每个点之前线段左、右端点各出现了多少次。
然后查询就是用右端点之前出现了多少次减去左端点减一之前出现了多少次
#include<cstdio> #include<cctype> #include<cstring> #include<algorithm> #define N 200005 #define min(A,B) ((A)<(B)?(A):(B)) #define max(A,B) ((A)>(B)?(A):(B)) #define swap(A,B) ((A)^=(B)^=(A)^=(B)) int tot,cnt; int g[N<<1]; int l[N],r[N]; int T,n,cas,m; int ques[N][5]; int xgl[N],xgr[N]; struct BIT{ int f[N<<1]; void clear(){ memset(f,0,sizeof f); } int query(int x){ int ans=0; for(;x>=1;x-=x&-x) ans+=f[x]; return ans; } void add(int x,int y){ for(;x<=m;x+=x&-x) f[x]+=y; } }a,b; int getint(){ int x=0,f=0;char ch=getchar(); while(!isdigit(ch)) f|=ch==‘-‘,ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return f?-x:x; } signed main(){ freopen("segment.in","r",stdin); freopen("segment.out","w",stdout); T=getint(); while(T--){ a.clear();b.clear(); cnt=tot=0; n=getint(); for(int i=1;i<=n;i++){ ques[i][1]=getint(); ques[i][2]=getint(); if(ques[i][1]){ xgl[i]=l[ques[i][2]]; xgr[i]=r[ques[i][2]]; } else{ cnt++; ques[i][3]=ques[i][2]+cnt; l[cnt]=ques[i][2]; r[cnt]=ques[i][3]; g[++tot]=ques[i][2]; g[++tot]=ques[i][3]; } } std::sort(g+1,g+1+tot); m=std::unique(g+1,g+1+tot)-g-1; printf("Case #%d:\n",++cas); for(int i=1;i<=n;i++){ if(ques[i][1]==0){ ques[i][2]=std::lower_bound(g+1,g+1+m,ques[i][2])-g; ques[i][3]=std::lower_bound(g+1,g+1+m,ques[i][3])-g; printf("%d\n",b.query(ques[i][3])-a.query(ques[i][2]-1)); a.add(ques[i][2],1); b.add(ques[i][3],1); } else{ xgl[i]=std::lower_bound(g+1,g+1+m,xgl[i])-g; xgr[i]=std::lower_bound(g+1,g+1+m,xgr[i])-g; a.add(xgl[i],-1); b.add(xgr[i],-1); } } } return 0; }
T3 什么鬼啊喂 2^((n-1)*(m-1)-k) 是啥啊 noip 压轴题靠打表的啊啊啊？
证明：不会(×)
#include<cstdio> #include<cctype> #include<cstring> #define int long long #define min(A,B) ((A)<(B)?(A):(B)) #define max(A,B) ((A)>(B)?(A):(B)) #define swap(A,B) ((A)^=(B)^=(A)^=(B)) int k; int n,m,p; int ksm(int a,int b){ int ans=1; if(b<0) return ans; while(b){ if(b&1) ans=ans*a%p; a=a*a%p; b>>=1; } return ans; } int getint(){ int x=0,f=0;char ch=getchar(); while(!isdigit(ch)) f|=ch==‘-‘,ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return f?-x:x; } signed main(){ freopen("number.in","r",stdin); freopen("number.out","w",stdout); n=getint();m=getint();k=getint(); for(int i=1;i<=k;i++) int a=getint(),b=getint(),c=getint(); p=getint(); if((n+m)%2==1) return printf("0"),0; printf("%lld\n",ksm(2,(n-1)*(m-1)-k)); return 0; }
原文：https://www.cnblogs.com/YoungNeal/p/9307950.html
