发表于 | 更新于

Link

设计出了状态，但没有想到转移

Solution

f[l][r][c]f[l][r][c]表示在洗车店区间[l,r][l,r]，最便宜的价格为cc的最大收入。 一开始想转移的时候，觉得应该是所有经过一段区间的消费者都要算进去，但这样就会有重复 最后发现自己的想法是多么naive 每次转移f[l][r][c]f[l][r][c]，只算被区间完全包含的消费者们。 对于枚举到的每个区间，处理h[i][c]h[i][c]，表示经过点ii而且要求高于cc的消费者的个数，然后就枚举断点转移就好了。

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
#include "lucida"

using std::max;
using std::sort;
using std::lower_bound;
using std::unique;
using std::partial_sum;
const int MAXN=50+11,MAXM=4000+11;
int a[MAXN],f[MAXN][MAXN][MAXM],g[MAXN][MAXN][MAXM],pp[MAXN][MAXN][MAXM],plim[MAXN][MAXN][MAXM];
void DFS(int l,int r,int c) {
	if(l>r || !pp[l][r][c]) 
		return;
	a[pp[l][r][c]]=plim[l][r][c];
	DFS(l,pp[l][r][c]-1,plim[l][r][c]);
	DFS(pp[l][r][c]+1,r,plim[l][r][c]);
}
int main() {
//	freopen("input","r",stdin);
	static int lbd[MAXM],rbd[MAXM],lim[MAXM],nums[MAXM],cnt[MAXN][MAXM];
	int n,m;is>>n>>m;
	for(int i=1;i<=m;++i) {
		is>>lbd[i]>>rbd[i]>>lim[i];
		nums[i]=lim[i];
	}
	sort(nums+1,nums+1+m);
	int nc=unique(nums+1,nums+1+m)-nums-1;
	for(int i=1;i<=m;++i)
		lim[i]=lower_bound(nums+1,nums+1+nc,lim[i])-nums;
	//处理出被当前区间完全包含的
	//最低要求为c的
	//经过i点的
	//数目h[i][c]
	for(int length=1;length<=n;++length)
		for(int l=1,r=length;r<=n;++l,++r) {
			memset(cnt,0,sizeof(cnt));
			for(int i=1;i<=m;++i) 
				if(l<=lbd[i] && rbd[i]<=r){
					for(int p=lbd[i];p<=rbd[i];++p)
						cnt[p][lim[i]]++;
				}
			for(int i=1;i<=n;++i) 
				//partial_sum(cnt[i]+1,cnt[i]+1+m,cnt[i]+1);
				for(int c=m-1;c;--c)
					cnt[i][c]+=cnt[i][c+1];
			for(int c=1;c<=m;++c)
				for(int i=l;i<=r;++i)
					if(chkmx(f[l][r][c],g[l][i-1][c]+g[i+1][r][c]+cnt[i][c]*nums[c])) {
						pp[l][r][c]=i;
						plim[l][r][c]=c;
						g[l][r][c]=f[l][r][c];
					}
			for(int c=m-1;c;--c)
				if(chkmx(g[l][r][c],g[l][r][c+1])) {
					pp[l][r][c]=pp[l][r][c+1];
					plim[l][r][c]=plim[l][r][c+1];
				}
		}
	os<<g[1][n][1]<<'\n';
	DFS(1,n,1);
	for(int i=1;i<=n;++i)
		os<<nums[a[i]?a[i]:m]<<(i==n?'\n':' ');
	return 0;
}

发表于 | 更新于

Link

Solution

化简一下式子，比较简单，只用到了等比数列的知识 化简出来之后，发现是当 的时候，是几个幂乘一乘加一加，而这些数字都是小于模数的，所以一定与模数互质，用费马小定理优化即可。 有一个坑点： 当a==1a==1的时候，求和的式子里面就没有幂了！所以只能先把nn存起来，然后分开讨论！

Tips

看一个式子是否满足适用条件，要循环地展开下去查看是否满足

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
//Code by Lucida
#include<bits/stdtr1c++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
typedef long long int64;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int P=1000000007,MAXN=1e3+11,MAXL=1e6+11;

