1.8 高一周赛总结

这次考试主要考察状压和堆，内容广度和思维深度并不大，然鹅我还是没（wo）能（tai）A（cai）K（le）。

T1 NKOJ 3900 AC小程序

题面：何老板写了一个有趣小程序，你迫不及待的要玩一下。
程序只有一个按钮，一开始屏幕上显示一个大写字母A。
你按第一下按钮，屏幕会显示C
你按第二下按钮，屏幕会显示CA
你按第三下按钮，屏幕会显示CAC
你按第四下按钮，屏幕会显示CACCA
你按第五下按钮，屏幕会显示CACCACAC
你按第六下按钮，屏幕会显示CACCACACCACCA
......
何老板问你，你按第N下按钮后，屏幕上会显示多少个A？多少个C？

解法：我看题面没啥思路，然后去手推AC的数量发现是两个fibonacci数列（雾）。

#include <bits/stdc++.h>

using namespace std;

int f1[105], f2[105];

int main()
{
    int n;
    scanf("%d", &n);
    f1[2] = f1[3] = 1;
    for (int i = 4; i <= 45; i++) f1[i] = f1[i - 1] + f1[i - 2];
    f2[1] = f2[2] = 1;
    for (int i = 3; i <= 45; i++) f2[i] = f2[i - 1] + f2[i - 2];
    printf("%d %d", f1[n], f2[n]);
}

T2 NKOJ 3789 营养午餐

题面：信竞班的同学们拼命学习，编程刷题到了废寝忘食的地步，看着大家日渐消瘦，这让何老板很是担心。于是何老板打算给大家提供营养午餐。

   何老板问同学们：“大家中午想吃什么呀？”
   A同学:"牛排、意大利面、面包、水果汁"；
B同学:"酸辣粉、薯片、牛肉干、回锅肉、小虾龙、葡萄干、烤鱼、二锅头"
......
信竞班总共n个同学，每个同学都提出了自己必吃的若干种食物，何老板统计了一下，全班提出的食物总共有m种(编号1到m)。
   受工资的影响，何老板最多只能提供其中k种食物，于是何老板想选出一些同学出来给他们提供午餐，要求选出来的这些同学所需的食物种类不超过k种。仁慈的何老板想让尽可能多的同学吃上午餐，问，最多能选出多少个同学出来？

解法：其实是个暴力，暴力枚举老板可提供的每一种食材（状压），然后判断是否合法，若合法就可以更新最大值。

#include <bits/stdc++.h>

using namespace std;

int nd[(1 << 15) + 1];

int getcnt(int x)
{
    int sum = 0;
    for (int i = 1; i <= 17; i++) if (x & (1 << i - 1)) sum++;
    return sum;
}

int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, t; i <= n; i++)
    {
        scanf("%d", &t);
        for (int j = 1, q; j <= t; j++)
        {
            scanf("%d", &q);
            if (!(nd[i] & (1 << q - 1))) nd[i] |= (1 << q - 1);
        }
    }
    int ans = 0;
    int tot = (1 << m) - 1;
    for (int i = 1; i <= tot; i++)
    {
        if (getcnt(i) <= k)
        {
            int sum = 0;
            for (int j = 1; j <= n; j++)
            {
                if ((nd[j] & i) == nd[j]) sum++;
            }
            ans = max(ans, sum);
        }
    }
    printf("%d", ans);
}

T3 NKOJ 1349 罐头到期

题面：约翰有一箱罐头快要过期保质期了，他知道奶牛贝茜非常喜欢吃罐头，于是他将这箱罐头送给了贝茜，但约翰要求，不许吃过了保质期的罐头，并且每天最多只能吃一只罐头。
贝西打开箱子数了数，共N只罐头，每只罐头的味道不同，保质期也不一定相同。它依次查看了每只罐头，并做了如下登记：第i号罐头，Xi

#include <bits/stdc++.h>

using namespace std;

struct node {
    int x, y;
    bool operator< (node q) const {
        return x < q.x;
    }
}a[100005];

priority_queue <int, vector <int>, greater<int> > Q; 

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].x, &a[i].y);
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
    {
        if (Q.size() < a[i].x) Q.push(a[i].y);
        else if (Q.top() < a[i].y) Q.pop(), Q.push(a[i].y);
    }
    long long sum = 0;
    while (Q.size())
    {
        sum += Q.top();
        Q.pop();
    }
    printf("%lld", sum);
}

