CF1716

发布于 2022-08-05  499 次阅读


碎碎念

《重生之七日成神》火热连载中(

Day4

因为Day3没有完成当日计划,于是开摆,并延续到了今天(

晚上心血来潮打完了欠下的F题(E题太难了),然后发现胡了一个假的算法,好啊!!!

在床上想到了正解,写进备忘录里,下次再打叭qwq

Day5

白天加了个实验室类的社团群,发现里面有个oj,做完了还有奖品拿

瞄了一眼49题都是普及-,狂喜,正好适合俺练手

虽然一题只要5分钟,写了28题还是写麻了

有一说一,疯狂星期四我好爱

晚上cf有场edu,两个小时,六题做四题

《关于我一天A了32题这档事》

30道普及-,2道普及+,呜呜

Day6

晚上九点,昨天的edu还是没加rating,难道edu场不算rating的吗

今天准备写完剩下的21题(大概),顺便来个下期预告

《重生之七日成神》大结局-Day7

《第一份兼职竟然是信奥助教》Day1-Day?

--------碎碎念到此结束,下面是正文(手动分割线)--------

A - 2-3 Moves

每次左右任走2到3步,询问0到n的最少步数

solution

手算几个找规律即可

#include<bits/stdc++.h>
using namespace std;
int T,n;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		if(n==1)printf("2\n");
		else printf("%d\n",(n-1)/3+1);
	}
    return 0;
}

B - Permutation Chain

定义一个排列 a (有 n 个元素)的“固定性”为:∑​[a[i]=i]

要求你建立一个排列的序列 a1​,a2​,...,ak​ ( a[i] 为一个 1 ~ n 的排列),使得:

  • ai+1​ 是由 ai​ 交换任意两个元素得到的
  • 这些排列的"固定性"严格递减

输出任意一个最长的序列

solution

最长的序列一定是长度为n的,考虑直接构造这个序列

第一次交换1和n,后面每次把1往前移一位即可

#include<bits/stdc++.h>
using namespace std;
int T,n,a[110];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		printf("%d\n",n);
		for(int i=1;i<=n;i++)
			a[i]=i,printf("%d ",a[i]);
		printf("\n"),swap(a[1],a[n]);
		for(int i=1;i<n;i++)
		{
			for(int j=1;j<=n;j++)
				printf("%d ",a[j]);
			printf("\n"),swap(a[n-i],a[n-i+1]);
		}
	}
    return 0;
}

C - Robot in a Hallway

有一2行m列的网格,从上到下编号为1至2,从左往右编号为1至m

机器人开始时在网格(1,1)内。一秒内,它可以进行如下任意一个动作:

  • 走到上、下、左、右任意相邻的网格
  • 待在网格内不动

开始时,除了网格(1,1)其他格子都是锁着的。每个网格(i,j)有一个值ai,j,表示该网格解锁的时间。只有经过至少ai,j​秒后,机器人才可以进入网格(i,j)。

机器人要走遍所有网格,且每个网格只能被访问一次(网格(1,1)在一开始就被访问过)。访问可以在任意网格内结束。

实现如上操作的最快时间是什么?

solution

可以发现走的方案数其实是很有限的,所以计算每一次的答案就可以了

难点在于如何统计每一个格子的贡献,太复杂了懒得写了QAQ

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
struct node
{
	int x,y,p,s;
}l[200010],r[200010];
int T,m,rt,a[2][200010];
int id(int i,int j)
{
	if(i==0)return j;
	return m*2-j+1;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
			scanf("%d",&a[0][rt+i]);
		for(int i=1;i<=m;i++)
			scanf("%d",&a[1][rt+i]);
		a[0][rt+1]=-1;
		if(a[0][rt+m]>a[1][rt+m])
			r[rt+m]={0,m,id(0,m),a[0][rt+m]};
		else r[rt+m]={1,m,id(1,m),a[1][rt+m]};
		if(a[0][rt+m]<a[1][rt+m])
			l[rt+m]={1,m,id(1,m),a[1][rt+m]};
		else l[rt+m]={0,m,id(0,m),a[0][rt+m]};
		for(int i=m-1;i>=1;i--)
		{
			if(a[0][rt+i]-id(0,i)+l[rt+i+1].p>l[rt+i+1].s)
				l[rt+i]={0,i,id(0,i),a[0][rt+i]};
			else l[rt+i]=l[rt+i+1];
			if(a[1][rt+i]-id(1,i)+l[rt+i].p>l[rt+i].s)
				l[rt+i]={1,i,id(1,i),a[1][rt+i]};
			
			if(a[0][rt+i]+id(0,i)-r[rt+i+1].p>r[rt+i+1].s)
				r[rt+i]={0,i,id(0,i),a[0][rt+i]};
			else r[rt+i]=r[rt+i+1];
			if(a[1][rt+i]+id(1,i)-r[rt+i].p>r[rt+i].s)
				r[rt+i]={1,i,id(1,i),a[1][rt+i]};
		}
		int step=0;
		int ans=inf;
		for(int i=1;i<=m;i++)
		{
			if(i%2)
			{
				ans=min(ans,max(step,l[rt+i].s-l[rt+i].p+id(1,i)+1));
				step=max(step,max(a[0][rt+i]+m*2-i*2+2,a[1][rt+i]+m*2-i*2+1));
			}
			else
			{
				ans=min(ans,max(step,r[rt+i].s+r[rt+i].p-id(0,i)+1));
				step=max(step,max(a[0][rt+i]+m*2-i*2+1,a[1][rt+i]+m*2-i*2+2));
			}
		}
		printf("%d\n",ans);
		rt+=m;
	}
    return 0;
}

D - Chip Move

给定两个数 n,k,问从 0 开始,第 i 步只能走 (k+i−1) 的倍数,问分别走到 x∈[1,n] 的方案数,对 998244353 取模。

solution

一眼dp,每k个为一组,分组dp即可

#include<bits/stdc++.h>
#define MOD 998244353
using namespace std;
int n,k,dp[200010],lp[200010],p[200010];
int main()
{
	scanf("%d%d",&n,&k);
	int st=k;p[0]=1;
	while(st<=n)
	{
		for(int i=st;i<=n;i++)
			p[i]=(p[i-k]+lp[i-k])%MOD;
		for(int i=st;i<=n;i++)
			dp[i]=(dp[i]+p[i])%MOD,lp[i]=p[i],p[i]=0;
		k++,st+=k;
	}
	for(int i=1;i<=n;i++)
		printf("%d ",dp[i]);
    return 0;
}