NIOP 09 题解

2009 NOIP 提高组题解

这次考试，呃，除了第一题就没怎么拿分。后面几道题都比较难想，想到了又不怎么写的出来，哎。

几道题总的难度都不是很大，总结最近几次做题来说，在图论上只是还是很欠缺，做题都不怎么会去想图论方面的知识，但其实只要能想到用图论知识的话最近的几道题都还是很好处理的。假期要在复习一遍图论了。

这次的题主要是读懂题。

T1 潜伏者 T2 Hankson的趣味题 T3 最优贸易 T4 靶形数独

额，该怎么判断怎么判断吧。旁边的cyy同学认为推出25个字母的密码可以自行推出最后一个，怎么说呢，他高估了竞赛题里面间谍的智商。加之题目中有说可能有重复的字母出现，哇，间谍你推过了字母你还能再用一次，哎，智商可想而知了，难保推完25个字母在推一次用过的字母。

想了很久，想的是分解质因数，然后依次相乘进行判断。嘛，思路是正确的。但这样做考虑的情况蛮多的，我是自最小依次向上乘上去的，还有就是多出来的数乘每个因子没有乘。这种还是应该多测试来以防万一。

比较难想，本来是说广搜前50%的点的，但广搜不知怎么就爆掉了，还有之前写的时候搞混了.pop 和 .front 这点需要注意。比较容易理解的方法的话就是Spfa求最大最小值(注意利用将图反向来求取)。

/*首先看题目以后我们知道这个题目一定是贪心，贪心的思路也很简单就是在最便宜的地方买商品在最贵的地方卖出去赚取差价，但是如果我们直接比较出最大值最小值做差是有问题的，当然不可能这个简单这个题目是当年的压轴题啊。这么简单怎么玩。【虽然实际上也不难】因为那个人在不断的往前面走并在前面买东西在后面卖，所以我就把原来的边拆了建在两个图上。把所有的边正向建一张图，然后把边反过来再建一次，这样我原来的图就有两个了，于是我在正向的图上跑一边SPFA**不断更新从1到该点的最小值然后我再在反向的图上面跑第二遍SPFA然后更新最大值**并且把每个点的最大值与最小值做差来更新答案。这样就是正确的姿势啦。
【证明】因为我们正向的跑了一边spfa更新最小值就相当于把起点到每个点的最小值求出来了，然后我第二遍spfa就做了两件事情第一个证明了连通性【因为我这个题目中有一些路是单向的，所以说可能某些点买的价格特别低或者特别高，但是我去的那儿是陷阱，你进去了就出不来了这样你的答案就是错的了，所以我把图反过来建这样你从终点可以反着跑到这个点也就代表这个点可以正着跑到终点，这就相当于证明了连通性】
第二个事情就是不断的货比三家，计算利润和差值。 */

是准备搞出数独再进行处理的，但惊讶的发现我填不来数独啊天。用excel填了半天果断还是放了。

看到做法有DFS的，还有用启发式搜索的，不过较为感兴趣的还是跳舞链求解数独，感觉好神奇的高级算法，看了半天没有看的懂，不过hzwer大神是用的DFS，说是时间很尴尬。

这次的题目总的来说并没什么特别上难度的题，但是这一年的题目还是很有借鉴意义的，因为题目普遍难懂（可能只是我的语文水平不咋滴），但还是反应出对知识理解的不透彻，不能很好的熟练应用。总的来说，还是要加强对题目的练习与理解，这也是不管学习什么都必须的。

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 string s1,s2,s3;
 5 char standard[110],ops[110];
 6 bool comp[50];
 7 int main()
 8 {
 9     freopen("spy.in","r",stdin);
10     freopen("spy.out","w",stdout);
11     cin >> s1 >> s2 >> s3;
12     for(int i=0;i<s1.size();i++){
13         if((comp[s2[i] - 'A'] && ops[s2[i] - 'A'] != s1[i]) || (standard[s1[i] - 'A'] && standard[s1[i] - 'A'] != s2[i])){
14             cout << "Failed"; return 0;
15         }
16         ops[s2[i] - 'A'] = s1[i];
17         comp[s2[i] - 'A'] = true;
18         standard[s1[i] - 'A'] = s2[i];
19     }
20     for(int i=0;i<26;i++) if(!comp[i]) {cout << "Failed"; return 0;}
21     for(int i=0;i<s3.size();i++){
22         cout << standard[s3[i] - 'A'];
23     }
24     return 0;
25 }

