paulzrm's blog

发表于 分类于

本文迁移自洛谷原文。

实质上这题可以用4棵不同的树状数组莽过去

大致思路其他的题解已经讲的很清楚了，这里就讲讲树状数组的不同写法和作用。

比如这道题，我写的第1、2、3、4棵线段树，作用分别是：

1，求左端后缀最大值

2，求右端后缀最小值

3，求左端前缀最大值

4，求右端前缀最小值

如果是要处理前缀的话，我们的 add 函数 和 ask 函数 应该这么写：

1
2
3
4
5
6
inline void add(int x,int d){for(;x<mxn;x+=x&-x)val[x]=max(val[x],d);}  //add 往后 让后面的数在ask时能够处理到它
inline int ask(int x){  //ask 往前
	int rt=0;
	for(;x;x-=x&-x)rt=max(rt,val[x]);
	return rt;
}

反之，如果是处理后缀的话：

1
2
3
4
5
6
inline void add(int x,int d){for(;x;x-=x&-x)val[x]=max(val[x],d);}//add往前
inline int ask(int x){//ask往后
	int rt=0;
	for(;x<mxn;x+=x&-x)rt=max(rt,val[x]);
	return rt;
}

此外，这题还有个小问题，样例以就很好的体现了：在两个数相同的时候，且它们都可以作为最小/大值，那么，他们的贡献就会被多次计算。

其实没有太大的关系，因为我们可以钦定如果两个数相同，前面的数大于后面的数，就可以处理掉这种情况了。实现的话就是在 ask 左端时 ask 而在 ask 右端时 ask 或 即可。

Code:

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
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
using namespace std;
const int mxn=1e6+6;
int a[mxn],n;
struct fenwick1{
	int val[mxn];
	inline void init(){memset(val,0,sizeof(val));}
	inline void add(int x,int d){for(;x;x-=x&-x)val[x]=max(val[x],d);}
	inline int ask(int x){
		int rt=0;
		for(;x<mxn;x+=x&-x)rt=max(rt,val[x]);
		return rt;
	}
}f1;
struct fenwick2{
	int val[mxn];
	inline void init(){for(int i=0;i<mxn;++i)val[i]=n+1;}
	inline void add(int x,int d){for(;x;x-=x&-x)val[x]=min(val[x],d);}
	inline int ask(int x){
		int rt=n+1;
		for(;x<mxn;x+=x&-x)rt=min(rt,val[x]);
		return rt;
	}
}f2;
struct fenwick3{
	int val[mxn];
	inline void init(){memset(val,0,sizeof(val));}
	inline void add(int x,int d){for(;x<mxn;x+=x&-x)val[x]=max(val[x],d);}
	inline int ask(int x){
		int rt=0;
		for(;x;x-=x&-x)rt=max(rt,val[x]);
		return rt;
	}
}f3;
struct fenwick4{
	int val[mxn];
	inline void init(){for(int i=0;i<mxn;++i)val[i]=n+1;}
	inline void add(int x,int d){for(;x<mxn;x+=x&-x)val[x]=min(val[x],d);}
	inline int ask(int x){
		int rt=n+1;
		for(;x;x-=x&-x)rt=min(rt,val[x]);
		return rt;
	}
}f4;
int BiggerL[mxn],BiggerR[mxn];
int SmallerL[mxn],SmallerR[mxn];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	f1.init(),f2.init(),f3.init(),f4.init();
	for(int i=1;i<=n;++i){
		BiggerL[i]=f1.ask(a[i]);
		f1.add(a[i],i);
	}
	for(int i=n;i;--i){
		BiggerR[i]=f2.ask(a[i]+1);
		f2.add(a[i],i);
	}
	for(int i=1;i<=n;++i){
		SmallerL[i]=f3.ask(a[i]);
		f3.add(a[i],i);
	}
	for(int i=n;i;--i){
		SmallerR[i]=f4.ask(a[i]-1);
		f4.add(a[i],i);
	}
	ll ans=0;
	for(int i=1;i<=n;++i){
		ans+=a[i]*1ll*(i-BiggerL[i])*(BiggerR[i]-i);
		ans-=a[i]*1ll*(i-SmallerL[i])*(SmallerR[i]-i);
	}
	cout<<ans<<'\n';
	return 0;
}

