河南理工大学18级算法协会招新赛(第二场)非官方题解

我校oj：HPUOJ
本场招新赛：河南理工大学18级算法协会招新赛(第二场)

A. wzy学长温暖的签到题

题目描述

单测试点时限: 1.0 秒

内存限制: 256 MB

每位ACMer（JBer）都是从a+b开始的！
作为本场比赛的良心出题人，怎么能忘记出a+b这么经典的题目呢？
请作为ACMer的你来尝试解决它吧！

输入
单组输入
每行输入两个实数a，b（用空格隔开）

输出
输出a+b的结果（结果保留两位小数）

样例
input
1 1
output
2.00
input
1.555 1.001
output
2.56
提示
0≤a,b≤100
请使用double定义变量，并使用%lf输入和输出

题意分析

这道题确实没有什么难得，简单的a+b，很多人也都a了，提示写的明明白白(wzy学长是真的可爱

代码实现

#include<stdio.h>
int main()
{
    double a,b;
    scanf("%lf %lf",&a,&b);
    printf("%.2lf\n",a+b);
    return 0;
}

B. 分糖果

题目描述

单测试点时限: 2.0 秒

内存限制: 512 MB

Codancer 现在有n颗糖果，现在他要把这n颗糖果全部分给两个小朋友Dicer和thelittleboy,已知第i颗糖果能够使小朋友的开心值增加i,为了不让两个小朋友争吵，他必须使两个小朋友最终的开心值的差值最小化，现在Codancer很头疼，请你快来帮帮他吧QAQ。

输入
单组输入
输入一个数n,代表codancer的糖的数量。
(1≤n≤1000000000)

输出
输出两个小朋友的开心值的最小差值

样例
input
3
output
0
input
1
output
1

题意分析

输入一个数n，题意就是把从1-n个数分成两组让他们的和的差最小。这道题我看到第一感觉就是找规律，其实规律无非也就哪几种。这道题我们可以列出来几个情况求出来答案来找规律
1 2 3 4 5 6 7 8

糖果数量  分配方案    最小差值
1         1    0        1
2         1    2        1
3         1，2     3       0
4         1，4     2.3     0
5         1，2，5    3，4    1
6         1，2，3，5    4，6   1
7         1，2，5，6    3，4，7    0
8         4,6,8    1,2,3,5,7    0

现在看起来规律就很明显了，1，1，0，0，1，1，0，0......
在找规律的过程中我发现从1到n的和如果是偶数，最小差值就是0，如果是奇数，最小差值就是1.于是我直接定义了一个求和函数后判断奇偶，直接T了。。。其实可以发现1100是四个一组出现的，直接n对4求余判断余数就好了。

代码实现

#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    if(n%4==0||n%4==3)
    puts("0");
    else
    puts("1");
    return 0;
}

有些题掌握了规律实现起来就会很简单。
(什么时候codancer能给我们发糖吃呢

C. 中位数

题目描述

单测试点时限: 2.0 秒

内存限制: 512 MB

给出一个1−n的排列，统计该排列有多少个长度为奇数的连续子序列的中位数是k。中位数是指把所有元素从小到大排列后，位于中间的数。
接下来一行n个数代表这个排列。

输入
单组输入
一行两个数n,k代表排列的长度以及中位数。(1≤n≤100000,1≤k≤n)

输出
输出满足条件的区间个数。

样例
input
7 4
5 7 2 4 3 1 6
output
4
提示
样例解释：满足条件的区间为{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}。

题意分析

这道题刚看见以为是很简单的一道题，WA了几次之后才发现并不简单。最后好像也没几个人做出来这道题。学长讲的时候也没听懂。。咳咳，确实挺难。这两天为了更好的帮(ceng)助(re)大(du)家，这几天也是一直在搞这道题。不断地查阅资料，现在也差不多是搞懂了，快点来帮(ceng)助(re)大(du)家。
参考于：洛谷P1627题解
中位数说明这个区间内大于他的数的数量与小于他的数的数量相等。且这个题中符合题意的区间顺序是必须与输入一样的，不能更改。
先找到中位数的位置标记一下，然后输入的同时对每一个数进行判断，大于中位数的标记为1，小于中位数的标记为-1。然后从中位数的左边开始第一次循环，对标记求和，如果有和为0的情况（即大于中位数的数的数量与小于中位数的数量相等），即说明这是一个符合题意的区间。接着对右边开始第二次循环，与第一次循环相等的步骤，但是要多一步，就是要考虑中位数位于区间中间（不是两端）的情况。具体可以在代码中解释。最后得到的答案还要加一，因为中位数自己一个区间也是可以的。

代码实现

#include<bits/stdc++.h>
using namespace std;
int a[100050],flag[100050],f[200050];
const int key=100000;
int main()
{
    int n,k,bj,s,ans;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]==k)        bj=i;
        else if(a[i]>k)        flag[i]=1;
        else     flag[i]=-1;
    }//进行标记
    s=ans=0;
    for(int i=bj-1;i>=1;i--)
    {
        s+=flag[i];
        f[s+key]++;//用一个f数组来记录s为为-1，0，1时候的个数
        if(s==0)    ans++;
    }
    s=0;
    for(int i=bj+1;i<=n;i++)
    {
        s+=flag[i];
        if(s==0)    ans++;
        ans+=f[-s+key];//中位数在区间中的情况。
    }
    ans+=1;
    cout<<ans<<endl;
    return 0;
}

