CXJY-Day 11

Author Avatar
Axell 8月 08, 2019
  • 在其它设备中阅读本文章

题面

T1

维护一个后缀和差分数组，从后往前算出每个操作的执行次数
然后正着扫描，做差分求出数组，做前缀和即可
注意要取模
其实$n log _n$也能过了

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

struct node
{
    int a, l, r;
} op[1000005];
int n, m;
ll ct[2][1000005], mod = 1e9 + 7;

void add(int k, int x, ll v)
{
    for (; x <= m; x += x & -x)
    {
        ct[k][x] += v;
        if (ct[k][x] >= mod)
            ct[k][x] -= mod;
        if (ct[k][x] < 0)
            ct[k][x] += mod;
    }
}
ll query(int k, int x)
{
    ll ans = 0;
    for (; x; x -= x & -x)
    {
        ans += ct[k][x];
        if (ans >= mod)
            ans -= mod;
        if (ans < 0)
            ans += mod;
    }
    return ans;
}

int main()
{
    freopen("operate.in", "r", stdin);
    freopen("operate.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &op[i].a, &op[i].l, &op[i].r);
    }
    add(0, 1, 1);
    add(0, m + 1, -1);
    for (int i = m; i >= 1; --i)
    {
        if (op[i].a == 2)
        {
            ll t = query(0, i);
            add(0, op[i].l, t);
            add(0, op[i].r + 1, -t);
        }
    }
    for (int i = 1; i <= m; ++i)
    {
        if (op[i].a == 1)
        {
            ll t = query(0, i);
            ct[1][op[i].l] += t;
            ct[1][op[i].r + 1] -= t;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        ct[1][i] += ct[1][i - 1];
        if (ct[1][i] >= mod || ct[1][i] < 0)
            ct[1][i] %= mod;
        if (ct[1][i] < 0)
            ct[1][i] += mod;
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        ans ^= ct[1][i];
    }
    cout << ans << endl;
    return 0;
}

T2

50
定义$dp[i][j]$表示在第一天已经用了j小时，完成i子树的题目最小还要多少天多少小时(pair类型)
考虑m较小，直接暴力枚举m!即可
100
状压所有儿子，$dp[i][j]$为在第一天用了j个小时，完成i集合内的子树中的题目至少需要多少天多少小时
向后转移即可

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

int cnt, head[5005], w[5005], t[5005], n, h;
pii dp[5005][25], f[1025][25];
vector<int> v[5005];

void update(pii x, pii &y)
{
    if (y.first == -1)
        y = x;
    else if ((y.first == x.first && y.second > x.second) || y.first > x.first)
        y = x;
}

void dfs(int x)
{
    for (int i = 0; i < w[x]; i++)
    {
        dfs(v[x][i]);
    }
    int full = (1 << w[x]) - 1;
    for (int i = 0; i <= full; ++i)
    {
        for (int j = 0; j < h; ++j)
        {
            f[i][j] = pii(-1, -1);
        }
    }
    for (int i = 0; i + t[x] < h; ++i)
    {
        f[0][i] = pii(0, i + t[x]);
    }
    f[0][h - t[x]] = pii(1, 0);
    for (int i = h - t[x] + 1; i < h; ++i)
    {
        if (t[x] < h)
            f[0][i] = pii(1, t[x]);
        else
            f[0][i] = pii(2, 0);
    }
    for (int s = 0; s < h; ++s)
    {
        for (int mask = 0; mask <= full; ++mask)
        {
            for (int j = 0; j < w[x]; ++j)
            {
                if ((mask >> j) & 1)
                    continue;
                int a = f[mask][s].first + dp[v[x][j]][f[mask][s].second].first;
                int b = dp[v[x][j]][f[mask][s].second].second;
                update(pii(a, b), f[mask | (1 << j)][s]);
            }
        }
    }
    for (int i = 0; i < h; ++i)
        dp[x][i] = f[full][i];
}

int main()
{
    freopen("coding.in", "r", stdin);
    freopen("coding.out", "w", stdout);
    cin >> n >> h;
    for (int i = 1; i <= n; ++i)
        scanf("%d", &t[i]);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &w[i]);
        for (int j = 1; j <= w[i]; ++j)
        {
            int x;
            scanf("%d", &x);
            v[i].push_back(x);
        }
    }
    dfs(1);
    if (dp[1][0].second)
        dp[1][0].first++;
    cout << dp[1][0].first << endl;
    return 0;
}

