Znzryb's Blog
0%

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……）

Posted on Edited on

思路讲解

我们先考虑不向左循环移动的情况，那么实际上这个块要么从左边转移过来，要么从上边转移过来。

那么如果加了向左循环移动那？首先dp里存的东西变成了到达此块的总代价即题目中的（kx+y）（y即经过之点的权重之和）

转移的话，从上面转移还是简单，就是要多加一个 K* 向左循环移动次数就行。

如果需要从左边转移，那么要注意，此时只有第一个块需要加一个 K* 向左循环移动次数，后面的块是不需要的，这个要小心一点。

（其实严格来说只有第一行第一个块需要加，因为后面的块都是先从上面转移下来，已经加过一个这个了，不过我也懒得这么严格，因为我的左边界是无穷大除了第一行第一个块旁边是0）

AC代码

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

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
#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 MAXDP=1e15+7;
ll n,T,m,K;
ll maze[210][210];
ll dp[210][210][210],dpUp[210][210];
// dpUp是指无视向左循环移动次数的最优解

// move函数是以该位置为主体的，即移动
inline ll move(ll x, ll step){
    if(x+step<=m){
        return x+step;
    }else{
        return (x+step)%m;
    }
}
inline void init() {
    for(int i=0;i<=n;++i) {
        for(int j=0;j<=m;++j) {
            dpUp[i][j]=MAXDP;
            for(int k=0;k<=m;++k) {
                dp[i][j][k]=MAXDP;
            }
        }
    }
}


inline void solve(){
    std::cin>>n>>m>>K;
    // memset(maze,0,sizeof(maze));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            std::cin>>maze[i][j];
        }
    }
    // memset(dp, 0x3f, sizeof(dp));
    // memset(dpUp, 0x3f, sizeof(dpUp));
    init();
    for(int i=0;i<m;++i) {  // 第1行左边的数我们全部设为0，否则没法推
        dp[1][0][i]=0;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            for(int k=0;k<m;++k){ //k是循环移动次数，K时全局系数
                //    横向k要相等（向左循环移动次数要相等），纵向k不用相等
                if(j==1) {
                    dp[i][j][k]=std::min({dp[i][j][k],dpUp[i-1][j]+maze[i][move(j,k)]+k*K,
                        dp[i][j-1][k]+maze[i][move(j, k)]+K*k});
                }else {
                    dp[i][j][k]=std::min({dp[i][j][k],dpUp[i-1][j]+maze[i][move(j,k)]+k*K,
                        dp[i][j-1][k]+maze[i][move(j, k)]});
                }
            }
            for(int k=0;k<m;++k){
                dpUp[i][j]=std::min(dp[i][j][k],dpUp[i][j]);
            }
        }
    }
    std::cout<<dpUp[n][m]<<std::endl;
}

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/299989686
*/

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

这个转移公式不是每一次都要+kK，如果是从一个已经加过kK的地方转移过来的，那么就不用加了

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
        for(int k=0;k<m;++k){ //k是循环移动次数，K时全局系数
            //    横向k要相等，纵向k不用相等
            dp[i][j][k]=std::min({dp[i][j][k],dpUp[i-1][j]+maze[i][move(j,k)]+k*K,
                dp[i][j-1][k]+maze[i][move(j, k)]+K*k});
        }
        for(int k=0;k<m;++k){
            dpUp[i][j]=std::min(dp[i][j][k],dpUp[i][j]);
        }
    }
}

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

TLE，因为memset()。

1
2
// memset(dp, 0x3f, sizeof(dp));
// memset(dpUp, 0x3f, sizeof(dpUp));

Posted on Edited on

思路讲解

数位dp记忆化搜索做法

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
// dp装的在top位为n的情况下，第i位符合要求的数字数量
ll L,R,digit[25],dp[15][25];
// 为什么要开两维？因为top位不同的情况下，结果没有加和性
//                                isTop是指该位是不是最高位
ll dfs(ll len,ll isMax,ll top,bool isTop){
	if(len==0)
		return 1;
	if(dp[top][len]!=-1 && !isMax)
		return dp[top][len];
	ll maxx,res=0;
	maxx= isMax ? digit[len]:9;
	for(int i=0;i<=maxx && i<top;++i){
		if(isTop){ // 是首数，再考虑0和非0的情况
			if(i==0){
				//                                  top=10 就是指不限制
				res+=dfs(len-1,isMax && i==digit[len],10,true);
				// 不限制的原因是前导为0，没有资格作首数
			}else{
				// 是top数，可以改top
				res+=dfs(len-1, isMax && i==digit[len], i, false);
			}
		}else{
			// 不是top数，没有资格改top
			res+=dfs(len-1, isMax && i==digit[len], top, false);
		}
	}
	if(!isMax)
		dp[top][len]=res;
	return res;
}

