atcoder abc 188 题解

技术文章 11个月前 完美者
1,128 0

标签:begin   扫描   tor   lse   signed   empty   second   lang   其他   

A - Three-Point Shot

题目大意

两个球队现在分数分别给出,问少的一方投入三分球之后是否能翻盘.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	


int main()
{
	int a,b;cin >> a >> b;
	if(a > b)	swap(a,b);
	if(a + 3 > b)	cout << "Yes";
	else cout << "No";
    return 0;
}

B - Orthogonality

题目大意

给定两个向量,问两者内积是否是0.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	

const int N = 1e5+7;
int a[N],b[N];
int main()
{
	ll res = 0;
	int n,x,y;scanf("%d",&n);
	forn(i,1,n)	scanf("%d",&a[i]);
	forn(i,1,n)	scanf("%d",&b[i]);
	
	forn(i,1,n)	res += a[i] * b[i];
	if(res == 0)	puts("Yes");
	else	puts("No");
    return 0;
}

C - ABC Tournament

题目大意

\(2^n\)个队伍打比赛,每个队伍有自己的分值,分值高的获胜.对局呈完美二叉树形态,从低到高,问第二名是谁.

思路

把整个局面划分两段再递归,当区间里只有一个人的时候返回自己,其他时候返回两个人对战胜利者.记录最后一个对局中输掉的人的编号,即为第二名.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	

const int N = (1 << 16) + 7;
int a[N],last;

int solve(int l,int r)
{
	if(l == r)	return l;
	int mid = l + r >> 1;
	int lf = solve(l,mid),rt = solve(mid + 1,r);
	if(a[lf] > a[rt])	return last = rt,lf;
	else	return last = lf,rt;
}

int main()
{
	int n;scanf("%d",&n);
	int m = 1 << n;
	forn(i,1,m)	scanf("%d",&a[i]);
	solve(1,m);
	printf("%d",last);
    return 0;
}

D - Snuke Prime

题目大意:

有个公司售卖他们的\(n\)种服务,售卖方式有两种:每天花费\(C\)元订阅费,在订阅期间任何服务可以直接使用;对\(i\)种服务花费\(c_i\)元每天使用.现给出若干个\(a_i,b_i,c_i\)表示在第\(a_i\)天到第\(b_i\)天需要使用第\(i\)种服务,以及使用这项服务的每天花费\(c_i\)

数据范围:

\(1 \leq n \leq 2 * 10^5\)

\(1 \leq C \leq 10^9\)

\(1 \leq a_i \leq b_i \leq 10^9\)

\(1 \leq c_i \leq 10^9\)

思路

由于数据范围过大,但是种类数只有\(2*10^5\)考虑离散化打标记.但是离散化只保留相对大小关系,使得"天数"这一信息被删掉,因此离散化处理不了.

考虑扫描线,以天数为扫描线的划分.将所有服务分成两个事件:一个事件包含两个变量\({a,c}\)表示在第\(a\)天,增加一个每天花费为\(c\)的服务.对于原来的每种服务拆成\(\{a_i,c_i\}\)以及\(\{b_i+1,c_i\}\)两个事件,表示第\(a_i\)天开始增加,直到\(b_i+1\)天结束.维护当前天数\(cur\)以及当前需要使用的各种服务的总花费\(sum\),因为可以通过订阅的方式使用所有服务,所以每段的实际贡献是\((a - cur) * min(sum,C)\).

将所有事件按左端点排序,扫描即可.

注意防范爆数据

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	
typedef pair<ll,ll> pll;
#define x first
#define y second
#define int ll
const int N = 2e5+7;
struct Node
{
	int a,b,c;
}a[N];