发表于 分类于

本文迁移自洛谷原文。

首先我们可以先贪心的想：

假设我们已经匹配到了 串的第 位，那么有一个结论，就是如果 的子串 是 的子串，而 不是，那么最优方案一定是将 整个截下来。

可以感性证明：如果不用 ，用 ，那么 肯定是在 中的；但如果第 个字符加到了后面，就不能确定原来的那一段加上它后是否还在 中，就可能不是最优了。

如果暴力地枚举复杂度会达到 ；

但如果对于 二分最远可以匹配到的地方就可以优化到 。

ps. 我写的这个字符串匹配实质上是 的，但由于题目的要求跑起来实质上跟 的差不多。如果总时限要稳在 就可以写个 kmp 处理，但会变得更复杂。

code:

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
using namespace std;
const int mxn=2e5+5;
string a,b,ta;
int n,m;
vector<pair<int,int> >ans;
inline bool check(int bg,int ed){           //正反都匹配
	if(ed-bg+1>a.size())return 0;
	string t=b.substr(bg,ed-bg+1);
	for(int i=0;i<a.size()-t.size()+1;++i){
		bool ok=1;
		for(int j=0;j<t.size();++j){
			if(a[i+j]!=t[j]){
				ok=0;
				break;
			}
		}
		if(ok)return 1;
	}
	for(int i=0;i<ta.size()-t.size()+1;++i){
		bool ok=1;
		for(int j=0;j<t.size();++j){
			if(ta[i+j]!=t[j]){
				ok=0;
				break;
			}
		}
		if(ok)return 2;
	}
	return 0;
}
inline pair<int,int> getp(int bg,int ed){       //找到位置
	string t=b.substr(bg,ed-bg+1);
	for(int i=0;i<a.size()-t.size()+1;++i){
		bool ok=1;
		for(int j=0;j<t.size();++j){
			if(a[i+j]!=t[j]){
				ok=0;
				break;
			}
		}
		if(ok)return mp(i,i+t.size()-1);
	}
	for(int i=0;i<ta.size()-t.size()+1;++i){
		bool ok=1;
		for(int j=0;j<t.size();++j){
			if(ta[i+j]!=t[j]){
				ok=0;
				break;
			}
		}
		if(ok)return mp(a.size()-i-1,a.size()-i-t.size());
	}
}
inline string E(int bg,int ed){
	return b.substr(bg,ed-bg+1);
}
inline void solve(){
	cin>>a>>b;ta=a;reverse(ta.begin(),ta.end());
	n=a.size(),m=b.size();
	int b=0;
	for(;b<m;++b){    //b是当前处理到的字符串的开头位置
		int l=b,r=m,md;
		for(;l<r-1;){   //二分
			md=l+r>>1;
			if(check(b,md))l=md;
			else r=md;
		}
		if(l==b and !check(b,l)){  //可能是无法匹配
			cout<<"-1\n";
			return;
		}
		if(check(b,l)==1)ans.push_back(getp(b,l));  //贪心过头了，最后一小截没法匹配，与上一个串合并
		b=l;
	}
	cout<<ans.size()<<'\n';
	for(int i=0;i<ans.size();++i)cout<<ans[i].first+1<<' '<<ans[i].second+1<<'\n';
	return;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;//cin>>T;
	for(;T--;)solve();
}

发表于 分类于

本文迁移自洛谷原文。

这里是全网唯一一份分块的题解（也可能是唯一一份分块卡过去的做法）。

现将这 个数分块。

令 表示考虑到某一块中，考虑到第 个位置，上一个位置填的数是 时，这一块的开头为 的方案数对 的贡献的系数。注意，这里是系数，为了好带入到查询时的整合。可以发现， 对于转移无关。

