A Shortest Path with Obstacle
题目大意
给你一个位置A,一个位置B,还有一个不能经过的位置F,让你判断需要多少步能从A到B
主要思路
答案为A到B的曼哈顿距离,仅当ABF在一条直线上且F在AB中间时答案+2
AC代码
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <string>
#include <cmath>
#include <unordered_map>
#include <queue>
#include <map>
using namespace std;
#define int long long
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef pair<int, int> P;
const int N = 200010;
int n, a[N];
signed main(void)
{
int T;
cin >> T;
while(T--)
{
int x, y, x1, y1, x2, y2;
cin >> x >> y >> x1 >> y1 >> x2 >> y2;
if(x == x1 && x1 == x2 && (y < y2 && y2 < y1 || y > y2 && y2 > y1) || y == y1 && y1 == y2 && (x < x2 && x2 < x1 || x > x2 && x2 > x1))
{
cout << abs(x - x1) + abs(y - y1) + 2 << endl;
}
else
{
cout << abs(x - x1) + abs(y - y1) << endl;
}
}
return 0;
}
B Alphabetical Strings
题目大意
从a到z添加字母,每次只能添加在字符串的最左边或者最右边,给定一个字符串,问该字符串是不是由此操作得到的
主要思路
从a开始,用两个指针来往左或往右判断即可
AC代码
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <string>
#include <cmath>
#include <unordered_map>
#include <queue>
#include <map>
using namespace std;
#define int long long
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef pair<int, int> P;
const int N = 200010;
int n, a[N];
signed main(void)
{
int T;
cin >> T;
while(T--)
{
string t;
cin >> t;
int l, r;
bool flag1 = false;
for(int i = 0; i < t.size(); i++)
{
if(t[i] == 'a') l = r = i, flag1 = true;
}
bool flag = true;
char c = 'b';
while(true)
{
if(l > 0 && t[l - 1] == c)
{
l--;
c++;
}
else if(r < t.size() - 1 && t[r + 1] == c)
{
r++;
c++;
}
else
{
if(l != 0 || r != t.size() - 1) flag = false;
break;
}
}
if(flag && flag1) puts("YES");
else puts("NO");
}
return 0;
}
C Pair Programming
题目大意
刚开始给你一个大小K,然后给a,b两个数组,问你能否在不改变a,b数组本身顺序的情况下,合并a,b数组,且合并后的数组要满足,当数组元素为0时k+1,当不为0时该元素值>=k
主要思路
贪心+双指针,a,b两个数组分别一个指针,当有0时继续遍历,直到a,b都不为0时判断能否将两个元素放入合并后的数组
AC代码
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <string>
#include <cmath>
#include <unordered_map>
#include <queue>
#include <map>
using namespace std;
#define int long long
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef pair<int, int> P;
const int N = 310;
int a[N], b[N];
int cnt, ans[N];
signed main(void)
{
int T;
cin >> T;
while(T--)
{
cnt = 0;
int k, n, m;
cin >> k >> n >> m;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < m; i++) cin >> b[i];
int ta = 0, tb = 0;
int t = k;
bool flag = true;
while(cnt < n + m && flag)
{
if(a[ta] == 0 && ta < n) ans[cnt++] = a[ta], ta++, t++;
else if(b[tb] == 0 && tb < m) ans[cnt++] = b[tb], tb++, t++;
else
{
if(a[ta] <= t && ta < n) ans[cnt++] = a[ta], ta++;
else if(b[tb] <= t && tb < m) ans[cnt++] = b[tb], tb++;
else if(a[ta] > t && ta < n && b[tb] > t && tb < m ||
(ta >= n && b[tb] > t && tb < m) ||
(a[ta] > t && ta < n && tb >= m)) flag = false;
}
}
if(flag)
{
for(int i = 0; i < n + m; i++)
{
cout << ans[i] << ' ';
}
cout << endl;
}
else cout << -1 << endl;
}
return 0;
}
D Co-growing Sequence
题目大意
给一个数组x,想让你求一个字典序最小数组y,使x的每个元素与y异或后的数组k,满足ki & ki+1 = ki
主要思路
- 当(x[i] & (x[i - 1] ^ y[i - 1])) == (x[i - 1] ^ y[i - 1])满足时y[i] = 0
- 否则,设t = x[i - 1] ^ y[i - 1],(x ^ y) & t = t 说明t二进制表示中为1的位,(x ^ y)也一定为1,想求y最小本质上是找t中二进制位为1而x中二进制位为0的位,y中的这一位一定为1且仅这些位为1,那么y最小
AC代码
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <string>
#include <cmath>
#include <unordered_map>
#include <queue>
#include <map>
using namespace std;
#define int long long
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef pair<int, int> P;
const int N = 200010;
int n, x[N], y[N];
int t[N];
signed main(void)
{
int T;
cin >> T;
while(T--)
{
cin >> n;
for(int i = 0; i < n; i++) cin >> x[i];
y[0] = 0;
for(int i = 1; i < n; i++)
{
if((x[i] & (x[i - 1] ^ y[i - 1])) == (x[i - 1] ^ y[i - 1])) y[i] = 0;
else
{
int t = x[i - 1] ^ y[i - 1];
y[i] = (x[i] ^ t) & t;
}
}
for(int i = 0; i < n; i++) cout << y[i] << ' ';
cout << endl;
}
return 0;
}
E Air Conditioners
题目大意
给一个n和k,位置为1~n,接下来给一个长度为k的数组表示空调的位置,再给一个长度为k的数组表示该位置空调的温度,距离空调位置为1那么温度+1,问每个位置的最低温度
主要思路
我们先从左往右扫描一遍空调对右边元素的影响,再从右往左扫描一遍空调对左边元素影响即可
AC代码
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <string>
#include <cmath>
#include <unordered_map>
#include <queue>
#include <map>
using namespace std;
#define int long long
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef pair<int, int> P;
const int N = 300010;
int st[N], a[N];
int n, k;
signed main(void)
{
int T;
cin >> T;
while(T--)
{
memset(a, 0x3f, sizeof(a));
cin >> n >> k;
for(int i = 0; i < k; i++) cin >> st[i];
for(int i = 0; i < k; i++)
{
cin >> a[st[i]];
}
for(int i = 2; i <= n; i++) a[i] = min(a[i], a[i - 1] + 1);
for(int i = n - 1; i >= 1; i--) a[i] = min(a[i], a[i + 1] + 1);
for(int i = 1; i <= n; i++) cout << a[i] << ' ';
puts("");
}
return 0;
}
F Array Stabilization (GCD version)
题目大意
给定一个长度为n的环,我们对数组每次操作都能使ai = gcd(a[i], a[i + 1]),问至少进行多少次操作使数组所有值相等
主要思路
将长度为n的环展开为2*n的数组,也就是将两个长度为n的数组拼起来,便于操作(环常用操作)。
gcd(gcd(a, b), gcd(b, c)) == gcd(gcd(a, b), c)
如果有两个相邻的数x[i], x[i+1]不等, 由于这个公式,那我们每次都往后取gcd直到两个数相同为止,记下每次操作的最大次数,最后取一个max即可。
AC代码
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <string>
#include <cmath>
#include <unordered_map>
#include <queue>
#include <map>
using namespace std;
#define int long long
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef pair<int, int> P;
const int N = 200010;
int n, a[2 * N];
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
signed main(void)
{
int T;
cin >> T;
while(T--)
{
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> a[i];
a[i + n] = a[i];
}
int ans = 0;
for(int i = 0; i < n; i++)
{
int cnt = 0;
int x = a[i];
int y = a[i + 1];
int t = i + 1;
while(x != y)
{
x = gcd(x, a[t]);
y = gcd(y, a[t + 1]);
t++;
cnt++;
}
ans = max(ans, cnt);
}
cout << ans << endl;
}
return 0;
}