2019 杭电多校（第三场）

本文主要是介绍2019 杭电多校（第三场），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1002 Blow up the city （支配树）

http://acm.hdu.edu.cn/showproblem.php?pid=6604

题意

给你个DAG图 然后若干次询问 每次询问给你两个点 问你去掉某个点使这量两个点不能到达最终点

进阶版 https://blog.csdn.net/sdut_jk17_zhangming/article/details/98069924

思路

去掉不能到达 即给定点是去掉点的支配点 建支配树即可

代码

#include <bits/stdc++.h>using namespace std;
const int maxn = 1e5+10;
vector<int> G[maxn];
vector<int> E[maxn];
vector<int> T[maxn];
int fa[maxn][20],deep[maxn];
int dfn[maxn],in[maxn];
int n,m;
int ans[maxn];
void init()
{memset(in,0,sizeof(in));for(int i = 0;i <= n;i++){E[i].clear(),G[i].clear(),T[i].clear();}
}
int LCA(int u,int v)
{if(deep[u] < deep[v]) swap(u,v);for(int i = 18;i >= 0;i--){if(deep[fa[u][i]] >= deep[v])u = fa[u][i];}if(u == v) return u;for(int i = 18;i >= 0;i--){if(fa[u][i] != fa[v][i]){u = fa[u][i];v = fa[v][i];}}return fa[u][0];
}
void solve(int u)
{int x = G[u][0];for(int i = 1;i < G[u].size();i++){x = LCA(x,G[u][i]);}T[x].push_back(u);deep[u] = deep[x]+1;fa[u][0] = x;for(int j = 1;j <= 18;j++){fa[u][j] = fa[fa[u][j-1]][j-1];}
}
void topsort()
{for(int i = 1;i <= n;i++){if(in[i] == 0){G[i].push_back(0);E[0].push_back(i);}}queue<int> q;q.push(0);deep[0] = 0;while(!q.empty()){int x = q.front();q.pop();for(int i = 0;i < E[x].size();i++){int y = E[x][i];in[y]--;if(in[y]<= 0){q.push(y);solve(y);}}}
}
void dfs(int u,int num)
{ans[u] = num;for(int i = 0;i < T[u].size();i++){int v = T[u][i];dfs(v,ans[u]+1);}
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);init();for(int i = 1;i <= m;i++){int u,v;scanf("%d%d",&u,&v);in[u]++;E[v].push_back(u);G[u].push_back(v);}topsort();dfs(0,1);int qw;scanf("%d",&qw);while(qw--){int u,v;scanf("%d%d",&u,&v);int w = LCA(u,v);int sum = ans[u] + ans[v] - ans[w] - 1;printf("%d\n",sum);}}return 0;
}

1004 Distribution of books

http://acm.hdu.edu.cn/showproblem.php?pid=6606

题意

给你n个数 让你从前面取若干数 分成k个区间 让区间最大值最小

思路

最大值最小 二分

 

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 10;
const ll inf = 1e18;
ll a[maxn],b[maxn];
int tree[maxn*4];
int n,k,tot;
void build(int x,int l,int r)
{tree[x] = 0;if(l == r) return ;int mid = (l + r) / 2;build(x*2,l,mid);build(x*2+1,mid+1,r);
}
int query(int x,int l,int r,int L,int R)
{if(L <= l&&R >= r) return tree[x];int mid = (l + r) / 2;int res = 0;if(L <= mid) res = max(query(x*2,l,mid,L,R),res);if(R > mid) res = max(res,query(x*2+1,mid+1,r,L,R));return res;
}
void update(int x,int l,int r,int pos,int val)
{if(l == r){tree[x] = max(val,tree[x]);return ;}int mid = (l + r) / 2;if(pos <= mid) update(x*2,l,mid,pos,val);if(pos > mid) update(x*2+1,mid+1,r,pos,val);tree[x] = max(tree[x*2],tree[x*2+1]);
}int check(ll mid)
{build(1,1,tot);ll sum=0,mxsum=0;for(int i=1;i<=n;i++){sum+=a[i];if(sum-mid>mxsum) continue;int pos=lower_bound(b+1,b+1+tot,sum-mid)-b;int dp=query(1,1,tot,pos,tot)+1;pos=lower_bound(b+1,b+1+tot,sum)-b;update(1,1,tot,pos,dp);mxsum=max(mxsum,sum);if(dp>=k)return 1;}return 0;
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&k);b[0] = 0;for(int i = 1;i <= n;i++){scanf("%lld",&a[i]);b[i] = b[i-1] + a[i];}sort(b+1,b+1+n);tot = unique(b+1,b+1+n) - (b+1);ll l = -inf,r = inf;while(l + 1 < r){ll mid = (l + r) / 2;if(check(mid)){r = mid;}else l = mid;}if(check(l)) printf("%lld\n",l);else printf("%lld\n",r);}return 0;
}

