进行一个题的乱做

qtanglani 发布于

最后更新于

arc160b

我们设三元组(x,y,z)(x,y,z)中xx为最大的

设m=⌊n⌋m=\left \lfloor \sqrt{n} \right \rfloor

当x≤mx \le m时，x,y,zx,y,z三个值可以随便选，这时答案为m3m^{3}

当x>mx>m时，y,zy,z的值都需要≤⌊nx⌋\le \left \lfloor \frac{n}{x} \right \rfloor

他们的可选数目便是⌊nx⌋2\left \lfloor \frac{n}{x} \right \rfloor^{2}，由于xx的位置有三种，所以还要乘三，⌊nx⌋2\left \lfloor \frac{n}{x} \right \rfloor^{2}可以用数论分块快速求出

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
#include<iostream>
#include<cmath>
#define int long long
using namespace std;
const int P=998244353;
void solve()
{
    int n;
    cin>>n;
    int m=sqrt(n);
    int ans=m*m%P*m%P;
    int l=m+1,r=0;
    while(r<=n&&l<=n)
    {
        r=n/(n/l);
        int now=n/l;
        ans=(ans+(r-l+1)*now%P*now%P*3%P)%P;
        l=r+1;
    }
    cout<<ans<<'\n';
}
signed main()
{
    int T;
    cin>>T;
    while(T--)
        solve();
}

arc161c

一眼此题的突破口在叶子结点，叶子结点的答案一定是他父节点想要的颜色，那么就可以先给叶子结点赋值，之后进行DFS

在DFS时，记录子节点的颜色数量：白，黑，无

一个节点的大部分贡献值都来自于子节点，除了子节点白色与黑色相等时

如果此节点想要的是白色，那么我们可以将子节点中暂时没有颜色的赋值为白色，若加上父节点还不够，那就标记−1-1

如果此节点想要的是黑色，那么我们可以将子节点中暂时没有颜色的赋值为黑色，若加上父节点还不够，那就标记−1-1

若两者相等，则此节点的颜色取决于父节点，这时我们就可以确定父节点的颜色，相反则确定不了，这就是为什么会有记录子节点无颜色的情况

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
#include<iostream>
#include<vector>
using namespace std;
const int N=200010;
vector<int> g[N];
int n;
char c[N];
char ans[N];
int V=0;
void Dfs(int u,int fa)
{
    int B=0,W=0;
    int ling=0;
    for(int it:g[u])
    {
        if(it==fa)
            continue;
        Dfs(it,u);
        B=B+(ans[it]=='B');
        W=W+(ans[it]=='W');
        ling+=(ans[it]!='B'&&ans[it]!='W');
    }
    if(c[u]=='B')
    {
        if(B+ling<W)
            V=1;
        B+=ling;
        for(int it:g[u])
        {
            if(it==fa)
                continue;
            if(ans[it]!='W'&&ans[it]!='B')
                ans[it]='B';
        }
    }
    if(c[u]=='W')
    {
        if(W+ling<B)
            V=1;
        W+=ling;
        for(int it:g[u])
        {
            if(it==fa)
                continue;
            if(ans[it]!='W'&&ans[it]!='B')
                ans[it]='W';
        }
    }
    if(B==W)
    {
        if((ans[fa]=='B'&&c[u]=='W')||(ans[fa]=='W'&&c[u]=='B'))
            V=1;
        ans[fa]=c[u];
    }
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        g[i].clear();
        ans[i]=0;
    }
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        cin>>c[i];
    for(int i=2;i<=n;i++)
        if(g[i].size()==1)
            ans[i]=c[g[i][0]];
    V=0;
    Dfs(1,0);
    if(V)
    {
        cout<<-1<<'\n';
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(ans[i]!='B'&&ans[i]!='W')
            cout<<'W';
        else
            cout<<ans[i];
    }
    cout<<'\n';
}
int main()
{
    int T;
    cin>>T;
    while(T--)
        solve();
}

arc162c

首先Bob填kk是最优的，然后每个点判断一下是否在一步以内就可以将此子树填满并且答案为kk，注意

一定要将子树填满才可以算答案

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
#include<iostream>
#include<vector>
using namespace std;
const int N=2010;
vector<int> g[N];
int n,k;
int w[N];
int vis[N];
int res;
void Dfs(int u)
{
    if(w[u]==-1)
        res++;
    else
        vis[w[u]]=1;
    for(int it:g[u])
        Dfs(it);
}
void solve()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        g[i].clear();
    for(int i=2;i<=n;i++)
    {
        int x;
        cin>>x;
        g[x].push_back(i);
    }
    for(int i=1;i<=n;i++)
        cin>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
            vis[j]=0;
        res=0;
        Dfs(i);
        if(res>=2)
            continue;
        int now=0;
        while(vis[now])
            now++;
        if(now==k)
        {
            cout<<"Alice"<<'\n';
            return;
        }
        if(res)
            now++;
        while(vis[now])
            now++;
        if(now==k)
        {
            cout<<"Alice"<<'\n';
            return;
        }
    }
    cout<<"Bob"<<'\n';
}
int main()
{
    int T;
    cin>>T;
    while(T--)
        solve();
}
/*
1
7 3
1 1 1 2 2 4 
1 -1 -1 0 1 -1 1 

1
7 2
1 1 3 4 5 1 
0 1 -1 -1 -1 -1 3 
*/