以下为思维做法，了解数位dp后觉得有点玄学

我的思路就是先算出1～两个数之间的snake number数量，再将两者相减。

我们以1～90011来解释我们的运算过程

90011可以拆成首位为0～9的情况，其中2～8的计算相对简单，首位已经确定，后面每位有首位种选择，snake number 数量就是 首位^后面的位子数

0的情况就是

1
2
3
4
5
6
7
8
// 假设首位为0情况
if(i==0){
	for(int j=0;j<s.size()-1;++j){
		for(int k=1;k<=9;++k){
			res+=pown[k][j];
		}
	}
}

9的情况就是和2～8一样正常算，然后把不可行的情况数剪掉

1
2
3
4
5
if(i==s[0]-'0'){
	for(int j=0;j<s.size()-1;++j){
		res-=(s[0]-'0'-1-(s[s.size()-j-1]-'0'))*pown[i][j];
	}
}

具体而言如下图

image

AC代码

AC https://atcoder.jp/contests/abc387/submissions/61678607

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

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10;

// dp装的在top位为n的情况下，第i位符合要求的数字数量
ll L,R,digit[25],dp[15][25];
// 为什么要开两维？因为top位不同的情况下，结果没有加和性
//                                isTop是指该位是不是最高位
ll dfs(ll len,ll isMax,ll top,bool isTop){
	if(len==0)
		return 1;
	if(dp[top][len]!=-1 && !isMax)
		return dp[top][len];
	ll maxx,res=0;
	maxx= isMax ? digit[len]:9;
	for(int i=0;i<=maxx && i<top;++i){
		if(isTop){
			if(i==0){
				//                                  top=10 就是指不限制
				res+=dfs(len-1,isMax && i==digit[len],10,true);
				// 不限制的原因是前导为0，没有资格作首数
			}else{
				// 是top数，可以改top
				res+=dfs(len-1, isMax && i==digit[len], i, false);
			}
		}else{
			// 不是top数，没有资格改top
			res+=dfs(len-1, isMax && i==digit[len], top, false);
		}
	}
	if(!isMax)
		dp[top][len]=res;
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>L>>R;
	L-=1;
	ll idx=0;
	while(L){
		digit[++idx]=L%10;
		L/=10;
	}
	memset(dp, -1, sizeof(dp));
	// 刚传进去该位肯定是最高位
	ll lRes=dfs(idx,true,10,true);
	idx=0;
	while(R){
		digit[++idx]=R%10;
		R/=10;
	}
//	memset(dp, -1, sizeof(dp));
	ll rRes=dfs(idx,true,10,true);
	cout<<rRes-lRes<<'\n';
	return 0;
}

AC https://atcoder.jp/contests/abc387/submissions/61423141

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
94
95
96
97
#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>

using namespace std;
typedef unsigned long long ll;
string L,R;
string Ls,Rs;
ll pown[11][21];

void init(){
	Ls.assign(L);
	Rs.assign(R);
	bool isChange=false;
	// 通过这种方法可以得到最靠近原数的snake number
	for(int i=1;i<Rs.size();++i){
		if(Rs[i]<Rs[0] && !isChange){
			continue;
		}
		isChange=true;
		Rs[i]=static_cast<char> (Rs[0]-1);
	}
	isChange=false;
	for(int i=1;i<Ls.size();++i){
		if(Ls[i]<Ls[0] && !isChange){
			continue;
		}
		isChange=true;
		Ls[i]=static_cast<char> (Ls[0]-1);
	}
	// 通过递推得到pow数组，方便后续计算
	for(int i=1;i<=10;++i){
		pown[i][0]=1;
		for(int j=1;j<=19;++j){
			pown[i][j]=i*pown[i][j-1];
		}
	}
}
inline ll getAns(string &s){
	ll res=0;
	for(int i=0;i<=s[0]-'0';++i){
		// 假设首位为0情况
		if(i==0){
			for(int j=0;j<s.size()-1;++j){
				for(int k=1;k<=9;++k){
					res+=pown[k][j];
				}
			}
		}else{
			// 首数为i，后面有i^(size-1)种选择
			res+=pown[i][s.size()-1];
		}
		if(i==s[0]-'0'){
			for(int j=0;j<s.size()-1;++j){
				res-=(s[0]-'0'-1-(s[s.size()-j-1]-'0'))*pown[i][j];
			}
		}
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>L>>R;
	init();
	// 先算出1-R，再算出1-L,两者相减
	ll Rto1=0,Lto1=0;
	Rto1=getAns(Rs);
	Lto1=getAns(Ls);
	if(L==Ls){
		cout<<Rto1-Lto1+1<<endl;
	}else{
		cout<<Rto1-Lto1<<endl;
	}
	return 0;
}
/*
AC https://atcoder.jp/contests/abc387/submissions/61423141
29 55

90011 98888

*/

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