首页 > 其他分享 >Educational Codeforces Round 158 (Rated for Div. 2)

Educational Codeforces Round 158 (Rated for Div. 2)

时间：2023-12-07 11:59:06浏览次数：35  
标签：Educational Rated const int 158 typedef long include define

Preface

补题，妈的现在Edu E都做不来这搞毛啊

A. Line Trip

签到

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=55;
int t,n,x,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&x),i=1;i<=n;++i) scanf("%d",&a[i]);
		int ans=2*(x-a[n]); for (i=1;i<=n;++i) ans=max(ans,a[i]-a[i-1]);
		printf("%d\n",ans);
	}
	return 0;
}

B. Chip and Ribbon

不难发现这题转化一下就是每次可以给一段区间内的数都减\(1\)，问最少要几步可以把所有数变成\(0\)，经典差分求解即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		LL ans=0; for (i=1;i<=n;++i) ans+=max(0,a[i]-a[i-1]);
		printf("%lld\n",ans-1);
	}
	return 0;
}

C. Add, Divide and Floor

不难发现我们只要把序列的最大最小值找出来，只要把它们变成相同的，那么整个序列中所有数一定都相同

同时稍作分析会发现所有操作可以归为\(x=0\)或\(x=1\)，并且手玩一下会发现最优策略就是看最小值的奇偶性

如果最小值为奇数就用\(x=1\)，为偶数就用\(x=0\)，这样可以尽量减小两个数的差值

操作次数是\(\log\)级别的，可以直接模拟

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		int mn=*min_element(a+1,a+n+1),mx=*max_element(a+1,a+n+1);
		vector <int> ans; while (mn!=mx)
		{
			if (mn%2==1) ans.push_back(1),mn=(mn+1)/2,mx=(mx+1)/2;
			else ans.push_back(0),mn/=2,mx/=2;
		}
		printf("%d\n",ans.size());
		if (ans.size()>0&&ans.size()<=n)
		{
			for (auto x:ans) printf("%d ",x); putchar('\n');
		}
	}
	return 0;
}

D. Yet Another Monster Fight

枚举第一次操作的位置\(i\)，分别考虑此时向两边传递的最坏次数

对于\(j<i\)，其最坏需要的初始伤害为\(a_j+n-j\)；对于\(j>i\)，其最坏需要的初始伤害为\(a_j+j-1\)

做一个前缀/后缀max后直接枚举即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=300005;
int n,a[N],pre[N],suf[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);
	for (pre[0]=0,i=1;i<=n;++i) pre[i]=max(pre[i-1],a[i]+n-i);
	for (suf[n+1]=0,i=n;i>=1;--i) suf[i]=max(suf[i+1],a[i]+i-1);
	int ans=1e18; for (i=1;i<=n;++i) ans=min(ans,max({a[i],pre[i-1],suf[i+1]}));
	printf("%lld\n",ans);
	return 0;
}

E. Compressed Tree

我承认我大物课最后几分钟想这题有点急，但这不是做不出的理由

考虑最后压缩时一个点被删去当且仅当其度数为\(2\)，考虑直接用树形DP求解

当我们把这棵树强制转化成有根树后，一个点的度数的贡献就有两种类型，来自儿子的和来自父亲的

但由于这题的删除操作有着很好的性质：如果要将某个点父亲方向的连边断开，则需要把这个点子树外的所有点都删去

因此我们还是只要像一般的树形DP那样只关系子树状态即可，最后枚举要不要删这个点父亲方向的边即可

令\(f_x\)表示在点\(x\)的子树中，当\(x\)向父亲方向的边保留时能得到的最大权值，转移的话根据\(x\)点的度数讨论下即可，注意当\(x\)只有一个孩子时不能算\(a_x\)的贡献

最后考虑如果要断开\(x\)向父亲方向的边时也是类似的情况，注意当\(x\)有两个孩子时不能算\(a_x\)的贡献