P4503

此题是24/6/23 wpy与我在随题的时候做到的，刚看到此题时，wpy立马给了两个暴力，他就去打了，然后，他查看了题解，然后发现他 unsigned long long 写成了 int

下面介绍介绍wpy所给出的暴力

1
亻尔 女马

以上是 wpy 给出的评价

考虑枚举每一位的64个字符，用mapmap 维护的话需要一个loglog 显然复杂度过不去

我们考虑维护每个串的前后缀，当有一位不同时，就将这位暂时删去，比较剩下的位，这样用mapmap维护的话复杂度O(nmlogn)O(nmlogn) 但这样过不了，我们将每一位去掉后所剩的串排序，然后顺序遍历就可以了

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
#include<iostream>
#include<map>
#include<algorithm>
#define int long long
using namespace std;
const int N=30010;
const int L=210;
const int base=13331;
const int base1=23;
const int base2=17;
const int P=998244353;
int h1[N][L],h2[N][L];
int n,m,OvO;
string s[N];
int lit[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>OvO;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]='0'+s[i];
    }
    for(int i=1;i<=n;i++)
    {
        h1[i][0]=1;
        for(int j=1;j<=m;j++)
            h1[i][j]=(h1[i][j-1]*149+(int)(s[i][j]));
        h2[i][m+1]=1;
        for(int j=m;j>=1;j--)
            h2[i][j]=(h2[i][j+1]*137+(int)(s[i][j]));
    }
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
            lit[j]=(h1[j][i-1]*233+h2[j][i+1]*213);
        sort(lit+1,lit+n+1);
        int now=1;
        for(int j=2;j<=n;j++)
        {
            if(lit[j]==lit[j-1])
            {
                ans+=now;
                now++;
            }
            else
                now=1;
        }
    }
    cout<<ans;
}

arc162d

前置知识：Prufer序列

根据Prufer序列可得，本质不同的无根树的个数为
(n−2)!∏i=1n(di−1)!\frac{(n-2)!}{\prod_{i=1}^{n} (d_{i}-1)!}

did_{i}是ii号节点的度数，在下面，我们把它定义为一个点的出度

当一个点是一号节点或叶子结点时，他们所作的贡献是所有
树的数量，直接加上上面的式子就好

其他点时，我们可以分两部分考虑，一部分是子树内部，另一部分是子树外部

在子树内部时，设此子树的根为 xx ，他的子树内所有的点都 $\in \left [ x+1,n\right ] $ 这样才会给xx产生11的贡献，同样，在子树内部既有选择的方案，又有排列的方案，排列的方案好说，就是上面的式子算一遍，假设我们选择了kk个，分别为x,t1,t2…tk−1x,t_{1},t_{2} \dots t_{k-1} 那么这个子树的排列数就是

(k−2)!(dx−1)!∏i∈t(di)!\frac{(k-2)!}{(d_{x}-1)! \prod_{i \in t }(d_{i})!}

太难看了

dx(k−2)!(dx)!∏i∈t(di)!\frac{d_{x}(k-2)!}{(d_{x})! \prod_{i \in t }(d_{i})!}

至于选择的方案，我们要在这个子树内选择所有点的出度和为k−1k-1，也就是能构成一棵树，我们可以使用动态规划（想不到一点）

我们定义fi,j,kf_{i,j,k}的含义为选择了jj个∈[i,n]\in[i,n]的节点，且did_{i}的和为kk的方案数

1
2
3
4
5
6
7
8
9
f[n+1][0][0]=1;
    for(int i=n;i>=1;i--)
        for(int j=0;j<=n-i+1;j++)
            for(int k=0;k<n;k++)
            {
                f[i][j][k]=f[i+1][j][k];
                if(j>0&&k-w[i]>=0)
                    f[i][j][k]=(f[i][j][k]+f[i+1][j-1][k-w[i]])%P;
            }

（会不了一点）

注意，以xx为根且选了kk个点的方案数是fx+1,k−1,k−1−dxf_{x+1,k-1,k-1-d_{x}}

这样整个子树内部的方案数算出来了

dx(k−2)!(dx)!∏i∈t(di)!×fx+1,k−1,k−1−dx\frac{d_{x}(k-2)!}{(d_{x})! \prod_{i \in t }(d_{i})!} \times f_{x+1,k-1,k-1-d_{x}}

至于子树外部的方案数，我们可以把以xx节点的子树当做一个子节点，然后再利用公式

d1(n−k+1−2)!∏i∉t(di)!\frac{d_{1}(n-k+1-2)!}{\prod_{i \notin t} (d_{i})!}

太难看了

d1(n−k−1)!∏i∉t,i≠x(di)!\frac{d_{1}(n-k-1)!}{\prod_{i \notin t,i\not=x} (d_{i})!}

所以以点xx为根的子树内选了kk个点的合法方案数就是以上两个式子相乘

d1dx(k−2)!(n−k−1)!∏i=1n(di)!×fx+1,k−1,k−1−dx\frac{d_{1}d_{x}(k-2)!(n-k-1)!}{\prod_{i=1}^{n} (d_{i})!} \times f_{x+1,k-1,k-1-d_{x}}