咳咳，可以对着样例和代码自己跑一遍可以加深一下理解。

D. 打麻将

题目描述

单测试点时限: 2.0 秒

内存限制: 512 MB

打麻将实在是太有趣了，不知道大家过年的时候有没有打麻将呢？

我是十分喜欢打麻将的，但是因为我不够聪明，所以我经常会诈胡(不具备胡牌的条件而胡牌)，因此我希望你能帮我判断一下我当前的手牌是否符合胡牌的条件。

为了简化这个问题，我们规定胡牌的条件如下：

你必须有且仅能有一个对子(即两张相同的牌)。
除了那个对子之外，其他的都是刻子(3张相同的牌)。(刻子的数量可以为0)
我们用两个字符表示一张麻将：

B，T, W 分别表示牌的种类为 筒子，条子，万子 。(可能你不知道这是什么意思，不过没有关系，你只需要知道这三种类型的牌是互不相同的。)
数字1~9表示牌上的数字。
另外用HZ，FC，BB，EE，WW，SS，NN 来分别表示除了 筒子，条子，万子 以外的 红中，发财，白板，东风，西风，南风，北风 。
对于两种牌来说，只要表示它们的两个字符中第一个字符或第二个字符任意一个不同，那么它们就是不同的牌，每种牌最多只有四张。(例如：B1 和 B2，B1 和 T1,HZ 和 FC 都是不同的。)
输入
第一行是一个数字T，表示你需要判断的次数。(1 \leq T \leq 10000)
接下来2*T行，前一行是一个数字 n 是你的手牌数，2≤n≤14，接下来一行有 n 对字符，每一对字符代表你的一张手牌。
保证不会有未知的牌型，不会有任何一种牌出现超过四次，但是你的手牌数因为某种原因可能会是正常出牌不能出现的个数。
输出
如果可以胡牌请输出 YES，否则输出 NO 。

样例
input
3
14
B1 B1 B1 T1 T1 T1 W1 W1 W1 HZ HZ HZ WW WW
2
BB BB
7
BB BB B1 B1 B1 B2 B2
output
YES
YES
NO

题意分析

题面看起来很长，但是我们需要学会如何找到有用的信息。这道题我们需要知道的就是我们手中的牌只能有一种是出现了两次，别的牌出现的只能是三次。思路一清晰实现起来就会简单点了。这道题如果按我的方法的话希望大家补一下相关的知识：基础容器之map以及c++中的string(用char数组应该也是可以的，但是string会方便一些)类型。更详细的解释我会加在代码里。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s[15];
    int n,a;
    cin>>n;
    map<string,int> ma;
    while(n--)
    {
        ma.clear();//因为是多组输入，所以每次开始时都需要将map清空，避免干扰到下一次的判断。
        int flag=1;
        cin>>a;
        for(int i=0;i<a;i++)
        {
            cin>>s[i];
            ma[s[i]]++;
        }
        map<string,int>::iterator it;
        for(it=ma.begin();it!=ma.end();it++)
        {
            if(it->second==1||it->second==4)
            {
                flag=0;
                break;
            }//如果有出现一次的或者出现四次的，肯定不能胡牌。
            if(it->second==2)
                flag++;//判断出现两次的牌的数量。
        }
        if(flag==2)//因为flag定义时的赋值是1，所以如果现在的值是2则说明出项两次的牌（字符串）只有一个，符合条件，可以胡牌。否则就不能胡牌。
        puts("YES");
        else
        puts("NO");
    }
    return 0;
}