template <class T> T Pow(T base,int index)
{
	T res;
	for(res.SetI();index;base*=base,index>>=1)
		if(index&1) res*=base;
	return res;
}
struct ModInt
{
	int num;
	ModInt(int x=0):num(x%P){}
	ModInt inv() {return Pow(*this,P-2);}
	ModInt &operator =(int x){return *this=ModInt(x);}
	ModInt &operator +=(ModInt a){num=((int64)num+a.num)%P;return *this;}
	ModInt &operator -=(ModInt a){num=((int64)num-a.num)%P;return *this;}
	ModInt &operator *=(ModInt a){num=((int64)num*a.num)%P;return *this;}
	ModInt &operator /=(ModInt a){return (*this)*=a.inv();}
	ModInt &operator +=(int a){return *this+=ModInt(a);}
	ModInt &operator -=(int a){return *this-=ModInt(a);}
	ModInt &operator *=(int a){return *this*=ModInt(a);}
	ModInt &operator /=(int a){return *this/=ModInt(a);}
	void SetI(){num=1;}
	int Num(){return (num+P)%P;}
};
template<class T> ModInt operator +(ModInt a,const T& b){a+=b;return a;}
template<class T> ModInt operator -(ModInt a,const T& b){a-=b;return a;}
template<class T> ModInt operator *(ModInt a,const T& b){a*=b;return a;}
template<class T> ModInt operator /(ModInt a,const T& b){a/=b;return a;}
int atoi_mod(char *ip,int modu)
{
	bool f;char ch;int x;
	for(f=0,ch=0;ch<'0' || '9'<ch;ch=*ip++) f|=ch=='-';
	for(x=0;'0'<=ch && ch<='9';ch=*ip++) x=((int64)x*10+ch-'0')%modu;
	x=f?modu-x:x;x=x==0?modu:x;return x;
}
char N[MAXL],M[MAXL];
int a,b,c,d;
struct Sequence
{
	int a,q;
	Sequence(int a,int q):a(a),q(q){}
	ModInt operator ()(int x) {return (Pow(ModInt(q),x)-1)*a/(q-1);}
};
int F()
{
	ModInt Ans=1,a=::a,b=::b,c=::c,d=::d,sam_1,ssn_1,s,t;
	int mp_1=atoi_mod(M,P-1),mp=atoi_mod(M,P),np_1=atoi_mod(N,P-1),np=atoi_mod(N,P);
	sam_1=a.Num()!=1?Sequence(1,a.Num())(mp_1-1):mp-1;
	s=c*Pow(a,mp_1-1),t=b*c*sam_1+d;
	ssn_1=s.Num()!=1?Sequence(1,s.Num())(np_1-1):np-1;
	Ans=Pow(s,np_1-1)+ssn_1*t;
	Ans=Pow(a,mp_1-1)*Ans+sam_1*b;
	return Ans.Num();
}

int main()
{
	scanf("%s%s",N,M);	
	get(a),get(b),get(c),get(d);
	put(F()),putchar('\n');
	return 0;
}

发表于 | 更新于

Link

想到了DP，也想出了状态，也想出了转移，但想不出怎么设置初始值。。

Solution

注意：平分不取整。。 f[i][0/1][0/1]f[i][0/1][0/1]表示第ii个和第i+1i+1个人分别选他左/右的食物，能否让前ii个人满意。 转移就很显然了。 然而因为是个环，初始状态怎么设置？ 没有办法，只好取Orz Claris大神，被深深折服了： 依次枚举f[1][0/1][0/1]f[1][0/1][0/1]每一维状态成立，DP完之后看能否满足 这就类似反证法的思路了吧。。假设结论成立，推矛盾。感觉非常地厉害！ 我在实现的时候把第n+1n+1个当成第11个，这样只要DP完了，看是否f[n+1][S]==1f[n+1][S]==1即可。

Tips

