总结
本场比赛很不负责对待
暴力都没怎么打
一个半小时后才开始打题
很悲剧的只有 (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);
}