(咳咳，我还是个麻将“高手”呢，

E. 假票

题目描述

单测试点时限: 2.0 秒

内存限制: 512 MB

春天到了，万物复苏，乍暖还寒。H城为了庆祝春天的到来，将要举办一场盛大的舞会。

由于舞会非常的盛大，H城许多的居民都想参加舞会，但是舞厅大小有限，只能容纳n个人，为了防止到时候位置不够，人太拥挤，H城城主决定在舞会开始前进行售票。城主规定，每个人只能买一张票，每张票都会有其固定的编号（1~n）。但是有一个人，由于没抢到票，居然制造了一张与真票一模一样的假票！城主知道这个消息后，当然不能允许这种行为，因此就派出他最信任的大臣你去找出制造假票的人。

输入
多组输入，处理到文件结束

第一行两个数n,m (1<=n<=10000,0<=m<=n+1)，表示总共售出n张票，编号为 1 ~ n，m表示舞会当天到场的人数（注意：由于有些人可能当天有事来不了，这种情况下你可能找不到制造假票的人）。

接下来一行m个数a1,a2,.....,am，表示检票口收到的所有票的编号。

输出
如果能找到假票，则输出假票编号，否则输出-1。

样例
input
5 6
3 1 4 2 3 5
5 3
1 2 4
output
3
-1

题意分析

这个题还是比较容易读懂的，就是让你输出一组数中出现了两次的数。我一开始用的是先排序然后判断每一项与它后面那一项是否相等来判断是否有出现两次的，如果有，就将这个数输出，没有就输出-1，但是不知道为什么会WA，于是又改用了map，还好最后过了。

补题

排序的那种方法也是可以的，只不过因为是多组输入，因为第一次的输入票的数量如果比第二次输入的多，此时就可能会存在数组中还依然存在着一些上一组的数据，导致结果错误。参考我之前的错误代码发现其中判断是否相等的时候多循环了一次——最后一次，这就会导致WA了。改一下就行了。代码请看下面。（感谢学长哈）

这题我跟小伙伴讨论之后发现用set也是可以的，比较前后的和的大小即可，有兴趣的可以自己实现一下。

代码实现

#include<bits/stdc++.h>
using namespace std;
int a[10050];
int main()
{
    map<int,int> ma;
    int n,m,b;
    while(~scanf("%d %d",&n,&m))
    {
        bool flag=1;
        ma.clear();
        while(m--)
        {
            cin>>b;
            ma[b]++;
        }
        map<int,int>::iterator it;
        for(it=ma.begin();it!=ma.end();it++)
        {
            if(it->second==2)
            {
                cout<<it->first<<endl;
                flag=0;
                break;
            }
        }
        if(flag)
        cout<<"-1"<<endl;
    }
    return 0;
}



#include<bits/stdc++.h>
using namespace std;
int a[10050];
int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        int ans=-1;
        for(int i=0;i<m;i++)
        {
            cin>>a[i];
        }
        sort(a,a+m);
        for(int i=0;i<m-1;i++)
        {
            if(a[i]==a[i+1])
            {
                ans=a[i];
                break;
            }
        }
        if(ans!=-1)
        cout<<ans<<endl;
        else
        puts("-1");
    }
    return 0;
}

F. 字符串博弈

题目描述

单测试点时限: 2.0 秒

内存限制: 512 MB

一天Codancer和Todest玩游戏。现在有一个由大写字母组成的字符串s，Codancer和Todest轮流进行一下操作：
如果存在i使得s[i]=s[i+1],就可以把这两个字符从s中删除。比如原本s为ABBA,现在可以把BB删除，此时s就变为AA。
如果一方不能再执行此操作时，该方即为败者。现在Codancer先手，判断Codancer能否获胜。

输入
单组输入
输入字符串s。1≤|s|≤10000

输出
如果Codancer能够获胜输出”YES”,否则输出”NO”。(不加引号)。

样例
input
ABBA
output
NO

题意分析

我对这道题的理解就是将字符串中相邻且相同的两个字母消掉，消到不能再消，统计消除的次数就是能进行的回合数，再对回合数的奇偶进行判断就可以了。但是消除的实现还是用栈（不会的可以补一下知识，这个我的博客中也有相关的文章不过是偏实用性（就是只讲了几种函数的用法）的）比较轻松。关于栈的传送门：Uncle_drew最帅

代码实现

#include<bits/stdc++.h>
using namespace std;
char s[10005];
int main()
{
    stack<char> sta;
    cin>>s;
    int a=0;
    for(int i=0;i<strlen(s);i++)
    {
        if(i>0)
        {
            if(sta.top()==s[i])
            {
                sta.pop();
                a++;
                continue;
            }
        }
        sta.push(s[i]);
    }
    if(a%2==0)
    puts("NO");
    else
    puts("YES");
}

