A

题意

问\(x,y\)相差是否小于\(3\)

#include<iostream>

#include<cstdio>

#include<cmath>

#define ll long long

ll x,y;

int main(){

	scanf("%lld%lld",&x,&y);

	if(abs(y - x) < 3)

	puts("Yes");

	else

	puts("No");

}

B

题意

问两个向量的内积是否为\(0\)

照着题目模拟就行

#include<iostream>

#include<cstdio>

#define ll long long

ll n,a[10000006],b[10000006];

int main(){

	scanf("%lld",&n);

	for(int i = 1;i <= n;++i)

	scanf("%lld",&a[i]);

	ll sum = 0;

	for(int i = 1;i <= n;++i){

		scanf("%lld",&b[i]);

		sum += a[i] * b[i];

	}

	if(sum == 0)

	puts("Yes");

	else

	puts("No");

}

C

题意

\(2^n\)个人进行树状比赛，问最后获得第二名的人是谁

用类似于线段树的建树，最后对根节点\(1\)的两个子节点进行判断(比较的时候用键值，树上存的是编号)

#include<iostream>

#include<cstdio>

#define ll long long

#define mid ((l + r) >> 1)

ll n,a[1000005];

int val[(1000005) << 2];

void build(int now,int l,int r){

	if(l == r){

		val[now] = l;

		return ;

	}

	build(now * 2,l,mid);

	build(now * 2 + 1,mid + 1,r);

	if(a[val[now * 2]] > a[val[now * 2 + 1]])

	val[now] = val[now * 2];

	else

	val[now] = val[now * 2 + 1];

	return;

} 

int main(){

	scanf("%lld",&n);

	n = (1 << n);

	for(int i = 1;i <= n;++i)

	scanf("%lld",&a[i]);

	build(1,1,n);

	if(val[1] == val[2])

	std::cout<<val[3];

	else

	std::cout<<val[2];

}

D

题意

\(Takahashi\) 出去游玩，现在提供了\(n\)个项目，时间是\([a_i, b_i]\)，这些项目每天分别需要花费\(c_i\)，但它可以选择一天花费\(C\)元玩这天所有可玩项目，项目出现了他就一定要玩，求他的最少花费

考虑离散化，在离散后的数组上打差分标记，再对当前的钱数进行一个前缀和，对每一段判断是否取\(C\)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long 

ll n,C;

ll a[200005],b[200005],c[200005],cnt;

ll num[800005],mark[800005];

unsigned ll now = 0,ans = 0;

int main(){

	scanf("%lld%lld",&n,&C);

	ll sum = 0;

	ll vsum = 0;

	for(int i = 1;i <= n;++i){

		scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);

		num[++cnt] = a[i];

		num[++cnt] = b[i] + 1;

	}

	std::sort(num + 1,num + cnt + 1);

	cnt = std::unique(num + 1,num + cnt + 1) - num - 1;

	for(int i = 1;i <= n;++i){

		mark[std::lower_bound(num + 1,num + cnt + 1,a[i]) - num] += c[i];

		mark[std::lower_bound(num + 1,num + cnt + 1,b[i] + 1) - num] -= c[i];

	}

	num[0] = num[1] + 1;

//	for(int i = 1;i <= cnt;++i)

//	std::cout<<num[i]<<" "<<mark[i]<<std::endl;

	now = mark[1];

	for(int i = 2;i <= cnt;++i){

		//std::cout<<" "<<num[i - 1]<<" "<<num[i]<<" "<<now<<std::endl;

		if(now <= C)

		ans += (now) * (num[i] - num[i - 1]);

		else

		ans += C * (num[i] - num[i - 1]);

		now += mark[i];

	}

	std::cout<<ans<<std::endl;

}

E

题意

有向图，有点权，你可以在一个点上用点权买一块黄金，在再另一块你能到达的点上以点权卖出，问必须进行一次买卖的最大收益

我原本是进行一次\(dfs\)这样处理每个点的前缀最小值，但这样会在环上跑\(2\)次，我也这样\(T\)了一发

我们可以考虑按照点权的大小优先\(dfs\)这样最算有环也只用跑\(1\)次

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define ll long long

ll n,m,cnt,ans = -0x3f3f3f3f;

ll head[200005];

ll val[200005],maxx[200005],minn[200005];

int vis[200005];

struct K{

	ll val,num;

}p[200005];

struct P{

	ll to,next;

}e[400005];

void add(ll x,ll y){

	e[++cnt].to = y;

	e[cnt].next = head[x];

	head[x] = cnt;

}

void dfs(ll now){

	//std::cout<<now<<" "<<val[now]<<" "<<minn[now]<<std::endl;

	ans = std::max(val[now] - minn[now],ans);

	for(int i = head[now];i;i = e[i].next){

		if(!vis[e[i].to]){

		minn[e[i].to] = std::min(minn[now],val[now]);

		vis[e[i].to] ++ ;

		dfs(e[i].to);

		}

	}

}

bool operator < (K a,K b){

	return a.val < b.val;

}

int main(){

	memset(maxx,-0x3f,sizeof(maxx));

	memset(minn,0x3f,sizeof(minn));

	scanf("%lld%lld",&n,&m);

	for(int i = 1;i <= n;++i)

	scanf("%lld",&p[i].val),p[i].num = i,val[i] = p[i].val;

	for(int i = 1;i <= m;++i){

		ll x,y;

		scanf("%lld%lld",&x,&y);

		add(x,y);

	}

	std::sort(p + 1,p + 1 + n);

	for(int i = 1; i<= n;++i)

	if(!vis[p[i].num])

	dfs(p[i].num);

	std::cout<<ans<<std::endl;

}

F

题意

有\(x,y\),可以对\(x做+1,-1,*2\)的操作请问最少几次能到\(y\)

考虑进行记忆化搜索，以后这种没有太好思路的题都可以往搜索想

#include<iostream>

#include<cstdio>

#include<map>

#define ll long long

using std::map;

ll x,y;

map<ll,ll>QWQ;

ll solve(ll y){

	if(y <= x) return x - y;

	if(QWQ.count(y)) return QWQ[y];

	ll ans = y - x;

	if(y % 2) ans = std::min(ans,1 + std::min(solve(y - 1),solve(y + 1)));

	else

	ans = std::min(ans,1 + solve(y / 2));

	return QWQ[y] = ans;

}

int main(){

	scanf("%lld%lld",&x,&y);

	std::cout<<solve(y);

}

巴特西

AtCoder Beginner Contest 188题解

A

题意

B

题意

C

题意

D

题意

E

题意

F

题意

最新文章

热门文章