周日gym组队赛补题

周日组队赛补题,雪崩。。。

题目链接

E

模拟取糖的问题
题解连接

ac code

F

题意不清楚啊,我也很绝望啊。。。

题解

每一个物品有三种状态,只要脸长大于等于3就可以确定关系
注意下面的例子:
4 3
1<2
1<3
3<4
上面4得状态是可以确定的,。。。我他妈觉得题面有毒。
这样枚举每一个点,然后找他的左边和右边是否有点,然后更新就可以了。
每次更新的长度为3
至于等号的时候用并查集维护就行了。

ac code

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int n, m;
int fa[maxn];
bool vis[maxn];
vector<int> G[maxn];
vector<int> rG[maxn];
struct Node{
int l, r;
char op;
int pri;
}node[maxn*maxn/2];
int find_fa(int x){
int a = x;
while(x!=fa[x]){
x = fa[x];
}
while(a!=fa[a]){
int z = a;
a = fa[a];
fa[z] = x;
}
return x;
}
void init(){
for(int i=0; i<maxn; i++) fa[i] = i;
for(int i=0; i<maxn; i++) G[i].clear();
for(int i=0; i<maxn; i++) rG[i].clear();
}
bool cmp(Node a, Node b){
return a.pri>b.pri;
}
void uni(int u, int v){
int fau = find_fa(u);
int fav = find_fa(v);
if(fau!=fav){
fa[fau] = fav;
}
}
char ans[maxn];
int main()
{
freopen("Input.txt", "r", stdin);
freopen("Output.txt", "w", stdout);
ios::sync_with_stdio(false);
init();
cin>>n>>m;
for(int i=0; i<m; i++){
cin>>node[i].l>>node[i].op>>node[i].r;
if(node[i].op == '='){
node[i].pri = 2;
}
else{
node[i].pri = 1;
}
}
sort(node, node+m, cmp);
int u, v;
for(int i=0; i<m; i++){
if(node[i].op == '='){
u = node[i].l;
v = node[i].r;
uni(u, v);
}
}
memset(vis, 0, sizeof(vis));
for(int i=1; i<=n; i++) find_fa(i);
for(int i=0; i<m; i++){
if(node[i].op == '=') continue;
u = fa[node[i].l];
v = fa[node[i].r];
if(node[i].op == '<'){
G[u].push_back(v);
rG[v].push_back(u);
}
else {
G[v].push_back(u);
rG[u].push_back(v);
}
}
memset(ans, '?', sizeof(ans));
for(int i=1; i<=n; i++){
if(fa[i]!=i) continue;
if(G[i].size()>0&&rG[i].size()>0){
ans[i] = 'R';
for(int j=0; j<G[i].size(); j++){
int v = G[i][j];
ans[v] = 'W';
}
for(int j=0; j<rG[i].size(); j++){
int v = rG[i][j];
ans[v] = 'B';
}
}
}
for(int i=1; i<=n; i++){
if(fa[i]!=i){
ans[i] = ans[fa[i]];
}
}
for(int i=1; i<=n; i++){
cout<<ans[i];
}
cout<<endl;
return 0;
}

J

裸的二分图匹配,我他妈一直卡F没有开,,,

AC code

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2+10;
bool G[maxn][maxn];
string l[maxn];
int l1[maxn], l2[maxn];
string r[maxn];
int r1[maxn], r2[maxn];
bool link[maxn][maxn];
bool AT[maxn][maxn];
bool TA[maxn][maxn];
int n, m;
int linker[maxn];
bool used[maxn];
void init(){
memset(l1, 0, sizeof(l1));
memset(l2, 0, sizeof(l2));
memset(r1, 0, sizeof(r1));
memset(r2, 0, sizeof(r2));
memset(link, 0, sizeof(link));
memset(AT, 0, sizeof(AT));
memset(TA, 0, sizeof(TA));
}
bool dfs(int u){
for(int v=0; v<m; v++){
if(link[u][v]&&!used[v]){
used[v] = true;
if(linker[v] == -1||dfs(linker[v])){
linker[v] = u;
return true;
}
}
}
return false;
}
int hungry(){
int res = 0;
memset(linker, -1, sizeof(linker));
for(int i=0; i<n; i++){
memset(used, 0, sizeof(used));
if(dfs(i)) res++;
}
return res;
}
void print_ans(){
for(int i=0; i<m; i++){
if(linker[i]!=-1){
int u = linker[i];
int v = i;
if(AT[u][v]){
cout<<"AT"<<" "<<l[u]<<" "<<r[v]<<endl;
}
else{
cout<<"TA"<<" "<<r[v]<<" "<<l[u]<<endl;
}
}
}
}
int main()
{
freopen("Input.txt", "r", stdin);
freopen("Output.txt", "w", stdout);
init();
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=0; i<n; i++){
cin>>l[i];
for(int j=0; j<3; j++){
l1[i] += l[i][j]-'0';
}
for(int j=3; j<6; j++){
l2[i] += l[i][j]-'0';
}
}
for(int i=0; i<m; i++){
cin>>r[i];
for(int j=0; j<3; j++){
r1[i] += r[i][j]-'0';
}
for(int j=3; j<6; j++){
r2[i] +=r[i][j]-'0';
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(l1[i] == r2[j]){
AT[i][j] = true;
link[i][j] = true;
}
if(l2[i] == r1[j]){
TA[i][j] = true;
link[i][j] = true;
}
}
}
int tot = hungry();
cout<<tot<<endl;
print_ans();
return 0;
}

未解决的问题

文章目录
  1. 1. E
    1. 1.1. ac code
  2. 2. F
    1. 2.1. 题解
    2. 2.2. ac code
  3. 3. J
    1. 3.1. AC code
  4. 4. 未解决的问题
{{ live2d() }}