什么时候能不der?
A. Space Navigation
题意
在二维坐标里面，你要移动到指定的点处，UDLR分别表上向上、下、左、右，你可以去除任意字符，问能否到达这个点。
题解
签到题，分别统计各个字母的个数，因为可以去除任意字符，如果x>0，我们就只需要右移动，即当 x>R的个数 的时候，x轴方向可以到达，其他方向同理。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
ll x,y;
cin>>x>>y;
string s;
cin>>s;
ll a=0,b=0,c=0,d=0;
for(ll i=0;i<s.size();i++){
if(s[i]=='U')a++;
if(s[i]=='D')b++;
if(s[i]=='L')c++;
if(s[i]=='R')d++;
}
//cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
int f=0;
if(x>0&&d<x)f=1;
else if(x<0&&c<abs(x))f=1;
if(y>0&&a<y) f=1;
else if(y<0&&b<abs(y))f=1;
if(f==1) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
B. New Colony
题意
你有n座山和k个石头，如果 第i座山的高度>第i+1座山的高度 ，石头可以直接滚过去，否则第i座山的高度+1，问第k个石头留在哪座山上，如果滚出去了，输入-1。
题解
这题一开始想复杂了，就模拟就行，但是别太直接。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
ll n,k,mi=lmax,mi2=lmax;
cin>>n>>k;
ll moun[n];
ll last=0,re=-1;
for(int i=0;i<n;i++){
cin>>moun[i];
mi=min(mi,moun[i]);
if(i!=0&&re==-1){
while(moun[i]>moun[i-1]){
mi2=lmax;
for(int j=i-1;j>=0;j--){
if(moun[j]==mi) {
moun[j]++;
k--;
if(k==0) re=j+1;
}
mi2=min(mi2,moun[j]);
}
mi=mi2;
}
}
}
cout<<re<<endl;
}
return 0;
}
C. Fence Painting
题意
你要给栅栏涂色，每个画家按顺序到达，你可以指派他去涂哪个栅栏但是你不能不让他去涂，最终能否把栅栏涂成希望的颜色？
题解
这题一直在der，因为一个小错误WA了好几发。
首先统计出已经有的颜色和需要的颜色，然后倒序遍历画家，如果最后一个画家的颜色不是已经有的颜色或需要的颜色之一，直接no。如果其他的画家出现了没关系，因为会被最后一个画家覆盖掉。
之后就是涂需要的颜色了，到最后如果所有需要涂的颜色都涂了，就是yes，否则no。
坑点：统计需要的颜色的时候要把该颜色从已有颜色中删掉，如果不删掉，可能出现最后一个颜色覆盖已经被涂过的颜色上面。
例如：
3 2
1 2 3
1 2 4
4 3
这个明显no，因为第1个画家必须涂在3上，第二个无处可涂。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
int n,m;
cin>>n>>m;
int num[n];
int want[n];
map<int,set<int> > needcolor;
map<int,set<int> > color;
for(int i=0;i<n;i++) {
cin>>num[i];
color[num[i]].insert(i);
}
for(int i=0;i<n;i++) {
cin>>want[i];
if(want[i]!=num[i]) {
needcolor[want[i]].insert(i);
color[num[i]].erase(i);
if(color[num[i]].size()==0) color.erase(num[i]);
}
}
int painter[m];
int re[m];
int bak,f=0;
for(int i=0;i<m;i++) cin>>painter[i];
if(needcolor.size()==0){
if(color.count(painter[m-1])==0) f=1;
else{
for(int i=0;i<m;i++) re[i]=*color[painter[m-1]].begin() ;
}
}
else{
for(int i=m-1;i>=0;i--){
//cout<<1<<endl;
if(needcolor.count(painter[i])!=0){
re[i]=*needcolor[painter[i]].begin() ;
bak=re[i];
needcolor[painter[i]].erase(re[i]);
if(needcolor[painter[i]].size()==0) needcolor.erase(painter[i]);
}
else if(i==m-1&&color.count(painter[i])!=0){
re[i]=*color[painter[i]].begin();
bak=re[i];
}
else if(i!=m-1){
re[i]=bak;
}
else {
f=1;
break;
}
}
}
if(f==1||needcolor.size()!=0){
cout<<"NO"<<endl;
}
else{
cout<<"YES"<<endl;
for(int i=0;i<m;i++) cout<<re[i]+1<<" ";
cout<<endl;
}
}
return 0;
}
