CodeForce刷题表

Day5

1607D - Blue-Red Permutation

题意:

给定n个数，每个数可能是蓝色也可能是红色，如果是蓝色，那他可以进行-1操作，如果是红色，那他可以进行+1操作。

问能不能让数组1~n每个数都出现一次。

思路：

排序，遍历两遍。

第一遍正向，遇到蓝色就放在最左边，计数器+1，如果这个数小于计数器那么这个数组就不能做到每个数出现一遍。

第二遍逆向，遇到红色就放在最右边，计数器-1，如果这个数大于计数器那么这个数组就不能做到每个数出现一遍。

假设比那里蓝色，如果这个数是2，前面已经有两个数了(计数器为3)，由于蓝色只能减不能加，所以这个数就不能起到作用，一共n个数如果少了一个数，那么就不可能同时存在 1~n了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const ll mod = 1e9+7; 
struct node {
	int num;
	char color;
}a[N];
bool cmp(node x,node y) {
	return x.num < y.num;
}
int main(){
	int _;cin>>_;
	while(_--) {
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>a[i].num;
		for(int i=1;i<=n;i++)
			cin>>a[i].color;
		sort(a+1,a+1+n,cmp); //排序
		int cnt = 1;
		bool k = false;
		for(int i=1;i<=n;i++)//正序遍历蓝色
			if(a[i].color=='B') {
				if(a[i].num >= cnt)
					cnt++;
				else
					k = true;
			}
		cnt = n;
		for(int i=n;i>=1;i--)//逆序遍历红色
			if(a[i].color=='R') {
				if(a[i].num <= cnt)
					cnt--;
				else
					k = true;
			}
			
		if(k)
			cout<<"NO";
		else
			cout<<"YES";
		cout<<endl;
	}
	return 0;
}

总结：

倒序思考一点问题都没有。

1607E - Robot on the Board 1

题意：

给定一个n*m的盘，机器人会根据命令运行，问起点在哪里的时候，可以做的指令最多。

思路：

从头遍历，记录最左端，最右端，最上端，最下端，如果右-左 超过了m或者下-上 超过了 n就退出。

1-w , 1-a就是所需要的

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const ll mod = 1e9+7; 
int main(){
	int _;cin>>_;
	while(_--) {
		int n,m;
		string ss;
		cin>>n>>m;
		int w,a,s,d,x,y;
		w = a = s = d = x = y = 0;
		cin>>ss;
		int len = ss.size();
		for(int i=0;i<len;i++) {
			if(ss[i]=='U')x--;
			if(ss[i]=='D')x++;
			if(ss[i]=='L')y--;
			if(ss[i]=='R')y++;
			if(abs(min(w,x)-max(s,x)) >= n || abs(min(a,y)-max(d,y)) >= m )
				break;
			w=min(w,x);a=min(a,y);
			s=max(s,x);d=max(d,y);
		}
		cout<<1-w<<" "<<1-a<<endl;
	}
	return 0;
}

总结：

模拟一下想一下应该是不难解决。

其实还有另外一种做法

代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        string s;
        cin>>s;
        int x=1,y=1;
        for(int i=s.size()-1;i>=0;i--){ //反向查找起始位置
            if(s[i]=='L'&&x<m)x++;
            if(s[i]=='R'&&x>1)x--;
            if(s[i]=='U'&&y<n)y++;
            if(s[i]=='D'&&y>1)y--;
        }
        cout<<y<<" "<<x<<endl;
    }
}

单独看左右，倒着找到起始位置，从起始位置可以走最远的路！

上下同样如此。

所以这样的题可以分治成左右和上下两部分来完成，左右能走最远的位置就是y坐标，上下能走最远的位置就是x坐标。