模考总结 - “君不见，高堂明镜悲白发”
2026-07-15 20:07:29
发布于：浙江
5阅读
0回复
0点赞
自主学习笔记类产物
“君不见，黄河之水天上来。奔流到海不复回。君不见，高堂明镜悲白发，朝如青丝暮成雪。” —— 李白《将进酒》
——————————————————————————————————————————
本次考试状态还算可以。
想打的部分分基本都打满了。
我觉得有问题的是：
1.T3没有想出来动态规划的部分分解法
2.T2为什么没有满分？
3.T1为什么没有满分？
T1 海报换色
https://xinyoudui.com/ac/contest/745010F75000BED091A8B1/problem/46068
这道题目在考试的时候我拼了很多个部分分解法拼出了95分。
考试的时候已经注意到了一共有九个格子（一个格子改变颜色最多只能影响到周围的那几个）
唯一没有想到的是当周围的八个格子已经包含了个颜色应该怎么办。
那现在来写写解法好了。
1.当周围的八个格子并没有凑满个颜色 -> 那么就让中间这个格子变成一个没有出现过的颜色
2.当周围的八个格子已经凑满了个颜色 -> 那么就枚举，让中间这个格子一次变成中颜色
而后计算变化后的价值（价值指的是与原先相比的差值），通过比较得出最大的差值。
计算一遍在没有任何修改时，原先的答案，然后把原先的答案加上现在的差值就是最终的答案了。
#include<bits/stdc++.h>
using namespace std;
const int N=305;
int a[N][N];
int s[10];
int q(int A,int B,int C,int D){
int c=1;
if(B!=A)c++;
if(C!=B&&C!=A)c++;
if(D!=C&&D!=B&&D!=A)c++;
if(c>=3)return 1;
return 0;
}
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
int sum1=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int yuan=0;
if(i>=2&&j>=2)yuan=q(a[i-1][j-1],a[i-1][j],a[i][j-1],a[i][j]);
if(i>=2&&j+1<=n)yuan+=q(a[i-1][j],a[i-1][j+1],a[i][j],a[i][j+1]);
if(j-1>=1&&i+1<=n)yuan+=q(a[i][j-1],a[i][j],a[i+1][j-1],a[i+1][j]);
if(i+1<=n&&j+1<=n)yuan+=q(a[i][j],a[i][j+1],a[i+1][j],a[i+1][j+1]);
int cnt=0;
if(a[i-1][j])s[++cnt]=a[i-1][j];
if(a[i][j-1])s[++cnt]=a[i][j-1];
if(a[i-1][j+1])s[++cnt]=a[i-1][j+1];
if(a[i][j+1])s[++cnt]=a[i][j+1];
if(a[i+1][j-1])s[++cnt]=a[i+1][j-1];
if(a[i+1][j])s[++cnt]=a[i+1][j];
if(a[i+1][j+1])s[++cnt]=a[i+1][j+1];
if(a[i-1][j-1])s[++cnt]=a[i-1][j-1];
sort(s+1,s+1+cnt);
int ed=std::unique(s+1,s+1+cnt)-s-1;
s[++ed]=k+1;
int cun=a[i][j];
int sum=0;
for(int z=1;z<=ed;z++){
if(z==ed&&ed-1==k)continue;
a[i][j]=s[z];
int yuan1=0;
if(i-1>=1&&j-1>=1)yuan1+=q(a[i-1][j-1],a[i-1][j],a[i][j-1],a[i][j]);
if(i-1>=1&&j+1<=n)yuan1+=q(a[i-1][j],a[i-1][j+1],a[i][j],a[i][j+1]);
if(j-1>=1&&i+1<=n)yuan1+=q(a[i][j-1],a[i][j],a[i+1][j-1],a[i+1][j]);
if(i+1<=n&&j+1<=n)yuan1+=q(a[i][j],a[i][j+1],a[i+1][j],a[i+1][j+1]);
sum=max(sum,yuan1-yuan);
}
a[i][j]=cun;
sum1=max(sum1,sum);
}
}
int ans=sum1;
for(int i=1;i<n;i++){
for(int j=1;j<n;j++){
ans+=q(a[i][j],a[i][j+1],a[i+1][j],a[i+1][j+1]);
}
}
cout<<ans;
return 0;
}
需要注意的问题：
1.发现近日在使用unqiue进行去重/离散化的时候非常容易弄混原来的下标和ed，所以在弄完unique之后需要注重检查
冰场折返
理论上而言，这道题目我应该在考场上写出来的。现在来看看哪里出问题了。
我原先的思路应该是趋近于正确的：用的数组取维护到达一个障碍物的方向，离开这个障碍物的方向。
用排序+二分+BFS的思路去寻找到达终点的最小值。
调出来了，但是我目前确实不清楚是错在了哪里，先放置一下。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define int long long
struct Node{
int x,y,b;
}node[N],node1[N];
int A[N],B[N];
bool cmp(Node a,Node b){
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
bool cmp1(Node a,Node b){
if(a.y!=b.y)return a.y<b.y;
return a.x<b.x;
}
struct Nodeq{
int nx,ny,now;
int f;//方向
};
queue<Nodeq>q;
bool vis[N][5][5];//每个路障，从四个方向过来，再从四个方向划出
signed main(){
int h,w,n;//行数，列数，路障数
cin>>h>>w>>n;
int sx,sy,gx,gy;//起点，终点
cin>>sx>>sy>>gx>>gy;
for(int i=1;i<=n;i++)cin>>node[i].x>>node[i].y,node[i].b=i;
for(int i=1;i<=n;i++)node1[i]=node[i];
sort(node+1,node+1+n,cmp);
sort(node1+1,node1+1+n,cmp1);
for(int i=1;i<=n;i++)A[i]=node[i].x,B[i]=node1[i].y;
q.push({sx,sy,0,1});//上
q.push({sx,sy,0,2});//下
q.push({sx,sy,0,3});//左
q.push({sx,sy,0,4});//右
while(!q.empty()){
Nodeq sum=q.front();
q.pop();
if(sum.nx==gx&&sum.ny==gy){
cout<<sum.now;
return 0;
}
if(sum.f==1){
int su=lower_bound(B+1,B+1+n,sum.ny)-B;
if(B[su]!=sum.ny||su==n+1)continue;
while(B[su]==sum.ny&&node1[su].x<sum.nx)su++;
su--;
if(node1[su].x>=sum.nx)continue;
for(int i=1;i<=4;i++){
if(vis[node1[su].b][2][i])continue;
if(i==2)continue;
vis[node1[su].b][2][i]=1;
q.push({node1[su].x+1,node1[su].y,sum.now+1,i});
}
}else if(sum.f==2){
int su=lower_bound(B+1,B+1+n,sum.ny)-B;
if(B[su]!=sum.ny||su==n+1)continue;
while(B[su]==sum.ny){
if(node1[su].x>sum.nx)break;
su++;
}
if(node1[su].x<=sum.nx)continue;
for(int i=1;i<=4;i++){
if(vis[node1[su].b][1][i])continue;
if(i==1)continue;
vis[node1[su].b][1][i]=1;
q.push({node1[su].x-1,node1[su].y,sum.now+1,i});
}
}else if(sum.f==3){
int su=lower_bound(A+1,A+1+n,sum.nx)-A;
if(A[su]!=sum.nx||su==n+1)continue;
while(A[su]==sum.nx&&node[su].y<sum.ny)su++;
su--;
if(node[su].y>=sum.ny)continue;
for(int i=1;i<=4;i++){
if(vis[node[su].b][4][i])continue;
if(i==4)continue;
vis[node[su].b][4][i]=1;
q.push({node[su].x,node[su].y+1,sum.now+1,i});
}
}else if(sum.f==4){
int su=lower_bound(A+1,A+1+n,sum.nx)-A;
if(A[su]!=sum.nx||su==n+1)continue;
while(A[su]==sum.nx){
if(node[su].y>sum.ny)break;
su++;
}
if(node[su].y<=sum.ny)continue;
for(int i=1;i<=4;i++){
if(vis[node[su].b][3][i])continue;
if(i==3)continue;
vis[node[su].b][3][i]=1;
q.push({node[su].x,node[su].y-1,sum.now+1,i});
}
}
}
cout<<-1;
return 0;
}
T3 玩具装箱
这玩意儿的正解是斜率优化DP，我写不出来。
我们直接来写它的部分分DP。
这道题目的部分分其实是一个相当常规的线性动态规划，有。
但是我考场上只写了一个剪枝暴力和一个假贪心，。
所以我认为我的普及组算法掌握的相当不好，正好明天是休息日。
这两天多写一点贪心和动态规划的基础题。
放置一下的代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
#define int long long
int a[N],pre[N],dp[N];
signed main(){
int n,l;
cin>>n>>l;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
for(int i=1;i<=n;i++){
dp[i]=1e18;
for(int j=1;j<=i;j++){
int x=(pre[i]-pre[j-1]+i-j-l)*(pre[i]-pre[j-1]+i-j-l);
dp[i]=min(dp[i],dp[j-1]+x);
}
}
cout<<dp[n];
return 0;
}
这里空空如也
有帮助，赞一个