Znzryb's Blog
0%

Posted on Edited on

思路讲解

这题难点主要就是不要怕，看起来好像很难，但其实就只有16种状态，我还没加快读只跑了171ms。

看了一下大佬的思路，主要就是状态分解，还是分层图的思想。

image

1
2
3
//       y  x  dir dirs
bool vis[N][M][5][5];  
memset(vis, false, sizeof(vis));

所以我们建一个分层状态vis数组，dir指的是方向，dirs指的是在此方向走过的次数

只要vis[][][][]==true我们就continue；

在这个分层图上跑一个bfs

然后注意一下不要撞墙，不要出界，不要dirs>3

AC代码

注意，该写法仅能在C11及以上环境中编译（C98好像没有array）

https://codeforces.com/contest/2041/submission/293790427

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#include <cstring>

using namespace std;
typedef long long ll;
constexpr int dx[]={0,1,0,-1};
constexpr int dy[]={1,0,-1,0};
ll n,m;

// 这题会不会是分层图问题？
// 分不同的层去解决这个问题？
// 先写个bfs
inline bool check(ll x,ll y,vector<vector<char> > &maze){	
// 检查是否出界以及撞墙
	if(y<1 || y>n)
		return false;
	if(x<1 || x>m)
		return false;
	if(maze[y][x]=='#')
		return false;
	return true;
}

int main() {
	cin>>n>>m;
	vector<vector<char> > maze(n+5,vector<char>(m+5)); 
	ll sy=0,sx=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>maze[i][j];
			if(maze[i][j]=='S')
				sy=i,sx=j;
		}
	}
	queue<array<ll, 5>> q;
	//       x,y,step,dir,dirs;
	q.push({sx,sy,0LL,0LL,0LL});
	const ll N=5+static_cast<ll> (n),M=static_cast<ll> (m)+5;
	bool vis[N][M][5][5];  
	memset(vis, false, sizeof(vis));
	ll ans=1e17;
	while (!q.empty()) {
		ll x=q.front()[0];
		ll y=q.front()[1];
		ll step=q.front()[2];
		ll dir=q.front()[3];
		ll dirs=q.front()[4];
		q.pop();
		if(vis[y][x][dir][dirs]){
			continue;
		}
		if(maze[y][x]=='T'){
			ans=min(ans,step);
			continue;
		}
		vis[y][x][dir][dirs]=true;
		for(int i=0;i<4;++i){
			if(i==dir && dirs<3 && check(x+dx[i],y+dy[i],maze))
				q.push({x+dx[i],y+dy[i],step+1,i,dirs+1});
			else if(i!=dir && check(x+dx[i],y+dy[i],maze))
				q.push({x+dx[i],y+dy[i],step+1,i,1LL});
		}
	}
	if(ans!=1e17)
		cout<<ans<<endl;
	else
		cout<<-1<<endl;
}
// AC https://codeforces.com/contest/2041/submission/293790427

心路历程（WA，TLE，MLE……）

前面少include 一个cstring库，唉，都是clang不支持<bits/stdc.h>导致的

Posted on Edited on

思路讲解

一个小的脑筋急转弯

构造数组为 b b 3a-2b

无论3a-2b 的值是多少，b都是中位数

AC代码

https://codeforces.com/contest/2041/submission/293763683

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>

using namespace std;
typedef long long ll;
ll a,b;

int main() {
	cin>>a>>b;
//	its mean is exactly a
//	and its median is exactly b
//  怎么做才能达到这样的效果那？
	cout<<3<<"\n";
	cout<<b<<" "<<b<<" "<<3*a-(2*b)<<endl;
}
// AC https://codeforces.com/contest/2041/submission/293763683

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

我反正贪心过的，n比较小，所以全部是循环。

先尝试性价比比较高的，再尝试性价比比较低的

AC代码

https://codeforces.com/contest/2038/submission/293535960

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
49
50
51
52
53
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;


