首页 > 其他分享 >Atcoder Beginner Contest 369

Atcoder Beginner Contest 369

时间:2024-08-31 21:36:28浏览次数:13  
标签:Atcoder Beginner int tr cin mx while 369 id

Atcoder Beginner Contest 369

唯一的一发罚时吃在 A 题,消息了。

A

挂一发的原因是以为 \(A,B\) 都是一位数,然后循环范围开了 \([-10,20]\)。

#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
//	int _;cin>>_;while(_--)

	int x,y,a[4],ans=0;
	cin>>x>>y;
	for(int i=-100;i<=200;i++)
	{
		a[1]=x,a[2]=y,a[3]=i;
		sort(a+1,a+4);
		ans+=a[3]-a[2]==a[2]-a[1];
	}
	cout<<ans;

	return 0;
}

B

Simulate

#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
//	int _;cin>>_;while(_--)

	int n,l=-1,r=-1;
	cin>>n;
	int ans=0;
	while(n--)
	{
		int p;char c;
		cin>>p>>c;
		if(c=='L')
		{
			if(~l)ans+=abs(l-p);
			l=p;
		}
		else
		{
			if(~r)ans+=abs(r-p);
			r=p;
		}
	}
	cout<<ans;

	return 0;
}

C

直接差分然后变成全相等的段数。这是简单的。\(\Theta(n)\)。

#include<bits/stdc++.h>
using namespace std;

const int N=200005;
int n,a[N];

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
//	int _;cin>>_;while(_--)

	cin>>n;
	ll ans=0;
	for(int i=1,lst=1;i<=n;i++)
	{
		cin>>a[i];
		if(lst<i-1&&a[i]-a[i-1]!=a[i-1]-a[i-2])lst=i-1;
		ans+=i-lst+1;
	}
	cout<<ans;

	return 0;
}

D

直接令 \(dp_{i,0/1}\) 表示前 \(i\) 个怪兽,打了偶数/奇数个的最大得分,维护个前缀 \(\max\) 即可。\(\Theta(n)\)。

#include<bits/stdc++.h>
using namespace std;

const int N=200005;
ll dp[N][2],mx[N][2];
int n;

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
//	int _;cin>>_;while(_--)

	cin>>n;
	mx[0][1]=LLONG_MIN;
	for(int i=1,x;i<=n;i++)
	{
		cin>>x;
		dp[i][0]=mx[i-1][1]+(x<<1);
		dp[i][1]=mx[i-1][0]+x;
		mx[i][0]=max(mx[i-1][0],dp[i][0]);
		mx[i][1]=max(mx[i-1][1],dp[i][1]);
	}
	cout<<max(mx[n][0],mx[n][1]);

	return 0;
}

E

你先钦定那 \(k\) 条边经过的顺序和方向,那么中间的过程就是从一个终点到另一个起点的最短路,直接预先 Floyd 出来即可。\(\Theta(n^3+m+qk!2^kk)\)。

#include<bits/stdc++.h>
using namespace std;

const int N=405,M=200005;
int n,m,q,u[M],v[M],w[M];
ll dis[N][N];

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
//	int _;cin>>_;while(_--)

	cin>>n>>m;
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=m;i++)
	{
		cin>>u[i]>>v[i]>>w[i];
		dis[u[i]][v[i]]=dis[v[i]][u[i]]=min(dis[u[i]][v[i]],(ll)w[i]);
	}
	for(int i=1;i<=n;i++)dis[i][i]=0;
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	cin>>q;
	while(q--)
	{
		int k,id[6];
		cin>>k;
		for(int i=1;i<=k;i++)cin>>id[i];
		sort(id+1,id+k+1);
		ll ans=LLONG_MAX;
		do
		{
			for(int j=0;j<1<<k;j++)
			{
				ll cur=0;
				for(int i=1;i<=k;i++)cur+=w[id[i]];
				for(int i=1;i<=k+1;i++)cur+=dis[i==1?1:(j>>i-2)&1?v[id[i-1]]:u[id[i-1]]][i>k?n:(j>>i-1)&1?u[id[i]]:v[id[i]]];
				ans=min(ans,cur);
			}
		}while(next_permutation(id+1,id+k+1));
		cout<<ans<<endl;
	}

	return 0;
}

