「模拟8.18」字符串(卡特兰数)·乌鸦喝水(树状数组，二分)·所驼门王的宝藏(tarjan，拓扑)...-白红宇

「模拟8.18」字符串(卡特兰数)·乌鸦喝水(树状数组，二分)·所驼门王的宝藏(tarjan，拓扑)...

阅读量：5337 次

发布时间：2019-06-15

本文共 5062 字，大约阅读时间需要 16 分钟。

最近好颓啊，所以啥都做不出来

简单说一下这次考试，分机房了，还分不同考卷，果然我还是留在二机房的蒟蒻，

大概也只有这样的简单题，才能勉强水个rank 3吧........

其实不必管在哪个机房，努力便好，不必在意什么，这么多的考试，对于成绩的好与坏大概都看淡了，无论如何无愧于心便好。

************************

T1 字符串

一看就是卡特兰的裸题，

卡特兰........(留坑待补...)

然后C(n+m,n)-C(n+m,m-1)结束了

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #define int long long 8 #define MAXN 2500001 9 using namespace std;10 const int mod=20100403;11 int n,m;12 int jie[MAXN];13 int poww(int x,int y)14 {15 int ans=1ll;16 while(y)17 {18 if(y&1)ans=ans*x%mod;19 x=x*x%mod;20 y>>=1;21 }22 return ans%mod;23 }24 int C(int x,int y)25 {26 if(y>x)return 0;27 if(y==0)return 1;28 return jie[x]%mod*poww(jie[y]%mod,mod-2)%mod*poww(jie[x-y]%mod,mod-2)%mod;29 }30 signed main()31 {32 //freopen("text.in","r",stdin);33 //freopen("a.out","w",stdout); 34 scanf("%lld%lld",&n,&m);35 jie[0]=1;jie[1]=1;36 for(int i=2;i<=n+m+1;++i)jie[i]=(jie[i-1]*i)%mod;37 if(n

View Code

T2乌鸦喝水

打链接表能水到90？？？？？？

正解：

我们考虑维护变量pos_water(表示当前乌鸦在哪喝水)，pos表示当前轮到谁喝完了

我们预处理出每缸水能下降的次数然后sort一边，

易知，在i被下降到不能喝之前，i+1肯定能喝

根据性质，我们令pos_water移动

树狀数组维护从当前喝水点到n可喝水的缸数，

假设缸数加上上一个状态的cnt<此时节点的val，那么直接跳

不然二分查找停在那个位置

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
             8 #include
             
               9 #include
              
                10 #include
               
                 11 #define MAXN 2000001 12 #define ps push_back 13 #define int long long 14 using namespace std; 15 int c[MAXN]; 16 struct node{ int id,val;}e[MAXN]; 17 int n,m; 18 int lowbit(int x){ return x&(-x);} 19 void add(int x,int k) 20 { 21 for(int i=x;i<=n;i+=lowbit(i)) 22 { 23 c[i]+=k; 24 } 25 } 26 int query(int x) 27 { 28 int ans=0; 29 for(int i=x;i>=1;i-=lowbit(i)) 30 { 31 ans+=c[i]; 32 } 33 return ans; 34 } 35 int adds[MAXN]; 36 bool cmp(node a,node b) 37 { 38 return (a.val!=b.val)?(a.val
                
                 
                  >1; 88 if(query(mid)-last+cnt>e[pos].val) 89 r=mid; 90 else l=mid; 91 } 92 if(query(l)+cnt-last==e[pos].val) 93 { 94 end_pos=l; 95 } 96 else if(query(r)+cnt-last==e[pos].val) 97 end_pos=r; 98 cnt+=query(end_pos)-last; 99 if(end_pos!=n)100 pos_water=end_pos;101 else102 {103 cir++;104 pos_water=0;105 }106 add(pos_id,-1);107 pos++;pos_id=e[pos].id; 108 //printf("新pos_water=%lld cnt=%lld %lld %lld\n",pos_water,cnt,pos,cir); 109 }110 if(cir>=m&&pos>=n)break;111 }112 printf("%lld\n",cnt);113 }

