Znzryb's Blog
0%

Posted on Edited on

思路讲解

参考题解

https://ac.nowcoder.com/discuss/1452143

1
2
3
// 以陪第i只猪猪为结束需要多少消耗
// 注意，这里的第i只猪猪是按照a排序过的顺序的第i个（cmp顺序）
ll dp[MAXN];

直接记忆化会导致TLE，所以我进行了一些小小的优化，具体见图

那一大段被注释掉的就是搜索程序

image

当然，改动之后dp里装的就是以前1～i位为末尾的最优的情况（最少的消耗）。

1
2
3
4
for(int i=1;i<=N;++i){
	if(i!=1) dp[i]=min(dfs(i),dp[i-1]);
	else dp[i]=dfs(i);
}

所以这个程序其实是个伪装成记忆化搜索的递推！

那为什么不直接写递推那？还不是不太直接想的出来。。。

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74795179

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10;
struct abVal{
	ll a;ll b;ll val;
	bool operator<(const abVal &other) const{
		return  a<other.a;
	}
};
vector<abVal> info(MAXN);	// 存储全部题目给出的信息
       // 所有猪猪都不陪伴消耗的总金钱
ll N,M,sumVal;
// 以陪第i只猪猪为结束需要多少消耗
// 注意，这里的第i只猪猪是按照a排序过的顺序的第i个（cmp顺序）
ll dp[MAXN];
bool cmp(abVal a,abVal b){
	return a.a<b.a;
}
ll dfs(int x){
	if(x==0) return sumVal; // 搜索的终点
	if(dp[x]!=-1) return dp[x];	 // 记忆化搜索	
	//                                   我们需要它找到比a-M刚好大一个或者等于的
	ll st=lower_bound(info.begin()+1, info.begin()+x, abVal{info[x].a-M,9999999,9999999})-info.begin()-1;	// start
	if(st==0){	// 没找到
		// 直接用通式计算    陪的代价              不陪的代价
		dp[x]=min(sumVal-info[x].val+info[x].b,sumVal);
		return dp[x];
	}
	//                   陪的代价            不陪的代价
	dp[x]=min(dfs(st)-info[x].val+info[x].b,dfs(st));
//	for(int i=st;i>=1;--i){
//		if(dp[x]==-1){
//			// 第一次我们就直接赋值  陪的代价            不陪的代价
//			dp[x]=min(dfs(i)-info[x].val+info[x].b,dfs(i));
//		}else{ //          陪的代价                        不陪的代价
//			dp[x]=min({dfs(i)-info[x].val+info[x].b,dp[x],dfs(i)});
//		}
//	}
	return dp[x];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i=1;i<=N;++i){
		cin>>info[i].a;
	}
	for(int i=1;i<=N;++i){
		cin>>info[i].b>>info[i].val;
		sumVal+=info[i].val;
	}
	sort(&info[1],&info[N+1],cmp);
	memset(dp, -1, sizeof(dp));
	for(int i=1;i<=N;++i){
		if(i!=1) dp[i]=min(dfs(i),dp[i-1]);
		else dp[i]=dfs(i);
	}
	ll ans=sumVal;
	for(int i=1;i<=N;++i){
		ans=min(ans,dp[i]);
	}
	cout<<ans<<'\n';
	return 0;
}

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

直接记忆化会喜提TLE

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74794988

Posted on Edited on

思路讲解

image

low值相同的点我们可以进行缩点，看成是一个点。

如何求low值及其定义见

为什么可以这样统计缩点的入度，不会有两个low值相同的点与该点相连嘛？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ll tarjan(){
	for(int i=1;i<=N;++i){
		for(int j=0;j<g[i].size();++j){
			ll node=g[i][j];
			if(low[node]!=low[i]){
				degree[low[i]]+=1;  // 以该low值为代表的缩点入度+1
			}
		}
	}
	ll res=0;
	for(int i=1;i<=N;++i){
		if(degree[i]==1){
			++res;
		}
	}
	return ceil(res*1.0/2);
}

显然不可能，有两个low值相同的点与该点相连，那么该点必然与这些点都有共同的low值

image

AC代码

AC

https://www.luogu.com.cn/record/198957305

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=5010;
vector<ll> g[MAXN];

ll N,M;
pll edge[10010];
// 该点的dfs序  子孙可以达到的dfsn值最小的点的dfsn
ll dfsn[MAXN],low[MAXN];
// dfs序编号（时间戳）
ll idx=0;
bool vis[MAXN];
// 计算每个缩点的入度
ll degree[MAXN];
ll dfs(int x,int pa){
	vis[x]=true;
	dfsn[x]=++idx;
	low[x]=dfsn[x];	// 暂设low[x]为自己的dfsn序
	for(int i=0;i<g[x].size();++i){
		if(!vis[g[x][i]]){
			low[x]=min(dfs(g[x][i],x),low[x]);
		}else if(g[x][i] != pa ){
			// 不是父节点且被访问过的要搞一下
			low[x]=min(dfsn[g[x][i]],low[x]);
		}else if(g[x][i+1]==pa){
			low[x]=min(dfsn[g[x][i]],low[x]);
		}
	}
	return low[x];
}
ll tarjan(){
	for(int i=1;i<=N;++i){
		for(int j=0;j<g[i].size();++j){
			ll node=g[i][j];
			if(low[node]!=low[i]){
				degree[low[i]]+=1;
			}
		}
	}
	ll res=0;
	for(int i=1;i<=N;++i){
		if(degree[i]==1){
			++res;
		}
	}
	return ceil(res*1.0/2);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i=1;i<=M;++i){
		cin>>edge[i].first>>edge[i].second;
		if(edge[i].first>edge[i].second)
			swap(edge[i].first, edge[i].second);
	}
	sort(&edge[1], &edge[M+1]);
	for(int i=1;i<=M;++i){
		g[edge[i].first].push_back(edge[i].second);
		g[edge[i].second].push_back(edge[i].first);
	}
	// which are numbered 1..F 一定有点1且图联通
	// They currently have at least one route between each pair of fields and want to have at least two. 
	dfs(1,1);
	cout<<tarjan()<<'\n';
	return 0;
}
/*
WA 63pts https://www.luogu.com.cn/record/198897988
AC https://www.luogu.com.cn/record/198957305
*/

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

