ABC-259

本文主要是介绍ABC-259，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

D - Circumferences(简单计算几何)

Problem

二维平面上给定两个点\(s,t\)和若干个圆，问是否可以从\(s\)只经过圆边到达\(t\)

\(1\le N\le 3000\)

Solve

把每个圆之间的相交或相切关系转换成两个圆可达，于是就变成了一个图论问题，给定起点和终点，问是否可以从起点到终点，一次\(bfs\)就可以实现。

但其实判断连通性也可以用并查集，这样更快。

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3005;
struct Point{
	int x,y;
};
struct Circle{
	Point c;
	int r;
}cir[N];
bool vis[N][N],st[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    Point s,t;
    cin>>s.x>>s.y>>t.x>>t.y;
    for(int i=1;i<=n;i++){
    	cin>>cir[i].c.x>>cir[i].c.y>>cir[i].r;
    }
    int ss=0,tt=0;
    auto get_dist=[&](Point a,Point b)->ll{
    	return 1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
    };
    for(int i=1;i<=n;i++){
    	if(get_dist(s,cir[i].c)==1LL*cir[i].r*cir[i].r){
    		ss=i;
    	}
    	if(get_dist(t,cir[i].c)==1LL*cir[i].r*cir[i].r){
    		tt=i;
    	}
    }
    for(int i=1;i<=n;i++)
    	for(int j=i+1;j<=n;j++){
    		ll d=get_dist(cir[i].c,cir[j].c);
    		ll L=1LL*(cir[i].r-cir[j].r)*(cir[i].r-cir[j].r);
    		ll R=1LL*(cir[i].r+cir[j].r)*(cir[i].r+cir[j].r);
            if(L<=d&&d<=R){
            	vis[i][j]=vis[j][i]=1;
                //f[find(i)]=find(j); 并查集
            }
    	}

    if(!ss||!tt) cout<<"No\n";
    else{
        /*
        if(find(ss)!=find(tt)) cout<<"No\n";
        else cout<<"Yes\n";s
        */
        queue<int>q;
        q.push(ss);
        while(q.size()){
        	int u=q.front();
        	q.pop();
        	if(st[u]) continue;
        	st[u]=1;
        	if(u==tt){
        		cout<<"Yes\n";
        		return 0;
        	}
        	for(int v=1;v<=n;v++){
        		if(vis[u][v]&&!st[v]){
        			q.push(v);
        		}
        	}
        }
        cout<<"No\n";
    }
    return 0;
}

E - LCM on Whiteboard(简单数论、STL 去重)

Problem

给定\(n\)个数，每个数按照质因子分解的形式给出，对于\(1\le i\le n\)，若把第\(i\)个数变成\(1\)，可以得到一个这些数的最小公倍数。问可以得到多少个不同的最小公倍数

Solve

显然一开始的最小公倍数就是每个质因子最大幂次的乘积，现在只需要考虑把一个数变成\(1\)后是否对质因子的最大幂次产生影响即可。

感觉不好想到的就是用 STL 去重了，其实只要满足偏序关系的都是可以去重的，一开始数论部分很好考虑，考虑去重的情况考虑了很久。

Code

#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
    vector<vector<pair<int,int>>>fac(n+1);
    map<int,vector<int>>v;
    for(int i=1;i<=n;i++){
    	int m;
    	cin>>m;
    	for(int j=1;j<=m;j++){
    		int p,x;
    		cin>>p>>x;
    		fac[i].emplace_back(p,x);
    		v[p].emplace_back(x);
    	}
    }
    for(auto &[p,q]:v) sort(q.begin(), q.end());
    vector<vector<pair<int,int>>>ans;

    for(int i=1;i<=n;i++){
    	vector<pair<int,int>>t;//这里存储的是需要除的因子的幂次，不直接求
    	for(auto [p,x]:fac[i]){
           //如果i这个因p的幂次等于最大的幂次，说明变为1就会改变,
    		if(x==v[p].back()){
    			//看次大的是否还是最大幂次，如果是，则没有影响，否则就要除以最大幂次并乘上次大幂次
    			int d=(v[p].size()==1)?0:v[p][int(v[p].size())-2];

                if(d!=x) t.emplace_back(p,d-x);
    		}
    	}
    	sort(t.begin(), t.end());
    	ans.push_back(t);
    }
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()),ans.end());
    cout<<ans.size()<<'\n';
}

F - Select Edges(树形 DP、带悔)

problem

给定一个\(N\)个点的树，每条树边有一个边权，现在要求每个点\(i\)的度数小于等于\(d_i\)，问保留哪些边可以使得保留下的边的边权和最大。

Solve

考虑树形\(dp\)：\(dp[u][0]\)表示不选择连向父亲的边，\(dp[u][1]\)表示选择连向父亲的边