处理更新的代码：

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
inline void go(){
	memset(dp,0,sizeof(dp));
	if(a[0]==0){
		for(ri f=1;f<=3;++f){   //不确定，枚举
			dp[f][0][f]=1;
			for(ri i=1;i<sz;++i){
				ri t=a[i];
				if(a[i]==0){    //分类转移
					for(t=1;t<=3;++t)
						for(ri p=1;p<=3;++p)if(c[p][t]==1)add(dp[f][i][t],dp[f][i-1][p]);
				}else{
					for(ri p=1;p<=3;++p)if(c[p][t]==1)add(dp[f][i][t],dp[f][i-1][p]);
				}
			}
		}
	}else{     //已经确定块头必须是多少
			ri f=a[0];
			dp[f][0][f]=1;
			for(ri i=1;i<sz;++i){
				ri t=a[i];
				if(a[i]==0){
					for(t=1;t<=3;++t)
						for(ri p=1;p<=3;++p)if(c[p][t]==1)add(dp[f][i][t],dp[f][i-1][p]);
				}else
					for(ri p=1;p<=3;++p)if(c[p][t]==1)add(dp[f][i][t],dp[f][i-1][p]);
			}
	}
}

然后，查询时有些复杂：

首先，单独处理好整个数列的第一个块（因为 存的是系数，不好接入）。

然后，对于接下来的每个块，考虑与上一个块的末尾相接。

先处理好每个块的块首的答案，然后利用 直接计算得到块尾的答案。

注意要时时刻刻取模。

这样，分块的做法就写好了。

不过，如果你只做到了这儿，你只会想绝大多数分块一样TLE 11

一些优化：

  • 对于查询时的处理，将 展开成 来节省常数

  • 尽量的去掉大括号

  • register inline

  • 快读快输，火车头

  • 快的大小是信仰数 srand(‘xhztxdy’)

  • 使用 C++14 来替代 C++11

痛苦的心路历程(在 mashups 不断测试)：

整体代码：

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

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define mp make_pair
#define ri register int
#define ld long double
using namespace std;
const int maxn=70007;
char buffer[maxn],*S,*T;
inline char Get_Char(){
    if(S==T){
        T=(S=buffer)+fread(buffer,1,maxn,stdin);
        if(S==T)return EOF;
    }
    return *S++;
}

inline int read(){
    char c;
    int re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)return -re;
    return re;
}