这种假设成立，带进去跑的做法比较厉害啊，，有点像 的感觉啊，又有点二分答案的感觉啊。。。 好吧，虽说这种枚举答案的做法也不是很少见，但我还是第一次见到放在这一类问题里面。可以记住这个脑洞啊

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
#include "lucida"
const int MAXN=1000000+11;
bool f[MAXN][4];
int c[MAXN],n,pre[MAXN][4],last;
bool DP(int s) {
	memset(f,0,sizeof(f));
	memset(pre,0,sizeof(pre));
	f[1][s]=1;c[n+1]=c[1],c[n+2]=c[2];
	for(int i=2;i<=n+1;++i)
		for(int cs=0;cs<4;++cs)
			for(int ps=0;!f[i][cs] && ps<4;++ps)
				if(f[i-1][ps] && ((ps&1)==(cs>>1&1))) {
					int lchs=(ps>>1&1),chs=(ps&1),rchs=(cs&1),valc,valo;
					if(chs==1) {
						valc=rchs==0?c[i+1]:c[i+1]*2;
						valo=lchs==1?c[i]:c[i]*2;
					} else {
						valc=lchs==1?c[i]:c[i]*2;
						valo=rchs==0?c[i+1]:c[i+1]*2;
					}
					f[i][cs]=valc>=valo;
					pre[i][cs]=ps;
				}
	last=pre[n+1][s];
	return f[n+1][s];
}
int main() {
//	freopen("input","r",stdin);
	is>>n;
	for(int i=1;i<=n;++i)
		is>>c[i];
	bool nie=1;
	for(int s=0;s<4;++s)
		if(DP(s)) {
			nie=0;
			break;
		}
	if(nie)
		os<<"NIE"<<'\n';
	else {
		static int seq[MAXN];
		for(int i=n;i>=1;--i) {
			seq[i]=(last>>1&1);
			last=pre[i][last];
		}
		for(int i=1;i<=n;++i) { 
			seq[i]=seq[i]==0?i:(i==n?1:i+1);
			os<<seq[i]<<(i==n?'\n':' ');
		}
	}
	return 0;
}

发表于 | 更新于

Link

好吧，又是神题。。

Solution

第一步想到了就做出了大半了 设前ii个字符中，有b[i]b[i]个'B'，c[i]c[i]个'C'，s[i]s[i]个'S' 那么只要有位置jj， , , ，就可以用i−ji-j更新答案了 把变量分离出来，得到三元组 ⟨b[i]−c[i],b[i]−s[i],c[i]−s[i]⟩\langle b[i]-c[i],b[i]-s[i],c[i]-s[i]\rangle 只要保证两个位置的三元组都不相等，就可以了。 第一维排序，第二维树状数组，树状数组维护第三维和位置。 具体说，第一维相同的一起转移，在第二维的树状数组里面维护位置的最大次大和最小次小值，且最值和次值的第三维必须不同，这样就可以查询了。

Tips

对于可以用前缀和维护的量，用上前缀和可能会有奇效

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
105
106
107
108
109
110
111
#include "lucida"

