AtCoder
ABC372 D - Buildings
单调栈，逆向进行，找左侧比他大的数，此时栈的大小即为当前位的答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e5+7, mod=1e9+7;
int n,h[N],ans[N];
stack<int>s;
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i];
}
for(int i=n;i>=1;i--){
ans[i]=s.size();
while(s.size()&&s.top()<h[i])s.pop();
s.push(h[i]);
}
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|
ABC372 E - K-th Largest Connected Components
并查集，我们可以开 $n$ 个堆，把每个联通块都存到同一个栈当中，查询时栈的大小小于 $k$ 就输出 -1，反之输出相应值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N = 2e5 + 7, mod = 1e9 + 7;
int n, q, u, v, op;
set<int> s[N];
int fa[N];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void unite(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
if (s[fx].size() < s[fy].size()) swap(fx, fy);
fa[fy] = fx;
for (int elem : s[fy]) {
s[fx].insert(elem);
}
s[fy].clear();
}
}
void solve() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
fa[i] = i;
s[i].insert(i);
}
while (q--) {
cin >> op >> u >> v;
if (op == 1) {
unite(u, v);
} else {
int x = find(u);
if (s[x].size() < v) {
cout << -1 << endl;
} else {
auto it = s[x].rbegin();
advance(it, v - 1);
cout << *it << endl;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
|
ABC372 F - Teleporting Takahashi 2
根据题意，可以推断出是用 $dp$ 解决
看题，可以发现一定是个从 $1$ 到 $n$ 的环，然后有 $m$ 条边是多出来的，那么多的方案数一定是由这 $m$ 条边决定的
开一个 $f[i][k]$ 数组，$i$ 指代当前是哪个节点，$k$ 指代当前是第几步
可以推断出每个点的第 $k$ 步的方案数
$f_{v,k}=f_{v-1,k-1}+\sum_{(u,v)\in edge}f_{u,k-1}$
$v$ 是当前点，$u$ 是 $m$ 条边中指向 $v$ 的点
但如果这么开的话，时间空间都会过大，显然不能通过
继续观察题目，发现我们可以将第二维滚动优化，变为一维数组
每次向前一步，这个环的起点就从 $st$ 变更为 $st-1+n$
可以看出，起始时，是以 1 为起点的一个环，进行了一次移动后，每个点都向后移动，8 这个点就移动到第一位了
所以 $f[8]’$ 的值就是 $f[1]$，$f[1]’$ 的值就是 $f[2]$
按照平移后的点的名称来计算 $f$ 数组的值，按照平移后的点来更新
先用一个 $lst$ 数组来记录当前的 $f$ 数组中的值，避免更新过程中被覆盖
接着，我们遍历 $edge$ 数组中存的边， $f_{v}=f_{v}+\sum_{{u,v}\in edge}lst_{u}$
答案即为 $\sum_{i=1}^{n}f_{i}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e5+70, mod=998244353;
vector<pair<int,int>>edge;
int n,m,k;
ll f[N],lst[N];
void solve(){
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
u--,v--;
edge.push_back({u,v});
}
f[0]=1;
int st=0;
for(int i=1;i<=k;i++){
st=(st-1+n)%n;
for(auto x:edge){
int u=x.first,v=x.second;
u=(st+1+u)%n,v=(st+v)%n;
lst[v]=f[v];
lst[u]=f[u];
}
for(auto x:edge){
int u=x.first,v=x.second;
u=(st+1+u)%n,v=(st+v)%n;
f[v]=(f[v]+lst[u])%mod;
}
}
ll ans=0;
for(int i=0;i<n;i++){
ans=(ans+f[i])%mod;
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|
NowCoder
开三倍空间，储存物种之间相食的关系，相邻层级之间如果是同一父节点，即有相食关系
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 2e5 + 7;
const int mod = 1e9 + 7;
int n, k;
int d, x, y;
int ans = 0;
int fa[N];
int find(int x) {
if (fa[x] != x) {
fa[x] = find(fa[x]);
}
return fa[x];
}
void unite(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
fa[fx] = fy;
}
}
void solve() {
cin >> n >> k;
for (int i = 1; i <= 3 * n; i++) {
fa[i] = i;
}
while (k--) {
cin >> d >> x >> y;
if (x > n || y > n) {
ans++;
continue;
}
if (d == 1) {
if (find(x) == find(y + n) || find(x) == find(y + 2 * n)) {
ans++;
continue;
}
unite(x, y);
unite(x + n, y + n);
unite(x + 2 * n, y + 2 * n);
} else {
if (find(x) == find(y) || find(x) == find(y + 2 * n)) {
ans++;
continue;
}
unite(x, y + n);
unite(x + n, y + 2 * n);
unite(x + 2 * n, y);
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
|
按冲突值从大到小排序，冲突值大的，先分开，同时标记分开的两个人，这两人现在不会产生冲突，继续向下看，如果遇到标记过的人，我们肯定将另一人放到之前和这个标记过的人冲突过的人所在的监狱，这样三个人都不会产生冲突，再往下如果继续在这三人中产生冲突，那么就是不可避免的了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
#define int long long
const int N=1e5+7, mod=1e9+7;
struct Node{
int a,b,c;
bool operator<(const Node &t){return c>t.c;}
}a[N];
int fa[N],fr[N];
int n,m;
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unite(int x,int y){
fa[find(x)]=fa[find(y)];
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<=m;i++){
cin>>a[i].a>>a[i].b>>a[i].c;
}
sort(a+1,a+1+m);
for(int i=1;i<=m;i++){
if(find(a[i].a)==find(a[i].b)){
cout<<a[i].c<<endl;
return;
}
if(!fr[a[i].a])fr[a[i].a]=a[i].b;
else unite(a[i].b,fr[a[i].a]);
if(!fr[a[i].b])fr[a[i].b]=a[i].a;
else unite(a[i].a,fr[a[i].b]);
}
cout<<"0\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|
拓展域并查集
$n$ 个点，每个点拓展为两个点，正点和反点，如果 $a$ 和 $b$ 不能在同一个集合内，就把 $a$ 和 $b$ 的反节点放在一起，如果发现 $a$ 和 $b$ 的正节点已经在一起了，说明之前的关系与现在的关系冲突，即不能同时满足
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
int n,m;
unordered_map<int,int>fa;
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unite(int x,int y){
fa[find(x)]=find(y);
}
void solve(){
cin>>n>>m;
n++;
for(int i=0;i<m;i++){
int x,y;
string op;
cin>>x>>y>>op;
x--;
if(fa.count(x)==0)fa[x]=x,fa[x+n]=x+n;
if(fa.count(y)==0)fa[y]=y,fa[y+n]=y+n;
if(op=="even"){
if(find(x)==find(y+n)){
cout<<i<<endl;
return;
}
unite(x,y);
unite(x+n,y+n);
}
else{
if(find(x)==find(y)){
cout<<i<<endl;
return;
}
unite(x,y+n);
unite(x+n,y);
}
}
cout<<m<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|
并查集本身不支持撤销操作，所以我们转为离线操作，所有数据记录后建图，先不加被删掉的边，在进行操作时，倒序进行，将后删的加回来即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
int n,m,q,a,b;
int fa[N],w[N],u[N],v[N],du[N],dv[N],ans[N];
char op;
set<pair<int,int>>s;
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unite(int x,int y){
int fx=find(x),fy=find(y);
if(w[fx]>w[fy])fa[fy]=fx;
else fa[fx]=fy;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>w[i];
fa[i]=i;
}
for(int i=1;i<=m;i++)cin>>u[i]>>v[i];
cin>>q;
for(int i=1;i<=q;i++){
cin>>op;
if(op=='Q')cin>>du[i];
else {
cin>>du[i]>>dv[i];
s.insert({du[i],dv[i]});
s.insert({dv[i],du[i]});
}
}
for(int i=1;i<=m;i++){
if(s.find({u[i],v[i]})==s.end())unite(u[i],v[i]);
}
for(int i=q;i>0;i--){
if(dv[i])unite(du[i],dv[i]);
else ans[i]=w[find(du[i])];
}
for(int i=1;i<=q;i++){
if(ans[i])cout<<ans[i]<<endl;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|
老子的全排列呢
输出 1~8 的全排列
主要是学习 next_permutation 和 prev_permutation
前者是数组的下一个字典序更大的排序，后者是字典序更小的排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n = 8;
int a[8];
for (int i = 0; i < n; i++) {
a[i] = i + 1;
}
do {
for (int i = 0; i < 8; i++) {
cout << a[i] << (i != 7 ? " " : "");
}
cout << endl;
} while (next_permutation(a, a + 8));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
|
也可以 dfs 硬搜
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
bool vis[10];
int a[10];
void dfs(int d){
if(d==9){
for(int i=1;i<=8;i++)cout<<a[i]<<(i==8?"":" ");
cout<<endl;
return;
}
for(int i=1;i<=8;i++){
if(!vis[i]){
a[d]=i;
vis[i]=1;
dfs(d+1);
a[d]=0;
vis[i]=0;
}
}
}
void solve(){
dfs(1);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
|