T1

题解

对于k=100的情况，贪心

对于100%的数据

可以发现，当前的决策只对后面的开采有影响，且剩余耐久度与之后的开采收益成正比，如果倒着考虑这个问题，得出i-n的星球1点耐久度所能获得的最大收益，从后往前dp，得出最大值最后乘w就是答案

代码

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=100001;

int n,w,t[maxn],a[maxn];

double k,c,ans;

int main()

{

    //freopen("exploit.in","r",stdin);

    //freopen("exploit.out","w",stdout);

    scanf("%d%lf%lf%d",&n,&k,&c,&w);

    k=1-0.01*k;c=1+0.01*c;

    for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&a[i]);

    for(int i=n;i;i--)

        if(t[i]==1)

            ans=max(ans,ans*k+a[i]);

        else

            ans=max(ans,ans*c-a[i]);

    printf("%.2lf\n",ans*w);

}

T2

题解

从前往后推出每个人最少/最多有几个和第一个人相同的勋章

然后看最后一个最少是否是0即可

代码

#include<bits/stdc++.h>

inline int read()

{

    int x = 0,t = 1; char ch = getchar();

    while(ch < '0' || ch > '9'){if(ch == '-') t = -1; ch = getchar();}

    while(ch >= '0' && ch <= '9'){x = x*10+ch-'0'; ch = getchar();}

    return x*t;

}

const int MAXN = 20010;

int n;

int num[MAXN];

int L,R,mid;

int dp[MAXN],gun[MAXN];

inline void init()

{

    n = read();

    for(int i=1;i<=n;i++)

        num[i] = read();

    for(int i=1;i<n;i++)

        L=std::max(L,num[i]+num[i+1]);

    L=std::max(L,num[n]+num[1]),R=0x7ffffff;

}

inline void DP()

{

    while(L<R)

    {

        mid=(L+R)>>1;

        dp[1]=gun[1]=num[1];

        for(int i=2;i<=n;i++)

            dp[i]=std::min(num[i],num[1]-gun[i-1]),

        gun[i]=std::max(0,num[i]-(mid-num[i-1]-(num[1]-dp[i-1])));

        if(gun[n]==0) R=mid;

        else L=mid+1;

    }

    std::cout << L;

}

int main(void)

{

    std::ios_base::sync_with_stdio(false); 

    init();

    DP();

    return 0;

}

T3

题解

30%: O(n ^ 2 * m)暴力判断。

100%: 很显然答案的可能性最多只有n 种，所以我们将所有人的答案按字典序排序后枚举

将每个人的答案作为正确答案来进行判断。由于是判断题，若当前人的答案为正确答

案则零分者的答案也就确定了，那么只需统计出这两种答案的人数判断是否满足题意

即可。这一步使用字符串哈希即可解决。

另外要注意p = 0 和p = q = 0 的情况。

代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

const int N = 3e4 + 2, M = 5e2 + 2, sed = 31, SED = 131, mod = 70177, MOD = 92311;

int n, m, p, q, ans, hash[N], HASH[N];

int top, info[mod], nxt[N * 2], fet[N * 2], cnt[N * 2];

struct node {

    char s[M];

    inline bool operator < (const node &b) const {

        return strcmp(s, b.s) < 0;

    }

} a[N];

inline void Insert(const int &x, const int &y) {

    for (int k = info[x]; k; k = nxt[k])

        if (fet[k] == y) {

            ++cnt[k]; return ;

        }

    nxt[++top] = info[x]; info[x] = top;

    fet[top] = y; cnt[top] = 1;

    return ;

}

inline int Query(const int &x, const int &y) {

    for (int k = info[x]; k; k = nxt[k])

        if (fet[k] == y) return cnt[k];

    return 0;

}

