首页 > 其他分享 >AtCoder Beginner Contest 359 解题报告

AtCoder Beginner Contest 359 解题报告

时间：2024-06-22 21:42:26浏览次数：12  
标签：AtCoder Name Beginner Contest int cin back pair define

AtCoder Beginner Contest 359

吐槽：A-F 还算正常，G 题你 tm 给我放了个出过的板子（ABC340G）是几个意思啊？？？

A

Simulate.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second

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

	int n,ans=0;cin>>n;string s;
	while(n--)cin>>s,ans+=s[0]=='T';
	cout<<ans;

	return 0;
}

B

Simulate.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second

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

	int n,ans=0;VI f[101];
	cin>>n;
	for(int i=1,x;i<=n<<1;i++)cin>>x,f[x].PB(i);
	for(int i=1;i<=n;i++)ans+=f[i][1]-f[i][0]==2;
	cout<<ans;

	return 0;
}

C

如果横着能免费移一下就先移，然后上一步靠近一步，上到等高就直接横着就行了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second

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

	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	if(a<c&&!((a+b)&1))a++;
	if(a<c&&((c+d)&1))c--;
	if(a>c&&((a+b)&1))a--;
	if(a>c&&!((c+d)&1))c++;
	cout<<abs((d-b))+max(0ll,(abs(a-c)-abs(d-b)+1)>>1);

	return 0;
}

D

直接状压即可。\(\Theta(n2^k)\)，下列实现多一个 \(k\) 的复杂度，但是可以优化掉。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second

const int N=1005,MOD=998244353;
int n,k,dp[N][512];
string s;

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

	cin>>n>>k>>s;s="$"+s;
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<1<<k-1;j++)
		{
			if(s[i]!='B')
			{//A
				bool ok=0;
				if(i<k)ok=1;
				int nxt=j<<1;
				for(int l=0;l<k>>1;l++)
					if(((nxt>>l)&1)!=((nxt>>k-l-1)&1))
					{ok=1;break;}
				if(ok)(dp[i][nxt&((1<<k-1)-1)]+=dp[i-1][j])%=MOD;
			}
			if(s[i]!='A')
			{//B
				bool ok=0;
				if(i<k)ok=1;
				int nxt=(j<<1)|1;
				for(int l=0;l<k>>1;l++)
					if(((nxt>>l)&1)!=((nxt>>k-l-1)&1))
					{ok=1;break;}
				if(ok)(dp[i][nxt&((1<<k-1)-1)]+=dp[i-1][j])%=MOD;
			}
		}
	int ans=0;
	for(int i=0;i<1<<k-1;i++)(ans+=dp[n][i])%=MOD;
	cout<<ans;

	return 0;
}

E

手模一下就可以发现：\(i\) 的答案就是所有的（\(i\) 结尾的）后缀极大值乘上距离上一个极大值的距离的和。单调栈维护即可。\(\Theta(n)\)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second

const int N=200005;
int n;

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

	cin>>n;
	ll ans=1;
	vector<PII>f;
	f.PB(0,INT_MAX);
	for(int i=1,x;i<=n;i++)
	{
		cin>>x;
		int lst,lx;
		while(f.back().se<=x)
		{
			lst=f.back().fi,lx=f.back().se;
			f.PPB();
			ans-=1ll*(lst-f.back().fi)*lx;
		}
		ans+=1ll*x*(i-f.back().fi);
		f.PB(i,x);
		cout<<ans<<" ";
	}

	return 0;
}

F

能构成树的充要条件就是：

  • \(\forall1\le i\le n,d_i\ge1\)，且
  • \(\displaystyle\sum_{i=1}^nd_i=2n-2\)。

直接先把全部 \(d_i\) 赋上 \(1\) 的权值，后面用 pq 维护 \(n-2\) 次贪心即可。\(\Theta(n\log n)\)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second

const int N=200005;
int n,a[N],d[N];
ll ans;
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >q;

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

	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],ans+=a[i],d[i]=1,q.emplace(3ll*a[i],i);
	for(int i=1;i<=n-2;i++)
	{
		int id=q.top().se;
		ans+=q.top().fi;
		q.pop();
		d[id]++;
		q.emplace(a[id]*(d[id]*2ll+1),id);
	}
	cout<<ans;

	return 0;
}

G

虚树板子。

直接对于某种颜色建虚树，然后就变成了无色的点对距离和问题，这是简单的。\(\Theta(n\log n)\)。

虚树是拷的 ABC340G。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second

const int N=200005,L=18;
int n,c[N];
VI col[N],g[N];
int dfn[N],nfd[N],df,fa[N],dep[N],rmq[N][L];
void dfs(int x,int f)
{
	dfn[x]=++df,nfd[df]=x,fa[x]=f,dep[x]=dep[f]+1;
	for(int y:g[x])
		if(y!=f)dfs(y,x);
}
int RMQ(int l,int r)
{
	int g=31-__builtin_clz(r-l+1);
	return min(rmq[l][g],rmq[r-(1<<g)+1][g],[&](int x,int y){return dep[x]<dep[y];});
}
int lca(int x,int y)
{
	if(x==y)return x;
	return fa[RMQ(dfn[x]+1,dfn[y])];
}
ll solve(VI &p,int co)
{
	if(p.empty())return 0;
	vector<pair<int,bool>>v;
	vector<VI>vg;
	sort(ALL(p),[&](int x,int y){return dfn[x]<dfn[y];});
	v.PB(p[0],0);
	for(int i=1;i<p.size();i++)
	{
		v.PB(p[i],0);
		v.PB(lca(p[i-1],p[i]),0);
	}
	sort(ALL(v),[&](pair<int,bool> x,pair<int,bool> y){return dfn[x.fi]<dfn[y.fi];});
	v.erase(unique(ALL(v)),v.end());
	for(auto &i:v)if(c[i.fi]==co)i.se=1;
	map<int,int>id;
	for(int i=0;i<v.size();i++)id[v[i].fi]=i;
	vg.resize(v.size());
	for(int i=1;i<v.size();i++)
		vg[id[lca(v[i-1].fi,v[i].fi)]].PB(id[v[i].fi]);
	ll res=0;
	VI sz(v.size());
	auto dfs2=[&](auto dfs2,int x)->void
	{
		dbg(co,v[x].fi);
		sz[x]=v[x].se;
		for(int y:vg[x])
		{
			dfs2(dfs2,y),sz[x]+=sz[y];
			dbg(v[y].fi,sz[y],dep[v[y].fi],dep[v[x].fi]);
			res+=1ll*sz[y]*(p.size()-sz[y])*(dep[v[y].fi]-dep[v[x].fi]);
		}
	};
	dfs2(dfs2,0);
	dbg(co,res);
	return res;
}

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

	cin>>n;
	for(int i=1,u,v;i<n;i++)cin>>u>>v,g[u].PB(v),g[v].PB(u);
	for(int i=1;i<=n;i++)cin>>c[i],col[c[i]].PB(i);
	dfs(1,0);
	for(int i=n;i;i--)
	{
		rmq[i][0]=nfd[i];
		for(int j=1;i+(1<<j)-1<=n;j++)
			rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<j-1)][j-1],[&](int x,int y){return dep[x]<dep[y];});
	}
	ll ans=0;
	for(int i=1;i<=n;i++)ans+=solve(col[i],i);
	cout<<ans;

	return 0;
}

标签：AtCoder,Name,Beginner,Contest,int,cin,back,pair,define
From： https://www.cnblogs.com/No-play-Yes-splay/p/18262753/abc359-sol

相关文章

  • AtCoder ABC 358
    比赛链接A-WelcometoAtCoderLandAC_Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongsignedmain(){strings,t;cin>>s>>t;if(s=="AtCoder"&&t=="Land")co......
  • AtCoder Beginner Contest 357-F
    Problem同步于博客ProblemYouaregivensequencesoflength\(N\),\(A=(A_1,A_2,\ldots,A_N)\)and\(B=(B_1,B_2,\ldots,B_N)\).Youarealsogiven\(Q\)queriestoprocessinorder.Therearethreetypesofqueries:1lrx:Add\(x\)toeachof......
  • 2023 Jiangsu Collegiate Programming Contest, National Invitational of CCPC (Huna
    题目思路来源乱搞ac题解枚举gcd，gcd一定是x的因子，由于lcm+gcd=x，有lcm/gcd+1=x/gcd，还有lcm/gcd>=1枚举lcm/gcd=y，显然如果gcd>1，让gcd和lcm同除以gcd即可，所以可以认为gcd=1，问题转化为，大小为k的集合，k个不同的数，满足gcd=1，且lcm=y的方案数，然后写了个大暴力容斥，没想到过了…......
  • AtCoder Beginner Contest 358
    A-WelcometoAtCoderLandvoidsolve(){strings,t;cin>>s>>t;if(s=="AtCoder"&&t=="Land"){cout<<"Yes\n";return;}cout<<"No\n&qu......
  • [atcoder 358] 【动态规划】
    dp[i][j]表示前i个和为j的个数。那么就有递推式dp[i][j]+=dp[i][j-x]*c(j,j-x);其中x满足从0到c[i],并且x满足<=j组合数递推公式c(n,k)=c(n,k-1)+c(n,k);importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;impor......
  • ATcoder ABC 358 补题记录（A~D，G）
    A直接模拟即可。#pragmaGCCoptimize(3)#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1000100,mod=998244353;inta[N];signedmain(){strings,t;cin>>s>>t;if(s=="AtCoder"&&t==&qu......
  • square869120Contest #3 G Sum of Fibonacci Sequence
    洛谷传送门AtCoder传送门特判\(n=1\)。将\(n,m\)都减\(1\)，答案即为\[[x^m]\frac{1}{(1-x-x^2)(1-x)^n}\]若能把这个分式拆成\(\frac{A(x)}{(1-x)^n}+\frac{B(x)}{1-x-x^2}\)的形式，其中\(\degA(x)\len-1,\degB(x)\le1\)，那么答案就是好算的。......
  • atcoder 官方dp题单题解(持续更新)
    题单链接:https://atcoder.jp/contests/dp/tasks洛谷搜索:https://www.luogu.com.cn/problem/list?keyword=at_dp&type=AT|B|CF|P|SP|UVA&page=1A题目链接:https://atcoder.jp/contests/dp/tasks/dp_a简单线性dp.dp[i]表示在i这个位置的最小代价,转移的时候把两种选择都考虑......
  • 由AtCoder_ABC357D引发的除法同余学习
    鉴于最近的Atcoder周赛又出现除法求余，下定决心学习逆元相关内容同余概述定义同余定义：若a和b是整数，且m|(a-b),则称a和b模m同余。即两者除以m得到的余数相同。剩余系：一个模m完全剩余系是一个整数集合，任何一个整数恰好与该集合中的一个元素模m同余。例如0,1,...,m-1的集......
  • Atcoder357D题解(求解等比数列求和公式的推导)
    解题思路设连接之后的N等于Nlast，w=10^(N在10进制下的长度,例如N=5,那么w=10)Nlast=N+N*w+N*(w^2)+N*(w^3)+.....+N*(w^n)举个例子N=5，因为510进制的长度是1，所以w=10，那么Nlast=5+5*10(w)^1+5*10(w)^2+5*10(w)^3+......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99