wzy的大冒险——出发前的清理

Description:
由于上次学弟们没有ak，导致许多蚂蚁被留下了。wzy在出发冒险前请来了一只食蚁兽帮忙清理。
现在出现了一只食蚁兽。每个蚂蚁都有wzy给它的一个编号，食蚁兽要吃蚂蚁必须要确认蚂蚁的编号X是否满足要求，如下：

X的质因子的种类不超过13种
X的食蚁数是个素数(食蚁数的定义见最下方提示)
X的食蚁数是个回文数
如果都满足则输出 YES ,否则输出 NO

输入格式
第一行给定一个T,(1≤T≤1e5)
接下来T行，每行给出数字X,(1≤X≤1e17)

输出格式
每行输出 YES 或者 NO

样例
input
3
121666
111666
1312333
output
NO
NO
YES
提示
补充：

1. 回文数至少为两位数，如 131 、 22
2. 如果X的长度为 len1 ，令 len2=⌊len12⌋，则 X 的前 len2 位形成的数是它的食蚁数

Problem solving:
挺好的一道题，但是我没做出来，先放上学长代码把，以后会了在补上思路。

Code:

//---JQM---//
//#pragma GCC optimize(3)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int MAXN = 1e7+7;

int prime[MAXN];
int visit[MAXN];
void Prime(){   //网上随便找了个素筛板子，好像visit[i]==0表示素数（为什么两个数组不反过来用
    memset(visit,0, sizeof(visit));
    memset(prime, 0, sizeof(prime));
    for (int i = 2;i <= MAXN; i++) {
        // cout<<" i = "<<i<<endl;
        if (!visit[i]) {
            prime[++prime[0]] = i;      //纪录素数， 这个prime[0] 相当于 cnt，用来计数
        }
        for (int j = 1; j <=prime[0] && i*prime[j] <= MAXN; j++) {
            visit[i*prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

char s[20];
char w[20];

int main()
{
    Prime();
    int i, k, flag, n;
    ll a, b;
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%lld", &a);
        if(a<=1000) //食蚁数长度在两位及以上，所以a的长度在四位及以上
        {
            printf("NO\n");
            continue;
        }
        b = a;
        k = 0;
        flag = 1;
        while(b)  //统计a的长度并且转换为字符串
        {
            s[k++] = b%10;
            b/=10;
        }
        n = k;  //长度
        if(n>=16)   //a长度为16、17位，食蚁数长度为8位；或者a==100000000000000000，食蚁数==100000000
        {
            printf("NO\n");
            continue;
        }
        for(i=0; i<k/2; i++)  //取食蚁数字符串
            w[i] = s[k-i-1];
        k/=2;   //k为食蚁数位数
        if(!(k%2))   //一个回文数如果位数为偶数位那么它一定不是素数（11除外）
        {
            if(a/100==11 || a/1000==11) printf("YES\n");
            else printf("NO\n");
            continue;
        }
        for(i=0; i<k/2; i++)  //检查回文串
        {
            if(w[i] != w[k-i-1])
            {
                flag = 0;
                break;
            }
        }
        n = a/pow(10, n-k);
        if(flag && !visit[n]) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

wzy的大冒险——出发咯QAQ

Description:
wzy踏上了冒险的旅程。
现在他从地精手里买了一份地图，地图上有n个城镇。
他从第一个城镇出发，走向（没钱只能走）第n个城镇，现在，请你帮wzy找到一条最短的路径，并倒序（从n到1）输出一条最短路径。
举个栗子:如果有两条路径6 4 3 1和6 5 2 1，我们选择6 4 3 1这条。
地精小提示：路是单向的QAQ。

输入格式
第一行两个数n,m ，(1≤n≤1e3,1≤m≤1e3)

接下来m行，每行三个数x,y,z，表示点 x 与点 y 之间有一条权值为 z 的有向边 (1≤x,y,z≤1e3).

输出格式
第一行一个整数表示 1 到 n 的最短距离；
第二行倒序输出这条路径。

input
5 7
1 2 69
1 3 87
1 4 79
2 5 94
2 3 10
3 5 79
4 5 43

output
122
5 4 1

Problem solving:
这道题题意就是给你一个图的信息，让你求出最短路径的长度以及最短路。

这道题我就是直接套的最短路的板子，但是板子里面没有记录路径，我就想到了离散数学讲到的最短路径的输出使用一个f数组记录，试了一下，还真过了。
其实就是记录一下，然后输出的时候是一个查找的过程，可以看代码注释。

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
const int INF=0x3f3f3f3f;
int a[maxn][maxn],dis[maxn],f[maxn];
bool vis[maxn];
int n,m,u,v,w;
struct node{
    int d,id;
};
bool operator<(node a,node b)
{
    return a.d>b.d;
}
priority_queue<node> q;
void solve()
{
    for(int i=1;i<=n;i++)    dis[i]=INF;
    dis[1]=0;
    q.push(node{dis[1],1});
    while(!q.empty())
    {
        node p=q.top();
        q.pop();
        int mid=p.id;
        if(vis[mid]==1)    continue;
        vis[mid]=1;
        for(int i=1;i<=n;i++)
        {
            if(dis[i]>dis[mid]+a[mid][i])
            {
                dis[i]=dis[mid]+a[mid][i];
                f[i]=mid;//这就是记录路径所用到的数组
                q.push(node{dis[i],i});
            }
        }
    }
    cout<<dis[n]<<endl;
}
int main()
{
    cin>>n>>m;
    f[1]=1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)    a[i][j]=INF;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        a[u][v]=w;
    }
    solve();
    cout<<n<<" ";
    while(f[n]!=n)//输出最短路径所用到的查找
    {
        cout<<f[n]<<" ";
        n=f[n];
    }
}

wzy的大冒险——数学王国

Description:
wzy这一次来到了数学王国，加号国王为了考验他，找来了一个数字n，告诉了wzy这个数字的阶乘的末尾零的个数Q，猜错的话就要把wzy赶出去。现在请你帮帮wzy求这个数最小为多少。
若不存在输出"impossible"(输出不带引号)。

输入格式
输入数据包含T组(1≤T≤10000)
每一组数据包含一个数字Q (0≤Q≤1e8)

输出格式
对于每一组数据请输出这个数字n,否则输出"impossible"(输出不带引号)。

样例
input
3
1
2
5

output
5
10
impossible

input
1
10000000
output
40000010

Problem solving:
这道题题意就是给你一个数n，让你求是否存在一个数，它的阶乘后面有n个0.
这个问题很经典了，就是看这个数里面有几个5，因为出现0的话只有2*5才会出现，而2的个数有很多，所以说出现5的个数就是0的个数。
这道题用到的是二分，我觉得这道题挺好的

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF= 0x3f3f3f3f;
ll solve(ll x)
{
    ll ans=0;
    while(x)
    {
        ans+=x/5;
        x/=5;
    }
    return ans;
}
int main()
{
    ll n,a;
    cin>>n;
    while(n--)
    {
        cin>>a;
        ll ans=INF;
        ll l=5,r=INF,mid;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(solve(mid)==a)
            {
                ans=min(ans,mid);
                r=mid-1;
            }
            else if(solve(mid)>a)
            {
                r=mid-1;
            }
            else    l=mid+1;
        }
        if(ans==INF)    puts("impossible");
        else
        cout<<ans<<endl;
    }
}

wzy的大冒险——a+b问题

Description:
每个ACMer都是从a+b问题开始的，今天wzy翻到了他的第一个a+b程序，并想让你来输出它

include

int main()
{
int a,b;
scanf("%d %d",&a,&b);
int c=a+b;
printf("%d\n",c);
return 0;
}
输入格式
本题无输入

输出格式
将上面代码输出
Problem solving:
一道签到题，注意输出的时候里面有些神奇的地方需要注意一下。
Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    puts("#include<stdio.h>");
    puts("int main()");
    puts("{");
    puts("int a,b;");
    puts("scanf(\"%d %d\",&a,&b);");
    puts("int c=a+b;");
    puts("printf(\"%d\\n\",c);");
    puts("return 0;");
    puts("}");
}

wzy的大冒险——炉石传说

Description:
wzy 来到了炉石传说的世界。
他发现他现在有n个攻击力为ai的随从，每个随从只能攻击一次。
对面的boss有m个血量为bi的具有嘲讽的随从（嘲讽即为你必须先把这些怪物击败才可攻击boss）。
当我方随从攻击力大于等于敌方随从血量时，敌方随从死亡。
由于boss的强力技能，对方的随从只能受到一次攻击，受到攻击后无法再一次受到攻击。(你无法使两个随从都攻击对方的同一个的随从)。
wzy必须先干掉对方的所有随从才能使用剩下的随从攻击boss本身。
对方boss有k的血量，现在请问wzy能否干掉敌方boss回归现实世界？

输入格式
第一行为三个数n，m，k。n 为wzy拥有的随从数量，m为boss拥有的随从数量，k为boss血量。
第二行为n个数，分别是wzy随从的攻击力;
第三行为m个数，分别是boss随从的血量。
以上数据范围均在[1,100]范围内

输出格式
如果胜利输出Win，否则输出Lose

样例
input
4 3 2
2 4 6 8
3 5 7
output
Win

Problem solving:
这道题的意思就是给你你的仆从的攻击力以及boss的仆从的攻击力，攻击力大的能杀死攻击力小的，问你最后剩下的仆从是不是能击败boss。每个普通都只能被击败一次，打boss的时候可以上多个仆从。

简单的模拟一下即可。把用来打败怪物的仆从标记一下，然后看标记的个数与boss仆从的个数是否相等，并看未标记的仆从的攻击力与boss血量的大小关系。然后就可以输出了。

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int a[maxn],b[maxn];
int main()
{
    int n,m,k,ans=0;
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)    cin>>a[i];
    for(int i=0;i<m;i++)    cin>>b[i];
    sort(a,a+n),sort(b,b+m);
    int pos=0,flag=0,s=0;
    for(int i=0;i<m;i++)
    {
        while(a[pos]<b[i])
        {
            pos++;
            if(pos>=n)
            {
                    s=1;break;
            }
        }
        if(s)    break;
        a[pos]=0;
        flag++;
    }
    for(int i=0;i<n;i++)    ans+=a[i];
    if(ans>=k&&flag==m)    puts("Win");
    else    puts("Lose");
}

