当前位置：首页 > news >正文

10.18做题记

news 2024/10/23 21:04:20

关于jsz和lyq：不要再约会了啊喂！

P3130 [USACO15DEC] Counting Haybale P

1.本题是一道线段树板子题，简单分析一下题意：给定长度为N的数组，对这个数组分别进行区间加，区间取min，区间求和操作。

2.其他的不再进行阐述。

区间加：

void change(int p,int l,int r,int z){if(l<=t[p].l&&r>=t[p].r){t[p].add+=z;t[p].min+=z;t[p].sum+=(t[p].r-t[p].l+1)*z;return;}pushdown(p);int mid=t[p].l+t[p].r>>1;if(l<=mid) change(p<<1,l,r,z);if(r>mid) change(p<<1|1,l,r,z);pushup(p);
}

区间取min：

int querymin(int p,int l,int r){if(l<=t[p].l&&r>=t[p].r) return t[p].min;pushdown(p);int mid=t[p].l+t[p].r>>1;int ans=0x7f7f7f7f;if(l<=mid) ans=querymin(p<<1,l,r);if(r>mid) ans=min(ans,querymin(p<<1|1,l,r));return ans;
}

区间求和：

int querysum(int p,int l,int r){if(l<=t[p].l&&r>=t[p].r) return t[p].sum;pushdown(p);int mid=t[p].l+t[p].r>>1;int ans=0;if(l<=mid) ans+=querysum(p<<1,l,r);if(r>mid) ans+=querysum(p<<1|1,l,r);return ans;
}

最后给出完整代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,a[N];
char c;
struct tree{int l,r,min,sum,add;
}t[N<<2];
void pushup(int p){t[p].sum=t[p<<1].sum+t[p<<1|1].sum;t[p].min=min(t[p<<1].min,t[p<<1|1].min);
}
void pushdown(int p){if(!t[p].add) return;t[p<<1|1].add+=t[p].add;t[p<<1].add+=t[p].add;t[p<<1].min+=t[p].add;t[p<<1|1].min+=t[p].add;t[p<<1|1].sum+=(t[p<<1|1].r-t[p<<1|1].l+1)*t[p].add;t[p<<1].sum+=(t[p<<1].r-t[p<<1].l+1)*t[p].add;t[p].add=0;
}
void build(int p,int l,int r){t[p].l=l,t[p].r=r;if(l==r){t[p].min=t[p].sum=a[l];return;}int mid=l+r>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);pushup(p);
}
void change(int p,int l,int r,int z){if(l<=t[p].l&&r>=t[p].r){t[p].add+=z;t[p].min+=z;t[p].sum+=(t[p].r-t[p].l+1)*z;return;}pushdown(p);int mid=t[p].l+t[p].r>>1;if(l<=mid) change(p<<1,l,r,z);if(r>mid) change(p<<1|1,l,r,z);pushup(p);
}
int querysum(int p,int l,int r){if(l<=t[p].l&&r>=t[p].r) return t[p].sum;pushdown(p);int mid=t[p].l+t[p].r>>1;int ans=0;if(l<=mid) ans+=querysum(p<<1,l,r);if(r>mid) ans+=querysum(p<<1|1,l,r);return ans;
}
int querymin(int p,int l,int r){if(l<=t[p].l&&r>=t[p].r) return t[p].min;pushdown(p);int mid=t[p].l+t[p].r>>1;int ans=0x7f7f7f7f;if(l<=mid) ans=querymin(p<<1,l,r);if(r>mid) ans=min(ans,querymin(p<<1|1,l,r));return ans;
}
signed main(){scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}build(1,1,n);for(int i=1;i<=m;i++){cin>>c;if(c=='P'){int l,r,z;scanf("%lld%lld%lld",&l,&r,&z);change(1,l,r,z);}if(c=='M'){int l,r;scanf("%lld%lld",&l,&r);printf("%lld\n",querymin(1,l,r));}if(c=='S'){int l,r;scanf("%lld%lld",&l,&r);printf("%lld\n",querysum(1,l,r));}}return 0;
}

P2783 有机化学之神偶尔会做作弊

（关于一道黑题掉紫又掉蓝这回事）

1.又是一道做过的原题（悲），原题干简化后就是把n个点m条边的无向图中的环都变成一个点。（可能是因为题目太生草导致看不出来，也可能是个人问题...）。