void solve(ll n){
	ll a=n,b=n,c=n;
	ll cnt=0;
	while (a>=1 && b>=2){
		a-=1;
		b-=2;
		++cnt;
	}
	while (a>=3) {
		a-=3;
		++cnt;
	}
	while (a>=1 && c>=1){
		a-=1,c-=1;
		++cnt;
	}
	while (b>=1 && c>=1) {
		b-=1;
		c-=1;
		++cnt;
	}
	while (c>=1) {
		c-=2;
		++cnt;
	}
	while (b>=1) {
		b-=2;
		++cnt;
	}
	while (a>=1) {
		a-=2;
		++cnt;
	}
	cout<<cnt<<endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	ll n;
	cin>>n;
	solve(n);
	return 0;
}

// AC https://codeforces.com/contest/2038/submission/293535960

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

用了一个map来存一下每个数出现的次数，然后只有出现两次的数才可参与矩形的构建。

然后C++的map是有序的，所以遍历也是有序的

AC代码

https://codeforces.com/contest/2038/submission/293462817

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
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;
typedef long long ll;
ll T;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		ll n;
		cin>>n;
		vector<ll> A(n+10);
		map<ll,ll> occur;
		for(int i=1;i<=n;++i){
			cin>>A[i];
			if(occur.count(A[i]))
				occur[A[i]]+=1;
			else
				occur[A[i]]=1;
		}
		vector<ll> validNum;	// 因为遍历是有序的，所以validNum也是有序的
		for(map<ll,ll>::iterator it=occur.begin();it!=occur.end();it++){
			ll num=it->first,cnt=it->second;
			while (cnt>=2){
				validNum.push_back(num);
				cnt-=2;
			}
		}
		if(validNum.size()<4){
			cout<<"NO"<<endl;
		}else {
			cout<<"YES"<<endl;
			ll a=validNum[0],b=validNum[1],c=validNum[validNum.size()-1],d=validNum[validNum.size()-2];
			cout<<a<<" "<<b<<" "<<a<<" "<<c<<" "<<d<<" "<<b<<" "<<d<<" "<<c<<endl;
		}
	}
}
// AC https://codeforces.com/contest/2038/submission/293462817

心路历程（WA，TLE，MLE……）

输出顺序要好好想想

1
cout<<a<<" "<<b<<" "<<a<<" "<<c<<" "<<d<<" "<<b<<" "<<d<<" "<<c<<endl;

Posted on Edited on

思路讲解

你最少可以干多少活=总共要干多少活-之前的人干了多少活-后面的人最多干多少活

AC代码

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
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
ll n,k;
const ll N=1010;
ll A[N],B[N],C[N];
ll upDo[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i)
        cin>>A[i];
    for(int i=1;i<=n;++i)
        cin>>B[i];
//  ll maxDo=0;
//  for(int i=1;i<=n;++i){
//      maxDo+=A[i]/B[i];
//  }
    for(int i=n;i>=1;--i){
        upDo[i]=upDo[i+1]+A[i]/B[i];
    }
    if(upDo[1]<k){
        for(int i=1;i<=n;++i)
            cout<<0<<" ";
        cout<<endl;
        return 0;
    }
    ll sumUpDo=0;	// 之前的人总共做了多少
    for(int i=1;i<=n;++i){
        
     // 你最少可以干多少活=总共要干多少活-之前的人干了多少活-后面的人最多干多少活
        C[i]=min(A[i]/B[i],max(k-upDo[i+1]-sumUpDo,0LL));
        sumUpDo+=C[i];
    }
    for(int i=1;i<=n;++i)
        cout<<C[i]<<" ";
    cout<<endl;

    return 0;
}
// WA on test 9 https://codeforces.com/contest/2038/submission/293384404
// 应该比较接近了
// AC 加了个max（0LL，。。。）https://codeforces.com/contest/2038/submission/293422369

心路历程（WA，TLE，MLE……）