wzy的大冒险——接龙红包

Description:
最近QQ更新了一个新的功能–“接龙红包”，会长作为算协的土豪，便开始在群里发红包,wzy总是抢的又快又准，现在他开始研究成语接龙的奥秘。
现在QQ的词库里面有n种成语，每种成语由一个只由小写字母组成的字符串表示，现在wzy发现了一个问题，如果有个同学说了一个成语，但是在词库里找不到可以接在它后面的成语（即找不到一个成语的首字母和该成语的尾字母相同），这样的成语被称为死局成语，现在zy想知道在词库里面有多少这样的死局成语。

输入格式
第一行输入n，接下来n行每行输入一个字符串代表一个成语s。
(1≤n≤100,1≤|s|≤20)

输出格式
第一行输出死局成语的个数m。
接下来m行每行输出一个死局成语，输出顺序应和输入顺序保持一致。

样例
input
3
aaa
bab
abc
output
1
abc
input
3
a
b
c
output
0
提示
一血通过本题奖励5毛红包(手动滑稽)。
Problem solving:
接龙红包，就是看每个字符串的最后一个字母有没有在第一个位置出现过。简单模拟一下，让当前的字符串的最后一个字母分别于所有字符串的第一个字母比较，如果出现相等的就直接判断下一个。复杂度是N^2，但是题目的数据范围也很小，不用考虑超时。