View Code

tarjan

然后DFS会炸成n^2

要用拓扑

记清楚！！！！！！！！！！！！！！！！！！

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
             8 #include
             
               9 #include
              
                10 #include
               
                 11 #define MAXN 2000001 12 #define ps push_back 13 using namespace std; 14 int n,R,C; 15 vector
                
                 lie[MAXN]; 16 vector
                 
                  hang[MAXN]; 17 int dx[8]={ 0,1,0,-1,1,1,-1,-1}; 18 int dy[8]={ 1,0,-1,0,-1,1,1,-1}; 19 map
                  
                   
                    ,int>h; 20 struct no{ int to,n;}e1[MAXN*2],e2[MAXN*2]; 21 int head1[MAXN],tot1;int head2[MAXN],tot2; 22 void add1(int u,int v) 23 { 24 e1[++tot1].to=v;e1[tot1].n=head1[u];head1[u]=tot1; 25 } 26 void add2(int u,int v) 27 { 28 e2[++tot2].to=v;e2[tot2].n=head2[u];head2[u]=tot2; 29 } 30 struct node{ int x,y,data,id;}e[MAXN]; 31 int read() 32 { 33 int x=0;char c=getchar(); 34 while(c<'0'||c>'9') 35 { 36 c=getchar(); 37 } 38 while(c>='0'&&c<='9') 39 { 40 x=(x<<1)+(x<<3)+(c^48); 41 c=getchar(); 42 } 43 return x; 44 } 45 int d[MAXN]; 46 bool vis[MAXN];int maxn;int cnt; 47 stack
                    
                     q;int belong[MAXN]; 48 vector
                     
                      v[MAXN]; 49 int de=0,dfn[MAXN],low[MAXN]; 50 void tarjan(int x) 51 { 52 dfn[x]=low[x]=++de;vis[x]=1;q.push(x); 53 for(int i=head1[x];i;i=e1[i].n) 54 { 55 int to=e1[i].to; 56 if(!dfn[to]) 57 { 58 tarjan(to); 59 low[x]=min(low[x],low[to]); 60 } 61 else if(vis[to]) 62 { 63 low[x]=min(low[x],low[to]); 64 } 65 } 66 if(dfn[x]==low[x]) 67 { 68 cnt++; 69 int top=0; 70 while(top!=x) 71 { 72 top=q.top();q.pop();vis[top]=0;v[cnt].ps(top);belong[top]=cnt;d[cnt]++; 73 } 74 } 75 } 76 int ru[MAXN]; 77 void init() 78 { 79 for(int x=1;x<=n;++x) 80 { 81 for(int i=head1[x];i;i=e1[i].n) 82 { 83 int to=e1[i].to; 84 if(belong[x]==belong[to])continue; 85 add2(belong[x],belong[to]); 86 ru[belong[to]]++; 87 } 88 } 89 } 90 int len[MAXN]; 91 queue
                      
                       qq; 92 void tuopu() 93 { 94 for(int i=1;i<=cnt;++i) 95 { 96 if(ru[i]==0){qq.push(i);len[i]=d[i];} 97 } 98 while(!qq.empty()) 99 {100 int x=qq.front();101 qq.pop();102 for(int i=head2[x];i;i=e2[i].n)103 {104 int to=e2[i].to;105 len[to]=max(len[x]+d[to],len[to]);106 maxn=max(len[to],maxn);ru[to]--;107 if(ru[to]==0)qq.push(to);108 }109 }110 }111 signed main()112 {113 n=read();R=read();C=read();114 for(int i=1;i<=n;++i)115 {116 e[i].x=read();e[i].y=read();e[i].data=read();117 e[i].id=i;118 hang[e[i].x].ps(i);119 lie[e[i].y].ps(i);120 h[make_pair(e[i].x,e[i].y)]=e[i].id;121 }122 for(int i=1;i<=n;++i)123 {124 if(e[i].data==1)125 {126 for(int k=0;k