前言

难度比较大，特别是有不少二分答案的题目，并且最后一题的dp还需要额外的优化；构造题也是卡了不少同学，需要仔细观察才行

T1

多多最近在玩一种卡牌对弈游戏，对弈双方手中各有个卡牌，每个卡牌都有一个武力值，在每一轮对弈中，双方各出一张卡牌，只有自己卡牌的武力值高于对方，该轮对弈才算取胜，然而多多有一种超能力一读心术，可以预先知道对方下一步如何出牌，奈何多多是个数学菜鸟，即使知道了对方的出牌顺序，也难以使得收益最大化。请为多多设计一种出牌顺序，使得多多赢得尽可能多的对弈局数。注意每张卡牌只能用一次，对弈结束后要用完所有的卡牌。

输入描述

第一行输入一个数字n(1<=n<=10^5),表示有n个卡牌。

接下来两行，每行包含个数字，分别用来表示多多和对方手里所拥有的卡牌的武力值xi和yi（1<=xi,yi<=10^5))

输出描述

输出一个整数，表示多多最多能赢得的对弈局数。

样例

输入
3
1 2 3
1 2 3
输出
2

输入
3
1 3 2
5 5 5
输出
0

思路与代码

类似田忌赛马的思想，可以贪心。把双方的牌都从小到大排序，然后对于每个对手的牌，贪心的找我能用哪个最小的牌比他大。实现思路是双指针，线性复杂度。

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[100005], b[100005];
int main() {
    cin>>n;
    for(int i = 1; i<=n; i++) cin>>a[i];
    for(int i = 1; i<=n; i++) cin>>b[i];
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    int ta=1, tb=1,ans=0;
    while(ta <= n && tb <= n) {
        while(ta <= n && a[ta] <= b[tb]) ta++;
        if(ta <= n) ans ++;
        ta++;tb++;
    }
    cout << ans << endl;
}
// 64 位输出请用 printf("%lld")

T2

今天是小王在小李子公司工作的第一天，他收到了老板小李子给他的一个长度为的正整数序列p0,p1,...,pn-1。p0表示股票的初始价格，p1~p-1表示的是股票的每个月的上涨情况，小李子希望小王能够让这只股票的价格按这个序列上涨。但是小王知道如果上涨系数超过k%就会违反多多村委会的规定，所以小王决定适当增加这只股票某些月份要上张的数值（必须是整数，包括第一个月的初始价格)，以保证上涨系数不超过k%，但是为了尽量遵循小李子的意愿，要求对所有月份股票价格变更的总和要尽可能的小。第i个月的股票价格的上涨系数为

输入描述

第一行为一个整数t表示有t个测试样例(1≤t≤100)

随后每个测试样例包含两行。第一行分别为n，k(2≤n≤1000,1≤k≤100)，n表示序列长度，k表示上涨系数。第二行包括n个正整数p0,p1,p2,...,pn-1(1≤pi≤10^5)

输出描述

输出t行，每行一个整数表示在保证对应测试样例中每月上涨系数不超过k%的条件下，整个序列的最小变更总和。

样例

输入
2
5 12
1000 34 12 27 131
4 10
100 1 1 1
输出
19
0

思路与代码

由于序列变更只能变大，而对于上涨系数过大的月份，期望上涨系数变小。所以对于上述公式，趋势上要让分子减小，分母变大。因此可以考虑把所有变更都加到p_0上。因此我们可以二分这个变更，然后check是否满足[每月的上涨系数均<k%]的题意即可。复杂度O(nlogn)

#include <iostream>
using namespace std;
int n,k,a[100005];
bool ok(int x ) {
    long long now = a[1] + x;
    for(int i = 2; i<=n; i++) {
        if(a[i]*1.0/now > k/100.0) return false;
        now += a[i];
    }
    return true;
}
int main() {
    int t;
    cin>>t;
    while(t--) {
        cin>>n>>k;
        for(int i = 1; i<=n; i++) cin>>a[i];
        long long l = 0, r = 1e9, ans = 0;
        while(l<=r) {
            long long mid = (l+r)/2;
            if(ok(mid)) {
                r = mid-1;
                ans = mid;
            } else l = mid+1;
        }
        cout << ans << endl;
    }
}
// 64 位输出请用 printf("%lld")

T3

题意

给定一个字符串S和整数m,所有与S的编辑距离在m以内的字符串，最多能包含多少个"PDD"子串？

输入描述

第一行为一个整数t表示有t个测试样例。(1≤t≤50)

随后每个测试样例包含两行

第一行一个整数0≤m≤10^6

第二行一个非空字符串S,长度在1和10^5之间，只包含字符P和D。

对于50%的数据，m和S的长度不超过100

输出描述

T行，每个测试样例一行，输出一个整数表示最多能包含多少个PDD子串

样例

输入
2
3
PDPPDDDDD
6
P
输出
3
2

思路与代码

先转化一下题意，“编辑距离在m以内”，可以转化为“增加删除修改操作最多不超过m次”。