Code:

#include<bits/stdc++.h>
using namespace std;
string s[105];
int main()

{
    int n,ans=0,flag=0;
    cin>>n;
    queue<string> que;
    for(int i=0;i<n;i++)    cin>>s[i];
    for(int i=0;i<n;i++)
    {
        flag=0;
        char mid=s[i][s[i].size()-1];
        for(int j=0;j<n;j++)
        {
            if(s[j][0]==mid)
            {
                flag=1;
                break;
            }
        }
        if(flag)    continue;
        ans++;
        que.push(s[i]);
    }
    cout<<ans<<endl;
    while(!que.empty())
    {
        cout<<que.front()<<endl;
        que.pop();
    }
}

大树的水塘

Description:
那一天，世界上所有的人类都……变成了石头！

3700年后，千空和大树从石头中苏醒过来，但是世界发生了翻天覆地的变化，人类文明已经不复存在

天才少年千空立志用自己的科学知识在这个「石之世界」中重建文明

为了生存，淡水是必不可少的，每次都用海水进行蒸馏会比较麻烦，所以千空决定让大树建造一个水塘来存储雨水

水塘建造在一个无限长，高度不超过100，宽度为1的峡谷里，所以只需要往里面填石头，即可达到蓄水的目的

当大树建造好水塘让千空去检查的时候，千空一口老血喷了出来：因为大树是一个体力笨蛋，所以建造的水塘底部是参差不齐的，这使得建造蓄水相同体积的水塘，大树多用了好多石头

