最近好颓啊，所以啥都做不出来
简单说一下这次考试，分机房了，还分不同考卷，果然我还是留在二机房的蒟蒻，
大概也只有这样的简单题，才能勉强水个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 }
T3
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，拓扑)
原文：https://www.cnblogs.com/Wwb123/p/11373988.html