F

考虑 dp,令 \(dp_i\) 表示走到第 \(i\) 枚金币的最大拿到的金币数量。那么转移就是

\[dp_i=\max_{\substack{x_i\ge x_j\\y_i\ge y_j}}\{dp_j\}+1 \]

直接按 \(x\) 排序,那么就是 \(y\) 坐标上的单点取 \(\max\) /前缀求 \(\max\),直接树状数组。构造不难。\(\Theta(n\log W)\)。

#include<bits/stdc++.h>
using namespace std;

const int N=200005;
int H,W,n;
PII p[N],dp[N];
PII f[N];
void put(int p,PII v){while(p<=W)f[p]=max(f[p],v),p+=p&-p;}
PII get(int p){PII res={-1,0};while(p)res=max(res,f[p]),p^=p&-p;return res;}

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
//	int _;cin>>_;while(_--)

	cin>>H>>W>>n;
	for(int i=1;i<=n;i++)cin>>p[i].fi>>p[i].se;
	p[0]={1,1},p[n+1]={H,W};
	sort(p+1,p+n+1);
	fill(f+1,f+n+1,MP(INT_MIN,0));
	put(1,dp[0]);
	for(int i=1;i<=n+1;i++)
	{
		dp[i]=get(p[i].se);
		put(p[i].se,{++dp[i].fi,i});
	}
	string ans;
	cout<<dp[n+1].fi-1<<endl;
	for(int i=n+1;i;i=dp[i].se)
	{
		for(int j=1;j<=p[i].fi-p[dp[i].se].fi;j++)ans+='D';
		for(int j=1;j<=p[i].se-p[dp[i].se].se;j++)ans+='R';
	}
	reverse(ALL(ans));
	cout<<ans;

	return 0;
}

G

不难发现当钦定点集时答案是虚树边权和的两倍。

直接费用流思想可以得到一个贪心:每次取一个离根最远的点,把答案加上其到根的距离,然后把它到根的路径上的边权全部置 \(0\)。

直接 dfn 序拍平维护点到根距离,那么置 \(0\) 就相当于区间减,查询是全局 \(\max\),直接线段树,\(\Theta(n\log n)\)。

#include<bits/stdc++.h>
using namespace std;

const int N=200005;
int n;
vector<PII>g[N];
struct node
{
	ll add,mx;
	int xid;
}tr[1<<19];
#define lid (id<<1)
#define rid (lid|1)
#define mid (l+r>>1)
#define rmd (mid+1)
void build(int l=1,int r=n,int id=1)
{
	tr[id].add=tr[id].mx=0,tr[id].xid=r;
	if(l==r)return;
	build(l,mid,lid),build(rmd,r,rid);
}
void pushdown(int id)
{
	ll &ad=tr[id].add;
	tr[lid].add+=ad,tr[rid].add+=ad,tr[lid].mx+=ad,tr[rid].mx+=ad;
	ad=0;
}
void add(int L,int R,int v,int l=1,int r=n,int id=1)
{
	if(L==l&&R==r)return tr[id].mx+=v,void(tr[id].add+=v);
	pushdown(id);
	if(L<=mid)add(L,min(R,mid),v,l,mid,lid);
	if(R>=rmd)add(max(L,rmd),R,v,rmd,r,rid);
	tie(tr[id].mx,tr[id].xid)=max(MP(tr[lid].mx,tr[lid].xid),MP(tr[rid].mx,tr[rid].xid));
}
int dfn[N],rdn[N],ed[N],df,f[N],fw[N];
void dfs(int x,int fa,int wg)
{
	dfn[x]=++df,rdn[df]=x,f[x]=fa,fw[x]=wg;
	for(auto y:g[x])
		if(y.fi!=fa)dfs(y.fi,x,y.se);
	ed[x]=df;
	add(dfn[x],ed[x],wg);
}
bool vis[N];

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
//	int _;cin>>_;while(_--)

	cin>>n;
	for(int i=1,u,v,w;i<n;i++)
		cin>>u>>v>>w,g[u].PB(v,w),g[v].PB(u,w);
	build();
	dfs(1,0,0);
	ll ans=0;
	vis[1]=1;
	for(int i=1;i<=n;i++)
	{
		cout<<((ans+=tr[1].mx)<<1)<<endl;
		for(int j=rdn[tr[1].xid];!vis[j];j=f[j])
			vis[j]=1,add(dfn[j],ed[j],-fw[j]);
	}

	return 0;
}

