蓝桥杯3/28

竞赛部培训

• ✨竞赛部培训

文件格式转换

原题链接

题目描述

小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次同时出现。

更准确的说，小明定义 Alice 和 Bob "同时出现" 的意思是：在小说文本 中 Alice 和 Bob 之间不超过 K 个字符。

例如以下文本：

This is a story about Alice and Bob.Alice wants to send a private message to Bob.

假设 K = 20，则 Alice 和 Bob 同时出现了 2 次，分别是"Alice and Bob" 和 "Bob. Alice"。前者 Alice 和 Bob 之间有 5 个字符，后者有 2 个字符。

注意:

1. Alice 和 Bob 是大小写敏感的，alice 或 bob 等并不计算在内。

2. Alice 和 Bob 应为单独的单词，前后可以有标点符号和空格，但是不能 有字母。例如 Bobbi 並不算出现了 Bob。

输入描述

第一行包含一个整数$K（1 \leq K \leq 10^6）$。

第二行包含一行字符串，只包含大小写字母、标点符号和空格。长度不超过 $10^6$。

输出描述

输出一个整数，表示 Alice 和 Bob 同时出现的次数。

输入输出样例

输入

20
This is a story about Alice and Bob.Alice wants to send a private
message to Bob.

输出

2

运行限制

最大运行时间：1s
最大运行内存: 512M

题解

string.find(str, pos)如果找到目标，则返回该子字符串首次出现时其首字符的索引；否则，返回string::npos

#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
typedef long long LL;
using namespace std;
string a = "Alice", b = "Bob";
int main()
{
    LL k;
    string s;
    cin >> k;
    getchar();
    getline(cin , s);
    vector<int>va,vb;
    int ita = 0 , itb = 0;
    while(s.find(a ,ita+1) != string::npos)
    {
        ita = s.find(a , ita);
        va.push_back(ita);
        ita++;
    }
    while(s.find(b , itb) != string::npos)
    {
        itb = s.find(b , itb);  
        vb.push_back(itb);
        itb++;
    }
    LL l = 0 , r = 0;
    LL cnt = 0;
    for(LL i = 0 ; i<va.size() ; i++)
    {
        while(l<vb.size() && va[i]-vb[l]-3 > k)  l++;
        while(r<vb.size() && vb[r]-va[i]-5 <= k) r++;
        cnt += r-l;
    }
    cout << cnt;
    return 0;
}

包子凑数

原题链接

题目描述

资源限制

时间限制：1.0s 内存限制：256.0MB

　小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

　　每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。

　　当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。

　　小明想知道一共有多少种数目是包子大叔凑不出来的。

输入格式

　　第一行包含一个整数N。(1 <= N <= 100)
　　以下N行每行包含一个整数Ai。(1 <= Ai <= 100)

输出格式

　　一个整数代表答案。如果凑不出的数目有无限多个，输出INF。

样例

Input

　　2
　　4
　　5

Output

　　6

　　再例如，
Input

　　2
　　4
　　6

Output

　　INF

样例说明
　　对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。
　　对于样例2，所有奇数都凑不出来，所以有无限多个。

　　资源约定：
　　峰值内存消耗（含虚拟机） < 256M
　　CPU消耗 < 1000ms

严格的来讲，如果将其边界定义为其所有数字的最小公倍数，在4号用例之后会超时

以4号用例
Input:

10
87
86
56
84
96
62
83
71
76
73

得出其最小公倍数：

因此 凑不出的数目为有限个时，找的上界可以自己定，只要不超时就行
Output

135

