T1

一个玩具可能在很多天打折，每次只要在最后一天打折的时候买即可
二分答案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

struct node
{
    int t, x;
} b[200005];
bool cmp(node a, node b)
{
    return a.t < b.t;
}
int n, m, a[200005], c[200005];

bool check(ll k)
{
    ll mon = 0;
    int last = 0;
    for (int i = 1; i <= n; ++i)
        c[i] = a[i];
    for (int i = 1; i <= m; ++i)
    {
        if (b[i].t > k)
        {
            break;
        }
        last = i;
        mon += b[i].t - b[i - 1].t;
        ll buy = min(mon, (ll)c[b[i].x]);
        c[b[i].x] -= buy, mon -= buy;
    }
    mon += k - b[last].t;
    ll cnt = 0;
    for (int i = 1; i <= n; ++i)
        cnt += c[i];
    if (cnt * 2 > mon)
        return 0;
    else
        return 1;
}

int main()
{
    freopen("toys.in", "r", stdin);
    freopen("toys.out", "w", stdout);
    cin >> n >> m;
    ll l = 0, r = 0, ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        r += 2 * a[i];
    }
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &b[i].t, &b[i].x);
    }
    sort(b + 1, b + m + 1, cmp);
    while (l <= r)
    {
        ll mid = (l + r) >> 1;
        if (check(mid))
        {
            r = mid - 1;
            ans = mid;
        }
        else
            l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}

T2

将每个属性扩展成K-1个01属性，可以发现本质不同的属性不超过$2^k$种，因此只要计算最多4096个二进制位的情况
合成成功相当于or,失败相当于and
TODO

T3

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/cxjy-day-13/