枚举x,kx,k即可求出答案

CF696E

由于每个树节点上都有多个编号的点，于是我们开一个
vector c[N]来存储,然后now[i]表示在第ii个树节点现在该删哪个点了，之后用树剖来求出删掉节点所属的树节点xx，然后将该树结点的c[x][now[x]]加入vector ans，最后输出即可，注意在查找时记一个最大值，如果还是该最大值不变的话那就证明在此路径上没有可以能删去的节点

每次操作一循环kk次，当最大值不变时退出，每一次都单点修改最小值所在的树节点的权值，然后操作二就是普通的子树加

个人感觉主函数里的东西最难写

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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include<iostream>
#include<algorithm>
#include<vector>
#define int long long

using namespace std;
const int N=100010;
vector<int> g[N];
int now[N];
vector<int> c[N];
struct info
{
	int num,val;
};
struct node
{
	int tag;
	info v;
}tr[N*4];
int n,m,q,w[N];
int Tid[N],idT[N],deep[N],top[N],siz[N],fa[N],son[N],cnt;
void Dfs1(int u,int f)
{
	deep[u]=deep[f]+1;
	fa[u]=f;
	siz[u]=1;
	for(int it:g[u])
	{
		if(it==f)
			continue;
		Dfs1(it,u);
		siz[u]+=siz[it];
		if(siz[it]>siz[son[u]])
			son[u]=it;
	}
}
void Dfs2(int u,int T)
{
	Tid[u]=++cnt;
	idT[cnt]=u;
	top[u]=T;
	if(son[u])
		Dfs2(son[u],T);
	for(int it:g[u])
	{
		if(it==fa[u]||it==son[u])
			continue;
		Dfs2(it,it);
	}
}
info merge(info a,info b)
{
	info c;
	if(a.val<b.val)
		c=a;
	if(b.val<a.val)
		c=b;
	if(a.val==b.val)
	{
		if(a.num<b.num)
			c=a;
		else
			c=b;
	}
	return c;
}
void update(int x)
{
	tr[x].v=merge(tr[x*2].v,tr[x*2+1].v);
}
void built(int x,int l,int r)
{
	if(l==r)
	{
		tr[x].v.val=c[idT[l]][0];
		tr[x].v.num=idT[l];
		return;
	}
	int mid=(l+r)/2;
	built(x*2,l,mid);
	built(x*2+1,mid+1,r);
	update(x);
}
void maketag(int x,int k,int L,int R)
{
	tr[x].tag+=k;
	tr[x].v.val+=k;
}
void pushdown(int x,int L,int R)
{
	if(L==R)
		return;
	int mid=(L+R)/2;
	maketag(x*2,tr[x].tag,L,mid);
	maketag(x*2+1,tr[x].tag,mid+1,R);
	tr[x].tag=0;
}
void modify(int x,int l,int r,int k,int L,int R)
{
	pushdown(x,L,R);
	if(l==L&&r==R)
	{
		maketag(x,k,L,R);
		return;
	}
	int mid=(L+R)/2;
	if(r<=mid)
		modify(x*2,l,r,k,L,mid);
	else if(l>=mid+1)
		modify(x*2+1,l,r,k,mid+1,R);
	else
	{
		modify(x*2,l,mid,k,L,mid);
		modify(x*2+1,mid+1,r,k,mid+1,R);
	}
	update(x);
}
info find(int x,int l,int r,int L,int R)
{
	pushdown(x,L,R);
	if(l==L&&r==R)
		return tr[x].v;
	int mid=(L+R)/2;
	if(r<=mid)
		return find(x*2,l,r,L,mid);
	else if(l>=mid+1)
		return find (x*2+1,l,r,mid+1,R);
	return merge(find(x*2,l,mid,L,mid),find(x*2+1,mid+1,r,mid+1,R));
}
pair<int,int> find_T(int u,int v)
{
	pair<int,int> ans={1e17+10,1e17+10};//num,val
	while(top[u]!=top[v])
	{
		if(deep[top[u]]>deep[top[v]])
			swap(u,v);
		info OvO=find(1,Tid[top[v]],Tid[v],1,n);
		if(OvO.val==ans.second)
		{
			if(OvO.num<ans.first)
				ans={OvO.num,OvO.val};
		}
		else
		{
			if(OvO.val<ans.second)
				ans={OvO.num,OvO.val};
		}
		v=fa[top[v]];
	}
	if(deep[u]>deep[v])
		swap(u,v);
	info OvO=find(1,Tid[u],Tid[v],1,n);
	if(OvO.val==ans.second)
	{
		if(OvO.num<ans.first)
			ans={OvO.num,OvO.val};
	}
	else
	{
		if(OvO.val<ans.second)
			ans={OvO.num,OvO.val};
	}
	return ans;
}
signed main()
{
	cin>>n>>m>>q;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	Dfs1(1,0);
	Dfs2(1,1);
	for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;
		c[x].push_back(i);
		w[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		sort(c[i].begin(),c[i].end());
		c[i].push_back(1e17+10);
	}
	built(1,1,n);
	for(int i=1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int u,v,k;
			cin>>u>>v>>k;
			vector<int> ans;
			for(int j=1;j<=k;j++)
			{
				pair<int,int> x=find_T(u,v);
				if(x.first==1e17+10||c[x.first][now[x.first]]==1e17+10)
					break;
				ans.push_back(c[x.first][now[x.first]]);
				now[x.first]++;
				modify(1,Tid[x.first],Tid[x.first],c[x.first][now[x.first]]-c[x.first][now[x.first]-1],1,n);
			}
			cout<<ans.size()<<" ";
			for(int it:ans)
				cout<<it<<" ";
			cout<<'\n';
		}
		else
		{
			int u,k;
			cin>>u>>k;
			modify(1,Tid[u],Tid[u]+siz[u]-1,k,1,n);
		}
	}
}