已知每块石头中的规格是1×1×1，水塘的长度为N，宽度为1，在第i位置，大树放了ai个石头

设大树建造的水塘蓄水量为V

请你求出在长度和宽度不变的情况下，建造一个蓄水量不小于V的水塘最多可以节约多少石头

输入格式
单组输入

第一行一个数N (1≤N≤1e7)表示水塘的长度

第二行有N个非负数xi (0≤xi≤100)，表示第i个位置上放的石头数

输出格式
输出有两行

第一行输出大树建造的水塘的蓄水量V

第二行输出最多可以节约多少石头

样例
input
5
2 1 3 1 3
output
3
8
提示
大树的水塘长这样：

最节约石头的水塘长这样：

Problem solving:
这道题看提示应该就能明白了。就是宽度是固定的为1，然后告诉你每个地方石头的高度，问你它的存水量以及能节省的最大的石头数。

这道题我们可以直接考虑每个位置的蓄水量然后累加。找到当前位置左右两边分别能达到的最高的位置，两个最高位置的最小值减去当前位置的高度就是当前位置可以达到的蓄水量。但是1e7的数据，如果直接暴力N^2的复杂度，两秒也会超时。所以我们可以构建一个前n项最大值的数组和后n项最大值的数组，然后以O(N)的复杂度处理这个问题。

这个数组跟前缀和数组是一种思想，因为当我们计算当前位置的蓄水量的时候所需要的时从当前位置分别到最左端和最右端的最大值，现在假设l[i]是前n个数的最大值，r[i]存的是后n个数的最大值，那么i位置两边所能达到的最大高度就是l[i]和r[i]。所以当前位置的蓄水量v就等于v=min(l[i],r[i])-a[i]，a[i]就是当前位置的高度。

蓄水量求出来了，节省的最多的石头个数也就简单了。这也有一点贪心的思想，我们只在两边放石头，中间全部用来存水。求出这种情况下需要的石头个数，用之前的石头的总个数减去这个需要的石头个数就是最大能节省的石头个数。

还有一个坑点就是计算需要石头的个数的时候别忘了向上取整。

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e7 + 10;
ll       a[maxn], l[maxn], r[maxn];
int main()
{
    ll n, sum = 0;
    scanf("%lld", &n);
    for (ll i = 0; i < n; i++)
    {
        scanf("%lld", &a[i]);
        sum += a[i];
    }
    l[0] = a[0]; r[n - 1] = a[n - 1];
    for (int i = 1; i < n; i++)
        l[i] = max(l[i - 1], a[i]);
    for (int i = n - 2; i >= 0; i--)
        r[i] = max(a[i], r[i + 1]);
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
            ans += min(l[i], r[i]) - a[i];
    }
    int ans2 = ceil(ans * 1.0 / (n - 2));
    printf("%d\n%d", ans, sum - ans2 * 2);
}

这道题卡了我2个小时也没做出来，后来才知道题意理解错了，我。。。

幸运素数

Description:
跳皮筋 我第一，马兰开花二十一；

二五六 二五七，二八二九三十一；

三五六 三五七，三八三九四十一；

......

童谣《马兰花》作为建国以来最大的数学难题，里面数字的含义困扰了全国人民几十年，并且一直未解

难道这些数字真的只是为了押韵生搬硬凑的数字吗？

并！不！是！

经过wzy的多年研究，他发现了里面潜藏的惊天大秘密（并没有）：

28=256，而257是离256最近的素数

28是第二个完美数，29是离28最近的素数

31是第四个幸运素数

仅仅这一句话中，就出现了二进制、素数、完美数、幸运数！

这哪里是童谣？这分明就是中国版的达芬奇密码！

今天wzy就来考考你《马兰花》里出现的数学知识：

幸运数是经由类似埃拉托斯特尼筛法的演算法后留下的整数集合，是在1955年波兰数学家乌拉姆提出。

由一组由1开始的数列为例：

1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25, …
先将所有偶数删去，只留下奇数：

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25,…
然后把数列中的第 2 个数字(设该数字为 x )的倍数对应的数删除，即把所有第 nx,x∈Z+ 个数删除，例如上述例子中，第 2 数字是 3 ，所以删去所有第 3n 个数：

1, 3, 7, 9, 13, 15, 19, 21, 25,…
新数列的第 3 项(每次都加上 1 )为 7 ，因此将新数列的第 7n 个数删除：

