首页 > 代码库 > NOI2014 DAY2 题解
NOI2014 DAY2 题解
当天下午3点拿到jcvb现场发来的数据，本地自测100+100+30=230。
BUAA成绩60+60+30=150。sad story~
动物园 zoo
既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作num[i]。
偌大的提示：kmp! 思路很简单，求出next数组，你会发现这是一棵树，求出根(0)~i路径上<i/2的元素有多少个。
BIT nlogn? 多组数据会被卡。（ok多个log也能过的策爷！人家是策爷！）
我跟dzy说，类似单调栈..反正栈上搞搞就行。（考试时请改手工栈，笔者RE60）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #define mo 1000000007 8 #define maxn 1100000 9 using namespace std;10 int v[maxn],nxt[maxn],first[maxn];11 char ch[maxn];int next[maxn];12 int q,n,tot,ans;13 int st[maxn],top,cnt;14 15 void addedge(int x,int y){16 v[++tot]=y;nxt[tot]=first[x];first[x]=tot;17 }18 19 void getnext(){20 next[1]=0;21 for(int i=2;i<=n;i++){22 int j=next[i-1];23 while(ch[j+1]!=ch[i]&&j>0) j=next[j];24 if(ch[j+1]==ch[i]) next[i]=j+1;25 else next[i]=0;26 }27 }28 29 void dfs(int u){30 ans=1ll*ans*(cnt+1)%mo; int t;31 for(int i=first[u];i;i=nxt[i]){32 st[++top]=v[i]; t=cnt;33 while(st[cnt+1]*2<=v[i]) cnt++;34 dfs(v[i]);35 --top; cnt=t;36 }37 } 38 39 int main(){40 freopen("zoo.in","r",stdin);freopen("zoo.out","w",stdout);41 scanf("%d",&q);42 while(q--){43 scanf("%s",ch+1); n=strlen(ch+1);44 getnext();45 for(int i=0;i<=n;i++) first[i]=0; tot=0;46 for(int i=1;i<=n;i++) addedge(next[i],i);47 ans=1,top=cnt=0;48 dfs(0);49 printf("%d\n",ans);50 }51 return 0;52 }
随机数生成器 random
傻逼题。暴力是n^2你可能以为是n^3去写线段树n^2logn那就70分洗洗睡吧。
最多取的数是2n，修改是o(n)，所以总的复杂度是o(n^2)。
若评测机不给力请不要两次取模。同步赛选手没有能A的。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #define MAXL 25000010 8 #define MAXN 10010 9 using namespace std;10 typedef long long LL;11 typedef short int SI;12 int t[MAXL]; SI x[MAXL],y[MAXL];13 SI sl[MAXN],sr[MAXN];14 int X,A,B,C,D;15 int n,m,q,l;16 LL x0,x1; 17 18 void swap(int&x,int&y){19 x^=y,y^=x,x^=y;20 }21 22 int main(){23 freopen("random.in","r",stdin);freopen("random.out","w",stdout);24 scanf("%d%d%d%d%d",&X,&A,&B,&C,&D);25 scanf("%d%d%d",&n,&m,&q);26 x0=X,l=n*m;27 for(int i=1;i<=l;i++){28 t[i]=i;29 x1=(x0*x0*A+x0*B+C)%D;30 if(x1%i+1!=i) swap(t[x1%i+1],t[i]);31 x0=x1;32 }33 int u,v;34 while(q--){35 scanf("%d%d",&u,&v);36 if(u!=v) swap(t[u],t[v]);37 }38 SI px=1,py=0;39 for(int i=1;i<=l;i++){40 py++;if(py>m) px++,py=1;41 x[t[i]]=px,y[t[i]]=py;42 }43 for(int i=1;i<=n;i++) sl[i]=1,sr[i]=m;44 int tot=n+m-1;45 for(int i=1;i<=l;i++)46 if(sl[x[i]]<=y[i]&&y[i]<=sr[x[i]]){47 tot--;48 if(tot) printf("%d ",i);49 else{50 printf("%d\n",i);51 break;52 }53 for(int j=1;j<x[i];j++) sr[j]=min(y[i],sr[j]);54 for(int j=x[i]+1;j<=n;j++) sl[j]=max(y[i],sl[j]);55 }56 return 0;57 }
购票 ticket
毫无疑问是今年比赛最有价值的题。30分送分，DP方程很显然。
dp[i]=min{dp[j]+(dist[i]-dist[j])*p[i]+q[i]),j是i的祖先
令k<j<i，dp[j]<dp[k]当且仅当(dp[j]-dp[k])/(dist[j]-dist[k])<p[i]，其中dist[]单调递增。
所以维护下凸壳优化DP。
笔者给出的是逗比做法，简洁易懂。
插入红色点，维护凸壳性质，会删去非最优的黄框中的点，他们一定是连续的，且接在最后的。
考虑是在树上，回溯时凸壳要退一步，删去红色点，接回黄框中的点。
似乎好像是split/merge操作，我就弄了棵splay来搞。
还有是距离限制。1..x都失效，我们需要得到x+1..father[i]的凸壳。
于是套棵线段树，能得到任意两点之间的凸壳。凸壳上二分斜率DP~
时间复杂度是nlog^2，空间是nlogn，不对也是nlog^2。
PS：线段树套splay确实是我最信不过的树套了，我的代码在链上的效率不高。有很优秀的算法请分享我。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #define INF 9000000000000000000LL 8 #define eps 1e-10 9 #define MAXN 200010 10 using namespace std; 11 typedef long long LL; 12 LL s[MAXN],p[MAXN],q[MAXN],l[MAXN],dist[MAXN],dp[MAXN]; 13 int father[MAXN],dep[MAXN],st[MAXN]; 14 int ch[MAXN*30][2],f[MAXN*30],pre[MAXN*30],suc[MAXN*30],b[MAXN*30],cnt; 15 int lc[MAXN][30],rc[MAXN][30]; 16 int n,t,now,tmp,low,high,mid; 17 18 struct edge{ 19 int v,next; 20 }e[MAXN]; 21 int h[MAXN],tot=0; 22 23 void addedge(int x,int y){ 24 ++tot;e[tot].v=y;e[tot].next=h[x];h[x]=tot; 25 } 26 27 double cross(double a,double b,double c,double d){ 28 return a*d-b*c; 29 } 30 31 void rotate(int x,int t){ 32 if(!x) return; 33 int y=f[x]; 34 f[x]=f[y];if(f[y]) ch[f[y]][ch[f[y]][1]==y]=x; 35 ch[y][t]=ch[x][!t];if(ch[x][!t]) f[ch[x][!t]]=y; 36 f[ch[x][!t]=y]=x; 37 } 38 39 void splay(int x,int goal){ 40 if(!x) return; 41 while(f[x]!=goal){ 42 if(f[f[x]]==goal) 43 rotate(x,ch[f[x]][1]==x); 44 else{ 45 int y=f[x],t=(ch[f[y]][1]==y); 46 if(ch[y][t]==x) rotate(y,t),rotate(x,t); 47 else rotate(x,!t),rotate(x,t); 48 } 49 } 50 } 51 52 int find(int x){ 53 int ret=0; 54 while(x) 55 if(pre[x]==0||(double)(dp[b[x]]-dp[b[pre[x]]])<(double)(dist[b[x]]-dist[b[pre[x]]])*p[now]) 56 ret=x,x=ch[x][1]; 57 else 58 x=ch[x][0]; 59 return ret; 60 } 61 62 int maintain(int x){ 63 int ret=0; 64 while(x) 65 if(pre[x]==0||cross(dist[b[x]]-dist[b[pre[x]]],dp[b[x]]-dp[b[pre[x]]],dist[now]-dist[b[x]],dp[now]-dp[b[x]])>eps) 66 ret=x,x=ch[x][1]; 67 else 68 x=ch[x][0]; 69 return ret; 70 } 71 72 struct segment_tree_node{ 73 int l,r,no,rt; 74 }a[MAXN*6]; 75 76 void Build(int k,int l,int r){ 77 a[k].l=l;a[k].r=r;a[k].no=a[k/2].no+1; 78 if(l==r) return;int mid=(l+r)>>1; 79 Build(k*2,l,mid); 80 Build(k*2+1,mid+1,r); 81 } 82 83 void Insert(int k){ 84 b[++cnt]=now,tmp=lc[now][a[k].no]=maintain(a[k].rt); 85 if(tmp){ 86 splay(a[k].rt=tmp,0); 87 if(t!=0&&t!=2) splay(rc[now][a[k].no]=suc[tmp],tmp); 88 ch[tmp][1]=suc[f[cnt]=pre[cnt]=tmp]=cnt; 89 } 90 else a[k].rt=cnt; 91 if(t==0||a[k].l==a[k].r) return; 92 if(dep[now]<=a[k*2].r) Insert(k*2); 93 else Insert(k*2+1); 94 } 95 96 void Delete(int k){ 97 if(tmp=lc[now][a[k].no]) splay(a[k].rt=tmp,0),ch[tmp][1]=suc[tmp]=rc[now][a[k].no]; else a[k].rt=0; 98 if(t==0||a[k].l==a[k].r) return; 99 if(dep[now]<=a[k*2].r) Delete(k*2);100 else Delete(k*2+1);101 }102 103 LL Query(int k,int x,int y){104 if(t==0||x<=a[k].l&&a[k].r<=y){105 int j=b[find(a[k].rt)];106 return dp[j]+(dist[now]-dist[j])*p[now]+q[now];107 }108 LL ret=INF;109 if(x<=a[k*2].r) ret=min(Query(k*2,x,y),ret);110 if(y>=a[k*2+1].l) ret=min(Query(k*2+1,x,y),ret);111 return ret; 112 }113 114 115 void dfs(int u){116 now=u,dep[u]=dep[father[u]]+1,dist[u]=dist[father[u]]+s[u];117 low=1,high=dep[father[u]];118 while(low<=high){119 mid=(low+high)>>1;120 if(dist[u]-dist[st[mid]]<=l[u]) high=mid-1;121 else low=mid+1;122 }123 dp[u]=dep[father[u]]?Query(1,high+1,dep[father[u]]):0;124 st[dep[u]]=u;Insert(1);125 for(int i=h[u];i;i=e[i].next) dfs(e[i].v);126 now=u;127 if(t!=0&&t!=2) Delete(1);128 }129 130 char buf[10000000],*pt = buf,*o = buf;131 LL getint(){132 LL x = 0;133 while((*pt < ‘0‘ || *pt > ‘9‘)) pt ++;134 x = *pt++ - 48;135 while(*pt >= ‘0‘ && *pt <= ‘9‘) x = x * 10 + *pt ++ - 48;136 return x;137 }138 139 int main(){140 freopen("ticket.in","r",stdin);freopen("ticket.out","w",stdout);141 fread(buf,1,10000000,stdin); 142 //scanf("%d%d",&n,&t);143 n=getint(),t=getint();144 for(int i=2;i<=n;i++){145 father[i]=getint(),s[i]=getint(),p[i]=getint(),q[i]=getint(),l[i]=getint();146 // scanf("%d%lld%lld%lld%lld",&father[i],&s[i],&p[i],&q[i],&l[i]);147 addedge(father[i],i);148 }149 Build(1,1,n);150 dfs(1);151 for(int i=2;i<=n;i++) printf("%lld\n",dp[i]);152 return 0;153 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。