(Todest很帅的，小学妹们抓住机会，ε=ε=ε=┏(゜ロ゜;)┛

G. 小w的过路费(暂无)

H. 超级简单的斐波那契数列

题目描述

单测试点时限: 1.0 秒

内存限制: 256 MB

众所周知，斐波那契数列又称黄金分割数列，由数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入

斐波那契的通项公式为：

计算斐波那契的第n项是一件容易的事，但是如果给出第n项的斐波那契数num，你能反推出n吗？

试一试吧！

输入
第一行一个整数T (0≤T≤100)，表示测试组数。
之后的T行，每行一个斐波那契数num (num≠0,1)

输出
对于每个测试数据，输出一行表示数num是斐波那契数列的第几项

样例
input
2
2
5
output
3
5
提示
保证num在斐波那契数列的前200000项中

题意分析

一开始我看错题，以为是数列的最大值不超过200000.。。。直接交了3次，WA了3次。。。所以说看题还是很重要的。我们昨天也都听学长说了，斐波(肥波)那契数列第50项已经爆了unsigned long long了。所以我们直接存是不现实的，这时候就需要存储的时候对其取模然后存储，并且用map存储一下每个值对应的斐波(肥波)那契数列的项数。因为输入的数会很大，所以我们需要用到字符串输入，然后用到一个很XX的东西——对字符串表示的大数取模。

代码实现

对用字符串输入的大数取模(感谢学长！

        cin>>s;
        ll ans,num;
        ll l=strlen(s);
        num=0;
        for(ll i=0;i<l;i++)
        {
            num=num*10+s[i]-'0';
            num%=maxx;
        }//num就是这个大数取模之后的结果。

//这道题比赛的时候我是没写出来的，赛后补题。学会了大数取模屁颠屁颠的跑去交题
#include<bits/stdc++.h>
using namespace std;
const int maxx=1e9+7;
typedef long long ll;
ll f[200050];
char s[100000];
int main()
{
    map<ll,ll> ma;
    f[0]=0;
    f[1]=1;
    for(ll i=2;i<200001;i++)
    {
        f[i]=(f[i-1]+f[i-2])%maxx;
        ma[f[i]]=i;
    }//对斐波(肥波)那契数列进行取模存储
    ll n;
    cin>>n;
    while(n--)
    {
        cin>>s;
        ll ans,num;
        num=0;
        for(ll i=0;i<strlen(s);i++)
        {
            num=num*10+s[i]-'0';
            num%=maxx;
        }
        cout<<ma[num]<<endl;        
    }
    return 0;
}
//然后TLE了。。。观察一下(hao jiu)代码会发现我在大数取模的for循环里面每次都对s的长度重新求一次，这样是很耗费时间的，自然会tle，改一下就好


#include<bits/stdc++.h>
using namespace std;
const int maxx=1e9+7;
typedef long long ll;
ll f[200050];
char s[100000];
int main()
{
    ios::sync_with_stdio(false);
    map<ll,ll> ma;
    f[0]=0;
    f[1]=1;
    for(ll i=2;i<200001;i++)
    {
        f[i]=(f[i-1]+f[i-2])%maxx;
        ma[f[i]]=i;
    }
    ll n;
    cin>>n;
    while(n--)
    {
        cin>>s;
        ll ans,num,l;
        l=strlen(s);//先把长度求出来，用的时候直接用
        num=0;
        for(ll i=0;i<l;i++)
        {
            num=num*10+s[i]-'0';
            num%=maxx;
        }
        cout<<ma[num]<<endl;        
    }
    return 0;
}
取模的部分也可以这样写
        for(ll i=0;i<s.length();i++)
        {
            num=num*10+s[i]-'0';
            num%=maxx;
        }

I. 斐波那契（非递归）

题目描述

单测试点时限: 2.0 秒

内存限制: 512 MB

请输出斐波那契的第n项

输入
多组输入处理到文件结束，每组输入一个数n。1≤n≤10000

输出
输出第n个斐波那契数对109+7取模的结果

样例
input
3
4
output
2
3

题意分析

简单的斐波(肥波)那契数列问题，与J题差不多，不过加了取模。直接代码就行了。

代码实现

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e9+7;
ll f[10005];
int main()
{
    f[0]=0;
    f[1]=1;
    for(int i=2;i<10001;i++)
    {
        f[i]=f[i-1]+f[i-2];
        f[i]=f[i]%maxn;
    }//打表
    int a;
    while(~scanf("%d",&a))
    {
        cout<<f[a]<<endl;
    }
    return 0;
}

J. 斐波那契数列

题目描述

单测试点时限: 2.0 秒

内存限制: 512 MB

请输出斐波那契的第n项

输入
单组输入
每组输入一个数n。0≤n≤10

输出
输出斐波那契数列的第n项

样例
input
0
output
0
input
1
output
1

题意分析

妥妥的签到

代码实现

#include<stdio.h>
int a[15];
int main()
{
    int n;
    scanf("%d",&n);
    a[0]=0;
    a[1]=1;
    for(int i=2;i<=10;i++)
    {
        a[i]=a[i-1]+a[i-2];
    }//打表
    printf("%d\n",a[n]);
    return 0;
}

咳咳，写这个“题解”，我是为了帮助同学，没有骗访问量没有没有。有不懂的可以直接qq我或者网页右下角有一个可以实时联系我的小框框你们可以直接跟我聊天，看见就会回复的，有什么不同的想法和思路可以在评论区发表一下意见，毕竟不是官方题解，考虑的可能不周全莫名其妙的a题，集思广益。