Znzryb's Blog
0%

Posted on Edited on

思路讲解

?即是有多少个数不参与这个移动

image

当然这个公式只有在特定条件下才能用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if(K==0){
	if(First>=N){
		 std::cout<< N<<"\n";
	}else if(First>=N-2){
		// 不用移动N次，因为N有一个数可以作为不动数
		 std::cout<< N-1<<"\n";
	}else{
		std::cout<<-1<<"\n";
	}
}else{
	if(First>=N){
		std::cout<< N<<"\n";
	}else{
		// res即是上图的？
		ll res=(N-First-1)/K+1;
		std::cout<< N-res<<"\n";
	}
}

AC代码

https://codeforces.com/contest/2028/submission/300282002

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

typedef long long ll;
typedef std::pair<ll,ll> pll;
const ll MAXN=static_cast<ll>(2e5)+10;
ll N,T,K,First;

void solve(){
	// 项数，公差以及首项
	std::cin>>N>>K>>First;
	if(K==0){
		if(First>=N){
			 std::cout<< N<<"\n";
		}else if(First>=N-2){
			// 不用移动N次，因为N有一个数可以作为不动数
			 std::cout<< N-1<<"\n";
		}else{
			std::cout<<-1<<"\n";
		}
	}else{
		if(First>=N){
			std::cout<< N<<"\n";
		}else{
			ll res=(N-First-1)/K+1;
			std::cout<< N-res<<"\n";
		}
	}
	return;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);std::cout.tie(0);
	std::cin>>T;
	while (T--) {
		solve();
	}
	return 0;
}
/*
AC https://codeforces.com/contest/2028/submission/300282002
1
10 10 10

9

1
1 0 0

1
1 1 2

*/

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

Posted on Edited on

思路讲解

我看题解说，注意到，每个块最多被move back一次，那为什么最多被移动一次那？

我个人的理解是因为我们是可以随意选择move back的顺序，所以我们可以让我们的move back自动搞为一个单调的。

其实这个题解主要还是坚定了我的信心，让我知道我做法的时间复杂度是没问题的，我前面想复杂了。

总体上的思路是用数据结构优化模拟法，当然发现加粗（每个块最多被move back一次）是非常重要的，否则很容易想复杂。

核心是这段程序

1
2
3
4
5
6
7
8
9
10
11
12
13
while (!pq.empty()) {
	pll temp=pq.top();
	pq.pop();
	if(temp.second>needBack){
		// 我们发现这个不要后移，那就不后移
		Ans[++idx]=temp.first;
		needBack=temp.second;
	}else{
		// 如果我们发现这个要后移，那我们就模拟后移
		pq.push({temp.first+1,N+back});
		back+=1;
	}
}

AC代码

https://codeforces.com/contest/2047/submission/300222017

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
73
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

typedef long long ll;
typedef std::pair<ll,ll> pll;
const ll MAXN=static_cast<ll>(1e5)+10;
ll N,T,A[MAXN],Ans[MAXN];
struct cmp{
	bool operator()(pll a,pll b){
		if(a.first!=b.first){
			return a.first>b.first;
		}
		if(a.second!=b.second){
			return a.second>b.second;
		}
		return false;
	}
};

void solve(){
	std::cin>>N;
	// 里面装的东西，容器，以及比较规则
	std::priority_queue<pll,std::vector<pll>,cmp > pq;
	// needBack指的是这之前的数都要往后移
	ll needBack=0;
	for(int i=1;i<=N;++i){
		std::cin>>A[i];
		pq.push({A[i],i});
	}
	// back是指被移到后面的哪个位置（即移到原来的N+back）
	ll idx=0,back=1;
	// 每一个位置最多被移动一次，所以复杂度不会太高。
	while (!pq.empty()) {
		pll temp=pq.top();
		pq.pop();
		if(temp.second>needBack){
			Ans[++idx]=temp.first;
			needBack=temp.second;
		}else{
			pq.push({temp.first+1,N+back});
			back+=1;
		}
	}
	for(int i=1;i<=N;++i){
		std::cout<<Ans[i]<<" ";
	}
	std::cout<<"\n";
	return;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);std::cout.tie(0);
	std::cin>>T;
	while (T--) {
		solve();
	}
	return 0;
}

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

Posted on Edited on

思路讲解

1
2
3
4
5
6
7
// 在这两个位置的s和p等价于点
if(S[1]=='s'){
	S[1]='.';
}
if(S[N]=='p'){
	S[N]='.';
}

然后就是不能有p出现在s之后，不能有s出现在p之后，非常简单吧

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

typedef long long ll;
const ll MAXN=510;
ll N,T;
char S[MAXN];

