Znzryb's Blog
0%

Posted on Edited on

思路讲解

思路其实就是组合数生成惯用套路+深度控制

组合数生成其实就是从start开始，这样可以保证加入顺序都是从编号小的到编号大的，进而达到无视元素加入顺序的效果。

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int dep,int start,ull sum){
	if(dep>T){
		ans=max(ans,sum^xorSum);
		return;
	}
	FOR(i, start, N){
		if(vis[i]) continue;
		vis[i]=true;
		dfs(dep+1,i+1,sum^A[i]);
		vis[i]=false;
	}
}

当然，利用异或计算的性质，我们可以控制深度，枚举不选的，而不是枚举选的，以减少计算次数

1
2
3
4
5
if(T>N-T){
		T=N-T;
	}else{	// 正向进行不需要异或
		xorSum=0;
	}

AC代码

AC

https://atcoder.jp/contests/abc386/submissions/62216769

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
#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 SZ(x) ((int)x.size())
#define all(x,size) x.begin()+1,x.begin()+size+1
#define all1(x) x.begin(),x.end()

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;
const ll MAXN=static_cast<ll>(1e6)+10,MAXval=static_cast<ll>(1e18)+3;

ll N,T;
ull A[MAXN];
bool vis[MAXN];
ull ans,xorSum;