inline void Solve1() {

    int tmp, TMP; ans = -1;

    for (int i = 0; i < n; ++i) {

        tmp = TMP = 0;

        for (int j = 0; j < m; ++j) {

            tmp = (tmp * sed + (a[i].s[j] == 'N')) % mod;

            TMP = (TMP * SED + (a[i].s[j] == 'N')) % MOD;

        }

        hash[i] = tmp, HASH[i] = TMP;

        Insert(tmp, TMP);

    }

    for (int i = 0; i < n; ++i)

        if (Query(hash[i], HASH[i]) == p) {

            tmp = TMP = 0;

            for (int j = 0; j < m; ++j) {

                tmp = (tmp * sed + (a[i].s[j] == 'Y')) % mod;

                TMP = (TMP * SED + (a[i].s[j] == 'Y')) % MOD;

            }

            if (Query(tmp, TMP) == q) {

                ans = i; break;

            }

        }

    if (ans != -1) printf("%s\n", a[ans].s);

    else 	puts("-1");

    return ;

}

char cur[M];

inline void Solve2() {

    int tmp, TMP; ans = -1;

    for (int i = 0; i < n; ++i) {

        tmp = TMP = 0;

        for (int j = 0; j < m; ++j) {

            tmp = (tmp * sed + (a[i].s[j] == 'N')) % mod;

            TMP = (TMP * SED + (a[i].s[j] == 'N')) % MOD;

        }

        hash[i] = tmp, HASH[i] = TMP;

        Insert(tmp, TMP);

    }

    for (int i = n - 1; i >= 0; --i)

        if (Query(hash[i], HASH[i]) == q) {

            tmp = TMP = 0;

            for (int j = 0; j < m; ++j) {

                tmp = (tmp * sed + (a[i].s[j] == 'Y')) % mod;

                TMP = (TMP * SED + (a[i].s[j] == 'Y')) % MOD;

            }

            if (Query(tmp, TMP) == p) {

                ans = i; break;

            }

        }

    if (ans != -1) {

        for (int i = 0; i < m; ++i)

            cur[i] = a[ans].s[i] == 'N' ? 'Y' : 'N';

        printf("%s\n", cur);

    }

    else 	puts("-1");

    return ;

}

void Solve3() {

    int tmp, TMP;

    for (int i = 0; i < n; ++i) {

        tmp = TMP = 0;

        for (int j = 0; j < m; ++j) {

            tmp = (tmp * sed + (a[i].s[j] == 'N')) % mod;

            TMP = (TMP * SED + (a[i].s[j] == 'N')) % MOD;

        }

        Insert(tmp, TMP);

        tmp = TMP = 0;

        for (int j = 0; j < m; ++j) {

            tmp = (tmp * sed + (a[i].s[j] == 'Y')) % mod;

            TMP = (TMP * SED + (a[i].s[j] == 'Y')) % MOD;

        }

        Insert(tmp, TMP);

    }

    bool flag = true;

    for (int i = 0; i < m; ++i) cur[i] = 'N';

    do {

        tmp = TMP = 0;

        for (int j = 0; j < m; ++j) {

            tmp = (tmp * sed + (cur[j] == 'N')) % mod;

            TMP = (TMP * SED + (cur[j] == 'N')) % MOD;

        }

        if (Query(tmp, TMP) == 0) {

            flag = true; break;

        }

        flag = false;

        for (int j = m - 1; j >= 0; --j)

            if (cur[j] == 'Y') cur[j] = 'N';

            else {

                cur[j] = 'Y'; flag = true; break;

            }

    } while (flag);

    if (flag) printf("%s\n", cur);

    else 	puts("-1");

    return ;

}

int main() {

    //freopen("answer.in", "r", stdin);

    //freopen("answer.out", "w", stdout);

    scanf("%d%d%d%d", &n, &m, &p, &q);

    for (int i = 0; i < n; ++i) scanf("%s", a[i].s);

    sort(a, a + n);

    if (p) Solve1();

    else if (q) Solve2();

    else 	Solve3();

    fclose(stdin); fclose(stdout);

    return 0;

}