A.Three Strings
题意：给定三个等长的序列a、b、c,将c的每一位与a或b对应的位置互换，是否有一种交换方式使得a、b最终相等。
题解：遍历每一位，如果存在有一位c与a或b相等即可，如果c与a相等，只要将c与b互换；反之，c与b相等，只要将c与a互换。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const int mod = 1e9+7;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
string a,b,c;
cin >> a >> b>> c;
int flag = 1;
for(int i=0;i<a.length();i++)
{
if(a[i]==c[i]||b[i]==c[i])
continue;
else
{
flag=0;
break;
}
}
if(flag)puts("YES");
else puts("NO");
}
return 0;
}B.Motarack's Birthday
题意：给定一段数字序列，其中-1代表未知的数k，让你求出k的值使得序列内相邻两个数的差值最小，输出最小的差值和k所取的值。
题解：如果两个相邻的数均不是-1，则两者的差值就是确定的，我们更新差值最大值，否则我们把确定的数加入到一个数组内，为了使差值最小，我们k肯定要取最大值和最小值的平均值。最终比较确定的差值和k与最大值、最小值的差值，取较大者。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const int mod = 1e9+7;
int a[maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
vector<int>v;
int ans = 0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(a[i]==-1)
{
if((i-1)>=0&&a[i-1]!=-1)
v.push_back(a[i-1]);
}
else
{
if((i-1)>=0)
{
if(a[i-1]==-1)
v.push_back(a[i]);
else
ans=max(ans,abs(a[i]-a[i-1]));
}
}
}
if(v.size()==0)
{
printf("0 0\n");
continue;
}
sort(v.begin(),v.end());
int a = v[0], b=v[v.size()-1];
int k = (a+b)/2;
ans = max(ans,max(k-a,b-k));
printf("%d %d\n",ans,k);
}
return 0;
}C.Ayoub's function（思维）
题意：给定长度为n的0/1序列，其中1的个数为m个，问你0和1要分布才能使包含1的区间个数最多，输出对应的个数。
题解：分析发现长度为n的序列，最多能组成(n+1)*n/2个区间，对于每个0，能组成包含1的区间，只能往右边找到第一个1，所以对于每个0，设它到它右边第一个1的距离为x，不能构成包含1的区间个数为x（x+1）/2。所以我们尽量要让1均匀分部，来使每个0距离它右边的1尽可能地进。所以m个1可以讲0分成m+1组，如果有多余，那么均摊。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
int a[maxn];
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n, m;
scanf("%d%d", &n, &m);
ll ans = 1ll * (n + 1) * n / 2;
if (m == 0)
{
puts("0");
continue;
}
int x = n - m;
int z1 = x / (m + 1);
int z2 = z1 + 1;
int s2 = x % (m + 1);
int s1 = m + 1 - s2;
ans -= 1ll * (z1 + 1) * z1 / 2 * s1 + 1ll * (z2 + 1) * z2 / 2 * s2;
printf("%lld\n", ans);
}
return 0;
}D.Time to Run(模拟)
题意：给定一个n行m列的矩形，矩形内部两两之间都有一条路径，一共有4nm-2n-2m条，每一条路径只能走一次，问你是否有一种方法能恰好走k的长度。如果能输出一种走法。
题解：其实所有的路径都能走完，所以如果k<=4nm-2n-2m就能走，走法有很多种，我的走法如下。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, m, k, cur;
vector<pair<int, char>> ans;
void add(int num, char c)
{
if (num == 0 || cur == k)
return;
num = min(num, k - cur);
ans.push_back({num, c});
cur += num;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
cur = 0;
add(n - 1, 'D');
for (int i = 1; i < m; i++)
{
add(1, 'R');
add(n - 1, 'U');
add(n - 1, 'D');
}
add(m - 1, 'L');
for (int i = n - 1; i >= 1; i--)
{
add(1, 'U');
add(m - 1, 'R');
add(m - 1, 'L');
}
if (cur < k)
puts("NO");
else
{
puts("YES");
printf("%d\n", ans.size());
for (auto i : ans)
printf("%d %c\n", i.first, i.second);
}
return 0;
}E.Nanosoft
题意：在给定的图形里让你求出以为(x1,y1)和(x2,y2)对顶点组成的矩形内最大的符合要求的一个正方形，要求左上角全为红色，左下角权全为黄色，右上角全为绿色，右下角全为蓝色。
题解：我们可以先记录以(i，j)为右下角的每种颜色的最大正方形，通过这个我们可以记录以(1,1)和(i,j)为顶点的矩阵内最大的符合要求的正方形是否存在。最终通过二分半径长度，用二位前缀和来check()要求内矩阵中是否有符合长度要求的正方形，具体看代码。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int n, m, q, L, R, ans, c[maxn][maxn][4], s[maxn][maxn][maxn >> 1];
char a[maxn][maxn];
int f(char x)
{
if (x == 'G')
return 0;
if (x == 'Y')
return 1;
if (x == 'R')
return 2;
if (x == 'B')
return 3;
return -1;
}
bool check(int x, int x1, int y1, int x2, int y2)
{
if (!x)
return 1;
return s[x2][y2][x] - s[x1 + (x << 1) - 2][y2][x] - s[x2][y1 + (x << 1) - 2][x] + s[x1 + (x << 1) - 2][y1 + (x << 1) - 2][x];
}
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i++)
scanf("%s", a[i] + 1);
for (int i = 1, t; i <= n; i++)
for (int j = 1; j <= m; j++)
{
t = f(a[i][j]);
c[i][j][t] = min(min(c[i - 1][j][t], c[i][j - 1][t]), c[i - 1][j - 1][t]) + 1;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 1; k <= min(i >> 1, j >> 1); k++)
{
s[i][j][k] = s[i - 1][j][k] + s[i][j - 1][k] - s[i - 1][j - 1][k];
if (c[i][j][3] >= k && c[i - k][j][0] >= k && c[i][j - k][1] >= k && c[i - k][j - k][2] >= k)
s[i][j][k]++;
}
for (int i = 1, x1, x2, y1, y2; i <= q; i++)
{
ans = 0;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
L = 0;
R = min(x2 - x1 + 1 >> 1, y2 - y1 + 1 >> 1);
while (L < R)
{
int mid = L + R + 1 >> 1;
if (check(mid, x1, y1, x2, y2))
L = mid;
else
R = mid - 1;
}
printf("%d\n", 4 * R * R);
}
return 0;
}F.Super Jaber(多源bfs)
题意：有n * m个城市，每个城市都有一个颜色，共有 k 种颜色，也就是每个城市的颜色只能是 1 ~ k 的某个数字。然后，有q次询问，每次询问给你 x1, y1, x2, y2；问你从(x1, y1)到(x2, y2)的最少操作数。操作有两种： 1、 你可以移动到你当前位置的上下左右，只要不越界。2、你可以移动到任意和你当前所在的位置颜色相同的位置。1 <= n, m <= 1000, k <= min(40, n * m)；
题解：多源bfs，算出每个点到每种颜色的距离，最终只需要比较每个abs(x1-x2)+abs(y1-y2)与(x1,y1)和(x2,y2)到同一种颜色距离再加1的大小。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 510;
int n, m, k;
vector<pair<int, int>> G[50];
int dis[50][1005][1005], vis[50];
queue<pair<int, int>> Q;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int a[1005][1005];
void bfs(int col)
{
for (pair<int, int> v : G[col])
{
dis[col][v.first][v.second] = 0;
Q.push(v);
}
for (int i = 1; i <= k; i++)
vis[i] = 0;
while (!Q.empty())
{
pair<int, int> tmp = Q.front();
Q.pop();
int x = tmp.first, y = tmp.second;
if (!vis[a[x][y]])
{
vis[a[x][y]] = 1;
for (pair<int, int> v : G[a[x][y]])
{
if (dis[col][v.first][v.second] == -1)
{
dis[col][v.first][v.second] = dis[col][x][y] + 1;
Q.push(v);
}
}
}
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m || dis[col][nx][ny] != -1)
continue;
dis[col][nx][ny] = dis[col][x][y] + 1;
Q.push({nx, ny});
}
}
}
int main()
{
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
scanf("%d", &a[i][j]);
G[a[i][j]].push_back({i, j});
}
memset(dis, -1, sizeof(dis));
for (int i = 1; i <= k; i++)
bfs(i);
int q;
scanf("%d", &q);
while (q--)
{
int x1, x2, y1, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
int ans = abs(y1 - y2) + abs(x2 - x1);
for (int i = 1; i <= k; i++)
ans = min(ans, dis[i][x1][y1] + dis[i][x2][y2] + 1);
printf("%d\n", ans);
}
return 0;
}
投递海康威视等公司7个岗位 >