T3

求出从s出发到每个点经过i条权值为x的边的最短路径
然后维护一个凸包（单调栈）即可（详见Day3-T1）
本题也可直接计算出每一个一次函数的作用范围，即$ij$与它的最右交点

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

struct node
{
    int Next, y, v;
} Pth[10005];

int cnt, head[505], n, m;
ll dis[505][505], INF = 0x3f3f3f3f3f3f3f3f;
bool v[505][505];
void add(int x, int y, int v)
{
    cnt++;
    Pth[cnt].Next = head[x];
    Pth[cnt].y = y;
    Pth[cnt].v = v;
    head[x] = cnt;
}
char s[10];

void spfa(int s)
{
    memset(dis, -1, sizeof dis);
    memset(v, 0, sizeof v);
    dis[s][0] = 0;
    queue<pii> q;
    q.push(pii(s, 0));
    while (!q.empty())
    {
        int x = q.front().first;
        int st = q.front().second;
        q.pop();
        if (st > 500)
            continue;
        v[x][st] = 0;
        for (int i = head[x]; i; i = Pth[i].Next)
        {
            int y = Pth[i].y;
            int nt = st;
            if (Pth[i].v == 0)
                nt++;
            if (dis[y][nt] == -1 || Pth[i].v + dis[x][st] < dis[y][nt])
            {
                dis[y][nt] = Pth[i].v + dis[x][st];
                if (!v[y][nt])
                {
                    q.push(pii(y, nt));
                    v[y][nt] = 1;
                }
            }
        }
    }
}

int main()
{
    freopen("dist.in", "r", stdin);
    freopen("dist.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int x, y, v;
        scanf("%d%d%s", &x, &y, s + 1);
        if (s[1] == 'x')
        {
            add(x, y, 0);
        }
        else
        {
            sscanf(s + 1, "%d", &v);
            add(x, y, v);
        }
    }
    int q;
    cin >> q;
    while (q--)
    {
        int s, t;
        scanf("%d%d", &s, &t);
        spfa(s);
        int fl = 0;
        for (int i = 0; i <= n; ++i)
        {
            if (dis[t][i] != -1)
                fl = 1;
        }
        if (fl == 0)
        {
            puts("0 0");
            continue;
        }
        else if (dis[t][0] == -1)
        {
            puts("inf");
            continue;
        }
        else
        {
            ll ans2 = 0, ans1 = 0, last = 0, naxl;
            for (int i = 0; i <= n; ++i)
            {
                ll l = 1, r = INF;
                if (dis[t][i] == -1)
                    continue;
                for (int j = 0; j < i; ++j)
                {
                    if (dis[t][j] == -1)
                        continue;
                    ll rs = (dis[t][j] - dis[t][i]) / (i - j);
                    if ((dis[t][j] - dis[t][i]) % (i - j) == 0)
                        rs--;
                    r = min(r, rs);
                }
                for (int j = i + 1; j <= n; ++j)
                {
                    if (dis[t][i] == -1)
                        continue;
                    ll rs = (dis[t][i] - dis[t][j]) / (j - i);
                    if ((dis[t][i] - dis[t][j]) % (j - i))
                        rs++;
                    l = max(l, rs);
                }
                if (l <= r)
                {
                    if (i)
                        ans1 += (r - l + 1), ans2 += (ll)(r - l + 1) * dis[t][i] + (ll)i * (l + r) * (r - l + 1) / 2;
                    else
                        ans1++, ans2 += dis[t][i];
                }
            }
            printf("%lld %lld\n", ans1, ans2);
        }
    }
    return 0;
}

背包

梦幻岛宝珠
Cutting Grass(Topcoder SRM 517 DIV2 1000 CuttingGrass)
Codeforces 808E Selling Souvenirs
hdu6125 Free from square

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