Codeforces Round #731 (Div. 3)
在家打了好久COD和战雷，偶尔也得学习一下，要不然感觉时间都浪费了，游戏玩多了也腻，保持适当学习才能爽玩游戏。申请完了也不想做太难的题了，那么就来一场div3保持一下思维敏捷度吧。
A. Shortest Path with Obstacle
题解
这道题的思路很简单，判断block点和start点是否在同一行或者同一列，如果是的话，那么就需要多走2步，否则就是最短曼哈顿距离。
代码
AC代码
#include <bits/stdc++.h>
using namespace std;
constexpr int limit = (4e5 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;
char s = getchar();
while (s > '9' || s < '0') {
if (s == '-')sign = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if (x / 10) print(x / 10);
*O++ = x % 10 + '0';
}
void write(ll x, char c = 't') {
if (x < 0)putchar('-'), x = -x;
print(x);
if (!isalpha(c))*O++ = c;
fwrite(obuf, O - obuf, 1, stdout);
O = obuf;
}
int n, m;
int a[limit];
void solve() {
int xa,ya;
int xb, yb;
cin>>xa>>ya;
cin>>xb>>yb;
int xf, yf;
cin>>xf>>yf;
int ans = abs(xa - xb) + abs(ya - yb);
if(xa == xb){
if(xf == xa){
auto [l, r] = minmax(ya, yb);
if(yf >= l and yf <= r){
cout<<ans + 2<<endl;
return;
}
}
}
if(ya == yb){
if(ya == yf){
auto [l, r] = minmax(xa, xb);
if(xf >= l and xf <= r){
cout<<ans + 2<<endl;
return;
}
}
}
cout<<ans<<endl;
}
int32_t main() {
#ifdef LOCAL
FOPEN;
// FOUT;
#endif
FASTIO
int kase;
cin>>kase;
while (kase--)
invoke(solve);
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
return 0;
}
B. Alphabetical Strings
题解
倒着模拟就行了，没啥难度
代码
AC代码
#include <bits/stdc++.h>
using namespace std;
constexpr int limit = (4e5 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;
char s = getchar();
while (s > '9' || s < '0') {
if (s == '-')sign = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if (x / 10) print(x / 10);
*O++ = x % 10 + '0';
}
void write(ll x, char c = 't') {
if (x < 0)putchar('-'), x = -x;
print(x);
if (!isalpha(c))*O++ = c;
fwrite(obuf, O - obuf, 1, stdout);
O = obuf;
}
int n, m;
int a[limit];
void solve() {
string str;
cin>>str;
n = str.length();
deque<char>q{str.begin(), str.end()};
per(i,0,n - 1){
char c = 'a' + i;
if(q.front() == c){
q.pop_front();
continue;
}
if(q.back() == c){
q.pop_back();
continue;
}
cout<<"NO"<<endl;
return;
}
cout<<"YES"<<endl;
}
int32_t main() {
#ifdef LOCAL
FOPEN;
// FOUT;
#endif
FASTIO
int kase;
cin>>kase;
while (kase--)
invoke(solve);
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
return 0;
}
C. Pair Programming
题解
这个题模拟就行了，如果a不行放b，如果b不行放a，如果都不行输出-1，因为太久没写代码所以卡在了一些implementation details上面
代码
AC代码
#include <bits/stdc++.h>
using namespace std;
constexpr int limit = (4e5 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;
char s = getchar();
while (s > '9' || s < '0') {
if (s == '-')sign = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if (x / 10) print(x / 10);
*O++ = x % 10 + '0';
}
void write(ll x, char c = 't') {
if (x < 0)putchar('-'), x = -x;
print(x);
if (!isalpha(c))*O++ = c;
fwrite(obuf, O - obuf, 1, stdout);
O = obuf;
}
int n, m;
int a[limit];
int b[limit];
void solve() {
int k;
cin>>k>>n>>m;
deque<int>p,q;
rep(i,1,n){
int x;
cin>>x;
p.push_back(x);
}
rep(i,1,m){
int x;
cin>>x;
q.push_back(x);
}
vector<int>ans;
while(p.size() or q.size()){
if(p.size()){
auto x = p.front();
// cout<<x<<endl;
p.pop_front();
if(!x){
ans.push_back(x);
k++;
continue;
}else{
if(x <= k){
ans.push_back(x);
continue;
}else{
if(!q.size()){
cout<<"-1"<<endl;
return;
}
if(q.front() > k){
cout<<"-1"<<endl;
return;
}
ans.push_back(q.front());
k += not q.front();
q.pop_front();
p.push_front(x);
}
}
}else{
auto x = q.front();
// cout<<x<<endl;
q.pop_front();
if(x <= k){
ans.push_back(x);
k += not x;
continue;
}else{
if(!p.size()){
cout<<"-1"<<endl;
return;
}
if(p.front() > k){
cout<<"-1"<<endl;
return;
}
ans.push_back(p.front());
k += not p.front();
p.pop_front();
q.push_front(x);
}
}
}
for(const auto &it : ans){
cout<<it<<" ";
}
cout<<endl;
}
int32_t main() {
#ifdef LOCAL
FOPEN;
// FOUT;
#endif
FASTIO
int kase;
cin>>kase;
while (kase--)
invoke(solve);
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
return 0;
}
D. Co-growing Sequence
题解
这道题就是统计一下前一个和后一个有多少不一样的，很容易想到，没啥说的
代码
AC代码
#include <bits/stdc++.h>
using namespace std;
constexpr int limit = (4e5 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;
char s = getchar();
while (s > '9' || s < '0') {
if (s == '-')sign = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if (x / 10) print(x / 10);
*O++ = x % 10 + '0';
}
void write(ll x, char c = 't') {
if (x < 0)putchar('-'), x = -x;
print(x);
if (!isalpha(c))*O++ = c;
fwrite(obuf, O - obuf, 1, stdout);
O = obuf;
}
#define int ll
int n, m;
int a[limit];
void solve() {
cin>>n;
rep(i,1,n){
cin>>a[i];
}
vector<int>ans(n + 1, 0);
rep(i,2,n){
ll x = a[i - 1] ^ ans[i - 1];
ll y = a[i];
ll res = 0;
rep(j, 0, 30){
ll now = 1ll << j;
int fst = x bitand now;
int scd = y bitand now;
if(fst == scd or scd){
continue;
}
res += now;
}
ans[i] = res;
}
for(const auto &it : ans | views::drop(1)){
cout<<it<<" ";
}
cout<<endl;
}
int32_t main() {
#ifdef LOCAL
FOPEN;
// FOUT;
#endif
FASTIO
int kase;
cin>>kase;
while (kase--)
invoke(solve);
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
return 0;
}
E. Air Conditioners
题解
不会，没想到，等晚上回家补一下，真的不会
F. Array Stabilization (GCD version)
题解
这题刚开始看上去暴力可做，后来发现其实是没考虑需要一段的情况。我们从每一个i开始，让i和i + 1相同，就要除掉这个以i开头连续的段的所有gcd，然后所需要最长的段的长度就是我们的答案(很好理解，因为每次只能消掉一个嘛)
代码
AC代码
#include <bits/stdc++.h>
using namespace std;
constexpr int limit = (4e5 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;
char s = getchar();
while (s > '9' || s < '0') {
if (s == '-')sign = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if (x / 10) print(x / 10);
*O++ = x % 10 + '0';
}
void write(ll x, char c = 't') {
if (x < 0)putchar('-'), x = -x;
print(x);
if (!isalpha(c))*O++ = c;
fwrite(obuf, O - obuf, 1, stdout);
O = obuf;
}
int n, m;
int a[limit];
void solve() {
cin>>n;
rep(i,1,n){
cin>>a[i];
a[i + n] = a[i];
}
int ans = 0;
rep(i,1,n){
auto fst = a[i];
auto scd = a[i + 1];
int res = 0;
int now = i + 1;
while(fst != scd){
// cout<<fst<<" "<<scd<<endl;
fst = gcd(fst, a[now]);
scd = gcd(scd, a[now + 1]);
++now;
++res;
}
ans = max(ans, res);
}
cout<<ans<<endl;
}
int32_t main() {
#ifdef LOCAL
FOPEN;
// FOUT;
#endif
FASTIO
int kase;
cin>>kase;
while (kase--)
invoke(solve);
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
return 0;
}
G. How Many Paths?
题解
这题不出意外又是个大模拟
首先因为这是一个有向图，所以我们不难发现两点
- 如果一个点u在一个环(从点1可到达的连通分量)上，那么点u有无数条path从1到u，从u这个连通分量能够到达的点的path数也是无数的
- 如果一个点u不在一个环上，而从点1到点u有大于一条路径，那么从u出发的path数也是大于1的。
显然，1的优先级是大于2的，所以我们可以先找到所有的环，然后再找到所有的非环但有大于1条路径的点，然后再统计答案。
如何做呢？
首先我们要处理所有的环，把图编程connected DAG，这一步可以用tarjan来做，但是记住我们只dfs 1，如果1到不了的地方直接给0就行。然后重新建图
其次，我们对于情况2，统计从1可达的点的in degree，如果in[u] >= 2， 那么这个点就属于情况2、
最后如果不属于1或者2的，那么就属于是只有一条路径。
其实也没有看上去那么难，对吧？
代码
AC代码
#include <bits/stdc++.h>
using namespace std;
constexpr int limit = (5e5 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll sign = 1, x = 0;
char s = getchar();
while (s > '9' || s < '0') {
if (s == '-')sign = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * sign;
#undef getchar
}//快读
void print(ll x) {
if (x / 10) print(x / 10);
*O++ = x % 10 + '0';
}
void write(ll x, char c = 't') {
if (x < 0)putchar('-'), x = -x;
print(x);
if (!isalpha(c))*O++ = c;
fwrite(obuf, O - obuf, 1, stdout);
O = obuf;
}
int n, m;
int a[limit];
vector<int>g[limit];
// tarjan 缩点
int dfn[limit], low[limit], scc[limit], cnt, scc_cnt;
stack<int> st;
void dfs(int u) {
dfn[u] = low[u] = ++cnt;
st.push(u);
for (auto v : g[u]) {
if (!dfn[v]) {
dfs(v);
low[u] = min(low[u], low[v]);
} else if (!scc[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
++scc_cnt;
while (true) {
int x = st.top();
st.pop();
scc[x] = scc_cnt;
if (x == u)break;
}
}
}
vector<int>g2[limit];
int color[limit];
int in[limit]; // 入度
void solve() {
cin>>n>>m;
set<int>circle;
rep(i,1,n){
g[i].clear();
g2[i].clear();
}
while(st.size())st.pop();
fill(dfn, dfn + 1 + n, 0);
fill(low, low + 1 + n, 0);
fill(color, color + 1 + n, 0);
fill(scc, scc + 1 + n, 0);
fill(in, in + 1 + n, 0);
rep(i,1,m){
int x,y;
cin>>x>>y;
if(x == y){
circle.insert(x);
continue;
} // 去除自环
g[x].push_back(y);
}
scc_cnt = 0;
cnt = 0;
dfs(1);
rep(i,1,n){
if(!low[i]){
color[i] = 0;
}
}
// 接下来处理所有链路上的点
map<int, vector<int>> grp;
rep(i, 1, n){
if(!low[i])
continue;
grp[scc[i]].push_back(i);
}
set<int>real_circle;
for(const auto &[id, nodes] : grp){
if(nodes.size() > 1 or circle.contains(nodes.front())){
for(const auto & it : nodes){
color[it] = -1;
}
real_circle.insert(id);
}
// 重新建图
for(const auto &it : nodes){
for(const auto &v : g[it]){
g2[id].push_back(scc[v]); // 重新连边
in[scc[v]]++;
}
}
}
int vs = scc[1];
// 开始bfs, 先处理有环的点的连边问题
// 此时应该是无环图
map<int, bool>visited;
{
queue<int>q;
for(auto &&src : real_circle){
q.push(src);
visited[src] = 1;
}
while(q.size()){
auto u = q.front();
q.pop();
for(auto &&v : g2[u]){
if(!visited[v]){
visited[v] = true;
q.push(v);
}
}
}
}
for(auto &&[k, v]: visited){
if(v){
for(auto &&node : grp[k]){
color[node] = -1;
}
}
}
map<int, bool>vis;
queue<int>q;
rep(i,1,n){
if(in[i] > 1){
q.push(i);
vis[i] = 1;
}
}
while(q.size()){
auto u = q.front();
q.pop();
if(visited[u])
continue;
for(auto &&v : g2[u]){
if(visited[v])
continue;
if(!vis[v]){
vis[v] = 1;
q.push(v);
}
}
}
for(auto &&[id, v] : vis){
if(visited[id])
continue;
for(auto &&node: grp[id]){
color[node] = 2;
}
}
rep(i,1,n){
if(low[i]){
if(not color[i])
color[i] = 1;
}
}
rep(i,1,n){
cout<<color[i]<<" ";
}
cout<<endl;
}
int32_t main() {
#ifdef LOCAL
FOPEN;
// FOUT;
#endif
FASTIO
int kase;
cin>>kase;
while (kase--)
invoke(solve);
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
return 0;
}