丽泽普及2022交流赛day15 社论
前言
太牛逼了，补完我一定放代码 .
orz 越看越牛逼 orz .
时间复杂度都是口胡，不要信 .
以下是目录
缺省源
/*
_/_/_/_/ _/_/_/_/_/ _/_/_/
_/ _/ _/ _/ _/
_/ _/ _/ _/ _/
_/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/_/
_/_/_/_/ _/_/ _/_/_/_/_/
_/_/_/_/ _/ _/ _/ _/
_/ _/ _/ _/ _/_/ _/_/
_/ _/ _/_/ _/ _/_/ _/
_/ _/ _/ _/ _/ _/
_/ _/ _/_/ _/ _/
_/ _/ _/ _/ _/ _/
_/_/_/_/ _/ _/ _/ _/
_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
_/ _/ _/
_/ _/ _/
_/ _/ _/_/_/_/
_/ _/ _/
_/ _/ _/
_/ _/_/_/_/_/ _/_/_/_/_/
_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
_/ _/ _/
_/ _/ _/
_/ _/ _/_/_/_/
_/ _/ _/
_/ _/ _/
_/ _/_/_/_/_/ _/_/_/_/_/
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
前排膜拜 SoyTony
A
题面
小 S 手上有一个长度为 \(n\) 的单词。
现在，小 S 发现这个单词有M处被污染了（用 # 代替），已经看不出原来是什么了。
现在知道每个被污染的地方都有 \(K\) 个备选的可能字母。
现在，小 S 想要知道，在所有可能的单词里面，字典序第 \(X\) 小的是哪个？
题解
\(X-1\) 分解成 \(K\) 进制然后选 .
时间复杂度 \(O(X\log K)\) .
题解写的谔分 
代码
不知道为什么有人挂 \(60pts\) .
这题我倒是过得挺快，其他题全他妈挂飞 /ll.
using namespace std;
const int N = 1e5 + 500;
int n, m, k, x, cc;
string s;
struct Node
{
int pos;
string val;
}Q[N];
vector<int> vec;
int main()
{
scanf("%d%d%d%d", &n, &m, &k, &x); --x;
cin >> s; int l = s.length();
for (int i=0; i<l; i++)
if (s[i] == '#') Q[++cc].pos = i;
for (int i=1; i<=cc; i++)
{
cin >> Q[i].val;
sort(Q[i].val.begin(), Q[i].val.end());
}
for (int i=cc; i>=1; i--)
{
int now = x % k;
s[Q[i].pos] = Q[i].val[now];
x /= k;
}
cout << s << "\n";
return 0;
}
B
题面
一棵有点权的树，定义一条路径的权值是点权积除以点数量 .
求权值最小的路径权值 .
题解
牛逼结论题 .
SoyTony 说 APJ 说是屑题
显然有 \(1\) 都选上 .
然后可以选一个 \(2\)，要不然答案会更劣 .
于是就随便做了 .
stO SoyTony Orz
时间复杂度 \(O(n)\) .
代码
看 SoyTony 的博客 .
枚举二，然后贡献分两半 .
完了 .
似乎错了，看 SoyTony 的吧 qwq
using namespace std;
inline int chkmin(int& a, const int& b){if (a > b) a = b; return a;}
inline int chkmax(int& a, const int& b){if (a < b) a = b; return a;}
const int N = 1e6 + 500, INF = 0x3f3f3f3f;
int n, v[N], f[N][2], g[N], ans1, ans2;
vector<int> G[N];
inline void addedge(int u, int v){G[u].emplace_back(v);}
inline void ade(int u, int v){addedge(u, v); addedge(v, u);}
void dfs1(int u, int fa)
{
int fst=0, sec=0;
for (int v : G[u])
{
if (v == fa) continue;
dfs1(v, u);
if (f[v][0] > fst){sec = fst; fst = f[v][0];}
else if (f[v][9] > sec) sec = f[v][0];
}
if (v[u] == 1){f[u][0] = fst+1; if (sec) f[u][1] = sec+1;}
}
void dfs2(int u, int fa)
{
if (v[fa] == 1)
{
g[u] = f[fa][f[u][0]+1 == f[fa][0]];
chkmax(g[u], g[fa]+1);
}
for (int v : G[u]) if (v != fa) dfs2(v, u);
}
void dfs3(int u, int fa)
{
if (v[u] == 1) chkmax(ans1, max(f[u][0]+f[u][1]-1, f[u][0]+g[u]));
else if (v[u] == 2)
{
int maxn = 0;
for (int v : G[u])
if (v != fa) chkmax(maxn, f[v][0]);
chkmax(ans2, max(maxn+f[u][1]-1, maxn+g[u]));
}
for (int v : G[u]) if (v != fa) dfs3(v, u);
}
int main()
{
scanf("%d", &n);
for (int i=1, u, v; i<n; i++) scanf("%d%d", &u, &v), ade(u, v);
int minn = INF;
for (int i=1; i<=n; i++) scanf("%d", v+i), chkmin(minn, v[i]);
if (minn > 1){printf("%d/1\n", minn); return 0;}
dfs1(1, 0); dfs2(1, 0); dfs3(1, 0);
++ans2;
if (ans1 * 2 >= ans2) printf("1/%d\n", ans1);
else
{
if (ans2 & 1) printf("1/%d\n", ans2>>1);
else printf("2/%d\n", ans2);
} return 0;
}
C
题面
小 S 在玩一个叫丢手绢的游戏 .
一共 \(n\) 个小朋友围成一圈，其中第 \(i\) 个小朋友的能力值是 \(P_i\) .
小 S 一共会丢 \(n\) 个手绢，其中第 \(i\) 个的能力值是 \(V_i\)，且在丢第 \(i\) 个手绢的时候，他会先站在第 \(A_i\) 个小朋友身后。如果当前这个小朋友手上没有手绢，他就会把当前这个手绢交给这个小朋友。否则，他就会走向下一个人 .
现在，小 S 想要让尽量多的人得到的手绢能力值比他本身的能力值大。小 S 可以以任意顺序发放手绢 .
请问这个最大值是多少？
题解
链做法显然，就是随便贪心一下 .
大眼观察，可以发现必然存在一个位置 \(pos\) 可以把小朋友破环成链，于是我们只需找到这个位置 .
如果能破显然意味着没有手绢会经过 \(pos\to pos+1\)（模意义）
令 \(\Delta(l,r)\) 表示区间 \([l,r]\) 内手绢数量减小朋友数量 .
于是：
\]
\(j\) 是一个位置 .
然后分类推一下可以知道 \(\Delta(0,i)\) 最小 .
于是扫一遍就完了 .
时间复杂度 \(O(n\log n)\) .
代码
// set
using namespace std;
inline int chkmin(int& a, const int& b){if (a > b) a = b; return a;}
inline int chkmax(int& a, const int& b){if (a < b) a = b; return a;}
const int N = 5e5+500, INF = 0x3f3f3f3f;
int n, a[N], p[N], delta[N];
vector<int> c[N]; // children
set<int> s;
int main()
{
scanf("%d", &n);
for (int i=1; i<=n; i++) scanf("%d", a+i);
for (int i=1; i<=n; i++) scanf("%d", p+i);
for (int i=1, x; i<=n; i++) scanf("%d", &x), c[a[i]].emplace_back(x);
for (int i=1; i<=n; i++) delta[i] = delta[i-1] + c[i].size() - 1;
int minn = 0x3f3f3f3f, pos = 0, ans = 0;
for (int i=1; i<=n; i++)
if (minn > delta[i]){minn = delta[i]; pos = i;}
for (int i=1; i<=n; i++)
{
int tmp = (pos+i) % n;
if (!tmp) tmp = n;
for (int _ : c[tmp]) s.insert(_);
auto it = s.upper_bound(p[tmp]);
if (it == s.end()) s.erase(s.begin());
else{s.erase(it); ++ans;}
} printf("%d\n", ans);
return 0;
}
D
题面
给 \(n\) 个字符串 \(\{s_i\}\)，可以任意打乱，最小化 Trie 的节点总数 .
题解
两个字符串 \(s_1,s_2\) 存在字典树里需要 \(|s_1|+|s_2|-|s_{\operatorname{lcp}(s_1,s_2)}|\) 个节点 .
因为可以随机打乱，于是 \(\operatorname{lcp}\) 只需要记每个字母存在的次数即可 .
然后显然这个玩意可以拆成两两合并的形式，于是状压 dp 即可 .
口胡了一个 Trie 算法，好像和 Keven_He 写的一样，保龄力
（枚举子集是 \(O(3^n)\) 的）
时间复杂度 \(O(\text{能过})\) .
代码
using namespace std;
inline int chkmin(int& a, const int& b){if (a > b) a = b; return a;}
inline int chkmax(int& a, const int& b){if (a < b) a = b; return a;}
const int N = 17, M = 1e6+500, Sig = 33, INF = 0x3f3f3f3f;
int n, cnt[N][Sig], dp[1<<N], pre[Sig];
string s;
int main()
{
scanf("%d", &n);
for (int i=1; i<=n; i++)
{
cin >> s; int l = s.length();
s = "$" + s;
for (int j=1; j<=l; j++) ++cnt[i][s[j]-'a'];
}
for (int i=0; i<(1<<n); i++)
{
dp[i] = 0;
memset(pre, 0x3f, sizeof pre);
for (int j=1; j<=n; j++)
if (i & (1<<(j-1)))
for (int k=0; k<26; k++){dp[i] += cnt[j][k]; chkmin(pre[k], cnt[j][k]);}
int _ = 0;
for (int j=0; j<26; j++) _ += pre[j];
for (int j = i&(i-1); j ; j = i&(j-1)) chkmin(dp[i], dp[j] + dp[i^j] - _);
}
printf("%d\n", dp[(1<<n)-1]+1);
return 0;
}
最新文章
- UA模拟
- jQuery.fn.extend与jQuery.extend
- Android 问题流水总结
- LA 5009 (三分法求极值) Error Curves
- Side by Side Assembly介绍--manifest文件的使用
- Ext秒表
- k-近邻算法实例
- MyCat 启蒙：分布式系统的数据库架构演变
- RabbitMQ消息队列（七）：适用于云计算集群的远程调用(RPC)
- yum安装k8s集群(kubernetes)
- CentOS 7 Squid代理服务器正向代理-传统代理
- HDU1171将多个不同价值不同数量的器材尽可能按等价值均分 第一份的价值尽可能的大 所以sum/2对第二份进行01背包 使其价值尽可能的大
- Find the Missing Number II
- 20145333茹翔 Exp5 MSF基础应用
- Jquery中bind(), live(), on(), delegate()四种注册事件的优缺点，建议使用on（）
- plot sin 03-数据区域边界线的位置
- webpack和webpack-dev-server安装配置
- [EffectiveC++]item22：Declare data members private
- hdu1789 Doing Homework again(贪心+排序)
- 【IdentityServer4文档】- 支持协议