2.5 蓝桥杯练习4题

昨天忘记写题解啦，今天补上。

1.[P8687 蓝桥杯 2019 省 A] 糖果

题意：糖果店的老板一共有 \(M\) 种口味的糖果出售。为了方便描述，我们将 \(M\) 种口味编号 \(1\) ∼ \(M\)。

小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而是 \(K\) 颗一包整包出售。

幸好糖果包装上注明了其中 \(K\) 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。

给定 \(N\) 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。

思路：看到数据范围只有\(20\)，这不是妥妥的状压\(dp\)？\(dp[i]\)表示达到状态\(i\)最少要买多少包。

先预处理出能满足的状态\(h\)，置\(dp[h] = 1\)。

然后转移方程：\(dp[i|a[j]] = min(dp[i|a[j]],dp[i]+1)\)

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,m,k;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>m>>k;
    ll dp[1<<m],a[n];
    memset(dp,127,sizeof(dp));
    for(int i = 1;i <= n; i++)
    {
        int h = 0;
        for(int j = 1;j <= k; j++)
        {
            int x; cin>>x;
            x--;
            h |= (1<<x);            
        }
        dp[h] = 1;
        a[i] = h;
    }

    for(int i = 0;i < (1<<m); i++)
    {
        for(int j = 1;j <= n; j++)
        {
            if(dp[i] < (1<<30))
                dp[i|a[j]] = min(dp[i|a[j]],dp[i]+1);
        }
    }

    if(dp[(1<<m)-1] >= 1<<30)cout<<-1<<"\n";
    else cout<<dp[(1<<m)-1]<<"\n";

    return 0;
}

2.[P8611 蓝桥杯 2014 省 AB] 蚂蚁感冒

题意：长 \(100\) 厘米的细长直杆子上有 \(n\) 只蚂蚁。它们的头有的朝左，有的朝右。

每只蚂蚁都只能沿着杆子向前爬，速度是 \(1\) 厘米 / 秒。

当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。

这些蚂蚁中，有 \(1\) 只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。

请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。

思路：又来到咱们经典的蚂蚁题了。两个蚂蚁相碰会掉头，这个其实我们不用考虑掉头，我们可以当作是两只蚂蚁交换位置然后朝着原方向走。那么有多少只会被感染呢？我们以被感染的朝着左边走为例。那么该只蚂蚁左边的与它方向相反的所有蚂蚁都会被感染，它右边的和它方向相同的蚂蚁都会被感染。

注意：特别的，如果被感染的蚂蚁在两端，且朝着它的那端走的话就只有它自己，因为它不会掉头了，另一边也就不用考虑啦。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 100;
struct node
{
    int dist,dir;
}a[N];

bool cmp(node a,node b)
{
    return a.dist<b.dist;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n; cin>>n;
    for(int i = 1;i <= n; i++)
    {
        int x; cin>>x;
        a[i].dist = abs(x),a[i].dir = (x>0?1:-1);
    }
    int ill = a[1].dist,d = a[1].dir;
    sort(a+1,a+1+n,cmp);
    int k = 1;
    for(int i = 1;i <= n; i++)
    {
        if(a[i].dist == ill)
        {
            k = i;
            break;
        }
    }
    int cnt = 0;

    if(d < 0)//左
    {
        for(int i = 1;i <= k-1; i++)
            cnt += (d !=a[i].dir);
        
        if(cnt){//!!!小心这里
             for(int i = k + 1;i <= n; i++)
                cnt += (d == a[i].dir);
        }
    }
    else
    {
        for(int i = k + 1;i <= n; i++)
            cnt += (d != a[i].dir);
       
        if(cnt){
            for(int i = 1;i <= k-1; i++)
                cnt += (d == a[i].dir);
        }
        
    }
    cout<<cnt+1<<"\n";
    return 0;
}

3.[P8638 蓝桥杯 2016 省 A] 密码脱落

题意：X 星球的考古学家发现了一批古代留下来的密码。

这些密码是由 A、B、C、D 四种植物的种子串成的序列。

仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的回文串）。

由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。

你的任务是：

给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

思路：其实很简单，我们只要把原串\(s\)反转一下变成\(t\)，求\(s\)和\(t\)的最长回文子串的长度，然后用\(n-最长回文子串的长度\)就是答案啦。这里求最长回文子串的长度我用的是记忆化搜索的版本。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e3 + 10;
int f[N][N],n,m;
string s,t;
int lcs(int i,int j)
{
    if(f[i][j] != -1)return f[i][j];
    if(i==0||j==0)return 0;
    else if(s[i]==t[j])f[i][j] = lcs(i-1,j-1) + 1;
    else f[i][j] = max(lcs(i,j-1),lcs(i-1,j));
    return f[i][j];
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>s;
    t = s;
    n = s.size();
    reverse(t.begin(),t.end());
    s = "?" + s,t = "?" + t;
    memset(f,-1,sizeof(f));
    cout<<n-lcs(n,n)<<"\n";

    return 0;
}

4.[P8646 蓝桥杯 2017 省 AB] 包子凑数

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

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

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

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

思路：由裴蜀定理可知\(ax+by = c\)。如果\(c = t\times\gcd(a,b)\)。只有\(\gcd(a,b)=1\)的时候才能表示所有的数。那么我们可以求一下所有数的\(\gcd\)的多少，如果不是\(1\)，那么答案就是\(INF\)。那么对于是\(1\)的情况，有多少是不能表示的呢？这里可以用完全背包啦。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N],dp[N],V = 1e4;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n; cin>>n;
    for(int i = 1;i <= n; i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    //ax + by = gcd(a,b);
    int g = a[1];
    for(int i = 1;i <= n; i++)
    {
        g = __gcd(g,a[i]);
    }
    if(g != 1)cout<<"INF\n";
    else{
        dp[0] = 1;
        for(int i = 1;i <= n; i++)
        {
            for(int j = a[i];j <= V; j++)
            {
                dp[j] = max(dp[j],dp[j-a[i]]);
            }
        }
        int cnt = 0;
        for(int i = 1;i <= V; i++)
        {
            if(!dp[i])cnt++;
        }
        cout<<cnt<<"\n";
    }
    return 0;
}