这还要写游记？
直接进入题解环节。
[[春季测试 2023] 涂色游戏]
难度： \(Easy+\)
标签：无
十分弱智的一道题......
显然地，对于任意一个格子 \((x,y)\) ，它最多被两次操作影响它 最终 的状态——对于行 \(x\) 的操作和对于列 \(y\) 的操作。
因为一次操作会被下一次操作覆盖，所以对于每个格子 \((x,y)\) 只需要看对于行 \(x\) 的操作和对于列 \(y\) 的操作的时间戳哪个大就行了。
简单地说，若对于行 \(x\) 的最后一次操作为将它染成 \(c_i\) ，对于列 \(y\) 的最后一次操作为将它染成 \(c_j\) ，那么若 \(i<j\) ，则格子 \((x,y)\) 的颜色为 \(c_j\) ；否则为 \(c_i\) 。
注意没被染色的格子为 \(0\) ，时间复杂度为 $ \Theta(nm+q) $ 。
点击查看代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int T,n,m,q;
pair<int,int> row[100005],line[100005];
inline void solve()
{
memset(row,0,sizeof(row)),memset(line,0,sizeof(line));
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=q;++i)
{
int opt,pos,color; scanf("%d%d%d",&opt,&pos,&color);
if(opt==0) row[pos]=make_pair(color,i);
if(opt==1) line[pos]=make_pair(color,i);
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(row[i]==make_pair(0,0)&&line[j]==make_pair(0,0)) printf("0 ");
else printf("%d ",(row[i].second>line[j].second)?(row[i].first):(line[j].first));
}
putchar('\n');
}
}
int main()
{
scanf("%d",&T);
while(T--) solve();
return 0;
}
[[春季测试 2023] 幂次]
难度： \(Normal\)
标签：暴力
如果你的暴力没过，那么就说明你的暴力不够优雅。
[[春季测试 2023] 圣诞树]
难度： \(Hard-\)
标签：区间类型动态规划、贪心算法
2023.3.4，傻逼待宵因没认真看样例痛失80pts，警钟长鸣。
很多人写的都是完全贪心，这当然是错误的，但是正解还是包含一些贪心思想的。
我们以 \(k\) 为分割点，将凸包分为两段：左段和右段。例如在题目给的图中，整个凸包就被分为了 $ \{ 1,2,3,4 \} $ 和 $ \{ 5,6,7,8,9 \} $ 两段，其中 $ \{ 1,2,3,4 \} $ 为左段， $ \{ 5,6,7,8,9 \} $ 为右段。
因为测试数据是顺序给出的，所以每一段的顺序还是原来的顺序。根据贪心思想，对于左段来说，设这里面有两个点 \(i,j(i<j)\) ，那么就不能先到 \(j\) 点再回到 \(i\) 点；对于右段来说，设这里面有两个点 \(i,j(i<j)\) ，那么就不能先到 \(i\) 点再回到 \(j\) 点。
所以其实我们都是已经走过了一个包含 \(k\) 的区间 \([l,r]\) ，然后再走到下一个点的。这不就是区间DP典题 关路灯 吗？
我们设 \(f(l,r,0)\) 表示已经走完了 \([l,r]\) 这段区间且走到这个区间的左端点 \(l\) 的最小花费，设 \(f(l,r,1)\) 表示已经走完了 \([l,r]\) 这段区间且走到这个区间的右端点 \(r\) 的最小花费，那么对于 \(f(l,r,0)\) ，我们肯定是先走完了 \([l+1,r]\) 这段区间再转移到 \(l\) 的，所以是从 \(f(l+1,r,0/1)\) 这个状态转移的。如果我们在 \([l+1,r]\) 这个区间的左端点 \((l+1)\) 上，那么就要花费 $ \text{dist} (l+1,l)$ 走到 \(l\) ；如果在右端点 \(r\) ，那么就要花费 $ \text{dist} (r,l)$ 走到 \(l\) ，所以有转移方程：
\[f(l,r,0)= \min \{ f(l+1,r,0)+ \text{dist} (l+1,l),f(l+1,r,1)+ \text{dist} (r,l) \} \]对于 \(f(l,r,1)\) 的转移同理，我们要先走完区间 \([l,r-1]\) 才能走到 \(r\) ：
\[f(l,r,1)= \min \{ f(l,r-1,0)+ \text{dist} (l,r),f(l,r-1,1)+ \text{dist} (r-1,r) \} \]然而还有一个很重要的一点： 因为终点不一定是 \(1\) 或 \(n\) ，所以我们走的实际上是一个环 。既然是环，那么我们就要断环为链，具体方法如下：
-
设二元组序列 \((x',y')_i\)
-
令 \((x',y')_{i-k}=(x,y)_i (i \in [k+1,n])\)
-
令 \((x',y')_{n-k+i}=(x,y)_i (i \in [1,k-1])\)
-
令 \((x',y')_n=(x,y)_k\)
-
以 \(n\) 为起点， \((x',y')\) 为各点位置进行区间DP
简单地说，就是将右段放在前面，左段放在右段的后面， \(k\) 放在最后。
最后输出路径即可。时间复杂度为 $ \Theta(n^2) $ 。
点击查看代码
#include <cmath>
#include <cstdio>
#include <algorithm>
#define x first
#define y second
using namespace std;
const double inf=1e18;
int n,k,id[1005];
double dis[1005][1005],f[1005][1005][2],pre[1005][1005][2];
pair<double,double> a[1005],b[1005];
inline double dist(const int A,const int B) {return sqrt((b[A].x-b[B].x)*(b[A].x-b[B].x)+(b[A].y-b[B].y)*(b[A].y-b[B].y));}
inline void print()
{
int l=1,r=n-1,mode=(f[1][n-1][0]+dist(1,n)>f[1][n-1][1]+dist(n-1,n));
printf("%d ",k);
while(true)
{
printf("%d ",id[(mode==0)?(l):(r)]);
if(l==r) return;
l+=(mode^1),r-=mode,mode=pre[l-(mode^1)][r+mode][mode];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
for(int i=n;i>=1;--i)
if(!k||a[i].y>a[k].y) k=i;
for(int i=k+1;i<=n;++i) b[i-k]=a[i],id[i-k]=i;
for(int i=1;i<k;++i) b[n-k+i]=a[i],id[n-k+i]=i;
b[n]=a[k];
for(int len=2;len<n;++len)
for(int l=1,r=l+len-1;r<n;++l,++r)
{
f[l][r][0]=f[l][r][1]=inf;
if(f[l][r][0]>f[l+1][r][0]+dist(l+1,l)) f[l][r][0]=f[l+1][r][0]+dist(l+1,l),pre[l][r][0]=0;
if(f[l][r][0]>f[l+1][r][1]+dist(r,l)) f[l][r][0]=f[l+1][r][1]+dist(r,l),pre[l][r][0]=1;
if(f[l][r][1]>f[l][r-1][0]+dist(l,r)) f[l][r][1]=f[l][r-1][0]+dist(l,r),pre[l][r][1]=0;
if(f[l][r][1]>f[l][r-1][1]+dist(r-1,r)) f[l][r][1]=f[l][r-1][1]+dist(r-1,r),pre[l][r][1]=1;
}
return print(),0;
}