一开始我们先记录\(u\)的儿子\(v\)都不选父边的贡献和\(s\)。然后我们记录每一个\(dp[v][1]+w-dp[v][0]\)，这一步是让我们有反悔的余地，这一步其实很好想到。

把所有\(dp[v][1]+w-dp[v][0]\)按照从大到小排序，然后开始转移：

令\(dp[u][0]=dp[u][1]=s\)，其实\(\sum_{v\in Son_u}dp[v][0]\)，然后我们开始反悔操作，加入一个\(dp[v][1]+w-dp[v][0]\)相当于撤销之前不选的操作从而选上这条边

对于\(dp[u][0]\)，把前\(d[u]\)大的累计进入答案，如果遇到小于\(0\)的，当做\(0\)加入答案。

对于\(dp[u][1]\)，把前\(d[u]-1\)大的累计进入答案，如果遇到小于\(0\)的，当做\(0\)加入答案。

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	vector<int>d(n+1);
	for(int i=1;i<=n;i++) cin>>d[i];
	vector<vector<pair<int,int>>>e(n+1);
	for(int i=1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		e[u].emplace_back(v,w);
		e[v].emplace_back(u,w);
	}
	vector<vector<ll>>dp(n+1,vector<ll>(2));
	//dp[u][0]:不选连向父亲的边
	//dp[u][1]:选连向父亲的边
	const int inf=1e9;
	auto dfs=[&](auto self,int u,int fa)->void{
         ll s=0;
         vector<ll>ww;
         for(auto [v,w]:e[u]){
         	if(v==fa) continue;
            self(self,v,u);
            s+=dp[v][0];
            //类似于带悔贪心的思想，假设u的连向儿子的边都没有选，通过这种差值替换每一条边的选择方案。
            //这里取好和0取max,是因为如果是负数，可能不会选，而题目要求的是选的边数小于等于d[u]
            ww.push_back(max(dp[v][1]+w-dp[v][0],0LL));
         }
         sort(ww.begin(), ww.end());;
         reverse(ww.begin(), ww.end());
         dp[u][0]=s;
         //在所有连向儿子的边中选择最大的d[u]条替换，由于选择的是d[u]条，所以向dp[u][0]转移
         for(int i=0;i<min(int(ww.size()),d[u]);i++) dp[u][0]+=ww[i];
         if(d[u]==0) dp[u][1]=-inf;
         else{
         	dp[u][1]=s;
         	//选择d[u]-1条，向dp[u][1]转移，代表要选连向u父亲的边
         	for(int i=0;i<min(int(ww.size()),d[u]-1);i++) dp[u][1]+=ww[i];
         }
	};
	dfs(dfs,1,1);
	cout<<dp[1][0]<<'\n';
}

G - Grid Card Game(最小割、网格模型)

Problem

给定一个\(n\times m\)的网格，每个格子上有一个数字\(a_{i,j}\)，现在可以选择若干列和若干行，贡献就是这些列和行中的元素的并集的和。但如果某一行和某一列的交点的数字是负数，那么贡献就要减去\(10^{100}\)，问可以得到的最大贡献是多少。

Solve

网格模型，把行和列分别当做点

显然，如果某一行和某一列的和小于\(0\)一定不会选

假设目前选择了一行\(i\)和一列\(j\)，由于我们已经分别统计过他们的和的贡献，因此还需要减去他们交点的数字，不然会重复计数

于是可以构建这样一个网络流模型：

源点\(S\)向每个和大于\(0\)的行连边
每个和大于\(0\)的列向汇点\(T\)连边
对于一行\(i\)和一列\(j\)，如果\(a_{i,j}\lt 0\)，那么\(i\)向\(j\)连边权为\(\infty\)的边，否则连边权为\(a_{i,j}\)的边权。
最后就是所有非负数行列和之和-最小割

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=205,M=N+N*N;
const ll INF=1LL<<60;
int n,m,S,T,cnt;
int head[N],d[N],cur[N];
struct edges
{
	int v,nxt;
	ll f;
}e[M*2];
void add(int u,int v,ll f)
{
	e[cnt].v=v,e[cnt].nxt=head[u],e[cnt].f=f,head[u]=cnt++;
	e[cnt].v=u,e[cnt].nxt=head[v],e[cnt].f=0,head[v]=cnt++;
}