signed main()
{
	int n,C;scanf("%lld%lld",&n,&C);
	vector<pll> event;
	forn(i,1,n)	scanf("%lld%lld%lld",&a[i].a,&a[i].b,&a[i].c);
	forn(i,1,n)	event.push_back({a[i].a,a[i].c}),event.push_back({a[i].b + 1,-a[i].c});	
	
	sort(event.begin(),event.end());
	
	int cur = 0;ll res = 0,sum = 0;
	for(auto& _ : event)
	{
		int a = _.x,c = _.y;
		res += 1ll*(a - cur) * min(max(sum,0ll),1ll*C);
		sum += c;
		cur = a;
	}
	
	printf("%lld",res);
    return 0;
}

E - Peddler

题目大意

\(n\)\(m\)边有向图,保证对于任何一条有向边\((u,v)\)都有\(u < v\),即只会从编号较小的点连向较大的点.每个点都有一个值\(A_i\)表示在这个点买入黄金的价格和卖出黄金的价格.你不能在同一个点买入并卖出,求最大的获利是多少.

你不能不买入,即使有负利润也必须买.

图可能不连通

思路

很恼火的一个题.

首先这个题有一个一般的解法,可以使用取极值的方式替代单源最短路的更新,这里不展开.

因为对于任何边都有\(u < v\)所以这个图是个DAG.直接\(dp\)即可.

  • 状态:\(f_u\)表示从起点走到\(u\)时,找到的最小的价格是多少.

  • 入口:\(f_u = a_u\)

  • 转移:对于\(u\)的任何一条出边对应的点\(v\),\(f_v = min(f_u,f_v)\)

更新答案\(res = max(res,a_u - f_u)\)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)

const int N = 2e5+7,M = N;
int edge[M],succ[M],ver[N],idx;
int w[N],deg[N];
ll f[N];
void add(int u,int v)
{
	edge[idx] = v;
	succ[idx] = ver[u];
	ver[u] = idx++;
}
		
int main()
{
	memset(ver,-1,sizeof ver);
	int n,m;scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++i)	scanf("%d",&w[i]);
	for(int i = 1;i <= m;++i)
	{
		int u,v;scanf("%d%d",&u,&v);
		add(u,v);++deg[v];
	}
	queue<int> q;forn(i,1,n) if(!deg[i])	q.push(i);
	forn(i,1,n)	f[i] = 1e18;
	ll res = -1e18;
	while(!q.empty())
	{
		int u = q.front();q.pop();
		res = max(res,w[u] - f[u]);
		f[u] = min(f[u],1ll*w[u]);
		for(int i = ver[u];~i;i = succ[i])
		{
			int v = edge[i];
			f[v] = min(f[v],f[u]);
			if(--deg[v] == 0)	q.push(v);
		}
	}
	printf("%lld",res);
    return 0;
}

F - +1-1x2

题目大意

给你一个数\(x\),每次可以加一减一或乘二,问使\(x\)变成\(y\)的最小步数.

数据范围:

\(1 \leq x,y \leq 10^{18}\)

思路

弱智题,显然.

不过注意分情况讨论奇数的时候,既有减一的拉回来的也有加一补上去的情况.

复杂度不知道,直觉是\(log\)的,可以冲的原因是直接的距离可以计算,其次乘2除2的速度非常快.

代码

ll x,y;
map<ll,ll> f;

ll solve(ll y)
{
	if(f.count(y))	return f[y];
	ll res = y - x;
	if(y <= x)	return x - y;
	
	if(y % 2 == 0)	res = min(res,solve(y / 2) + 1);
	else			res = min({res,solve(y / 2) + 2,solve((y / 2 + 1)) + 2});
	
	return f[y] = res;
}
int main()
{
	cin >> x >> y;
	cout << solve(y);
    return 0;
}

atcoder abc 188 题解

标签:begin   扫描   tor   lse   signed   empty   second   lang   其他   

原文地址:https://www.cnblogs.com/HotPants/p/14260875.html

版权声明:完美者 发表于 2021-01-13 10:46:21。
转载请注明:atcoder abc 188 题解 | 完美导航

暂无评论

暂无评论...