void solve(){
	std::cin>>N;
	for(int i=1;i<=N;++i){
		std::cin>>S[i];
	}
	// 在这两个位置的s和p等价于点
	if(S[1]=='s'){
		S[1]='.';
	}
	if(S[N]=='p'){
		S[N]='.';
	}
	// 检查有没有类似于ps,sp的结构
	for(int i=1;i<=N-1;++i){
		if(S[i]=='p'){
			for(int j=i+1;j<=N;++j){
				if(S[j]=='s'){
					std::cout<<"NO\n";
					return;
				}
			}
		}
		if(S[i]=='s'){
			for(int j=i+1;j<=N;++j){
				if(S[j]=='p'){
					std::cout<<"NO\n";
					return;
				}
			}
		}
	}
	std::cout<<"YES\n";
	return;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);std::cout.tie(0);
	std::cin>>T;
	while (T--) {
		solve();
	}
	return 0;
}
/*
AC https://codeforces.com/contest/2049/submission/300115610
*/

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

Posted on Edited on

思路讲解

我想到一个背景故事，就是说每条龙都想有和自己的朋友不同的涂装，但是编号越大的涂装越贵，龙龙们想用编号比较小的涂装达成这一目的，但是龙龙们不知道怎样组合才好，于是找到了你。

AC代码

多用构造之方法，少用特判之方法，毕竟是构造题嘛。

https://codeforces.com/contest/2049/submission/300064440

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

typedef long long ll;
const ll MAXN=static_cast<ll>(2e5)+10;
ll N,X,Y,T;
ll A[MAXN];

inline bool isOriginalFriend(ll x,ll y){
	x-=1;
	y-=1;
	if((x+1)%N==y){
		return true;
	}else if((x-1)%N==y){
		return true;
	}
	return false;
}

void solve(){
	std::cin>>N>>X>>Y;
	if(N%2==0){
		for(int i=1;i<=N;++i){
			A[i]=i%2;
		}
	}else{
		A[1]=2;
		for(int i=2;i<=N;++i){
			A[i]=(i+1)%2;
		}
	}
	// 无影响，我们使用普通的方法
	if(A[X]==A[Y]){
		// 有影响，我们要调整
		if(N%2==0){
			A[X]=2;
		}else{
			A[X]=2;
			for(int i=X+1;i<=X+N-1;++i){
				if(i<=N){
					A[i]=(i+X%2)%2;
				}else{
					A[i%N]=(i+X%2)%2;
				}
			}
		}
	}
	for(int i=1;i<=N;++i){
		std::cout<<A[i]<<" ";
	}
	std::cout<<std::endl;
	return;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);std::cout.tie(0);
	std::cin>>T;
	while (T--) {
		solve();
	}
	return 0;
}
/*
AC https://codeforces.com/contest/2049/submission/300064440
WA https://codeforces.com/contest/2049/submission/300052744
1
5 3 5

2 1 2 1 0 (A[2]=1,但应该是0)

WA https://codeforces.com/contest/2049/submission/300055526
1
5 2 4

1
7 3 7

*/

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

WA https://codeforces.com/contest/2049/submission/300052744
1
5 3 5
2 1 2 1 0 (A[2]=1,但应该是0)

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
// https://www.luogu.com.cn/problem/P3842
// dp
using namespace std;
const int maxn=2e4+10;
int n,dp[maxn],dp2[maxn];     // 这个dp表里存的应该是 从该点出 且 把该行线段走完的最短距离
struct startEnd {
    int s;
    int e;
}se[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>se[i].s>>se[i].e;
    }
    // dp initialize
    for(int i=1;i<=n;i++) {
        if(i==se[1].s)
            dp[se[1].s]=se[1].e-1+se[1].e-se[1].s;
        else if(i==se[1].e)
            dp[se[1].e]=se[1].e-1;
        else
            dp[i]=maxn;
    }
    for(int i=1;i<=n;i++) {
        dp2[i]=dp[i];
    }
    for(int r=2;r<=n;r++) {
        int currS=se[r].s,currE=se[r].e,sUp=se[r-1].s,eUp=se[r-1].e;
        if(eUp>=currE) {
            dp[currS]=dp2[eUp]+eUp-currS;
        }else {
            dp[currS]=dp2[eUp]+currE-currS+currE-eUp;
        }

        if(sUp<=currS) {
            dp[currE]=dp2[sUp]+currE-sUp;
        }else {
            dp[currE]=dp2[sUp]+sUp-currS+currE-currS;
        }

        if(sUp>=currE) {
            dp[currS]=min(dp[currS],dp2[sUp]+sUp-currS);
        }else {
            dp[currS]=min(dp[currS],dp2[sUp]+currE-currS+currE-sUp);
        }

        if(eUp<=currS) {
            dp[currE]=min(dp[currE],dp2[eUp]+currE-eUp);
        }else {
            dp[currE]=min(dp[currE],dp2[eUp]+eUp-currS+currE-currS);
        }
        // dp2缓存
        dp2[currS]=dp[currS],dp2[currE]=dp[currE];
    }
    dp[n]=min(dp[se[n].e]+n-se[n].e,dp[se[n].s]+n-se[n].s);
    // 没计算向下走的步数
    cout<<dp[n]+n-1<<endl;
    return 0;
}

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