void dfs(int dep,int start,ull sum){
	if(dep>T){
		ans=max(ans,sum^xorSum);
		return;
	}
	FOR(i, start, N){
		if(vis[i]) continue;
		vis[i]=true;
		dfs(dep+1,i+1,sum^A[i]);
		vis[i]=false;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>T;
	FOR(i, 1, N){
		cin>>A[i];
		xorSum^=A[i];
	}
	if(T>N-T){
		T=N-T;
	}else{	// 正向进行不需要异或
		xorSum=0;
	}
	dfs(1,1,0);
	cout<<ans<<endl;
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc386/submissions/62216769
*/

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

Posted on Edited on

思路讲解

如果红色块被涂黑了，所有被红线围住的块全部也要涂黑，所以说中间不能有一个白色的块

image

形式化的来说，B（x，y），那么不能有白块 ≤ x && ≤ y。

AC代码

AC

https://atcoder.jp/contests/abc386/submissions/62215130

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

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 <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 SZ(x) ((int)x.size())
#define all(x,size) x.begin()+1,x.begin()+size+1
#define all1(x) x.begin(),x.end()

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;
const ll MAXN=static_cast<ll>(2e5)+10,MAXval=static_cast<ll>(1e18)+3;

int N,T;
//ll coly[MAXN];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>T;
	vector<pll> wNode;
	// 我们要记录的是黑色最远出现位置和白色最近出现位置
	map<ll,ll> bHigh;
	FOR(i, 1, T){
		ll x,y;char c;
		cin>>x>>y>>c;
		if(c=='B'){
			bHigh[x]=bHigh.find(x)==bHigh.end()?y:max(y,bHigh[x]);
		}else{
			wNode.push_back({x,y});
		}
	}
	if(bHigh.empty()){	// 没有黑色块自然没那么多烦人事了
		cout<<"Yes\n";
		return 0;
	}
	ll maxHigh=0;
	for(map<ll,ll>::reverse_iterator it=bHigh.rbegin();it!=bHigh.rend();++it){
		it->second=max(it->second,maxHigh);
		maxHigh=it->second;
	}
	FOR(i, 0, SZ(wNode)-1){
		ll x=wNode[i].first,y=wNode[i].second;
		map<ll,ll>::iterator it=bHigh.lower_bound(x);
		if(it!=bHigh.end()){ // 确保lower_bound会搜到正确的东西
			ll yB=it->second;
			if(yB>=y){
				cout<<"No\n";
				return 0;
			}
		}
	}
	cout<<"Yes\n";
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc386/submissions/62215130
*/

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

如果出现样例结果评测机与本地结果不一致，大概率是空的情况处理有问题

还是要多防御性编程，不要相信lower_bound一定正确，避免其返回end（）的情况

Posted on Edited on

思路讲解

https://www.luogu.com.cn/article/5c0a5s3i

image

由上可知，只有让每行每列的和都为0才在所有情况下都有解。

所以说这种东西首先要确定在什么情况下是一定有解的，不能上来就做

AC代码

https://codeforces.com/contest/2055/submission/303531727

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#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>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)

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=1010;
// 假设我们要凑的数独是0吧

ll N,M,T,maze[MAXN][MAXN];
ll rowMaze[MAXN],colMaze[MAXN];

void solve(){
	cin>>N>>M;
	string s;
	cin>>s;
	FOR(i, 1, N){
		rowMaze[i]=0;
		FOR(j, 1, M){
			cin>>maze[i][j];
			rowMaze[i]+=maze[i][j];
		}
	}
	// 
	FOR(i, 1, M){
		colMaze[i]=0;
		FOR(j, 1, N){
			colMaze[i]+=maze[j][i];
		}
	}
	int px=1,py=1;
	if(s.back()=='D'){
		maze[N][M]=-rowMaze[N];
		colMaze[M]+=maze[N][M];
	}else{
		maze[N][M]=-colMaze[M];
		rowMaze[N]+=maze[N][M];
	}
	FOR(i, 0, s.size()-1){
		// 这样子的处理唯一就是要担心最后一个块，因为最后一个块行和列都后继无人了
		if(s[i]=='D'){
			// 如果他往下走，那么他这行就后继无人了
			ll h=-rowMaze[px];
			rowMaze[px]=0;
			colMaze[py]+=h;
			maze[px][py]=h;
		}else{
			// 如果他往右走，那么他这列就后继无人了
			ll h=-colMaze[py];
			colMaze[py]=0;
			rowMaze[px]+=h;
			maze[px][py]=h;
		}
		if(s[i]=='D'){
			px+=1;
		}else{
			py+=1;
		}
	}
	
	FOR(i, 1, N){
		FOR(j, 1, M){
			cout<<maze[i][j]<<' ';
		}
		cout<<'\n';
	}
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		solve();
	}
	return 0;
}
/*
1
2 3
RRD
0 0 0
0 1 0

4
3 3
DRRD
0 2 3
0 0 0
3 1 0
4 5
DRRRRDD
0 1 0 2 3
0 0 0 0 0
-1 0 -3 -3 0
0 0 0 -1 0
2 3
RRD
0 0 0
0 1 0
5 5
DDDDRRRR
0 25 2 9 11
0 6 13 20 22
0 17 24 1 8
0 3 10 12 19
0 0 0 0 0

*/

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

Posted on Edited on

思路讲解

我的总体思路就是把问题拆成3个背包，而且因为不同食物不会含有多种vitamin，所以背包之间不会有干扰。

然后枚举前两个背包的大小（第三个背包就是总背包-1-2），得出最优组合，输出答案即可

AC代码

AC

https://atcoder.jp/contests/abc390/submissions/62196209

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
#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)

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,MAXval=static_cast<ll> (1e18)+3;

ll N,T,C;
struct Food{
	ll unit,ene;
};
vector<Food> food[5];
// 该容量（卡路里）下，该卡路里摄入量最多是多少？
ll dp[5][MAXN];
ll Len[5];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>C;
	FOR(i, 1, N){
		ll kind,unit,ene;
		cin>>kind>>unit>>ene;
		food[kind].push_back((Food){unit,ene});
	}
	Len[1]=food[1].size();Len[2]=food[2].size();Len[3]=food[3].size();
	// 计算三种元素的背包问题答案
	FOR(i, 1, 3){
		FOR(j, 0, Len[i]-1){	// 枚举物品种类
			ROF(k, C, food[i][j].ene){	// 枚举背包容量
				dp[i][k]=max(dp[i][k],dp[i][k-food[i][j].ene]+food[i][j].unit);
			}
		}
	}
	ll ans=0;
	FOR(i, 0, C){
		FOR(j, 0, C-i){
			ans=max(min({dp[1][i],dp[2][j],dp[3][C-i-j]}),ans);
		}
	}
	cout<<ans<<'\n';
	return 0;
}

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

Posted on Edited on

思路讲解

2025牛客WC3-C-智乃的Notepad(Easy version) 的结论如下：

字典树每次扩充新节点++ans；最后ans就是字典树的节点数量（严格来说是不包含idx=0的节点的数量），当然此时不是答案，根据观察，所有的节点都需要被回退，只有最长的字符串不需要回退，所以答案就是

1
cout<<ans*2-maxLen<<'\n';

除了最长字符串上的节点，全部都要打一遍，然后再删除掉，故ans*2，然后最长的字符串不需要回退，-maxLen

那么既然就是要求区间快速查询，我们只要查出这个区间最长的字符串长度是多少 & 这个区间生成的Trie树节点数 就行了。

当然前者简单，用树状数组只会树状数组（ST表，线段树，单调栈……）就行了（前置知识：用树状数组实现RMQ）

后者怎么搞那？（思路参考以下讲解）

https://www.bilibili.com/video/BV1HzfmYZEje/?spm_id_from=333.337.search-card.all.click&vd_source=4350e5f2584d2f27c848b347ea11b675

