csp2019备赛之刷题赛-round3

csp2019备赛之刷题赛-round3

link to this contest

C. Winner

大意：有$n$个人打淘汰赛，每个人有$3$个权值，只要有一个权值大于对方就有可能获胜，问每个人是否有可能夺冠

$n leq 10^5$

题解：对于三维权值，每一维都排一次序，权值大的向权值小的连边，如果有权值相同，就开两个出入的虚点，如果存在一条$x-->y$的路径就说明$x$可能打败$y$，然后缩点，没有入度的那个块里面的点都可能拿冠军

  1 #include<bits/stdc++.h>
  2 namespace csx_std {
  3     using namespace std;
  4     typedef long long ll;
  5     #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
  6     #define For(i,a,b) for (register int i=(a);i>=(b);i--)
  7     #define mem(i,j) memset(i,j,sizeof(i))
  8     #define pii pair<int,int>
  9     #define MP make_pair
 10     #define fi first
 11     #define se second
 12     #define GO(u) for (register int j=first[u];j!=-1;j=nxt[j])
 13     const int N=4e5+5;
 14     const int mod=1e9+7;
 15     inline int qpow(int x,int y) {int ret=1;for (;y;y>>=1,x=1LL*x*x%mod) if (y&1) ret=1LL*ret*x%mod;return ret;}
 16     inline int Inv(int x) {return qpow(x,mod-2);}
 17     inline void upd(int &x,int y) {x=(1LL*x+y)%mod;return;}
 18     inline int chkmax(int &x,int y) {return (x<y)?(x=y,1):0;}
 19     inline int chkmin(int &x,int y) {return (x>y)?(x=y,1):0;}
 20     inline int read()
 21     {
 22         int x=0,f=1;
 23         char c=getchar();
 24         while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
 25         while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
 26         return f*x;
 27     }
 28     inline void write(int x)
 29     {
 30         if (x<0) x=-x,putchar('-');
 31         if (x>9) write(x/10);
 32         putchar(x%10+'0');
 33         return;
 34     }
 35 }
 36 using namespace csx_std;
 37 int n,q,Q[N],ans[N],vis[N],dfn[N],low[N],stck[N],dfnn=0;
 38 int bl[N],du[N],cnt,top=0,siz[N],gp=0,tag=0;
 39 int tot=0,first[N],nxt[N];
 40 struct E
 41 {
 42     int u,v;
 43 }e[N];
 44 inline void add(int u,int v)
 45 {
 46     if (!v) return;
 47     tot++;
 48     nxt[tot]=first[u];
 49     first[u]=tot;
 50     e[tot]=(E){u,v};
 51 //    printf("(%d,%d)
",u,v);
 52     return;
 53 }
 54 struct data
 55 {
 56     int a,b,c,id;
 57 }f[N];
 58 bool cmp1(const data x,const data y) {return x.a<y.a;}
 59 bool cmp2(const data x,const data y) {return x.b<y.b;}
 60 bool cmp3(const data x,const data y) {return x.c<y.c;}
 61 inline void build()
 62 {
 63     int last=0;
 64     sort(f+1,f+n+1,cmp1);
 65     FOR(i,1,n)
 66     {
 67         int r=i;
 68         while (f[i].a==f[r+1].a) r++;
 69         if (i<r)
 70         {
 71             cnt++;
 72             add(cnt,last);
 73             FOR(j,i,r) add(f[j].id,cnt);
 74             cnt++;
 75             FOR(j,i,r) add(cnt,f[j].id);
 76             last=cnt;
 77         }
 78         else add(f[i].id,last),last=f[i].id;
 79         i=r;
 80     }
 81     
 82     last=0;
 83     sort(f+1,f+n+1,cmp2);
 84     FOR(i,1,n)
 85     {
 86         int r=i;
 87         while (f[i].b==f[r+1].b) r++;
 88         if (i<r)
 89         {
 90             cnt++;
 91             add(cnt,last);
 92             FOR(j,i,r) add(f[j].id,cnt);
 93             cnt++;
 94             FOR(j,i,r) add(cnt,f[j].id );
 95             last=cnt;
 96         }
 97         else add(f[i].id,last),last=f[i].id;
 98         i=r;
 99     }
100     
101     last=0;
102     sort(f+1,f+n+1,cmp3);
103     FOR(i,1,n)
104     {
105         int r=i;
106         while (f[i].c==f[r+1].c) r++;
107         if (i<r)
108         {
109             cnt++;
110             add(cnt,last);
111             FOR(j,i,r) add(f[j].id,cnt);
112             cnt++;
113             FOR(j,i,r) add(cnt,f[j].id );
114             last=cnt;
115         }
116         else add(f[i].id,last),last=f[i].id;
117         i=r;
118     }
119     return;
120 }
121 inline void Tarjan(int u)
122 {
123     dfn[u]=low[u]=++dfnn;
124     vis[u]=1;
125     stck[++top]=u;
126     GO(u)
127     {
128         int v=e[j].v;
129         if (!dfn[v])
130         {
131             Tarjan(v);
132             chkmin(low[u],low[v]);
133         }
134         else if (vis[v]) chkmin(low[u],dfn[v]);
135     }
136     if (low[u]==dfn[u])
137     {
138         gp++;
139         while (stck[top+1]!=u)
140         {
141             bl[stck[top]]=gp;
142             vis[stck[top]]=0;
143             if (stck[top]<=n) siz[gp]++;
144             top--;
145         }
146     }
147     return;
148 }
149 int main()
150 {
151     mem(first,-1);
152     n=read(),q=read();
153     cnt=n;
154     FOR(i,1,n) f[i].a=read();
155     FOR(i,1,n) f[i].b=read();
156     FOR(i,1,n) f[i].c=read();
157     FOR(i,1,n) f[i].id=i;
158     FOR(i,1,q) Q[i]=read();
159     build();
160     FOR(i,1,cnt) 
161         if (!dfn[i]) Tarjan(i);
162     FOR(i,1,tot) if (bl[e[i].u]!=bl[e[i].v]) du[bl[e[i].v]]++;
163     FOR(i,1,gp) if (!du[i])
164     {
165         tag=i;
166         break;
167     }
168     FOR(i,1,n) if (bl[i]==tag) vis[i]=1;
169     FOR(i,1,q) ans[i]=vis[Q[i]];
170     FOR(i,1,q)
171         if (ans[i]) printf("YES
");
172         else printf("NO
");
173     return 0;
174 }
175 /*
176 4 4
177 1 2 3 4
178 1 2 4 3
179 2 1 3 4
180 1
181 2
182 3
183 4
184 */
View Code

D. Independent set

大意：给你一个$n$个点$m$条边的无向图，请你求出所有子图的最大独立集大小之和

$n leq 26,m leq frac{n(n-1)}{2}$

题解：

  • 设与$i$距离$leq 1$的点集的压缩状态为$edge_i$，$f_S$表示状态$S$的最大独立集大小
  • 于是有转移$f_S=max{f_{S-lowbit(S)},f_{S& (`edge_{ lowbit(S)} ) } }$
 1 #include<bits/stdc++.h>
 2 namespace csx_std {
 3     using namespace std;
 4     typedef long long ll;
 5     #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
 6     #define For(i,a,b) for (register int i=(a);i>=(b);i--)
 7     #define mem(i,j) memset(i,j,sizeof(i))
 8     #define pii pair<int,int>
 9     #define pb push_back
10     #define MP make_pair
11     #define fi first
12     #define se second
13     #define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
14     const int N=1e5+5;
15     const int mod=1e9+7;
16     inline int qpow(int x,int y) {int ret=1;for (;y;y>>=1,x=1LL*x*x%mod) if (y&1) ret=1LL*ret*x%mod;return ret;}
17     inline int Inv(int x) {return qpow(x,mod-2);}
18     inline void upd(int &x,int y) {x=(1LL*x+y)%mod;return;}
19     inline int chkmax(int &x,int y) {return (x<y)?(x=y,1):0;}
20     inline int chkmin(int &x,int y) {return (x>y)?(x=y,1):0;}
21     inline int read()
22     {
23         int x=0,f=1;
24         char c=getchar();
25         while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
26         while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
27         return f*x;
28     }
29     inline void write(ll x)
30     {
31         if (x<0) x=-x,putchar('-');
32         if (x>9) write(x/10);
33         putchar(x%10+'0');
34         return;
35     }
36 }
37 using namespace csx_std;
38 int n,m,edge[26],tmp1,tmp2;
39 char f[1<<26];
40 ll ans=0;
41 inline int lowbit(int x) {return x&-x;}
42 int main()
43 {
44     n=read(),m=read();
45     FOR(i,0,n-1) edge[i]|=1<<i;
46     FOR(i,1,m)
47     {
48         tmp1=read(),tmp2=read();
49         edge[tmp1]|=1<<tmp2;
50         edge[tmp2]|=1<<tmp1;
51     }
52     FOR(i,1,(1<<n)-1) 
53     {
54         int tmp=lowbit(i);
55         tmp=log2(tmp);
56         f[i]=max((int)f[i xor lowbit(i)],f[i & (~edge[tmp])]+1);
57     }
58     FOR(i,0,(1<<n)-1) ans+=f[i];
59     write(ans);
60     return 0;
61 }
View Code

E. Train Driver

大意：给出一个n个点m条边的无向图，肥宅和死肥宅决定同时追求女神,他们决定以最短的距离去到女神的位置，肥宅的家在点集SA中的某个点(等概率的)，死肥宅则在SB中，女神会在图中任意一个点出现(也可以出现在肥宅或者死肥宅的家中)，现在你想知道,如果他们3个人要在图中的某个点集合，那么他们所走过的最短路径的期望值是多少?

$1leq n,m leq 10^5,|SA|,|SB| leq 20$

题解：

  • 首先，期望改计数，我们要对于$|SA| imes |SB|$种肥宅出没的情况下，女神出现在任意地方的路径总和
  • 首先，大力$BFS$预处理出每个肥宅位到每个点的距离，考虑现在枚举两个肥宅的位置，我们如何知道女神出现在这$n$个点的距离总和，我们令$dis_i=disa_{u,i}+disb_{v,i}$，表示假设女神在$i$的最短距离总和，这么初始化是假设女神不动，然后这些值排个序放进一个队列里面，逐个松弛，新入队的点加入另一个队列（像是个输出值不为$0$的广搜）
  1 #include<bits/stdc++.h>
  2 namespace csx_std {
  3     using namespace std;
  4     typedef long long ll;
  5     #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
  6     #define For(i,a,b) for (register int i=(a);i>=(b);i--)
  7     #define mem(i,j) memset(i,j,sizeof(i))
  8     #define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
  9     const int N=2e5+5;
 10     inline int read()
 11     {
 12         int x=0,f=1;
 13         char c=getchar();
 14         while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
 15         while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
 16         return f*x;
 17     }
 18 }
 19 using namespace csx_std;
 20 int T,n,m,nsa,nsb,sa[25],sb[25],dis[N],disa[25][N],disb[25][N];
 21 int line[N],l,r,cnt[N<<2],tmp1,tmp2,gcd;
 22 ll ans=0;
 23 queue <int> q;
 24 int tot=0,f[N],nxt[N];
 25 struct E{int u,v;}e[N];
 26 inline void add(int u,int v)
 27 {
 28     tot++;
 29     nxt[tot]=f[u];
 30     f[u]=tot;
 31     e[tot]=(E){u,v};
 32     return;
 33 }
 34 inline int GCD(int x,int y)
 35 {
 36     if (!y) return x;
 37     if (x<y) return GCD(y,x);
 38     return GCD(y,x%y);
 39 }
 40 inline void BFS(int *d,int S)
 41 {
 42     d[S]=0;
 43     while (q.size()) q.pop();
 44     q.push(S);
 45     while (q.size())
 46     {
 47         int u=q.front();
 48         q.pop();
 49         GO(u) if (d[e[j].v]==-1) {d[e[j].v]=d[u]+1;q.push(e[j].v);}
 50     }
 51     return;
 52 }
 53 inline void BFS2()
 54 {
 55     while (q.size()) q.pop();
 56     while (l<=r||q.size())
 57     {
 58         int u;
 59         if (q.size()&&l>r) u=q.front(),q.pop();
 60         else if (q.empty()&&l<=r) u=line[l++];
 61         else if (dis[q.front()]<=dis[line[l]]) u=q.front(),q.pop();
 62         else u=line[l++];
 63         GO(u) if (dis[e[j].v]>dis[u]+1) {dis[e[j].v]=dis[u]+1;q.push(e[j].v);}
 64     }
 65     return;
 66 }
 67 inline void Sort()
 68 {
 69     l=1,r=n;
 70     FOR(i,0,n<<1) cnt[i]=0;
 71     FOR(i,1,n) cnt[dis[i]]++;
 72     FOR(i,1,n<<1) cnt[i]+=cnt[i-1];
 73     For(i,n,1) line[cnt[dis[i]]--]=i;
 74     return;
 75 }
 76 inline void clear()
 77 {
 78     FOR(i,0,n) f[i]=-1;
 79     tot=ans=0;
 80     return;
 81 }
 82 int main()
 83 {
 84 //    freopen("data.in","r",stdin);
 85     mem(f,-1);
 86     T=read();
 87     FOR(Case,1,T)
 88     {
 89         n=read(),m=read();
 90         FOR(i,1,m) tmp1=read(),tmp2=read(),add(tmp1,tmp2),add(tmp2,tmp1);
 91         nsa=read();
 92         FOR(i,1,nsa) sa[i]=read();
 93         nsb=read();
 94         FOR(i,1,nsb) sb[i]=read();
 95         FOR(i,1,nsa) 
 96         {
 97             FOR(j,0,n) disa[i][j]=-1;
 98             BFS(disa[i],sa[i]);
 99         }
100         FOR(i,1,nsb)
101         {
102             FOR(j,0,n) disb[i][j]=-1;
103             BFS(disb[i],sb[i]);
104         } 
105         FOR(i,1,nsa) FOR(j,1,nsb)
106         {
107             FOR(k,1,n) dis[k]=disa[i][k]+disb[j][k];
108             Sort();
109             BFS2();
110             FOR(k,1,n) ans+=dis[k];
111         }
112         gcd=GCD(ans,1LL*nsa*nsb*n);
113         printf("Case #%d: %lld/%lld
",Case,ans/gcd,1LL*nsa*nsb*n/gcd);
114         clear();
115     }
116     return 0;
117 }
View Code

F. Explorer

大意：给定一张无向图,每条边有权值范围$[l_i,r_i]$,要经过这条边的条件是你的容量要在$[l_i,r_i]$,现在问你有多少种容量,使得你能从$1$走到$n$

$n,m leq 10^5 , l,r leq 10^9$

题解：线段树分治加可撤销并查集，其中我们需要把权值区间离散化，那么我们线段树上的节点不能再使用闭区间了，否则$(mid,mid+1)$之间的权值会蒸发，改成左闭右开的区间就行了

  1 #include<bits/stdc++.h>
  2 namespace csx_std {
  3     using namespace std;
  4     typedef long long ll;
  5     #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
  6     #define For(i,a,b) for (register int i=(a);i>=(b);i--)
  7     #define mem(i,j) memset(i,j,sizeof(i))
  8     #define pii pair<int,int>
  9     #define pb push_back
 10     #define MP make_pair
 11     #define fi first
 12     #define se second
 13     #define GO(u) for (register int j=first[u];j!=-1;j=nxt[j])
 14     const int N=3e5+5;
 15     const int mod=1e9+7;
 16     inline int qpow(int x,int y) {int ret=1;for (;y;y>>=1,x=1LL*x*x%mod) if (y&1) ret=1LL*ret*x%mod;return ret;}
 17     inline int Inv(int x) {return qpow(x,mod-2);}
 18     inline void upd(int &x,int y) {x=(1LL*x+y)%mod;return;}
 19     inline int chkmax(int &x,int y) {return (x<y)?(x=y,1):0;}
 20     inline int chkmin(int &x,int y) {return (x>y)?(x=y,1):0;}
 21     inline int read()
 22     {
 23         int x=0,f=1;
 24         char c=getchar();
 25         while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
 26         while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
 27         return f*x;
 28     }
 29     inline void write(ll x)
 30     {
 31         if (x<0) x=-x,putchar('-');
 32         if (x>9) write(x/10);
 33         putchar(x%10+'0');
 34         return;
 35     }
 36 }
 37 using namespace csx_std;
 38 int n,m,fa[N],dep[N];
 39 ll ans=0,b[N<<1],len=0;
 40 int in1[N],in2[N],in3[N],in4[N];
 41 struct data
 42 {
 43     int u,v,w;
 44 };
 45 vector <data> vec[N<<2];
 46 inline int getfa(int x) {return (x==fa[x])?x:getfa(fa[x]);}
 47 inline int con(int x,int y)
 48 {
 49     int fx=getfa(x),fy=getfa(y);
 50     return (fx==fy);
 51 }
 52 inline data link(int x,int y)
 53 {
 54     data ret;
 55     int fx=getfa(x),fy=getfa(y);
 56     if (dep[fx]>dep[fy]) swap(x,y),swap(fx,fy);
 57     ret.u=fx,ret.v=fy;
 58     fa[fx]=fy;
 59     if (dep[fx]==dep[fy]) dep[fy]++,ret.w=1;
 60     else ret.w=0;
 61     return ret;
 62 }
 63 inline void del(vector <data> V)
 64 {
 65     For(i,(int)V.size()-1,0)
 66     {
 67         dep[V[i].v]-=V[i].w;
 68         fa[V[i].u]=V[i].u;
 69     }
 70     return;
 71 }
 72 inline void insert(int p,int l,int r,int L,int R,int ith)
 73 {
 74     if (L<=l&&r<=R) {vec[p].pb((data){in1[ith],in2[ith],0});return;}
 75     if (l==r-1) return;
 76     int mid=(l+r)>>1;
 77     if (L<=mid) insert(p<<1,l,mid,L,R,ith);
 78     if (R>mid) insert(p<<1|1,mid,r,L,R,ith);
 79     return;
 80 }
 81 inline void solve(int p,int l,int r)
 82 {
 83     vector <data> rub;
 84     rub.clear();
 85     FOR(i,0,(int)vec[p].size()-1) if (!con(vec[p][i].u,vec[p][i].v)) rub.pb(link(vec[p][i].u,vec[p][i].v));
 86     if (con(1,n)) {ans+=b[r]-b[l];del(rub);return;}
 87     if (l==r-1) {del(rub);return;}
 88     int mid=(l+r)>>1;
 89     solve(p<<1,l,mid);
 90     solve(p<<1|1,mid,r);
 91     del(rub);
 92     return;
 93 }
 94 inline void debug(int p,int l,int r)
 95 {
 96     printf("[%d,%d] : 
",l,r);
 97     FOR(i,0,(int)vec[p].size()-1)
 98     {
 99         printf("(%d,%d) ",vec[p][i].u,vec[p][i].v);
100     }
101     putchar('
');
102     int mid=(l+r)>>1;
103     if (l==r) return;
104     debug(p<<1,l,mid);
105     debug(p<<1|1,mid+1,r);
106     return;
107 }
108 int main()
109 {
110     n=read(),m=read();
111     FOR(i,1,n) fa[i]=i,dep[i]=1;
112     FOR(i,1,m) in1[i]=read(),in2[i]=read(),in3[i]=read(),in4[i]=read()+1,b[++len]=in3[i],b[++len]=in4[i];
113     sort(b+1,b+len+1);
114     len=unique(b+1,b+len+1)-b-1;
115     FOR(i,1,m) in3[i]=lower_bound(b+1,b+len+1,in3[i])-b,in4[i]=lower_bound(b+1,b+len+1,in4[i])-b;
116     FOR(i,1,m) insert(1,1,len,in3[i],in4[i],i);
117     solve(1,1,len);
118     write(ans),putchar('
');
119 //    debug(1,1,len);
120     return 0;
121 }
122 /*
123 5 5
124 1 2 10 40
125 2 3 10 20
126 3 5 20 40
127 2 4 10 30
128 4 5 20 40
129 */
View Code

G. Inner World

大意：有$n$棵树，一开始都只有一个$1$号节点，先有$m$个种植操作，后有$q$个询问操作

  • 种植操作形如$u,v,l,r$，表示$[l,r]$的树上的$u$号节点多了一个$v$号儿子（保证每次的$v$互不相同）
  • 询问操作形如$x,l,r$，表示询问$[l,r]$的树上的$x$号节点的子树大小之和

题解：

  • 由于每次的$v$互补相同，那么每个点出现的位置是连续区间，并且如果我们把所有种植操作集中在一棵树上，那么所有的树都会是这棵树的子图
  • 我们给这棵树表上$dfs$序，那么我们把树的下标和$dfs$序看作二维空间，每个种植操作相当于给一个线段加上$1$，每个询问操作相当于问某个矩形内的和
  • 我们扫描线枚举$dfs$序这一维，把询问拆开塞到某两个$dfs$序位置即可，线段树维护区间加，区间询问
  1 #include<bits/stdc++.h>
  2 namespace csx_std {
  3     using namespace std;
  4     typedef long long ll;
  5     #define FOR(i,a,b) for (register ll i=(a);i<=(b);i++)
  6     #define mem(i,j) memset(i,j,sizeof(i))
  7     #define pb push_back
  8     #define GO(u) for (register ll j=f[u];j!=-1;j=nxt[j])
  9     const ll N=3e5+5;
 10     inline ll read()
 11     {
 12         ll x=0,f=1;
 13         char c=getchar();
 14         while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
 15         while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
 16         return f*x;
 17     }
 18     inline void write(ll x)
 19     {
 20         if (x<0) x=-x,putchar('-');
 21         if (x>9) write(x/10);
 22         putchar(x%10+'0');
 23         return;
 24     }
 25 }
 26 using namespace csx_std;
 27 ll n,m,tmp1,tmp2,tmp3,tmp4,L[N],R[N],q,ans[N];
 28 ll tot=0,f[N],nxt[N],back[N],l[N],r[N],dfnn=0;
 29 struct E {ll u,v;}e[N];
 30 inline void Add(ll u,ll v)
 31 {
 32     tot++;
 33     nxt[tot]=f[u];
 34     f[u]=tot;
 35     e[tot]=(E){u,v};
 36     return;
 37 }
 38 struct data{ll id,l,r,fh;};
 39 vector <data> G[N];
 40 inline void dfs(ll u)
 41 {
 42     l[u]=++dfnn;
 43     back[dfnn]=u;
 44     GO(u) dfs(e[j].v);
 45     r[u]=dfnn;
 46     return;
 47 }
 48 ll t[N<<2],tag[N<<2];
 49 #define mid ((l+r)>>1)
 50 #define ls p<<1
 51 #define rs p<<1|1
 52 #define lson ls,l,mid
 53 #define rson rs,mid+1,r
 54 inline void up(ll p) {t[p]=t[ls]+t[rs];return;}
 55 inline void down(ll p,ll l,ll r)
 56 {
 57     if (!tag[p]) return;
 58     t[ls]+=(mid-l+1)*tag[p];
 59     t[rs]+=(r-mid)*tag[p];
 60     tag[ls]+=tag[p],tag[rs]+=tag[p];
 61     tag[p]=0;return;
 62 }
 63 inline void md(ll p,ll l,ll r,ll L,ll R,ll v)
 64 {
 65     if (L<=l&&r<=R) {t[p]+=(r-l+1)*v;tag[p]+=v;return;}
 66     down(p,l,r);
 67     if (L<=mid) md(lson,L,R,v);
 68     if (R>mid) md(rson,L,R,v);
 69     up(p);return;
 70 }
 71 inline ll qr(ll p,ll l,ll r,ll L,ll R)
 72 {
 73     if (L<=l&&r<=R) return t[p];
 74     down(p,l,r);
 75     ll ret=0;
 76     if (L<=mid) ret+=qr(lson,L,R);
 77     if (R>mid) ret+=qr(rson,L,R);
 78     up(p);return ret;
 79 }
 80 #undef mid
 81 #undef ls
 82 #undef rs
 83 #undef lson
 84 #undef rson
 85 int main()
 86 {
 87 //    freopen("data.in","r",stdin);
 88 //    freopen("myans.out","w",stdout);
 89     mem(f,-1);
 90     n=read(),m=read();
 91     L[1]=1,R[1]=n;
 92     FOR(i,1,m) tmp1=read(),tmp2=read(),tmp3=read(),tmp4=read(),Add(tmp1,tmp2),L[tmp2]=tmp3,R[tmp2]=tmp4;
 93     dfs(1);
 94     q=read();
 95     FOR(i,1,q) 
 96     {
 97         tmp1=read(),tmp2=read(),tmp3=read();
 98         G[l[tmp1]-1].pb((data){i,tmp2,tmp3,-1});
 99         G[r[tmp1]].pb((data){i,tmp2,tmp3,1});
100     }
101     FOR(i,1,dfnn)
102     {
103         ll u=back[i];
104         md(1,1,n,L[u],R[u],1);
105         FOR(j,0,(ll)G[i].size()-1)
106             ans[G[i][j].id]+=G[i][j].fh*qr(1,1,n,G[i][j].l,G[i][j].r);
107     }
108     FOR(i,1,q) write(ans[i]),putchar('
');
109     return 0;
110 }
View Code

H. Jump Frog

大意：有个青蛙要从$0$跳到$n$，每次至少跳$d$，其中有$m$个限制形如$t_i,p_i$，表示第$t_i$步不能跳到$p_i$问有多少种方案

$n,d leq 10^9,m leq 3000$

题解：

  • 我们称一个限制为一个关键点，答案就是总方案减去经过关键点的方案，关键点按步数排序
  • 设$cal(x,y)$为$y$步跳$x$距离的方案数，插板法$O(1)$计算，设$g_i$为跳距离$i$的方案数，$DP$计算
  • 枚举第一个经过的关键点，设从$0$不经过任何关键点到第$i$个关键点的方案是$dp_i$，那么$Ans=sum dp_i imes g_{n-p_i}$
  • 考虑平方的转移求出$dp$数组，$dp_i=cal(0,t_i)-sum_{j=1}^{i-1} dp_j imes cal(p_i-p_j,t_i-t_j)$
  • 总之这题就是大力容斥
 1 #include<bits/stdc++.h>
 2 namespace csx_std {
 3     using namespace std;
 4     typedef long long ll;
 5     #define FOR(i,a,b) for (register ll i=(a);i<=(b);i++)
 6     #define For(i,a,b) for (register ll i=(a);i>=(b);i--)
 7     #define mem(i,j) memset(i,j,sizeof(i))
 8     #define pii pair<ll,ll>
 9     #define pb push_back
10     #define MP make_pair
11     #define fi first
12     #define se second
13     #define GO(u) for (register ll j=f[u];j!=-1;j=nxt[j])
14     const ll N=3030;
15     const ll M=1e7+5;
16     const ll mod=998244353;
17     inline ll qpow(ll x,ll y) {ll ret=1;for (;y;y>>=1,x=1LL*x*x%mod) if (y&1) ret=1LL*ret*x%mod;return ret;}
18     inline ll Inv(ll x) {return qpow(x,mod-2);}
19     inline void upd(ll &x,ll y) {x=(1LL*x+y)%mod;return;}
20     inline ll read()
21     {
22         ll x=0,f=1;
23         char c=getchar();
24         while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
25         while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
26         return f*x;
27     }
28     inline void write(ll x)
29     {
30         if (x<0) x=-x,putchar('-');
31         if (x>9) write(x/10);
32         putchar(x%10+'0');
33         return;
34     }
35 }
36 using namespace csx_std;
37 ll n,d,m,g[M],sum_g[M],fac[M],inv[M],dp[N],ans=0;
38 struct data {ll t,p;}f[N];
39 bool operator <(data x,data y) {return x.t<y.t;}
40 inline ll C(ll x,ll y) {if (x<y) return 0;return 1LL*fac[x]*inv[y]%mod*inv[x-y]%mod;}
41 inline ll cal(ll x,ll y) {return C(x-y*(d-1)-1,y-1);}
42 int main()
43 {
44 //    freopen("data.in","r",stdin);
45 //    freopen("myans.out","w",stdout);
46     n=read(),d=read(),m=read();
47     FOR(i,1,m) f[i].t=read(),f[i].p=read();
48     sort(f+1,f+m+1);
49     g[0]=fac[0]=1;
50     FOR(i,1,n) fac[i]=1LL*fac[i-1]*i%mod;
51     inv[n]=Inv(fac[n]);
52     For(i,n-1,0) inv[i]=1LL*inv[i+1]*(i+1)%mod;
53     FOR(i,0,d-1) sum_g[i]=1;
54     FOR(i,d,n) g[i]=sum_g[i-d],sum_g[i]=(1LL*sum_g[i-1]+g[i])%mod;
55     FOR(i,1,m)
56     {
57         ll ban=0;
58         FOR(j,0,i-1) if (f[j].p<=f[i].p)
59             upd(ban,1LL*dp[j]*cal(f[i].p-f[j].p,f[i].t-f[j].t)%mod);
60         dp[i]=(1LL*cal(f[i].p,f[i].t)-ban+mod)%mod;
61     }
62     FOR(i,1,m) upd(ans,1LL*dp[i]*g[n-f[i].p]%mod);
63     ans=(1LL*g[n]-ans+mod)%mod;
64     write(ans),putchar('
');
65     return 0;
66 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/C-S-X/p/11791641.html