河南科技大学萌新训练赛题解（更新中）

1002 生不逢七

//只要在第一轮进行判断要报的数字是否合法，之后对轮数进行循环。
///在每次循环中要对将要报的数字的每一位进行判断，如果有7，则输出p，否则输出a+n。
//如果没有7，则输出a+n
void solve() {
    int n, a, k;
    cin >> n >> a >> k;

    a++;//当前玩家的初始数字为上一名玩家的数字加1
    int ge = a % 10;//上一名玩家报数的个位数
    int shi = a / 10;//上一名玩家报数的十位数
    if (ge == 7 || shi == 7 ||a%7==0) {
        cout << 'p' << " ";//当前玩家将要报的数字个位数含有 7 或者是 7 的倍数时，输出p
    }
    else {
        cout << a << " ";//当前玩家将要报的数字为上一名玩家的数字加1
    }

    k--;//轮数减一

    while (k--) {//循环剩下的轮数
        a += n;//a有可能超过100，所以要循环取模
        if (a % 7 == 0) {
            cout << 'p' << " ";//当前玩家将要报的数字是 7 的倍数时，输出p
        }
        else {
            int num = a;
            bool flag = false;//标记是否有7
            while (num) {//循环判断是否有7
                int ge = num % 10;
                if (ge == 7) {
                    cout << 'p' << " ";//当前玩家将要报的数字个位数含有 7 或者是 7 的倍数时，输出p
                    flag = true;
                    break;//退出循环
                }
                num /= 10;
            }
            if (!flag) {
                cout << a << " ";//当前玩家将要报的数字为上一名玩家的数字加n
            }
        }
    }
    cout << endl;
}

1003子序列的权值最小值

对于这个数组中的一个数的一个二进制位，我们想让这一位是0的话只要存在有一个其他数的这一个二进制位是0就可以了，而不管有多少数的这一个二进制位是1也没有用，所以我们将所有的数进行与运算一遍，让我们的每一个二进制位都尽可能的出现0，就能得到最小值。
关于位运算

1004 魔导师晨拥

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10;
int hp[N];
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>hp[i];
    int sum=0,atack=2;//总伤害和现在技能伤害 
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(hp[j]>0)//如果还没死 
            {
                hp[j]-=atack;
                if(hp[j]==0)//恰好死技能伤害加一 
                atack++;
            }
        }
        sum+=atack;//英雄受到伤害 
    }
    cout<<sum<<endl;
    return 0;
}

1005 走廊的灯

根据题意我们要找的连续序列可以分为两种情况：

不包含熄灭（0）着的灯的连续序列
不包含亮（1）着的灯的连续序列

两种情况取max即可

#include<bits/stdc++.h>
#define long long int 
using namespace std ;
const int N  = 1e6+10 ;
int INF = 0x3f3f3f3f3f3f3f3f;
int T = 1 ;
int ans = 0 ;
int n ;
string s ;
void solve(){
    cin >> n ;
    cin >> s ;
    ans = -INF ;
    int cnt1 = 0 ;//用来表示不包含灭着的灯的序列的长度
    int cnt2 = 0 ;
    for(int i = 0 ; i < s.size() ; ++ i){
        //不包含灭着的灯（0）
        if(s[i] == '1' || s[i] == '2'){//连续
            cnt1++;
        }else{//遇到不合法字符（0）序列中止
            ans = max(ans,cnt1) ;//记录这一次序列的长度，判断是否是最大值
            cnt1 = 0 ;//归0，重新开始计算长度
        }
        //不包含亮着的灯
        if(s[i] == '0' || s[i] == '2'){
            cnt2++;
        }else{//遇到不合法字符（1）序列中止
            ans = max(ans,cnt2) ;//记录这一次序列的长度，判断是否是最大值
            cnt2 = 0 ;//归0，重新开始计算长度
        }
    }
    //循环结束，判断末尾的连续的合法序列（如果存在）的长度是否是最大值，
    //因为我们最后的连续合法序列不会因为遇到不合法字符而终止，也就是说还没有归0，没办法在循环中用我们末尾的合法序列的长度对我们的最大值进行更新，所以要在循环外再来更新一次
    ans = max(ans,cnt1) ;
    ans = max(ans,cnt2) ;
    cout << ans <<endl ;

}
signed main(){
    cin >> T ;
    while(T --){
        solve() ;
    } 
}

1006 组队

根据题意，我们先让每一个人之间能力值在数组相邻之间差值最小，即对于能力值进行排序（小到大，大到小都可以），依次有序地将元素放入双端队列中，若头尾相差大于k，则去掉队头(注意这里，不一定之去掉一次队头)，循环的每一次最后都用队列长度来更新最大值即可。

1007 小苯的好数组

题目给你一串长度为n的数组，让你从中选择一个子序列(注释1)将按升序排序，并且这串排列好的序列和原来排列前的子序列不完全相等呢么这串子序列就是一个好数组，比如说[1,3,2,1]这串序列我们可以发现只要有一个逆序对（注释2）出现，那么这整个数组就可以进行升序排序并且排序好的序列一定和原来的序列不相等，这正好符合题目对好数组的定义。

注释1：子序列的定义：子序列就是在原来序列中找出一部分组成的序列（子序列不一定连续）
注释2：如果存在正整数i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则这个有序对称为A的一个逆序对，也称作逆序数。

1008 小竹关禁闭

