首页 > 其他分享 >Educational Codeforces Round 161 (Rated for Div. 2) - VP记录

Educational Codeforces Round 161 (Rated for Div. 2) - VP记录

时间:2024-11-06 19:46:23浏览次数:3  
标签:怪兽 Educational Rated idx int Codeforces long -- include

Preface

先被 A 题硬控 \(20\) 分钟,有点不爽。又看到 E 题 AC 的人比 D 题多而去嗑 E 题去了,结果 D 题反而是我更能做的。

将问题排序:根据你所需付出的努力,将能够最快解决的问题排在前面。(答题的次序为:以前做过的,容易的,不熟悉的,难的
——李博杰《骗分导论》\(\rm P_{114}\)

所以下次应该选更有感觉的一道,而不是盲目跟风(除非几道都毫无头绪)。

A. Tricky Template

被红题硬控二十分钟,还得是我。

如果 \(a_i=b_i\),\(s_i\) 可为小写的 \(a_i\)(此时保证 \(c_i \neq a_i,b_i\)),或大写的非 \(a_i\)(此时保证 \(s_i=c_i\))。

如果 \(a_i \neq b_i\),\(s_i\) 必须为大写的 \(c_i\)(此时保证 \(c_i \neq a_i\) 且 \(c_i \neq b_i\))。

有任意一个字母无法满足上述条件即为不合法,否则合法。

点击查看代码
#include<cstdio>
using namespace std;

const int N=25;
int n;
char a[N],b[N],c[N];

bool check()
{
	for(int i=1;i<=n;i++)
	{
		if(a[i]==b[i] && c[i]!=a[i]) return true;
		if(a[i]!=b[i] && c[i]!=a[i]&&c[i]!=b[i]) return true;
	}
	return false;
}
int main()
{
	int T; scanf("%d",&T);
	while(T--)
	{
		scanf("%d%s%s%s",&n,a+1,b+1,c+1);
		printf("%s\n",check()?"YES":"NO");
	}
	return 0;
}

B. Forming Triangles

易得在题目条件下,只有某两条边相等且第三遍不大于这两条边时才合法(即 \(a_i=a_j\) 且 \(a_k \le a_i,a_j\))。

为了避免重复,我们把三角形分为等边和不等边两种。

先把边长排序,从小到大遍历所有边。不等边三角形可以用与 \(a_i\) 相等的边的数量乘以小于 \(a_i\) 的边的数量;等边三角形则直接用组合公式 \(C_x^2 = \frac{x \times (x-1)}{2}\) 来求,其中 \(x\) 表示在此之前与 \(a_i\) 相等的边的数量。

点击查看代码
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=3e5+5;
int n,a[N],cnt[N];

int main()
{
	int T; scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		sort(a+1,a+n+1);
		long long ans=0;
		int end=0;
		for(int i=1;i<=n;i++)
		{
			if(a[i]!=a[i-1]) end=i-1;
			ans+=1ll*cnt[a[i]]*end;
			ans+=1ll*cnt[a[i]]*(cnt[a[i]]-1)/2;
			cnt[a[i]]++;
		}
		printf("%lld\n",ans);
		for(int i=1;i<=n;i++)
			cnt[a[i]]--;
	}
	return 0;
}

C. Closest Cities

贪心思想:从 \(x\) 到 \(y\) 的过程中不可能走回头路。因为不能通过这样的方式缩短路程(最近城市一定相邻)。

因为前面怎么走不影响后面怎么走,且走的时候路径上所有点都必须经过,所以设 \(x<t<y\),则 \(x\) 到 \(y\) 的路径长度等于 \(x\) 到 \(t\) 的路径长度加上 \(t\) 到 \(y\) 的路径长度。

由此,这道题可以用前缀和思想解决,预处理出 \(1\) 到所有点的路径长度,然后查询的时候 \(O(1)\) 直接减即可。

但是因为 \(x\) 可能大于 \(y\),所以还要反着来一遍(因为正着走和反着走路径长度不一定一样),预处理出 \(n\) 到所有点的路径长度(后缀和)。

注意,这里的路径长度是边权而不是点权,所以不用下标减一再算,直接算就可以了。

点击查看代码
#include<cstdio>
using namespace std;

const int N=1e5+5;
int n,q;
long long a[N];
long long presum[N],sufsum[N];