inline void read(int&x){
    char c;
    int re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)x=-re;
    else x=re;
}
const int mxn=78787;
vector<int>g[mxn];
int n,q;
int a[mxn];
int c[4][4];
const int siz=225;
const int md=777777777;
inline void add(int&x,int y){
	x+=y;
	if(x>=md)x-=md;
}
struct tmp{
	ll x,y,z;
	inline void G(){
		x%=md;
		y%=md;
		z%=md;
	}
};
struct ttmp{tmp x,y,z;};
struct kuai{
	int dp[4][siz][4],a[siz],sz;
	inline void init(){
		sz=0;memset(a,0,sizeof(a));
	}
	inline void go(){                //更新
    memset(dp,0,sizeof(dp));
		if(a[0]==0){
			for(ri f=1;f<=3;++f){
				dp[f][0][f]=1;
				for(ri i=1;i<sz;++i){
					ri t=a[i];
					if(a[i]==0){
						for(t=1;t<=3;++t)
							for(ri p=1;p<=3;++p)if(c[p][t]==1)add(dp[f][i][t],dp[f][i-1][p]);
					}else{
						for(ri p=1;p<=3;++p)if(c[p][t]==1)add(dp[f][i][t],dp[f][i-1][p]);
					}
				}
			}
		}else{
				ri f=a[0];
				dp[f][0][f]=1;
				for(ri i=1;i<sz;++i){
					ri t=a[i];
					if(a[i]==0){
						for(t=1;t<=3;++t)
							for(ri p=1;p<=3;++p)if(c[p][t]==1)add(dp[f][i][t],dp[f][i-1][p]);
					}else
						for(ri p=1;p<=3;++p)if(c[p][t]==1)add(dp[f][i][t],dp[f][i-1][p]);
				}
		}
	}
	inline ttmp ret(){return (ttmp){(tmp){dp[1][sz-1][1],dp[1][sz-1][2],dp[1][sz-1][3]},(tmp){dp[2][sz-1][1],dp[2][sz-1][2],dp[2][sz-1][3]},(tmp){dp[3][sz-1][1],dp[3][sz-1][2],dp[3][sz-1][3]}};}
}k[mxn/siz+3];
inline void solve(){
	read(n),read(q);
	for(ri i=1;i<=3;++i)for(int j=1;j<=3;++j)read(c[i][j]);
	for(ri i=0;i<mxn/siz+3;++i)k[i].init();
	for(ri i=0;i<n;++i)++k[i/siz].sz;
	int num=(n+siz-1)/siz;
	for(ri i=0;i<=num;++i)k[i].go();
	for(;q--;){
		ri x,t;read(x),read(t);--x;
		k[x/siz].a[x%siz]=t;
		k[x/siz].go();
		reg tmp cur;
		ri ta=k[0].a[0];
		if(!ta)cur.x=1,cur.y=1,cur.z=1;    //处理第一块
		else{
			cur.x=0,cur.y=0,cur.z=0;
			if(ta==1)cur.x=1;
			if(ta==2)cur.y=1;
			if(ta==3)cur.z=1;
		}
		{
			ttmp tt=k[0].ret();
			reg tmp x=tt.x,y=tt.y,z=tt.z;
			tmp nw;
				nw.x=x.x*cur.x+y.x*cur.y+z.x*cur.z;
				nw.y=x.y*cur.x+y.y*cur.y+z.y*cur.z;
				nw.z=x.z*cur.x+y.z*cur.y+z.z*cur.z;
			nw.G();
			cur=nw;
		}
		for(ri i=1;i<num;++i){
			ri ta=k[i].a[0];
			reg tmp ne;ne.x=0,ne.y=0,ne.z=0;
			if(ta==0){                   //处理块首
					if(c[1][1])ne.x+=cur.x;
					if(c[2][1])ne.x+=cur.y;
					if(c[3][1])ne.x+=cur.z;
					if(c[1][2])ne.y+=cur.x;
					if(c[2][2])ne.y+=cur.y;
					if(c[3][2])ne.y+=cur.z;
					if(c[1][3])ne.z+=cur.x;
					if(c[2][3])ne.z+=cur.y;
					if(c[3][3])ne.z+=cur.z;
			}
			if(ta==1){
					if(c[1][1])ne.x+=cur.x;
					if(c[2][1])ne.x+=cur.y;
					if(c[3][1])ne.x+=cur.z;
			}
			if(ta==2){
					if(c[1][2])ne.y+=cur.x;
					if(c[2][2])ne.y+=cur.y;
					if(c[3][2])ne.y+=cur.z;
			}
			if(ta==3){
					if(c[1][3])ne.z+=cur.x;
					if(c[2][3])ne.z+=cur.y;
					if(c[3][3])ne.z+=cur.z;
			}
			cur=ne;                       //得到块尾
			reg ttmp tt=k[i].ret();
			reg tmp x=tt.x,y=tt.y,z=tt.z;
			reg tmp nw;
				nw.x=x.x*cur.x+y.x*cur.y+z.x*cur.z;
				nw.y=x.y*cur.x+y.y*cur.y+z.y*cur.z;
				nw.z=x.z*cur.x+y.z*cur.y+z.z*cur.z;
				nw.G();
			cur=nw;
			cur.G();
		}
		ri ans=cur.x;add(ans,cur.y);add(ans,cur.z);
		printf("%d\n",ans);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;//cin>>T;
	for(;T--;)solve();
}

加上信仰火车头是6kb

所以6kb干了2kb的活

发表于 分类于

本文迁移自洛谷原文。

这里是验题人的思路（不同于官方题解）

将所有的树都缩成一个点。
对于第 棵树，如果与第 棵树有边，那么 为第 棵树的 号点到第 棵树的 号点的距离。

叶子节点要特判。

尤其要特判当1号节点为叶子（只有一条出边）时的情况。

最后对新图求直径即可。

Code:

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
#include<bits/stdc++.h>
#define ll long long
#define reg register
#define mp make_pair
#define ri register int
#define ld long double
using namespace std;
const int maxn=100004;
char buffer[maxn],*S,*T;
inline char Get_Char(){
    if(S==T){
        T=(S=buffer)+fread(buffer,1,maxn,stdin);
        if(S==T)return EOF;
    }
    return *S++;
}

inline int read(){
    char c;
    ri re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)return -re;
    return re;
}