P3168

此题区间修改单点查询，可以利用到差分数组，而可持久化线段树有类似前缀和的东西，具体来说

当一个区间修改时，我们用vector g[N]

g[l].push_back(k)

g[r+1].push_back(-k)

然后统一处理完后再从头到尾扫一遍，首先要将前一个节点拉过来

rt[i]=clone(rt[i-1]);

然后再扫g[i]，进行修改，注意当g[i][j]为负数时，由于我们使用的是权值线段树，所以说修改的位置是-g[i][j]。最后在线段树上进行二分，输出答案即可

此题可以不用离散化

P2839

此题可以不用离散化

在区间[a,b][a,b]中选取左端点，在区间[c,d][c,d]中选取右端点，求这个区间内最大中位数。

看到中位数，可以考虑二分，将比midmid大的的改成11，将比midmid小的改成−1-1求然后进行区间求和，若sum≥0sum\ge 0，则midmid还能再大。

此题让中位数最大，那可以转化为让区间和尽可能大，那我们就可以选取[a,b][a,b]的最大后缀和，[b+1,c−1][b+1,c-1]的和，[c,d][c,d]的最大前缀和，考虑到每次二分都修改时间复杂度太高，又发现将数组排好序后，修改是单调的，用可持久化线段树，以数组下标当作线段树的值域，那么我们就能拥有O(nlogn)O(nlogn)的好复杂度。

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
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
const int N=200100;
struct node
{
    int pre,suf,sum,len,ans;
}tr[N*40];
int ls[N*40],rs[N*40],yet[N*40];
int rt[N*40];
int a[N],b[N];
int n,q;
int cnt;
map<int,vector<int> > mp;
int now;
int l1,r1,l2,r2;
int Q[4];
node merge(node a,node b)
{
    node c;
    c.sum=a.sum+b.sum;
	c.pre=max(a.pre,a.sum+b.pre);
	c.suf=max(b.suf,b.sum+a.suf);
    return c;
}
void update(int x)
{
    tr[x]=merge(tr[ls[x]],tr[rs[x]]);
}
int built(int x,int l,int r)
{
    x=++cnt;
    if(l==r)
    {
        tr[x].pre=tr[x].suf=tr[x].sum=1;
        return x;
    }
    int mid=(l+r)/2;
    ls[x]=built(ls[x],l,mid);
    rs[x]=built(rs[x],mid+1,r);
    update(x);
    return x;
}
int clone(int x)
{
    cnt++;
    tr[cnt]=tr[x];
	ls[cnt]=ls[x];
	rs[cnt]=rs[x];
	yet[cnt]=yet[x];
    return cnt;
}
int modify(int x,int k,int l,int r)
{
    if(now!=yet[x])
    {
        x=clone(x);
        yet[x]=now;
    }
    if(l==r)
    {
        tr[x].pre=tr[x].suf=tr[x].sum=-1;
        return x;
    }
    int mid=(l+r)/2;
    if(k<=mid)
        ls[x]=modify(ls[x],k,l,mid);
    else
        rs[x]=modify(rs[x],k,mid+1,r);
    update(x);
    return x;
}
node find(int x,int l,int r,int L,int R)
{
	// if(l>r)
	// 	throw 0;
    // cerr<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<x<<'\n';
    // if(x==0)
    // {

	// }
    if(l==L&&r==R)
        return tr[x];
    int mid=(L+R)/2;
    if(r<=mid)
        return find(ls[x],l,r,L,mid);
    if(l>=mid+1)
        return find(rs[x],l,r,mid+1,R);
    return merge(find(ls[x],l,mid,L,mid),find(rs[x],mid+1,r,mid+1,R));
}
int OvO;
int check(int mid)
{
    int sum=0;
	if(l1>r1||l2>r2)
		throw 0;
    if(r1+1<=l2-1)
        sum=find(rt[mid],r1+1,l2-1,1,n).sum;
    sum=sum+find(rt[mid],l1,r1,1,n).suf;
    sum=sum+find(rt[mid],l2,r2,1,n).pre;
    if(sum>=0)
        return 1;
    return 0;
}
void F(int x,int l,int r)
{
	cout<<l<<" "<<r<<" "<<x<<'\n';
	if(l==r)
		return;
	int mid=(l+r)/2;
	F(ls[x],l,mid);
	F(rs[x],mid+1,r);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
        mp[a[i]].push_back(i);
    }
    sort(b+1,b+n+1);
    int len=unique(b+1,b+n+1)-b-1;
    rt[0]=built(rt[0],1,n);
    for(int i=1;i<=len;i++)
    {
        rt[i]=clone(rt[i-1]);
        yet[rt[i]]=i;
        now=i;
        for(auto it:mp[b[i-1]])
			rt[i]=modify(rt[i],it,1,n);
    }
    cin>>q;
    while(q--)
    {
        cin>>l1>>r1>>l2>>r2;
        l1=(l1+OvO)%n+1;
        r2=(r2+OvO)%n+1;
        r1=(r1+OvO)%n+1;
        l2=(l2+OvO)%n+1;
		Q[0]=l1;
		Q[1]=r1;
		Q[2]=l2;
		Q[3]=r2;
		sort(Q,Q+4);
		l1=Q[0];
		r1=Q[1];
		l2=Q[2];
		r2=Q[3];
        int l=1,r=len;
        while(l<r)
        {
            int mid=(l+r+1)/2;
            if(check(mid))
                l=mid;
            else
                r=mid-1;
        }
        OvO=b[l];
        cout<<OvO<<'\n';
    }
	// F(rt[1],1,n);
    // find(rt[3],3,4,1,n);
}
/*
5
206452321
206452321
206452321
206452321
206452321
1
3 1 0 2
2 3 1 4
*/

