B
BFS 思维
网格图上从起点到终点,只能往上下右走,人有一个视野,超出范围的看不到。问是否存在一个死胡同,会误导人走进来
等价于是否存在一个路径,人没走进来时无法确定是不是死路,只有等走进来了才能发现是死路(由于不能往左走,此时已经晚了,游戏失败)
首先需要找到所有死路的点,这可以通过找到所有能到终点的路径,剩下的就是所有死路包含的点。从起点出发,到终点,经过的所有可能点,可以分别从起点和终点出发BFS,所有同时被两次访问到的就是。剩下那些能从起点出发到达的,但不能从终点出发到达的,就是死路的点。
接下来就是找是否存在一个死路,他在左右方向上足够深,超出角色的视野,用一个dp维护所有死路点所在连通块的最大列号即可。最后检查所有死路点的深度,看是否存在一个深度大于视野即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;
void solve() {
int n,m,k;
cin>>n>>m>>k;
// array<array<int,m+1>,n+1>a,v1,v2,dep;
vector<vector<int>>a(n+1,vector<int>(m+1));
vector<vector<bool>>v1(n+1,vector<bool>(m+1));
vector<vector<bool>>v2(n+1,vector<bool>(m+1));
vector<vector<int>>dep(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++){
string s;
cin >> s;
for(int j=1;j<=m;j++){
a[i][j]=s[j-1]-'0';
}
}
queue<pair<int,int>>q;
v1[1][1]=1;
q.push({1,1});
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
while(q.size()){
auto p=q.front();
q.pop();
int x=p.first,y=p.second;
for(int i=0;i<4;i++){
if(i==1)continue;
int xx=x+dx[i],yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>m||a[xx][yy]==1||v1[xx][yy])continue;
v1[xx][yy]=1;
q.push({xx,yy});
}
}
v2[1][m]=1;
q.push({1,m});
while(q.size()){
auto p=q.front();
q.pop();
int x=p.first,y=p.second;
for(int i=0;i<4;i++){
if(i==3)continue;
int xx=x+dx[i],yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>m||a[xx][yy]==1||v2[xx][yy])continue;
v2[xx][yy]=1;
q.push({xx,yy});
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// if(v1[i][j]&&v2[i][j]){
// cout<<2;
// }
// else if(v1[i][j]){
// cout<<1;
// }
// else{
// cout<<0;
// }
// }
// cout<<'\n';
// }
for(int i=m;i>=1;i--){
for(int j=1;j<=n;j++){
if(v1[j][i]&&!v2[j][i]){
dep[j][i]=i;
}
else continue;
if((i+1)<=m&&(v1[j][i+1]&&!v2[j][i+1])){
dep[j][i]=max(dep[j][i],dep[j][i+1]);
}
if((j-1)>=1&&(v1[j-1][i]&&!v2[j-1][i])){
dep[j][i]=max(dep[j][i],dep[j-1][i]);
}
}
for(int j=n;j>=1;j--){
if(v1[j][i]&&!v2[j][i]){
if((j+1)<=n&&(v1[j+1][i]&&!v2[j+1][i])){
dep[j][i]=max(dep[j][i],dep[j+1][i]);
}
if(dep[j][i]-i>=k-1){
cout<<"Yes\n";
return;
}
}
}
}
cout<<"No\n";
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T = 1; cin >> T;
for (int ttt = 1; ttt <= T; ++ttt) {
solve();
}
return 0;
}
F
排序 贪心 思维
一个序列每次交换相邻元素,代价固定c。最后得分是前k个元素和-交换产生的总代价。问最大得分?
第一思路就是根据元素值,位置,代价排序,大概就是,然后取前k大之类的。但是排序根据什么标准?这里主要是前k个不好想,如果能统一交换到一个位置
,此时交换次数就是
,排序指标也就是
,就很好做了。但这里我们要求移动到前k个位置。
实际上这个死路是有道理的,沿着这个思路想,如果我们把所有前k大元素移动到开头,接下里其实把他们分散到前k个的代价和,是确定的。所以可以先假设都移动到开头,贪心算代价,然后加上把开头的k个元素移动到前k个位置的代价即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;
void solve() {
int n, k, c;
cin >> n >> k >> c;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
a[i] -= i * c;
}
sort(1 + a.begin(), a.end(), [&](int x, int y) {
return x > y;
});
int ans = 0;
for (int i = 1; i <= k; i++) {
ans += a[i] + i*c;
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T = 1;
for (int ttt = 1; ttt <= T; ++ttt) {
solve();
}
return 0;
}