bool bfs()
{
	memset(d,-1,sizeof d);
	queue<int>q;
	q.push(S);
	d[S]=0,cur[S]=head[S];
	while(q.size())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];~i;i=e[i].nxt)
		{
			int v=e[i].v;
			ll f=e[i].f;
			if(d[v]==-1&&f)
			{
				d[v]=d[u]+1;
				cur[v]=head[v];
				if(v==T) return true;
				q.push(v);
			}
		}
	}
	return false;
}
ll find(int u,ll limit)
{
	if(u==T) return limit;
	ll flow=0;
	for(int i=cur[u];~i&&flow<limit;i=e[i].nxt)
	{
		cur[u]=i;
		int v=e[i].v;
		ll f=e[i].f;
		if(d[v]==d[u]+1&&f)
		{
			ll t=find(v,min(f,limit-flow));
			if(!t) d[v]=-1;
			e[i].f-=t,e[i^1].f+=t,flow+=t;
		}
	}
	return flow;
}
ll dinic()
{
	ll ans=0,flow;
	while(bfs()) while(flow=find(S,INF)) ans+=flow;
	return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    memset(head,-1,sizeof head);
    cin>>n>>m;
    S=0,T=n+m+1;
    vector<vector<ll>>a(n+1,vector<ll>(m+1));
    vector<ll>x(n+1),y(m+1);
    ll sum=0;
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++){
              cin>>a[i][j];
              x[i]+=a[i][j];
              y[j]+=a[i][j];
              if(a[i][j]<0) add(i,n+j,INF);
              else add(i,n+j,a[i][j]);
    	}
    for(int i=1;i<=n;i++) if(x[i]>0)add(S,i,x[i]),sum+=x[i];
    for(int i=1;i<=m;i++) if(y[i]>0)add(n+i,T,y[i]),sum+=y[i];
    ll flow=dinic();
    cout<<sum-flow<<'\n';
	return 0;
}

Ex - Yet Another Path Counting(根号分治的思想)

Problem

给定一个\(n\times n\)的网格，每个网格上有一个数字\(1\le a_{i,j}\le n^2\)。每次在网格上可以向下或向右走，问起点和终点数字相同的路径数量

\(1\le N\le 400\)

Solve

暴力做法 1：

枚举每个数字，枚举它的所有出现过的网格，然后把这些网格两两组合，每次计算用组合数直接计算\(O(1)\)的复杂度。但如果全部格子都是一样的数字，那么\(n^2\)个格子两两组合就是\(n^4\)，时间复杂度显然不行。

暴力做法 2：
用\(dp\)的做法，每次枚举一种颜色，然后用\(dp\)做法\(O(n^2)\)求出，但如果有\(n^2\)种颜色，那么时间复杂度就是\(O(n^4)\)的，所以也不行。

考虑在这两种做法中做一个平衡，类似于根号分治的思想\(O(\sqrt{n^2}n^2)=O(n^3)\)

枚举每一个数字，如果这个数字的个数小于等于\(n\)，那么就用暴力做法 1，否则用暴力做法 2.

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=998244353;
int power(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=1LL*res*x%mod;
		x=1LL*x*x%mod;
		y>>=1;
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	vector<int>fac(2*n+1),infac(2*n+1);
	fac[0]=1;
	for(int i=1;i<=2*n;i++) fac[i]=1LL*fac[i-1]*i%mod;
	infac[2*n]=power(fac[2*n],mod-2);
    for(int i=2*n;i>=1;i--) infac[i-1]=1LL*infac[i]*i%mod;

    vector<vector<int>>a(n+1,vector<int>(n+1));
    vector<vector<pair<int,int>>>c(n*n+1);
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=n;j++){
            cin>>a[i][j];
            c[a[i][j]].emplace_back(i,j);
    	}
    auto binom=[&](int n,int m)->int{
    	if(n<m||m<0) return 0;
    	return 1LL*fac[n]*infac[m]%mod*infac[n-m]%mod;
    };
    ll ans=0;
    for(int k=1;k<=n*n;k++){
    	if(c[k].size()<=n){
    		for(int i=0;i<c[k].size();i++)
    			for(int j=i;j<c[k].size();j++){
    				auto p=c[k][i],q=c[k][j];
    				if(p.second>q.second) continue;
    				int x=q.first-p.first+q.second-p.second;
    			    int y=q.first-p.first;
    				ans=(ans+binom(x,y))%mod;
    			}
    	}else{
    		vector<vector<int>>dp(n+1,vector<int>(n+1));
    		for(int i=1;i<=n;i++)
    			for(int j=1;j<=n;j++){
    				if(a[i][j]==k) dp[i][j]=1;
    				dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
    				dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
    				if(a[i][j]==k) ans=(ans+dp[i][j])%mod;
    			}
    	}
    }
    if(ans<0) ans=(ans+mod)%mod;
    cout<<ans<<'\n';
}

这篇关于ABC-259的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程

ABC-259

D - Circumferences(简单计算几何)

Problem

Solve

Code

E - LCM on Whiteboard(简单数论、STL 去重)

Problem

Solve

Code

F - Select Edges(树形 DP、带悔)

problem

Solve

Code

G - Grid Card Game(最小割、网格模型)

Problem

Solve

Code

Ex - Yet Another Path Counting(根号分治的思想)

Problem

Solve

Code

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