既然能用可持久化线段树，那区间最大前缀后缀也一样能像普通线段树一样维护，具体而言

开一个map<int,vector<int> > mp

它的作用是将每个数存下它所对应的位置。

将输入的数组排好序，去重，先建好一颗根为rt[0]的树，每个位置初始为11，然后

1
2
for(auto it:mp[b[i-1]])
	rt[i]=modify(rt[i],it,1,n);

每次修改改成−1-1,最后再像普通线段树那样维护就好了。

注意，若是单独写了一个mergemerge函数，一定要注意好xx的左儿子右儿子要成功更新

7月3日DP

CF41D

起初，我定义的状态为fi,j,kf_{i,j,k}为走到格子i,ji,j的是kk的倍数的最大值，发现我写的转移复杂度并不优秀，且在输出路径的时候可能中间会断掉而无法很好的判断

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
for(int i=n;i>=1;i--)
{
    for(int j=1;j<=m;j++)
    {
        for(int k=1;k<=100;k++)
        {
            for(int l=1;l<=100;l++)
            {
                if((f[i+1][j-1][l]+w[i][j])%k==0)
                {
                    if(f[i][j][k]<f[i+1][j-1][l]+w[i][j])
                    {
                        lead[i][j][k]={l,'L'};
                        f[i][j][k]=f[i+1][j-1][l]+w[i][j];
                    }
                }
                if((f[i+1][j+1][l]+w[i][j])%k==0)
                {
                    if(f[i][j][k]<f[i+1][j+1][l]+w[i][j])
                    {
                        lead[i][j][k]={l,'R'};
                        f[i][j][k]=f[i+1][j+1][l]+w[i][j];
                    }
                }
            }
        }
    }
}

这坨跟史一样，
之后看了题解，类似于一个背包，他是定义是否能到达和为kk

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for(int i=n;i>=1;i--)///////////////////////////////////////////////
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=w[i][j];k<=900;k++)
            {
                if(f[i+1][j-1][k-w[i][j]]!=-1)
                {
                    lead[i][j][k]={k-w[i][j],'L'};
                    f[i][j][k]=1;
                }
                if(f[i+1][j+1][k-w[i][j]]!=-1)
                {
                    lead[i][j][k]={k-w[i][j],'R'};
                    f[i][j][k]=1;
                }
            }
        }
    }

这样就简洁很多，并且时间复杂度也下来了，那么如果说他的值域还可能再大的话，这个方法应该就不适用了，那有没有更好的方法呢？

CF82D

我们发现，第i(i≥2)i(i\ge2)次选人都是选择第2i,2i+1,j2i,2i+1,j这三个人，jj是之前选的剩下的那个，那看到数据范围能跑O(n2)O(n^{2})，我们便可以这样设计状态

fi,jf_{i,j}为第ii次选，选完后剩下哪一个。每次选都有三种情况

剩下上次选的剩下的那个，剩下2i2i,剩下2i+12i+1,那转移方程就出来了

fi,j=max⁡(fi,j,fi−1,j+wj)f_{i,j}= \max (f_{i,j},f_{i-1,j}+w_{j})

fi,2i=max⁡(fi,2i,fi−1,j+w2i)f_{i,2i}=\max (f_{i,2i},f_{i-1,j}+w_{2i})

fi,2i+1=max⁡(fi,2i+1,fi−1,j+w2i+1)f_{i,2i+1}=\max (f_{i,2i+1},f_{i-1,j}+w_{2i+1})