using std::max;
using std::sort;
using std::pair;
using std::make_pair;
const int MAXN=1000000+11,INF=0x1f1f1f1f;
namespace _Bit_ {
	const int BIT_L=1,BIT_R=-1;
	inline int lowbit(const int &x) {
		return x & -x;
	}
	template <int d> struct Bit {
		int maxv[MAXN<<1][2],minv[MAXN<<1][2],maxi[MAXN<<1],mini[MAXN<<1];
		int n;
		Bit(){}
		Bit(int n):n(n){
			for(int i=1;i<=n;++i) {
				maxv[i][0]=maxv[i][1]=-INF;
				minv[i][0]=minv[i][1]=INF;
			}
		}
		void Modify(int pos,pair<int,int> v) {
			for(;pos && pos<=n;pos+=d*lowbit(pos)) {
				if(v.first>maxv[pos][0]) {
					if(v.second!=maxi[pos])
						maxv[pos][1]=maxv[pos][0];
					maxv[pos][0]=v.first;
					maxi[pos]=v.second;
				} else if(v.first>maxv[pos][1] && v.second!=maxi[pos])
					maxv[pos][1]=v.first;
				if(v.first<minv[pos][0]) {
					if(v.second!=mini[pos])
						minv[pos][1]=minv[pos][0];
					minv[pos][0]=v.first;
					mini[pos]=v.second;
				} else if(v.first<minv[pos][1] && v.second!=mini[pos])
					minv[pos][1]=v.first;
			}
		}
		pair<int,int> Query(int pos,int diff) {
			pair<int,int> res=make_pair(-INF,INF);
			for(;pos && pos<=n;pos-=d*lowbit(pos)) {
				if(maxi[pos]!=diff)
					chkmx(res.first,maxv[pos][0]);
				else
					chkmx(res.first,maxv[pos][1]);
				if(mini[pos]!=diff)
					chkmn(res.second,minv[pos][0]);
				else
					chkmn(res.second,minv[pos][1]);
			}
			return res;
		}
	};
	Bit<BIT_L> pf;Bit<BIT_R> sf;
}using namespace _Bit_;
struct Triple {
	int a,b,c,id;
	Triple(){}
	Triple(int a,int b,int c,int id):a(a),b(b),c(c),id(id){}
	bool operator <(const Triple &x) const {
		return a<x.a;
	}
}node[MAXN];
int main() {
//	freopen("input","r",stdin);
	static char s[MAXN];
	int n;is>>n;
	is>>(s+1);
	int Ans=0;
	int pref[3]={0,0,0};
	for(int i=1,L=0;i<=n;++i) {
		L=(s[i]==s[i-1]?L+1:1);
		chkmx(Ans,L);
		int idx=(s[i]=='B'?0:(s[i]=='C'?1:2));
		pref[idx]++;
		new(&node[i]) Triple(pref[0]-pref[1]+n+1,pref[0]-pref[2]+n+1,pref[1]-pref[2]+n+1,i);
	}
	//因为有0，所以全都偏移了1
	//因为有负数 所以又偏移了n
	int nc=n+1;new(&node[nc]) Triple(n+1,n+1,n+1,0);
	sort(node+1,node+1+nc);
	new (&pf) Bit<BIT_L>((n<<1)+2);
	new (&sf) Bit<BIT_R>((n<<1)+2);
	
	/*
	for(int i=1;i<=nc;++i) {
		#define ir(x) (1<=x && x<=(2*n+1))
		assert(ir(node[i].a));
		assert(ir(node[i].b));
		assert(ir(node[i].c));
	}*/

	for(int l=1,r;l<=nc;l=r+1) {
		for(r=l;node[l].a==node[r+1].a;++r);
		for(int p=l;p<=r;++p) {
			pair<int,int> res;
			res=pf.Query(node[p].b-1,node[p].c);
			chkmx(Ans,max(res.first-node[p].id,node[p].id-res.second));
			res=sf.Query(node[p].b+1,node[p].c);
			chkmx(Ans,max(res.first-node[p].id,node[p].id-res.second));
		}
		for(int p=l;p<=r;++p) {
			pf.Modify(node[p].b,make_pair(node[p].id,node[p].c));
			sf.Modify(node[p].b,make_pair(node[p].id,node[p].c));
		}
	}
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

Link

Solution

就是模拟。。但是居然被细节坑了 Q：这题能有什么细节 A：I am too simple

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
#include "lucida"
const int MAXN=1000+11;
int n,m,a,b;
bool map[MAXN][MAXN],stp[MAXN][MAXN];
bool inside(int x,int y) {
	return 1<=x && x<=n && 1<=y && y<=m;
}
struct Point {
	int x,y;
}mo[MAXN*MAXN];int mc;
bool fit(int x,int y) {
	for(int iter=1;iter<=mc;++iter)
	{
		int i=mo[iter].x,j=mo[iter].y;
		if(!inside(x+i-1,y+j-1) || !map[x+i-1][y+j-1])
			return 0;
		map[x+i-1][y+j-1]=0;
	}
	return 1;
}
bool Work() {
	static char buf[MAXN];
	is>>n>>m>>a>>b;
	memset(map,0,sizeof(map));
	memset(stp,0,sizeof(stp));
	mc=0;
	bool have=0;
	for(int i=1;i<=n;++i) {
		is>>(buf+1);
		for(int j=1;j<=m;++j) { 
			map[i][j]=buf[j]=='x';
			have|=buf[j]=='x';
		}
	}
	for(int i=1;i<=a;++i) {
		is>>(buf+1);
		for(int j=1;j<=b;++j) {
			stp[i][j]=buf[j]=='x';
			if(stp[i][j]) {
				mo[++mc].x=i;
				mo[mc].y=j;
			}
		}
	}
	if(!mc && have)
		return 0;
	int fx=mo[1].x,fy=mo[1].y;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j) 
			if(map[i][j]==1 && !fit(i-fx+1,j-fy+1))
				return 0;
	return 1;
}
int main() {
//	freopen("input","r",stdin);
	int T;is>>T;
	//T=2;
	while(T--)
		os<<(Work()?"TAK":"NIE")<<'\n';
	return 0;
}

发表于 | 更新于

Link

自己又鼓捣出一个没有卵用的结论

Solution

正解： 枚举nn判断是否合法，只需要看[lx,rx][lx,rx]和[ly,ry][ly,ry]中是否都存在nn的倍数 只需要看(l−1n,rn](\dfrac {l-1}n,\dfrac rn]是不是空区间即可 一开始不明白为什么不能看[ln,rn][\dfrac ln,\dfrac rn]，发现l=11,r=15,n=10l=11,r=15,n=10就是反例

自己的没用结论 看[l,r][l,r]中有无nn的倍数，需要满足 然后就没办法了

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
#include "lucida"

using std::min;
using std::max;
void Work() {
	int lx,rx,ly,ry;
	is>>lx>>rx>>ly>>ry;
	int Ans=0;
	for(int lbd=1,rbd,endl=min(rx,ry);lbd<=endl;lbd=rbd+1) {
		rbd=min(rx/(rx/lbd),ry/(ry/lbd));
		if(lbd<=lx-1) chkmn(rbd,(lx-1)/((lx-1)/lbd));
		if(lbd<=ly-1) chkmn(rbd,(ly-1)/((ly-1)/lbd));
		if((lx-1)/lbd<rx/lbd && (ly-1)/lbd<ry/lbd)
			Ans=rbd;
	}
	os<<Ans<<'\n';
}
/*
void Vio() {
	int lx,rx,ly,ry,Ans=0;
	is>>lx>>rx>>ly>>ry;
	for(int i=1,endi=min(rx,ry);i<=endi;++i)
		if(((i-lx%i)%i)<=rx-lx && ((i-ly%i)%i)<=ry-ly)
			Ans=i;
	os<<Ans<<'\n';
}*/
int main() {
//	freopen("input","r",stdin);
	int T;is>>T;
	while(T--)
		//Vio();
		Work();
	return 0;
}

发表于 | 更新于

Link

Solution

离线，对时间离散化 然后把时间当作横坐标，维护最大最小值 用超神线段树即可

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
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
182
183
184
185
186
187
//Code by Lucida
#include<bits/stdtr1c++.h>
//#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define gets(x) scanf("%s",x)
//#define get64(x) scanf("%lld",&x)
#define put64(x) printf("%lld",x)
namespace IO
{
	template <class T>
	void get(T &x)
	{
		static int f;static char ch;
		for(f=1,ch=0;ch<'0' || ch>'9';ch=getchar()) if(ch=='-') f=-1;
		for(x=0;'0'<=ch && ch<='9';ch=getchar()) (x*=10)+=ch-'0';
		x*=f;
	}
}using IO::get;
typedef long long ll;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::swap;
using std::greater;
using std::less;
using std::unique;
using std::max;
using std::copy;
using std::sort;
const int MAXN=1e5+11,MAXQ=6e5+11;
const double inf=1e100;
struct Opt
{
	int l,r;
	bool query;
	int id,v;
}op[MAXQ+MAXN];int opc;
struct Line
{
	ll k,b;
	Line(){}Line(ll k,ll b):k(k),b(b){}
	ll operator ()(int x){return k*x+b;}
}position[MAXN];
int a[(MAXQ+MAXN)<<1];
namespace _SegTree_
{
	const int SIZE=MAXQ<<1<<2<<1;	
	struct Node
	{
		Node *son[2];Line ln;
		Node(){son[0]=son[1]=0;}
		void *operator new(size_t);
		void Append(int,int,Line);
	}*Me=(Node*)malloc(SIZE*sizeof(Node)),*Pool=Me;
	void *Node::operator new(size_t){return Me++;}
	#define template template <class Compare>
	template struct SegTree
	{
		int L,R;Node *root;
		Compare cmp;
		SegTree(int,int);
		void Build(Node*&,int,int);
		void Insert(Node*,int,int,int,int,Line);
		ll Query(Node*,int,int,int);
		void Append(Node*,int,int,Line);
		void Insert(int l,int r,Line ln)
		{
			if(l<=r)
			{
				l=lower_bound(a+L,a+R+1,l,less<int>())-(a+L-1);
				r=lower_bound(a+L,a+R+1,r,less<int>())-(a+L-1);//l?..
				Insert(root,L,R,l,r,ln);
			}
		}
		ll Query(int x)
		{
			int pos=lower_bound(a+L,a+R+1,x,less<int>())-(a+L-1);
			return Query(root,L,R,pos);
		}
	};
	template SegTree<Compare>::SegTree(int L,int R):L(L),R(R){Build(root,L,R);}
	template void SegTree<Compare>::Build(Node *&pos,int L,int R)
	{
		pos=new Node;
		if(L!=R)
		{
			int Mid=(L+R)>>1;
			Build(pos->son[0],L,Mid);
			Build(pos->son[1],Mid+1,R);
		}
	}
	template void SegTree<Compare>::Append(Node *pos,int L,int R,Line newln)
	{
		if(!pos) return;
		Line hl=pos->ln,hr=newln;
		if(!cmp(hl(a[L]),hr(a[L]))) swap(hl,hr);
		int Mid=(L+R)>>1;double x=(hr.k==hl.k)?inf:-(1.0*hr.b-hl.b)/(1.0*hr.k-hl.k);
		if(!(a[L]<=x && x<=a[R])) {pos->ln=hl;return;}
		if(x<=a[Mid]) Append(pos->son[0],L,Mid,hl),pos->ln=hr;
		else Append(pos->son[1],Mid+1,R,hr),pos->ln=hl;
	}
	template void SegTree<Compare>::Insert(Node* pos,int L,int R,int l,int r,Line newln)
	{
		if(L==l && R==r) Append(pos,L,R,newln);
		else
		{
			int Mid=(L+R)>>1;
			if(r<=Mid) Insert(pos->son[0],L,Mid,l,r,newln);
			else if(Mid+1<=l) Insert(pos->son[1],Mid+1,R,l,r,newln);
			else Insert(pos->son[0],L,Mid,l,Mid,newln),Insert(pos->son[1],Mid+1,R,Mid+1,r,newln);
		}
	}
	template ll SegTree<Compare>::Query(Node *pos,int L,int R,int goal)
	{
		if(L==R) return pos->ln(a[goal]);
		else
		{
			int Mid=(L+R)>>1;ll temp,res=pos->ln(a[goal]);
			if(goal<=Mid) temp=Query(pos->son[0],L,Mid,goal);
			else temp=Query(pos->son[1],Mid+1,R,goal);
			return cmp(res,temp)?res:temp;
		}
	}
	#undef template
}using _SegTree_::SegTree;
int main()
{
	static int pre[MAXN];
	int n,Q;get(n),get(Q);
	for(int i=1;i<=n;++i)
	{
		++opc;
		get(position[i].b),position[i].k=0;
		op[opc].v=0;op[opc].l=0;op[opc].id=i;
		pre[i]=opc;
	}
	for(int i=1;i<=Q;++i)
	{
		assert(op[i].l>=op[i-1].l);

		char opt[15];++opc;
		//op[opc]=op[opc-1];
		get(op[opc].l);
		gets(opt);
		if(opt[0]=='c')
		{
			get(op[opc].id),get(op[opc].v);
			if(pre[op[opc].id])
			{
				op[pre[op[opc].id]].r=op[opc].l-1;
				pre[op[opc].id]=opc;
			}
			op[opc].query=0;
		}
		else
			op[opc].query=1;
	}
	
	int nc=0;
	for(int i=1;i<=opc;++i)
	{
		a[++nc]=op[i].l;
		a[++nc]=op[i].r;
	}
	sort(a+1,a+1+nc);
	nc=unique(a+1,a+1+nc)-a-1;
	for(int i=1;i<=n;++i) op[pre[i]].r=a[nc];
	SegTree<greater<ll> > segmx(1,nc);
	SegTree<less<ll> > segmn(1,nc);
	for(int i=1;i<=opc;++i)
	{
		if(!op[i].query)
		{
			position[op[i].id]=Line(op[i].v,position[op[i].id](op[i].l)-(ll)op[i].l*op[i].v);
			segmx.Insert(op[i].l,op[i].r,position[op[i].id]);
			segmn.Insert(op[i].l,op[i].r,position[op[i].id]);
		}
	}
	for(int i=1;i<=opc;++i)
	{
		if(op[i].query)
		{
			ll Ans=max(segmx.Query(op[i].l),-segmn.Query(op[i].l));
			put64(Ans),putchar('\n');
		}
	}
	return 0;
}

发表于 | 更新于

Link

Solution

