NOIP2009题解

大家好，欢迎来到IT知识分享网。

spy：
题目大意：给定一串加密信息和原信息，让你求出该加密信息是否满足26个字母都存在，且加密信息中每个字母在原信息中对应不同的字母，原信息中的每个字母在加密信息中对应不同的字母，若不满足输出Failed，否则翻译指定的加密信息。字符串长度<=100.
题解：一道简单的字符串模拟题……看懂题目就好了，值得注意的是在样例中没有加密信息中的每个字母在原信息中对应不同的字母，题目看清楚了则无大碍。时间复杂度：O(len*26)，空间复杂度：O(len)。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
int i,n1,n2,n3,j;
char s1[110],s2[110],s3[110],a[30];
bool f[30];
int main(){
    freopen("spy.in","r",stdin);
    freopen("spy.out","w",stdout);
    scanf("%s",s1);
    scanf("%s",s2);
    scanf("%s",s3);
    n1=strlen(s1);
    n3=strlen(s3);
    for(i=0;i<n1;i++)f[s2[i]-'A']=1;
    for(i=0;i<26;i++)
        if(!f[i]){
            puts("Failed");
            return 0;
        }
    for(i=0;i<n1;i++)
        if(!a[s1[i]-'A'])a[s1[i]-'A']=s2[i];
        else
         if(a[s1[i]-'A']!=s2[i]){
            puts("Failed");
            return 0;
         }
    for(i=0;i<25;i++)
        for(j=i+1;j<26;j++)
            if(a[i]==a[j]){
                puts("Failed");
                return 0;
            }
    for(i=0;i<n3;i++)putchar(a[s3[i]-'A']);
    return 0;
}

son：
题目大意：对于n组数据求满足与a0的最大公因数为a1，与b0的最小公倍数是b1的数的个数。n<=2000，a0,a1,b0,b1<=2*1e9.
题解：
显然x是b1的约数a1的倍数吧……
一开始还以为这题很神……要用什么高超的方法……然而……
某道叫反质数的省选题可以证明b1的约数个数不会大于3000……这里就不写证明了……
于是我们只需要找出所有b1的约数，再一个个判断即可……
那么我们只需要O($\sqrt{b1}$)求出所有质因数，再枚举每个质因数需要选多少个，得到所有约数即可。
时间复杂度：O($2^{log b1}$*n)，空间复杂度：O(约数个数)。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
int pri[1010],i,j,n,a0,b0,a1,b1,a[1010],w,x[1000010],ans;
inline void chai(int x){
    for(int i=2;(long long)i*i<=x;i++)
        if(!(x%i)){
            pri[++a[0]]=i;
            while(!(x%i))a[a[0]]++,x/=i;
        }
    if(x>1)pri[++a[0]]=x,a[a[0]]=1;
}
inline int gcd(int x,int y){
    while(y){
        int t=x%y;
        x=y;
        y=t;
    }
    return x;
}
void dfs(int i,int j){
    if(i>a[0]){
        x[++w]=j;
        return;
    }
    dfs(i+1,j);
    for(int k=1;k<=a[i];k++){
        j*=pri[i];
        dfs(i+1,j);
    }
}
int main(){
    freopen("son.in","r",stdin);
    freopen("son.out","w",stdout);
    scanf("%d",&n);
    for(;n;n--){
        scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
        memset(a,0,sizeof(a));
        w=0;
        ans=0;
        chai(b1);
        dfs(1,1);
        for(i=1;i<=w;i++)
            if(gcd(x[i],a0)==a1&&(long long)x[i]*b0/gcd(x[i],b0)==b1)ans++;
        printf("%d\n",ans);
    }
    return 0;
}

