CF1291

A. Even But Not Even

题意：给一个长度为n(n < 3000)的数字，求能不能在各个位里凑出一个各个位数和为偶数却是一个奇数的数字

思路：直接找出两个奇数凑在一起

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <stack>

using namespace std;
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scl(a) scanf("%lld",&a)
#define scll(a,b) scanf("%lld%lld",&a,&b)
#define prl(a) printf("%lld
",a)
#define prd(a) printf("%d
",a)
#define prf(a) printf("%lf
",a)
#define ptd(a) printf("%d ",a)
#define scf(a) scanf("%lf",&a)
#define scff(a,b) scanf("%lf%lf",&a,&b)
#define scfff(a,b,c) scanf("%lf%lf%lf",&a,&b,&c)
#define rint register int
#define mem(a) memset(a,0,sizeof(a))
#define rush() int T;scd(T);while(T--)
#define lc(i) (i<<1)
#define rc(i) (i<<1|1)
#define mp make_pair
typedef long long ll;
typedef double db;
inline int read() {char c=getchar();int x=0,f=1;while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}return x*f;}
const int inf = 2147483647-1;
const int maxn = 2e5 + 10;
char s[3002];
int main ()
{    
    rush() {
        int n = read();
        scanf("%s",s);
        int ans[3002],cnt=0;
        for (int i = 0; i < n; ++i) {
            if ((s[i]-'0')%2==0)continue;
            ans[cnt++] = s[i]-'0';
        }
        if (cnt < 2) puts("-1");
        else
            printf("%d%d
",ans[0],ans[1]);
    }
    return 0;
}

View Code

B. Array Sharpening

题意：是否能通过某种操作使得数组的数字尖锐

数组尖锐的定义是数组保持严格递增或者严格递减（从左边严格递增）或者先严格递增再严格递减

操作是使得某一个位置上的数字不断自减

思路：先考虑让数组只负责从左边严格递增，查看峰值在哪里，记为 l, 再考虑让数组负责从最右端严格递增，查看峰值在哪里，记为 r。

可以证明，只要保证l >= r，就能保证存在一个在 (r，l)的点p，使得左边严格递增，右边严格递减

const int maxn = 3e5 + 10;
int a[maxn];
int main ()
{    
    rush() {
        int n = read();
        for (int i = 1; i <= n; ++i) a[i] = read();
        int l, r;
        for (int i = 1; i <= n; ++i) {
            if (a[i] >= i-1) l = i;
            else break;
        }
        for (int i = n; i; --i) {
            if (a[i] >= n-i) r = i;
            else break;
        }
//        printf("l = %d r = %d
", l, r);
        if (l >= r) puts("Yes");
        else puts("No");
    }
    return 0;
}

View Code

C. Mind Control

题意：有一个大小为n（n <= 3500）的数组，每一个人按照顺序从数组的最前端或者是最后端取走数字，玩家第k个取数字，但是玩家最多可以控制排在他前面 k 个人的决策，求出玩家采取采取最优策略至少能够取出多大的数字。

思路：暴力

const int maxn = 3e5 + 10;
int a[maxn];
int main ()
{    
    rush() {
        int n = read(), m = read(), k = read();
        k = min(k, m - 1);
        int len = n-m+1;
        int other = m-1-k;
        for (int i = 1; i <= n; ++i) a[i] = read();
        int ans = 0;
        for (int i = 0; i <= k; ++i) {
            int bad = inf;
            for (int j = i + 1; j <= i + 1 + other; ++j) {
                bad = min(bad, max(a[j], a[j + len - 1]));
//                printf("len = %d %d - %d
", len, j + len - 1, j);
            }
            ans = max(ans, bad);
        }
        prd(ans);
    }
    return 0;
}

View Code