T4 NKOJ 1530 混乱奶牛

题面：

Farmer John的N头奶牛中的每一头都有一个唯一的编号Si

奶牛们对在挤奶的时候被排成一支"混乱"的队伍非常反感. 如果一个队伍里任意两头相邻的奶牛的编号相差都超过K , 它就被称为是混乱的.

比如说，当N = 6, K = 1时,1, 3, 5, 2, 6, 4 就是一支"混乱"的队伍, 但是 1, 3, 6, 5, 2, 4 不是(因为5和6只相差1).

那么, 有多少种能够使奶牛排成"混乱"的队伍的方案呢?

解法：状压dp（刷表），考察每一个状态的方案数，但是没法转移，于是考虑添加一维记录上一只奶牛的编号。于是设f[j][i]表示当前奶牛的编号为j，已经选用奶牛的状态为i。

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll maxn = 105;

ll a[maxn], f[20][(1 << 17) + 1];

main()
{
    ll n, l;
    scanf("%d%d", &n, &l);
    for (ll i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    } 
    ll tot = (1 << n) - 1;
    for (ll i = 1; i <= n; i++) f[i][1 << i - 1] = 1;
    for (ll i = 0; i <= tot; i++)
    {
        for (ll j = 1; j <= n; j++)
        {
            if ((i & (1 << j - 1)))
            {
                for (ll k = 1; k <= n; k++)
                {
                    if ((!(i & (1 << k - 1))) && (abs(a[j] - a[k]) > l))
                    {
                        f[k][i | (1 << k - 1)] += f[j][i];
                    }
                }
            }
        }
    }
    ll ans = 0;
    for (ll i = 1; i <= n; i++)
    {
        ans += f[i][tot];
    }
    printf("%lld", ans);
}

T5（订正） NKOJ 1341 顺路外卖

题面：

何老板下班回家，他骑着一辆自行车，学校到家的为一条直路，距离为N公里。学校在0公里处，家在N公里处。

沿途每个一公里，都有一个小区。小区间有大量的外卖业务。何老板打算在回家途中，顺路揽送一些外卖，赚点钱，补贴家用。

今天有k家餐馆需要送外卖，其中第i家餐馆在Ai

何老板想知道，在从学校到家途中，在不走回头路的前提下，最多能送多少份外卖？

解法：堆 + 贪心，把每一份订单抽象为线段，于是有显然的贪心策略：当货框装不下时，依次扔掉右端点最远的线段直到货框装得下为止。

注：实现细节较多，需要谨慎思考。

#include <bits/stdc++.h>

using namespace std;

struct node {
    int l, r, num, id;
    bool operator< (node x) const {
        return r < x.r;
    }
    bool operator> (node x) const {
        return r > x.r;
    }
}a[100005];
inline bool cmp(node x, node y)
{
    return x.l < y.l;
}
priority_queue <node> maxqueue;
priority_queue <node, vector <node>, greater <node> > minqueue;

int sum[100005];

int main()
{
    int k, n, m;
    scanf("%d%d%d", &k, &n, &m);
    for (int i = 1; i <= k; i++)
    {
        scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].num);
        a[i].id = i;
    }
    sort(a + 1, a + k + 1, cmp);
    int ans = 0, cnt = 0;
    for (int i = 1, j = 1; i <= n && j <= k; i++)
    {
        while (!minqueue.empty() && i == minqueue.top().r)
        {
            ans += sum[minqueue.top().id];
            cnt -= sum[minqueue.top().id];
            sum[minqueue.top().id] = 0;
            minqueue.pop();
        }
        while (j <= k && i == a[j].l)
        {
            minqueue.push(a[j]), maxqueue.push(a[j]);
            cnt += a[j].num;
            sum[a[j].id] = a[j].num;
            j++;
        }
        while (!maxqueue.empty() && cnt - m >= sum[maxqueue.top().id])
        {
            cnt -= sum[maxqueue.top().id];
            sum[maxqueue.top().id] = 0;
            maxqueue.pop();
        }
        if (!maxqueue.empty() && cnt >= m && cnt - m < sum[maxqueue.top().id])
        {
            sum[maxqueue.top().id] -= (cnt - m);
            cnt = m;
        }
    }
    printf("%d", ans + cnt);
}

1.8 高一周赛总结

推荐阅读