总结

本场比赛很不负责对待

暴力都没怎么打

一个半小时后才开始打题

很悲剧的只有 \(23+11+36=70\) 分

\(T1\) 4300. 装饰大楼

题目

略

思路

很无聊的找规律题

考场弃疗

\(Code\)

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;

const int N = 1e6 + 5;
int n , a[N] , s , x , t;
LL ans;

int main()
{
    freopen("building.in" , "r" , stdin);
    freopen("building.out" , "w" , stdout);
    scanf("%d" , &n);
    for(register int i = 1; i < n; i++) scanf("%d" , &a[i]);
    for(register int i = 1; i < n; i++)
    {
        ans += (LL)s + 1;
        if (a[i] <= s + 1) ans--;
        s = max(s , a[i]);
    }
    ans += (LL)s + 1;
    s = 0;
    for(register int i = 1; i < n; i++)
    {
        if (a[i] - x > 2)
        {
            printf("0");
            return 0;
        }
        else if (a[i] - x == 2)
        {
            s++;
            if (s == 1) t = i;
        }
        if (s >= 2)
        {
            printf("0");
            return 0;
        }
        x = max(x , a[i]);
    }
    if (s == 1)
    {
        x = s = 0;
        for(register int i = 1; i < t; i++)
            if (a[i] > x) x = a[i] , s = i;
        ans = t - s;
    }
    printf("%lld" , ans);
}

\(T2\) 4301. 备用钥匙

题目

略

思路

奇怪的 \(dp\) 题

很容易想到按时间排序

相邻两个时间分离开和回来四种情况讨论

不用钥匙的直接加，记到 \(ans\) 里

单独用一个钥匙的另开数组记需要钥匙者产生的贡献，记到 \(c\) 里

两个都需要就弄出链来并算给他们两把钥匙能获得的贡献，记到 \(se\) 里

然后调整 \(dp\) 的顺序

链上的连在一起

设 \(f_{i,j}\) 表示前 \(1..i\) 中选 \(j\) 个人且强行让 \(i\) 也持有钥匙的最大答案， \(g_{i,j}=max_{k=1}^{i} f_{k,j}\)

那么转移：\(f_{i,j}=max{f_{i-1,j-1}+se[i],g[i-2][j-1]}+c[i]\)

最终 \(ans=ans+g[n][k]\)

\(Code\)

#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 2005;
int n , m , k , tot , s[N] , se[N] , sz[N] , c[N] , ans , pre[N] , nxt[N] , f[N][N] , g[N][N] , vis[N] , b[N];

struct node{
    int id , t , s;
}a[2 * N];

inline bool cmp(node x , node y){return x.t < y.t;}

int main()
{
    freopen("key.in" , "r" , stdin);
    freopen("key.out" , "w" , stdout);
    scanf("%d%d%d" , &n , &m , &k);
    int p , q;
    for(register int i = 1; i <= n; i++)
    {
        scanf("%d%d" , &p , &q);
        a[++tot].id = i , a[tot].t = p , a[tot].s = 1;
        a[++tot].id = i , a[tot].t = q , a[tot].s = 2;
    }
    sort(a + 1 , a + tot + 1 , cmp);
    ans = a[1].t + m - a[tot].t;    

    for(register int i = 1; i <= tot; i++)
    {
        if (a[i].s == 2 && a[i + 1].s == 1) ans += a[i + 1].t - a[i].t;
        if (a[i].id == a[i + 1].id) s[a[i].id] += a[i + 1].t - a[i].t;
        else if (a[i].s == 1 && a[i + 1].s == 1) s[a[i].id] += a[i + 1].t - a[i].t;
        else if (a[i].s == 2 && a[i - 1].s == 2) s[a[i].id] += a[i].t - a[i - 1].t;
        else if (a[i].s == 1 && a[i + 1].s == 2)
        {
            pre[a[i + 1].id] = a[i].id;
            nxt[a[i].id] = a[i + 1].id;
            sz[a[i + 1].id] = a[i + 1].t - a[i].t;
        }
    }

    int to;
    tot = 0;
    for(register int i = 1; i <= n; i++)
    if (!vis[i])
    {
        to = i;
        while (pre[to]) to = pre[to];
        while (to) b[++tot] = to , vis[to] = 1 , to = nxt[to];
    }

    for(register int i = 1; i <= n; i++) c[i] = s[b[i]] , se[i] = sz[b[i]];
    f[1][1] = g[1][1] = c[1];
    for(register int i = 2; i <= n; i++)
    {
        g[i][1] = max(g[i - 1][1] , f[i][1] = c[i]);
        for(register int j = 2; j <= k; j++)
            g[i][j] = max(g[i - 1][j] , f[i][j] = max(f[i - 1][j - 1] + se[i] , g[i - 2][j - 1]) + c[i]);
    }

    printf("%d" , ans + g[n][k]);
}