至于方案，就在DPDP时记录一下就可以了，枚举i,ji,j即可算出答案

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
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=1010;
int f[N][N],pre[N][N];
pair<int,int> pr[N][N];
int n,w[N];
int V;
void Dfs(int x,int y)
{
    if(x==0)
        return;
    Dfs(x-1,pre[x][y]);
    cout<<pr[x][y].first<<" "<<pr[x][y].second<<'\n';
}
signed main()
{
    memset(f,0x3f,sizeof(f));
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    if(n==1)
    {
        cout<<w[1]<<'\n';
        cout<<1;
        return 0;
    }
    if(n==2)
    {
        cout<<max(w[1],w[2])<<'\n';
        cout<<1<<" "<<2;
        return 0;
    }
    if(n%2==0)
        w[++n]=0x3f3f3f3f,V=1;
    f[1][1]=max(w[2],w[3]);
    pr[1][1]={2,3};
    f[1][2]=max(w[1],w[3]);
    pr[1][2]={1,3};
    f[1][3]=max(w[1],w[2]);
    pr[1][3]={1,2};
    for(int i=2;i<=n/2;i++)
    {
        for(int j=1;j<i*2;j++)
        {
            if(f[i-1][j]+max(w[i*2],w[i*2+1])<f[i][j])
            {
                f[i][j]=f[i-1][j]+max(w[i*2],w[i*2+1]);
                pre[i][j]=j;
                pr[i][j]={i*2,i*2+1};
            }
            if(f[i][i*2]>f[i-1][j]+max(w[i*2+1],w[j]))
            {
                f[i][i*2]=f[i-1][j]+max(w[i*2+1],w[j]);
                pre[i][i*2]=j;
                pr[i][i*2]={j,i*2+1};
            }
            if(f[i][i*2+1]>f[i-1][j]+max(w[i*2],w[j]))
            {
                f[i][i*2+1]=f[i-1][j]+max(w[i*2],w[j]);
                pre[i][i*2+1]=j;
                pr[i][i*2+1]={j,i*2};
            }
        }
    }
    int maxx=1e9;
    int now=0;
    if(V)
    {
        now=n;
        maxx=f[n/2][n];
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            if(f[n/2][i]+w[i]<maxx)
            {
                maxx=f[n/2][i]+w[i];
                now=i;
            }
        }
    }
    cout<<maxx<<'\n';
    Dfs(n/2,now);
    if(!V)
        cout<<now;
}

CF222E

有简单的转移方程式,设fi,jf_{i,j}为前ii个位置，第ii个位置选了jj这个碱基，且符合条件

fi,j=∑k=1m[visk,j]⋅fi−1,kf_{i,j}=\sum_{k=1}^{m} [vis_{k,j}]\cdot f_{i-1,k}

发现nn大，又发现mm数据范围较小，于是可以使用矩阵加速一个52⋅5252 \cdot 52的矩阵表示可达性，经过n−1n-1次快速幂，便可以达到目标

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
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=60;
const int P=1000000007;
int vis[N][N];
struct node
{
    int g[110][110];
    int r,c;
    node(){}
    node(int _r,int _c):r(_r),c(_c)
    {
        memset(g,0,sizeof(g));
    }
    
    void clear()
    {
        memset(g,0,sizeof(g));
        for(int i=0;i<=r;i++)
            g[i][i]=1;
    }
    
    node operator*(node b)
    {
        node ans(r,b.c);
        for(int i=0;i<=r;i++)
            for(int j=0;j<=b.c;j++)
                for(int k=0;k<=c;k++)
                    ans.g[i][j]=(ans.g[i][j]+g[i][k]*b.g[k][j]%P)%P;
        return ans;
    }
    
    node operator^(int b)
    {
        node ans(r,c);
        node a=*this;
        ans.clear();
        while(b)
        {
            if(b&1)
                ans=ans*a;
            b=b>>1;
            a=a*a;
        }
        return ans;
    }
}f,g;
int n,m,k;
signed main()
{
    cin>>n>>m>>k;
    g.r=g.c=60;
    f.r=f.c=60;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            g.g[i][j]=1;
    for(int i=1;i<=k;i++)
    {
        char a,b;
        cin>>a>>b;
        int aa,bb;
        if(a>='a'&&a<='z')
            aa=a-'a'+1;
        else
            aa=a-'A'+1+26;
        if(b>='a'&&b<='z')
            bb=b-'a'+1;
        else
            bb=b-'A'+1+26;
        g.g[aa][bb]=0;
    }
    g=g^(n-1);
    for(int i=1;i<=m;i++)
        f.g[1][i]=1;
    int ans=0;
    f=f*g;
    for(int i=1;i<=m;i++)
        ans=(ans+f.g[1][i])%P;
    cout<<ans;
}

7月4日DP

CF893E

考虑只有正整数的情况，先考虑质数如何拆成yy位，显然是一个位填xx，其余空填11,方案数为yy，至于其他的数，我们将xx质因数分解，假设有ii个pp,那这就是一个放球游戏，将ii个球放进yy个空，每个空可以不放，可以放多个，那这就是一个隔板法，使用Ci+y−1iC_{i+y-1}^{i}即可求出，我们现在考虑上负数，发现只有负号为偶数个时才会产生贡献，于是我们直接将答案乘上

∑i=0y2Cy2i\sum_{i=0}^{\frac{y}{2}}C_{y}^{2i}

即可，而上式又等于2y−12^{y-1}

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<iostream>
#define int long long
using namespace std;
const int P=1000000007;
int x,y;
int powq(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%P;
        b=b>>1;
        a=a*a%P;
    }
    return ans;
}
void solve()
{
    cin>>x>>y;
    int ans=1;
    int zi=1,mu=1;
    for(int i=2;i*i<=x;i++)
    {
        int d=0;
        while(x%i==0)
        {
            x=x/i;
            d++;
        }
        for(int i=y;i<=d+y-1;i++)
        {
            zi=zi*i%P;
            mu=mu*(i-y+1)%P;
        }
    }
    ans=ans*zi%P*powq(mu,P-2)%P;
    if(x!=1)
        ans=ans*y%P;
    ans=ans*powq(2,y)%P*powq(2,P-2)%P;
    cout<<ans<<'\n';
}
signed main()
{
    int T;
    cin>>T;
    while(T--)
        solve();
}