C++ 代码

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
typedef long long ll;
using namespace std;
const int N = 1e5;
int n, a[N], dp[N];
inline ll lcm(ll a,ll b)
{
    return a * b / __gcd(a,b);
}
int main()
{
    ll sum = 1;
    cin >> n;
    rep(i, 1, n)
    {
        cin >> a[i];
        // sum = lcm(sum, a[i]);
        // sum *= a[i];
    }
    int x = a[1];
    rep(i, 2, n)
        x = __gcd(x, a[i]);
    if(x != 1)  
    {
        cout << "INF" << endl;
        return 0;
    }
    dp[0] = 1;
    rep(i , 1 , n)
        for(ll j = 0; j <= N; j++)
        {
            if(j < a[i]) continue;
            if(dp[j - a[i]]) dp[j] = 1;
        }
    int num = 0;
    for(ll j = 1 ; j < N; j++)
        if(!dp[j]) num ++; 
    cout << num << endl;
    // debug(num);
    return 0;
}

游园安排

原题链接

【问题描述】

L 星球游乐园非常有趣，吸引着各个星球的游客前来游玩。小蓝是 L 星球游乐园的管理员。为了更好的管理游乐园，游乐园要求所有的游客提前预约，小蓝能看到系统上所有预约游客的名字。每个游客的名字由一个大写英文字母开始，后面跟 0 个或多个小写英文字母。游客可能重名。小蓝特别喜欢递增的事物。今天，他决定在所有预约的游客中，选择一部分游客在上午游玩，其他的游客都在下午游玩，在上午游玩的游客要求按照预约的顺序排列后，名字是单调递增的，即排在前面的名字严格小于排在后面的名字。一个名字 A 小于另一个名字 B 是指：存在一个整数$i$，使得 A 的前 $i$ 个字母与 B 的前$i$个字母相同，且 A 的第 $i+1$ 个字母小于 B 的第 $i+1$ 个字母。（如果 A 不存在第 $i + 1$ 个字母且 B 存在第 $i + 1$ 个字母，也视为 A 的第 $i + 1$ 个字母小于 B 的第 $i + 1$个字母）作为小蓝的助手，你要按照小蓝的想法安排游客，同时你又希望上午有尽量多的游客游玩，请告诉小蓝让哪些游客上午游玩。如果方案有多种，请输出上午游玩的第一个游客名字最小的方案。如果此时还有多种方案，请输出第一个游客名字最小的前提下第二个游客名字最小的方案。如果仍然有多种，依此类推选择第三个、第四个……游客名字最小的方案。

【输入格式】

输入包含一个字符串，按预约的顺序给出所有游客的名字，相邻的游客名字之间没有字符分隔。

【输出格式】

按预约顺序输出上午游玩的游客名单，中间不加任何分隔字符。

【样例输入】

WoAiLanQiaoBei

【样例输出】

AiLanQiao

【评测用例规模与约定】
对于 20% 的评测数据，输入的总长度不超过 20 个字母。
对于 50% 的评测数据，输入的总长度不超过 300 个字母。
对于 70% 的评测数据，输入的总长度不超过 10000 个字母。
对于所有评测数据，每个名字的长度不超过 10 个字母，输入的总长度不超过 1000000 个字母。

题解

题目大意
1. 一个大写单词表示一个游客，且可能重名
2. 上午的游客按照字典序排序，且人数尽可能多
3. 如果方案有多种，请输出上午游玩的游客名字的字典序最小的方案

字典序排序 ：
游客a 和 游客 b

Abcd 和 Abcde ==== a < b
Abcd 和 Bbcd ===== a < b

动态规划(最长上升子序列)+递归 $O(n^2)$

状态转移方程：

f[i] = max(f[i] , f[j] + 1) 

