A. Gellyfish and Tricolor Pansy
优先打最弱的即可
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
|
#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 a,b,c,d;
void solve(){
cin >> a >> b >> c >> d;
int mn = min({a, b, c, d});
if (mn == b || mn == d) {
cout << "Gellyfish" << endl;
} else cout << "Flower" << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
B. Gellyfish and Baby’s Breath
因为是 2 的次方，所以找序列中最大值的位置即可。
因为有两个序列，所以两个位置都找到，取最优。
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
|
#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=998244353;
int n,q[N],p[N];
ll res[N];
void solve(){
cin >> n;
for (int i = 0; i < n; i++) {
cin >> p[i];
}
for (int i = 0; i < n; i++) {
cin >> q[i];
}
vector<int> mpv(n + 1), mpi(n + 1), mqv(n + 1), mqi(n + 1);
int pos = -1, mx = -1;
for (int i = 0; i < n; i++) {
if (p[i] > mx) {
mx = p[i];
pos = i;
}
mpv[i] = mx;
mpi[i] = pos;
}
pos = -1, mx = -1;
for (int i = 0; i < n; i++) {
if (q[i] > mx) {
mx = q[i];
pos = i;
}
mqv[i] = mx;
mqi[i] = pos;
}
vector<int> ans(n+1);
for (int i = 0; i < n; i++) {
int x, y;
if (mpv[i] > mqv[i]) {
x = mpv[i];
y = q[i - mpi[i]];
} else if (mqv[i] > mpv[i]) {
x = mqv[i];
y = p[i - mqi[i]];
} else {
x = mpv[i];
int t1 = q[i - mpi[i]];
int t2 = p[i - mqi[i]];
y = max(t1, t2);
}
ans[i] = (res[x] + res[y]) % mod;
}
for (int i = 0; i < n; i++) {
cout << ans[i] << " ";
}
cout << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
res[0] = 1;
for (int i = 1; i < N; i++) {
res[i] = res[i-1] * 2 % mod;
}
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
C. Gellyfish and Flaming Peony
先找到整个数组的 GCD 值，如果当前数组中存在这个 GCD 值，那么答案就是这个值 n - cnt (GCD 出现次数)
如果原数组中没有这个值，就需要找到当前数组中的值到达 GCD 的最小步数，下面代码使用 BFS 解决。
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
|
#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=5e3+7, mod=1e9+7;
int n, a[N];
void solve(){
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int GCD = a[0];
for (int i = 1; i < n; i++) {
GCD = __gcd(GCD, a[i]);
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (a[i] == GCD) {
cnt++;
}
}
if (cnt == n) {
cout << 0 << endl;
return;
}
if (cnt > 0) {
cout << n - cnt << endl;
return;
}
vector<int> s, dist(N, 1e9);
for (int i = 0; i < n; i++) {
s.push_back(a[i]);
}
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
deque<int> q;
for (int i = 0; i < s.size(); i++) {
dist[s[i]] = 0;
q.push_back(s[i]);
}
int tmp = 1e9;
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v == GCD) {
tmp = dist[v];
break;
}
for (auto x : s) {
int w = __gcd(v, x);
if (dist[w] == 1e9) {
dist[w] = dist[v] + 1;
q.push_back(w);
}
}
}
int ans = n + (tmp - 1);
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;
}
|
D. Gellyfish and Camellia Japonica
坐牢。。。
首先可以确定逆向思考，z 取的是 x, y 中的最小值，所以初态中的 x, y 一定是 >= z 的，所以 x, y 分别与 z 取 max，如果 z != x, y 那么 z 这个位置优先填 0, 最后如果还是 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
|
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n), ans(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
ans[i] = a[i];
}
vector<int> x(m), y(m), z(m);
for (int i = 0; i < m; i++) {
cin >> x[i] >> y[i] >> z[i];
x[i]--, y[i]--, z[i]--;
}
for (int i = m - 1; i >= 0; i--) {
ans[x[i]] = max(ans[x[i]], ans[z[i]]);
ans[y[i]] = max(ans[y[i]], ans[z[i]]);
if (x[i]!= z[i] && y[i] != z[i]) {
ans[z[i]] = 0;
}
}
for (int i = 0; i < n; i++) {
if (ans[i] == 0) ans[i] = a[i];
}
vector<int> t(n);
t = ans;
for (int i = 0; i < m; i++) {
t[z[i]] = min(t[x[i]], t[y[i]]);
}
bool flag = 1;
for (int i = 0; i < n; i++) {
if (t[i] != a[i]) {
flag = 0;
break;
}
}
if (!flag) cout << "-1\n";
else {
for (int i = 0; i < n; i++) {
cout << ans[i] << " ";
}
cout << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
|