Znzryb's Blog
0%

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了，总之最后有惊无险，都搞定了

Posted on Edited on

思路讲解

这题代码挺简单的，这个代码看起来长，实际上全部是快读模版和一些宏定义

然后我们来讲一讲，实际上就是字典树建树过程。

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

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

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

AC代码

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

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
#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) 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 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 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;
}
int N,T;
int idx;
int nex[MAXN*10][28]; //wei[MAXN*10];
ll ans;
int L,R;

inline void buildTree(string &s){
	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;
			// wei[idx]+=len-i;
			++ans;
		}else{
			node=nex[node][s[i]-'a'];
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	N=read(),T=read();
	int maxLen=0;
	FOR(i, 1, N){
		string s;
		s=reads();
		maxLen=max(maxLen,SZ(s));
		buildTree(s);
	}
	L=read();R=read();
	cout<<ans*2-maxLen<<'\n';
	return 0;
}
/*

*/

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

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

段错误

字典树一般要开10倍空间。

Posted on Edited on

思路讲解

image

交换速度你可以理解为这两个球想幽灵一样，直接穿过，没有碰撞（因为我们不在乎是哪个球撞的，我们只在乎碰撞次数）

套了一个树状数组查逆序对的板子

不要用unordered_map以及set用于离散化，常数有一点大。

可以用unique，sort，以及lower_bound实现离散化，常数比较小，写也不是很难写

还有要求误差小于eps可以这么写，不用直接写<eps，快一点（卡常卡常）

