这次div2前三题其实都不难,全是暴力模拟,但是C有个点没考虑 一直wa2 浪费很多时间,D也没时间看,队友48min解决的C也没搞出来D,估计有点难度,有时间补一下。
初始位置在(0,0),有一串操作序列LRUD(代表上下左右移动),问你是否可以删去部分操作后使得移动到(x,y)
用一个桶存 L R U D 分别有几个,然后看数量是否分别大等于 x, y 即可,注意判断负数坐标。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int tong[200];
int main(int argc, char const *argv[]) {
string s;
int t;
cin >>t;
while(t--) {
int x, y;
cin >> x >> y;
cin >> s;
memset(tong, 0, sizeof tong);
for(int i = 0; i < s.size(); i++) tong[s[i]]++;
int flag = -1;
if(x < 0) {
if(tong['L'] >= -x) flag ++;
}
else {
if(tong['R'] >= x) flag ++;
}
if(y < 0) {
if(tong['D'] >= -y) flag ++;
}
else {
if(tong['U'] >= y) flag ++;
}
if(flag == 1) puts("YES");
else puts("NO");
}
return 0;
}
有 k 个石头,从第一座山滚下去,遇到第 i 座山满足高度 h_i<h_{i+1}h_i+1,表示石头停留在第 i 座山上。问你第 k 个石头最后停在哪座山上,如果滑出所有的山则输出-1。
虽然石头数量一个有 1e9,但是每座山最高100,最多100座山,那么其实最多使用的石头数量也就1e4级别(极限情况每座山高度最多都到达了100,则直接输出-1即可),所以直接暴力模拟一遍就可以了。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int h[110];
int main(int argc, char const *argv[]) {
int t;
cin >> t;
while(t--) {
int n, k;
cin >> n >> k;
for(int i = 0; i < n; i++) scanf("%d",&h[i]);
int ans;
while(k--) {
int flag = 0;
for(int i = 0; i < n - 1; i++) {
if(h[i] < h[i+1]) {
h[i] ++;
flag = 1;
ans = i+1;
break;
}
}
if(flag == 0) {
ans = -1;
break;
}
}
cout << ans << '\n';
}
return 0;
}
有n个篱笆,给你a数组表示每个篱笆初始的颜色,b数组表示最终每个篱笆染成什么颜色,有m个粉刷匠,c数组表示每个粉刷匠有那种颜料,每个粉刷匠必须染一次篱笆且只能染一次,且要按照1-m的顺序去染。
用一个vector数组 cha[ ] 记录每个需要染的颜色对应的位置,ans数组存每个粉刷匠刷的篱笆,遍历一遍c数组,如果cha中对应的颜色还有需要染的位置,则将粉刷匠分配过去。有些粉刷匠的颜料是多余的,那么我们可以让他刷在下一次即将要被刷的篱笆上,这样就能将其覆盖掉了。首先看最后一个粉刷匠,由于他最后粉刷,所以他不会被覆盖掉,那么他只能刷在已经存在的颜色上,如果存在则将其分配过去,否则输出NO。接着倒着遍历一遍ans,将所有ans为0的赋值为当前粉刷匠后面即将粉刷的位置即可(具体看代码,不好表述)
比赛的时候一直wa2因为没判断一种情况:所有粉刷匠都分配了篱笆,但是有些篱笆并未符合b的颜色,应该输出NO,但是我的代码实现过程让他输出了YES,然后由于调试改数据大小,最后慌忙又RE了一发,思路和实现一开始就是对的,很可惜!
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int a[maxn], b[maxn], c[maxn], ans[maxn];
vector<int> cha[maxn];
int main(int argc, char const *argv[]) {
int t;
cin >> t;
while(t--) {
int ed = 0, ne = 0;//ed表示已经修改的篱笆数,ne表示需要修改的篱笆数
memset(ans, 0, sizeof ans);
unordered_map<int,int> id;
int n, m;
cin >> n >> m;
for(int i = 0; i <= n; i++) cha[i].clear();
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
for(int i = 1; i <= n; i++) {
scanf("%d",&b[i]);
id[b[i]] = i;
if(a[i] != b[i]) {cha[b[i]].push_back(i);ne++;}// 存入需要修改的颜色对应的下标
}
for(int i = 1; i <= m; i++) scanf("%d",&c[i]);
for(int i = 1; i <= m; i++) {
if(cha[c[i]].size()!=0) {
//如果当前粉刷匠的颜色属于需要修改的颜色则直接分配他去修改
ans[i] = cha[c[i]].back();
cha[c[i]].pop_back();
ed++;
}
}
//最后一个粉刷匠刷完篱笆后不能被覆盖,所以只能修改现有的篱笆
if(ans[m] == 0 && id.find(c[m]) != id.end()) {
ans[m] = id[c[m]];
}
int now = -1;
for(int i = m; i >= 1; i--) {
if(ans[i] != 0) {now = ans[i];continue;}
if(now != -1 && ans[i] == 0) {
//如果当前未被修改,则改成他后面的离他最近的那个已经被修改的篱笆,这样到时候就可以被覆盖掉了
ans[i] = now;
}
}
//如果最后一个被分配了并且全部需要修改的都修改了则输出yes,当时就是没加第二个条件wa2
if(ans[m] != 0 && ne == ed) {
puts("YES");
for (int i = 1; i <= m; i++) {
printf("%d%c",ans[i], i == m ? '\n' : ' ');
}
}
else puts("NO");
}
return 0;
}