[tutorial:1704A]↵
↵
<spoiler summary="solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
const int maxn = 2e5;↵
signed main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
int T;↵
cin >> T;↵
while (T--) {↵
int n, m;↵
cin >> n >> m;↵
string a, b;↵
cin >> a >> b;↵
if (n < m) {↵
cout << "NO\n";↵
continue;↵
}↵
bool same = true;↵
for (int i = 1; i < b.size(); ++i) {↵
if (a[i + n - m] != b[i]) {↵
same = false;↵
break;↵
}↵
}↵
if (!same) {↵
cout << "NO\n";↵
continue;↵
}↵
for (int i = 0; i < n - m + 1; ++i) {↵
if (a[i] == b[0]) {↵
same = false;↵
}↵
}↵
if (same) {↵
cout << "NO\n";↵
}↵
else {↵
cout << "YES\n";↵
}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1704B]↵
↵
<spoiler summary="solution">↵
~~~~~↵
#include <stdio.h>↵
#include <string.h>↵
#include <vector>↵
#include <set>↵
#include <queue>↵
#include <string>↵
#include <map>↵
#include <chrono>↵
#include <stdlib.h>↵
#include <time.h>↵
#include <algorithm>↵
#include <iostream>↵
#include <memory>↵
#include <cstdio>↵
#include <assert.h>↵
#include <iostream>↵
const int MAXN = 300005;↵
int numbers[MAXN];↵
int main() {↵
int t;↵
int n, x;↵
↵
scanf("%d", &t);↵
while (t--)↵
{↵
scanf("%d %d", &n, &x);↵
for (int i = 1; i <= n; i++) {↵
scanf("%d", &numbers[i]);↵
}↵
int num_min = numbers[1];↵
int num_max = numbers[1];↵
int res = 0;↵
for (int i = 2; i <= n; i++) {↵
if (numbers[i] > num_max) {↵
num_max = numbers[i];↵
}↵
if (numbers[i] < num_min) {↵
num_min = numbers[i];↵
}↵
if (num_max - num_min > 2 * x) {↵
res++;↵
num_min = num_max = numbers[i];↵
}↵
}↵
printf("%d\n", res);↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1704C]↵
↵
<spoiler summary="solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
const int N = 500005, inf = 2147483647, M = 1004535809;↵
int n, m, a[N], T, k;↵
struct str {↵
int x, y;↵
}t[N];↵
int main() {↵
scanf("%d", &T);↵
while (T--) {↵
k = 0;↵
scanf("%d %d", &n, &m);↵
for (int i = 1; i <= m; ++i)↵
scanf("%d", &a[i]);↵
sort(a + 1, a + 1 + m);↵
for (int i = 2; i <= m; ++i)↵
t[++k] = { a[i] - a[i - 1] - 1,2 };↵
int num_tmp = a[1] + n - a[m] - 1;↵
if (num_tmp > 0) {↵
t[++k] = { num_tmp, 2 };↵
}↵
sort(t + 1, t + 1 + k, [](str a, str b) {return a.x > b.x; });↵
long long ans = 0, cnt = 0;↵
for (int i = 1; i <= k; ++i) {↵
if (t[i].x - cnt * 2 > 0) {↵
int num_tmp = max(1ll, t[i].x - cnt * 2 - 1);↵
ans += num_tmp;↵
}↵
cnt += 2;↵
}↵
printf("%lld\n", n - ans);↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1704D]↵
↵
<spoiler summary="solution">↵
~~~~~↵
#include <stdio.h>↵
#include <string.h>↵
#include <vector>↵
#include <map>↵
#include <cassert>↵
const int MAXN = 500005;↵
std::vector<long long> numbers[MAXN];↵
std::map<long long, long long> val_to_index;↵
int main()↵
{↵
int t;↵
int n, m;↵
scanf("%d ", &t);↵
while (t--)↵
{↵
val_to_index.clear();↵
scanf("%d %d", &n, &m);↵
long long num_tmp;↵
for (int i = 1; i <= n; i++) {↵
numbers[i].clear();↵
numbers[i].push_back(0);↵
for (int j = 1; j <= m; j++) {↵
scanf("%lld", &num_tmp);↵
numbers[i].push_back(num_tmp);↵
}↵
}↵
long long res_tmp = -1;↵
for (long long i = 1; i <= n; i++) {↵
long long val = 0;↵
for (long long j = 1; j <= m; j++) {↵
val += (j * numbers[i][j]);↵
}↵
if (val_to_index.find(val) != val_to_index.end()) {↵
res_tmp = val;↵
val_to_index[val] = -1;↵
}↵
else {↵
val_to_index[val] = i;↵
}↵
}↵
assert(val_to_index.size() == 2);↵
for (auto &item : val_to_index) {↵
if (item.second != -1ll) {↵
printf("%lld %lld\n", item.second, std::abs(res_tmp - item.first));↵
break;↵
}↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1704E]↵
↵
<spoiler summary="solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
const int N = 500005, inf = 2147483647, M = 998244353;↵
int n, m, a[N], u, v, i, d[N], q[N], r, mx;↵
int b[N], tmp[N];↵
vector<int> g[N], z[N];↵
long long s[N];↵
int p[15];↵
void NEX(int M) {↵
for (int i = 1; i <= n; ++i)↵
if (b[i]) {↵
tmp[i] += b[i] - 1;↵
for (auto it : g[i])↵
++tmp[it];↵
}↵
for (int i = 1; i <= n; ++i) {↵
if (tmp[i] >= M)↵
b[i] = tmp[i] % M + M;↵
else↵
b[i] = tmp[i] % M;↵
tmp[i] = 0;↵
}↵
}↵
int cal(int M) {↵
for (int i = 1; i <= n; ++i) {↵
b[i] = a[i];↵
}↵
for (int i = 1; i <= n; ++i) {↵
bool fl = false;↵
for (int j = 1; j <= n; ++j)↵
if (b[j])↵
fl = true;↵
if (!fl)↵
return i - 1;↵
NEX(M);↵
}↵
return n;↵
}↵
int main() {↵
int t;↵
scanf("%d", &t);↵
while (t--) {↵
scanf("%d %d", &n, &m);↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &a[i]);↵
g[i].clear();↵
z[i].clear();↵
d[i] = 0;↵
tmp[i] = 0;↵
s[i] = 0;↵
}↵
for (int i = 1; i <= m; ++i) {↵
scanf("%d %d", &u, &v);↵
++d[u];↵
g[u].push_back(v);↵
z[v].push_back(u);↵
}↵
mx = cal(M);↵
if (mx < n) {↵
cout << mx << endl;↵
continue;↵
}↵
r = 0;↵
for (int i = 1; i <= n; ++i)↵
if (!d[i])↵
q[++r] = i;↵
s[q[1]] = 1;↵
for (int i = 1; i <= r; ++i) {↵
s[q[i]] %= M;↵
for (auto it : z[q[i]]) {↵
--d[it];↵
s[it] += s[q[i]];↵
if (!d[it])↵
q[++r] = it;↵
}↵
}↵
long long ans = n;↵
for (int i = 1; i <= n; ++i)↵
ans = (ans + s[i] * b[i]) % M;↵
cout << ans << endl;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1704F]↵
↵
<spoiler summary="solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
const int N=500005,inf=2147483647,M=998244353;↵
int n,i,t,f[N],vis[N];↵
char c[N];↵
int main(){↵
for(int i=1;i<=1000;++i){↵
for(int j=0;j<=i-2;++j)↵
vis[f[j]^f[i-2-j]]=1;↵
int j;↵
for(j=0;vis[j];++j);↵
f[i]=j;↵
for(int j=0;j<=i;++j)↵
vis[j]=0;↵
}↵
for(int i=1001;i<N;++i)↵
f[i]=f[i-34];↵
scanf("%d",&t);↵
while(t--){↵
scanf("%d",&n);↵
scanf("%s",c+1);↵
int s=0;↵
for(int i=1;i<=n;++i)↵
if(c[i]=='R')↵
++s;↵
else↵
--s;↵
if(s>0)↵
puts("Alice");↵
if(s<0)↵
puts("Bob");↵
if(s==0){↵
int ans=0;↵
for(int i=1;i<=n;){↵
int j=i+1;↵
for(;j<=n&&c[j]!=c[j-1];++j);↵
ans^=f[j-i];↵
i=j;↵
}↵
puts(ans?"Alice":"Bob");↵
}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
The editorials of problem G and H will be adding soon.
↵
<spoiler summary="solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
const int maxn = 2e5;↵
signed main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
int T;↵
cin >> T;↵
while (T--) {↵
int n, m;↵
cin >> n >> m;↵
string a, b;↵
cin >> a >> b;↵
if (n < m) {↵
cout << "NO\n";↵
continue;↵
}↵
bool same = true;↵
for (int i = 1; i < b.size(); ++i) {↵
if (a[i + n - m] != b[i]) {↵
same = false;↵
break;↵
}↵
}↵
if (!same) {↵
cout << "NO\n";↵
continue;↵
}↵
for (int i = 0; i < n - m + 1; ++i) {↵
if (a[i] == b[0]) {↵
same = false;↵
}↵
}↵
if (same) {↵
cout << "NO\n";↵
}↵
else {↵
cout << "YES\n";↵
}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1704B]↵
↵
<spoiler summary="solution">↵
~~~~~↵
#include <stdio.h>↵
#include <string.h>↵
#include <vector>↵
#include <set>↵
#include <queue>↵
#include <string>↵
#include <map>↵
#include <chrono>↵
#include <stdlib.h>↵
#include <time.h>↵
#include <algorithm>↵
#include <iostream>↵
#include <memory>↵
#include <cstdio>↵
#include <assert.h>↵
#include <iostream>↵
const int MAXN = 300005;↵
int numbers[MAXN];↵
int main() {↵
int t;↵
int n, x;↵
↵
scanf("%d", &t);↵
while (t--)↵
{↵
scanf("%d %d", &n, &x);↵
for (int i = 1; i <= n; i++) {↵
scanf("%d", &numbers[i]);↵
}↵
int num_min = numbers[1];↵
int num_max = numbers[1];↵
int res = 0;↵
for (int i = 2; i <= n; i++) {↵
if (numbers[i] > num_max) {↵
num_max = numbers[i];↵
}↵
if (numbers[i] < num_min) {↵
num_min = numbers[i];↵
}↵
if (num_max - num_min > 2 * x) {↵
res++;↵
num_min = num_max = numbers[i];↵
}↵
}↵
printf("%d\n", res);↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1704C]↵
↵
<spoiler summary="solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
const int N = 500005, inf = 2147483647, M = 1004535809;↵
int n, m, a[N], T, k;↵
struct str {↵
int x, y;↵
}t[N];↵
int main() {↵
scanf("%d", &T);↵
while (T--) {↵
k = 0;↵
scanf("%d %d", &n, &m);↵
for (int i = 1; i <= m; ++i)↵
scanf("%d", &a[i]);↵
sort(a + 1, a + 1 + m);↵
for (int i = 2; i <= m; ++i)↵
t[++k] = { a[i] - a[i - 1] - 1,2 };↵
int num_tmp = a[1] + n - a[m] - 1;↵
if (num_tmp > 0) {↵
t[++k] = { num_tmp, 2 };↵
}↵
sort(t + 1, t + 1 + k, [](str a, str b) {return a.x > b.x; });↵
long long ans = 0, cnt = 0;↵
for (int i = 1; i <= k; ++i) {↵
if (t[i].x - cnt * 2 > 0) {↵
int num_tmp = max(1ll, t[i].x - cnt * 2 - 1);↵
ans += num_tmp;↵
}↵
cnt += 2;↵
}↵
printf("%lld\n", n - ans);↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1704D]↵
↵
<spoiler summary="solution">↵
~~~~~↵
#include <stdio.h>↵
#include <string.h>↵
#include <vector>↵
#include <map>↵
#include <cassert>↵
const int MAXN = 500005;↵
std::vector<long long> numbers[MAXN];↵
std::map<long long, long long> val_to_index;↵
int main()↵
{↵
int t;↵
int n, m;↵
scanf("%d ", &t);↵
while (t--)↵
{↵
val_to_index.clear();↵
scanf("%d %d", &n, &m);↵
long long num_tmp;↵
for (int i = 1; i <= n; i++) {↵
numbers[i].clear();↵
numbers[i].push_back(0);↵
for (int j = 1; j <= m; j++) {↵
scanf("%lld", &num_tmp);↵
numbers[i].push_back(num_tmp);↵
}↵
}↵
long long res_tmp = -1;↵
for (long long i = 1; i <= n; i++) {↵
long long val = 0;↵
for (long long j = 1; j <= m; j++) {↵
val += (j * numbers[i][j]);↵
}↵
if (val_to_index.find(val) != val_to_index.end()) {↵
res_tmp = val;↵
val_to_index[val] = -1;↵
}↵
else {↵
val_to_index[val] = i;↵
}↵
}↵
assert(val_to_index.size() == 2);↵
for (auto &item : val_to_index) {↵
if (item.second != -1ll) {↵
printf("%lld %lld\n", item.second, std::abs(res_tmp - item.first));↵
break;↵
}↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1704E]↵
↵
<spoiler summary="solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
const int N = 500005, inf = 2147483647, M = 998244353;↵
int n, m, a[N], u, v, i, d[N], q[N], r, mx;↵
int b[N], tmp[N];↵
vector<int> g[N], z[N];↵
long long s[N];↵
int p[15];↵
void NEX(int M) {↵
for (int i = 1; i <= n; ++i)↵
if (b[i]) {↵
tmp[i] += b[i] - 1;↵
for (auto it : g[i])↵
++tmp[it];↵
}↵
for (int i = 1; i <= n; ++i) {↵
if (tmp[i] >= M)↵
b[i] = tmp[i] % M + M;↵
else↵
b[i] = tmp[i] % M;↵
tmp[i] = 0;↵
}↵
}↵
int cal(int M) {↵
for (int i = 1; i <= n; ++i) {↵
b[i] = a[i];↵
}↵
for (int i = 1; i <= n; ++i) {↵
bool fl = false;↵
for (int j = 1; j <= n; ++j)↵
if (b[j])↵
fl = true;↵
if (!fl)↵
return i - 1;↵
NEX(M);↵
}↵
return n;↵
}↵
int main() {↵
int t;↵
scanf("%d", &t);↵
while (t--) {↵
scanf("%d %d", &n, &m);↵
for (int i = 1; i <= n; ++i) {↵
scanf("%d", &a[i]);↵
g[i].clear();↵
z[i].clear();↵
d[i] = 0;↵
tmp[i] = 0;↵
s[i] = 0;↵
}↵
for (int i = 1; i <= m; ++i) {↵
scanf("%d %d", &u, &v);↵
++d[u];↵
g[u].push_back(v);↵
z[v].push_back(u);↵
}↵
mx = cal(M);↵
if (mx < n) {↵
cout << mx << endl;↵
continue;↵
}↵
r = 0;↵
for (int i = 1; i <= n; ++i)↵
if (!d[i])↵
q[++r] = i;↵
s[q[1]] = 1;↵
for (int i = 1; i <= r; ++i) {↵
s[q[i]] %= M;↵
for (auto it : z[q[i]]) {↵
--d[it];↵
s[it] += s[q[i]];↵
if (!d[it])↵
q[++r] = it;↵
}↵
}↵
long long ans = n;↵
for (int i = 1; i <= n; ++i)↵
ans = (ans + s[i] * b[i]) % M;↵
cout << ans << endl;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[tutorial:1704F]↵
↵
<spoiler summary="solution">↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
const int N=500005,inf=2147483647,M=998244353;↵
int n,i,t,f[N],vis[N];↵
char c[N];↵
int main(){↵
for(int i=1;i<=1000;++i){↵
for(int j=0;j<=i-2;++j)↵
vis[f[j]^f[i-2-j]]=1;↵
int j;↵
for(j=0;vis[j];++j);↵
f[i]=j;↵
for(int j=0;j<=i;++j)↵
vis[j]=0;↵
}↵
for(int i=1001;i<N;++i)↵
f[i]=f[i-34];↵
scanf("%d",&t);↵
while(t--){↵
scanf("%d",&n);↵
scanf("%s",c+1);↵
int s=0;↵
for(int i=1;i<=n;++i)↵
if(c[i]=='R')↵
++s;↵
else↵
--s;↵
if(s>0)↵
puts("Alice");↵
if(s<0)↵
puts("Bob");↵
if(s==0){↵
int ans=0;↵
for(int i=1;i<=n;){↵
int j=i+1;↵
for(;j<=n&&c[j]!=c[j-1];++j);↵
ans^=f[j-i];↵
i=j;↵
}↵
puts(ans?"Alice":"Bob");↵
}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
The editorials of problem G and H will be adding soon.