View Code

第二题被我吃了，不要问我为什么，我才不会告诉你们我穿了两个一模一样的错误代码回家，哼。

View Code

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define MAXN 500000
int n,m,e = 1,ans,head[MAXN][2],MAX[MAXN],MIN[MAXN],Data[MAXN];
bool inq[MAXN];
queue<int>q;
struct node{
    int v,next;
} edge[MAXN];
void addedge(int u,int v)
{
    edge[e].next = head[u][0];
    edge[e].v = v;
    head[u][0] = e++;
    edge[e].next = head[v][1];
    edge[e].v = u;
    head[v][1] = e++;
}
void spfa_1()
{
    q.push(1);
    inq[1] = true;
    MIN[1] = Data[1];
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        inq[x] = false;
        for(int i = head[x][0]; i; i = edge[i].next)
        {
            int v = edge[i].v;
            if(MIN[v] > MIN[x] || MIN[v] > Data[v])
            {
                MIN[v] = min(MIN[x],Data[v]);
                if(!inq[v]) q.push(v),inq[v] = true;
            }
        }
    }
}
void spfa_2()
{
    q.push(n);
    inq[n] = true;
    MAX[n] = Data[n];
    ans = max(ans,MAX[n] - MIN[n]);
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        inq[x] = false;
        for(int i = head[x][1]; i; i = edge[i].next)
        {
            int v = edge[i].v;
            if(MAX[v] < MAX[x] || MAX[v] < Data[v])
            {
                MAX[v] = max(MAX[x],Data[v]);
                ans = max(MAX[v] - MIN[v],ans);
                if(!inq[v]) q.push(v),inq[v] = true;
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++)
        scanf("%d",&Data[i]), MIN[i] = 105;
    int u,v,k;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d%d%d",&u,&v,&k);
        addedge(u,v);
        if(k == 2) addedge(v,u);
    }
    spfa_1();
    memset(inq,0,sizeof(inq));
    spfa_2();
    printf("%d
",ans);
    return 0;
}

View Code

#include<iostream>
#include<cstdio>
#define searchnext(x,y) y==9? search(x+1,1):search(x,y+1)
using namespace std;
bool r[10][10],l[10][10],s[10][10];//行，列，小九宫格
int a[10][10],b[10][10];
int ans=-1,score;
int getscore(int x,int y,int k)
{
    if(x==5&&y==5)return 10*k;
    else if(x>=4&&x<=6&&y>=4&&y<=6)return 9*k;
    else if(x>=3&&x<=7&&y>=3&&y<=7)return 8*k;
    else if(x>=2&&x<=8&&y>=2&&y<=8)return 7*k;
    else return 6*k;
}
bool fillin(int x,int y,int k)
{
    if(r[x][k])return 0;
    if(l[y][k])return 0;
    if(s[(x-1)/3*3+(y-1)/3+1][k])return 0;
    b[x][y]=k;
    r[x][k]=l[y][k]=s[(x-1)/3*3+(y-1)/3+1][k]=1;
    score+=getscore(x,y,k);
    return 1;
}
void del(int x,int y,int k)
{
    b[x][y]=0;
    r[x][k]=l[y][k]=s[(x-1)/3*3+(y-1)/3+1][k]=0;
}
void search(int x,int y)
{
    if(x==10&y==1)
    {
        ans=max(ans,score);
        return;
    }
    if(b[x][y])searchnext(x,y);
    else
        for(int i=1; i<=9; i++)
        {
            int t=score;
            if(fillin(x,y,i))
            {
                searchnext(x,y);
                del(x,y,i);
                score=t;
            }
        }
}
int main()
{
    for(int i=9; i>0; i--)
        for(int j=9; j>0; j--)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j])fillin(i,j,a[i][j]);
        }
    search(1,1);
    printf("%d",ans);
    return 0;
}

View Code