Codeforce#547 Div3 F题题解？_coderforce 题解

题目:http://codeforces.com/contest/1141/problem/F2

一开始看数据规模，1500，啊好友好，直接F2吧……
多半是前面的【水题】做的膨胀了……
然后滚回F1了。
是这样的，春季校赛不是有个异或前缀和dp吗？也是选一些互不重合的连续区间，求区间异或和最大的数量。异或和和一般的和不是一样的吗？那敢情好，b[i]表示到i为止的前缀和，f[i]表示到i为止区间和为t的互不相交的最大区间数，dp时在i前面找一个j，使f[j]==f[i-1](保证j+1没有被覆盖过)且b[i]-b[j]==t(此时选定区间为[j+1,i])，由于b中元素范围比较大，用map维护b中元素的值对应的最后一个元素的下标，在map中找t-b[i]即可，O(nlogn)的dp。
那么问题来了，t是多少呢？
按数值枚举是不可能的，只能枚举每一种区间作为答案，有n^2种可能。总时间复杂度是O(n^3logn)。瞬间被打回原型。

    #include <bits/stdc++.h>
    using namespace std;
    long long a[4000],b[4000],f[3100][3100],dp[4000],g[4000];
    int main (/*int argc, char const* argv[]*/){
    	std::ios::sync_with_stdio(false);
    	int n;cin>>n;
    	for(int i=1;i<=n;i+=1){
    		cin>>a[i];
    		b[i]=b[i-1]+a[i];
    	}
    	for(int i=1;i<=n;i+=1){
    		for(int j=i;j<=n;j+=1){
    			f[i][j]=b[j]-b[i-1];
    		}
    	}
    	vector<pair<int,int>>ans;
    	for(int i=1;i<=n;i+=1){
    		for(int j=i;j<=n;j+=1){
    			int t=f[i][j];
    			vector<pair<int,int>>pans;
    			dp[0]=0;
    			map<int,int>st;
    			st[0]=0;
    			for(int k=1;k<=n;++k){
    				dp[k]=dp[k-1];
    				if(st.find(b[k]-t)!=st.end()){
    					int u=st[b[k]-t];
    					if(dp[u]==dp[k]){
    						++dp[k];
    						pans.push_back(make_pair(u+1,k));
    					}
    				}
    				st[b[k]]=k;
    			}
    			if(ans.size()<pans.size())ans=pans;
    		}
    	}
    	cout<<ans.size()<<endl;
    	for(auto i:ans){
    		cout<<i.first<<' '<<i.second<<endl;
    	}
    	
    	return 0;
    }
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

我不知道这种方法还能不能继续优化，如果要优化很可能是对外层i和j动手脚，或者和dp时的k联系起来，但本人实在想不到了……如果有人想到这种做法的优化，请务必联系本菜鸡……

于是推翻重来：
感谢Acoder巨佬提供的状态枚举思路，f[i][j]代表选取以区间[i,j]为最后一个区间的方案最大值。那么只要在之前的区间中找一对[p,q]，其中q<i，使b[q]-b[p-1]=f[j]-f[i-1]且f[p][q]尽量大。
还是用一个叫st的map<int,pair>维护区间和，这里st[m]=<p,q>表示目前为止区间和为m的各个区间中，f[p][q]最大而q尽量小的那个。
什么意思呢？首先，由于枚举了i,j，我们希望能在O(logn)的时间复杂度内完成转移。那么，转移的来源是什么？就是st[m]。但前提是必须保证转移的区间不重合，即st[m]的右端点q必须小于当前的左端点i！
如果f[i][j]不能由当前的st[m]转移，意味着什么？也许f[i][j]可以由更之前的区间转移过来，但回想st[m]的定义：st[m]=<p,q>，其中[p,q]是当前所有和为m的区间中f[p,q]最大的那个，且在此前提下q尽量的小。如果f[i][j]不能被f[p][q]转移，那么f[i][j]也一定不能由其他的和为m，且f值大于等于f[p][q]的区间转移过来。换句话说，即使f[i][j]被某个区间转移过来，它的值一定小于等于f[p][q]。而我们希望在相同f值的前提下，st[m]的右端点q尽量小；而j一定大于q。所以，此时的区间[i,j]如同【银背族长·詹姆斯】，被值不比它小，还比它靠左的区间[p,q]完爆了！所以，此时我们干脆不要管f[i][j]了，反正统计答案也轮不到它。所以修改f[i][j]的定义：f[i][j]代表选取以区间[i,j]为最后一个区间的方案最大值，但被前面的某个区间”完爆”者不算在内。
显然，先枚举右端点j，再枚举左端点i，所得到的f[i,j]的答案一定是相同答案中右端点最小的。而且f[i][j]如果成功被map[m]转移，那么显然f[i][j]一定是当前区间和为m的区间中答案最大的区间。所以只要f[i][j]能被转移，就用[i,j]更新map[m]，从而维护了map。另外，如果在map中找不到m，意味着[i,j]是区间和为m的第一个区间，令之为1并更新map即可。

    //模板嵌套不打空格，低版本c++CE注意
    #include <bits/stdc++.h>
    using namespace std;
    int a[2000],b[2000];
    struct msp{
    	int lasti,lastj,data;
    }f[2000][2000];
    int main (/*int argc, char const* argv[]*/){
    	std::ios::sync_with_stdio(false);
    	int n;cin>>n;
    	for(int i=1;i<=n;i+=1){
    		cin>>a[i];
    		b[i]=b[i-1]+a[i];
    	}
    	map<int,pair<int,int>>st;//st[i]means the maxsize of numbers of blocks with sum=i while r keep the min
    	for(int j=1;j<=n;j+=1){//j first
    		for(int i=1;i<=j;i+=1){
    			if(st.find(b[j]-b[i-1])!=st.end()){
    				pair<int,int>t=st[b[j]-b[i-1]];
    				if(t.second<i){
    					f[i][j].data=f[t.first][t.second].data+1,f[i][j].lasti=t.first,f[i][j].lastj=t.second;//lasti,lastj record the answer
    					st[b[j]-b[i-1]]=make_pair(i,j);
    				}
    			}
    			else f[i][j].data=1,st[b[j]-b[i-1]]=make_pair(i,j);
    		}
    	}
    	int fi,fj,maxm=0;
    	for(int i=1;i<=n;i+=1){
    		for(int j=i;j<=n;j+=1){
    			if(f[i][j].data>maxm){
    				maxm=f[i][j].data,fi=i,fj=j;
    			}
    		}
    	}
    	cout<<maxm<<endl;
    	while(fi){
    		cout<<fi<<' '<<fj<<endl;
    		int ti=f[fi][fj].lasti,tj=f[fi][fj].lastj;
    		fi=ti,fj=tj;
    	}
    	return 0;
    }
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

以上。