--原题见洛谷P3954 - P3957
T1成绩
一看就是 A * 0.2 + B * 0.3 + C * 0.5 .
复杂度O （1）.
T2 图书管理员
我们可以发现，输入数据给定了需求码的位数，所以我们可以预处理出10的1-9次幂，
然后在每次询问中我们可以把图数码 % ( 10^k ) 其中k为需求码的位数.
复杂度 O（nq）.
T3棋盘
记忆化宽搜
记录状态：
x,y 表示当前坐标；
cost 表示当前的花费;
magic 表示上一步是否用了魔法,如果用了,magic标记为上一步把这个格子变成了什么颜色,否则magic标记为-1;（这个很关键！）
然后，宽搜时我们可以开一个二维数组ans[][]来维护每个格子的Ans，（初始化为INT_MAX）
最后我们输出ans[m][m] 或 -1 作为答案。
//具体见文末代码（有注释）
T4跳房子
二分答案+DP
显然这个问题单调，所以我们可以二分答案（不知道的自行百度）。
二分答案中我们可以DP作为check，
50分做法：
F[i] 表示 从 1 跳到 i 的最大分数
显然 F[i] = MAX( F[j] ) + s_i, 其中 j 为所有可以跳到 i 的格子。
复杂度O（n^2*k），其中 k为二分答案的check次数
但显然过不了（手动滑稽）。
100分做法：
在上一个算法的基础上，用单调队列/线段树 优化DP到 O（nlogn）
复杂度O(n * logn * k)
T3代码：
#include <bits/stdc++.h>#define maxm 500
using namespace std;
inline int read(){ // 读入优化（But没用啊QWQ）
int x = 0,f = 1; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') f = -1;c = getchar();}
while (c <='9' && c >='0') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int c[maxm+10][maxm+10],n,m; // 记录颜色和矩阵规模
int ans[maxm+10][maxm+10]; //ans数组
struct ZT{ int x,y,magic,cost;}; // 状态记录，见上分析
queue <ZT> Q; // STL队列
int tx[4] = { 0,-1,0,1},ty[4] = { -1,0,1,0}; // 坐标增量
bool Try(int x,int y){ // 一个小判断
return x<=m && y <= m && x>=1 && y >= 1;
}
int main(){
m = read(); n = read(); //读入
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= m; ++j)
c[i][j] = -1,ans[i][j] = -1;
for (int i = 1; i <= n; ++i){
int X = read(),Y = read(),C = read();
c[X][Y] = C; // 读入颜色
}
ZT tmp; tmp.x = 1; tmp.y = 1; tmp.cost = 0; tmp.magic=-1; //第一个状态
Q.push(tmp);
int Ans=-1;
while ( !Q.empty() ){ // 宽搜
tmp = Q.front();
if (tmp.x == m && tmp.y == m){ // 走到终点,更新Ans
if (Ans==-1) Ans = tmp.cost; else Ans = min(Ans,tmp.cost);
}
for (int i = 0; i <= 3; ++i){ // 四个方向
int nx = tmp.x+ tx[i],ny = tmp.y + ty[i];
if (Try(nx,ny)){ // 在棋盘中
if (c[nx][ny] != -1){ // 不用魔法
ZT New;
New.x = nx;New.y = ny; // 计算坐标
New.magic = -1; // 标记
New.cost = (c[tmp.x][tmp.y] == c[nx][ny]) ? tmp.cost : (tmp.cost+1); //计算花费
if (tmp.magic == c[nx][ny]) --New.cost; // 特判上一步有没有用魔法
if (New.cost<ans[nx][ny] || ans[nx][ny] == -1)Q.push(New);
if (ans[nx][ny] == -1) ans[nx][ny] = New.cost;//如果可以更新ans，就更新
else ans[nx][ny] = min(ans[nx][ny],New.cost);
}
else if (tmp.magic == -1){ // 用魔法，条件:上一步magic标记为-1
ZT New;//同理可得
New.x = nx;New.y = ny; //坐标
New.magic = c[tmp.x][tmp.y]; //颜色标记
magic New.cost = tmp.cost+2; // 花费
if (New.cost<ans[nx][ny] || ans[nx][ny] == -1) Q.push(New);
if (ans[nx][ny] == -1) ans[nx][ny] = New.cost; // ans的更新和记录
else ans[nx][ny] = min(ans[nx][ny],New.cost);
}//
}//
}//for循环结束
Q.pop();
}
printf("%d\n",Ans); // 输出
return 0;
}
顺便啰嗦几句……
NOIP居然考挂了，只有250（说好的300分呢）（手动滑稽）
T1 T2 T3 本来都会，结果T3写挂了（手动滑稽）
NOIP2017，再见！