SDTBU-ACM集训队20级---个人赛 7

前言

简单写一下题解。

最近科学研究表明：锻炼身体可以有效增加脑容量。而且不是线性增长，也就是说哪怕是抽空散步走走也可以让大脑变得更聪明。

题目：A. Even But Not Even

链接： Even But Not Even

题意：

给定一个数字，可以任意删除数字中的某些位。如果最后该数字本身不能被2除尽，但是所有位数值的和可以，那么将该数字称之为 ebne 数字。例如：13不能被2除尽，但是1+3=4，可以被2除尽，那么13就是 ebne 数字。

输入格式

输入由多个测试用例组成。第一行包含单个整数t (1 ≤ t ≤ 1000） — 测试用例的数量。测试用例的说明如下。

每个测试用例的第一行包含一个整数n(1 ≤ n ≤ 3000） — 原始数字中的位数。

每个测试用例的第二行包含一个非负整数s，包括n个数字。

保证s不包含前导零和n在所有测试用例中不超过3000。

输出格式

对于输入中给出的每个测试用例，请按以下格式打印答案：

• 如果无法创建 ebne 数字，请打印“-1”（不带引号）;
• 否则，请在删除一些数字（可能是零，但不是全部数字）后打印生成的数字。此数字应为 ebne。如果有多个答案，您可以打印其中任何一个。请注意，不接受带有前导零或空字符串的答案。不必最小化或最大化已删除的位数。

数据范围

1 ≤ t ≤ 3000

1 ≤ n ≤ 3000

输入样例：

4
4
1227
1
0
6
177013
24
222373204424185217171912

输出样例：

1227
-1
17703
2237344218521717191

思路：

• 思维 。ebne 数字首先要满足的是该数本身不能除尽2，那么最后一位一定是以奇数结尾。其次要满足所有位数的和要是偶数。
• 那么我们就可以在读入数字后，用 sum 存好所有位数的和，然后从后往前开始遍历。
  • 如果当前位是奇数，那么就判断此时的 sum 是否为偶数，若满足条件就退出；如果不满足条件就将当前位的数字在 sum 中减去。
  • 如果当前位是偶数，不满足第一个条件，直接将当前位在 sum 中减去即可。

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10;
typedef long long ll;

int a[3][N];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        string s;
        cin>>n>>s;
        int sum=0;
        for(int i=0;i<n;++i)sum+=s[i]-'0';

        int f=0;
        for(int i=n-1;i>=0;--i)
        {
            int t=s[i]-'0';
            if(t%2==1&&sum%2==0)
            {
                f=1;
                for(int j=0;j<=i;++j)cout<<s[j];
                cout<<endl;
                break;
            }
            sum-=t;
        }
        if(f==0)cout<<-1<<endl;
    }
    system("pause");
    return 0;
}

B. Array Sharpening

题目：Array Sharpening

题意：

给我们n个数组成的序列，我们可以将序列中的某个数字减去任意值，但是不可以使该数字的值小于0。我们可以进行上述操作任意次，请问我们是否可以使给定的序列变为严格单峰序列（即只有一个最大值，最大值两侧依次递减，不可以有相同的数字）。

输入格式

输入由多个测试用例组成。第一行包含单个整数t (1 ≤ t≤ 15000 ） — 测试用例的数量。测试用例的说明如下。

每个测试用例的第一行包含一个整数n (1 ≤ n ≤ 3×10⁵)。

每个测试用例的第二行是包含n个非负整数的一个序列：a₁，…，a_n（0 <= a_i <=10⁹）。

保证n在所有测试用例中不超过3×10⁵。

输出格式

对于每个测试用例，如果可以使用所描述的操作使给定的数组锐化，则输出一行包含“Yes”（不带引号）的行，否则输出“No”（不带引号）。

数据范围

1 ≤ t≤ 15000

1 ≤ n ≤ 3×10⁵

0 <= a_i <=10⁹

保证n在所有测试用例中不超过3×10⁵。

输入样例：

10
1
248618
3
12 10 8
6
100 11 15 9 7 8
4
0 1 1 0
2
0 0
2
0 1
2
1 0
2
1 1
3
0 1 0
3
1 0 1

输出样例：

Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No

思路：

• 如果一个序列可以变为单峰序列，那么它要满足什么性质？显然，如果满足单峰，那么最小值就不能在序列中间出现，只能放在两侧的边沿。也就是说我们要让两边尽可能的小。
• 两边数字的最小值是多少？因为数字必须为非负数，且不能有相同的数字，那么左右两侧的第一个数字最小就是0，往里走的第二个数字是1，依次递增，那么我们就可以找到规律：
  • 从左往右：当前数字需要满足 a[i]<(i-1) ，直到不满足或者遍历结束时退出。
  • 从右往左：当前数字需要满足 a[i]<(n-i) ，直到不满足或者遍历结束时退出。
  • 最后要判断一下 从右往左 的循环是否遍历到 从左往右 的循环的后2个数字，如果是就说明满足条件。
  • ps：为什么是后2个数字？因为如果只是前面一个数字，那么例如 0 1 1 0 也是满足的，但显然该序列不满足单峰序列的条件。

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=3e5+10;
typedef long long ll;

int a[N];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;++i)cin>>a[i];

        int k=0;
        for(int i=1;i<=n;++i)
        {
            if(a[i]<(i-1))
            {
                k=i;
                break;
            }
        }
        if(k==0)
        {
            cout<<"Yes"<<endl;
            continue;
        }

        int u=0;
        for(int i=n;i>=0;--i)
        {
            if(a[i]<(n-i))
            {
                u=i;
                break;
            }
        }
        //cout<<k<<" "<<u<<endl;
        if(u<k-1)
            cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    system("pause");
    return 0;
}