noip2009提高组题解,卖萌是没有用的

2019-11-08 作者:奥门金沙手机娱乐网址   |   浏览(108)

 

            然而这样会超时,codevs上可以过但是最慢的点用了2400多ms,时限4秒。

 

 

第四题谜面:

图片 1

http://goo.gl/Z0U4p renumber digits rub ink long hiatus big redskin damp heat calming moon third felon neutral pink technical flyer robs enemy sea honour saintly chef two cents old enchanter sparkle biz crocus fiord dusty brown ruby queen rich garcons sardine gland sans broker hated seaman not tensely gloved barker noted cavern evilest trooper scarlet esquire educators role manly beer carrot nubs thinks bigger hawthorn holler nocturnal howls diurnal gripes mad realtor gas alternate civil oratory orange press english carol tallest peahen rare lotus clan idol concerning torment darn heel

这个还真长,你不会真读了吧……

先来看上面的网址,这个网址指向了一幅恶搞版的“世界地铁网络图”,这和最上面那几个彩色的数字怎么能结合起来呢?坐过地铁就知道,换乘站普遍会用多种线路标志色来表示——于是做个大胆的猜测:数字圈的配色实际上是对应换乘站,而数字即换乘站名的字母序号。

图片 2

查看大图请点这里

比如,第三个色圈,配色是粉、黄、灰,于是找到图中这三个颜色的换乘站:Berlin,取第6个字母N。以此类推,就得到了六个色圈暗藏的单词:

LONDON

伦敦?这又在暗示什么呢?其实,如果你对英国有所了解就会知道,伦敦的地铁系统异常的庞大,共有12条线路和300多个车站,连伦敦地铁图都成为了信息设计的典范。而之前的这幅“世界地铁网络图”正是一幅翻版的伦敦地铁图:

图片 3

如此繁多、且无一重复的站名(全表见 wiki页面 ,共306个)不正是绝好的字符加密素材么?这好比给本就精力无限的Geek们打了一针鸡血。那就赶紧来配对吧!这个荒谬的想法还真有人这么做了,当然,他用的是程序……

可怕的事终于发生了!程序匹配的结果表示,这就是正确解题思路!简单讲,谜面中的每对词组都是伦敦某地铁站名字母的重排列,唯一的不同是,出题人在每对词组中刻意隐去了一个字母……

举个例子:谜面第7组词“third felon”对应“Northfields”车站,并隐去了最后的字母“s”,所以第7组取“S”,以此类推完成44次匹配,并把字符串加上空格、标点,谜底揭晓:

Please send me a Nexus S, so Google goodies I can access!(送我台Nexus S尝点Google的甜头嘛~)

 

还真是肉麻又隐晦的一句话啊,这不就是撒娇卖萌吗,但这是没有用的,一样把你推倒。

题目大意:给出一段密文和破译后的明文,一个字母对应一个密文字母,要求破译一段密文,如果有矛盾或有未出现密文无法破译输出failed,否则输出明文。

第一题谜面:

3154, 75757, 854, 2737, 37553, 15059, 6278, 4085, 3634, 2414, 46483

是不是冷到了?可能是因为反响不热烈,开题后很久又给出了一条提示:”start with the prime factors and see where they take you”。居然是求质因数!@#$%^&*

那就开始吧,3154=2×1577=2×19×83,此时2、19、83都是质数,即完成了质因数分解,以此类推,可以将全部数都解开。

但类似 [2,19,83 ] 的东西怎么变成真正的谜面呢?就用加密的鼻祖凯撒加密法试试好了,把 A-Z 的字母拿来和前26个质数一一对应的替换(2对A,3对B,5对C……101对Z),于是谜面就成了这样:

[a, h, w], [e, t, y], [a, d, r], [d, g, i], [g, o, o], [e, l, l], [a, n, u], [c, h, n], [a, i, v], [a, g, t], [i, n, o]

这一堆字母又是什么意思呢?那个”goo”是不是提醒到了啥?只要字母调整下位置就出现了真正的谜面:

what year did google launch navigation(Google 啥时推出了导航服务?)

于是谜底来了:

2009

 

第三题谜面:

图片 4

 

哈,这不就是填字游戏一样的字谜么?先解开再说:

图片 5

但怎么用这些词呢?注意到谜面的颜色没有,这不就是Google那套“蓝红黄,蓝绿红”配色嘛……

图片 6

于是我们就用这个配色规律在每个谜底里选择一个字母,比如:“Folks”的谜底PEOPLE,蓝色,对应了“Google”中的“G”,也就是“Google”的第1、第4个字母,对应回“PEOPLE”,就得到“P”,以此类推,我们就有了谜底:

图片 7

Viva!这个词我太熟了,意思是“棱镜”,哼哼哼,晕了没?

AC代码:

Google 前些日子启动了第二届 Nexus S 解迷挑战赛(Nexus S Challenge 2),虽然又把中国大陆排除在比赛之外,但还是不影响我们自娱自乐, 点这里查看官方规则 。

 

废话少说,直接开始解题吧。

  这样的话,显然就可以枚举b1的所有因数,sqrt(b1),加上gcd复杂度是logb1,所以单组数据复杂度是sqrt(b1)*log2(b1).

 

思路:解法肯定还是一样的,dfs。然后比较分数大小输出最大的。

 

 2017.5.6补充题解:

  然后就各种焦虑,物色到了一个超级有道理的题解:

 ----------------------------------------------------------

  今天又做了一遍,然后对上面自己的做法一脸懵逼,估计是之前就没看懂吧然后贴了题解???

 

由此,可以求出对于每一个质数,x可能含有几个它,并求出一共有多少种选择方式。然后根据乘法原理,将每一个质数的选择方案数乘起来,就得到了答案。