inline void read(int&x){
    char c;
    ri re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)x=-re;
    else x=re;
}
const int mxn=1e6+6;
vector<int>f[mxn];
vector<pair<int,int> >g[mxn];
int n,root;
int u[mxn],v[mxn];
int pa[mxn];
int dep[mxn];
int max_deep;
int mxdp[mxn];
inline void dfs1(int x,int par=-1,int deep=1){
	mxdp[x]=1;
	dep[x]=deep;pa[x]=par;
	max_deep=max(max_deep,deep);
	for(ri i=0;i<f[x].size();++i){
		ri y=f[x][i];
		if(y!=par)dfs1(y,x,deep+1),mxdp[x]=max(mxdp[x],mxdp[y]+1);
	}
}
ll dist[mxn];
inline void dfs2(int x,int par=-1,ll dst=0){
	dist[x]=dst;
	for(ri i=0;i<g[x].size();++i){
		ri y=g[x][i].first;ll w=g[x][i].second;
		if(y!=par)dfs2(y,x,dst+w);
	}
}
inline void solve(){
	read(n);
	for(ri i=1;i<n;++i){
		read(u[i]),read(v[i]);
		f[u[i]].push_back(v[i]);
		f[v[i]].push_back(u[i]);
	}
	root=1;
	dfs1(root);//对原树进行处理
	for(ri i=1;i<n;++i){   //将树缩成点
		if((u[i]==1 or v[i]==1) and f[1].size()==1){
			int t;
			if(u[i]==1)t=v[i];
			else t=u[i];
			g[u[i]].push_back(mp(v[i],max_deep+dep[t]-1));
			g[v[i]].push_back(mp(u[i],max_deep+dep[t]-1));
		}else if(f[u[i]].size()==1 or f[v[i]].size()==1){
			g[u[i]].push_back(mp(v[i],max_deep));
			g[v[i]].push_back(mp(u[i],max_deep));
		}else if(u[i]==pa[v[i]]){
			g[u[i]].push_back(mp(v[i],dep[v[i]]));
			g[v[i]].push_back(mp(u[i],dep[v[i]]));
		}else{
			g[u[i]].push_back(mp(v[i],dep[u[i]]));
			g[v[i]].push_back(mp(u[i],dep[u[i]]));
		}
	}
	memset(dist,63,sizeof(dist)); //求直径
	dfs2(root);
	ri place;
	place=1;
	for(ri i=1;i<=n;++i)if(dist[i]>dist[place])place=i;
	memset(dist,63,sizeof(dist));
	dfs2(place);
	ll Max=0;
	for(ri i=1;i<=n;++i)Max=max(Max,dist[i]);
	printf("%lld\n",Max+1);
}
int main(){
	ios_base::sync_with_stdio(false);
	int T=1;//cin>>T;
	for(;T--;)solve();
	return 0;
}

发表于 分类于

本文迁移自洛谷原文。

考虑dp。

令 表示走到底 个集市时的最大收益。

1.最朴素的dp

循环 ，枚举 进行转移。

复杂度：

2.分离常项

假设现在是 ，要从 转移

1.

dp[i]=max(dp[j]+U*(place[i]-place[j]))+val[i]