然后还有一个点可能没有点破，就是其实你可以在插入完第R个字符串之后马上处理以第R个为结尾的询问，因为你提前知道所有的询问是吧（又不是强制在线），这也算是一种离线的trick吧

既然我们知道了可以这么玩就好了，我们只需要优先考虑后面插入的字符串就好了，因为后面要的一定要，区间是必定包含后面的，前面要的只有在包含前面是才加入节点数。

具体实现也可以用树状数组维护前缀和来做。

AC代码

AC

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

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = b; i >= a; --i)
#define SZ(x) ((int)x.size())
#define all(x,N) x.begin()+1,x.begin()+N+1
#define all1(x) x.begin(),x.end()

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;
const ll MAXN=static_cast<ll>(1e5)+10;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{
			if(ch=='-')
				f=-1;
			ch=getchar();
		}
	while(ch>='0' && ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline string reads()
{
	string str="";
	char ch=getchar();
	//处理空格或回车 
	while(ch==' ' || ch=='\n' || ch=='\r')
		{
			ch=getchar(); 
		}
	//读入
	while(ch!=' ' && ch!='\n' && ch!='\r')
		{
			str+=ch;
			ch=getchar();
		} 
	return str;
}
inline void write(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int N,T;
int nex[MAXN*10][28];	// trie树
int color[MAXN*10]; // 颜色
int tr[MAXN];	// 树状数组，用来求区间最长字符串长度
int tree[MAXN];	// 树状数组2，用来记录前缀和
int idx;	// trie树用编号
int Len[MAXN];
int Ans[MAXN];
string S[MAXN];
struct Query{
	int l,r,id;
	bool operator<(const Query &other) const{
		return r<other.r;
	}
};
vector<Query> que(MAXN); 
inline int lowbit(int x){
	return x&(-x);
}
inline void add2(int p,int x){
	while (p<=N) {
		tree[p]+=x;
		p+=lowbit(p);
	}
}
inline int query2(int p){
	int res=0;
	while (p>0) {
		res+=tree[p];
		p-=lowbit(p);
	}
	return res;
}
inline void add(int p,int x){
	while (p<=N) {
		tr[p]=x;	// 因为只是用来建树，顺序调用，所以这样写没问题
		for(int i=1;i<lowbit(p);i*=2){	// 遍历i下面的区间
			tr[p]=max(tr[p],tr[p-i]);
		}
		p+=lowbit(p);
	}
}
inline int query(int l,int r){
	int res=0;
	while (l<=r) {
		if(r-lowbit(r)<l){
			res=max(Len[r],res);
			r-=1;
		}else {
			res=max(tr[r],res);
			r-=lowbit(r);
		}
	}
	return res;
}
inline void buildTree(string &s,int c){
	int node=0;
	int len=SZ(s);
	FOR(i, 0, len-1){
		if(nex[node][s[i]-'a']==0){
			nex[node][s[i]-'a']=++idx;
			node=idx;
			add2(c,1);
			color[node]=c;
		}else{
			node=nex[node][s[i]-'a'];
//			colCnt[color[node]]-=1;
			add2(color[node], -1);
			add2(c, 1);
//			colCnt[c]+=1;
			color[node]=c;
		}
	}
	int begin=lower_bound(all(que,T),(Query){0,c,0})-que.begin();
	int end=upper_bound(all(que,T),(Query){MAXN,c,MAXN})-que.begin();
	FOR(j, begin, end-1){
		int res=query2(que[j].r)-query2(que[j].l-1);
		Ans[que[j].id]=res*2-query(que[j].l, que[j].r);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	N=read();T=read();
	FOR(i, 1, N){
		S[i]=reads();
		Len[i]=SZ(S[i]);
		// 树状数组操作(RMQ)
		add(i,Len[i]);
	}
	FOR(i, 1, T){
		que[i].l=read();
		que[i].r=read();
		que[i].id=i;
	}
	sort(all(que,T));
	FOR(i, 1, N){
		buildTree(S[i], i);
	}
	FOR(i, 1, T){
		write(Ans[i]);
		putchar('\n');
	}
	return 0;
}
/*
3 3
nowcoder
nowdays
now
1 3
1 2
3 3

10 1
agdsjaxbsv
afghdgsgahg
saghjvxbaa
aasagahdb
abnsbdvsbdabvgh
abnsbbzbavba]
aaaasdfxfvax
ytftyfsasdfd
fdsdssddsdx
uufdssdvgd
1 10

*/

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

因为用了两个树状数组，这个名字起的也比较重，前面好几次搞混了。还有N，T搞混了，que数组长度是T，我以为是N了，总之最后有惊无险，都搞定了