NOIP PJ 2017 解题报告

Start

---

模拟测试:[https://www.luogu.org/contestnew/show/4468]

哇，幸亏普及组只有一天，要是提高组我怕是心态已经炸了23333 反正现在的局面很尴尬，因为大家的分数貌似差别都不大

T1 成绩

---

题目是真的水，不过出题人貌似还是给你了个坑(我差点就掉进去了 这个坑就是int的精度问题，估计dalao最容易死在这 直接上

#include <cstdio>
using namespace std;
int main(){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    int cnt=a/10*2+b/10*3+c/10*5;
    printf("%d",cnt);
}

T2 图书管理员

---

至少在我眼里是到水题，数据范围那么小懒得写power，直接打表 当然能力次点的到底这么看的我就不知道了

#include <cstdio>
#include <algorithm>
using namespace std;
int mmp[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
//真 - 打表
int a[1100],b[1100][2];
int main(){
    int n,p;
    bool x;
    scanf("%d%d",&n,&p);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<p;i++) scanf("%d%d",&b[i][0],&b[i][1]);
    sort(a,a+n);//排序写起来方便点
//反正数据范围比较小
    for(int i=0;i<p;i++){
        x=false;
        for(int j=0;j<n;j++){
            if(a[j]%mmp[b[i][0]]==b[i][1]){
                       printf("%dn",a[j]);
                x=true;
                break;
            }
        }
        if(!x) printf("-1n");
    }
}

T3

---

T3写了好几种，基本上都炸，最后骗-1

2017.12.16 更新 最近学了会宽搜，发现宽搜还算简单的 直接上代码

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1<<27;
const int MAX_M=101;
const int MAX_N = 1001;
int chess[MAX_M][MAX_M];//棋盘，1代表红色，2代表黄色
int d[MAX_M][MAX_M]; //每个点到起点[1,1]的代价
int dx[]={0,-1,0,1,0};
int dy[]={0,0,1,0,-1};
int m; //棋盘实际的行和列
int n; //有颜色的个数
struct point{
    int x,y;
    int f_x,f_y; //来自哪个坐标
    int d; //距离起点的代价
};
queue<point> que; //bfs所需
bool inchess(int x,int y)
{
    if(x>=1&&x<=m&&y>=1&&y<=m)
        return true;
    return false;
}
//判断从点(p.x,p.y)到点(x,y)的代价
int getcost(int x,int y,point p)
{
    int f_x = p.x,f_y=p.y;
    if(chess[x][y]==0 && chess[f_x][f_y]==0) //都是空白
        return -1; //不可达
    if(chess[x][y]==0) return 2;
    if(chess[x][y]==chess[f_x][f_y]) return 0; //颜色相等
    if(chess[x][y]!=chess[f_x][f_y] && chess[f_x][f_y]!=0) return 1;
    if(chess[f_x][f_y]==0 && chess[x][y] != chess[p.f_x][p.f_y]) return 1;
    return 0;
}
int main()
{
    int ans=MAX;
    cin>>m>>n;
    for(int i=1;i<=m;i++) {fill(d[i],d[i]+m+1,MAX);fill(chess[i],chess[i]+m+1,0);}
    for(int i=1;i<=n;i++){
        int x,y,c;
        cin>>x>>y>>c;
        chess[x][y] = c+1;
    }
    point p,p2;
    p.x =1; p.y=1; p.f_x=0;p.f_y=0; p.d = 0;
    que.push(p);
    d[1][1]=0;
    while(!que.empty()){
        p = que.front(); que.pop();
        if(p.x==m && p.y==m ){
            if(p.d<ans) ans=p.d;
            continue;
        }
        int x,y;
        for(int i=1;i<=4;i++){
            x=p.x+dx[i]; y=p.y+dy[i];
            if(inchess(x,y) && !(x==p.f_x && y==p.f_y)){
                 int cost = getcost(x,y,p);
                 if(cost==-1) continue;
                 p2.x=x; p2.y=y; p2.f_x=p.x; p2.f_y=p.y;
                 p2.d = p.d+cost;
                 if(p2.d<d[x][y]) {
                    d[x][y]=p2.d;
                     que.push(p2);
                }
            }
        }
    }
    if(ans!=MAX)     cout<<ans;
    else cout<<-1;
    return 0;
}

T4

---

T4直接骗-1 ~ 实际上T3那几种方法方法都比骗分拿的分高 ~

End

---

愿图灵祝我一力

]]>