看见机房有大佬上周写了上面的普及信心赛 于是我康了康 8月的提高组模拟赛 9月的还没开始qwq
https://www.jisuanke.com/contest/3119?view=challenges
真的 有点难 主要是我先打开了T2 我再次 对自己的数学产生了怀疑
T1 又又又又都错题了 下次重建图 尽量写vector 都写 邻接表 变量差不多的容易搞混 我这个同学变又写错了
T1 ：https://nanti.jisuanke.com/t/41086
题目大意就是 一个有向图 删一个点 把与他直接和间接 相连的点 删掉 然后 求删掉所有点的最小最大代价 ；
为了避免这个环的情况 我们显然是先 tarjan 求一下强连通分量 然后考虑 缩点 显然是删掉这个强连通分量的任意一个点 这个强连通分量都会被删掉
但是题目要求我们求出最大最小代价 那我们在求tarjan的过程中 维护每一个块的最大最小代价
那么对于最小代价 显然是缩点之后入度为0的节点的代价的累和
对于最大代价 我们反向建图 从叶子结点往上便利 然后每一个连通块的最大代价 累和 即可
#include<bits/stdc++.h> using namespace std; const int inf=1e9; template<typename T>inline void read(T &x) { x=0;T f=1,ch=getchar(); while(!isdigit(ch)) ch=getchar(); if(ch=='-') f=-1, ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar(); x*=f; } const int N=250000; int n,m,x,y,cnt=0,ans1,ans2,num,tot,tc,top; int in1[N],in2[N],Stack[N],minn[N],cost[N],maxx[N],dfn[N],low[N],lin[N],linc[N],ins[N],belong[N]; struct gg { int y,next; }a[N],e[N]; inline void add(int x,int y) { a[++tot].y=y; a[tot].next=lin[x]; lin[x]=tot; } inline void add_c2(int x,int y) { e[++tc].y=y; e[tc].next=linc[x]; linc[x]=tc; } inline void tarjan(int x) { dfn[x]=low[x]=++num; Stack[++top]=x; ins[x]=1; for(int i=lin[x];i;i=a[i].next) { int y=a[i].y; if(!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); } else if(ins[y]) low[x]=min(low[x],dfn[y]); } if(dfn[x]==low[x]) { ++cnt; int k; do { k=Stack[top--]; ins[k]=0; belong[k]=cnt; minn[cnt]=min(minn[cnt],cost[k]); maxx[cnt]=max(maxx[cnt],cost[k]); }while(x!=k); } } inline void topsort() { queue<int>q; for(int i=1;i<=cnt;i++) if(!in2[i]) q.push(i); while(q.size()) { int x=q.front();ans2+=maxx[x]; q.pop(); for(int i=linc[x];i;i=e[i].next) { int y=e[i].y; in2[y]--; if(!in2[y]) q.push(y); } } } int main() { //freopen("1.in.cpp","r",stdin); read(n); read(m); for(int i=1;i<=n;i++) read(cost[i]),minn[i]=inf,maxx[i]=-inf; for(int i=1;i<=m;i++) { read(x); read(y); add(x,y); } for(int i=1;i<=n;i++) { if(!dfn[i]) tarjan(i); } for(int i=1;i<=n;i++) { //cout<<maxx[i]<<endl; for(int j=lin[i];j;j=a[j].next) { int y=a[j].y; if(belong[i]!=belong[y]) { //add_c(belong[i],belong[y]);没必要建图了; add_c2(belong[y],belong[i]); in1[belong[y]]++; in2[belong[i]]++; } } } ans1=ans2=0; for(int i=1;i<=cnt;i++) if(!in1[i]) ans1+=minn[i]; topsort(); printf("%d %d ",ans1,ans2); return 0; }
T2 恶心数学题？？？ 原来只做过一个简化版的qwq 模拟赛当时考了 然后暴毙了；
那个模拟赛 我也没有写题解 那我在这里总结一下好吧 题目大意：
从（0,0）这个点 不跨过 y=x 和 y=x-(n-m） 到达（n,m）的方案数 保证 n>=2m
显然需要用不考虑跨过任何一条直线的方案数-跨过某一条直线的方案数*2+跨过两条的方案数；
总的方案数 $ binom{n+m}{m}$
然后考虑 跨过某一条直线的方案数 $ binom{n+m}{m-1}$
因为题目保证n>=2m 所以跨过第二条直线的时候 就没有机会跨过第一个了qwq 所以一定是 先跨过第一条线 在跨过第二条线
用和卡特兰数类似的方法也能求出来 方案数 $ binom{n+m}{m}$-$ binom{n+m}{m-1}$*2+$ binom{n+m}{m-2}$
这个T2 就比较恶心了 目标就是求从 (0,0)走到 (n,m) 且不经过 y=x+a 和 y=x+b 这两条的方案数，模数为 998244353 。
考虑 怎么做呢 其实 我的思路也是在不断 订正的 我第一遍看到 不会写 只会分类讨论 但是 刘神 指导说 应该是有通解的
那么我们不妨一点一点思考 讨论一下 这种组合数求解 这种问题的方法 需要几个简单例子的引入
如果 给定 （n，m） 和一个点 p（a，b） 只能往右 往上走 求出 不经过这个点p 到达终点 的方案数
那么我们也是用所有的方案数 减去 经过 p的 方案数
总的方案数 $ binom{n+m}{m}$ 然后考虑 一定经过p的方案数 那么我们先从（0，0） 走到 （a，b） 的方案数 再求出 （a，b) 走到（n，m）的方案数 这样我们显然
可以推出 方案数为$ binom{n+m}{m}$-$ binom{a+b}{b}$*$ binom{m+n-a-b}{n-a}$
那么如果推广到T个点呢 T<=2000 题目链接：CF559C
我们发现白色点的数量是很多的qwq 但是黑色点最多2000个 我们应该利用黑色点进行转移 这个题目是从（1，1） 出发到（n，m）
所以说 如果不考虑 经过 黑色点 那么显然是 $ binom{H+W-2}{H-1}$ 如果我们求出来 从左上到右下 （和上面坐标设的不一样，但是思路是一样的 明白即可） 至少经过了一个黑色格子 的方案数
然后两者 相见 就是不经过黑色格子的方案数
我们首先 将所有的格子按照 行列递增 排序 我们假设 左上角是第0个黑色格子 然后 右下是第T+1 个黑色格子 设第i个格子 位于（xi，yi）
$$f[i]= binom{x_i-1+y_i-1}{x_i-1} - sum_{j=0}^{i-1} f[j] imes binom{x_i-x_j+y_i-y_j}{x_i-x_j} x_j le x_i, y_j le y_i$$
这个式子的意义是 枚举j作为从左上角 到（xi，yi）的第一个黑色格子 也就说不能经过其他黑色格子 的路线数
求和部分求出了 从左上角到（xi，yi），途中 经过至少 一个黑色格子 的方案数 用总数减去 那么就求出合法方案数了
我们不妨思考一下 这样写的 正确性 在这种计数类dp里面 最重要的就是 子问题不能重叠 既然我们需要求出 从左上角 到（xi，yi）至少经过一个黑色格子的方案数
枚举第一个经过的格子是哪个 前半部分j之前 不能拆开 因为是不经过黑色格子的 而第一个经过的黑色格子不同 那么 后面的路线也一定不同 这样就保证了 子问题是互斥 不重复的
对应加法和乘法原理 我们就求出来了不重复的方案 然后你搞一下 逆元啥了 注意取模 不要爆负
#include<bits/stdc++.h> using namespace std; #define x first #define y second template<typename T>inline void read(T &x) { x=0;T f=1,ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x*=f; } const int p=1000000007; typedef long long ll; const int N=200010; int H,W,T,f[2200]; ll jc[N],jcinv[N]; pair<int,int>a[2200]; //f[i]表示 从左上角 走到排序后的第i个黑格子 并且中途不经过其他黑格子 的方案数 inline int C(int n,int m) { return jc[n]*jcinv[m]%p*jcinv[n-m]%p; } inline ll power(ll a,int b) { ll res=1; while(b) { if(b&1) res=res*a%p; a=a*a%p; b>>=1; } return res; } int main() { //freopen("1..cpp","r",stdin); jc[0]=1;jcinv[0]=1; for(int i=1;i<=200000;i++) { jc[i]=jc[i-1]*i%p; jcinv[i]=power(jc[i],p-2); } read(H); read(W); read(T); for(int i=1;i<=T;i++) { read(a[i].x); read(a[i].y); } sort(a+1,a+T+1); a[T+1].x=H,a[T+1].y=W; for(int i=1;i<=T+1;i++) { f[i]=C(a[i].x+a[i].y-2,a[i].x-1); for(int j=1;j<i;j++) { if(a[j].x>a[i].x||a[j].y>a[i].y) continue; f[i]=(f[i]-(ll)f[j]*(C(a[i].x+a[i].y-a[j].x-a[j].y,a[i].x-a[j].x)))%p; } } cout<<(f[T+1]+p)%p<<endl; return 0; }
好了 我们又回到这个题目了qwq 具体怎么做呢 不如大力分类讨论一下先 毕竟我先看到T2 然后 想到要分类讨论 而且分类的情况较多 当时弃疗 不过如果真的分类讨论 也不是很麻烦qwq
对于a，b>n 或者 a，b< -m 显然发现的是 这两条直线 对答案是没有影响的 所以类比于我们上面使用的组合数
答案为 $ binom{n+m}{m}$ 这样可以获得十五分
那么 在考虑 n,m<1000 的部分 我们考虑 范围较小 不妨使用 动态规划 解决 这个问题
Fi,j 表示从（0，0） 走到（i，j）不经过两条直线的方案数 然后 由Fi-1,j和 Fi,j-1转移过来 并且判断边界
对于a ,b>0 我们考虑 只会有一条直线 产生贡献 那么 直接容斥 瞎搞就好了 ans=$ binom{n+m}{m}$-触碰到直线的方案
触碰到直线的方案是 从（0，0）到将（n，m) 关于直线对称后的点的方案数 思考是为什么呢
考虑所有触碰直线的路径 翻转之后必定到达同一个点 并且所有到达这个点的路径都在 第一次触碰直线后翻转也都恰好达到
所以直接到达翻转后的点的方案数就恰好是不合法的方案数
对于 a,b<0 方案数 和上面一样 这样我们已经把所有比较好拿到的分数 拿到了 接下来就是考虑100%的数据怎么写啦
对不起 还在研究题解 不过近段时间会补 我又来了！！！ 今天下午脑子清醒 写了一遍
我们已经知道了 $ANS= binom{n+m}{m}-先跨过A线的-先跨过B线的$
我们这里将 多次触碰视作一次触碰 所以触碰A线的路线只可能是 BABABABA....或者ABABABAB.....
对于先触碰A的方案数 我们可以考虑先删去以A结尾的方案数 然后加上以BA结尾的方案数 然后减去已ABA结尾的方案数 再加上以BABA结尾的方案数 以此类推
显然是（n）的 那么就解决了 先跨过A的方案数 那么 我们考虑 先跨过B的 我们依旧按照这样的方法做
至于这种 结尾方案数 我们是需要将 终点进行对称的 这样能保证最后一定经过A线 然后 将关于A对称后的点 记作P 我们再做P关于B的对称点 这样求出来的方案数
可以保证最后先经过B 然后经过A到达终点 然后 我们这样逆向思维就可以了 按照刚才的思路 我们就处理出来所有的方案数
这里为什么 倒着思考呢 为什么 能保证 最后的方案数 是先跨过A线的呢 而且 一加一减 是不是容斥原理的应用呢 这都是我需要在思考的地方 先把问题抛出 在做讨论
总的来说 比起 模拟赛上$y=x 和 y=x-(n-m)$的方案数来说 这种问题模型似乎是一种通解 这次我对这种组合数的理解 似乎加深了一点 包括隔板法的应用
可以借鉴 我为jzyz题库写的题解 这种数学模型真的是让信息选手头大啊
#include<bits/stdc++.h> using namespace std; template<typename T>inline void read(T &x) { x=0;T f=1,ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x*=f; } typedef long long ll; const int p=998244353; const int N=12000000; const int M=13000000; ll jc[M],jcinv[M]; int a,b,n,m; inline ll power(ll a,ll b) { ll res=1; while(b) { // cout<<"(("; if(b&1) (res*=a)%=p; (a*=a)%=p; b>>=1; } return res; } inline ll C(ll n,ll m) {//计算组合数 return jc[n]*jcinv[m]%p*jcinv[n-m]%p; } inline ll calc(ll n,ll m) { if(n<0||m<0) return 0; return C(n+m,n); } inline ll filpA(int &x,int &y) {//关于直线A对称 swap(x,y); x-=a; y+=a; } inline ll filpB(int &x,int &y) {//关于直线B对称 swap(x,y); x-=b; y+=b; } int main() { // freopen("1.in","r",stdin); read(n); read(m); read(a); read(b); jc[0]=1; for(int i=1;i<=N;i++) jc[i]=jc[i-1]*i%p; jcinv[N]=power(jc[N],p-2); for(int i=N-1;i>=0;--i) jcinv[i]=jcinv[i+1]*(i+1)%p; ll ans=calc(n,m); if(a<0&&b<0) a=max(a,b); if(a>0&&b>0) a=min(a,b); int x=n,y=m; while(x>=0&&y>=0) { filpA(x,y); ans-=calc(x,y); if((a<0&&b<0)||(a>0&&b>0)) { printf("%lld ",((ans%p)+p)%p); return 0; } filpB(x,y); ans+=calc(x,y); ans%=p; } x=n,y=m; while(x>=0&&y>=0) { filpB(x,y); ans-=calc(x,y); filpA(x,y); ans+=calc(x,y); ans%=p; } ans+=p; ans%=p; printf("%lld ",ans); return 0; }
T3 ：一看就是个数据结构的样子
有 n 个集合，编号为 1 到 n。有 m 次操作，每次输入 l,r,x 表示往编号在 [l,r]间的集合中的每个集合都插入一个数 x 。
最后对每个集合都询问他的最长连续段的长度是多少。
连续段 [l,r] 定义为在集合 S 中 l 到 r 的元素都出现过。
输入格式
第一行两个数 n,m 表示集合的个数和操作次数。
接下来 m 行每行三个数 l,r,x表示往集合 l 到集合 r 都插入 x。
输出格式
输出一行 n 个数，第 i 个数代表集合 i 的最长连续段。
数据范围与约定
对于 30% 的数据, n,m≤1000
对于 30% 的数据, l,r 随机。
对于 100% 的数据, n,m≤100000,1≤l≤r≤n,1≤x≤109
除 100% 的数据其他数据没有交集，保证同一个元素不会被多次插入同一个集合。
暴力模拟 可以拿到三十分
别管时间跑不跑的过 模拟就完事了 我们考虑开个set 每次暴力找到这个集合的最长连续段
#include<bits/stdc++.h> using namespace std; template<typename T>inline void read(T &x) { x=0;T f=1,ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x*=f; } const int N=1200000; set<int>S[N]; int n,m,tot,a[N]; inline int cal(int x) { set<int>::iterator it; tot=0; for(it=S[x].begin();it!=S[x].end();it++) a[++tot]=*it; if(S[x].empty()) return 0; int bns=1,ans=1; for(int i=2;i<=tot;i++) { if(a[i]-1==a[i-1]) bns++; else bns=1; ans=max(ans,bns); } return ans; } int main() { read(n); read(m); for(int i=1;i<=m;i++) { int l,r,x; read(l); read(r); read(x); for(int i=l;i<=r;i++) S[i].insert(x); } for(int i=1;i<=n;i++) printf("%d ",cal(i)); return 0; }
其实 我们还有一种操作 不妨将x 排序 然后考虑 操作的连续性 对于连续断开 考虑赋值 然后 查找 区间历史最大值？？？对不起 又口胡了
题解给的是扫描线的做法 看不懂 等下再学习吧。