题解讲的云里雾里的，有的时候还是得看书，黑书牛逼！

Posted on Edited on

思路讲解

参考题解

https://www.luogu.com.cn/article/j9njcvee

总之就是祖先的low值比祖父的dfs序大的点，说明他不存在其他路径到达祖父节点

1
2
3
4
5
6
7
// 这个条件满足说明i不存在其他路径到达祖父节点
if(low[i]>dfsn[fa[i]]){
	ll a=fa[i],b=i;
	if(a>b)
		swap(a, b);
	ans.push_back({a,b});
}

AC代码

AC

https://www.luogu.com.cn/record/198829769

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=160;
vector<ll> g[MAXN];

ll N,M;
pll edge[5010];
// 该点的dfs序  子孙可以达到的dfsn值最小的点的dfsn
ll dfsn[MAXN],low[MAXN];
// 该点的父节点
ll fa[MAXN];
ll idx=0;
bool vis[MAXN];

ll dfs(int x,int pa){
	fa[x]=pa;
	vis[x]=true;
	dfsn[x]=++idx;
	low[x]=dfsn[x];	// 暂设low[x]为自己的dfsn序
	for(int i=0;i<g[x].size();++i){
		if(!vis[g[x][i]]){
			low[x]=min(dfs(g[x][i],x),low[x]);
		}else if(g[x][i] != pa ){
			// 不是父节点且被访问过的要搞一下
			low[x]=min(dfsn[g[x][i]],low[x]);
		}else if(g[x][i+1]==pa){
			low[x]=min(dfsn[g[x][i]],low[x]);
		}
	}
	return low[x];
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i=1;i<=M;++i){
		cin>>edge[i].first>>edge[i].second;
	}
	sort(&edge[1], &edge[M+1]);
	for(int i=1;i<=M;++i){
		g[edge[i].first].push_back(edge[i].second);
		g[edge[i].second].push_back(edge[i].first);
	}
	dfs(1,1);
	vector<pll> ans;
	for(int i=1;i<=N;++i){
		// 这个条件满足说明i不存在其他路径到达祖父节点
		if(low[i]>dfsn[fa[i]]){
			ll a=fa[i],b=i;
			if(a>b)
				swap(a, b);
			ans.push_back({a,b});
		}
	}
	sort(ans.begin(),ans.end());
	for(int i=0;i<ans.size();++i){
		cout<<ans[i].first<<' '<<ans[i].second<<'\n';
	}
	return 0;
}
/*
AC https://www.luogu.com.cn/record/198829769
3 3 
1 2 
1 2 
2 3

*/

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

Posted on Edited on

思路讲解

子串哈希值的计算见下

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

二分+哈希，其实不用先生成后缀数组，可以直接用哈希+二分算

参考以下题解

https://luogu.com.cn/article/g6xhm285

AC代码

AC

https://www.luogu.com.cn/record/198696498

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#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=2010,base=131;

ll N,hashe[15][MAXN],len[15],powBase[MAXN];

inline bool check(ll x){
	// x是指公共子串长度
	if(x==0)
		return true;
	// 计算子串哈希值
	map<ll,ll> hashCnt;
	for(int i=1;i<=N;++i){
		unordered_set<ll> isAdd;
		for(int j=0;j<=len[i]-x;++j){
			ll subStringHash=hashe[i][j+x-1]-(j>0?hashe[i][j-1]*powBase[x]:0);
			// 没找到直接赋值
			if(hashCnt.find(subStringHash)==hashCnt.end()){
				hashCnt[subStringHash]=1;
				isAdd.insert(subStringHash);
			}else if(isAdd.find(subStringHash)==isAdd.end()){
				hashCnt[subStringHash]+=1;
				isAdd.insert(subStringHash);
			}
		}
	}
	for(map<ll,ll>::iterator it=hashCnt.begin();it!=hashCnt.end();it++){
		ll val=it->second;
		if(val>=N)
			return true;
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	powBase[0]=1;
	for(int i=1;i<=MAXN;++i){
		powBase[i]=powBase[i-1]*base;
	}
	ll r=999999;
	for(int i=1;i<=N;++i){
		string s;
		cin>>s;
		len[i]=s.size();
		r=min(len[i],r);
		hashe[i][0]=0;
		for(int j=0;j<len[i];++j){
			hashe[i][j]=hashe[i][(j>0?j-1:0)]*base+s[j];
		}
	}
	ll l=0;
	while (l<r) {
		ll mid=l+r+1>>1;
		if(check(mid)){
			l=mid;
		}else{
			r=mid-1;
		}
	}
	cout<<l<<'\n';
	return 0;
}
/*
82 https://www.luogu.com.cn/record/198689007
AC https://www.luogu.com.cn/record/198696498
2
ab
ca

*/

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

WA

https://www.luogu.com.cn/record/198689007

在查哪里出问题了

搞半天原来是这里忘记insert进isAdd了。

image