Znzryb's Blog
0%

Posted on Edited on

思路讲解

AC代码

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

Posted on Edited on

思路讲解

AC代码

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

Posted on Edited on

思路讲解

赛时AC，记录一下

这个东西说难也不难，就是要抓住不变的东西，其实就是生成的烟雾相对于最初的烟雾其实相对位置是不变的

所以我们把所有烟雾相对于最初烟雾的偏离存在一个set里，接着我们得到目标块与最初烟雾的相对位置，在set里一找，然后就知道有没有烟雾了。

AC代码

https://atcoder.jp/contests/abc398/submissions/64075308

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
98
99
100
101
// Problem: D - Bonfire
// Contest: AtCoder - UNIQUE VISION Programming Contest 2025 Spring (AtCoder Beginner Contest 398)
// URL: https://atcoder.jp/contests/abc398/tasks/abc398_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,R,C,T,A[MAXN];
char S[MAXN];

inline void solve(){
	cin>>N>>R>>C;
	R=-R;
	FOR(i,1,N){
		cin>>S[i];
	}
	ll x=0,y=0;
	set<pll> smoke;
	smoke.insert((pll){0,0});
	FOR(i,1,N){
		// if(R==0 && C==0){
			// cout<<1;
			// continue;
		// }
		if(S[i]=='N'){
			y+=1;
			smoke.insert((pll){0-y,0-x});
			if(smoke.find((pll){R-y,C-x})==smoke.end()){
				cout<<0;
			}else{
				cout<<1;
			}
		}else if(S[i]=='S'){
			y-=1;
			smoke.insert((pll){0-y,0-x});
			if(smoke.find((pll){R-y,C-x})==smoke.end()){
				cout<<0;
			}else{
				cout<<1;
			}
		}else if(S[i]=='E'){
			x+=1;
			smoke.insert((pll){0-y,0-x});
			if(smoke.find((pll){R-y,C-x})==smoke.end()){
				cout<<0;
			}else{
				cout<<1;
			}	
		}else{
			x-=1;
			smoke.insert((pll){0-y,0-x});
			if(smoke.find((pll){R-y,C-x})==smoke.end()){
				cout<<0;
			}else{
				cout<<1;
			}
			
		}
		
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc398/submissions/64075308
*/

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

Posted on Edited on

思路讲解

和这道leetcode很像

https://leetcode.cn/problems/shortest-palindrome/solutions/392676/shou-hua-tu-jie-cong-jian-dan-de-bao-li-fa-xiang-d/

其实思路也很简单，暴力方法时间复杂度最大的部分其实是一个一个判断字符串是不是回文（一样），那么我们直接用字符串哈希加速这个过程就行。

这个下面的讲的很详细

P10469 后缀数组(如何算子串哈希值)

唉，前面怎么样都不太对，结果发现其实是我的哈希递推式子错了。

hash[i]=hash[i−1]∗base+s[i]hash[i]=hash[i-1]*base+s[i]

正确的哈希递推式子长这样，相当于我们把第一位看成最高位，和我们的数字写法一样。

AC代码

https://atcoder.jp/contests/abc398/submissions/64119843

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// Problem: F - ABCBA
// Contest: AtCoder - UNIQUE VISION Programming Contest 2025 Spring (AtCoder Beginner Contest 398)
// URL: https://atcoder.jp/contests/abc398/tasks/abc398_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(5e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll base=131;

ll N,M,T,A[MAXN];
ull hashe[MAXN],hashrs[MAXN];
ull powBase[MAXN];


inline void solve(){
	string s;
	cin>>s;
	string rs(s.rbegin(),s.rend());
	rs='0'+rs;
	N=SZ(s);
	if(N==1){
		cout<<s<<"\n";
		return;
	}
	powBase[0]=1;
	FOR(i,1,N){
		powBase[i]=powBase[i-1]*base;
	}
	s='0'+s;
	FOR(i,1,N){
		hashe[i]=hashe[i-1]*base+s[i];
	}
	FOR(i,1,N){
		hashrs[i]=hashrs[i-1]*base+rs[i];
	}
	FOR(i,N/2+1,N){
		ull len,suf,pre;
		// 以i的前面作为对称中心
		len=N-i+1;
		suf=hashrs[len]-hashrs[0]*powBase[len];
		pre=hashe[i-1]-hashe[i-len-1]*powBase[len];
// #ifdef LOCAL
    // cerr<<len<<" " <<i<<" "<< suf<<" "<<pre << '\n';
// #endif
		if(suf==pre){	
			FOR(i,1,N){
				cout<<s[i];
			}
			FOR(i,len*2+1,N){
				cout<<rs[i];
			}
			cout<<"\n";
			return;
		}
		// 以i作为对称中心
		len=N-i;
		suf=hashrs[len]-hashrs[0]*powBase[len];
		pre=hashe[i-1]-hashe[i-len-1]*powBase[len];
		if(suf==pre){	
			FOR(i,1,N){
				cout<<s[i];
			}
			FOR(i,len*2+2,N){
				cout<<rs[i];
			}
			cout<<"\n";
			return;
		}

	}
	FOR(i,1,N){
		cout<<s[i];
	}
	FOR(i,1,N){
		cout<<rs[i];
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc398/submissions/64119843
*/

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

Posted on Edited on

思路讲解

类似于最短路问题。但这题真的难度只有977吗？这个1400多的树上dp我都有点思路。这个是看完一点思路都没有呀。

不过图论嘛有什么难的那？我很快想到了分层图。这个其实把这张图分为两层就可以了，一层正图，一层反图，正图到反图或者反图到正图都有代价X。

其实dijsktra的关键在于是去找点，就是说目前为止找到的不确定点（dist=INF）中与原点最近的点，改为确定点就（dist=dis）好了。

AC代码

https://atcoder.jp/contests/abc395/submissions/64132524

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
// Problem: E - Flip Edge
// Contest: AtCoder - AtCoder Beginner Contest 395
// URL: https://atcoder.jp/contests/abc395/tasks/abc395_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,X,T,A[MAXN];
vector<ll> g[MAXN];
ll dist[MAXN];

struct cmp{
	bool operator()(const arr &a,const arr &b)const{
		return a[1]>b[1];
	}
};

inline void solve(){
	cin>>N>>M>>X;
	FOR(i,1,2*N){
		dist[i]=INF;
	}
	FOR(i,1,M){
		ll u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v+N].pb(u+N);
	}
	priority_queue<arr,vector<arr>,cmp> pq;
	pq.push({1,0});
	while(!pq.empty()){
		ll node=pq.top()[0],dis=pq.top()[1];
		pq.pop();
		if(dist[node]==INF){
			dist[node]=dis;
			FOR(i,0,SZ(g[node])-1 ){
				ll toNode=g[node][i];
				pq.push({toNode,dis+1});
			}
			if(node>N){
				pq.push({node-N,dis+X});
			}else{
				pq.push({node+N,dis+X});
			}
		}
	}
	cout<<min(dist[N],dist[2*N])<<"\n";
// #ifdef LOCAL
    // FOR(i,1,2*N){
    	// cerr<<dist[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc395/submissions/64132524
*/

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