牛客小白月赛99 C~E
牛客小白月赛99 C~E
C-迷宫
思路：其实能不能到达，只要看起点和终点是否能变成连通的。射线技能只能用一次，我们在起点能到的点\((x,y)\)去\(check：x，y,x-1,y-1,y+1\)是否在终点能到达的点的坐标中出现。
// 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;
char a[N][N];
int ds[N][N],de[N][N];
bool vis[N][N];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
bool in(int x,int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>n>>m;
int sx,sy,ex,ey;
for(int i = 1;i <= n; i++)
{
for(int j = 1;j <= m; j++)
{
cin>>a[i][j];
if(a[i][j]=='S')
sx = i,sy = j;
if(a[i][j]=='E')
ex = i,ey = j;
}
}
queue<array<int,3>>q;
memset(ds,127,sizeof(ds));
memset(vis,false,sizeof(vis));
ds[sx][sy] = 0;
q.push({sx,sy,0});
vis[sx][sy] = true;
while(!q.empty())
{
auto [x,y,d] = q.front();
q.pop();
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});
ds[dx][dy] = d + 1;
}
}
}
vector<array<int,2>>vs;
for(int i = 1;i <= n; i++)
for(int j = 1;j <= m; j++)if(ds[i][j] < (1<<30)){
vs.push_back({i,j});
// cout<<"i = "<<i<<" j = "<<j<<"\n";
}
memset(de,127,sizeof(de));
memset(vis,false,sizeof(vis));
de[ex][ey] = 0;
q.push({ex,ey,0});
vis[ex][ey] = true;
while(!q.empty())
{
auto [x,y,d] = q.front();
q.pop();
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});
de[dx][dy] = d + 1;
}
}
}
set<int>x,y;
for(int i = 1;i <= n; i++)
for(int j = 1;j <= m; j++)if(de[i][j] < (1<<30)){
// cout<<"i = "<<i<<" j = "<<j<<"\n";
x.insert(i);
y.insert(j);
}
bool ok = false;
for(auto [i,j] : vs){
if(x.find(i) != x.end())
ok = true;
if(i-1>=1 && x.find(i-1) != x.end())
ok = true;
if(i+1<=n && x.find(i+1) != x.end())
ok = true;
if(y.find(j) != y.end())
ok = true;
if(j-1>=1 && y.find(j-1) != y.end())
ok = true;
if(j+1<=m && y.find(j+1) != y.end())
ok = true;
}
cout<<(ok?"YES":"NO")<<"\n";
return 0;
}
D-又是一年毕业季
思路：如果眨眼时间是质数，那么它的倍数就都不可以。如果眨眼时间是合数，那么它分解出的最小质数就是答案。
那么我们去预处理出质数，然后找到第一个没出现过的质数就是答案。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5e6 + 10;
int n;
ll tot, p[N], pr[N];
bool vis[N];
void prime(int n)
{
for (int i = 2; i <= n; i++)
{
if (!p[i]) p[i] = i, pr[++tot] = i;
for (int j = 1; j <= tot && pr[j] * i <= n; j++) {
p[pr[j] * i] = pr[j];
if(p[i] == pr[j]) break;
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
prime(N);
int t; cin>>t;
while(t--)
{
cin>>n;
vector<int>v;
for(int i = 1;i <= n; i++)
{
ll x; cin>>x;
if(x > 5e6)continue;
vis[x] = true;
v.push_back(x);
}
for(int i = 1;i <= tot; i++)
{
if(!vis[pr[i]])
{
cout<<pr[i]<<"\n";
break;
}
}
for(auto x : v)
vis[x] = false;
}
return 0;
}
E-多米诺骨牌
思路：毫无疑问是用第一个能压倒它的去压倒是最优的。我们记录当前最高的，能压就压，如果在这之前最高的都不能压倒的话，下一块就作为第一块再往后算。最后去前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 f[N];
struct ty
{
int h,x;
}a[N];
bool cmp(int x,int y)
{
return x > y;
}
bool cmp1(ty x,ty y)
{
return x.x < y.x;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int n,m; cin>>n>>m;
for(int i = 1;i <= n; i++)
cin>>a[i].h;
for(int i = 1;i <= n; i++)
cin>>a[i].x;
sort(a+1,a+1+n,cmp1);
int t = 1,mx = a[1].h+a[1].x;
vector<int>ans;
for(int i = 2;i <= n; i++)
{
if(mx >= a[i].x){
t++;
mx = max(mx,a[i].h+a[i].x);
}else{
ans.push_back(t);
t = 1;
mx = a[i].h + a[i].x;
}
}
ans.push_back(t);
sort(ans.begin(),ans.end(),cmp);
ll res = 0;
for(int i = 0;i < min(m,(int)ans.size());i++)
res += ans[i];
cout<<res<<"\n";
}
return 0;
}