JSOI 2012~2013 C 游戏中的学问

题面：bzoj
题解：递推
注意一个圈至少要三小我私家……（上来以为是圆摆列然后WA）
式子看代码吧

I 侦探jyy

题面：bzoj
题解：bfs
对付每个事件，，假设他必需产生
那么有两种可能
一是由他往上只要有一个点是一开始钦定了要产生
二是由所有入度为零且不是他祖先的点往下推，推完后还有钦定被产生而没有产生的

Q 贪心的导游

题面：bzoj
题解：主席树
看到\(a[i],p\leq 1000\)，可以考虑暴力
每次在主席树的\([l,r]\)区间找到对应的数字
具体看代码吧

C code

#include<bits/stdc++.h> using namespace std; #define ll long long ll s[3005][3005],n,k,p; int main() { scanf("%lld%lld%lld",&n,&k,&p); s[0][0]=1; for(int j=1;j<=k;++j) for(int i=3*j;i<=n;++i) s[i][j]=(1ll*(i-1)*(i-2)*s[i-3][j-1]+1ll*(i-1)*s[i-1][j])%p; printf("%lld\n",s[n][k]); return 0; }

I code

#include<bits/stdc++.h> using namespace std; #define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout); inline void read(int& x) { x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=x*10+c-'0',c=getchar(); } #define maxn 100005 struct Edge { int fr,to; }eg[maxn<<1],eg_rev[maxn<<1]; int head[maxn],head_rev[maxn],edgenum,deg[maxn]; inline void add(int fr,int to) { eg[++edgenum]=(Edge){head[fr],to}; eg_rev[edgenum]=(Edge){head_rev[to],fr}; ++deg[to]; head[fr]=head_rev[to]=edgenum; } queue<int> q; int vis[maxn],Clock; int d,n,m,ans[maxn],ans_cnt,a[maxn],vis_a[maxn]; void bfs(Edge* eg,int* head) { int id; while(!q.empty()) { id=q.front();q.pop(); vis[id]=Clock; for(int i=head[id];i;i=eg[i].fr) if(vis[eg[i].to]!=Clock) vis[eg[i].to]=Clock,q.push(eg[i].to); } } bool check(int x) { ++Clock; q.push(x); bfs(eg_rev,head_rev); for(int i=1;i<=d;++i) if(vis[a[i]]==Clock) return true; for(int i=1;i<=n;++i) if(!deg[i]&&vis[i]!=Clock) q.push(i); bfs(eg,head); for(int i=1;i<=d;++i) if(vis[a[i]]!=Clock) return true; return false; } int main() { read(n),read(m),read(d); int x,y; for(int i=1;i<=m;++i) read(x),read(y),add(x,y); for(int i=1;i<=d;++i) read(a[i]),vis_a[a[i]]=1; for(int i=1;i<=n;++i) if(vis_a[i]||check(i)) ans[++ans_cnt]=i; sort(ans+1,ans+ans_cnt+1); for(int i=1;i<=ans_cnt;++i) printf("%d ",ans[i]); puts(" "); return 0; }

Q code #include<bits/stdc++.h> using namespace std; #define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout); inline void read(int& x) { x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=x*10+c-'0',c=getchar(); } #define maxn 1000005 int ls[maxn*20],rs[maxn*20],val[maxn*20],rt[maxn],tot; void build(int& rt,int l,int r) { rt=++tot; if(l==r) return; int mid=(l+r)>>1; build(ls[rt],l,mid); build(rs[rt],mid+1,r); } void update(int& rt,int las,int l,int r,int pos) { rt=++tot; ls[rt]=ls[las],rs[rt]=rs[las],val[rt]=val[las]+1; if(l==r) return; int mid=(l+r)>>1; if(pos<=mid) update(ls[rt],ls[rt],l,mid,pos); else update(rs[rt],rs[rt],mid+1,r,pos); } #define Maxn 1000 int ans; void query(int fr,int to,int l,int r,int L)//主席树盘问区间最大值 { int mid; while(true) { if(l==r) break; mid=(l+r)>>1; if(val[rs[to]]>val[rs[fr]]) l=mid+1,fr=rs[fr],to=rs[to]; //if(val[rs[to]]-val[rs[fr]]>0) 右边有就右边 else r=mid,fr=ls[fr],to=ls[to]; } ans=max(ans,l-L); } void solve(int fr,int to,int l,int r,int qfr,int qto,int pos)//有点类似线段树，找到对应区间 { if(val[fr]==val[to]) return; if(qfr<=l&&qto>=r) return query(fr,to,l,r,pos); int mid=(l+r)>>1; if(qfr<=mid) solve(ls[fr],ls[to],l,mid,qfr,qto,pos); if(qto>mid) solve(rs[fr],rs[to],mid+1,r,qfr,qto,pos); } int main() { //file("test"); int n,m; read(n),read(m); build(rt[0],0,Maxn); int tp,l,r,p; for(int i=1;i<=n;++i) read(p),update(rt[i],rt[i-1],0,Maxn,p); while(m--) { read(l),read(r),read(p),++l,++r; if(l>r) swap(l,r); tp=ans=0; while(tp<=Maxn) { solve(rt[l-1],rt[r],0,Maxn,tp,min(tp+p-1,Maxn),tp);//暴力 tp+=p; if(ans==p-1) break; } printf("%d\n",ans); } return 0; }