1006 Fansblog （数论定理 威尔逊定理）

http://acm.hdu.edu.cn/showproblem.php?pid=6608

题意

给你一个素数P 让你求Q!%Q   Q是小于P的最大素数

思路

威尔逊定理 ： 对于一个素数P （p-1）! ≡ -1(p)

可以求出（P-1）！ 除去(P-1)比Q多的

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
ll ksc(ll x,ll y,ll p){//计算x乘y的积ll res=0;//加法初始化while(y){if(y&1)res=(res+x)%p;//模仿二进制x=(x<<1)%p; y>>=1;//将x不断乘2达到二进制}return res;
}
ll qpow(ll x,ll n,ll mod)
{ll ans = 1;while(n){if(n % 2 == 1){ans = ksc(ans,x,mod) % mod;}x = ksc(x,x,mod) % mod;n /= 2;}return ans;
}int ok(ll x)
{int qw = sqrt(x);for(int i = 2; i <= qw;i++){if(x % i == 0) return 0;}return 1;
}
int main()
{int T;scanf("%d",&T);while(T--){ll p,q;scanf("%lld",&p);ll ans = p - 1;;for(ll i = p-1;i >= 1;i--){if(ok(i)){printf("%lld\n",ans);break;}ans = (ksc(ans,qpow(i,p-2,p),p))%p;}}return 0;
}

1007 Find the answer （权值线段树）

http://acm.hdu.edu.cn/showproblem.php?pid=6609

题意

给你n个数 问你1 - i(1<=i<=n) 去掉多少个数和小于等于m

思路

对于每个位置，求出需要减掉的数 然后在权值线段树上进行二分找答案。

代码

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int MAX = 200005;struct node
{ll num,sum;
}tree[MAX*4];
int n,m,nn;
ll a[MAX],w[MAX];
ll ans;
void build(int rt,int l,int r)
{tree[rt].num = tree[rt].sum = 0;if(l==r) return ;int mid = (l + r) / 2;build(rt*2,l,mid);build(rt*2+1,mid+1,r);
}
void updata(int rt,int l,int r,int x)
{if(l == r&&l == x){tree[rt].num++;tree[rt].sum += a[x];return ;}int mid = (l + r) / 2;if(mid >= x) updata(rt*2,l,mid,x);else updata(rt*2+1,mid+1,r,x);tree[rt].num = tree[rt*2].num + tree[rt*2+1].num;tree[rt].sum = tree[rt*2].sum + tree[rt*2+1].sum;
}
void query(int rt,int l,int r,ll need)
{if(l == r){   ans += need / a[l];if(need%a[l]) ans++;return ;}int mid = (l+r)/2;if(tree[rt*2+1].sum >= need){query(rt*2+1,mid+1,r,need);}else{ans += tree[rt*2+1].num;query(rt*2,l,mid,need-tree[rt*2+1].sum);}}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&nn,&m);for(int i = 1;i <= nn;i++){scanf("%lld",&a[i]);w[i] = a[i];}sort(a+1,a+1+nn);n = unique(a+1,a+1+nn) - (a+1);build(1,1,n);ll sum = 0;for(int i = 1;i <= nn;i++){sum += w[i];if(sum <= m){printf("0 ");int x = lower_bound(a+1,a+1+n,w[i]) - (a);updata(1,1,n,x);}else{ll need = sum - m;ans = 0;query(1,1,n,need);printf("%lld ",ans);int x = lower_bound(a+1,a+1+n,w[i]) - (a);updata(1,1,n,x);}}printf("\n");}return 0;
}

 

这篇关于2019 杭电多校（第三场）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---