根据题意，我们对于每一个数有两种选择，选或不选。

当我们选择第i个物品时，因为我们不能让我们想要选择的数无法被选择，所以我们上一次选的数只能在1····（i-k-1）中选择，所以得到递推方程就是
```
dp[i] = dp[i-k-1] + a[i]
```
当我们不选择第i个物品时，直接继承上一次的选择即可。
```
dp[i] = dp[i-1]
```
最终得到递推方程
```
dp[i] = max(dp[i-k-1] + a[i],dp[i-1]) 
```
1012 交换数字

1015 音标

直接模拟即可，又因为题目有多行输入所以要用while (scanf("%s", str))来循环读入每一行的字符串。

ps：很多人可能没看到'y'在题目中也是元音

s[i] == 'a' ··· 'd' ，s[i] = 'a'\\
s[i] == 'e' ··· 'h' ，s[i] = 'e' \\
s[i] == 'i' ··· 'n' ，s[i] = 'i' \\
s[i] == 'o' ··· 't' ，s[i] = 'o' \\
s[i] == 'u' ··· 'x' ，s[i] = 'u' \\
s[i] == 'y' ··· 'z' ，s[i] = 'y' \\

1016 tb的字符串问题

这道题目需要用到了一个栈的数据结构，栈的基本操作有push、pop、top、empty，大家可以自己去了解一下。
题目要求删掉所有的"fc"和"tb"子字符串。我们很容易想到通过遍历来实现，遇到"fc"和"tb"就缩短字符串长度，
但是有一个问题，如果遇到"ffcfcc"这样的字符串，我们删掉中间的两个"fc"后，字符串就变成了"fc"。仍然可以删掉，
因此我们使用栈来记录当前的状态，遇到"fc"和"tb"时，我们判断栈顶元素是否为"f"和"t"，如果是，我们弹出栈顶元素，
否则我们压入当前元素。最后栈的大小就是我们需要删掉的"fc"和"tb"子字符串的个数。

附上代码

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt = n;
    stack<char>st;
    for (int i = 0; i < n; i++) {
        if (st.empty()) {
            st.push(s[i]);
            continue;
        }
        if (st.top() == 'f' && s[i] == 'c') {
            st.pop();
        }
        else if (st.top() == 't' && s[i] == 'b') {
            st.pop();
        }
        else {
            st.push(s[i]);
        }
    }
    cout << st.size() << endl;
}

1021 A+B问题

根据题意我们考虑对于任意一个范围内的a，我们有多少个范围内的b与之对应，这道题有点坑，要考虑到所得到的和溢出后的答案也可能是我们的c的值，就比如说题目说明的最后一组合法数据：

这两个数的和显然会溢出32位有符号整数能存储的范围，但是溢出出后所得到的值也是1，所以这种情况也合法。由此可以看出任意一个范围内的a都有一个范围内的b与之对应，所以答案就是a的取值范围的大小2^{32}

关于溢出：一旦数字超过了这个限定，就会发生溢出，超过上限，叫做上溢出。超过下限，叫做下溢出。上溢出之后，又从下限开始：最大的数加1，就变成了最小的数。下溢出之后又从上限开始，最小的数减去1就变成了最大的数，如此循环往复。

1023 小A的线段（easy version)

根据题目中m的大小可以看出可以暴力枚举，枚举我们要选择哪些线段，判断这个状态是否合法。这里可以采用二进制形式的状态来代表每一种状态，举个例子：

所以我没只要从0到2^{n}-1进行状态的枚举，并对于每一种状态判断其是否合法，是否合法可以采用差分再前缀和的方式计算的方式，对于每一种选择的线段，我们让b[l] ++ ，b[r + 1] -- 来得出我们的差分数组，最后算一遍前缀和判断每一个位置是否都大于等于2即可。

1026 括号序列操作专家

这是一道贪心题目，如果左右括号不相等直接输出-1即可，对于其他情况我们用一个双端队列来遍历我们的括号序列，我们可以分为三种情况讨论

我们设s[i]是将要存入队列的字符，设该双端队列为que，

que.back() = '(' \quad ,\quad s[i] =')'：说明正好和队尾匹配，让队尾出队
que.back() = ')' \quad ,\quad s[i] ='('：出现了无法匹配的情况，说明必须要进行交换，我们贪心地将是s[i]与队列que.front()进行匹配（通过我们的操作我们显然发现队列中只会出现 ')' 字符），并且让队头出队，这一交换需要进行操作(i - 头部元素在原字符串的下标 - 两个位置之间已经交换过位置的\quad'('\quad的数目)次，为什么要减去两个位置之间已经交换过位置的数目是因为在队列中一串连续')'序列中，我们让一个'('与队列的头部元素去匹配了，所以当接下来的')'与后面的'('去匹配时，实际上两者之间已经少了那些已经交换过位置的'('元素，所以要减去它们。
举一个例子：

))((这样的序列，队列中存储就是{')',’)‘}，第一个(要与最前面的)进行匹配,因为这个')'的下标是0，'('的下标是2，所以操作次数是2，然后让队头出队，队列就变成{')'}，第二个'('要与最当前队列头部的')'进行匹配,因为这个')'的下标是1，'('的下标是3，但是原序列两者之间的一个'('已经交换过位置不在两者之间了，所以算出来的结果要减去1，所以这次操作次数为1，最终结果就是2 + 1 = 3 。
其他情况直接队尾入队（包括队空的情况）