时间复杂度 $O(n^2)$

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#define ios ios::sync_with_stdio(false), cin.tie(0)
#define rep(i, a, n) for (register int i = a; i <= n; i++)
#define per(i, a, n) for (register int i = n; i >= a; i--)
#define debug(x) cout << #x << ": " << x << endl
#define MOD 1000000007
#define INF 0x3f3f3f3f
typedef long long LL;
using namespace std;
const int N =1e6 + 10;
string name[N]; //存储游客名字
int n;  //游客总数
int dp[N] , m[N];   
// vector< vector<int> > m(N);
int main()
{
    string s;
    cin >> s;
    rep(i , 0 , s.size()-1) //记录游客名字 1~n
    {
        n++;
        name[n] = s[i];
        while(s[i+1] - 'A' > 26)  name[n] += s[++i];
    }
    // debug(n);    //测试输入
    // rep(i , 1, n)
    //  cout << name[i] << ' ';
    /**
     * @brief 
     * dp(i) : 以前i个人为例，上午游玩的客人方案的集合，
     * 属性：  人数的最大值
     * 对于 以第i人为结尾的所有集合，以倒数第二人区分该集合的元素
     * 有一个特殊点 只有一个人 
     */
    rep(i , 1, n)
    {
        dp[i] = 1;
        m[i] = -1;
        rep(j , 1, i-1)
            if(name[j] < name[i])
            {
                if(dp[j] +1 > dp[i] ||(dp[i]==dp[j]+1 && name[j] < name[m[i]])) 
                {
                    dp[i] = dp[j] + 1;
                    m[i] = j;
                }
            }
    }
    int cnt = 0 , t;
    rep(i , 1 , n)
        if(dp[i] > cnt)
        {
            cnt = dp[i];
            t = i;
        }
    string str, ans = name[t];
    rep(i ,1 , cnt-1)
    {
        str = ans;
        t = m[t];
        ans = name[t] + str;
    }
    debug(cnt);
    cout << ans;
    return 0;
}

标准答案：

AtbdAvymmBhBppwCbazuDFskGjopJJeeuLegMhectMqdcyMsrqcMuNpOOneeOxPfPqnPunkdQRimpmRmowzRsrte
SzrTjTsshUr

我的输出：

AtbdAvymmBhBppwCbazuDFskGjopJJeeuLegMhectMqdcyMsrqcMuNpOOneeOxPfPqnPunkdQRimpmRmowzRsrte
TVtXifbZ

分析：

如果方案有多种输出字典序最小的方案

使用二分 $O(nlogn)$

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, a, n) for (register int i = a; i <= n; i++)
#define per(i, a, n) for (register int i = n; i >= a; i--)
#define debug(x) cout << #x << ": " << x << endl
typedef long long LL;
using namespace std;
const int N =1e6 + 10;
string name[N]; //存储游客名字
int n;  //游客总数
string q[N];
int pos[N], ans[N];
int bsearch(int l ,int r, string x)
{
    while(l < r)
    {
        int mid = l + r  >> 1;
        if(q[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}
int main()
{
    string s;
    cin >> s;
    rep(i , 0 , s.size()-1) //记录游客名字 1~n
    {
        n++;
        name[n] = s[i];
        while(s[i+1] - 'A' > 26)  name[n] += s[++i];
    }
    int len = 1;
    q[1] = name[1];
    pos[1] = len;
    rep(i , 2, n)
    {
        if(name[i] > q[len])
        {
            q[++len] = name[i];
            pos[i] = len;
        }
        else
        {
            int t = bsearch(1 , len + 1, name[i]);
            q[t] = name[i];
            pos[i] = t;
        }
    }
    int tmp = len;
    string smx = "Zzzzzzzzzz"; //10
    per(i , 1 , n)
    {
        if(!tmp) break;
        if (pos[i] == tmp && smx > name[i]) {
            ans[tmp] = i;
            tmp --;
            smx = name[i];
        }
    }
    rep(i , 1 , len)
        cout << name[ans[i]];
    return 0;
}

经典最长上升子序列模板

    for(int i = 1 ; i <= n; i++)
    {
        dp[i]=1;
        for(int j = 1; j < i ;j++)
            if(a[j] < a[i]) dp[i] = max(dp[i] , dp[j] + 1);
        mx = max(mx , dp[i]);
    }

二分处理最长上升子序列

    rep(i , 1 , n)
    {
        int l = 0 , r = len;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(q[mid] < name[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len , r + 1);
        q[r + 1] = name[i];
    }