1
2
3
4
5
6
7
8
while (r-l>(eps*l)) {
		DB mid=(l+r)/2.0;
		if(check(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}

双指针就是可以从暴力优化，原本是双层循环，但其实第二次循环有必要从1开始吗？显然不是对吧。

然后注意notMeet可能还是需要lower_bound()一下

1
2
3
4
5
6
7
8
9
10
11
12
13
FOR(i, 1, idx){
		FOR(j,flag,idx_+1){
			if(j>=idx_+1) {flag=j;break;}
			if(pv_[j]<pv[i]) {continue;}	// 必然不会碰到
			DB curt=fabs(pv_[j]-pv[i])/2.0;
			if(curt>t){
				flag=j;
				break;
			}
		}
		int notMeet=lower_bound(&pv_[1], &pv_[idx_+1], pv[i])-&pv_[0];
		res+=flag-notMeet;
	}

AC代码

双指针肯定比树状数组稍微快一点

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

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double DB;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10;
const DB eps=1e-7;
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;
}

ll N,K,tr[MAXN];
DB curP[MAXN];
int idx,idx_;

int pv[MAXN],pv_[MAXN];	// 正速度，负速度
inline bool check(DB t){	// 枚举时间
	ll res=0;
	//   break的那个不要，所以notMeet初始为1
	int flag=1;     // flag=1 上次在哪里停的？
	FOR(i, 1, idx){
		FOR(j,flag,idx_+1){
			if(j>=idx_+1) {flag=j;break;}
			if(pv_[j]<pv[i]) {continue;}	// 必然不会碰到
			DB curt=fabs(pv_[j]-pv[i])/2.0;
			if(curt>t){
				flag=j;
				break;
			}
		}
		int notMeet=lower_bound(&pv_[1], &pv_[idx_+1], pv[i])-&pv_[0];
		res+=flag-notMeet;
	}
	
	if(res>=K){
		return true;
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	N=read(),K=read();
	FOR(i, 1, N){
		int p=read(),v=read();
		if(v<0){
			pv_[++idx_]=p;
		}else{
			pv[++idx]=p;
		}
	}
	sort(&pv[1], &pv[idx+1]);
	sort(&pv_[1], &pv_[idx_+1]);
	DB l=0,r=1e9;
	while (r-l>(eps*l)) {
		DB mid=(l+r)/2.0;
		if(check(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	if(fabs(l-1e9)<(eps*l)){
		cout<<"No\n";
		return 0;
	}
	cout<<"Yes\n";
	cout<<setprecision(7)<<fixed<<l<<endl;
	return 0;
}
/*

4 4
1 1
2 -1
3 -1
0 1

1.5

4 1
4 1
3 -1
2 -1
1 -1

No

8 8
67 1
88 1
75 -1
43 1
23 -1
45 1
49 1
87 -1


*/

各种卡常技巧一起上，终于是过了用树状数组。

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

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double DB;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10;
const DB eps=1e-7;
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;
}

ll N,K,tr[MAXN];
DB curP[MAXN];

struct posv{
	int p,v;
//	bool operator<(const posv &other) const{
//		return p<other.p;
//	}
};
posv pv[MAXN];
inline bool cmp(posv a, posv b){
	return a.p<b.p;
}

inline ll lowbit(ll x){
	return x&(-x);
}
inline void add(ll x) {
	while (x<=N) {
		tr[x]+=1;
		x+=lowbit(x);
	}
}
inline ll query(ll x){
	ll res=0;
	while (x>0) {
		res+=tr[x];
		x-=lowbit(x);
	}
	return res;
}
inline bool check(DB t){	// 枚举时间
	vector<DB> li(N);
//	unordered_map<DB,ll> rank;
	FOR(i, 1, N){
		curP[i]=pv[i].p*1.0+t*pv[i].v;
		li[i-1]=curP[i];
	}
	sort(li.begin(), li.end());
	vector<DB>::iterator it=unique(li.begin(), li.end());
	li.resize(it-li.begin()); // 相当于R-L+1，传进去的仍然是个数
	FOR(i, 1, N){	// 初始化rank与树状数组
		tr[i]=0;
//		rank[li[i-1]]=i;
	}
	ll res=0;
	// 就是求逆序对
	FOR(i, 1, N){
		ll rk=lower_bound(li.begin(), li.end(),curP[i])-li.begin()+1;
		res+=max(i-1-query(rk-1),0ll);
		add(rk);
	}
	if(res>=K){
		return true;
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
//	cin>>N>>K;
	N=read(),K=read();
	FOR(i, 1, N){
		pv[i].p=read();
		pv[i].v=read();
//		cin>>pv[i].p>>pv[i].v;
	}
	sort(&pv[1], &pv[N+1],cmp);
	DB l=0,r=1e9;
	while (r-l>(eps*l)) {
		DB mid=(l+r)/2.0;
		if(check(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	if(fabs(l-1e9)<(eps*l)){
		cout<<"No\n";
		return 0;
	}
	cout<<"Yes\n";
	cout<<setprecision(7)<<fixed<<l<<endl;
	return 0;
}
/*
4 4
1 1
2 -1
3 -1
0 1

3 2
0 1
2 -1
9 -1

*/

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

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

双指针有问题是因为这个

1
2
3
4
5
6
7
8
9
10
11
12
FOR(i, 1, idx){
		FOR(j,flag,idx_+1){
			if(j>=idx_+1) {flag=j;break;}
			if(pv_[j]<pv[i]) {++notMeet;continue;}	// 必然不会碰到
			DB curt=fabs(pv_[j]-pv[i])/2.0;
			if(curt>t){
				flag=j;
				break;
			}
		}
		res+=flag-notMeet;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
hack数据
8 8
67 1
88 1
75 -1
43 1
23 -1
45 1
49 1
87 -1

应该输出
22
输出
18（约）

这个程序看起来没问题，但其实有点问题，就是88理应得到0，但这个程序会给出错误判断，说明notMeet的逻辑有问题，应该使用二分查找更为保险

树状数组超时，MLE

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double DB;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10;
const DB eps=1e-6;

ll N,K,tr[MAXN];
DB curP[MAXN];

struct posv{
	ll p,v;
	bool operator<(const posv &other) const{
		return p<other.p;
	}
};
vector<posv> pv(MAXN);

inline ll lowbit(ll x){
	return x&(-x);
}
inline void add(ll x) {
	while (x<=N) {
		tr[x]+=1;
		x+=lowbit(x);
	}
}
inline ll query(ll x){
	ll res=0;
	while (x>0) {
		res+=tr[x];
		x-=lowbit(x);
	}
	return res;
}
inline bool check(DB t){	// 枚举时间
	vector<DB> li(N);
	unordered_map<DB,ll> rank;
	FOR(i, 1, N){
		curP[i]=pv[i].p*1.0+t*pv[i].v;
		li[i-1]=curP[i];
	}
	sort(li.begin(), li.end());
	vector<DB>::iterator it=unique(li.begin(), li.end());
	li.resize(it-li.begin());
	FOR(i, 1, N){	// 初始化rank与树状数组
		tr[i]=0;
		rank[li[i-1]]=i;
	}
	ll res=0;
	// 就是求逆序对
	FOR(i, 1, N){
		res+=max(i-1-query(rank[curP[i]]-1),0ll);
		add(rank[curP[i]]);
	}
	if(res>=K){
		return true;
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>K;
	FOR(i, 1, N){
		cin>>pv[i].p>>pv[i].v;
	}
	sort(pv.begin()+1, pv.begin()+N+1);
	DB l=0,r=1e9;
	while (r-l>eps) {
		DB mid=(l+r)/2.0;
		if(check(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	if(fabs(l-1e9)<eps){
		cout<<"No\n";
		return 0;
	}
	cout<<"Yes\n";
	cout<<setprecision(7)<<fixed<<l<<endl;
	return 0;
}
/*
4 4
1 1
2 -1
3 -1
0 1

3 2
0 1
2 -1
9 -1

*/

Posted on Edited on

思路讲解

想这样枚举是会超时的，我们发现其实元素加入顺序其实不重要，重要的是这个元素加入到了哪个组中

1
2
3
4
5
6
7
8
9
10
for (int i=1; i<=N; ++i) {
    if(vis[i]) continue;
    for(int j=1;j<=groups+1;++j){
        sumG[j]+=A[i];
        vis[i]=true;
        dfs(cur+1,max(groups,j));
        sumG[j]-=A[i];
        vis[i]=false;
    }
}

所以说只需要减少枚举维度就行了（不再枚举元素）

1
2
3
4
5
6
7
    for(int j=1;j<=groups+1;++j){
        sumG[j]+=A[dep];
//      vis[dep]=true;
        dfs(dep+1,max(groups,j));
        sumG[j]-=A[dep];
//      vis[dep]=false;
    }

AC代码

AC

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

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
#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 pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=17;
ull N,T;
ull A[MAXN];
string s;
unordered_set<ull> st;
//bool vis[MAXN];
ull sumG[MAXN];
// dep就是指当前要计算的用掉的总数量，groups是指现在的组数
void dfs(int dep,int groups) {
    if(dep>N){
        ull res=0;
        for (int i=1; i<=groups; ++i) {
            res^=sumG[i];
        }
        st.insert(res);
        return;
    }
    for(int j=1;j<=groups+1;++j){
        sumG[j]+=A[dep];
//      vis[dep]=true;
        dfs(dep+1,max(groups,j));
        sumG[j]-=A[dep];
//      vis[dep]=false;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>N;
    for(int i=1;i<=N;++i) {
        cin>>A[i];
    }
    dfs(1,0);
    cout<<st.size()<<endl;
    
//  cout<<endl;
//  for(auto it:st) {
//      cout<<it<<endl;
//  }
    return 0;
}
/*
AC https://atcoder.jp/contests/abc390/submissions/62115363

*/

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

TLE

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

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
#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 pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=17;
ull N,T;
ull A[MAXN];
string s;
unordered_set<ull> st;
bool vis[MAXN];
ull sumG[MAXN];
// cur就是指当前要计算的用掉的总数量，groups是指现在的组数
void dfs(int cur,int groups) {
    if(cur>N){
        ull res=0;
        for (int i=1; i<=groups; ++i) {
            res^=sumG[i];
        }
        st.insert(res);
        return;
    }
    for (int i=1; i<=N; ++i) {
        if(vis[i]) continue;
        for(int j=1;j<=groups+1;++j){
            sumG[j]+=A[i];
            vis[i]=true;
            dfs(cur+1,max(groups,j));
            sumG[j]-=A[i];
            vis[i]=false;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>N;
    for(int i=1;i<=N;++i) {
        cin>>A[i];
    }
    dfs(1,0);
    cout<<st.size()<<endl;
    
//  cout<<endl;
//  for(auto it:st) {
//      cout<<it<<endl;
//  }
    return 0;
}
/*

*/