有

$dp_j+U*(place_i-place_j)=dp_j-Uplace_j+Uplace_i$

所以

dp[i]=max(dp[j]-U*place[j])+val[i]+U*place[i]

用线段树/树状数组维护即可。

2.

同理。

时间复杂度:

3.日期相同的情况

贪心可得一定是从一个点直着走到另一个点，中间不会回头。

这里单独弄一个dp。

表示以为结束点，进过集市的开始点在 的左边/右边的最大收益。

预处理出不考虑相同日期时每一个点的dp值，然后从左往右、从右往左贪心的递推即可。类似最大子段和。

Code:

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
#include<bits/stdc++.h>
#define ll long long
#define reg register
#define mp make_pair
#define ri register int
#define ld long double
using namespace std;
const int mxn=1e6+6;
int dp[mxn];
vector<int>g[mxn];
int n,S,D,U;
struct market{
	int date,money,place;
}a[mxn];
inline bool operator <(market a,market b){
	if(a.date!=b.date)return a.date<b.date;
	return a.place<b.place;
}
struct bit1{  //左边（前缀）
	int val[mxn];
	inline void init(){memset(val,-63,sizeof(val));}
	inline void upd(int x,int d){for(++x;x<mxn;x+=x&-x)val[x]=max(val[x],d);}
	inline int ask(int x){
		ri rt=-2147483647;
		for(++x;x;x-=x&-x)rt=max(rt,val[x]);
		return rt;
	}
}Left;
struct bit2{  //右边（后缀）
	int val[mxn];
	inline void init(){memset(val,-63,sizeof(val));}
	inline void upd(int x,int d){for(++x;x;x-=x&-x)val[x]=max(val[x],d);}
	inline int ask(int x){
		ri rt=-2147483647;
		for(++x;x<mxn;x+=x&-x)rt=max(rt,val[x]);
		return rt;
	}
}Right;
int tmpl[mxn],tmpr[mxn];
inline void cmax(int&x,int y){if(x<y)x=y;}
inline void Same(int L,int R){ //日期相同的情况
	for(ri i=L;i<=R;++i)tmpl[i]=tmpr[i]=max(Left.ask(a[i].place)-a[i].place*D,Right.ask(a[i].place)+a[i].place*U)+a[i].money;
	for(ri i=L+1;i<=R;++i)cmax(tmpl[i],tmpl[i-1]-(a[i].place-a[i-1].place)*D+a[i].money);
	for(ri i=R-1;i>=L;--i)cmax(tmpr[i],tmpr[i+1]-(a[i+1].place-a[i].place)*U+a[i].money);
	for(ri i=L;i<=R;++i){
		dp[i]=max(tmpl[i],tmpr[i]);
		Left.upd(a[i].place,dp[i]+a[i].place*D);
		Right.upd(a[i].place,dp[i]-a[i].place*U);
	}
}
inline void solve(){
	Left.init();Right.init();
	memset(dp,-63,sizeof(dp));
	scanf("%d%d%d%d",&n,&U,&D,&S);
	for(ri i=1;i<=n;++i)scanf("%d%d%d",&a[i].date,&a[i].place,&a[i].money);
	sort(a+1,a+n+1);
	a[n+1].place=S;a[0].place=S;a[n+1].date=a[n].date+1;++n;
	dp[0]=0;
	Left.upd(S,S*D);
	Right.upd(S,-S*U);
	for(ri i=1;i<=n;++i){
		if(a[i+1].date==a[i].date and i<=n){
			ri j=i+1;
			for(;j<=n and a[j].date==a[i].date;++j);
			Same(i,j-1);
			i=j-1;
			continue;
		}
		dp[i]=max(Left.ask(a[i].place)-a[i].place*D,Right.ask(a[i].place)+a[i].place*U)+a[i].money;
		Left.upd(a[i].place,dp[i]+a[i].place*D);
		Right.upd(a[i].place,dp[i]-a[i].place*U);
	}
	printf("%d\n",dp[n]);
}
int main(){
	ios_base::sync_with_stdio(false);
	int T=1;//cin>>T;
	for(;T--;)solve();
}

