Preface
警钟长鸣，经典一个变量拿来跑两次循环然后挂了看不出来，主要这种睿智错误只有像我这种把循环变量声明在开头的人才会犯
当时看了半天没看出来红温了，还把队友都摇过来看，然后三个人全红温了
直到最后瞎JB assert 了半天才发现这个问题，然后罚时爆炸，会的题也没时间写了，直接掉大分
Cake
这题队友扔给我的就是转化后的题意，给一棵树每个点有个点权，定义一条根到叶子的路径的权值为路径上所经点权值的最小值；先手要最大化这个值，后手要最小化这个值
首先叶子节点的权值就是初始的点权，然后考虑将树分层，在先手对应的层先手肯定是选一个值最大的子树，在后手对应的层后手肯定是选一个值最小的子树，简单 DP 处理即可
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
int t,n,x,y,z; long double a[N],f[N]; vector <pi> v[N];
inline void DFS(CI now=1,CI fa=0,CI player=0,CI sum=0,CI len=0)
{
if (len==0) a[now]=1e9; else a[now]=1.0L*sum/len;
bool is_leaf=1;
if (player) f[now]=1e9; else f[now]=0;
for (auto [to,w]:v[now]) if (to!=fa)
{
is_leaf=0;
DFS(to,now,player^1,sum+w,len+1);
if (player) f[now]=min(f[now],f[to]);
else f[now]=max(f[now],f[to]);
}
if (is_leaf) f[now]=a[now]; else f[now]=min(f[now],a[now]);
}
int main()
{
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) v[i].clear();
for (i=1;i<n;++i) scanf("%d%d%d",&x,&y,&z),v[x].push_back(pi(y,z)),v[y].push_back(pi(x,z));
DFS(); printf("%.12Lf\n",f[1]);
}
return 0;
}
Cake 2
算区域数量考虑用平面图的欧拉定理，求出顶点数和边数后可以很容易算出区域数
令 \(k=\min(k,n-k)\)，答案为 \(n\times k+1\)
#include <bits/stdc++.h>
int main() {
int64_t n, k;
std::cin >> n >> k;
if(k + k > n) k = n - k;
if(k + k == n) {
std::cout << n << char(10);
} else {
int64_t ans = 1 + n * k;
std::cout << ans << char(10);
}
return 0;
}
Puzzle: Wagiri
先保留所有黑边跑一个边双，然后把桥全部断开
此时考虑用白边把原本不连通的连通块连接，根据最终得到的图的连通性判定是否有解即可
#include <bits/stdc++.h>
namespace Tarjan {
const int MAXN = 100020;
const int MAXM = 400020;
struct Edge {
int to, next, id;
bool cut;
} edge[MAXM];
int head[MAXN], tot = 0;
int Low[MAXN], DFN[MAXN], Stack[MAXN];
int Index, top;
bool Instack[MAXN];
bool cut[MAXN];
int add_block[MAXN];
int bridge;
void add_edge(int u, int v, int id) {
edge[tot].to = v;
edge[tot].next = head[u];
edge[tot].cut = false;
edge[tot].id = id;
head[u] = tot++;
}
void Tarjan(int u, int pre) {
int v;
Low[u] = DFN[u] = ++Index;
Stack[top++] = u;
Instack[u] = true;
int son = 0;
int pre_cnt = 0;
for(int i = head[u]; i != -1; i = edge[i].next) {
v = edge[i].to;
if(v == pre && pre_cnt == 0) { pre_cnt++; continue; }
if(!DFN[v]) {
son++;
Tarjan(v, u);
if(Low[u] > Low[v]) Low[u] = Low[v];
if(Low[v] > DFN[u]) {
bridge++;
edge[i].cut = true;
edge[i^1].cut = true;
}
if(u != pre && Low[v] >= DFN[u]) {
cut[u] = true;
add_block[u]++;
}
} else
if(Low[u] > DFN[v]) Low[u] = DFN[v];
}
if(u == pre && son > 1) cut[u] = true;
if(u == pre) add_block[u] = son - 1;
Instack[u] = false;
top--;
}
void init() {
memset(DFN, 0, sizeof(DFN));
memset(Instack, false, sizeof(Instack));
memset(add_block, 0, sizeof(add_block));
memset(cut, false, sizeof(cut));
Index = top = 0;
bridge = 0;
tot = 0;
memset(head, -1, sizeof(head));
}
}
int n, m;
std::vector<std::pair<int, int>> Lun, Qie, Ans;
int fa[100010], siz[100010];
int father(int i) {
if(fa[i] == i) return i;
return fa[i] = father(fa[i]);
}
void unionn(int a, int b) {
a = father(a), b = father(b);
if(a == b) return ;
if(siz[a] < siz[b]) std::swap(a, b);
fa[b] = a; siz[a] += siz[b]; return ;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin >> n >> m;
for(int i = 1; i <= n; ++i) fa[i] = i, siz[i] = 1;
for(int i = 0, u, v; i < m; ++i) {
static std::string type; std::cin >> u >> v >> type;
if(type[0] == 'L') Lun.emplace_back(u, v);
else Qie.emplace_back(u, v);
}
Tarjan::init();
for(int i = 0; i < Lun.size(); ++i) {
auto [u, v] = Lun[i];
Tarjan::add_edge(u, v, i);
Tarjan::add_edge(v, u, -1);
}
for(int i = 1; i <= n; ++i) if(!Tarjan::DFN[i]) Tarjan::Tarjan(i, i);
for(int i = 1; i <= n; ++i) for(int j = Tarjan::head[i]; j != -1; ) {
auto [to, next, id, cut] = Tarjan::edge[j];
if(id < 0 || cut) { j = next; continue; }
unionn(i, to); Ans.emplace_back(i, to);
j = next;
}
for(auto [u, v]: Qie) {
int f = father(u), t = father(v);
if(f == t) continue;
Ans.emplace_back(u, v);
unionn(u, v);
}
if(siz[father(1)] != n) {
std::cout << "NO\n";
return 0;
}
std::cout << "YES\n" << Ans.size() << char(10);
for(auto [u, v]: Ans) std::cout << u << " " << v << char(10);
return 0;
}
Challenge NPC 2
本来 20min 就能出的题硬是把我们队整场罚时搞炸了，最大战犯没得洗
对于某棵树，我们先求出它的直径 \(d\)，显然若 \(d\ge 4\) 则我们始终存在如下构造方案：
- 先依次将深度为 \(2,4,6,\dots\) 层的所有点选上
- 再依次将深度为 \(1,3,5,\dots\) 层的所有点选上
不难发现此时我们就得到了这棵树的一种合法的选法，而单个点的情况也可以视为合法，因此不合法的情况只有菊花图
手玩后发现可以给每个菊花图分为两层，如果有两个及以上的菊花图那我们依次先选第一层的所有点，再选第二层的所有点即可
否则我们可以从合法的树中选一个点补到单个菊花图的两层之间，如果不存在可以补上的点（即整个图只有一棵树且其为菊花图）则无解
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
int t,n,m,x,y,vis[N],mx,pos; vector <int> v[N],bkt[N];
inline void DFS1(int now,CI fa=0,CI len=1)
{
vis[now]=1; if (len>mx) mx=len,pos=now;
for (auto to:v[now]) if (to!=fa) DFS1(to,now,len+1);
}
inline void DFS2(CI now,CI fa=0,CI dep=1)
{
bkt[dep].push_back(now);
for (auto to:v[now]) if (to!=fa) DFS2(to,now,dep+1);
}
int main()
{
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) v[i].clear(),vis[i]=0;
for (i=1;i<=m;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
vector <int> valid,l1,l2; int cnt=0,trees=0;
for (i=1;i<=n;++i) if (!vis[i])
{
++trees; mx=0; DFS1(i); mx=0; DFS1(pos);
if (mx==1) valid.push_back(i); else
if (mx>=4)
{
DFS2(pos);
for (j=2;j<=mx;j+=2)
for (auto x:bkt[j]) valid.push_back(x);
for (j=1;j<=mx;j+=2)
for (auto x:bkt[j]) valid.push_back(x);
for (j=1;j<=mx;++j) bkt[j].clear();
} else
if (mx==2)
{
++cnt; l1.push_back(pos);
for (auto x:v[pos]) l2.push_back(x);
} else
{
++cnt; int center=0;
for (auto x:v[pos]) center=x;
l1.push_back(center);
for (auto x:v[center]) l2.push_back(x);
}
}
if (trees==1&&cnt==1) { puts("-1"); continue; }
vector <int> ans;
if (cnt==0) ans=valid; else
if (cnt>=2)
{
for (auto x:l1) ans.push_back(x);
for (auto x:l2) ans.push_back(x);
for (auto x:valid) ans.push_back(x);
} else
{
for (auto x:l1) ans.push_back(x);
ans.push_back(valid.back()); valid.pop_back();
for (auto x:l2) ans.push_back(x);
for (auto x:valid) ans.push_back(x);
}
for (auto x:ans) printf("%d ",x); putchar('\n');
}
return 0;
}
Genshin Impact's Fault
签到，读懂题意即可
#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int t,n,pfx[N]; char s[N];
int main()
{
for (scanf("%d",&t);t;--t)
{
RI i; scanf("%s",s+1); n=strlen(s+1); bool flag=1;
for (i=1;i<=n;++i) pfx[i]=pfx[i-1]+(s[i]=='3');
for (i=10;i<=n;++i) if (pfx[i]-pfx[i-10]==10) { flag=0; break; }
if (!flag) { puts("invalid"); continue; }
for (i=1;i<=n;++i) pfx[i]=pfx[i-1]+(s[i]=='5'||s[i]=='U');
for (i=90;i<=n;++i) if (pfx[i]-pfx[i-90]==0) { flag=0; break; }
if (!flag) { puts("invalid"); continue; }
int lst=-1; for (i=1;i<=n;++i)
if (s[i]=='5'||s[i]=='U')
{
if (lst==-1) { lst=i; continue; }
if (s[lst]=='5'&&s[i]=='5') { flag=0; break; }
lst=i;
}
puts(flag?"valid":"invalid");
}
return 0;
}
Intersecting Intervals
徐神看一眼就会了，可惜因为我拉了全队帮我看 F 的唐氏错误，导致最后没写完
考虑将题意转化为有个人在格子上走路，每次只能往左、右、下的某个方向走
以每层往下走的位置为关键点进行 DP，即令 \(f_{i,j}\) 表示处理了前 \(i\) 行，其中第 \(i\) 行是在第 \(j\) 个位置往下走时的最大贡献
转移时考虑枚举上一行往下走的位置，预处理出从某个点开始只向左/只向右得到的最大贡献，写出 DP 式子后发现可以很容易用前/后缀 \(\max\) 优化
这种做法和题解中本质等价，但个人认为更好理解，不愧是徐神
#include <bits/stdc++.h>
#define int int64_t
inline void chkmx(int &a, const int &b) {
if(b > a) a = b;
}
void work() {
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int>> a(n, std::vector<int>(m, 0x8000000000000000)), lmax = a, rmax = a, ldp = a, rdp = a;
for(auto &a: a) for(auto &a: a) std::cin >> a;
for(int i = 0, s; i < n; ++i) {
for(int j = 0, s = 0; j < m; ++j)
lmax[i][j] = s = std::max(int(0), s + a[i][j]);
for(int j = m - 1, s = 0; j >= 0; --j)
rmax[i][j] = s = std::max(int(0), s + a[i][j]);
}
for(int j = 0; j < m; ++j) {
rdp[0][j] = ldp[0][j] = a[0][j];
// if(j > 0) rdp[0][j] += lmax[0][j - 1];
// if(j < m - 1) ldp[0][j] += rmax[0][j + 1];
}
auto safe_get = [&](const std::vector<std::vector<int>> &a, int i, int j) -> int {
if(i < 0 || i >= n || j < 0 || j >= m) return 0;
return a[i][j];
};
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(j) chkmx(rdp[i][j], rdp[i][j - 1] + a[i][j]);
if(i < n - 1) {
chkmx(ldp[i + 1][j], rdp[i][j] + a[i + 1][j] + safe_get(rmax, i, j + 1) + safe_get(rmax, i + 1, j + 1));
chkmx(rdp[i + 1][j], rdp[i][j] + a[i + 1][j] + safe_get(rmax, i, j + 1) + safe_get(lmax, i + 1, j - 1));
}
}
for(int j = m - 1; j >= 0; --j) {
if(j < m - 1) chkmx(ldp[i][j], ldp[i][j + 1] + a[i][j]);
if(i < n - 1) {
chkmx(ldp[i + 1][j], ldp[i][j] + a[i + 1][j] + safe_get(lmax, i, j - 1) + safe_get(rmax, i + 1, j + 1));
chkmx(rdp[i + 1][j], ldp[i][j] + a[i + 1][j] + safe_get(lmax, i, j - 1) + safe_get(lmax, i + 1, j - 1));
}
}
}
// for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j)
// std::cout << std::max(ldp[i][j], ldp[i][j]) << char(j == m - 1 ? 10 : 32);
int ans = 0x8000000000000000;
for(int j = 0; j < m; ++j) chkmx(ans, ldp[n - 1][j]), chkmx(ans, rdp[n - 1][j]);
std::cout << ans << char(10);
}
int32_t main() {
std::ios::sync_with_stdio(false);
int T; std::cin >> T; while(T--) work();
return 0;
}
Stone Merging
ORZ 祁神，在我白兰红温的时候把这个题 solo 掉了，好像是个比较恶心的分讨，而我题目都没看来着
#include<bits/stdc++.h>
using namespace std;
int n, k;
struct Node{
int m;
vector<int> vec;
};
vector<Node> ans;
int pile;
void merge(int id, int x, vector<int> &vec, int bis){
vector<int> res;
for (int i=1; i<=x; ++i){
res.push_back(vec.back());
vec.pop_back();
}
ans.push_back(Node{x, res});
pile -= (x-1);
vec.push_back(n+2*id+bis);
}
void solve(){
cin >> n >> k;
vector<int> A(n+1), cnt(k+1);
vector<int> is2, n2;
for (int i=1; i<=n; ++i){
cin >> A[i];
if (2==A[i]) is2.push_back(i);
else n2.push_back(i);
if (A[i]<=k) ++cnt[A[i]];
}
int x=-1;
for (int i=k; i>=2; --i){
if (0==cnt[i]){x=i; break;}
}
if (-1==x){
bool ok=true;
for (int i=1; i<=n; ++i) if (A[i]!=n){ok=false; break;}
if (ok && k==n){
cout << "1\n" << n;
for (int i=1; i<=n; ++i) cout << ' ' << i;
cout << '\n';
}else cout << "-1\n";
return ;
}
ans.clear();
pile=n;
int id;
for (id=1; pile>x; ++id){
if (n2.size()>=2) merge(id, 2, n2, 0);
else{
int sz2=is2.size();
int bis=(n2.empty() ? 0 : 1);
if (sz2-x+bis >= 2) merge(id, 3, is2, 0);
else if (sz2-x+bis == 1) merge(id, 2, is2, -1);
}
}
vector<int> res;
for (int x : is2) res.push_back(x);
for (int x : n2) res.push_back(x);
ans.push_back(Node{x, res});
cout << ans.size() << '\n';
for (auto [m, vec] : ans){
cout << m;
for (int x : vec) cout << ' ' << x;
cout << '\n';
}
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t; while (t--) solve();
return 0;
}
Postscript
感觉越加训越唐了，怎么回事呢
标签：std,int,auto,++,多校,back,2024,牛客,now From： https://www.cnblogs.com/cjjsb/p/18337327