第二次在牛客上AK（可能是数据比较水？被我卡过去了？）
总的来说感觉题目原题偏多？没有特别难的防AK题好评
A、Race
题意：给出两个人的速度，和赛道总长度，如果小明超过小红一定的距离，需要等待T秒，问谁先到终点
模拟，只在整数秒判断状态即可，注意只需要小明等待小红，不需要双向等待。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int main()
{
int v1, v2, t, s, l;
sc("%d%d%d%d%d", &v1, &v2, &t, &s, &l);
double a = 0, b = 0; int time = 0;
int time1 = 0, time2 = 0;
while (a < l && b < l)
{
a += v1; b += v2;
time++;
if (a >= l || b >= l)
break;
if (a >= b + t)
{
for (int i = 0; i < s; i++)
{
b += v2;
time++;
if (b >= l)
goto qwe;
}
}
}
qwe:;
if (a >= l && b >= l)
pr("Tie %d\n", time);
else if (a >= l)
pr("Ming %d\n", time);
else
pr("Hong %d\n", time);
} B、Min Value 题意：给一个数组，取两个数字，要求两个数字的和的绝对值最小，第二要求下标之和最小
对于每个数字，我们只需要找到最接近他的相反数的数字即可，使用set即可解决
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
map<int, int>mp;
int a[200005];
int main()
{
int n;
sc("%d", &n);
for (int i = 1; i <= n; i++)
{
sc("%lld", &a[i]);
if (!mp.count(a[i]))
mp[a[i]] = i;
}
int ans = 1e9 + 7, ans1 = 0;
set<int>s;
s.insert(a[1]);
for (int i = 2; i <= n; i++)
{
auto it = s.lower_bound(-a[i]);
if (it != s.end())
{
int num = *it;
if (ans > abs(num + a[i]))
{
ans = abs(num + a[i]);
ans1 = i + mp[num];
}
else if (ans == abs(num + a[i]))
{
ans1 = min(ans1, i + mp[num]);
}
}
if (it != s.begin())
{
it--;
int num = *it;
if (ans > abs(num + a[i]))
{
ans = abs(num + a[i]);
ans1 = i + mp[num];
}
else if (ans == abs(num + a[i]))
{
ans1 = min(ans1, i + mp[num]);
}
}
s.insert(a[i]);
}
pr("%d %d\n", ans, ans1);
} C、Coronavirus 题意：n*m的图，高危地区旁边8个位置不能走，求能否从S走到E，最短步数
简单bfs，先把所有高危地区的旁边标记，然后直接bfs即可。注意要判断高危地区旁边的是不是高危地区，如果是的话，不需要覆盖标记。
简单bfs，先把所有高危地区的旁边标记，然后直接bfs即可。注意要判断高危地区旁边的是不是高危地区，如果是的话，不需要覆盖标记。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
char s[55][55];
int dir[4][2] = { 1,0,0,1,-1,0,0,-1 };
struct node
{
int first;
int second;
int step;
};
int book[55][55];
int main()
{
int n, m;
sc("%d%d", &n, &m);
queue<node>q;
for (int i = 1; i <= n; i++)
sc("%s", s[i] + 1);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (s[i][j] == 'S')
{
q.push(node{ i,j,0 });
book[i][j] = true;
}
if (s[i][j] == '*')
{
for (int q = i - 1; q <= i + 1; q++)
{
for (int w = j - 1; w <= j + 1; w++)
{
if (s[q][w] == '.')
s[q][w] = '@';
if (s[q][w] == 'E')
{
pr("Impossible\n");
return 0;
}
}
}
}
}
}
while (!q.empty())
{
node t = q.front();
if (s[t.first][t.second] == 'E')
{
pr("%d\n", t.step);
return 0;
}
q.pop();
for (int k = 0; k < 4; k++)
{
int tx = t.first + dir[k][0];
int ty = t.second + dir[k][1];
if (tx<1 || tx>n || ty<1 || ty>m)
continue;
if (book[tx][ty] == true || s[tx][ty] == '*' || s[tx][ty] == '@')
continue;
book[tx][ty] = true;
q.push(node{ tx,ty,t.step + 1 });
}
}
pr("Impossible\n");
} D、Array 题意：n个数字异或值已知，和已知，求最少多少个数字满足题目所述的条件
CF原题的简单版？可以证明3个数字一定足够 a, (b-a)/2, (b-a)/2
《Codeforces Round #628 (Div. 2) D》
给两个数字，a,b ，一些数字异或等于a，求和等于b，问数字至有多少个并输出
若a>b，显然无解，然后由于题意特判0 0 和a==b的情况。
剩下的情况，由于异或的特性，a,b的奇偶性相同，所以判断不行的，就剩下 a, (b-a)/2, (b-a)/2
然后判断一下 a 能不能和 (b-a)/2 合成一个数字即可
若a>b，显然无解，然后由于题意特判0 0 和a==b的情况。
剩下的情况，由于异或的特性，a,b的奇偶性相同，所以判断不行的，就剩下 a, (b-a)/2, (b-a)/2
然后判断一下 a 能不能和 (b-a)/2 合成一个数字即可
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int main()
{
ll a, b;
while (sc("%lld%lld", &a, &b) > 0)
{
if (a > b)
pr("-1\n");
else if (a == 0 && b == 0)
pr("0\n");
else if (a == b)
pr("1\n");
else
{
ll x = (b - a) / 2;
if ((b - a) & 1)
pr("-1\n");
else if ((x & a) == 0)
pr("2\n");
else
pr("3\n");
}
}
} E、Prize 题意：给n个数字，给m个匹配长度，每个匹配位置可能有多个数字满足匹配要求，问有多少个完全匹配题目给定的m个条件
暴力复杂度大概1.6e9，过不去，(然后想起了这学期讲了个从后往前匹配可能会更快?)，然后尝试一下，过了？不知道能不能证明复杂度，不过我猜是数据比较弱让我卡过去了？（运行时间： 219 ms）
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e6 + 5;
char s[MAXN];
bool a[805][11];
int main()
{
int n, m;
sc("%d%d", &n, &m);
sc("%s", s + 1);
for (int i = 1; i <= m; i++)
{
int t; sc("%d", &t);
while (t--)
{
int tt; sc("%d", &tt);
a[i][tt] = true;
}
}
int cnt = 0;
for (int i = n; i >= m; i--)
{
for (int j = i, k = m; j >= i - m + 1 && k >= 1; j--, k--)
{
if (a[k][s[j] - '0'] == false)
goto qwe;
}
cnt++;
i = i + 1 - m;
qwe:;
}
if (cnt == 0)
pr("Failed to win the prize");
else
pr("%d", cnt);
} F、Animal Protection 题意：求不包含给定点的，构成的不同矩形的数量。
大概两年前网络赛的原题？暴力枚举，复杂度大概在 O(n*m*min(n,m))
本题大概在 1e9/2=4e8，感觉在超时的边缘试探，然后过了，感谢出题人放过
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
char s[1005];
int e[1005][1005], up[1005];
const ll mod = 1e9 + 7;
int main()
{
int t, n, m, k, a, b;
ll ans = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
sc("%s", s + 1);
for (int j = 1; j <= m; j++)
{
if (s[j] == 'X')
e[i][j] = 1;
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
if (e[i][j])
up[j] = i;
for (int j = 1; j <= m; j++)
{
ll temp = LLONG_MAX;
for (int k = j; k >= 1; k--)
{
temp = min(temp, (ll)(i - up[k]));
ans = (ans + temp);
}
}
}
printf("%lld\n", ans % mod);
} G、XOR 题意：从1-n里面选两个数字异或最大值
注意到我们只要取最高位为1其他为0 和 最高位为0其他为1的两个数字即可满足从最高位开始全为1，最大。
由于两个数字必须不同，所以注意特判0
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int main()
{
ll n, ans = 0;
sc("%lld", &n);
if (n==1)
{
pr("0");
return 0;
}
for (ll i = 1; true; i = i * 2)
{
if (i <= n)
ans += i;
else
break;
}
pr("%lld\n", ans);
} H、Maze 题意：n*m的图，图中只包含+，-两个符号，+只能走到-，-只能走到+，q次询问，每个询问给出一个点，问这个点能到达的点的数量
显然，一个点能走到的点的对应查询答案是一样的，所以我们对图进行染色并且记录每个颜色的数量即可。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define Pair pair<int,int>
using namespace std;
const int MAXN = 3005;
char ss[MAXN];
int s[MAXN][MAXN];
bool book[MAXN][MAXN];
int color[MAXN][MAXN];
int ans[MAXN * MAXN];
int dir[4][2] = { 1,0,0,1,-1,0,0,-1 };
int n, m, k;
void dfs(int x, int y, int cnt)
{
queue<Pair>q;
q.push(Pair{ x,y });
while (!q.empty())
{
Pair t = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
int tx = t.first + dir[k][0];
int ty = t.second + dir[k][1];
if (tx<1 || tx>n || ty<1 || ty>m)
continue;
if (book[tx][ty] == true || s[tx][ty] == s[t.first][t.second])
continue;
book[tx][ty] = true;
color[tx][ty] = cnt;
ans[cnt]++;
q.push(Pair{ tx,ty });
}
}
}
int main()
{
sc("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
{
sc("%s", ss + 1);
for (int j = 1; j <= m; j++)
s[i][j] = (ss[j] == '+' ? 1 : 0);
}
int cnt = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (book[i][j] == false)
{
book[i][j] = true;
color[i][j] = cnt;
ans[cnt]++;
dfs(i, j, cnt);
cnt++;
}
}
while (k--)
{
int x, y;
sc("%d%d", &x, &y);
pr("%d\n", ans[color[x][y]]);
}
} I、Prime题意：求区间质数个数
埃筛或者欧拉筛都可通过此题
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e7 + 5;
bool vis[MAXN];
int prime[MAXN];
int cnt = 0;
int sub[MAXN];
void Eluer()
{
for (int i = 2; i < MAXN; i++)
{
if (vis[i] == false)
{
prime[cnt++] = i;
}
for (int j = 0; j < cnt && i * prime[j] < MAXN; j++)
{
vis[i * prime[j]] = true;
if (i % prime[j] == 0)
break;
}
}
sub[1] = 0;
for (int i = 2; i < MAXN; i++)
sub[i] = sub[i - 1] + (vis[i] == false ? 1 : 0);
}
int main()
{
Eluer();
int T;
sc("%d", &T);
while (T--)
{
int a, b;
sc("%d%d", &a, &b);
pr("%d\n", sub[b] - sub[a - 1]);
}
} J、Compare题意：比较两个最多1000位数字的大小
字符串或者上JAVA大数
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
char s1[100005], s2[100005];
int main()
{
sc("%s%s", s1, s2);
int len1 = strlen(s1);
int len2 = strlen(s2);
if (len1 > len2)
pr(">");
else if (len1 < len2)
pr("<");
else
{
for (int i = 0; i < len1; i++)
{
if (s1[i] < s2[i])
{
pr("<");
return 0;
}
if (s1[i] > s2[i])
{
pr(">");
return 0;
}
}
pr("=");
}
} K、Walk 题意：n*m的图，从左上角走到右下角，步数最少的情况有多少种
欧拉计划原题?最少要走n+m-2步，假设这些步数都走右边，那么我们要选择其中的m-1步向下走才能到达右下角，所以答案是C(n+m-2,m-1)
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e6 + 5;
const ll mod = 1e9 + 7;
ll invi[MAXN], fac[MAXN], inv[MAXN];
void init()
{
invi[0] = invi[1] = 1;
fac[0] = 1;
inv[0] = 1;
for (int i = 2; i < MAXN; i++)
invi[i] = invi[mod % i] * (ll)(mod - mod / i) % mod;
for (int i = 1; i < MAXN; i++)
{
fac[i] = fac[i - 1] * i % mod;
inv[i] = invi[i] * inv[i - 1] % mod;
}
}
ll C(ll n, ll m)
{
ll ans = fac[n] * inv[m] % mod * inv[n - m] % mod;
return ans;
}
int main()
{
init();
int T;
sc("%d", &T);
while (T--)
{
ll n, m;
sc("%lld%lld", &n, &m);
n--, m--;
ll ans = C(n + m, m);
pr("%lld\n", ans);
}
} L、Defeat the monster 题意：有n个人，选择最大值与最小值不超过5的最大人数
这个题目怎么长的有点眼熟？这不是我出的牛客小白赛嘛。滑动窗口、二分都可解决这个问题，可以参考 牛客小白月赛24B https://ac.nowcoder.com/acm/contest/5158/B
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll a[200005];
int main()
{
int n;
sc("%d", &n);
for (int i = 1; i <= n; i++)
sc("%lld", &a[i]);
sort(a + 1, a + 1 + n);
int ans = 0, st = 1, ed = 0;
while (ed < n)
{
ed++;
while (a[ed] > a[st] + 5)
st++;
ans = max(ans, ed - st + 1);
}
pr("%d\n", ans);
} 
京公网安备 11010502036488号