发表于 分类于

本文迁移自洛谷原文。

一道较为简单的双指针

每次维护左边的人走到那个旗子，右边的人走到那个旗子，慢慢向中间不断更新靠拢即可。

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
#include<bits/stdc++.h>
#define ll long long
#define reg register
#define mp make_pair
#define ri register int
#define ld long double
using namespace std;
const int mxn=2e5+5;
vector<int>g[mxn];
int n,m;
ld len;
ld a[mxn];
inline void solve(){
	cin>>n>>len;
	for(int i=1;i<=n;++i)cin>>a[i];
	int l=1,r=n;
	ld cl=0,cr=len;
	ld sl=1,sr=1;
	ld ans=0;
	for(;l<=r;){//向中间推
		ld dl=a[l]-cl,dr=cr-a[r];
		ld tl=dl/sl,tr=dr/sr;
		if(tl<tr){
			cl=a[l];
			cr-=tl*sr;
			ans+=tl;
			sl=sl+1;
			++l;
		}else{
			cr=a[r];
			cl+=tr*sl;
			ans+=tr;
			sr=sr+1;
			--r;
		}
	}
	ans+=(cr-cl)/(sl+sr);//中间没有旗子了
	cout<<fixed<<setprecision(9)<<ans<<'\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;cin>>T;
	for(;T--;)solve();
}

发表于 分类于

本文迁移自洛谷原文。

考虑dp。

令 表示向左移动 格时，向上移动的最小格数。

对于数据预处理完后，倒着去一边取 即可。（因为它要大于它后面所有的）

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
#include<bits/stdc++.h>
#define ll long long
#define reg register
#define mp make_pair
#define ri register int
#define ld long double
using namespace std;
const int mxn=1e6+6;
int n,m;
int a[mxn],b[mxn],c[mxn],d[mxn];
int l[mxn],u[mxn];
inline void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;++i)cin>>a[i]>>b[i];
	for(int i=1;i<=m;++i)cin>>c[i]>>d[i];
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(c[j]>=a[i] and d[j]>=b[i]){//预
				l[c[j]-a[i]]=max(l[c[j]-a[i]],d[j]-b[i]+1);
			}
		}
	}
	for(int i=1000001;~i;--i)l[i]=max(l[i],l[i+1]);//总
	int ans=100000001;
	for(int i=0;i<=1000001;++i)ans=min(ans,i+l[i]);//比较
	cout<<ans<<'\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;//cin>>T;
	for(;T--;)solve();
}

发表于 分类于

本文迁移自洛谷原文。

考虑构图。

对于集合 ，如果有 的话，对号节点向 号节点连一条边权为 的边。

由于题目要求说是无还，所以对这张新图跑最大生成树即可。（不是树必然有环）

最大生成树就是将最小生成树 Kruskal 中每次取出边权最小的边改为最大的边即可，

Code:

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
#include<bits/stdc++.h>
#define ll long long
#define reg register
#define mp make_pair
#define ld long double
using namespace std;
const int mxn=4e5+5;
vector<int>g[mxn];
int n,m;
int a[mxn],b[mxn];
vector<pair<ll,pair<int,int> > >edges;
int f[mxn];
inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
inline void uni(int x,int y){
	x=find(x),y=find(y);
	if(x!=y)f[x]=y;
}
ll tot,ans;
inline void solve(){
	cin>>m>>n;
	for(int i=1;i<=n+m;++i)f[i]=i;
	for(int i=1;i<=m;++i)cin>>a[i];
	for(int i=1;i<=n;++i)cin>>b[i];
	for(int i=1;i<=m;++i){
		int x,u;cin>>x;
		for(;x--;){
			cin>>u;
			edges.push_back({a[i]+b[u],{i,m+u}});//建边
			tot+=a[i]+b[u];
		}
	}
	sort(edges.rbegin(),edges.rend());
	for(int tt=0;tt<edges.size();++tt){ //最大生成树（最大能保留的边的权值和）
		pair<ll,pair<int,int> >p=edges[tt];
		int x=p.second.first,y=p.second.second;
		if(find(x)==find(y))continue;
		uni(x,y);
		ans+=p.first;
	}
	cout<<tot-ans<<'\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;//cin>>T;
	for(;T--;)solve();
}