CF167B

我们定义fi,jf_{i,j}为前ii场，赢了jj场并符合条件的概率，发现无法维护现背包的体积，于是我们增加一维维护背包体积

我们定义fi,j,kf_{i,j,k}为前ii场，赢了jj场，且现背包体积为kk的概率，这样列出来发现时间复杂度高达O(n4)O(n^{4})，我们发现每个物品只会减少一个体积，那总共减少不会超过nn，于是我们将超过nn的范围缩为nn，由于我们将k≥nk\ge n的状态归为nn，有很多状态不能通过填表发维护，于是我们列出下面两个方程

fi,j,k+=fi−1,j,k⋅(100−pi)⋅0.01f_{i,j,k}+=f_{i-1,j,k}\cdot (100-p_{i})\cdot 0.01

这是输了的

fi,j+1,min⁡(n,k+ai)+=fi−1,j,k⋅pi⋅0.01f_{i,j+1,\min (n,k+a_{i})}+=f_{i-1,j,k}\cdot p_{i}\cdot 0.01

这是赢了的

最后只需要输出

∑i=ln∑j=0nfn,i,j\sum_{i=l}^{n} \sum_{j=0}^{n} f_{n,i,j}

即可

由于我们不需要在意过程，并且这个转移式不能处理先赢东西再加体积，于是我们便可以按照aa来给它从大到小排序

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
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,l;
double f[210][210][210];
struct node
{
    int p,a;
}e[210];
int cmp(node a,node b)
{
    return a.a>b.a;
}
int main()
{
    cin>>n>>m>>l;
    f[0][0][min(n,l)]=1;
    for(int i=1;i<=n;i++)
        cin>>e[i].p;
    for(int i=1;i<=n;i++)
        cin>>e[i].a;
    sort(e+1,e+n+1,cmp);
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            for(int k=0;k<=n;k++)
            {
                f[i][j+1][min(n,k+e[i].a)]+=f[i-1][j][k]*e[i].p*0.01;
                f[i][j][k]+=f[i-1][j][k]*(100-e[i].p)*0.01;
            }
    double ans=0;
    for(int i=m;i<=n;i++)
        for(int k=0;k<=n;k++)
            ans+=f[n][i][k];
    printf("%.6lf",ans);
}

CF730J

这个题第一问非常简单，第二问就是在第一问的基础上来求移动最小值

要求移动最小值，那么就是求不移动最大值，我们定义fi,j,kf_{i,j,k}为前ii个杯子，选了jj个杯子，现容积
为kk的最大不移动值，那

fi,j,k=max⁡fi−1,j−1,k−bi+aif_{i,j,k}=\max f_{i-1,j-1,k-b_{i}}+a_{i}

第一维可以滚掉，那这就类似一个背包了，我们设sumsum为总体积，tottot为选cntcnt个容器的最大体积,cntcnt是第一问的答案，于是我们将ansans统计出来即可

ans=max⁡i=sumtotfcnt,ians=\max_{i=sum}^{tot} f_{cnt,i}

7月5日

梦熊

字符串SS,仅包含0∼90\sim9 一个n×nn \times n的矩阵AA,Ai,jA_{i,j}这个数就是Si×SjS_{i}\times S_{j}，求有多少个子矩阵和等于TT

发现一个子矩阵(x1,y1),(x2,y2)(x_{1},y_{1}),(x_{2},y_{2})就是

∑i=x1x2∑j=y1y2Si×Sj=T\sum_{i=x_{1}}^{x_{2}} \sum_{j=y_{1}}^{y_{2}} S_{i} \times S_{j}=T

设prepre为前缀和，则上式等于

(prex2−prex1)×(prey2−prey1)=T(pre_{x_{2}}-pre_{x_{1}})\times (pre_{y_{2}}-pre_{y_{1}})=T

枚举y1,y2y_{1},y_{2}，预处理每一对x2−x1x_{2}-x_{1}的和

最后检验Tprey2−prey1\frac{T}{pre_{y_{2}}-pre_{y_{1}}}是否存在即可