因为当一个点的孩子数量\(\ge 3\)时就不再有区别了，因此开一个\([0,3]\)的辅助数组即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=500005,INF=1e18;
int t,n,a[N],x,y,f[N],ans; vector <int> v[N];
inline void DFS(CI now=1,CI fa=0)
{
	int g[4]={0,-INF,-INF,-INF}; RI i;
	for (auto to:v[now]) if (to!=fa)
	{
		DFS(to,now); for (i=3;i>=0;--i)
		g[min(i+1,3LL)]=max(g[min(i+1,3LL)],g[i]+f[to]);
	}
	for (f[now]=-INF,i=0;i<4;++i)
	{
		f[now]=max(f[now],g[i]+(i==1?0:a[now]));
		ans=max(ans,g[i]+(i==2?0:a[now]));
	}
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]),v[i].clear();
		for (i=1;i<n;++i) scanf("%lld%lld",&x,&y),v[x].push_back(y),v[y].push_back(x);
		ans=0; DFS(); printf("%lld\n",ans);
	}
	return 0;
}

Postscript

菜的发昏属于是

标签：Educational,Rated,const,int,158,typedef,long,include,define
From： https://www.cnblogs.com/cjjsb/p/17881364.html

相关文章

  • CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
    Preface补题，经典不会F，看了会题解发现看不懂，索性直接开摆A.JaggedSwaps判断\(a_1\)是否为\(1\)即可#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>#include<cmath>#include<cstdlib>#include<al......
  • Educational Codeforces Round 159 总结
    最失败的一集。C开题顺序搞错，不小心先开了C，以为是A。还好C不难。题意大概是在给定的数组最后添一个数（所有数两两不同），再自定义一个数\(k\)，数组中每个数可以加上若干个\(k\)，最后使得所有数字相等。要求加\(k\)的次数最少。如果不加最后一个数，那么显然把所有的数加到与最大......
  • [CF1902] Educational Codeforces Round 159 A~E 题解
    [CF1902]EducationalCodeforcesRound159A~E题解A.BinaryImbalance很快观察到如果有不同的相邻元素，那么一定有解，意味着如果全是1无解，其他有解B.GettingPoints题面很长，可以发现，最好的偷懒方式一定是把所有的课都拖到最后几天上（真实），可以简单调整证明这样是不劣的，最后......
  • [Educational Codeforces Round 159 (Rated for Div. 2)](https://codeforces.com/con
    EducationalCodeforcesRound159(RatedforDiv.2)好困，差点没打A-BinaryImbalance#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){ strings; intn; cin>>n; cin>>s; if(n==......
  • Educational Codeforces Round 158 (Rated for Div. 2)
    EducationalCodeforcesRound158(RatedforDiv.2)AEDU的题总是感觉写起来怪怪的#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;inta[101];voidsolve(){intn,x;cin>>n>>x;intans=0;......
  • Educational Codeforces Round 159 (Rated for Div. 2)
    EducationalCodeforcesRound159(RatedforDiv.2)基本情况A题秒了。B题想出来贪心思想，也想出来怎么找最优解了，但实现极其复杂繁琐，最后以先超时优化后又错误的结果告终。B.GettingPoints明显越后面开始学收益越高。然后写了个简单粗暴的纯模拟，T了。#include<iostrea......
  • 13、深度学习入门：P154、P155、P156、P157、P158、P159
    1、调整权重和偏置以便拟合训练数据的过程称为学习这句话指的是机器学习中模型训练的过程。在训练一个机器学习模型时，我们通常有一个训练数据集，其中包含输入和对应的期望输出。模型的目标是通过学习这些数据中的模式和规律，以便在未见过的数据上做出准确的预测或执行任务。模型学......
  • AT_ARC158A解题报告
    AT_ARC158A解题报告题意题目传送门给你3个数\(a,b,c\)，通过若干次操作使得\(a=b=c\)。一次操作指将\(a,b,c\)按任意顺序分别\(+3,+5,+7\)。若可以使\(a=b=c\)，输出最小操作次数，否则输出\(-1\)。思路我们可以将\(+3,+5,+7\)每一项都减去\(5\)得到\(-2,0,+2\)。......
  • Educational Codeforces Round 158 (Rated for Div. 2)
    A.LineTripThereisaroad,whichcanberepresentedasanumberline.Youarelocatedinthepoint\(0\)ofthenumberline,andyouwanttotravelfromthepoint\(0\)tothepoint\(x\),andbacktothepoint\(0\).Youtravelbycar,whichs......
  • CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
    看到B官方题解写了一堆，而如果能注意到一些性质，几行就写完了题意：给一个A，B构成的字符串，可以将“AB”翻转成"BA",问最多可以进行多少次翻转？实际上在手动模拟以后发现，由于题目限制了每个位置只能翻转一次，所以情况简单了不少。只要还没过最后一个B，那么最后一个B之前的所有A就会被反......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99