发表于 分类于

本文迁移自洛谷原文。

人菜，只会打暴力

虽然是用小号， 但还是div2里第一个AC的

由于每操作一次就相当于将两个不互质的数变得互质，所以我们的目标是找到一种排列使得相邻两个数不互质的数量尽可能的少。

考虑分解质因数。将由相同质因数的放在一起，留下一个做为连接这个质因数与下一个质因数的桥梁。

暴力即可。

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<bits/stdc++.h>
#define ll long long
#define reg register
#define mp make_pair
#define ri register int
#define ld long double
using namespace std;
const int mxn=2e5+5;
vector<int>g[mxn];
int n,m;
int a[mxn];
vector<int>ps;
inline void solve(){
	cin>>n;ps.clear();int tn=n;
	vector<int>v;v.clear();
	for(int i=2;i*i<=n;++i){
		if(n%i==0){
			v.push_back(i);
			if(i!=n/i)v.push_back(n/i);
		}
	}
	v.push_back(n);
	sort(v.begin(),v.end());
	for(int i=2;i*i<=tn;++i){
		if(tn%i==0){
			ps.push_back(i);
			for(;tn%i==0;)tn/=i;
		}
	}
	if(tn!=1)ps.push_back(tn);
	if(ps.size()==1){
		for(int i:v)cout<<i<<' ';
		cout<<'\n'<<0<<'\n';
		return;
	}
	if(ps.size()==2 and v.size()==3){
		cout<<v[0]<<' '<<v[1]<<' '<<v[2]<<'\n';
		cout<<1<<'\n';
		return;
	}
	if(ps.size()>2){
		for(int i=0;i<ps.size()-1;++i){
			if(i){
				for(int j=0;j<v.size();++j){
					if(v[j]%ps[i]==0 ){
						if(v[j]!=ps[i]*ps[i+1])cout<<v[j]<<' ';
						v.erase(v.begin()+j);
						--j;
					}
				}
				cout<<ps[i]*ps[i+1]<<' ';
			}else{
				cout<<ps[i]*ps[ps.size()-1]<<' ';
				for(int j=0;j<v.size();++j){
					if(v[j]%ps[i]==0 ){
						if(v[j]!=ps[i]*ps[i+1] and v[j]!=ps[i]*ps[ps.size()-1])cout<<v[j]<<' ';
						v.erase(v.begin()+j);
						--j;
					}
				}
				cout<<ps[i]*ps[i+1]<<' ';
			}
		}
		for(int i:v)cout<<i<<' ';cout<<"\n0\n";
	}else{//只有两个质因数的时候不用留桥梁，需要特判
		for(int i=0;i<ps.size()-1;++i){
			if(i){
				for(int j=0;j<v.size();++j){
					if(v[j]%ps[i]==0 ){
						if(v[j]!=ps[i]*ps[i+1])cout<<v[j]<<' ';
						v.erase(v.begin()+j);
						--j;
					}
				}
				cout<<ps[i]*ps[i+1]<<' ';
			}else{
				cout<<ps[i]*ps[ps.size()-1]<<' ';
				for(int j=0;j<v.size();++j){
					if(v[j]%ps[i]==0 ){
						if(v[j]!=ps[i]*ps[i+1] and v[j]!=ps[i]*ps[ps.size()-1])cout<<v[j]<<' ';
						v.erase(v.begin()+j);
						--j;
					}
				}
			}
		}
		for(int i:v)cout<<i<<' ';cout<<"\n0\n";
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;cin>>T;
	for(;T--;)solve();
}
0%