碎碎念
《重生之七日成神》火热连载中（
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;
}
Comments NOTHING