标签:Atcoder,Beginner,int,tr,cin,mx,while,369,id
From: https://www.cnblogs.com/No-play-Yes-splay/p/18390802/abc369-sol

相关文章

  • AtCoder Beginner Contest 053
    A-ABC/ARC#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); intx; cin>>x; if(x<1200)cout<<"ABC"; elsecout<<"ARC&q......
  • luoguP5369 [PKUSC2018] 最大前缀和
    题目n<=20题解想了半天3位状态的折半,然后发现空间开不下(时间也不太行)所以放弃思考,直接枚举答案答案是a中的一个集合,设为S;记集合S的和为sum[S]考虑当S确定时,有多少种方案能使答案恰好为sum[S]。为了处理多种sum相同的情况,记S为从前往后考虑,第一次出现最大ans的集合;记剩余部......
  • Versal Prime 系列 VM2202 自适应 SoC平台,XCVM2202-1LSINSVH1369、XCVM2202-1MLINSVH1
    VersalPrime系列是一款高度集成、多核、异构计算平台,适用于数据中心网络、存储和有线通信等多种应用。它通过在优化了连接性的设备中实现低延迟的内联加速,为这些应用提供突破性的性能。VersalPrime系列VM2202自适应SoC相关型号:XCVM2202-1LSINSVH1369XCVM2202-2LSENSVH13......
  • Hitachi Vantara Programming Contest 2024(AtCoder Beginner Contest 368)F - Dividing
    https://atcoder.jp/contests/abc368/tasks/abc368_f#include<bits/stdc++.h>#definexfirst#defineysecondusingnamespacestd;typedeflonglongll;typedefpair<ll,char>pii;constintN=2e5+10,inf=1e9;lln,m,k;intb[N],sg[N],a[N];vector......
  • Atcoder [AGC006D] Median Pyramid Hard 题解 [ 紫 ] [ 二分 ] [ adhoc ]
    MedianPyramidHard:二分trick加上性质观察题。trick我们可以二分值域,然后把大于等于它的数标记成\(1\),其他标记为\(0\)(有些题需要标记成\(-1\)),然后根据这个来check方案是否可行,这通常通过判断某个数是否是\(1\)来实现。本质上其实就是check大于等于它的数能否成为......
  • AtCoder Beginner Contest 368
    A-Cut题意签到题思路代码#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,k;scanf("%d%d",&n,&k);vector<int>v(n);for(inti=0;i<n;i++){scanf("%d",&v[i......
  • AtCoder Beginner Contest 052
    A-TwoRectangles#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); intA,B,C,D; cin>>A>>B>>C>>D; cout<<max(A*B,C*D); ......
  • AtCoder Beginner Contest 051
    A-Haiku直接模拟。#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); strings; cin>>s; stringa,b,c; a=s.substr(0,5); b=s.substr(6,7); c=s.substr(......
  • Hitachi Vantara Programming Contest 2024(AtCoder Beginner Contest 368)题解A~D
    A-Cut题意:将数组的后k个字符移到前面思路:可以用rotate()函数让数组中的元素滚动旋转rotate(v.begin(),v.begin()+n-k,v.end());直接输出后k个元素,再输出前n-k个元素for(inti=n-k;i<n;i++)write(v[i]);for(inti=0;i<n-k;i++)write(v[i]);B-Decrease2......
  • AtCoder ABC 368题解
    前言本题解部分思路来自于网络。A-Cut题目大意有\(n\)张卡片叠在一起,从上到下给出\(n\)卡片的编号,将\(k\)张卡片从牌堆底部放到顶部后,从上到下输出卡片的编号。解题思路按照题意模拟即可。code#include<bits/stdc++.h>usingnamespacestd;inta[105];intmai......