Catalan数不能再裸了
#include<cstdio> #include<iostream> #include<cstring> using namespace std; typedef long long ll; const ll mod=20100403; const int N=2000005; ll n,m; ll fac[N]; ll qpow(ll a,ll b) { ll res=1;a=a%mod; while(b) { if(b&1)res=res*a%mod; a=a*a%mod; b>>=1; } return res; } ll C(ll x,ll y) { if(y>x)return 0; return fac[x]*(qpow(fac[y]*fac[x-y]%mod,mod-2))%mod; } ll lucas(ll x,ll y) { if(!y)return 1; return C(x%mod,y%mod)*lucas(x/mod,y/mod)%mod; } void ini() { fac[0]=1; for(ll i=1;i<=m+n;i++) fac[i]=fac[i-1]*1LL*i%mod; } int main() { scanf("%lld%lld",&n,&m); ini(); ll ans=(lucas(m+n,m)-lucas(m+n,m-1)+mod)%mod; cout<<ans<<endl; return 0; }
很能开阔思路的乱搞题。对于每一个缸算出它最多下降的次数，连同它所在的位置进行二元组排序。设rest表示剩下多少缸还能喝，now表示过了几轮，total表示一共喝了多少次水，num[]表示每个缸喝的次数。显然所求即为$\sum num[i]$
对于每一个缸，二分它还能被喝几轮，如果第i个缸还能喝cnt轮，后面(排序后)的缸自然也可以喝cnt轮。易得$num[i]=now+cnt$，之后用树状数组判断位置在i之前的缸能否让它再喝一次，即剩下的次数是否大于等于在该缸之前(包括)的缸数，如果是的话now和num[]都要++。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> using namespace std; typedef long long ll; #define pa pair<ll,ll> const int N=100005; int n,m,tot,rest,now; ll x,w[N],a[N],num[N],cnt,total,ans; pa bu[N]; namespace bit { ll c[N]; int lb(int x){return x&-x;} void add(int x) { for( ;x<=n;x+=lb(x)) c[x]++; } int ask(int x) { int res=0; for( ;x;x-=lb(x)) res+=c[x]; return res; } } int main() { scanf("%d%d%lld",&n,&m,&x); for(int i=1;i<=n;i++) scanf("%lld",&w[i]); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=n;i++) if(x>=w[i])bu[++tot]=make_pair((x-w[i])/a[i]+1,tot); sort(bu+1,bu+tot+1); rest=tot; for(int i=1;i<=tot;i++) { int l=0,r=m-now; while(l<=r) { int mid=l+r>>1; if(1LL*rest*mid<bu[i].first-total)l=mid+1,cnt=mid; else r=mid-1; } if(now+cnt==m) { ans+=(tot-i+1)*m; cout<<ans<<endl; exit(0); } num[i]=now+cnt; int pre=bu[i].second-bit::ask(bu[i].second); bit::add(bu[i].second); if(bu[i].first-rest*cnt-total>=pre)total++,num[i]++; total+=cnt*rest,now+=cnt; rest--; ans+=num[i]; } cout<<ans<<endl; return 0; }
十分不敢相信居然会有这么水的省选题……
可以发现跳过去再跳过来的情况对统计答案造成了困难，所以考虑缩点。把整张图缩成一个森林之后我们要让它经过的点尽量多，所以找联通的最长链。
一句话题解：将每个格子和它能到达的格子暴力连边，然后Tarjan缩点，最后跑一遍拓扑求树上最长链就是答案。
#include<cstdio> #include<iostream> #include<cstring> #include<vector> #include<queue> #include<algorithm> using namespace std; const int M=1000005,N=1e5+5; int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-‘0‘,ch=getchar(); return x*f; } struct room_ { int x,y,op; }a[N]; int n,R,C; vector<int> h[M],l[M],g[N]; int tot,head[M<<2],nxt[M<<2],to[M<<2],deg[N],ans[N]; void add(int x,int y) { to[++tot]=y; nxt[tot]=head[x]; head[x]=tot; } int dfn[N],low[N],st[N],top=0,vis[N],bel[N],scc,ind,size[N]; void tarjan(int x) { dfn[x]=low[x]=++ind; vis[x]=1; st[++top]=x; for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(!dfn[y])tarjan(y),low[x]=min(low[x],low[y]); else if(vis[y])low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]) { scc++;int now=0; do { now=st[top--]; size[scc]++; bel[now]=scc; vis[now]=0; }while(now!=x); } } int main() { n=read();R=read();C=read(); for(int i=1;i<=n;i++) { a[i].x=read(),a[i].y=read(),a[i].op=read(); h[a[i].x].push_back(i);l[a[i].y].push_back(i); } for(int i=1;i<=n;i++) { int op=a[i].op; if(op==1) { int sz=h[a[i].x].size(); for(int j=0;j<sz;j++) { if(h[a[i].x][j]==i)continue; add(i,h[a[i].x][j]); } } else if(op==2) { int sz=l[a[i].y].size(); for(int j=0;j<sz;j++) { if(l[a[i].y][j]==i)continue; add(i,l[a[i].y][j]); } } else if(op==3) { int sz; if(a[i].x>1) { sz=h[a[i].x-1].size(); for(int j=0;j<sz;j++) { if(a[h[a[i].x-1][j]].y>=a[i].y-1&&a[h[a[i].x-1][j]].y<=a[i].y+1) add(i,h[a[i].x-1][j]); } } sz=h[a[i].x].size(); for(int j=0;j<sz;j++) { if(h[a[i].x][j]==i)continue; if(a[h[a[i].x][j]].y>=a[i].y-1&&a[h[a[i].x][j]].y<=a[i].y+1) add(i,h[a[i].x][j]); } if(a[i].x<R) { sz=h[a[i].x+1].size(); for(int j=0;j<sz;j++) { int now=h[a[i].x+1][j]; if(a[now].y>=a[i].y-1&&a[now].y<=a[i].y+1) add(i,now); } } } } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); for(int x=1;x<=n;x++) for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(bel[y]!=bel[x]) g[bel[x]].push_back(bel[y]),deg[bel[y]]++; } //debug(); //puts("----------------------------------------"); /* for(int i=1;i<=scc;i++) if(!v[i]) { num=0,dfs(i); }*/ queue<int> q; for(int i=1;i<=scc;i++) if(!deg[i])q.push(i),ans[i]=size[i]; while(!q.empty()) { int x=q.front(); q.pop();int sz=g[x].size(); for(int i=0;i<sz;i++) { int y=g[x][i]; ans[y]=max(ans[y],ans[x]+size[y]); if(!(--deg[y]))q.push(y); } } cout<<*max_element(ans+1,ans+1+scc)<<endl; return 0; }
原文：https://www.cnblogs.com/Rorschach-XR/p/11373906.html
