牛客小白月赛100 A~E
A-ACM中的A题
签到不多说
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N],b[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
for(int i = 1;i <= 3; i++)
cin>>a[i];
bool ok = false;
for(int i = 1;i <= 3; i++)
{
int t = a[i];
for(int j = 1;j <= 3; j++)
{
b[j] = a[j];
}
b[i] = t*2;
sort(b+1,b+1+3);
// cout<<b[1]<<" "<<b[2]<<" "<<b[3]<<"\n";
if(b[1] + b[2] > b[3])
ok = true;
}
if(ok)cout<<"Yes\n";
else cout<<"No\n";
return 0;
}
B-ACM中的C题
思路：我们知道肯定是没交互过的之间进行交互更优。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n; cin>>n;
for(int i = 1;i <= n; i++)
cin>>a[i];
ll ans = 0;
if(n==1)ans = -1;
else if(n==2)ans = 1;
else if(n==3)ans = 2;
else{
ans = (n+1)/2;
}
cout<<ans<<"\n";
return 0;
}
C-ACM中的M题
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N],b[N];
vector<int>type[N];
map<int,int>mp;
int cnt = 0;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n; cin>>n;
for(int i = 1;i <= n; i++)
cin>>a[i];
for(int i = 1;i <= n; i++)
{
cin>>b[i];
if(mp[b[i]] == 0)
mp[b[i]] = ++cnt;
type[mp[b[i]]].push_back(a[i]);
}
ll ans = 0;
for(int i = 1;i <= cnt; i++)
{
if(type[i].size()==1)
{
ans = -1;
break;
}
ans += (type[i].size()+1)/2;
}
cout<<ans<<"\n";
return 0;
}
D-ACM中的AC题
无非就是三种情况：
- 我先到
- 镜像先到
- 一起到
其实本质上都是一种。
我们可以先做一个预处理，预处理出每一个出口到每一个点的最短距离。然后在做bfs，注意两个一起走，都不能越界和到陷阱里面。
因为是关于\(sx,sy\)对称的，因此可以通过我的\((x_1,y_1)\)推出镜像的(\(2 * sx - x_1,2*sy-x_2\))。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e3 + 10;
int n,m,sx,sy;
char a[N][N];
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int ans = 1e9;
bool vis[N][N];
int dist[N][N];
bool in(int x,int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void init()
{
memset(dist,0x3f,sizeof(dist));
queue<array<int,3>>q;
for(int i = 1;i <= n; i++)
for(int j = 1;j <= m; j++)if(a[i][j] == '@'){
q.push({i,j,0});
vis[i][j] = true;
}
while(!q.empty())
{
auto [x,y,d] = q.front();
q.pop();
dist[x][y] = d;
for(int i = 0;i < 4; i++)
{
int dx = x + dir[i][0];
int dy = y + dir[i][1];
if(in(dx,dy) && a[dx][dy] != '#' && !vis[dx][dy]){
vis[dx][dy] = true;
q.push({dx,dy,d + 1});
}
}
}
}
void bfs(int sx,int sy)
{
memset(vis,false,sizeof(vis));
queue<array<int,3>>q;
q.push({sx,sy,0});
vis[sx][sy] = true;
while(!q.empty()){
auto [x,y,d] = q.front();
q.pop();
if(a[x][y] == '@'){
ans = min(ans,d + dist[2*sx-x][2*sy-y]);
}
for(int i = 0;i < 4; i++)
{
int dx1 = x + dir[i][0];
int dy1 = y + dir[i][1];
int dx2 = 2 * sx - dx1;
int dy2 = 2 * sy - dy1;
if(in(dx1,dy1) && in(dx2,dy2) && !vis[dx1][dy1] && a[dx1][dy1] != '#' && a[dx2][dy2] != '#'){
vis[dx1][dy1] = true;
q.push({dx1,dy1,d+1});
}
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>n>>m>>sx>>sy;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m; j++)
cin>>a[i][j];
init();
bfs(sx,sy);
if(ans == 1e9) ans = -1;
cout<<ans<<"\n";
return 0;
}
E-ACM中的CM题
思路：我们可以考虑枚举排雷能力。二分找到第一个大于pos+m的地方，不断往后跳，算贡献取min即可。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n; cin>>n;
for(int i = 1;i <= n; i++)
cin>>a[i];
sort(a+1,a+1+n);
int ans = n;
for(int m = 0;m < n; m++)
{
int t = m;
int pos = a[1];
while(1)
{
t++;
pos = upper_bound(a+1,a+1+n,pos+m)-a;
if(pos == n+1)break;
pos = a[pos];
}
ans = min(ans,t);
}
cout<<ans<<"\n";
return 0;
}