当前位置：网站首页>2022牛客多校第二场解题报告
2022牛客多校第二场解题报告
2022-07-28 06:38:00 【野指针*】
A.Ancestor
思路:树中多个点的lca为dfs序最小的和dfs序最大的两个点的lca,枚举然后求lca即可
技巧:
代码:
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <time.h>
#include <assert.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PDI pair<double, int>
#define PDD pair<double, double>
#define debug(a) cout << #a << " = " << a << endl
#define all(x) (x).begin(), (x).end()
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x))
#define SZ(x) ((x).size())
#define wtn(x) wt(x), printf("\n")
#define wtt(x) wt(x), printf(" ")
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define eps 1e-8
int T = 1;
using namespace std;
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c-o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x);*x = 0; return *this;} template<typename t> q&operator>>(t&x){for (r(y),s=0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p!=h) w(*--p);return *this;}}qio; }using nqio::qio;
const int N = 1e6 + 10;
int n, k, x[N], a[N], b[N];
struct KK {
int h[N], v[N], to[N], tot;
int tpf[N], fa[N], sz[N], son[N], dep[N], in[N], tim;
void add(int a, int b) {v[++tot] = b, to[tot] = h[a], h[a] = tot;}
void dfs1(int x, int f, int depth) {
dep[x] = depth; fa[x] = f, sz[x] = 1;
int mxsz = -1;
for (int i = h[x]; i; i = to[i]) {
int y = v[i];
if (y == f) continue;
dfs1(y, x, depth + 1);
sz[x] += sz[y];
if (mxsz < sz[y]) mxsz = sz[y], son[x] = y;
}
}
void dfs2(int x, int topf) {
in[x] = ++tim, tpf[x] = topf;
if (!son[x]) return;
dfs2(son[x], topf);
for (int i = h[x]; i; i = to[i]) {
int y = v[i];
if (y == fa[x] || y == son[x]) continue;
dfs2(y, y);
}
}
void init() {
for (int i = 1; i <= n; ++i) h[i] = 0;
tim = tot = 0;
}
void work() {
dfs1(1, -1, 1); dfs2(1, 1);
}
int LCA(int x, int y) {
while (tpf[x] != tpf[y]) {
if (dep[tpf[x]] < dep[tpf[y]]) swap(x, y);
x = fa[tpf[x]];
}
if (dep[x] > dep[y]) swap(x, y);
return x;
}
} A, B;
struct recA {
int x;
bool operator< (const recA& i) const {
return A.in[x] < A.in[i.x];
}
};
struct recB {
int x;
bool operator< (const recB& i) const {
return B.in[x] < B.in[i.x];
}
};
void solve() {
qio >> n >> k;
set<recA> sa;
set<recB> sb;
for (int i = 1; i <= k; ++i) qio >> x[i];
A.init(), B.init();
for (int i = 1; i <= n; ++i) qio >> a[i];
for (int i = 2; i <= n; ++i) {int x; qio >> x; A.add(i, x); A.add(x, i);}
for (int i = 1; i <= n; ++i) qio >> b[i];
for (int i = 2; i <= n; ++i) {int x; qio >> x; B.add(i, x); B.add(x, i);}
A.work(), B.work();
for (int i = 1; i <= k; ++i) sa.insert({x[i]}), sb.insert({x[i]});
int ans = 0;
for (int i = 1; i <= k; ++i) {
sa.erase({x[i]}), sb.erase({x[i]});
int la = A.LCA((*sa.begin()).x, (*sa.rbegin()).x);
int lb = B.LCA((*sb.begin()).x, (*sb.rbegin()).x);
if (a[la] > b[lb]) ++ans;
sa.insert({x[i]}), sb.insert({x[i]});
}
qio << ans << "\n";
}
signed main() {
IOS;
while (T--) solve();
}C.Concatenation
思路:重载<,return AB < BA
代码:
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <time.h>
#include <assert.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PDI pair<double, int>
#define PDD pair<double, double>
#define debug(a) cout << #a << " = " << a << endl
#define all(x) (x).begin(), (x).end()
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x))
#define SZ(x) ((x).size())
#define wtn(x) wt(x), printf("\n")
#define wtt(x) wt(x), printf(" ")
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define eps 1e-8
int T = 1;
using namespace std;
namespace nqio{const unsigned R=4e5,W=4e5;char*a,*b,i[R],o[W],*c=o,*d=o+W,h[40],*p=h,y;bool s;struct q{void r(char&x){x=a==b&&(b=(a=i)+fread(i,1,R,stdin),a==b)?-1:*a++;}void f(){fwrite(o,1,c-o,stdout);c=o;}~q(){f();}void w(char x){*c=x;if(++c==d)f();}q&operator>>(char&x){do r(x);while(x<=32);return*this;}q&operator>>(char*x){do r(*x);while(*x<=32);while(*x>32)r(*++x);*x=0;return*this;}template<typename t>q&operator>>(t&x){for(r(y),s=0;!isdigit(y);r(y))s|=y==45;if(s)for(x=0;isdigit(y);r(y))x=x*10-(y^48);else for(x=0;isdigit(y);r(y))x=x*10+(y^48);return*this;}q&operator<<(char x){w(x);return*this;}q&operator<<(char*x){while(*x)w(*x++);return*this;}q&operator<<(const char*x){while(*x)w(*x++);return*this;}template<typename t>q&operator<<(t x){if(!x)w(48);else if(x<0)for(w(45);x;x/=10)*p++=48|-(x%10);else for(;x;x/=10)*p++=48|x%10;while(p!=h)w(*--p);return*this;}}qio;}using nqio::qio;
const int N = 2e6 + 10;
string s[N];
bool cmp(string &A, string &B) {return A + B < B + A;}
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> s[i];
sort(s + 1, s + 1 + n, cmp);
for (int i = 1; i <= n; ++i) cout << s[i];
}
signed main() {
IOS;
while (T--) solve();
}F.Fief
思路:题目要求在图上找两个点,然后使得从其中任何一个点开始"烧",都不会把整张图给"烧断"(把这两个点所占的区域分隔开).这提醒我们往割点想.首先很显然的一点就是,当整个图只有一个点双通分量或者只有两个点时,一定有解.如果整张图不连通,一定无解.接下来,我们考虑求点双然后缩点.可以发现,当一个点双有3个以上的儿子时,无论这两个点在哪,从其中一个点开始烧,一定会烧断这个图.所以,一个点双度数小于等于2,也就是说,是链.如果两个点在链的两端,显然这是满足的.否则除非只有一个点双,两个点都不可能在一个点双内.还有一个情况就是,两个点至少有一个点不在链上,这样也是不行的.
代码:
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PDI pair<double, int>
#define PDD pair<double, double>
#define debug(a) cout << #a << " = " << a << endl
#define all(x) (x).begin(), (x).end()
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x))
#define SZ(x) ((x).size())
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 1e6 + 10;
int n, m;
int h[N], v[N], to[N], tot;
int dfn[N], low[N], tim, cut[N], cnt, dd[N], top;
vector<int> stk;
set<int> bcc[N];
void add(int a, int b) {v[++tot] = b, to[tot] = h[a], h[a] = tot;}
void tarjan(int x) {
dfn[x] = low[x] = ++tim;
stk.emplace_back(x);
int flag = 0;
for (int i = h[x]; i; i = to[i]) {
int y = v[i];
if (!dfn[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
if (low[y] >= dfn[x]) {
++flag;
if (x != 1 || flag > 1) cut[x] = true;
++cnt;
int p;
do {
p = stk.back();
stk.pop_back();
bcc[p].insert(cnt);
//bcc[cnt].insert(p);
} while (p != y);
bcc[x].insert(cnt);
//bcc[cnt].insert(p);
}
}else {
low[x] = min(low[x], dfn[y]);
}
}
}
signed main() {
qio >> n >> m;
for (int i = 1; i <= m; ++i) {int a, b; qio >> a >> b; add(a, b), add(b, a);}
//求点双通分量
tarjan(1);
bool ok = 1;
//如果图不是连通图 pass
for (int i = 1; i <= n; ++i) if (!dfn[i]) ok = 0;
int q;
qio >> q;
//如果某个割点的度数大于等于3 pass
for (int i = 1; i <= n; ++i) if (bcc[i].size() > 2) ok = 0;
for (int i = 1; i <= n; ++i) {
if (bcc[i].size() == 2)
for (int x : bcc[i])
++dd[x];
}
//如果某个连通分量的度数大于等于3 pass
for (int i = 1; i <= cnt; ++i) if (dd[i] >= 3) ok = 0;
int A = 0, B = 0;
//找出连通分量链的两端A, B,如果只有一个点,那么本身就是两端
for (int i = 1; i <= cnt; ++i) if (dd[i] == 1) (A ? B : A) = i;
if (!A) A = B = 1;
//如果只有两个点 √
if (n == 2) {
while (q--) qio << "YES\n";
return 0;
}
if (!ok) {
while (q--) qio << "NO\n";
return 0;
}
while (q--) {
int u, v;
qio >> u >> v;
//如果一个点同时属于两个连通分量,说明是割点 pass
if (bcc[u].size() >= 2 || bcc[v].size() >= 2) qio << "NO\n";
else {
int uu = *(bcc[u].begin()), vv = *(bcc[v].begin());
//如果不是位于链的两端 pass
if ((uu == A && vv == B) || (uu == B && vv == A)) qio << "YES\n";
else qio << "NO\n";
}
}
}D.Journey
思路:在边之间建图,右拐边权为0,其余为1,用双端队列优化bfs.
技巧:网格图建图
代码:
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PDI pair<double, int>
#define PDD pair<double, double>
#define debug(a) cout << #a << " = " << a << endl
#define all(x) (x).begin(), (x).end()
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x))
#define SZ(x) ((x).size())
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
namespace nqio{const unsigned R = 4e5, W = 4e5; char *a, *b, i[R], o[W], *c = o, *d = o + W, h[40], *p = h, y; bool s; struct q{void r(char &x){x = a == b && (b = (a = i) + fread(i, 1, R, stdin), a == b) ? -1 : *a++;} void f(){fwrite(o, 1, c - o, stdout); c = o;} ~q(){f();}void w(char x){*c = x;if (++c == d) f();} q &operator >>(char &x){do r(x);while (x <= 32); return *this;} q &operator >>(char *x){do r(*x); while (*x <= 32); while (*x > 32) r(*++x); *x = 0; return *this;} template<typename t> q&operator>>(t &x){for (r(y),s = 0; !isdigit(y); r(y)) s |= y == 45;if (s) for (x = 0; isdigit(y); r(y)) x = x * 10 - (y ^ 48); else for (x = 0; isdigit(y); r(y)) x = x * 10 + (y ^ 48); return *this;} q &operator <<(char x){w(x);return *this;}q &operator<< (char *x){while (*x) w(*x++); return *this;}q &operator <<(const char *x){while (*x) w(*x++); return *this;}template<typename t> q &operator<< (t x) {if (!x) w(48); else if (x < 0) for (w(45); x; x /= 10) *p++ = 48 | -(x % 10); else for (; x; x /= 10) *p++ = 48 | x % 10; while (p != h) w(*--p);return *this;}}qio; }using nqio::qio;
using namespace std;
const int N = 2e7 + 10;
int h[N], v[N], to[N], w[N], tot, n, f[N][5], s1, s2, t1, t2, d[N];
void add(int a, int b, int c) {w[++tot] = c, v[tot] = b, to[tot] = h[a], h[a] = tot; /*qio << a << " -> " << b << " is " << c << "\n";*/}
int pos(int x, int y) {return (x - 1) * 4 + y + 1;}
int find(int x, int y) {for (int i = 0; i < 4; ++i) if (f[x][i] == y) return pos(x, i); return 0;}
signed main() {
qio >> n;
for (int i = 1; i <= n; ++i) for (int j = 0; j < 4; ++j) qio >> f[i][j];
for (int i = 1; i <= n; ++i) for (int j = 0; j < 4; ++j)
if (f[i][j]) {
add(find(f[i][j], i), pos(i, j), 1);
if (f[i][(j + 1) % 4]) add(find(f[i][(j + 1) % 4], i), pos(i, j), 1);
if (f[i][(j + 2) % 4]) add(find(f[i][(j + 2) % 4], i), pos(i, j), 1);
if (f[i][(j + 3) % 4]) add(find(f[i][(j + 3) % 4], i), pos(i, j), 0);
}
qio >> s1 >> s2 >> t1 >> t2;
int st = find(s1, s2), ed = find(t1, t2);
deque<int> dq;
mem(d, 0x3f);
dq.push_back(st); d[st] = 0;
while (SZ(dq)) {
int x = dq.front(); dq.pop_front();
for (int i = h[x], y; i; i = to[i]) {
y = v[i];
if (d[y] <= d[x] + w[i]) continue;
d[y] = d[x] + w[i];
if (!w[i]) dq.push_front(y);
else dq.push_back(y);
}
}
qio << (d[ed] > inf ? -1 : d[ed]) << "\n";
}边栏推荐
- How to build the protection system of class protection technology of 2022 series of ISO compliance (Part I)
- Solve the inherent defects of CNN! Common CNN architecture ccnn is coming ｜ icml2022
- Redis of non relational database [jedis client +jedis connection cluster]
- Can the variable modified by final be modified
- 五张图看懂EMI电磁干扰的传播过程-方波陡峭程度对高频成分的影响，时序到频域频谱图形，波形形状对EMI辐射的影响。
- js卡通英文字母打字小游戏源码
- Record a MYCAT connection and solve the problems of communications link failure
- 解决CNN固有缺陷！通用 CNN 架构CCNN来了｜ ICML2022
- Technology sharing | common proxy tools for interface testing
- In QT multithreading, in which thread does the slot function perform analysis
猜你喜欢
Meituan Er Mian: why does redis have sentinels?
CarSim simulation quick start (10) - Modeling of braking system
本人男，27岁技术经理，收入太高，心头慌得一比
jquey的基础语法
Characteristics of EMC EMI beads
![[300 + selected interview questions from big companies continued to share] big data operation and maintenance sharp knife interview question column (VIII)](/img/86/8e97b4456e2ba9a8535debb099fee0.png)
[300 + selected interview questions from big companies continued to share] big data operation and maintenance sharp knife interview question column (VIII)
Es6: template string
C＃，入门教程——程序运行时的调试技巧与逻辑错误探针技术与源代码
Chairman tree review
sql server时间字段排序
随机推荐
Will ordinary browsers disclose information? How to protect privacy by using a secure browser?
The even number of an integer queue is placed in the front, the odd number is placed in the back, and the relative position of the even and odd numbers remains unchanged
pyspark更改列顺序存入iceberg数据库
Freezing and thawing of pytoch
Can the variable modified by final be modified
Es6: template string
What if the computer desktop icon has a small yellow lock?
Meituan Er Mian: why does redis have sentinels?
What if you are prompted that your connection to this website is not a private connection?
[Qt5] a method of multi window parameter transmission (using custom signal slot) and case code download
How do we run batch mode in MySQL?
js信息提示框定时关闭
本人男，27岁技术经理，收入太高，心头慌得一比
Opencv's practical learning of credit card recognition (4)
Chapter 01 introduction of [notes of Huashu]
Es6: arrow function usage
See how Google uses pre training weights in target detection tasks | CVPR 2022
[leetcode] 24. Exchange nodes in the linked list in pairs
[chart component kit] Shanghai daoning provides developers with steema download, trial and tutorial
Some experience of gd32 using Hal Library of ST and Gd official library