int main()
{
	int T; scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
			presum[i]=sufsum[i]=1e18;
		}
		a[0]=-1e18,a[n+1]=1e18;
		
		presum[1]=0;
		for(int i=1;i<n;i++)
		{
			if(a[i+1]-a[i]<a[i]-a[i-1]) presum[i+1]=presum[i]+1;
			else presum[i+1]=presum[i]+a[i+1]-a[i];
		}
		sufsum[n]=0;
		for(int i=n;i>1;i--)
		{
			if(a[i]-a[i-1]<a[i+1]-a[i]) sufsum[i-1]=sufsum[i]+1;
			else sufsum[i-1]=sufsum[i]+a[i]-a[i-1];
		}
		
		scanf("%d",&q);
		for(int i=1;i<=q;i++)
		{
			int x,y; scanf("%d%d",&x,&y);
			if(x<y) printf("%lld\n",presum[y]-presum[x]);
			else printf("%lld\n",sufsum[y]-sufsum[x]);
		}
		
		for(int i=0;i<=n+1;i++)
			a[i]=sufsum[i]=presum[i]=0;
	}
	return 0;
}

D. Berserk Monsters

考试的时候看到 E 题做对的人多就去做 E 去了,实际上这道题我应该更能做的。

一眼秒出做法,只是代码细节有点多。

首先题目中的怪兽向两侧发出攻击可以直接变成怪兽被两侧攻击,即左右两边攻击力大于怪兽防御时怪兽死亡。

只有当一个怪兽被击杀之后,它两边的怪兽才有机会攻击其它怪兽,进而有机会继续击杀。所以对于每一轮,只需要考虑上一轮死亡的怪兽周围的怪兽(即成功击杀了别的怪兽的怪兽)就行了。

上面的过程可以用 BFS 实现,并用滚动数组/队列来记录这一次需要处理的怪兽和下一轮待处理的怪兽。

\[\texttt{\boxed{\bf 特别注意:当所需要处理的数据分层次的时候,绝不能让本层数据和下一层数据互相影响;即一定不要混用不同层的数据}} \]

在本题中就是下一轮要死亡的怪兽不能在这一轮死亡。

我们还需要做到在每一轮怪兽死亡后快速维护每个怪兽新的相邻怪兽,这个明显可以用链表实现(死亡的数据结构突然开始攻击我:你有多久没有用过链表了?)

点击查看代码
#include<cstdio>
#include<queue>
using namespace std;

const int N=3e5+5;
int n,a[N],d[N];

struct Peter{
	int pre,nxt;
}ls[N];
void Build(int n)
{
	for(int i=1;i<=n;i++)
		ls[i]={i-1,i+1};
	return;
}
void del(int x)
{
	ls[ls[x].pre].nxt=ls[x].nxt;
	ls[ls[x].nxt].pre=ls[x].pre;
	return;
}

queue<int> q[2];
bool inq[2][N];
int ans[N],dead[N];
int predel[N],predel_idx;

void ClearData()
{
	for(int i=1;i<=n;i++)
	{
		inq[0][i]=inq[1][i]=false;
		ans[i]=0;
	}
	while(!q[0].empty()) q[0].pop();
	while(!q[1].empty()) q[1].pop();
	return;
}

int main()
{
	int T; scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++) scanf("%d",&d[i]);
		
		Build(n);
		a[0]=a[n+1]=0;
		for(int i=1;i<=n;i++)
		{
			q[1].push(i);
			inq[1][i]=true;
			dead[i]=0x3f3f3f3f;
		}
		for(int i=1;i<=n;i++)
		{
			bool p=i&1;
			while(!q[p].empty())
			{
				int x=q[p].front(); q[p].pop();
				if(dead[x]<=i) continue;
				inq[p][x]=false;
				int l=ls[x].pre,r=ls[x].nxt;
				if(a[l]+a[r]>d[x])
				{
					predel[++predel_idx]=x;
					dead[x]=i+1;
					ans[i]++;
					if(l!=0 && !inq[!p][l])
					{
						inq[!p][l]=true;
						q[!p].push(l);
					}
					if(r!=n+1 && !inq[!p][r])
					{
						inq[!p][r]=true;
						q[!p].push(r);
					}
				}
			}
			for(int i=1;i<=predel_idx;i++)
				del(predel[i]);
			predel_idx=0;
		}
		for(int i=1;i<=n;i++)
			printf("%d ",ans[i]);
		putchar('\n');
		ClearData();
	}
	return 0;
}

E. Increasing Subsequences

看到这道题做的人多就来做这道题了,把我坑惨了。

考虑新加数时的情景:加一个最小数相当于序列数 \(+1\),加一个最大数相当于序列数 \(\times 2 +1\),乘二是因为可以和前面所有元素组合,加一是因为最大数自己也单独算一个序列。但是,如果把空集看作合法的子序列(题目里也确实是这么规定的),那么这个加一就相当于与空集组合。即当把集合看作最开始就有一个元素“空”,那么每次单独一个元素就可以看作与空集组合,这样加最大数的时候就不用再额外判断自己单独组成一个序列,所有新序列都是和原序列组合而成的,这样就只用 \(\times 2\) 了。

