NOIP2013提高组复赛day2试题解析
1.
解析：
对于一道题可以先模拟一下他的样例，通过模拟样例发现，总次数正好是每个数与前一个数的差之和，所以就可以得到O(n)复杂度的代码
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+39+7;
ll n,a[N],ans=0;
int main(){
// freopen("block.in","r",stdin);
// freopen("block.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)ans+=(a[i]>a[i-1]?a[i]-a[i-1]:0);
cout<<ans;
return 0;
}
举一反三：
-
P3078 [USACO13MAR] Poker Hands S
-
P5019 [NOIP2018 提高组] 铺设道路
这两道题和本题是一样的
2.
解析：
跟上一道题一样，先模拟数据，通过模拟数据发现，本题可转化为求解整数h1,h2,h3,.....,hn中转折点的个数，就得出代码了
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+39+7;
ll turn=1,h[N],n,ans=0;
int main(){
// freopen("flower.in","r",stdin);
// freopen("flower.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)cin>>h[i];
if(n==1){
cout<<1;
return 0;
}
ans=1;turn=h[1]<=h[2];
for(int i=1;i<=n;i++){
if(i==n&&!turn){
ans++;
continue;
}
if(turn){
if(h[i+1]<h[i]){
turn=0;
ans++;
continue;
}
}else{
if(h[i+1]>h[i]){
turn=1;
ans++;
continue;
}
}
}
cout<<ans;
return 0;
}
3.
解析：
如果使用复杂度为O(n^4)的bfs暴力处理，q一大会TLE，这道题可以转化为spfa求最短路的题目，使用mat数组记录地图，dis记录距离，step记录步数，然后使用O(n^4)的预处理，处理出step数组，
在求解答案时，使用spfa求解最短路，最短路的长度即为答案
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 35+39+7,INF = 0x3f3f3f3f,dx[]={0,0,-1,1},dy[]={-1,1,0,0};
int mat[N][N],dis[N][N][4],step[N][N][4][4],d[N][N],n,m,q,T,ex,ey,sx,sy,tx,ty;
struct node{
int x,y;
};
struct node2{
int x,y,k;
};
bool isok(int x,int y){
return (1<=x&&x<=n&&1<=y&&y<=m);
}
int spfa(){
queue<node2>q;
for(int k=0;k<4;k++){
if(dis[sx][sy][k]!=INF){
q.push((node2){sx,sy,k});
}
}
while(q.size()){
int x=q.front().x,y=q.front().y,k=q.front().k;q.pop();
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(isok(xx,yy)&&mat[xx][yy]&&step[x][y][k][i]!=INF){
if(dis[xx][yy][i^1]>dis[x][y][k]+step[x][y][k][i]+1){
dis[xx][yy][i^1]=dis[x][y][k]+step[x][y][k][i]+1;
q.push((node2){xx,yy,i^1});
}
}
}
}
int ans=INF;
for(int i=0;i<4;i++)ans=min(ans,dis[tx][ty][i]);
return (ans==INF?-1:ans);
}
int bfs(int sx,int sy,int tx,int ty){
if(!mat[sx][sy]||!mat[tx][ty])return INF;
memset(d,0x3f,sizeof(d));
d[sx][sy]=0;
queue<node>q;
q.push((node){sx,sy});
while(q.size()){
if(d[tx][ty]!=INF)return d[tx][ty];
int x=q.front().x,y=q.front().y;
q.pop();
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(isok(xx,yy)&&mat[xx][yy]&&d[xx][yy]==INF){
d[xx][yy]=d[x][y]+1;
q.push((node){xx,yy});
}
}
}
return INF;
}
void init(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int vis=mat[i][j];mat[i][j]=0;
for(int k=0;k<4;k++){
for(int l=0;l<4;l++){
step[i][j][k][l]=bfs(i+dx[k],j+dy[k],i+dx[l],j+dy[l]);
}
}
mat[i][j]=vis;
}
}
}
int solve(){
cin>>ex>>ey>>sx>>sy>>tx>>ty;
if(sx==tx&&sy==ty)return 0;
if(sx==ex&&sy==ey)return -1;
if(!isok(ex,ey)||!isok(sx,sy)||!isok(tx,ty))return -1;
if(!mat[ex][ey]||!mat[sx][sy]||!mat[tx][ty])return -1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<4;k++){
dis[i][j][k]=INF;
}
}
}
mat[sx][sy]=0;
for(int k=0;k<4;k++)dis[sx][sy][k]=bfs(ex,ey,sx+dx[k],sy+dy[k]);
mat[sx][sy]=1;
return spfa();
}
int main(){
cin>>n>>m>>T;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mat[i][j];
}
}
init();
while(T--)
cout<<solve()<<'\n';
return 0;
}