\(T3\) 4302. IOIOI卡片占卜

题目

略

思路

牛逼得不得了的操作：记给定的序列 \(I\) 为 \(1\)，\(O\) 为 \(0\)。让这个序列相邻两个异或

于是区间 \([l..r]\) 翻转变为异或单点 \(l-1\) 和 \(r\) （亲手模拟看看）

异或后的序列只剩 \(4\) 个 \(1\)，让这四个 \(1\) 变 \(0\) 的最少代价即为答案

那么我们把 \(l-1\) 和 \(r\) 连边，边权为 \(r-l+1\)，表示 \(l-1\) 到 \(r\) 的最小代价为 \(r-l+1\)

因为一次翻一个区间，即转化后的一次翻两个点，所以现在要使 \(4\) 个 \(1\) 配对

使他们最短路的和最小即为答案

\(Code\)

#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;

const int N = 5e5 + 5;
int a , b , c , d , e , vis[N] , h[N] , tot , n;
LL dis[N] , ans;

struct edge{
    int nxt , to , w;
}E[2 * N];

struct node{
    int id;
    LL d;
    bool operator < (node c) const
    {
        return d > c.d;
    }
};

inline void add(int x , int y , int z)
{
    E[++tot].to = y;
    E[tot].w = z;
    E[tot].nxt = h[x];
    h[x] = tot;
}

priority_queue<node> Q;

inline LL dij(int s , int t)
{
    memset(vis , 0 , sizeof vis);
    memset(dis , 60 , sizeof dis);
    while (!Q.empty()) Q.pop();
    dis[s] = 0;
    Q.push((node){s , dis[s]});
    node x;
    while (!Q.empty())
    {
        x = Q.top();
        Q.pop();
        if (vis[x.id]) continue;
        vis[x.id] = 1;
        if (x.id == t) break;
        for(register int i = h[x.id]; i; i = E[i].nxt)
        {
            int v = E[i].to;
            if (dis[x.id] + E[i].w < dis[v])
            {
                dis[v] = dis[x.id] + E[i].w;
                Q.push((node){v , dis[v]});
            }
        }
    }
    return dis[t];
}

int main()
{
    freopen("card.in" , "r" , stdin);
    freopen("card.out" , "w" , stdout);
    scanf("%d%d%d%d%d" , &a , &b , &c , &d , &e);
    scanf("%d" , &n);
    int l , r;
    for(register int i = 1; i <= n; i++)
    {
        scanf("%d%d" , &l , &r);
        l--;
        add(l , r , r - l) , add(r , l , r - l);
    }
    ans = min(dij(a , a + b) + dij(a + b + c , a + b + c + d) , dij(a , a + b + c) + dij(a + b , a + b + c + d));
    ans = min(ans , dij(a , a + b + c + d) + dij(a + b , a + b + c));
    if (ans >= 4340410370284600380) printf("-1");
    else printf("%lld" , ans);
}