要特判00和Tprey2−prey1>36000\frac{T}{pre_{y_{2}}-pre_{y_{1}}}>36000

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
#include<iostream>
#define int long long
using namespace std;
int vis[400100];
int n,T;
int OvO;
string S;
int w[40100],s[40100];
signed main()
{
    freopen("submat.in","r",stdin);
    freopen("submat.out","w",stdout);
    cin>>T;
    cin>>S;
    n=S.size();
    S='0'+S;
    for(int i=1;i<=n;i++)
    {
        w[i]=(int)(S[i]-'0');
        s[i]=s[i-1]+w[i];
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            vis[s[i]-s[j]]++;
    int ans=0;
    for(int l=1;l<=n;l++)
        for(int r=l;r<=n;r++)
        {
            if(s[r]-s[l-1]==0)
            {
                if(T==0)
                    ans+=(n*n+n)/2;
                continue;
            }
            if(T%(s[r]-s[l-1])!=0)
                continue;
            if(T/(s[r]-s[l-1])>40000)
                continue;
            ans+=vis[T/(s[r]-s[l-1])];
        }
    cout<<ans;
}

梦熊

每次从当前的字符串SS中选择字典序最大的连续子串，将其从SS中删除，并追加到新的字符串TT的末尾，直到SS为空。馆长希望你能帮忙编写一个程序,实现这一规则,并最终得到字符串TT。

每次都找最大的后缀，那我们希望第一个字母就是当前串最大的字母，从zz循环到aa，记一个全局lastlast，代表下一次要从哪里开始，从lastlast到11，加字符，每次遇到外循环所枚举的字符，比较大小，更新last,复杂度最多O(26n)O(26n)

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
#include<iostream>
#include<queue>
using namespace std;
const int N=500010;
int n;
int T;
char c[N];
int vis[27];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        vis[c[i]-'a']++;
    }
    int last=n+1;
    int l=n+1;
    int pos=25;
    while(pos>=0)
    {
        string ans;
        string now;
        for(int j=last-1;j>=1;j--)
        {
            now=c[j]+now;
            if((int)(c[j]-'a')==pos)
            {
                if(now>ans)
                {
                    ans=now;
                    l=j;
                }
            }

        }
        for(int j=l;j<last;j++)
        {
            cout<<c[j];
            vis[(int)(c[j]-'a')]--;
        }
        last=l;
        while(pos>=0&&!vis[pos])
            pos--;
    }
    cout<<'\n';
}
int main()
{
    freopen("library.in","r",stdin);
    freopen("library.out","w",stdout);
    cin>>T;
    while(T--)
        solve();
}

梦熊

有nn个人,mm间旅馆，旅馆排成个圈，刚开始第ii个住在aia_{i}间旅馆里,第ii个人住在第jj个房间里幸福度为hi,jh_{i,j},有一个XX，每次可以指定两个不同的人i,ji,j，让ai+X,aj−Xa_{i}+X,a_{j}-X，这样的操作可以进行任意多次，求最后最大幸福度总和

此题让求最后总和，并没有求什么过程，也就是说，我们最后的+X,−X+X,-X相互抵消就可以，那考虑DPDP,fi,jf_{i,j}表示前ii个人选完后，有jj个XX没有抵消，举个例子f4,5f_{4,5}表示前44个人中，多加了55个XX,要想抵消，我们就需要在第55个人身上减去55个XX

XX的最大范围就是m−1m-1,jj的范围是2m:2m:从−m-m到mm

因为超过mm后，可以让他自己抵消mm个XX,一定会回到原位置

列出转移式

fi,j=max⁡k=−mmfi−1,k+hi,((a[i]−(k−j)∗X)%m+m)%mf_{i,j}=\max_{k=-m}^{m} f_{i-1,k}+h_{i,((a[i]-(k-j)*X)\%m+m)\%m}

最后答案就是fn,0f_{n,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
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=210;
const int D=300;
int f[N][N*3];
int n,m;
int h[N][N];
int a[N];
int X;
int MOD[200010];
void solve()
{
    memset(f,-0x3f,sizeof(f));
    cin>>n>>m>>X;
    X=X%m;
    f[0][0+D]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]--;
    }
    for(int i=-100000;i<=100000;i++)
        MOD[i+100000]=(i+m*1000000)%m;
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
            cin>>h[i][j];
    for(int i=1;i<=n;i++)
        for(int j=-m;j<=m;j++)
            for(int k=-m;k<=m;k++)
                f[i][j+D]=max(f[i][j+D],f[i-1][k+D]+h[i][MOD[(a[i]-(k-j)*X)+100000]]);
    cout<<f[n][0+D]<<'\n';
}
signed main()
{
    freopen("circle.in","r",stdin);
    freopen("circle.out","w",stdout);
    int T;
    cin>>T;
    while(T--)
        solve();
}

练习赛127B

我们发现一个数的给出质因数分解式，则这个数的约数个数就有

∏i=1n(ai+1)\prod_{i=1}^{n}(a_{i}+1)

那约数的kk次方和就是

∏i=1n∑j=0a[i]pij\prod_{i=1}^{n} \sum_{j=0}^{a[i]} p_{i}^{j}

发现后面是一个等比数列，那按照公式直接求和就可以，注意特判公比为11的情况

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<iostream>
#define int long long
using namespace std;
const int P=1000000007;
int n,d;
int powq(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%P;
        b=b>>1;
        a=a*a%P;
    }
    return ans;
}
signed main()
{
    cin>>n>>d;
    int ans=1;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        int now=powq(x,d);
        if(now==1)
            ans=ans*(y+1)%P;
        else
            ans=ans*(powq(now,y+1)-1+P)%P*powq(now-1+P,P-2)%P;
    }
    cout<<ans;
}

7月7日

颓颓颓，看了熊出没逆转时空的电影。

qtanglani

qtanglani

吾日三省吾身：有想法立即实现了吗，暴力分打满了吗,文件操作打对了吗。

4
0
0
NOTICE

亻尔 女子

CATEGORYS
TAGS