问题就可以转化为:初始为 \(1\),通过 \(+1\) 和 \(\times 2\) 这两种操作来构成 \(X\),这个很容易二进制分解实现,具体做法很多,我这里提供一种写法:

点击查看代码
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=205;
int ans[N];
long long x;

int main()
{
	int T; scanf("%d",&T);
	while(T--)
	{
		scanf("%lld",&x);
		int idx=0,tmp=1e9;
		while(x>1)
		{
			if(x&1) 
			{
				ans[++idx]=0;
				x--;
			}
			else
			{
				ans[++idx]=tmp--;
				x>>=1;
			}
		}
		printf("%d\n",idx);
		for(int i=idx;i>=1;i--)
			printf("%d ",ans[i]);
		putchar('\n');
	}
	return 0;
}

标签:怪兽,Educational,Rated,idx,int,Codeforces,long,--,include
From: https://www.cnblogs.com/jerrycyx/p/18530855

相关文章

  • Codeforces Round 983 (Div. 2) 10.31 ABC题解
    CodeforcesRound983(Div.2)10.31题解A.Circuit数学(math)贪心(greedy)模拟(implementation)题意:有\(n\)盏灯,对应\(2\astn\)个开关,即每盏灯对应两个开关,开关打开或者关闭用\(1\)和\(0\)表示。给出\(2\astn\)个开关的状态,需要求解出可能开灯的最小数量和最大数量。......
  • Educational Codeforces Round 171 (Rated for Div. 2) 题解
    A.PerpendicularSegments显然构造一个\(k\timesk\)的左下角是原点的正方形即可。voidslv(){ intx,y,k;Read(x,y,k); intmn=min(x,y); if(mn*mn*2>=k*k) Write(0,'',0,'',mn,'',mn,'\n'), Write(0,......
  • Codeforces Round 984 div3 个人题解(A~F)
    CodeforcesRound984div3个人题解(A~F)Dashboard-CodeforcesRound984(Div.3)-Codeforces火车头#define_CRT_SECURE_NO_WARNINGS1#include<algorithm>#include<array>#include<bitset>#include<cassert>#include<cmath>#in......
  • Codeforces Round 983 (Div. 2) 题解
    CodeforcesRound983(Div.2)题解CodeforcesRound983(Div.2)Problem-A-Codeforces解题思路考虑贪心,每个灯连两个开关,即两个开的灯可以关闭一盏灯,则灯数最多则尽可能让两个开关都开的灯尽量少,灯数最少则反之#include<bits/stdc++.h>#defineendl'\n'usingnam......
  • Codeforces Round 983 (Div. 2) A~D
    链接:CodeforcesRound983(Div.2)A:Circuit大意:    n个灯,每个灯连两个开关,每个开关只连一个灯,每个灯对应的两个开关如果异或为1就亮    现给定开关状态,求灯亮的最大和最小数量思路:    求最小数量的话,将开关为1的尽量组一起,我们发现,如果开关为1的......
  • Educational CF Round 171
    游记理所当然VP了秒速过A,打B犯了一天的傻逼看错条件理所当然的只过了一道愉快开启改题生活当然改题也挺那啥的题解A挺简单的找\(X,Y\)的最小值,即找到长方形可框住的最大的正方形直接输出此正方形的顶点坐标即可证明考虑超出此正方形的点在旋转平移以后都会超出长方形范......
  • Codeforces Round 983 Div2 A-C
    目录A-CircuitB-MediansC-TrinityD-总结与思考A-Circuit题目概述Alice刚刚制作了一个包含n个灯和2n个开关的电路。每个组件(灯或开关)有两种状态:开或关。灯和开关的排列方式如下:每个灯连接恰好两个开关。每个开关连接恰好一个灯。但并不知道每个开关......
  • Codeforces Round 983 (Div. 2)
    A最坏的情况就是所有开着的开关尽可能配对最好的情况就是所有开着的开关尽可能不配对#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<int,int>PII;constintN=1e6+10;constintmod=998244353;constintINF=0x3f3f3f3f;constllI......
  • Codeforces Round 983 div2 个人题解(A~D)
    CodeforcesRound983div2个人题解(A~D)Dashboard-CodeforcesRound983(Div.2)-Codeforces火车头#define_CRT_SECURE_NO_WARNINGS1#include<algorithm>#include<array>#include<bitset>#include<cassert>#include<cmath>#in......
  • CodeForces Dora and C++ (2007C) 题解
    CodeForcesDoraandC++(2007C)题解题意给一个数组\(c_{1...n}\),定义数组的\(range\)是最大值减最小值,即极差。给出两个值\(a\)和\(b\),每步操作中,可给数组中任一一个数增大\(a\)或增大\(b\)。问任意步操作后(可以是\(0\)步),极差的最小值。思路(要直接看答案可以跳......