【SDOI2016Round1】【解题报告】
Day1
T1:
题意:求
因为是抑或操作,每一位都是独立的,所以可以一位一位的算贡献。
复杂度是
#include #include #include #include using namespace std; #define LL long long const int N=100; int T,Mod,ni[N],mi[N],ki[N],len; LL n,m,K,f[N][2][2][3],g[N][2][2][3]; inline void calc(){ int i,a,b,c,o0,o1,x,y,z,o; g[0][1][1][1]=1; for(i=0;ini[i+1]) continue; if(o0==ni[i+1]) x=1; if(o0mi[i+1]) continue; if(o1==mi[i+1]) y=1; if(o1ki[i+1]) z=2; if(o==ki[i+1]) z=1; if(o>=1) ni[++ni[0]]=x&1LL; for(x=m;x;x>>=1) mi[++mi[0]]=x&1LL; for(x=K;x;x>>=1) ki[++ki[0]]=x&1LL; len=max(ni[0],max(mi[0],ki[0])); for(i=1;i>1);++i){ swap(ni[i],ni[len-i+1]); swap(mi[i],mi[len-i+1]); swap(ki[i],ki[len-i+1]); } calc(); printf("%lld\n",(f[len][0][0][2]-(K%Mod*g[len][0][0][2])%Mod+Mod)%Mod); } }
T2:
题意:给出n种数字,第i个是ai,个数是bi,权值是ci。如果
配对关系是一个二分图,所以建出费用流的图来,当跑到费用小于0的时候,处理一下当前的流量,退出就行了。
#include #include #include #include using namespace std; #define T n+2 #define D 795 #define LL long long #define inf 1000000000 #define INF 10000000000000LL const int N=800; const int M=100000; const int O=2000000; bool flag[M+10],use[N],f[N]; struct S{int st,en,va;LL co;}aa[O]; int n,a[N],b[N],c[N],prime[M+10],d[N],va,point[N],pre[N],next[O],map[N][N],tot=1,co[N]; int l[N],to[N]; LL dis[N]; inline void prepare(){ int i,j; for(i=2;i1) return false; if(now==1) return true; } if(now!=1) ++num; return num==1; } inline void paint(int x,int kind){ int i; co[x]=kind; for(i=1;i0&&dis[aa[i].en]
T3:
题意:给出一棵树,有点权和边权,有两种操作,一种是将一条路径上的点权修改成
第一种修改可以看成是往树上的一段区间中加入一个线段。这个东西可以用线段树维护。用线段树维护这个区间的线段的斜率和截距。每次向这个区间中加入一条新的线段的时候,看一下这段区间中原来的线段和新加入的线段哪一个对这段区间的影响更大,将影响小的线段下放到它有影响的子树,每次一直这样下放到叶子节点。这样每次插入的复杂度是
每次查询的时候只需要看一下这段区间中的最小值和这段区间中所保存的线段的两个端点的情况就行了,复杂度是
这道题每次的dis数组还是不知道的,可以在加入线段的时候顺便将lca传进去(常数大了好多。。。)
再加上链剖,总的复杂度就是
#include #include #include #include using namespace std; #define mid (l+r)/2 #define L k'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&chsiz[son[u]]) son[u]=aa[j].en; } } int now=1; for(i=1;i=r){ LL minn=D; minn=min(minn,calc(l,now.lca,now.st,now.kind)*now.k+now.b); minn=min(minn,calc(r,now.lca,now.st,now.kind)*now.k+now.b); now.minn=tr[k].minn=min(tr[k].minn,minn); if(!flag[k]){ flag[k]=1; tr[k]=now; return ; } int o1=calc(l,now.lca,now.st,now.kind)*now.k+now.bmid) insert(R,x,y,now); tr[k].minn=min(tr[k].minn,min(tr[k=r){ LL o_l=calc(l,tr[k].lca,tr[k].st,tr[k].kind); LL o_r=calc(r,tr[k].lca,tr[k].st,tr[k].kind); return min(tr[k].minn,min(o_l*tr[k].k+tr[k].b,o_r*tr[k].k+tr[k].b)); } minn=min(minn,calc(max(x,l),tr[k].lca,tr[k].st,tr[k].kind)*tr[k].k+tr[k].b); minn=min(minn,calc(min(y,r),tr[k].lca,tr[k].st,tr[k].kind)*tr[k].k+tr[k].b); if(xmid) minn=min(minn,query(R,x,y)); return minn; } inline void change(int x,int y,int st,int kind){ int i,j; T now=(T){lca,st,kind,a,b,D}; while(belong[x]!=belong[y]){ insert(1,1,n,pos[belong[x]],pos[x],now); x=fa[belong[x]][0]; } insert(1,1,n,pos[y],pos[x],now); } inline LL ask(int x,int y){ LL minn=D; while(belong[x]!=belong[y]){ minn=min(minn,query(1,1,n,pos[belong[x]],pos[x])); x=fa[belong[x]][0]; } minn=min(minn,query(1,1,n,pos[y],pos[x])); return minn; } int main(){ int i,j,x,y,t,z; n=in();m=in(); for(i=1;i
Day2:
T1:
题意:每次向一个字符串的结尾加一个字符,输出当前有多少种不同的非空子串。
先将这个字符串全读进来,然后把字符串反过来建后缀数组。总的答案就是
因为要动态的查询,所以维护一个rank的权值线段树,每次加入一个之后查询一下前驱和后继,每次更新的答案就是:
#include #include #include #include using namespace std; #define LL long long #define inf 0x7fffffff const int N=100010; struct S{int minn,maxn;}tr[N'9') ch=getchar(); while(ch>='0'&&ch=n)?-1:y[p+k]; o1=(q+k>=n)?-1:y[q+k]; return o0==o1&&y[p]==y[q]; } inline void build_sa(){ int i,k,p,*x=t1,*y=t2; for(i=0;i=k) y[p++]=sa[i]-k; for(i=0;i=n) break; } } inline void build_height(){ int i,j,k=0; for(i=0;i=r) return tr[k]; if(xmid) ans2=query(R,x,y),f2=true; if(f1&&f2) return update(ans1,ans2); else return f1?ans1:ans2; } int main(){ int i; n=in(); for(i=n-1;~i;--i) a[i]=b[i]=in(); sort(b+1,b+n+1); m=unique(b+1,b+n+1)-b-1; for(i=0;i
T2:
题意:求有多少长度为n的序列,满足1~n只出现过一次,而且恰好有m个数满足
答案就是
错拍的公式就是:
求c的时候预处理一下阶乘。
#include #include #include using namespace std; #define LL long long #define Mod 1000000007LL const int M=1000000; LL f[M+10],g[M+10]; int T,n,m; inline int in(){ int x=0;char ch=getchar(); while(ch'9') ch=getchar(); while(ch>='0'&&ch>=1LL; x=(x*x)%Mod; } return ans; } int main(){ int i; T=in(); for(f[1]=0LL,f[2]=1LL,f[0]=1LL,i=3;in){ printf("0\n"); continue; } LL ans=f[n-m]*((g[n]*quickpow(g[m],Mod-2)%Mod)*quickpow(g[n-m],Mod-2)%Mod)%Mod; printf("%lld\n",ans); } }
T3:
题意:有一个长度为n的序列,每个节点都有一个权值,分成m份,求m份的最小的方差是多少。答案要求
把
#include #include #include using namespace std; #define LL long long const int N=3010; LL f[N][N],a[N]; int n,m,h[N],t[N],q[N][N]; inline LL pow(LL x){return x*x;} inline LL get_son(int x,int y,int z){ return f[z][x]+pow(a[x])-f[z][y]-pow(a[y]); } inline LL get_fa(int x,int y){ return a[x]-a[y]; } inline LL calc(int x,int y,int z){ return f[z][x]+pow(a[y]-a[x]); } int main(){ int i,j; scanf("%d%d",&n,&m); for(i=1;i
上一篇: 干粉灭火器使用方法,灭火原理是什么
下一篇: [C++ 面试基础知识总结] 泛型算法
推荐阅读
-
Win10系统如何关闭Windows错误报告?Win10关闭系统错误报告的方法
-
网易云音乐2019听歌报告刷屏 抢100年黑胶VIP会员
-
2019优酷年度弹幕报告出炉:火影拿下“年度第一弹”
-
鲁大师315假机报告:iPhone 8一骑绝尘、华为独善其身
-
定义两个接口,其中各包括一个抽象方法分别用来完成两个数的加法和减法操作,然后创建一个类KY6_3来实现这两个接口中的抽象方法。编写程序KY6_3.java,将源程序写在实验报告中。
-
Oracle AWR报告详细分析--比较详细
-
AWR报告中Top 10 Foreground Events存在”reliable message”等待事件的处理办法
-
2019抖音数据报告看什么最火 地方小吃麻辣烫霸榜
-
艾媒咨询发布第三方手机浏览器监测报告 UC用户满意程度最高
-
【阶梯报告】洛谷P3391【模板】文艺平衡树 splay