贪心构造。先构造原生的"PDD"子串，因为此时他们不需要操作。刨除后寻找"PD"和"DD"子串，因为次数他们需要操作1次。对于剩下的字符一定是需要操作两次（增添两个字符）来得到PDD子串的，所以答案每增加1，就需要操作两次。这三步下来，如果还有富余的操作次数（即m次没用完），则生造PDD子串，即答案每增加1，就需要操作三次。复杂度是线性的，O(n)。

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int dp[105][105],m;// dp[i][j] 前i个字符，编辑距离为j的
char s[100005];
char s2[100005];
vector<vector<char> > vv;
int main() {
    int t;
    cin>>t;
    while(t--) {
        cin>>m;
        cin>>s;
        int len = strlen(s);
        int i = 0, ans = 0, p = 0;
        int ret_s_num = len;
        memset(s2,0,sizeof s2);
        for(int i = 0; i<len; i++) {
            if(i+2<len && s[i]=='P' && s[i+1]=='D' && s[i+2]=='D') {
                s2[p++] = 'Q',i+=2;ret_s_num -= 3;ans ++;
            } else s2[p++] = s[i];
        } s[p] = 0;
        int nowm = 0;
        for(int i = 0; i+1<p; i++) {
            if(nowm >= m) break;
            if(s2[i] == 'P' && s2[i+1] == 'D') {
                nowm++;
                i++;
                ans ++;
                ret_s_num -= 2;
            }
            if(s2[i] == 'D' && s2[i+1] == 'D') {
                nowm++;
                i++;
                ans ++;
                ret_s_num -= 2;
            }
        }
        int retm = m - nowm;
        if(retm > 2*ret_s_num) {
            ans += ret_s_num + (retm-2*ret_s_num)/3;
        } else {
            ans += retm/2;
        }
        cout << ans <<endl;
    }
}
// 64 位输出请用 printf("%lld")

T4

题意

多多负责守卫新手村同学免受魔物的攻击，这天他知道了经过时间t后，将会有特级魔物召唤百鬼夜行入侵新手村，多多决定在魔物到来之前尽可能多地在入口搭建魔法防御塔（要求搭建总耗时<=t），入口两端之间可建造的位置被多多按顺序标记为1,2,...,n,由于地形环境差异，不同位置搭建防御塔的耗时也不同，第i个位置建造耗时为xi. 时间有限，多多可能无法将每座防御塔都搭建完成，防御塔间连续空缺越多，魔力也会相对越弱，魔物的攻击就会变得更加猛烈。特级魔物会寻找魔力最薄弱进攻，你需要告诉多多魔力最薄弱处至少有多少座防御塔空缺。

输入描述

第一行为一个整数T,表示共有T个测试数据(1<=T<=10)

每组测试数据：

第一行为两个整数n与t,分别表示可搭建的魔法防御塔个数和经过多少时间魔物发动百鬼夜行(1<=n<=10^5,1<=t<=10^9)

第二行为个整数，用空格隔开，xi表示第座魔法防御塔的搭建耗时(1<=xi<=5000)

输出描述

每组数据输出一个结果，每个结果占一行

样例

输入
1
6 9
12 2 7 4 10 11
输出
2

输入
1
8 14
12 8 15 11 12 1 13 13
输出
3

思路与代码

二分防御塔空缺数+dp来check合法性。

假设二分的值为x，则其中dp[i]代表在前i个防御塔满足最大空缺数为x的前提下，造第i个防御塔所需要的最大耗时。这里让n+1放一个0值，把末尾这段空缺考虑进去。

对于dp状态转移，只需要维护区间长度为x的窗口内的最小值（假设为minn），则dp[i]=minn+a[i]，这里需要动态维护长度为x的窗口内的最小值。代码里用multiset来做的维护最小值和窗口的动态更新。（复杂度O(nlognlogn)，会超时）

这里可以优化为用单调队列维护，这样复杂度O(nlogn)

#include <iostream>
#include <set>
#include <cstring>
using namespace std;
int n,t;
long long a[100005];
long long dp[100005];
bool ok(int x) {
    multiset<long long> ss;
    memset(dp,0,sizeof dp);
    for(int i = 1; i<=x; i++) {
        dp[i] = a[i];
        ss.insert(dp[i]);
        
    }
    for(int i = x+1; i<=n; i++) {
        dp[i] = *ss.begin() + a[i];
        ss.insert(dp[i]);
        auto it = ss.find(dp[i-x]);
        ss.erase(it);
    }
    return dp[n] <= t;
}
int main() {
    int T;
    cin>>T;
    while(T--) {
        cin>>n>>t;
        for(int i = 1; i<=n; i++) cin>>a[i];
        n++;
        a[n] = 0;
        int l = 1, r = n, ans = 0;
        while(l<=r) {
            int mid = (l+r)/2;
            if(ok(mid)) {
                r = mid - 1;
                ans = mid;
            } else l = mid + 1;
        }
        cout << ans-1 << endl;
    }
}
// 64 位输出请用 printf("%lld")