题目大意:解一个多解数独,从内向外分数不同,求分数最大的解法。

T1:潜伏者

 

T4:靶形数独

思路:纯模拟题

题目大意:给出a0,a1,b0,b1求满足条件的x的个数;

 

#include <iostream>

using namespace std;



int num[100000];

int map[1000000],nxt[1000000];

int las;

int head[100000];

int map2[1000000],nxt2[1000000];

int las2;

int head2[100000];



void adad(int a,int b)

{

    map[las]=b;

    nxt[las]=head[a];

    head[a]=las++;

}



void adad2(int a,int b)

{

    map2[las2]=b;

    nxt2[las2]=head2[a];

    head2[a]=las2++;

}



#define Q_MAX 100000

int used[100000];

int queue[Q_MAX];

int h,r;



void enq(int k)

{

    if (used[k])

        return;

    used[k]=1;

    queue[r]=k;

    r=(r+1)%Q_MAX;

}



int exq()

{

    int t;

    t=queue[h];

    used[t]=0;

    h=(h+1)%Q_MAX;

    return t;

}



int minn[100000];

int maxn[100000];



int main()

{

    int i,j;

    int n,m;

    int a,b,c;

    cin >> n >> m;

    for (i=0;i<n;i++)

         {

        head[i]=head2[i]=-1;

        maxn[i]=-100000;

        minn[i]=0xFFFFFFF;

        cin >> num[i];

    }

    for (i=0;i<m;i++)

         {

        cin >> a >> b >> c;

        a--,b--;

        if (c==2)

                   {

            adad(a,b);

            adad(b,a);

            adad2(a,b);

            adad2(b,a);

        }

                   else

                   {

            adad(a,b);

            adad2(b,a);

        }

    }

    minn[0]=num[0];

    enq(0);

    while (h!=r)

         {

        i=exq();

        for (a=head[i];a!=-1;a=nxt[a])

                   {

            j=map[a];

            if (minn[j]>minn[i])

                            {

                minn[j]=minn[i];

                enq(j);

            }

            if (minn[j]>num[j])

                            {

                minn[j]=num[j];

                enq(j);

            }

        }

    }

    maxn[n-1]=num[n-1];

    enq(n-1);

    while (h!=r)

         {

        i=exq();

        for (a=head2[i];a!=-1;a=nxt2[a])

                   {

            j=map2[a];

            if (maxn[j]<maxn[i])

                            {

                maxn[j]=maxn[i];

                enq(j);

            }

            if (maxn[j]<num[j])

                            {

                maxn[j]=num[j];

                enq(j);

            }

        }

    }

    for (i=a=0;i<n;i++)

        if (a<maxn[i]-minn[i])

            a=maxn[i]-minn[i];

    cout << a << "n";

    return 0;

}
#include<iostream>

#include<cmath>

using namespace std;



int h[10]={},hs[10]={},zs[10]={},xj[5][5]={},hq[10]={};

int ans=-1,st[10],a[10][10];



void make()

{

         int i,j,sum=0;

         for (i=1;i<5;i++)

         {

                   for (j=i;j<11-i;j++)

                            sum+=(a[i][j]+a[10-i][j])*(5+i);

                   for (j=i+1;j<10-i;j++)

                            sum+=(a[j][i]+a[j][10-i])*(5+i);

         }

         sum+=a[5][5]*10;  

         if (sum>ans)

                   ans=sum;

}



void dfs(int k)

{

         if (k==10)

                   make();

         else

         {

                   int x,y,j,pos,p,i=st[k];

                   x=511-h[i];

                   y=x&-x;

                   h[i]|=y;

                   j=(int)log2(y)+1;

                   pos=511-(hs[i]|zs[j]|xj[(i-1)/3][(j-1)/3]);

                   while (pos>0)

                   {

                            p=pos&-pos;

                            pos-=p;

                            a[i][j]=(int)log2(p)+1;

                            hs[i]|=p;

                            zs[j]|=p;

                            xj[(i-1)/3][(j-1)/3]|=p;

                            if (x==y)

                                     dfs(k+1);

                            else

                                     dfs(k);

                            hs[i]-=p;

                            zs[j]-=p;

                            xj[(i-1)/3][(j-1)/3]-=p;

                   }

                   h[i]-=y;

         }

}



int main()

{

         int i,j,p0;

         for (i=1;i<10;i++)

                   for (j=1;j<10;j++)

                   {

                            cin >> a[i][j];

                            if (a[i][j]>0)

                            {

                                     h[i]|=1<<(j-1);

                                     p0=1<<(a[i][j]-1);

                                     if (((hs[i]&p0)!=0)||((zs[j]&p0)!=0)||((xj[(i-1)/3][(j-1)/3]&p0)!=0))

                                     {

                                               cout << "-1n";

                                               return 0;

                                     }

                                     hs[i]|=p0;

                                     zs[j]|=p0;

                                     xj[(i-1)/3][(j-1)/3]|=p0;

                            }

                            else

                                     hq[i]++;

                   }

         for (i=1;i<10;i++)

                   st[i]=i;

         for (i=1;i<9;i++)

                   for (j=i+1;j<10;j++)

                            if (hq[st[i]]>hq[st[j]])

                            {

                                     st[i]^=st[j];

                                     st[j]^=st[i];

                                     st[i]^=st[j];

                            }

         i=1;

         while (hq[st[i]]==0)

                   i++;

    dfs(i);

         cout << ans << "n";

         return 0;

}

本文由奥门金沙网址发布于奥门金沙手机娱乐网址,转载请注明出处:noip2009提高组题解,卖萌是没有用的

关键词: