Codeforces Round 731 (Div 3)(A - F)

Codeforces Round 731 (Div. 3)(A - F)

Dashboard - Codeforces Round 731 (Div. 3) - Codeforces

A. Shortest Path with Obstacle（思维）

思路：显然要计算 A → B 之间的曼哈顿距离 ， 要绕开 F 当且仅当 AB形成的直线平行于坐标轴且 F 在 AB之间 ， 绕开贡献加2即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t;int x_1 , y_1 , x_2 , y_2 , x_3 , y_3 , res;signed main(){IOScin >> t;while(t --){res = 0;cin >> x_1 >> y_1;cin >> x_2 >> y_2;cin >> x_3 >> y_3;bool tag = 0;if(x_1 == x_2 && x_2 == x_3 && y_3 > min(y_1 , y_2) && y_3 < max(y_1 , y_2)) tag = 1;if(y_1 == y_2 && y_2 == y_3 && x_3 > min(x_1 , x_2) && x_3 < max(x_1 , x_2)) tag = 1;res += abs(x_1 - x_2) + abs(y_1 - y_2);if(tag) res += 2;cout << res << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

B. Alphabetical Strings（双指针）

思路：维护头尾两个指针 ， 不断往中间找加入的字母 ， 找不到跳出 ， 判断指针是否相遇即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t , l , r , n;
string s;signed main(){IOScin >> t;while(t --){cin >> s;r = s.size();l = 1;n = r;s = '#' + s;while(l <= r){if(s[r] == (char)('a' - 1 + n)) r -= 1 , n -= 1;else if(s[l] == (char)('a' - 1 + n)) l += 1 , n -= 1;else break;}if(l > r) cout << "YES\n";else cout << "NO\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

C. Pair Programming(栈 + 贪心)

思路：需要保证在原数列中的相对位置不变 ， 不难想出合并后的操作序列就是一个出栈序列 ，维护两个栈 ， 贪心的选 ， 有 0 选 0 ， 没 0 去检查这两个数是否能处理即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int n , k , x , y , t;
int a[N] , b[N] , ans[N];	signed main(){IOScin >> t;while(t --){cin >> k >> x >> y;stack<int>st1 , st2;for(int i = 1 ; i <= x; i ++) cin >> a[i];for(int i = x ; i >= 1 ; i --) st1.push(a[i]);for(int i = 1 ; i <= y; i ++) cin >> b[i];for(int i = y ; i >= 1 ; i --) st2.push(b[i]);for(int i = 1 ; i <= x + y ; i ++){if(st1.size() && st1.top() == 0){ans[i] = 0;st1.pop();k += 1;}else if(st2.size() && st2.top() == 0){ans[i] = 0;st2.pop();k += 1;}else{if(st1.size() && k >= st1.top()){ans[i] = st1.top();  st1.pop();}else if(st2.size() && k >= st2.top()){ans[i] = st2.top();st2.pop();}else break;}}if(st1.size() || st2.size()) cout << "-1\n";else{for(int i = 1 ; i <= x + y ; i ++) cout << ans[i] << " ";cout << '\n';}}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

D. Co-growing Sequence（位运算）

思路：对于 b 数组 ， 我们从前往后处理 ， 贪心的让每一位最小就能保证字典序最小。那么怎么让每一位最小呢。对于题中所限制的条件(growing)

$$xandy=x$$

即需要 x 为 1 的位 y 当前位 必须是 1

对于 b 数组 ， 我们可以考虑 b 是通过异或操作为 a 数组补位来达到题目要求的条件。

b 数组的首位显然贪心的放 0 。 对于其后每一位 ，贪心的考虑当前的 b 最小即可 ， 即当且仅当前一个数当前位为 1 ， 后一个数当前位为 0 时，需要通过异或操作放 1 补位 ， 计算贡献即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int n , t , a[N] , b[N];signed main(){IOScin >> t;while(t --){cin >> n;for(int i = 1 ; i <= n ; i ++) cin >> a[i];b[1] = 0;for(int i = 2 ; i <= n ; i ++){a[i - 1] ^= b[i - 1];b[i] = 0;for(int j = 0 ; j <= 30 ; j ++){int x = (a[i - 1] >> j & 1);int y = (a[i] >> j & 1);if(x && !y) b[i] += (1 << j);}}for(int i = 1 ; i <= n ; i ++) cout << b[i] << " ";cout << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

E. Air Conditioners（思维）

思路：很好的一道思维题 ， 对于每一个位置 ， 我们分别考虑其前边的空调和其后边的空调对其的影响。以前边空调举例 ， 由于一个点前面的空调对当前点的影响是 温度 + 距离 ，这个总和是不变的， 我们不妨把前面的空调都等价到一号坐标点 ，这样距离都固定了 ， 我们只需要维护一个最小温度即可 。 对于后边空调的影响反向处理一遍即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t , n , k;
int ans[N] , pos[N] , val[N];signed main(){IOScin >> t;while(t --){cin >> n >> k;for(int i = 1 ; i <= n ; i ++){ans[i] = 9e18;val[i] = 0;}for(int i = 1 ; i <= k ; i ++) cin >> pos[i];for(int i = 1 ; i <= k ; i ++) cin >> val[pos[i]];int minn = 9e18;for(int i = 1 ; i <= n ; i ++){if(val[i]) minn = min(minn , val[i] - (i - 1));ans[i] = min(ans[i] , minn + (i - 1));}minn = 9e18;for(int i = n ; i >= 1 ; i --){if(val[i]) minn = min(minn , val[i] - (n - i));ans[i] = min(ans[i] , minn + (n - i));}for(int i = 1 ; i <= n ; i ++) cout << ans[i] << " ";cout << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

F. Array Stabilization (GCD version)（st表维护区间gcd）

思路：假如原数组是 a 数组 ， 我们模拟一下这个过程

a1	a2	a3	a4
gcd(a1 , a2)	gcd(a2 , a3)	gcd(a3 , a4)	gcd(a4 , a1)
gcd(a1 , a2 , a3)	gcd(a2 , a3 , a4)	gcd(a3 , a4 , a2)	gcd(a3 , a4 , a1)
gcd(a1 , a2 , a3 , a4)	gcd(a2 , a3 , a4 , a1)	gcd(a3 , a4 , a2 , a1)	gcd(a3 , a4 , a1 , a2)

不难发现最多 n - 1 次是一定能让所有的数字相等的 ， 而且这个次数满足二分性 ， 考虑二分 ， 那么问题就转化成了如何处理区间gcd的问题 ， 考虑st表处理即可 。 对于环 ， 我们把数组变成二倍长度断环为链。复杂度

$$O(nlogn)$$

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;int t , n;int a[N] , st[N][21];int get(int x , int y){int l = x , r = x + y - 1 , len = y;int now = log2(len);return __gcd(st[l][now] , st[r - (1 << now) + 1][now]);
}bool judge(int x){for(int i = 1 ; i < n ; i ++) if(get(i , x + 1) != get(i + 1 , x + 1)) return 0;return 1;
}signed main(){IOScin >> t;while(t --){cin >> n;for(int i = 1 ; i <= n ; i ++) cin >> a[i];for(int i = n + 1 ; i <= 2 * n ; i ++) a[i] = a[i - n];for(int i = 1 ; i <= 2 * n ; i ++) st[i][0] = a[i];for(int j = 1 ; j <= 20 ; j ++){for(int i = 1 ; i + (1 << j) - 1 <= 2 * n ; i ++){st[i][j] = __gcd(st[i][j - 1] , st[i + (1 << (j - 1))][j - 1]);}}int l = 0 , r = n ;while(l < r){int mid = (l + r) >> 1;if(judge(mid)) r = mid;else l = mid + 1;}cout << l << "\n";}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);