Codeforces Round 826 (Div.3)
A. Compare T-Shirt Sizes
题目大意
给你两个T恤的尺码，问你两个T恤的尺码的大小关系。尺码是有三种主要类型SML，分别代表Small，Medium，Large。SML的大小关系是S < M < L。Small和Large两种类型的尺码，可以在前面加上若干个X。X越多，对于S类型就越小，对于L类型就越大。
题解
主要是分类型讨论，然后判断大小关系。
- 如果两个T恤的类型字符串完全相同：那么这两个T恤的尺码大小相同。
- 如果两个T恤的类型字符串不同：
- 如果两个T恤的主要类型（SML）相同：
- S类型的T恤，X的个数越多，尺码越小。
- L类型的T恤，X的个数越多，尺码越大。
- 如果两个T恤的主要类型不同：
- 第一件T恤尺寸大于第二件T恤尺寸的条件是：
- 第一件T恤的主要类型是L
- 第一件T恤的主要类型是M，第二件T恤的主要类型是S
- 其他情况是第一件T恤尺寸小于第二件T恤尺寸。
- 第一件T恤尺寸大于第二件T恤尺寸的条件是：
- 如果两个T恤的主要类型（SML）相同：
参考代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
string a, b;
cin >> a >> b;
if(a == b) cout << "=\n";
else{
if(a.back() == b.back()){
if(a.back() == 'S'){
cout << (a.length() > b.length() ? "<" : ">") << endl;
}else{
cout << (a.length() > b.length() ? ">" : "<") << endl;
}
}else if(a.back() == 'L' or (a.back() == 'M' and b.back() == 'S')){
cout << ">" << endl;
}else{
cout << "<" << endl;
}
}
}
return 0;
}B. Funny Permutation
题目大意
给你一个长度为n，构造一个元素为1到n的排列p，使得这个排列满足以下条件：
- 对于任意的i，都有 。
- 对于任意一个i，都有 或者
题解
- 如果n为偶数，那么可以直接构造一个递减的排列， 。逆序之后因为偶数是放在奇数编号的位置，奇数都放在偶数编号位置，所以满足条件1。
- 如果n为奇数，那么可以将前面三个元素移动到末尾，。如果n等于3，那么无法构造出一个满足两个条件的排列，所以输出-1。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
if(n & 1){
if(n == 3) cout << -1 << endl;
else{
for(int i = 4; i <= n; ++i) cout << i << " ";
cout << "1 2 3" << endl;
}
}else{
for(int i = n; i >= 1; --i){
cout << i << " ";
}
cout << endl;
}
}
return 0;
}C. Minimize the Thickness
题目大意
给你一个长度为n的序列，序列中每个数都是正整数。现在需要将序列且分成若干个连续子序列。
- 每个子序列的和相同
- 原本的序列中的每个数，都必须在某个子序列中，并且仅在一个子序列中
然后让你求一个分割方法，使得分割之后的子序列中最长的子序列的长度（ans）最小。
题解
初始化ans = n。通过枚举第一个子序列的长度，枚举第一个子序列的和。然后对于每个，检查将序列分割成每个子序列和均为的情况是否存在，如果存在，那么将这种分割方法的最长长度更新到结果当中，ans = min(ans, len);。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int> arr(n + 1, 0);
vector<int> sum(n + 1, 0);
for(int i = 1; i <= n; ++i){
cin >> arr[i];
sum[i] = sum[i - 1] + arr[i];
}
int ans = n;
for(int i = 1; i <= n; ++i){
int ts = sum[i];
if(sum[n] % ts == 0){
int cnt = 0;
int len = i;
int pre = 0;
for(int j = 1; j <= n; ++j){
if(sum[j] % ts == 0){
++cnt;
len = max(len, j - pre);
pre = j;
}
}
if(cnt >= sum[n] / ts){
ans = min(ans, len);
}
}
}
cout << ans << endl;
}
return 0;
}D. Masha and a Beautiful Tree
题目大意
给你一个有 个叶子节点的满二叉树，数上的每个叶子节点上面都有一个值，这些值从左到右构成了一个从 到 的一个排列。
每次操作，你可以选择一个非叶子节点，交换其左右孩子子树。
问能否通过这样的操作，使得叶子节点上面的数值，从左到右构成一个递增的排列。如果能构成这样的排列，求最少的操作次数。
题解
可以从最深的节点开始考虑，在每个节点上标记他的子树的叶子节点的最小值和最大值区间，如果每个非叶子节点的左子树的叶子节点的最小值和最大值区间和右子树的叶子节点的最小值和最大值区间重叠，那么就不能将这个子树的叶子节点通过操作转化成一个连续递增的排列。如果这个非叶子节点的左子树的最大值小于右子树的最小值，那么就不需要交换这个节点的左子树和右子树。如果这个非叶子节点的左子树的最小值大于右子树的最大值，那么就需要在这个节点上进行一次左子树和右子树的交换。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int> arr(n);
for(auto& it: arr){
cin >> it;
--it;
}
auto&& dfs = [&](auto&& self, int l, int r) -> tuple<int, int, int>{
if(l == r){
return {arr[l], arr[r], 0};
}
auto [ll, lr, lo] = self(self, l, (l + r) / 2);
auto [rl, rr, ro] = self(self, (l + r) / 2 + 1, r);
int ml = min(ll, rl), mr = max(lr, rr);
int mo = 0;
if(lo == -1 or ro == -1){
return {ml, mr, -1};
}
else mo = lo + ro;
if(ll > rr){
return {ml, mr, mo + 1};
}else if(lr < rl){
return {ml, mr, mo};
}else{
return {ml, mr, -1};
}
};
auto [x, y, v] = dfs(dfs, 0, n - 1);
cout << v << endl;
}
return 0;
}E. Sending a Sequence Over the Network
题目大意
给你一个长度为n序列seq，问你能不能将序列seq分割成若干段，使得每段的左边或者右边伴随一个子段的长度。
题解
这个题目采用动态规划。dp[i]代表长度为i的前缀是否满足这样的分割条件。初始化dp为false，dp[0]为true。对于每个位置i，分别假定seq[i]为序列在i左边的序列长度，或者序列在i右边的序列长度。
那么转移方式就是：
if(arr[i] < i) dp[i] |= dp[i - arr[i] - 1];
if(arr[i] + i <= n) dp[i + arr[i]] |= dp[i - 1];最后检查dp[n]是否为true。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int> arr(n + 1, 0);
for(int i = 1; i <= n; ++i){
cin >> arr[i];
}
vector<int> dp(n + 1, 0);
dp[0] = 1;
for(int i = 1; i <= n; ++i){
if(arr[i] < i){
dp[i] = dp[i] | dp[i - arr[i] - 1];
}
if(arr[i] + i <= n){
dp[i + arr[i]] = dp[i + arr[i]] | dp[i - 1];
}
}
cout << (dp[n] ? "YES" : "NO") << endl;
}
return 0;
}
F. Multi-Colored Segments
题目大意
有n条带有颜色线段 , 对于每条线段，问离他最近的不同颜色的线段的距离。如果它与不同颜色线段相交，那么结果为0。
题解
考虑使用线段树来解决这个问题。线段树中的每个节点需要保存它所对应的区间的覆盖长度。线段树还需要具有以下功能：
- 将一个覆盖区间插入线段树
- 将一个覆盖区间从线段树中移除
- 查询区间内的覆盖长度
- 查询区间内的被覆盖的最左端点
- 查询区间内的被覆盖的最右端点
然后，开始动手写这个题
首先把所有的区间按照颜色分类，然后把所有的区间都放入线段树当中。
对于每个颜色，将此颜色的所有覆盖区间从线段树中移除。然后对于当前颜色的每一条覆盖区间，分别求当前区间覆盖的长度、当前区间左边的被覆盖的最右端点和当前区间右侧被覆盖的最左端点。最后将当前颜色的所有覆盖区间插入到线段树当中。
最后，需要注意的是，在处理线段树的时候，需要将区间的端点进行离散化。因为如果用动态开点的线段树会mle，别问我为什么会知道。
参考代码
#include <bits/stdc++.h>
using namespace std;
#define b2e(...) begin(__VA_ARGS__), end(__VA_ARGS__)
#define initIO() \
ios::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr); \
cout << fixed << setprecision(10)
#define debug(x...) \
do { \
cout << "\033[32;1m" << #x << " -> "; \
rd_debug(x); \
} while (0)
void rd_debug() { cout << "\033[39;0m" << endl; }
template <class T, class... Ts> void rd_debug(const T &arg, const Ts &...args) {
cout << arg << " ";
rd_debug(args...);
}
#define PF(x) ((x) * (x))
#define LF(x) ((x)*PF(x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const double eps = 1e-6;
const int MOD = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3fll;
#define LEFT (node[cur].l)
#define RIGHT (node[cur].r)
#define MID ((l + r) >> 1)
struct Node {
int l, r;
int lazy;
int len;
};
struct Seg {
Seg() : node(2) {
}
void add(int cur, int l, int r, int st, int ed, int tv) {
if (ed < l or r < st)
return;
if (st <= l && r <= ed) {
node[cur].lazy += tv;
if (node[cur].lazy > 0) {
node[cur].len = r - l + 1;
} else {
node[cur].len = 0;
if (LEFT)
node[cur].len += node[LEFT].len;
if (RIGHT)
node[cur].len += node[RIGHT].len;
}
return;
}
if (!LEFT) {
LEFT = node.size();
node.push_back({0, 0, 0, 0});
}
if (!RIGHT) {
RIGHT = node.size();
node.push_back({0, 0, 0, 0});
}
add(LEFT, l, MID, st, ed, tv);
add(RIGHT, MID + 1, r, st, ed, tv);
if (node[cur].lazy > 0) {
node[cur].len = r - l + 1;
} else {
node[cur].len = node[LEFT].len + node[RIGHT].len;
}
}
auto query(int cur, int l, int r, int st, int ed) -> int {
if (ed < l or r < st)
return 0;
if (node[cur].lazy) {
return min(r, ed) - max(l, st) + 1;
}
if(node[cur].len == 0)
return 0;
if (st <= l && r <= ed) {
return node[cur].len;
}
int ret = 0;
if (LEFT)
ret += query(LEFT, l, MID, st, ed);
if (RIGHT)
ret += query(RIGHT, MID + 1, r, st, ed);
return ret;
}
auto queryPosL(int cur, int l, int r, int st, int ed) -> int {
if (ed < l or r < st)
return -1;
if (node[cur].lazy) {
return max(l, st);
}
if(node[cur].len == 0) return -1;
if (st <= l && r <= ed) {
if (node[cur].lazy > 0)
return l;
if (LEFT) {
int ret = queryPosL(LEFT, l, MID, st, ed);
if (ret != -1)
return ret;
}
if (RIGHT) {
int ret = queryPosL(RIGHT, MID + 1, r, st, ed);
if (ret != -1)
return ret;
}
return -1;
}
int ret = -1;
if (LEFT)
ret = queryPosL(LEFT, l, MID, st, ed);
if (ret != -1)
return ret;
if (RIGHT)
ret = queryPosL(RIGHT, MID + 1, r, st, ed);
return ret;
}
auto queryPosR(int cur, int l, int r, int st, int ed) -> int {
if (ed < l or r < st)
return -1;
if (node[cur].lazy) {
return min(r, ed);
}
if(node[cur].len == 0) return -1;
if (st <= l && r <= ed) {
if (node[cur].lazy > 0)
return r;
if (RIGHT) {
int ret = queryPosR(RIGHT, MID + 1, r, st, ed);
if (ret != -1)
return ret;
}
if (LEFT) {
int ret = queryPosR(LEFT, l, MID, st, ed);
if (ret != -1)
return ret;
}
return -1;
}
int ret = -1;
if (RIGHT)
ret = queryPosR(RIGHT, MID + 1, r, st, ed);
if (ret != -1)
return ret;
if (LEFT)
ret = queryPosR(LEFT, l, MID, st, ed);
return ret;
}
vector<Node> node;
};
int main() {
initIO();
int t;
cin >> t;
Seg seg;
while (t--) {
int n;
cin >> n;
map<int, vector<tuple<int, int, int>>> mp;
vector<int> ans(n, inf);
vector<int> pos;
for (int i = 0; i < n; i++) {
int l, r, h;
cin >> l >> r >> h;
mp[h].push_back({l, r, i});
pos.push_back(l);
pos.push_back(r);
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
auto&& getPos = [&](int x) -> int{
return lower_bound(pos.begin(), pos.end(), x) - pos.begin() + 1;
};
for(auto& [h, v]: mp){
for(auto& [l, r, i]: v){
seg.add(1, 1, pos.size(), getPos(l), getPos(r), 1);
}
}
for(auto& [h, v] : mp) {
for (auto &[l, r, i] : v) {
seg.add(1, 1, pos.size(), getPos(l), getPos(r), -1);
}
for (auto &[l, r, i] : v) {
int qs = seg.query(1, 1, pos.size(), getPos(l), getPos(r));
if (qs > 0) {
ans[i] = 0;
} else {
int ql = seg.queryPosL(1, 1, pos.size(), getPos(r) + 1, pos.size());
if (ql != -1) {
ans[i] = min(ans[i], pos[ql - 1] - r);
}
int qr = seg.queryPosR(1, 1, pos.size(), 1, getPos(l) - 1);
if (qr != -1) {
ans[i] = min(ans[i], l - pos[qr - 1]);
}
}
}
for (auto &[l, r, i] : v) {
seg.add(1, 1, pos.size(), getPos(l), getPos(r), 1);
}
}
for(auto& [h, v] : mp) {
for (auto &[l, r, i] : v) {
seg.add(1, 1, pos.size(), getPos(l), getPos(r), -1);
}
}
for (auto &it : ans) {
cout << it << " ";
}
cout << '\n';
}
return 0;
}G. Multi-Colored Segments
题目大意
K住在一个有个节点的m条边的无向联通图的编号为的点。晚上，他有个朋友要从他家返回各自的家。有 （ ）个朋友没有车，这个人将会步行回家，如果没有其他人载他一程。其他有车的朋友可以载无限个朋友，但是有车的朋友回家的时候，只会走从K的家到他家的最短的一条路径。K希望你帮他算一下，最少有多少朋友需要步行回家。
题解
首先将没有车的朋友给他编号，分别是。因为比较小，我们就可以用个状态来代表每个有车的人回家的途中，可以捎上哪些朋友。
然后通过bfs来计算每个有车的人回家途中可以走的路线长度和每条路线可以捎的朋友的状态。
最后使用背包，根据每个有车的人能捎带的朋友的状态，来统计多个有车的人能捎的朋友的最大数量。从而得到需要步行回家的朋友的最少数量。
参考代码
#include <bits/stdc++.h>
using namespace std;
#define b2e(...) begin(__VA_ARGS__), end(__VA_ARGS__)
#define initIO() \
ios::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr); \
cout << fixed << setprecision(10)
#define debug(x...) \
do { \
cout << "\033[32;1m" << #x << " -> "; \
rd_debug(x); \
} while (0)
void rd_debug() { cout << "\033[39;0m" << endl; }
template <class T, class... Ts> void rd_debug(const T &arg, const Ts &...args) {
cout << arg << " ";
rd_debug(args...);
}
#define PF(x) ((x) * (x))
#define LF(x) ((x)*PF(x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const double eps = 1e-6;
const int MOD = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3fll;
int main() {
initIO();
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
int f;
cin >> f;
vector<int> location(f + 1);
for (int i = 1; i <= f; ++i)
cin >> location[i];
vector<int> noBike, hasBike;
vector<int> vis(f + 1, 1);
int h;
cin >> h;
for(int i = 0; i < h; ++i){
int tv;
cin >> tv;
noBike.push_back(location[tv]);
vis[tv] = 0;
}
for(int i = 1; i <= f; ++i){
if(vis[i]){
hasBike.push_back(location[i]);
}
}
vector<int> dis(n + 1, inf);
dis[1] = 0;
vector flag(n + 1, vector<int>(1 << h, 0));
flag[1][0] = 1;
queue<int> q;
q.push(1);
while (!q.empty()) {
auto cur = q.front();
q.pop();
for (auto &v : g[cur]) {
if (dis[v] > dis[cur] + 1) {
dis[v] = dis[cur] + 1;
for(int j = 0; j < (1 << h); ++j){
if(flag[cur][j]){
int tv = j;
flag[v][tv] = 1;
for(int k = 0; k < h; ++k){
if(v == noBike[k]){
tv |= (1 << k);
}
}
flag[v][tv] = 1;
}
}
q.push(v);
} else if (dis[v] == dis[cur] + 1) {
for(int j = 0; j < (1 << h); ++j){
if(flag[cur][j]){
flag[v][j] = 1;
int tv = j;
for(int k = 0; k < h; ++k){
if(v == noBike[k]){
tv |= (1 << k);
}
}
flag[v][tv] = 1;
}
}
}
}
}
vector<int> dp(1 << h, 0);
dp[0] = 1;
int ans = 0;
for(auto& idx: hasBike){
for(int j = (1 << h) - 1; j >= 0; --j){
if(dp[j]){
for(int k = 0; k < (1 << h); ++k){
if(flag[idx][k]){
dp[j | k] = 1;
}
}
}
}
}
for(int i = 0; i < (1 << h); ++i) if(dp[i]) ans = max(ans, __builtin_popcount(i));
cout << h - ans << endl;
}
return 0;
}Codeforces Round 826 (Div.3)
https://www.dianhsu.com/2022/10/12/cf1741/