2018.8.8 Noip2018模拟测试赛（二十一）

日期：	八月七号	总分：	300分
难度：	提高 ~ 省选	得分：	112分（OvO）

题目目录：

　　T1：幸福的道路

　　T2：Solitaire

　　T3：Flags

赛后心得：

第一题裸树d啊！竟然花了一个多小时才切掉……

第二题输出样例成功骗到12分。

题解：

T1：幸福的道路

树形dp，先两次dfs算出每个点的最长路，用两个单调队列维护每天的极差……做完了……

CODE：

 #include<iostream>

 #include<queue>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 int n,m,x,tot=,h[];

 long long y,f[],g[],a[];

 struct Edge{

     int x,next;

     long long dis;

 }e[];

 int q1[],q2[];

 inline void add_edge(int x,int y,long long z){

     e[++tot].x=y,e[tot].dis=z;

     e[tot].next=h[x],h[x]=tot;

 }

 void dfs1(int x,int fa){

     for(int i=h[x];i;i=e[i].next){

         if(e[i].x==fa)continue;

         dfs1(e[i].x,x);

         f[x]=max(f[x],f[e[i].x]+e[i].dis);

     }

 }

 void dfs2(int x,int fa){

     long long maxn=,sec=;

     for(int i=h[x];i;i=e[i].next){

         if(e[i].x==fa)continue;

         if(f[e[i].x]+e[i].dis>maxn)

             sec=maxn,maxn=f[e[i].x]+e[i].dis;

         else sec=max(sec,f[e[i].x]+e[i].dis);

         g[e[i].x]=g[x]+e[i].dis;

     }

     for(int i=h[x];i;i=e[i].next){

         if(e[i].x==fa)continue;

         if(f[e[i].x]+e[i].dis==maxn)

             g[e[i].x]=max(g[e[i].x],sec+e[i].dis);

         else g[e[i].x]=max(g[e[i].x],maxn+e[i].dis);

         dfs2(e[i].x,x);

     }

 }

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++){

         scanf("%d%lld",&x,&y);

         add_edge(i,x,y);

         add_edge(x,i,y);

     }

     dfs1(,-),dfs2(,-);

     for(int i=;i<=n;i++)a[i]=max(f[i],g[i]);

     int l1=,l2=,r1=,r2=,tmp=,ans=;;

     for(int i=;i<=n;i++){

         while(l1<=r1&&a[i]<=a[q1[r1]])r1--;

         while(l2<=r2&&a[i]>=a[q2[r2]])r2--;

         q1[++r1]=i,q2[++r2]=i;

         if(a[q2[l2]]-a[q1[l1]]>m){

             if(q2[l2]<=q1[l1])tmp=q2[l2],l2++;

             else tmp=q1[l1],l1++;

         }

         ans=max(ans,i-tmp);

     }

     printf("%d",ans);

 }

T2：Solitaire

题解戳这里

CODE：

 #include<iostream>

 #include<cstdio>

 using namespace std;

 #define mod 1000000007

 int n,k,ans,f[][],sum[];

 int main(){

     scanf("%d%d",&n,&k);

     f[][n+]=;

     for(int i=;i<=k;i++)

         for(int j=n+;j>=;j--){

             sum[j]=(sum[j+]+f[i-][j])%mod;

             f[i][j]=(j<=n-i+?sum[j]:);

         }

     ans=(f[k][]-f[k-][]+mod)%mod;

     for(int i=;i<=n-k-;i++)ans=(ans+ans)%mod;

     printf("%d",ans);

 }

T3：Flags

2-sat 问题

题解戳这里

CODE：

 #include<iostream>

 #include<cstdio>

 #include<stack>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int v[];

 int n,x,y,tot=,h[];

 int scc[],dfn[],low[],C,cnt;

 bool vis[];

 struct Edge{

     int x,next;

 }e[];

 pair<int,int> a[];

 stack<int> s;

 inline void add_edge(int x,int y){

     e[++tot].x=y;

     e[tot].next=h[x],h[x]=tot;

 }

 void tarjan(int x){

     dfn[x]=low[x]=++cnt;

     s.push(x),vis[x]=true;

     for(int i=h[x];~i;i=e[i].next){

         if(!dfn[e[i].x]){

             tarjan(e[i].x),low[x]=min(low[x],low[e[i].x]);

         }else if(vis[e[i].x]){

             low[x]=min(low[x],dfn[e[i].x]);

         }

     }

     if(dfn[x]==low[x]){

         C++;

         int tmp;

         for(;;){

             tmp=s.top();

             vis[tmp]=false,scc[tmp]=C;

             s.pop();

             if(tmp==x)break;

         }

     }

 }

 void build(int o,int l,int r){

     if(r-l==){

         add_edge(o+n*,a[l].second^);

         return;

     }

     add_edge(o+n*,(o<<)+n*);

     add_edge(o+n*,(o<<|)+n*);

     int mid=l+r>>;

     build(o<<,l,mid),build(o<<|,mid,r);

 }

 void link(int o,int l,int r,int x,int y,int a){

     if(l>=x&&r<=y){

         add_edge(a,o+n*);

         return;

     }

     int mid=l+r>>;

     if(x<mid)link(o<<,l,mid,x,y,a);

     if(y>mid)link(o<<|,mid,r,x,y,a);

 }

 inline pair<int,int> get(int x,int len){

     int l=,r=x;

     pair<int,int> ans;

     while(l<r){

         int mid=l+r>>;

         if(a[x].first-a[mid].first<len)r=mid;

         else l=mid+;

     }

     ans.first=l;

     l=x,r=n*-;

     while(l<r){

         int mid=l+r+>>;

         if(a[mid].first-a[x].first<len)l=mid;

         else r=mid-;

     }

     ans.second=l;

     return ans;

 }

 inline bool check(int d){

     memset(scc,,sizeof(scc));

     memset(dfn,,sizeof(dfn));

     memset(low,,sizeof(low));

     memset(h,-,sizeof(h)),tot=;

     build(,,n*);

     for(int i=;i<n*;i++){

         int id=a[i].second;

         pair<int,int> x=get(i,d);

         if(i<x.second)link(,,n*,i+,x.second+,id);

         if(x.first<i)link(,,n*,x.first,i,id);

     }

     C=cnt=;

     for(int i=;i<n*;i++)if(!dfn[i])tarjan(i);

     for(int i=;i<n*;i++)

         if(scc[a[i].second]==scc[a[i].second^])return false;

     return true;

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<n;i++){

         scanf("%d%d",&x,&y);

         a[*i+]=make_pair(x,*i+);

         a[*i]=make_pair(y,*i);

     }

     sort(a,a+n*);

     int l=,r=;

     while(l<r){

         int mid=l+r+>>;

         if(check(mid))l=mid;

         else r=mid-;

     }

     printf("%d",l);

 }

巴特西

2018.8.8 Noip2018模拟测试赛（二十一）

题目目录：

赛后心得：

题解：

T1：幸福的道路

CODE：

T2：Solitaire

CODE：

T3：Flags

CODE：

最新文章

热门文章