可以看出，每个点的子树怎么装最快是一个独立的子问题。 所以现在考虑的就是在每个根节点如何安排每个子树的安装顺序 每个子树uu最后完成的时间t[u]t[u]，是进入的时间+f[u]+f[u]。 而整个子树完成的时间，是max{t[u]}\max\{t[u]\} 子树进入的时间是遍历完之前所有子树的时间 一开始的想法是： 如果本身装机时间就长，还要等别的子树，那肯定最后是最慢的？ 于是就按照装机时间排序贪心，WA。 考虑一种极端情况：有一个超大的子树，每个点安装的时间都是00，但是遍历很慢，凭此rank1。如果先安装了这个，别的就白等了。 于是启发采用新的策略：按照f[u]−(sz[u]−1)∗2f[u]-(sz[u]-1)*2排序，也就是子树安装的时间除去遍历的时间。这样就对了。 具体地说 有一个pairpair的序列s[]s[]，每个s[i]s[i]对答案的贡献是s[i].first+∑j<is[j].seconds[i].first+\sum\limits_{j< i} s[j].second 则Ans=max{s[i].first+∑j<is[j].second}Ans=\max\{s[i].first+\sum\limits_{j< i} s[j].second\} 设最大值在点uu取得，设uu与vv交换可以使得最大值在vv取得且变小 s[u].first+∑s[u′∣u′<u].seconds[u].first+\sum s[u'|u' < u].second 感觉不靠谱。。。能否给个证明。。

Tips

如果可能的话，要科学地贪心。 想一些具体的边界情况试着叉掉做法。

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
#include "lucida"
using std::pair;
using std::make_pair;
using std::sort;
using std::greater;
using std::max;
const int MAXN=500000+11;
struct Edge {
	int to;
	Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Pool=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*Me=Pool;
		return Me++;
	}
}*id[MAXN];
void Adde(int f,int t) {
	id[f]=new Edge(t,id[f]);
	id[t]=new Edge(f,id[t]);
}
int c[MAXN],sz[MAXN];
int64 f[MAXN];
int64 DP(int pos,int fa) {
	sz[pos]=1;
	f[pos]=c[pos];
	for(Edge *e=id[pos];e;e=e->pre)
		if(e->to!=fa) {
			int u=e->to;
			DP(u,pos);
			sz[pos]+=sz[u];
		}
	static pair<int64,int> son[MAXN];
	int sc=0;
	for(Edge *e=id[pos];e;e=e->pre)
		if(e->to!=fa) {
			int u=e->to;
			son[++sc]=make_pair(f[u]-(sz[u]-1)*2,(sz[u]-1)*2);
		}
	sort(son+1,son+1+sc,greater<pair<int64,int> >());
	int64 res=0,sum=1; 
	for(int i=1;i<=sc;++i) {
		chkmx(res,sum+son[i].first+son[i].second);
		sum+=son[i].second+2;
	}
	chkmx(f[pos],res);
	return f[pos];
}

int main() {
	freopen("input","r",stdin);
	int n;is>>n;
	for(int i=1;i<=n;++i)
		is>>c[i];
	for(int i=1;i<=n-1;++i) {
		int x,y;
		is>>x>>y;
		Adde(x,y);
	}
	int64 Ans=max((int64)c[1]+(n-1)*2,DP(1,0));
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

Link

Solution

Tips

如果要把内存分配处理的精细一些还是有点繁的(当然仅仅对我这种juruo) g[]g[]要开两倍。。(好吧我知道地球人都知道但是我刚知道。。)

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
105
106
107
108
#include "lucida"
using std::pair;
using std::make_pair;
const int MAXN=100000+11;
struct Edge {
	int to,v;
	Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void *operator new(size_t) {
		static Edge *Pool=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*Me=Pool;
		return Me++;
	}
};
struct Graph {
	Edge *head;
	void App(int to) {
		head=new Edge(to,head);
	}
	operator Edge*(){
		return head;
	}
}G[MAXN];
int64 *f[MAXN],*g[MAXN];
pair<int64*,int64*> alloc(size_t cnt) {
	//os<<'['<<cnt<<"]\n";

	static const int SIZE=MAXN<<2;
	static int64 *Pool=new int64[SIZE](),*Me=Pool,*re;
	return re=Me,Me+=cnt,make_pair(re,Me-1);
	//+=cnt?
}
int prefer[MAXN],fa[MAXN],chd[MAXN]={-1};
void DFS(int pos) {
	for(Edge *e=G[pos];e;e=e->pre)
		if(e->to!=fa[pos]) {
			int u=e->to;
			fa[u]=pos;
			DFS(u);
			if(chd[u]>chd[prefer[pos]])
				prefer[pos]=u;
		}
	chd[pos]=chd[prefer[pos]]+1;
}
void Alloc(int pos,int len) {

//	os<<pos<<':'<<len<<'\n';

	if(!prefer[pos]) {
		f[pos]=alloc(len).second;
		g[pos]=alloc(len<<1).first;//没有开两倍
	} else {
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=fa[pos]) {
				int u=e->to;
				Alloc(u,(u==prefer[pos])*len+1);
			}
	}
}
int64 DP(int pos) { 
	int64 res=0;
	if(!prefer[pos]) {
		f[pos][0]=1;
	} else {
		int u;
		for(Edge *e=G[pos];e;e=e->pre)
			if((u=e->to)!=fa[pos]) 
				res+=DP(u);
		u=prefer[pos];
		f[pos]=f[u]-1;
		g[pos]=g[u]+1;
		f[pos][0]=1;
		res+=g[pos][0];
		for(Edge *e=G[pos];e;e=e->pre)
			if((u=e->to)!=fa[pos] && u!=prefer[pos]) {
				for(int d=0;d<=chd[u]+1;++d) {
					if(d>=1)
						res+=g[pos][d]*f[u][d-1];
					if(d<=chd[u]-1)
						res+=f[pos][d]*g[u][d+1];
				}
				for(int d=0;d<=chd[u]+1;++d) {
					if(d>=1) {
						g[pos][d]+=f[pos][d]*f[u][d-1];
						f[pos][d]+=f[u][d-1];
					}
					if(d<=chd[u]-1)
						g[pos][d]+=g[u][d+1];
				}
			}
	}
	//os<<pos<<':'<<res<<'\n';
	return res;
}
int main() {
	//freopen("input","r",stdin);
	int n;is>>n;
	for(int i=1;i<=n-1;++i) {
		int x,y;
		is>>x>>y;
		G[x].App(y);
		G[y].App(x);
	}
	DFS(1);
	Alloc(1,1);
	int64 Ans=DP(1);
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

Link

Solution

先计算得到数列 根据字典序最小，肯定要先贪心地取最小的 取了一个数字之后，会增加一个限制条件：路径必须在它的左上方和右下方 所以不停地取合法的，并不停地把条件取交集，直到取满为止

Tips

字典序可以优先考虑贪心(SDOI的最小字典序割)

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
//Code by Lucida
#include<bits/stdtr1c++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
typedef long long ll;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::swap;
using std::find;
using std::merge;
using std::sort;

const int MAXN=5000+1;
int T[MAXN*MAXN],ref[MAXN*MAXN],Ans[MAXN<<1],lbd[MAXN],rbd[MAXN];
struct Random
{
	ll seed;int a,b,c,d;
	Random(ll seed,int a,int b,int c,int d):seed(seed),a(a),b(b),c(c),d(d){}
	int next() {return seed=(seed*(seed*a+b)+c)%d;}
};
int main()
{
	int x,a,b,c,d,n,m,q,sz;
	get(x),get(a),get(b),get(c),get(d),get(n),get(m),get(q);
	Random random(x,a,b,c,d);
	sz=n*m;
	for(int i=1;i<=sz;++i) T[i]=i;
	for(int i=1;i<=sz;++i) swap(T[i],T[random.next()%i+1]);
	for(int i=1;i<=q;++i) 
	{
		int u,v;get(u),get(v);
		swap(T[u],T[v]);
	}
	for(int i=1;i<=sz;++i) ref[T[i]]=i;
	for(int i=1;i<=n;++i) rbd[i]=m,lbd[i]=1;
	int ac=0,goal=n+m-1;
	for(int i=1;i<=sz && ac!=goal;++i)
	{
		int pos=ref[i],x=(pos-1)/m+1,y=(pos-1)%m+1;
		if(lbd[x]<=y && y<=rbd[x])
		{
			Ans[++ac]=i;
			for(int row=1;row<x;++row) chkmn(rbd[row],y);
			for(int row=x+1;row<=n;++row) chkmx(lbd[row],y);
		}
	}
	for(int i=1;i<=ac;++i) put(Ans[i]),putchar(i==ac?'\n':' ');
	return 0;
}