trade：
题目大意：有n个城市，有些城市之间有有向边，有些城市之间有无向边，每个城市对水晶球有一个固定价格，你现在需要找到一条从1~n的路从i买入从j卖出(j可以等于i)求卖出价-买入价最大值。n<=100000，m<=500000.
题解：
很显然我们可以用一遍最短路得到从1~i的最小价对吧？只需把最短路中的d[i]=d[pos]+a[i][pos]改为d[i]=min(d[pos],a[i])即可。同理，我们只需将边反向，即可得到i~n的最大价格，于是，我们对于所有的i，只需要用卖出价-买入价即可。
其实这相当于是在求一个前缀最小值和后缀最大值……只不过是在图上求，于是我们将普通的序列上的求法改为最短路即可……时间复杂度：O(n log n+m log m)，空间复杂度：O(m log m)。
sudoku：
题目大意：一个靶形数独，上面已经填了若干个数，越接近靶心的数分值基数越高，一个数填进去的分值为该数*分值基数，求填完数独的最大分值和，若数独无解输出-1。已填的数不少于24个。
题解：
对于这种题目，最直观的想法自然是爆搜……枚举每个还没填数的格子填什么数，然后一直搜下去即可……如果这么正着搜的话只有70分……倒着搜有90分（倒着搜的分数高是因为出题人的疏忽……）
正确的做法应该这么玩……
首先想想我们自己玩数独的时候会怎么操作？
显然是先去那些已填的数最多的九宫格、行、或列开始填数对吧？
但是我们没法每填一个数就判断一下还没填的数应该填哪一个……（这个其实我们可以用IDA*解决，但这里不讲）于是我们只能先预判一下哪些数要先填。
然后枚举填什么数的话可以用位运算加速处理。这样的话就可以解决了。时间复杂度：O(9^（81-2*n))，空间复杂度：O(n)。

//位压+按每行每列每九宫格需要填的数的个数排序 
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
int sodu[9][9]={
  
  {
  
  1,1,1,2,2,2,3,3,3},
                {
  
  1,1,1,2,2,2,3,3,3},
                {
  
  1,1,1,2,2,2,3,3,3},
                {
  
  4,4,4,5,5,5,6,6,6},
                {
  
  4,4,4,5,5,5,6,6,6},
                {
  
  4,4,4,5,5,5,6,6,6},
                {
  
  7,7,7,8,8,8,9,9,9},
                {
  
  7,7,7,8,8,8,9,9,9},
                {
  
  7,7,7,8,8,8,9,9,9}},
    pnt[20][20],i,j,a[20][20],ans,n,cnt,h[20],l[20],s[20],hang[20],lie[20],sod[20];
struct node{
    int x,y;
    bool friend operator <(node a,node b){
        if(hang[a.x]==hang[b.x]){
            if(lie[a.y]==lie[b.y])return sod[sodu[a.x][a.y]]<sod[sodu[b.x][b.y]];
            return lie[a.y]<lie[b.y];
        }
        return hang[a.x]<hang[b.x];
    }
}nd[60];
bool flag;
void dfs(int k,int now){
    if(!k){
        ans=max(ans,now);
        flag=1;
        return;
    }
    int x=nd[k].x,y=nd[k].y;
    for(int i=1;i<=9;i++)
        if(h[x]&l[y]&s[sodu[x][y]]&1<<(i-1)){
            h[x]^=1<<(i-1);
            l[y]^=1<<(i-1);
            s[sodu[x][y]]^=1<<(i-1);
            dfs(k-1,now+pnt[x][y]*i);
            h[x]^=1<<(i-1);
            l[y]^=1<<(i-1);
            s[sodu[x][y]]^=1<<(i-1);
        }
}
int main(){
    freopen("sudoku.in","r",stdin);
    freopen("sudoku.out","w",stdout);
    for(i=0;i<9;i++)
        for(j=0;j<9;j++)
            pnt[i][j]=min(min(i,8-i),min(j,8-j))+6;
    for(i=0;i<9;i++)h[i]=l[i]=(1<<9)-1;
    for(i=1;i<10;i++)s[i]=(1<<9)-1;
    for(i=0;i<9;i++)
        for(j=0;j<9;j++){
            scanf("%d",&a[i][j]);
            if(a[i][j]==0)nd[++n].x=i,nd[n].y=j;
            else h[i]^=1<<(a[i][j]-1),l[j]^=1<<(a[i][j]-1),s[sodu[i][j]]^=1<<(a[i][j]-1),cnt+=pnt[i][j]*a[i][j],hang[i]++,lie[j]++,sod[sodu[i][j]]++;
        }
    ans=cnt;
    sort(nd+1,nd+1+n);
    dfs(n,ans);
    if(!flag)puts("-1");
    else printf("%d",ans);
    return 0;
}