1, 3, 7, 9, 13, 15, 21, 25,…
若一直重复上述的步骤，最后剩下的数就是幸运数

（以上内容来自维基百科幸运数）

我们将既是幸运数又是素数的数叫做幸运素数

现在给你一个数N，请判断N是否是一个幸运素数

输入格式
第一行一个数T，代表有T个数(1≤T≤2×1e5)

第1∼T行，每行一个正整数N(1≤N≤2×1e5)

输出格式
对于每个输入的数N，如果N是幸运素数，输出Yes，否则输出No

样例
input
3
1
2
3
output
No
No
Yes
Problem solving:
这道题的难点就在于模拟那个幸运数的生成过程吧。涉及到删除操作，本来我也想到用标记解决，但是没实现出来，就放弃了。

看了学长代码。发现学长用了vector来写，因为vector中有个函数叫erase。还是很方便的。

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
vector<int> ve;
int vis[maxn],via[maxn];
void init()//生成幸运数
{
    ve.push_back(0);
    for(int i=1;i<maxn;i+=2)
        ve.push_back(i);
    int res=ve[2];
    int len=ve.size(),cnt=2;
    while(res<=len)
    {
        for(int i=1;i*res<=len;i++)
            ve[i*res]=0;
        for(auto it=ve.begin()+1;it!=ve.end();)
        {
            if(*it==0)  it=ve.erase(it);
            else    it++;
        }
        len=ve.size();
        if(res==ve[cnt])
            cnt++;
        res=ve[cnt];
    }
    for(int i=0;i<ve.size();i++)
        via[ve[i]]=1;
}
void init2()//素数打表
{
    vis[0]=vis[1]=1;
    for(int i=2;i<=maxn;i++)
    {
        if(!vis[i])
        for(int j=2;j*i<=maxn;j++)
            vis[i*j]=1;
    }
}
int main()
{
    init();init2();
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        if(!vis[n]&&via[n])
            puts("Yes");
        else
            puts("No");
    }
}

NO GAME NO Life

Description:
空白，永不败北！

作为世界的唯一神灵，游戏之神特图的日常就是改变自己的外表，在世界各地游荡

在被空和白在一次网上的国际象棋比赛击败后，他以拯救人类种的名义将兄妹二人召唤到迪斯博德

来到迪斯博德的空白，常常因为在游戏上找不到对手而感到无聊

在风和日丽的一个下午，空白出门视察国情，在路上偶遇了扮成人类种闲逛的特图，特图为了打发时间，决定向空白发起挑战，游戏内容如下：

在一棵有着N个节点的树上，第i个节点上有xi颗钻石，由最先开始的一方选择一个节点进行标记，标记完成后，双方轮流进行如下操作：拿走标记节点的一颗钻石，并将标记移至与当前节点直接相连的节点，至到出现无法拿石子的一方停止。

空白兄妹听完游戏规则后，立刻做出了回应，但前提是空白作为先手选择节点

特图自认为这是一个特别公平的游戏，所以就答应了这个要求

每当一棵树出现后，空白凭借超人的数学能力，能够在一秒内快速判断出能否获胜

输入格式
单组输入，第一行一个正整数N (2≤N≤1e6)，表示这棵树有N个节点

第二行有N个正整数xi (1≤xi≤100)，表示i节点上有xi颗钻石

接下来N−1行，每行两个整数x,y (1≤x,y≤N)，表示节点x与节点y相连

输出格式
如果空白可以获胜，输出Blank

否则输出Teto

样例
input
2
1 1
1 2
output
Teto
input
2
1 2
1 2
output
Blank

Problem solving:
这道题的意思就是有一个树，每个节点都有一个值代表这个地方的硬币个数，先手的那个人选择一个节点并拿走一枚硬币，然后下一个人就需要从这个节点能直接到达的节点拿走一颗硬币，最后无法再拿硬币的人获胜。

这算是个思维题把，学长不讲也想不到原来是这样写的，就是如果每个节点d的值都相等的话，先手是必败的，反之先手必胜。

Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a,sum,u,v,flag=0,now;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a);
        sum+=a;
        if(!i) now=a;
        else if(a!=now)
            flag=1;
    }
    for(int i=0;i<n-1;i++)
    {
        scanf("%d %d",&u,&v);
    }
    if(!flag)    puts("Teto");
    else    puts("Blank");
}