2.思路简析：本题考查最近公共祖先，通过tarjan算法求解。

前置知识：1.tarjan缩点 2.倍增求LCA

可以按照原来无向图缩点的方法，但此时to!=fa[x]。

因为这是无向图，可能有的边会直接连向他父亲，假如要走这条边的话，就会重复搜，就这样一直无限循环下去。剩下的就和有向图的缩点没什么区别了。

接着就要考虑每个询问，把所有的环去掉后，就会得到一个有向无环图（树）。那么问题就会转化为树上问题。

本题也考察了十进制转化为二进制

void shuchu(int x){int xx=0;for(;x;x>>=1){xx++;if(x&1) t[xx]=1;else t[xx]=0;}for(int i=xx;i>=1;i--) printf("%d",t[i]);printf("\n");
}

一些小tips：

求两个点的LCA要在新的图上求。

tarjan缩点时要注意不能访问到父亲的边。

3.完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,u,v,x,y,tot,sum,cnt,num,topp,T;
int dep[N],fa[N],size[N],top[N],head[N],hed[N];
int shu[N],dfn[N],low[N],sta[N],son[N];
int t[N];
bool vis[N];
inline int read(){int s = 0,w = 1; char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10+ch -'0'; ch = getchar();}return s * w;
}
struct node{int to,net;
}e[N<<1],edge[N<<1];
void add(int x,int y){e[++tot].to = y;e[tot].net = head[x];head[x] = tot;
}
void add_(int x,int y){edge[++sum].to = y;edge[sum].net = hed[x];hed[x] = sum;
}
void tarjain(int x,int fa){dfn[x] = low[x] = num++;sta[++topp] = x; vis[x] = 1;for(int i = head[x]; i; i = e[i].net){int to = e[i].to;if(to == fa) continue;if(!dfn[to]){tarjain(to,x);low[x] = min(low[x],low[to]);}else if(vis[to]){low[x] = min(low[x],dfn[to]);}}if(dfn[x] == low[x]){cnt++; int y;do{y = sta[topp--];shu[y] = cnt;vis[y] = 0;}while(x != y);}
}
void get_tree(int x){dep[x] = dep[fa[x]] + 1; size[x] = 1;for(int i = hed[x]; i; i = edge[i].net){int to = edge[i].to;if(to == fa[x]) continue;fa[to] = x;get_tree(to);size[x] += size[to];if(size[to] > size[son[x]]) son[x] = to;}
}
void dfs(int x,int topp){top[x] = topp;if(son[x]) dfs(son[x],topp);for(int i = hed[x]; i; i = edge[i].net){int to = edge[i].to;if(to == fa[x] || to == son[x]) continue;dfs(to,to);}
}
int lca(int x,int y){while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]]) swap(x,y);x = fa[top[x]];}if(dep[x] < dep[y]) return x;else return y;
}
void shuchu(int x){int xx = 0;for(; x; x>>=1){xx++;if(x & 1) t[xx] = 1;else t[xx] = 0;}for (int i = xx; i >= 1; i--) printf("%d",t[i]);printf("\n");
}
int main(){n = read(); m = read();for(int i = 1; i <= m; i++){u = read(); v = read();add(u,v); add(v,u);}for(int i = 1; i <= n; i++){if(!dfn[i]) tarjain(i,0);}for(int i = 1; i <= n; i++){for(int j = head[i]; j; j = e[j].net){int to = e[j].to;if(shu[to] != shu[i]){add_(shu[i],shu[to]);}}}get_tree(1);dfs(1,1);T = read();while(T--){x = read(); y = read();int Lca = lca(shu[x],shu[y]);int ans = dep[shu[x]] + dep[shu[y]] - 2 * dep[Lca] + 1;shuchu(ans);}return 0;
}

P4251 [SCOI2015] 小凸玩矩阵

1.题目简述：给定一个n*m的矩阵，从中选出n个数，任意两个数都不能在同一行或同一列（简单来说，从n行中各选出1个数，使得这些数不在同一列），要求的是所选的n个数中第k大的数的最小值。

2.思路简述：本题可以使用网络流，（由于作者太菜）这里只讲二分答案和二分图匹配做法。

由于每行每列只能选一个，可以想到二分图，也就是将行和列连边。通过二分图匹配，就可以保证一行对应一边。因为要求出第 k 大数的最小值，于是想到二分出一个第 k 大的数，然后小于这个数的就行向列建边，跑出二分图最大匹配。如果最大匹配大于 n-k，就说明这个数字还可以变得更小，从而缩小二分的边界。

3.完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,K;
int a[255][255];
inline int read() {int tmp=0,w=1;char ch=0;while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}while(isdigit(ch)) tmp=(tmp<<1)+(tmp<<3)+ch-'0',ch=getchar();return tmp*w;
}
struct node {int v,nex;
}e[N*N];
int tot,h[N];
void add(int u,int v) {e[++tot].v=v,e[tot].nex=h[u],h[u]=tot;
}
bool vis[N];
int match[N];
bool find(int x) {int xx;for(int i=h[x];i;i=e[i].nex) {xx=e[i].v;if(!vis[xx]) {vis[xx]=1;if(!match[xx]||find(match[xx])) {match[xx]=x;return 1;}}}return 0;
}
bool pd(int mid) {memset(h,0,sizeof(h)),tot=1;memset(match,0,sizeof(match));for(int i=1;i<=n;++i) {for(int j=1;j<=m;++j) {if(a[i][j]<=mid) add(i,j+n);}}int res=0;for(int i=1;i<=n;++i) {memset(vis,0,sizeof(vis));res+=find(i);}return res>=n-K+1;
}
int maxx=-1e9,minn=1e9;
void Bsearch() {int l=minn,r=maxx,mid,ans;while(l<=r) {mid=(l+r)>>1;if(pd(mid)) r=mid-1,ans=mid;else l=mid+1;}printf("%d\n",ans);
}
int main(){n=read(),m=read(),K=read();for(int i=1;i<=n;++i) {for(int j=1;j<=m;++j) {a[i][j]=read();maxx=max(maxx,a[i][j]);minn=min(minn,a[i][j]);}}Bsearch();return 0;
}

P3266 [JLOI2015] 骗我呢

1.这道题比较考验思维，主要考察的是容斥原理+组合数学+dp。

2.讲这道题之前，先补充一下格路问题：从 (0,0) 点出发，每步只能沿 x 轴或 y 轴的正方向每步走一个单位，最终走到 (m,n) 点，有多少条路径—> 因为一共要走 m+n 步，其中必定有 m 步是向左走一格、有 n 步是向上走一格。所以方案数为 $C_{m+n}^{m}=C_{m+n}^{n}$ 。一般化：从 (m0,n0) 点出发，每步只能沿 x 轴或 y 轴的正方向每步走一个单位，最终走到 (m+m0,n+n0) 点，有多少条路径—> $C_{m+n}^{m}=C_{m+n}^{n}$ 条。

不能接触对角线的格路问题：假设要从 (0,0) 到 (m,n) （其中 m>n ），要求途径的每个点 (a,b) 都满足 a>b （除起点外）。首先第一步一定是 (0,0)→(1,0)，之后每1条接触对角线的道路都一一对应1条从 (0,1) 到 (m,n) 的道路（就是第一次接触对角线之前的道路做关于对角线的对称）。结果为 $C_{m+n-1}^{n}-C_{m+n-1}^{m}=C_{m+n}^{m}*(m-n)/(m+n)$ 。当m=n+1时，结果为 $C_{2n}^{n}/(n+1)$ ，即卡特兰数。

不能穿越对角线的格路问题：相当于将对角线上移一格，移到 l:y=x+1 。转化为不可“接触” l 的问题。后面的不多作赘述。

3.思路简述：可以分析出一个性质：每行是递增的并且一行m个元素，取值只能在[0,m]中选那么必然该行至多有一个位置与后一个位置相差2，其余的都只相差1。从而可以列出一个比较简单的dp：dp[i][j]表示第i行没有出现过的数是j的方案数， $dp[i][j]=\sum_{k=0}^{j+1}dp[i-1][k]$ ，至于上界为什么是j+1可以手动模拟一下，假设这行j没有出现过，上一行试一试j-1、j、j+1、j+2，发现大于j+1的就不合法了，略微优化一下就变成了dp[i][j]=dp[i-1][j+1]+dp[i][j-1]。（这应该只能得部分分，但作者的能力有限也就止步于此了~）