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

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

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

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

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

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

T1 字符串

一看就是卡特兰的裸题，

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

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

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<cstring>

 4 #include<cmath>

 5 #include<string>

 6 #include<algorithm>

 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<m)printf("0\n");

38     else

39     printf("%lld\n",(C(n+m,n)-C(n+m,m-1)+mod)%mod);

40 }

T2乌鸦喝水

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

正解：

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

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

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

根据性质，我们令pos_water移动

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

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

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

  1 #include<iostream>

  2 #include<cstdio>

  3 #include<cstring>

  4 #include<cmath>

  5 #include<string>

  6 #include<algorithm>

  7 #include<map>

  8 #include<vector>

  9 #include<stack>

 10 #include<queue>

 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<b.val):(a.id<b.id);

 39 }

 40 int k;

 41 signed main()

 42 {

 43

 44     //freopen("text.in","r",stdin);

 45     //freopen("b.out","w",stdout);

 46     scanf("%lld%lld%lld",&n,&m,&k);

 47     for(int i=1;i<=n;++i){scanf("%lld",&e[i].val);e[i].id=i;add(e[i].id,1);}

 48     for(int i=1;i<=n;++i)scanf("%lld",&adds[i]);

 49     for(int i=1;i<=n;++i)

 50     {

 51         e[i].val=(k-e[i].val)/adds[i]+1;

 52         //printf("e[%lld].val=%lld\n",i,e[i].val);

 53     }

 54     sort(e+1,e+n+1,cmp);

 55     int pos=1,pos_water=0,cnt=0,cir=0;

 56     for(pos=1;pos<=n;++pos)if(e[pos].val!=0)break;

 57     int pos_id=e[pos].id;

 58     while(pos<=n&&cir<m)

 59     {

 60          int nxt=query(n);

 61          int last=query(pos_water);

 62          pos_id=e[pos].id;

 63          //printf("pos=%lld nxt=%lld last=%lld %lld\n",pos,nxt,last,cir);

 64          //printf("比较%lld %lld\n",nxt+cnt-last,e[pos].val);

 65          if(nxt+cnt-last<e[pos].val)

 66          {

 67               cnt+=nxt-last;

 68               cir++;

 69               pos_water=0;

 70               //printf("更改 pos_water=%lld cnt=%lld cir=%lld\n",pos_water,cnt,cir);

 71          }

 72          else if(nxt+cnt-last==e[pos].val)

 73          {

 74              cnt+=nxt-last;

 75              cir++;

 76              pos_water=0;

 77              add(e[pos].id,-1);

 78              pos++;

 79              pos_id=e[pos].id;

 80          }

 81          else

 82          {

 83              int l=pos_water+1;int r=n;int end_pos=pos_water;

 84              //printf("l%lld r=%lld\n",l,r);

 85              while(l+1<r)

 86              {

 87                    int mid=(l+r)>>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              else

102              {

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 }

tarjan

然后DFS会炸成n^2

要用拓扑

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

  1 #include<iostream>

  2 #include<cstdio>

  3 #include<cstring>

  4 #include<cmath>

  5 #include<string>

  6 #include<algorithm>

  7 #include<map>

  8 #include<vector>

  9 #include<stack>

 10 #include<queue>

 11 #define MAXN 2000001

 12 #define ps push_back

 13 using namespace std;

 14 int n,R,C;

 15 vector<int>lie[MAXN];

 16 vector<int>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<pair<int,int>,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<int>q;int belong[MAXN];

 48 vector<int>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<int>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<hang[e[i].x].size();++k)

127            {

128                int j=hang[e[i].x][k];

129                if(j==e[i].id)continue;

130                add1(e[i].id,j);

131            }

132         }

133         if(e[i].data==2)

134         {

135            for(int k=0;k<lie[e[i].y].size();++k)

136            {

137                int j=lie[e[i].y][k];

138                if(j==e[i].id)continue;

139                add1(e[i].id,j);

140            }

141         }

142         if(e[i].data==3)

143         {

144             for(int j=0;j<=7;++j)

145             {

146                 int x=e[i].x;int y=e[i].y;

147                 if(h[make_pair(x+dx[j],y+dy[j])]!=0)

148                 {

149                      add1(e[i].id,h[make_pair(x+dx[j],y+dy[j])]);

150                 }

151             }

152         }

153     }

154     for(int i=1;i<=n;++i)

155     {

156         if(!dfn[i])tarjan(i);

157     }

158     init();tuopu();

159     printf("%lld\n",maxn);

160 }

巴特西

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

最新文章

热门文章