发表更新Problem Solutions3 分钟读完 (大约444个字)

题解：CF438D The Child and Sequence

题目

思路

题目要求我们完成三种操作：

  • 区间求和
  • 区间取模
  • 单点修改

1，3两种都非常简单，问题在于如何维护区间取模。

可以想到维护区间最大值，如果小于模数则不处理，否则将这个区间重新pushup。

如何证明该复杂度？注意到，一个数最多会被取模 $log{a_i}$ 次，所以复杂度我 $O(nlog_nlog{\max{a_i}})$ 。

代码

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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=1e5+5;

ll n,m;
ll a[N];

struct segtree
{
    struct node
    {
        ll sum,mx;
    } tr[N*4];

    void pushup(ll p)
    {
        tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
        tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);
    }

    void build(ll p,ll l,ll r)
    {
        if(l==r)
        {
            tr[p]={a[l],a[l]};
            return ;
        }

        ll mid=l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        pushup(p);
    }

    void update(ll p,ll l,ll r,ll x,ll y)
    {
        if(l==r)
        {
            tr[p]={y,y};
            return ;
        }

        ll mid=l+r>>1;
        if(x<=mid)
        {
            update(p<<1,l,mid,x,y);
        }
        else
        {
            update(p<<1|1,mid+1,r,x,y);
        }

        pushup(p);
    }


    void update_mod(ll p,ll l,ll r,ll x,ll y,ll v)
    {
        if(l==r)
        {
            tr[p].sum%=v;
            tr[p].mx%=v;
            return ;
        }

        ll mid=l+r>>1;
        if(x<=mid&&tr[p<<1].mx>=v)
        {
            update_mod(p<<1,l,mid,x,y,v);
        }
        if(y>mid&&tr[p<<1|1].mx>=v)
        {
            update_mod(p<<1|1,mid+1,r,x,y,v);
        }

        pushup(p);
    }


    ll query(ll p,ll l,ll r,ll x,ll y)
    {
        if(x<=l&&y>=r)
        {
            return tr[p].sum;
        }

        ll mid=l+r>>1;
        ll ret=0;
        if(x<=mid)
        {
            ret+=query(p<<1,l,mid,x,y);
        }
        if(y>mid)
        {
            ret+=query(p<<1|1,mid+1,r,x,y);
        }

        return ret;
    }
} T;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>n>>m;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    T.build(1,1,n);

    while(m--)
    {
        ll typ,l,r;
        cin>>typ>>l>>r;
        if(typ==1)
        {
            cout<<T.query(1,1,n,l,r)<<"\n";
        }
        else if(typ==2)
        {
            ll x;
            cin>>x;
            T.update_mod(1,1,n,l,r,x);
        }
        else
        {
            T.update(1,1,n,l,r);
        }
    }

    return 0;
}

然而没有什么技巧。

发表更新Problem Solutions2 分钟读完 (大约308个字)

题解：CF628D Magic Numbers

题目

思路

首先可以看出这是一道数位dp。它的参数分为两个部分：是否magic和是否是 $m$ 的倍数。这两个部分其实都比较好处理：前者在dfs是判断即可（这里并不复杂，其实直接从高位开始推就行了，不用考虑奇偶位不一样问题…），后者记录一下当前$\mod m$ 的余数，最后再判断。最后，因为字符串不好减一（其实也可以减），所以需要特判一下左端点字符串。

代码

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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=2005,mod=1e9+7;

ll m,d;
string a,b;
ll dig[N];
ll len;

ll dp[N][N];

ll dfs(ll x,ll r,bool lim)
{
	if(x==len)
	{
		return r==0;
	}
	
	if(~dp[x][r]&&!lim)
	{
		return dp[x][r];
	}
	
	ll ret=0,up=lim?dig[x]:9;
	for(ll i=0;i<=up;i++)
	{
//		if(x==0&&i==0)
//		{
//			continue;
//		}
		if(x%2==0&&i!=d) //odd
		{
			ret=(ret+dfs(x+1,(r*10+i)%m,lim&&(i==up)))%mod;
		}
		if(x%2==1&&i==d) //even
		{
			ret=(ret+dfs(x+1,(r*10+i)%m,lim&&(i==up)))%mod;
		}
	}
	
	if(!lim)
	{
		dp[x][r]=ret;
	}
	return ret;
}

ll solve(string x)
{
	len=x.size();
	for(ll i=0;i<len;i++)
	{
		dig[i]=x[i]-'0';
	}
	return dfs(0,0,1);
}

bool check(string x)
{
	ll r=0; 
	for(ll i=0;i<len;i++)
	{
		if(i%2==0&&x[i]==d+'0')
		{
			return 0;
		}
		if(i%2==1&&x[i]!=d+'0')
		{
			return 0;
		} 
		r=(r*10+x[i]-'0')%m;
	}
	return r==0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	memset(dp,-1,sizeof dp);
	cin>>m>>d;
	cin>>a>>b;
	
	cout<<(solve(b)-solve(a)+check(a)+mod)%mod<<'\n';	
	
	return 0;
}

发表更新Problem Solutions5 分钟读完 (大约807个字)

题解：HDU4879 ZCC loves march

题目

vjudge

You have a square grid of size $m×m$. There are $n$ troops placed on this grid, each with coordinates $(x_i​,y_i​)$.

Over t minutes, the following events occur:

  1. Move: A troop numbered x moves in a direction (up, down, left, or right) for d units. Troops cannot move outside the grid.

  2. Regroup: Troop x gathers all other troops that share the same row or column as troop x. These troops move to troop x’s location.

The cost of moving troop $i$ to troop $j$ is calculated as: $(x_i​−x_j​)^2+(y_i​−y_j​)^2$.

For each regrouping event, output the total cost of all troop movements during that regrouping, modulo $10^9+7$.

思路

我们对于每一个横坐标/纵坐标，记录下它们对应的纵坐标/横坐标（由于 $m$ 会很大，我们考虑把这些坐标离散化）。使用并查集，记录每一个士兵属于的块（即祖先节点），以及该块的大小。接下来开始操作。首先使用一个小技巧：对于每次操作，再开一个新点，这样就不用讨论该块的祖先节点是否改动。

对于操作1（对应下面操作S）非常好处理，将原来块大小减一，再将其放置到新快中；

对于操作2（对应下面操作Q），我们把当前士兵的位置作为新的块，依次遍历所有和它同行同列的块，这里要注意，对于与该士兵同样位置的士兵会在两次遍历中都被加入新块，要减一次。

想通这些部分，问题就迎刃而解了，只需模拟我们上述的思路即可。

Warnings:

  • 要看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
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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=1e5+5,mod=1e9+7;

ll n,m,t;
struct node
{
	ll x,y;
} a[N*2];

ll ans;
ll tox,toy;
map<ll,ll> mx,my;
vector<ll> ex[N*2],ey[N*2];
ll id[N];

ll cn[N*2],par[N*2];

ll find(ll x)
{
	return par[x]==x?x:par[x]=find(par[x]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n>>m;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
		id[i]=i;
		if(!mx[a[i].x])
		{
			mx[a[i].x]=++tox;
		}
		if(!my[a[i].y])
		{
			my[a[i].y]=++toy;
		}
		ex[mx[a[i].x]].push_back(i);
		ey[my[a[i].y]].push_back(i);
		par[i]=i;
		cn[i]++; 
	}
	
	cin>>t;
	for(ll i=n+1;i<=n+t;i++)
	{
		char c;
		ll p;
		cin>>c>>p;
		p^=ans;
		ll fp=find(id[p]);
		ll cx=a[fp].x,cy=a[fp].y;
		if(c=='Q')
		{
			ans=0;
			a[i].x=cx,a[i].y=cy;
			ll cn2=0;
			for(auto q:ex[mx[cx]])
			{
				ll fq=find(q);
				ll val=(a[fq].y-cy)%mod;
				val=val*val%mod;
				ans=(ans+val*cn[fq]%mod)%mod;
				cn[i]+=cn[fq];
				if(a[fq].y==cy) //count twice
				{
					cn2+=cn[fq];
				}
				else
				{
					par[fq]=i;
				}
			}
			ex[mx[cx]].clear();
			for(auto q:ey[my[cy]])
			{
				ll fq=find(q);
				ll val=(a[fq].x-cx)%mod;
				val=val*val%mod;
				ans=(ans+val*cn[fq]%mod)%mod;
				cn[i]+=cn[fq];
				if(a[fq].x!=cx)
				{
					par[fq]=i;
				}
			}
			ey[my[cy]].clear();
			cn[i]-=cn2;
			ex[mx[cx]].push_back(i);
			ey[my[cy]].push_back(i);
			par[i]=i;
			cout<<ans<<"\n";
		}
		else
		{
			ll d;
			cin>>d;
			if(c=='L')
			{
				cy-=d;
			}
			else if(c=='R')
			{
				cy+=d;
			}
			else if(c=='U')
			{
				cx-=d;
			}
			else if(c=='D')
			{
				cx+=d;
			}
			
			if(!mx[cx])
			{
				mx[cx]=++tox;
			}
			if(!my[cy])
			{
				my[cy]=++toy;
			}
			a[i]={cx,cy};
			cn[fp]--;
			ex[mx[cx]].push_back(i);
			ey[my[cy]].push_back(i);
			cn[i]++;
			par[i]=i;
		}
		id[p]=i;
	}
	
	return 0;
}

做了我2d，纯纯可恶 (σ｀д′)σ

发表更新Problem Solutions5 分钟读完 (大约742个字)

题解：Black And White / Flip and Combos

题目

题目描述

给你一个长度为n的01序列 a[1],…,a[n]

每次询问给定一个区间[l,r]，询问[l,r]里最长的连续的1的长度

每次修改给定一个区间[l,r]，将[l,r]里的a[i]变成1-a[i]（或者说异或1）

n, m <= 100000

输入格式

第一行一个n

第二行n个数，表示01序列初始状态

第三行一个m，接下来m行，每行有三个数x,l,r

若 x=0，表示一次查询，查询[l,r]里的最长连续1的长度

若 x=1，表示一次修改，将[l,r]里的数异或1

输出格式

对于输入里的每一个查询，输出一行一个整数，该询问的最长连续1的长度

思路

维护最长子串是经典的线段树，由于有01翻转修改，所以不能只存连续1串，也要存0.

思路可能和GSS有点像，都是维护区间最长前缀、后缀和子串（GSS是子序列），修改就翻转+重新pushup就行了。

其实不是很困难，但是线段树写起来非常易错（因为我很菜orz）

代码

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>

using namespace std;

#define ll long long

const ll N=100005;

ll n,m;
ll a[N];

struct node
{
	ll l[2],r[2],mx[2]; //最长前缀，最长后缀，最长子串 
	bool lz; //懒惰标记
} tr[N*4];

void pushup(ll p,ll l,ll r) 
{
	ll mid=l+r>>1;
	
	for(ll i=0;i<2;i++)
	{
		tr[p].l[i]=tr[p<<1].l[i];
		if(tr[p<<1].l[i]==mid-l+1) //如果左半个区间全是i，前缀加上右半个区间
		{
			tr[p].l[i]+=tr[p<<1|1].l[i];	
		}
		tr[p].r[i]=tr[p<<1|1].r[i];
		if(tr[p<<1|1].r[i]==r-mid) //如果右半个区间全是i，后缀加上左半个区间
		{
			tr[p].r[i]+=tr[p<<1].r[i];
		}
		tr[p].mx[i]=max(max(tr[p<<1].mx[i],tr[p<<1|1].mx[i]),tr[p<<1].r[i]+tr[p<<1|1].l[i]);
	}
}

void flip(ll p) //翻转修改 
{
	swap(tr[p].l[0],tr[p].l[1]);
	swap(tr[p].r[0],tr[p].r[1]);
	swap(tr[p].mx[0],tr[p].mx[1]);
}

void pushdown(ll p,ll l,ll r)
{
	if(l!=r)
	{
		tr[p<<1].lz^=1;
		tr[p<<1|1].lz^=1;
		flip(p<<1),flip(p<<1|1); //左儿子右儿子继续翻转
		
		tr[p].lz=0;
	}
}

void build(ll p,ll l,ll r)
{
	tr[p].lz=0;
	if(l==r) //叶子区间赋值，写得比较无用抽象
	{
		for(ll i=0;i<2;i++)
		{
			ll j=i;
			if(a[l]==0) 
			{
				j^=1;
			}
			tr[p].l[i]=tr[p].r[i]=tr[p].mx[i]=j;
		}
		return ;
	}
	
	ll mid=l+r>>1;
	
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	
	pushup(p,l,r);
}


void update(ll p,ll l,ll r,ll x,ll y)
{
	if(l>=x&&r<=y)
	{
		tr[p].lz^=1;
		flip(p);
		return ;
	}
	
	if(tr[p].lz)
	{
		pushdown(p,l,r);
	}
	
	ll mid=l+r>>1;
	if(mid>=y)
	{
		update(p<<1,l,mid,x,y);
	}
	else if(mid<x)
	{
		update(p<<1|1,mid+1,r,x,y);
	}
	else
	{
		update(p<<1,l,mid,x,y);
		update(p<<1|1,mid+1,r,x,y);	
	}
	
	pushup(p,l,r);
}

ll query(ll p,ll l,ll r,ll x,ll y)
{
	if(l>=x&&r<=y)
	{
		return tr[p].mx[1];
	}
	
	if(tr[p].lz)
	{
		pushdown(p,l,r);
	}
	
	ll mid=l+r>>1;
	if(mid>=y)
	{
		return query(p<<1,l,mid,x,y);
	}
	else if(mid<x)
	{
		return query(p<<1|1,mid+1,r,x,y);
	}
	else
	{
		ll m1=query(p<<1,l,mid,x,y); //左半个区间的mx
		ll m2=query(p<<1|1,mid+1,r,x,y); //右半个区间的mx
		
		ll m3=min(mid-x+1,tr[p<<1].r[1]); //左半个区间的最大后缀 
		ll m4=min(y-mid,tr[p<<1|1].l[1]); //右半个区间的最大前缀 
		
		return max(max(m1,m2),m3+m4);
	}
	
	pushup(p,l,r);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	
	build(1,1,n);
	
	cin>>m;
	while(m--)
	{
		ll q,l,r;
		cin>>q>>l>>r;
		
		if(q==1)
		{
			update(1,1,n,l,r);
		}
		else
		{
			cout<<query(1,1,n,l,r)<<"\n";
		}
	}
	
	
	return 0;
}

撒花！

发表更新Problem Solutions3 分钟读完 (大约443个字)

题解：洛谷P6279 [USACO20OPEN] Favorite Colors G

洛谷

被for(auto a:b)背刺了/fn/fn

思路

使用并查集和启发式合并

由题意我们可以很显然地发现一个节点的子节点颜色一样，同理，这些子节点的所有子节点颜色都一样，这时，我们可以把这些子节点全部合并到一个节点上，为降低复杂度，我们找到子节点最多的节点，把所有同深度的子树放到这个节点上。

对于每一棵树，我们给所有节点设定同一个颜色即可。

代码

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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=200005;

ll n,m;
vector<ll> e[N];
ll par[N];
ll cn[N];

ll find(ll x)
{
	return par[x]==x?x:par[x]=find(par[x]);
}

void dfs(ll x)
{
	ll hvs=e[x][0],mx=e[hvs].size();
    //size可能不是ll型的，不知道是不是必须转，但是如果把mx赋成-1就得转，否则会RE
	for(auto y:e[x])
	{
		if((ll)e[y].size()>mx) 
		{
			hvs=y;
			mx=(ll)e[hvs].size();
		}
	}
	
	ll mxf=find(hvs);
//	for(auto y:e[x]) //就是被这个东西背刺的，原因可能是e[x]后面会push新的节点进去，或者被clear，会导致错误
	for(ll i=0;i<(ll)e[x].size();i++)
	{
		ll y=e[x][i];
		ll yf=find(y);
		if(yf!=mxf)
		{
			par[yf]=mxf;
			for(auto k:e[yf])
			{
				e[mxf].push_back(k);
			}
			e[yf].clear();
		}
	}
	
	e[x].clear();
	e[x].push_back(mxf);
	
	if(e[mxf].size()>1)
	{
		dfs(mxf);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n>>m;
	for(ll i=1;i<=m;i++)
	{
		ll x,y;
		cin>>x>>y;
		e[x].push_back(y);
	}
	
	for(ll i=1;i<=n;i++)
	{
		par[i]=i;
	}
	
	for(ll i=1;i<=n;i++)
	{
		if(e[i].size()>1)
		{
			dfs(i);
		}
	}
	
	ll tot=0;
	for(ll i=1;i<=n;i++)
	{
		ll f=find(i);
		if(!cn[f])
		{
			cn[f]=++tot;
		}
		cout<<cn[f]<<"\n";
	}
	
	return 0;
}

Finished…

发表更新Problem Solutions13 分钟读完 (大约1883个字)

题解：SPOJ-GSS系列

GSS系列 - 题单 - 洛谷

又开天坑.mp4

做一下SPOJ的8道数据结构，但是什么时候能写完我也不知道qwq

关于SPOJ注册问题

这个很多帖子都有讲，主要就是google的recaptcha用不了，把它更换成recaptcha.net的验证（虽然尝试跨越长城了，但是仍然用不了，不知道为啥）

解决方法就是安装 Gooreplacer(for Microsoft Edge)

下载完成后，点击橙色小刷子，在弹出的窗口中点击最上方的蓝色按钮“配置规则”。点击页面中表格上方的“新增”，在弹出的窗口内依次输入 www.google.com/recaptcha，“通配符”，recaptcha.net/recaptcha，点击“提交”。

正文

GSS1

思路

这个比较简单，就是最基本的一个框架。

一个节点有4个部分：区间和sum、区间最大前缀和lmx，区间最大后缀和rmx，区间最大子段和mx

  • 在算一个区间最大子段和时，会出现两种情况：

    1. 该区间最大子段和是左/右儿子的最大子段和
    2. 该区间最大子段和是左儿子的最大后缀和+右儿子的最大前缀和

  • 在算一个区间的最大前缀/后缀和时，也会出现两种情况：（以前缀和为例）

    1. 该区间最大前缀和是左儿子的最大前缀和
    2. 该区间最大前缀和是左儿子的区间和加右儿子的最大前缀和

至此，我们就可以将线段树build起来了，有一个技巧注意一下，因为在接下来的题里也会用：

​ 重定义node结构体的”+“，或者写一个merge函数，表示node之间的加法，因为不仅有pushup会用到，query也会用。

然后关于query没有什么好讲的吧。就这样，看代码。

代码

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>

using namespace std;

#define ll long long

const int N=50005;

ll n,m;
ll a[N];

struct node
{
    ll sum,lmx,rmx,mx;
    
    node()
    {
    	sum=lmx=rmx=mx=0;
	}
    
} tr[N<<2];

node merge(node x,node y)
{
	node ans;
	ans.sum=x.sum+y.sum;
    ans.lmx=max(x.lmx,x.sum+y.lmx);
    ans.rmx=max(y.rmx,y.sum+x.rmx);
    ans.mx=max(max(x.mx,y.mx),x.rmx+y.lmx);
    
    return ans;
}

void pushup(ll p) 
{
    tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}

void build(ll p,ll l,ll r) 
{
    if(l==r) 
	{
        tr[p].lmx=tr[p].rmx=tr[p].mx=tr[p].sum=a[l];
        return;
    }
    
    ll mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    
    pushup(p);
}

node query(ll p,ll l,ll r,ll x,ll y) 
{
    if(x<=l&&y>=r) 
	{
		return tr[p]; 
	}
	
    ll mid=(l+r)>>1;
    node L,R;
    
    if(y<=mid)
    {
    	return query(p<<1,l,mid,x,y);
	}
    else if(x>mid)
    {
    	return query(p<<1|1,mid+1,r,x,y);
	}
	else
	{
		L=query(p<<1,l,mid,x,y);
		R=query(p<<1|1,mid+1,r,x,y);
		return merge(L,R);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
    	cin>>a[i];
	}
    
    build(1,1,n);
    
    cin>>m;
    while(m--) 
	{
        ll x,y;
        cin>>x>>y;
        
        cout<<query(1,1,n,x,y).mx<<"\n";
        
    }
    
    return 0;
}

GSS2

思路

没写，这个难，咕

代码

1

GSS3

思路

本题在第一题的基础上加入了单点修改，没有任何攻击性（确信

update就很正常，把边界的点重新赋值，然后重新往上pushup一下就行了。

代码

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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=100005;

int n,m;
int a[N];

struct node
{
    ll sum,lmx,rmx,mx;
    
    node()
    {
    	sum=lmx=rmx=mx=0;
	}
    
} tr[N<<2];

node merge(node x,node y)
{
	node ans;
	ans.sum=x.sum+y.sum;
    ans.lmx=max(x.lmx,x.sum+y.lmx);
    ans.rmx=max(y.rmx,y.sum+x.rmx);
    ans.mx=max(max(x.mx,y.mx),x.rmx+y.lmx);
    
    return ans;
}

void pushup(int p) 
{
    tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}

void build(int p,int l,int r) 
{
    if(l==r) 
	{
        tr[p].lmx=tr[p].rmx=tr[p].mx=tr[p].sum=a[l];
        return;
    }
    
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    
    pushup(p);
}

void update(int p,int l,int r,int x,int v)
{
	if(l==r)
	{
		tr[p].lmx=tr[p].rmx=tr[p].mx=tr[p].sum=v;
		return;
	}
	
	int mid=(l+r)>>1;
	if(x<=mid)
    {
        update(p<<1,l,mid,x,v);
    }
    else
    {
        update(p<<1|1,mid+1,r,x,v);
    }
    
    pushup(p);
}

node query(ll p,ll l,ll r,ll x,ll y) 
{
    if(x<=l&&y>=r) 
	{
		return tr[p]; 
	}
	
    ll mid=(l+r)>>1;
    node L,R;
    
    if(y<=mid)
    {
    	return query(p<<1,l,mid,x,y);
	}
    else if(x>mid)
    {
    	return query(p<<1|1,mid+1,r,x,y);
	}
	else
	{
		L=query(p<<1,l,mid,x,y);
		R=query(p<<1|1,mid+1,r,x,y);
		return merge(L,R);
	}
}

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];
	}
    
    build(1,1,n);
    
    cin>>m;
    while(m--) 
	{
        int op,x,y;
        cin>>op>>x>>y;
        
        if(op==0)
        {
        	update(1,1,n,x,y);
		}
        else
        {
        	cout<<query(1,1,n,x,y).mx<<"\n";
		}
    }
    
    return 0;
}

GSS4

思路

这题跟前面3问好像没啥关系，不知道为啥放这，但是总体架构仍然不变。

区间求和没有什么难度，但是在修改的时候如果每一个数用sqrt开一下方，常数会剧增，因此需要讨论一种特殊情况：

​ 如果这一个区间的最大值已经<=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
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
#include<bits/stdc++.h>

using namespace std;

#define ll long long
mt19937 rnd(time(NULL));

ll n,m;
ll a[100005];

struct node
{
	ll sum,mx;
	node()
	{
		sum=mx=0;
	}
} tr[400005];

node merge(node x,node y)
{
	node ans;
	ans.sum=x.sum+y.sum;
    ans.mx=max(x.mx,y.mx);
    
    return ans;
}

void pushup(ll p)
{
	tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}

void build(ll p,ll l,ll r)
{
	if(l==r)
	{
		tr[p].sum=tr[p].mx=a[l];
		return ;
	}
	
	ll mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	
	pushup(p);
}

void update(ll p,ll l,ll r,ll x,ll y)
{
	if(l==r)
	{
		tr[p].sum=sqrt(tr[p].sum);
		tr[p].mx=sqrt(tr[p].mx);
		return ;
	}
	
	ll mid=(l+r)>>1;
	if(x<=mid&&tr[p<<1].mx>1)
	{
		update(p<<1,l,mid,x,y);
	}
	if(y>mid&&tr[p<<1|1].mx>1)
	{
		update(p<<1|1,mid+1,r,x,y);
	}
	
	
	pushup(p);
	
}

node query(ll p,ll l,ll r,ll x,ll y)
{
	if(x<=l&&y>=r)
	{
		return tr[p];
	}
	
	ll mid=(l+r)>>1;
	node L,R;
	if(x<=mid)
	{
		L=query(p<<1,l,mid,x,y);
	}
	if(y>mid)
	{
		R=query(p<<1|1,mid+1,r,x,y);
	}
	
	return merge(L,R);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	for(ll cs=1;cin>>n;cs++)
	{
		for(ll i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		build(1,1,n);
		
		cout<<"Case #"<<cs<<":\n";
		
		cin>>m;
		while(m--)
		{
			ll op,x,y;
			cin>>op>>x>>y;
			
			if(x>y)
			{
				swap(x,y);
			}
			
			if(op==0)
			{
				update(1,1,n,x,y);
			}
			else
			{
				cout<<query(1,1,n,x,y).sum<<"\n";
			} 
		}
		cout<<"\n";
	}

	return 0;
}

GSS7

思路

在第三题的基础上加入树链剖分。

代码

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
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int inf=0x3f3f3f3f;
const int N=1e5+5;

ll n,q;
ll x[N];

ll tot;
ll head[N],to[N*2],nxt[N*2];

ll cnt;
ll dfn[N],id[N];

ll sz[N],dep[N],hvy[N],top[N],par[N];

struct node
{
	ll sum,lmx,rmx,mx,lz;
	
	node()
    {
        sum=lmx=rmx=mx=0;
        lz=inf;
    }
    
} tr[N<<2];

void add(ll u,ll v)
{
    to[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
}

void dfs1(ll u,ll f)
{
    dep[u]=dep[f]+1;
    par[u]=f;
    sz[u]=1;
    
    for(ll i=head[u];i;i=nxt[i])
    {
        ll v=to[i];
        if(v==f)
        {
            continue;
        }
        dfs1(v,u);
        
        sz[u]+=sz[v];
        if(sz[v]>sz[hvy[u]])
        {
            hvy[u]=v;
        }
    }
}

void dfs2(ll u,ll tp) 
{
    dfn[u]=++cnt;
    id[cnt]=u;
    top[u]=tp;
    
    if(!hvy[u])
    {
        return;
    }
    
    dfs2(hvy[u],tp);
    
    for(ll i=head[u];i;i=nxt[i])
    {
        ll v=to[i];
        if(v==par[u]||v==hvy[u])
        {
            continue;
        }
        
        dfs2(v,v);
    }
}

node merge(node x,node y)
{
    node ans;
    ans.sum=x.sum+y.sum;
    ans.lmx=max(x.lmx,x.sum+y.lmx);
    ans.rmx=max(y.rmx,y.sum+x.rmx);
    ans.mx=max(max(x.mx,y.mx),x.rmx+y.lmx);
    ans.lz=inf;
    
    return ans;
}

void pushup(ll p)
{
    tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}

void build(ll p,ll l,ll r)
{
    if(l==r)
    {
        tr[p].sum=x[id[l]];
        tr[p].lmx=tr[p].rmx=tr[p].mx=max(tr[p].sum,0ll);
        tr[p].lz=inf;
        return;
    }
    
    ll mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    
    pushup(p);
}

void pushdown(ll p,ll l,ll r)
{
    if(tr[p].lz==inf)
    {
        return;
    }
    
    ll t=tr[p].lz;
    
    ll mid=(l+r)>>1;
    tr[p<<1].sum=(mid-l+1)*t;
    tr[p<<1].lmx=tr[p<<1].rmx=tr[p<<1].mx=max(tr[p<<1].sum,0ll);
    tr[p<<1].lz=t;
    tr[p<<1|1].sum=(r-mid)*t;
    tr[p<<1|1].lmx=tr[p<<1|1].rmx=tr[p<<1|1].mx=max(tr[p<<1|1].sum,0ll);
    tr[p<<1|1].lz=t;
    
    tr[p].lz=inf;
}

void update(ll x,ll y,ll p,ll l,ll r,ll k)
{
    if(x<=l&&r<=y)
    {
        tr[p].sum=(r-l+1)*k;
        tr[p].lmx=tr[p].rmx=tr[p].mx=max(tr[p].sum,0ll);
        tr[p].lz=k;
        return;
    }
    
    pushdown(p,l,r);
    
    ll mid=(l+r)>>1;
    if(x<=mid)
    {
        update(x,y,p<<1,l,mid,k);
    }
    if(mid<y)
    {
        update(x,y,p<<1|1,mid+1,r,k);
    }
    
    pushup(p);
}

node query(ll x,ll y,ll p,ll l,ll r)
{
    if(x<=l&&r<=y)
    {
        return tr[p];
    }
    
    pushdown(p,l,r);
    
    ll mid=(l+r)>>1;
    node L,R;
    if(x<=mid)
    {
        L=query(x,y,p<<1,l,mid);
    }
    if(mid<y)
    {
        R=query(x,y,p<<1|1,mid+1,r);
    }
    
    return merge(L,R);
}

void update_chain(ll u,ll v,ll k)
{
    ll fu=top[u],fv=top[v];
    
    while(fu!=fv)
    {
        if(dep[fu]<dep[fv])
        {
            swap(u,v);
            swap(fu,fv);
        }
        
        update(dfn[fu],dfn[u],1,1,n,k);
        u=par[fu],fu=top[u];
    }
    
    if(dep[u]>dep[v])
    {
        swap(u,v);
    }
    update(dfn[u],dfn[v],1,1,n,k);
}

node query_chain(ll u,ll v)
{
    node L,R;
    
    ll fu=top[u],fv=top[v];
    while(fu!=fv)
    {
        if(dep[fu]<dep[fv])
        {
            R=merge(query(dfn[fv],dfn[v],1,1,n),R);
            v=par[fv],fv=top[v];
        }
        else
        {
            L=merge(query(dfn[fu],dfn[u],1,1,n),L);
            u=par[fu],fu=top[u];
        }
    }
    
    if(dep[u]>dep[v])
    {
        L=merge(query(dfn[v],dfn[u],1,1,n),L);
    }
    else
    {
        R=merge(query(dfn[u],dfn[v],1,1,n),R);
    }
    
    swap(L.lmx,L.rmx);
    
    return merge(L,R);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        cin>>x[i];
    }
    for(ll i=1;i<n;i++)
    {
        ll u,v;
        cin>>u>>v;
        add(u,v),add(v,u);
    }
    
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    
    cin>>q;
    while(q--)
    {
        ll op,a,b,c;
        cin>>op>>a>>b;
        
        if(op==1)
        {
            cout<<query_chain(a,b).mx<<"\n";
        }
        else
        {
            cin>>c;
            update_chain(a,b,c);
        }
    }
    
    return 0;
}
发表更新Problem Solutions4 分钟读完 (大约538个字)

题解：ABC310F Make 10 Again

atcoder.jp

然而已经很久没有写题解了，天天模拟赛挂大分（摆=__=）

随机选取幸运题目，然而是dp

思路

首先这道题的“概率”非常扯，因为和求这个概率 $\frac{a}{b}$ 就相当于分别求一下 $a$ ，$b$ 然后相除。

分母非常好算，就是所有掷骰子的方案总和，全部乘起来即可。

分子则需要考虑 万能的 动态规划。因为我们只考虑总点数为10以内的情况，所以所有点数大于10的情况实际上是等价且不会影响结果的，而10很小，因此考虑状压。

用数组 $dp[i][s]$ 表示枚举到第 $i$ 枚骰子，状态为 $s$ 的方案数，其中 $s$ 是一个11位二进制数，分别表示点数和为0~10的情况。分别枚举每一枚骰子掷出的所有点数，进行状态转移，而如果可以掷出大于10的点数，对转移没有影响，单独加起来即可。

代码

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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll mod=998244353;

ll n;
ll a[105];
ll dp[105][(1<<11)+5];

ll den=1,num; //den:分母 num:分子

ll qpow(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1)
		{
			ret=ret*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	
	return ret;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i];
		den=den*a[i]%mod;
	}
	
	dp[0][1]=1; //第0枚骰子投出0的方案为1
	for(ll i=1;i<=n;i++) //第i枚骰子
	{
		for(ll j=1;j<=min(10ll,a[i]);j++) //第j种情况
		{
			for(ll s=0;s<(1<<11);s++) //原来的状态为s
			{
				ll s1=s; //现在的状态为s1
				for(ll k=0;k<11;k++) //对于原来状态的第k位
				{
					if(s&(1<<k))
					{
						s1=(s1|(1<<(j+k))); //用或运算表述取不取都可以
					}
				}
				s1%=(1<<11); //点数和超出10的舍掉
				dp[i][s1]=(dp[i][s1]+dp[i-1][s])%mod; //转移
			}
		}
		if(a[i]>10) //大于10
		{
			for(ll s=0;s<(1<<11);s++) //对于每个状态都有a[i]-10种方案（不取）
			{
				dp[i][s]=(dp[i][s]+dp[i-1][s]*(a[i]-10))%mod;
			}
		}
	}
	
	for(ll i=(1<<10);i<(1<<11);i++) //所有可以掷出10的方案和
	{
		num=(num+dp[n][i])%mod;
//		cout<<num<<"\n";
	}
	
	cout<<(num*qpow(den,mod-2)%mod)<<"\n"; //如题
	
	return 0;
}

好啦，你A了一道蓝题喵。时间复杂度 $O(100Sn)$ 其中 $S=2^{11}$ 。

发表更新Problem Solutions5 分钟读完 (大约777个字)

题解：洛谷P1149 [NOIP2008 提高组] 火柴棒等式 加强版！！！

洛谷の原版，原题n<=24，暴力即可，本题n<=30000。

内存限制：128 MiB

时间限制：3000 ms

给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：img

注意：

  1. 加号与等号各自需要两根火柴棍
  2. 如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）
  3. n根火柴棍必须全部用上

答案对 1000000007 取模输出

n <= 30000

思路

为了达成复杂度 $O(可过)$，考虑类似数位dp的写法，对A和B按位考虑，再求得C，总体分为以下几个部分：

  1. 考虑有没有进位
  2. 考虑A或者B是不是在这一位到达最高位（以免接下来的前导0耗费火柴，导致错误）
  3. 考虑A或者B是不是0，即目前是不是最低位（用bool值可以为dp数组省去一个30000的位，防止MLE）

即可写出数位dp的dfs框架：（是否为最低位，A结束，B结束，进位，剩余火柴）

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
int dfs: bool zero, bool enda, bool endb, bool carry, int sum:
	if enda and endb: 
		if !sum and !carry or sum==2 and carry : return 1
		return 0
		
	for a 0...9:
		if enda and a : continue
		for b 0...9:
			if endb and b : continue
			c=(a+b+carry)%10,ncarry=(a+b+carry)/10
			nsum=sum-(matches used by a,b,c)
			
			zero=0
			if !enda and !endb:
				dfs in now
				if a can be cut: dfs in enda=1
				if b can be cut: dfs in endb=1
				if both can be cut: dfs in enda=endb=1
			else if !endb:
				dfs in now
				if b can be cut: dfs in endb=1
			else if !enda:
				dfs in now
				if a can be cut: dfs in enda=1
			else:
				dfs in now

	dp[sum][zero][enda][endb][carry]=dfs's sum
	return dfs's sum

非常的简单，直接代码

代码

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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll mod=1000000007;

ll n;
ll match[]={6,2,5,5,4,5,6,3,7,6}; // matches of 0...9

ll dp[30005][2][2][2][2];

ll dfs(bool zero,bool enda,bool endb,bool carry,ll sum)
{
	if(dp[sum][zero][enda][endb][carry]!=-1)
	{
		return dp[sum][zero][enda][endb][carry];
	}
	
	if(enda&&endb)
	{
		if((sum==0&&!carry)||(sum==2&&carry))
		{
			return 1;
		}
		return 0;
	}
	
	ll ret=0;
	
	for(ll a=0;a<10;a++)
	{
		if(enda&&a)
		{
			continue;
		}
		
		for(ll b=0;b<10;b++)
		{
			if(endb&&b)
			{
				continue;
			}
			
			ll c=a+b+carry;
			ll ncarry=c/10;
			c=c%10;
			
			ll nsum=sum-match[c];
			if(!enda)
			{
				nsum-=match[a];
			}
			if(!endb)
			{
				nsum-=match[b];
			}
			if(nsum<0)
			{
				continue;
			}
			
			bool cuta=(a!=0||(a==0&&zero==1)); //a can be cut
			bool cutb=(b!=0||(b==0&&zero==1)); //b can be cut
			
			if(!enda&&!endb)
			{
				ret=(ret+dfs(0,0,0,ncarry,nsum))%mod;
				if(cuta)
				{
					ret=(ret+dfs(0,1,0,ncarry,nsum))%mod;
				}
				if(cutb)
				{
					ret=(ret+dfs(0,0,1,ncarry,nsum))%mod;
				}
				if(cuta&&cutb)
				{
					ret=(ret+dfs(0,1,1,ncarry,nsum))%mod;
				}
			}
			else if(enda&&!endb)
			{
				ret=(ret+dfs(0,1,0,ncarry,nsum))%mod;
				if(cutb)
				{
					ret=(ret+dfs(0,1,1,ncarry,nsum))%mod;
				}
			}
			else if(!enda&&endb)
			{
				ret=(ret+dfs(0,0,1,ncarry,nsum))%mod;
				if(cuta)
				{
					ret=(ret+dfs(0,1,1,ncarry,nsum))%mod;
				}
			}
			else if(enda&&endb)
			{
				ret=(ret+dfs(0,1,1,ncarry,nsum))%mod;
			}
		}
	}
	
	ret%=mod;
	
	dp[sum][zero][enda][endb][carry]=ret;
	
	return ret;
}
 

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	memset(dp,-1,sizeof dp);

	cin>>n;
	cout<<dfs(1,0,0,0,n-4)<<"\n"; //"+" and "=" cost 4 matches
	
	return 0;
}

样例

找不到其他可以测的地方，两个样例：

样例输入1

1
30000

样例输出1

1
75143404

样例输入2

1
20000

样例输出2

1
990516656
发表更新Problem Solutions3 分钟读完 (大约502个字)

题解：洛谷P2929 [USACO09HOL] Transmission Delay G

给出 $N (1 \leq N \leq 2000)$ 表示 $01$ 串的长度， $D(O \leq D < N)$ 表示 $0$ 或 $1$ 的最大偏离距离，一个长度为 $N$ 的 $01$ 串和一个整数 $K(1 \leq K \leq10^8)$，请计算传输延迟发生后一共有多少种可能的 $01$ 串，以及其中第 $K$ 大的串是什么。

洛谷

思路

首先这是一个分成两问的 DP 问题。通过原题，$01$ 串中两种位各自的数量不会发生变化，所以对于 DP 的状态，我们可以选用 $0$（或 $1$ ）的数量，即：$f[i][j]$ 表示 $i…n$ 为中使用 $j$ 个 $0$ 的方案数，这里倒着处理是为了求第二问。

另外，已知 $K(1 \leq K \leq10^8)$ ，如果 $f$ 数组的某一位超过 $10^8$ 那么它就会被取模，这会导致错误，因此我们开一个 $g$ 和 $f$ 的操作基本一致，但是如果某一位超过 $10^8$ ，就直接将其改为 $10^8+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
#include<bits/stdc++.h>

using namespace std;

#define ll long long
mt19937 rnd(time(NULL));

const int mod=100000000;

int n,d,k;
string s; 

int f[2005][2005],g[2005][2005]; //f:Question 1; g:Question 2
int cn0[2005],cn1[2005]; // 记录0和1的位置

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n>>d>>k>>s;
	s=" "+s;
	
	int l0=0,l1=0;
	for(int i=n;i>0;i--)
	{
		if(s[i]=='0')
		{
			cn0[++l0]=i;;
		}
		else
		{
			cn1[++l1]=i;;
		}
	}
	
	
	f[n+1][0]=g[n+1][0]=1;
	for(int i=n+1;i>1;i--)
	{
		for(int j=0;j<=l0;j++)
		{
			if(f[i][j])
			{
				if(j!=l0&&abs(i-1-cn0[j+1])<=d) //当前位选择0
				{
					if(!(j+l1!=n-i+1&&cn1[n-i+2-j]-i+2>d))
					{
						f[i-1][j+1]=(f[i-1][j+1]+f[i][j])%mod;
						g[i-1][j+1]=g[i-1][j+1]+g[i][j];
						g[i-1][j+1]=min(g[i-1][j+1],mod+1);
					}
				}
				
				if(j+l1!=n-i+1&&abs(i-1-cn1[n-i+2-j])<=d) //当前位选择1
				{
					if(!(j!=l0&&cn0[j+1]-i+2>d))
					{
						f[i-1][j]=(f[i-1][j]+f[i][j])%mod;
						g[i-1][j]=g[i-1][j]+g[i][j];
						g[i-1][j]=min(g[i-1][j],mod+1);
					}
				}
			}
//			;cout<<f[i-1][j+1]<<" "<<f[i-1][j]<<"\n";
		}
	}
	
	cout<<f[1][l0]<<"\n";
	
	for(int i=1;i<=n;i++)
	{
//		cout<<"\n"<<g[i+1][l0-1]<<" "<<k<<"\n";
		if(g[i+1][l0-1]>=k) // 如果当前位为0的方案多于k，就输出0，否则输出1
		{
			cout<<0;
			l0--;
		}
		else
		{
			cout<<1;
			k-=g[i+1][l0-1];
		}
	}
	
	return 0;
}
发表更新Problem Solutions11 分钟读完 (大约1576个字)

题解：[Apio2014]序列分割

其实下面的这个题是一个简化版本，原题要给dp数组开滚动数组，这个很简单就不写了；还有就是原题要输出方案，注释在代码里。

Luogu: [APIO2014] 序列分割

题面

题目描述

小H最近迷上了一个分隔序列的游戏。在这个游戏里，小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列，小H需要重复k次以下的步骤：

1.小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列）；

2.选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。

每次进行上述步骤之后，小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式，使得k轮之后，小H的总得分最大。

输入格式

输入第一行包含两个整数n，k（k+1≤n）。

第二行包含n个非负整数a1，a2，…，an（0≤ai≤10^4），表示一开始小H得到的序列。

输出格式

输出第一行包含一个整数，为小H可以得到的最大分数。

样例

样例输入
1
2
7 3 
4 1 3 4 0 2 3
样例输出
1
108

数据范围与提示

数据满足2≤n≤100000,1≤k≤min(n -1，200)。

注意，输入的a[i]里可能有0

解法

转移方程

$f[l][r][k]$: 将[l,r]这个区间，切k刀，所能得到的最大得分

$f[l][r][k]: \max_{i=1…n-1, j=0..k-1}f[l][i][j]+f[i+1][r][k-1-j]+(sum[r]-sum[i])*(sum[i]-sum[l-1])$

p.s. 当我们确定了最后切分出来的是哪些区间，我们的答案就是一样的

时间复杂度 $O(n^4)$

使用前缀和优化：

$f[m][i]$: 前 $a[1]..a[i]$ 分成m段，这前m段所贡献的最大得分和

记 $s[i]=\sum_{k=1..i}a[k]$

$f[m][i]=\max_{j=0..i-1} f[m-1][j]+(s[i]-s[j])*s[j]$

优化

法1：分离变量后使用单调队列

$s[i]$: 前缀和

$f[m][i]=\max_{j=0..i-1} f[m-1][j]+(s[i]-s[j])*s[j]$

从小到大枚举m，固定当前m，考虑到当前在计算f[m][i]:

假如有两个不同决策点j,k，尝试分析它们谁更优:

不妨设 j<k<i

对于当前的i，k比j更优等价于:

将j,k分到不等式一侧，i分到另一侧得：

$s[i]>(f[m-1][j]-f[m-1][k]-s[j]^2+s[k]^2)/(s[k]-s[j])$

记右式为 $g(j,k)$，左式为 $h(i)$

对于固定的m，有jg(j,k)$

三个决策点，易知，有 j1g(j2,h3)$ ，j2不会成为最优决策点，所以可以直接舍去

双端队列维护j[l]…j[r]从小到大，g函数也是从小到大的

对于任意 $l+1<=x<=r-1$ 有：$g(j[x-1],j[x])<g(j[x],j[x+1])$

1
2
3
4
5
6
7
8
9
10
//框架
for m=1..k
	queue q, l=r=1, q[1]=0
	for i=1..n
		while l+1<=r and h(i)>g(j[l],j[l+1])
			l++
		j[l]为决策点，更新dp[m][i]
		while l+1<=r and g(j[r-1],j[r])>g(j[r],i)
			r--
		j[++r]=i

然后我们可以解决本题

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
#include<bits/stdc++.h>

using namespace std;

#define ll long long
mt19937 rnd(time(NULL));

int n,k;
int a[100005];
ll s[100005];

int q[100005];
ll dp[100005][205];
//int pre[100005][205];

double g(int x,int y,int z)
{
	if(s[x]==s[y])
	{
		return -1e18;
	}
    return (double)(s[x]*s[x]-s[y]*s[y]-dp[x][z-1]+dp[y][z-1])/(s[x]-s[y]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	
	for(int j=1;j<=k;j++)
	{
		int l=1,r=1;
		q[1]=0;
		for(int i=1;i<=n;i++)
		{
			while(l<r&&g(q[l],q[l+1],j)<=s[i])
			{
				l++;
			}
            
//			pre[i][j]=q[l];
			dp[i][j]=dp[q[l]][j-1]+s[q[l]]*(s[i]-s[q[l]]);
			
			while(l<r&&g(q[r-1],q[r],j)>=g(q[r],i,j))
			{
				r--;
			}
			q[++r]=i;
		}
		
	}
	
	cout<<dp[n][k]<<"\n";
//	for(int x=n,i=k;i>=1;i--)
//	{
//		x=pre[x][i];
//		cout<<x<<" ";
//	}
    
	return 0;
}
法2：斜率优化（aka 数形结合）

$f[m][i]=\max_{j=0..i-1}f[m-1][j]+(s[i]-s[j])*s[j]$

=$f[m-1][j]-s[j]s[j]+s[j]s[i]$

$A(j)=f[m-1][j]-s[j]*s[j]$

$B(j)=s[j]$

$C(i)=s[i]$

相当于我们有若干个选项 j，每个j提供一个一次函数 y[j]

$y[j]=A(j)+B(j)*x$

对于所有 $y[0]..y[i-1]$，找一个最大的作为 $f[m][i]$ 的答案

此时我们维护若干个一次函数，要支持插入和求最大值

对于本题的特殊的单调性，即每次插入的 $B(j)$, $C(i)$ （斜率和横坐标）都是递增的

于是，我们可以用双端队列来维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//框架
struct line
{
	int a,b;
} q[];

for m=1..k
	q.clear(),l=r=1,q[1]为j=0代表的直线
	for i=1..n
		while l+1<=r and c(i)>q[l],q[r]交点的x坐标
			l++
		line lnew=i //决策点所代表的直线A(i)+B(i)*x
		while l+1<=r and q[r-1],q[r]交点x坐标>q[r]和lnew的交点x坐标
			r--
		q[++r]=lnew

与刚刚的单调队列优化相比，$g(j1,j2)$ => 交点x坐标 $h(i)$ => $C(i)$

此处也可以用维护凸壳来实现

一般地，给定dp方程

$f[i]=\max_{j=1..i-1} W(i,j)$

通过恒等变形，使其变成：

$W(i,j)=\frac{A(i)-B(j)}{C(i)-D(j)}$

这使得我们联想到了斜率公式

$k=\frac{Δy}{Δx}=\frac{y2-y1}{x2-x1}$

这样可以询问到一个点连到现有的点的斜率最大

  • 如何维护下凸线？

    如果每次加入点的x坐标是单调增的：和上面两种方法几乎一样的单调队列写法即可维护下凸线

  • 如何处理查询？

    对于给定的查询点，凸壳上的点到这个查询点的斜率是先严格单调增，（然后可能会恒等不变一段），然后再严格单调减的。

    在凸壳上使用三分法

斜率优化代码会长成这样：（其实长得跟上面的没什么区别qwq）

1
2
3
4
5
6
7
8
9
10
double slope(int a,int b)
{
	ll x1=-s[a],y1=dp1[a]-s[a]*s[a];
	ll x2=-s[b],y2=dp1[b]-s[b]*s[b];
	if(x1==x2)
	{
		return -1e18;
	}
	return (double)(y2-y1)/(x2-x1);
}
法3：二分队列

考虑一个dp方程 $dp[i]=\max_{j=1..i-1} W(i,j)$

对于某两个 $j1<j2$，如果在某个 $i$ 处 $j2$ 比 $j1$ 优，那么在更大的 $i$ 处 $j2$ 也一定比 $j1$ 优。

即满足强决策单调性：一旦一个后来者超过你，他就会一直超过你，所以随着i增大，最优决策点也严格单调增

而本题满足 $h(i) > g(j1, j2)$ ，可以使用二分队列的方法进行优化

考虑：每个决策点j，是哪些i的最优决策点

对于每个 $j$，它成为最优决策点的 $i$ 要么不存在，要么一定是一段连续的区间，记为 $[l_j,r_j ]$

对于 $ j1<j2$，且 $[l{j1},r{j1} ]$ 和 $[l{j2},r{j2} ]$ 都不为空，那么有 $r{j1}<l{j2}$

所有这些 $ [l_j,r_j ] $ 构成了 $[1, n]$ 的一个划分

我们尝试维护当前[0,i-1]间的最优决策区间：

但是那些>=i的决策点，未来可能“抢走”当前某个j的 $[l_j,r_j]$ 的一部分，因此当前某个j的 $[l_j,r_j]$ ，只有可能变小，不可能再变大。计算i的最优决策点后，因为只需要计算i往后的，所以我们只需要保留构成[i,n]的划分的那些$[l_j,r_j]$

也就是我们将维护若干个三元组(j,l,r)

然后在队列里二分就可以找到切分点了

发表更新Problem Solutions4 分钟读完 (大约660个字)

题解：洛谷P2568 GCD

最近在学欧拉函数，数学太烂，遂写一题解。

其实这个东西是我5月底咕咕写的，但是1整月了我还没发过东西，所以我今天来把这道题补完

洛谷

前言

欧拉函数

不会欧拉函数

好的，欧拉函数，AKA. Euler’s totient function，AKA. $\varphi(n)$ ，表示小于等于 $n$ 和 $n$ 互质的数的个数

这个 $\varphi(n)$ 是满足积性函数的性质的：

$\gcd(a,b)==1 \rightarrow \varphi(ab)=\varphi(a)\varphi(b)$

还有一些性质：

$n=\sum_{d|n} \varphi(d)$

$n=p^k \rightarrow \varphi(n)=p^k-p^{k-1}$

$n=\prod{i=1}^{s}p_i^{k_i} \rightarrow \varphi(n)=n\times\prod{i=1}^{s}\frac{p_i-1}{p_i}$

…

重点，是如何快速求出欧拉函数

现在我们处理好数组 $p[]$，表示一个范围内的质数（可以用欧拉筛）

若对于 $i$，如果已知所有的 $1−i$ 的 $\varphi $，枚举 $<=i$的质数 $p[j]$，可以求得 $\varphi (x×p[j])$

1.若 $p[j]$ 与 $x$ 互质 $\varphi (x \times p[j])=\varphi (x)\times\varphi (p[j])$

2.若不互质，设 $x=t\times p[j]^k$

$\varphi (x \times p[j])=\varphi (t \times p[j]^{k+1})=\varphi (t) \times \varphi (p[j]^{k+1})=\varphi (t) \times \varphi (p[j]^k) \times p[j]=\varphi (x) \times p[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
ll tot;
ll p[1000005];
bool pr[10000005];
ll phi[10000005];

void init(int n)
{
	phi[1]=1;
	for(ll i=2;i<=n;i++)
	{
		if(!pr[i])
		{
			p[++tot]=i;
			phi[i]=i-1;
		}
		for(ll j=1;j<=tot&&i*p[j]<=n;j++)
		{
			pr[i*p[j]]=1;
			
			if(i%p[j]==0)
			{
				phi[i*p[j]]=phi[i]*p[j];
				break;
			}
			else
			{
				phi[i*p[j]]=phi[i]*phi[p[j]];
			}
		}
	}
}

思路

根据题意知道：$\gcd(x,y)=p$为一个素数，因此：$\gcd(x/p,y/p)=1$，即 $x/p,y/p$ 是互质的，因此我们想到欧拉函数。

在原来板子的基础上进行一个前缀和的添加。

正常来说我们会进行一个双层枚举，枚举 $i,j$ 使得 $\gcd(i,j)=1$ 的情况，就相当于分别考虑 $i,j$ 的欧拉函数，对于 $i==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
#include<bits/stdc++.h> 

using namespace std;

#define ll long long

ll n;

ll tot;
ll p[1000005];
bool pr[10000005];

ll phi[10000005];

void init()
{
	phi[1]=1;
	for(ll i=2;i<=n;i++)
	{
		if(!pr[i])
		{
			p[++tot]=i;
			phi[i]=i-1;
		}
		for(ll j=1;j<=tot&&i*p[j]<=n;j++)
		{
			pr[i*p[j]]=1;
			
			if(i%p[j]==0)
			{
				phi[i*p[j]]=phi[i]*p[j];
				break;
			}
			else
			{
				phi[i*p[j]]=phi[i]*phi[p[j]];
			}
		}
	}
	for(ll i=1;i<=n;i++) //前缀和
	{
		phi[i]+=phi[i-1];
	}
}

ll ans;

int main()
{	
	ios::sync_with_stdio;
	cin.tie(0),cout.tie(0);
	
	cin>>n;
	
	init();
	
	for(ll i=1;i<=tot;i++)
	{
		ans+=2*phi[n/p[i]]-1; //会重复算gcd(i,i)的情况所以-1
	}                                                  
	
	cout<<ans<<"\n";
                       
	return 0;
}

Abalabakabala…

发表更新Problem Solutions3 分钟读完 (大约376个字)

题解：洛谷P4101 [HEOI2014] 人人尽说江南好

博弈论的代码是这样的，别的算法只要考虑码力和思维，而博弈论要考虑的就多了

洛谷

思路

n堆石子，每堆数量不超过m

当n<=m，n为偶数先手赢，否则后手

当n>m，与上述同理，所以两方都希望最终合并次数变成奇数/偶数，假如现在轮到先手操作，先手还没动，这个时候最长合并次数为偶数次，那么先手有两种可能性，把后面一个堆丢进大堆里面，这样后手再丢一个小堆进去，或者把后面两个堆合成一个，无论怎么做，后手都能保证每轮完了之后，大堆的石子会增加两个，那么合并次数也会-2，一直保持为偶数，而这种方式使得合并次数最多。

那么先手一定会把小堆合并到一个大堆里，直到这一堆变成m个，所以最后的结果就会变成若干堆m个石子和一堆n%m个石子，总共要合并 $(n/m)*(m-1)+(n\%m?(n\%m-1):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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

int t,n,m;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		ll ans=(n/m)*(m-1)+(n%m!=0)*(n%m-1);
		cout<<(ans&1?0:1)<<"\n";
	}

	return 0;
}

Very good Game Theory…

发表更新Problem Solutions3 分钟读完 (大约451个字)

题解：洛谷P1337 [JSOI2004] 平衡点 / 吊打XXX

玄学算法，但是有必要知道一下以便日后骗分（）

太幽默了。

洛谷

模拟退火

Simulated annealing - Wikipedia

模拟退火算法 - 百度百科

首先这个算法名字就很魔性，还要根据什么固体退火原理，听不懂（bu

其次我们发现这是一个叫做玄学的东西，它的精度会对它的结果和时间复杂度有所影响

思路

使用模拟退火，因为我觉得这就是模拟退火模板题。

代码

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
#include<bits/stdc++.h>

using namespace std;

struct node
{
	int x,y,w;
} a[10005]; //记录坐标
int n; 

double potential_energy(double nowx,double nowy) //计算势能总和
{
	double sum=0;
	for(int i=1;i<=n;i++)
	{
		double delx=nowx-a[i].x;
		double dely=nowy-a[i].y;
		sum+=(sqrt(delx*delx+dely*dely))*a[i].w;
	}
	return sum;
}

double xans,yans;
double ans=1e18+7,t;
const double delta=0.993; //降温速度

void simulate_anneal()
{
	double xx=xans;
	double yy=yans;
	t=1926; //初始温度，设置成一个比较大的数即可
	while(t>1e-14) //精度
	{
		double xtemp=xans+(rand()*2-RAND_MAX)*t; //随机位置
		double ytemp=yans+(rand()*2-RAND_MAX)*t;
		
		double new_ans=potential_energy(xtemp,ytemp); //势能和与当下最小势能和的差
		double del=new_ans-ans;
		if(del<0) //
		{
			xx=xtemp;
			yy=ytemp;
			xans=xx;
			yans=yy;
			ans=new_ans;
		}
		else if(exp(-del/t)*RAND_MAX>rand()) //exp表示e的x次幂，这里就是求概率
		{
			xx=xtemp;
			yy=ytemp;
		}
		t*=delta; //降温
	}
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].w;
	}
	
	simulate_anneal(); //多跑几遍（
	simulate_anneal();
	simulate_anneal();
	
	printf("%.3lf %.3lf\n",xans,yans);
	
	return 0;
}

关于二分

看到 JSOI2004]平衡点 / 吊打XXX - 洛谷专栏 (luogu.com.cn) 这个题解用的是二分，先放在这里吧，回头搞一下咩~

发表更新Problem Solutions2 分钟读完 (大约268个字)

题解：洛谷P6078 [CEOI2004] Sweets

这是一道紫题！

我们需要接触一个叫做生成函数的登西。

洛谷

思路

对于至少 $a$ 个，不超过 $b$ 个的限制，可以先求出限制不超过 $b$ 个的方案数，然后减去限制不超过 $a-1$ 个的方案数，即为答案。

对第 $i$ 个糖果罐列出其的生成函数，得：

因此，设答案为G(x):

代码

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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll mod=2004;

ll n,a,b;
ll c[15];

ll C(ll x,ll y)
{
	if(y>x)
	{
		return 0;
	}
	
	ll ans=1,ans1=1;
	
	for(ll i=1;i<=y;i++)
	{
		ans1*=i;
	}
	for(ll i=x;i>x-y;i--)
	{
		ans=(ans*i)%(mod*ans1);
	}
	
	return ans/ans1;
}

ll dfs(ll x,ll y,ll sum)
{
	if(x>n)
	{
		return y*C(sum+n,n)%mod;
	}    
	                     
	return (dfs(x+1,y,sum)+dfs(x+1,-y,sum-c[x]-1))%mod;
}
                                                
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	                         
 	cin>>n>>a>>b;                 
	                                 
	for(ll i=1;i<=n;i++)
	{
		cin>>c[i];                
	}                                           
	
	cout<<((dfs(1,1,b)-dfs(1,1,a-1))%mod+mod)%mod<<"\n";
	
	return 0;                                            
}

咕了，学不懂数学

发表更新Problem Solutions2 分钟读完 (大约275个字)

题解：洛谷P8207 [THUPC2022 初赛] 最小公倍树

巩固一下最小生成树的Kruskal算法（）

洛谷

思路

首先如果我们将完全图的所有边都存下来，最多需要 $(R-L)^2$ 条边，时空复杂度皆到了 $10^{10}$

所以我们选择在存边的部分进行优化

首先对于两个点，它们连边的权值为 $lcm(u,v)$ ，这意味着当 $gcd(u,v)$ 越大，权值越优

因此，对于每一个 $i\in{[1,R]}$，我们枚举它符合在 $[L,R]$ 区间内的倍数存下来

然后套kruskal板子即可

代码

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<bits/stdc++.h>

using namespace std;

#define ll long long

ll l,r;
ll par[1000005];

struct edge
{
	ll u,v,w;
};

vector<edge> e;

ll find(ll x)
{
	return par[x]==x?x:par[x]=find(par[x]);
}

bool cmp(edge a,edge b)
{
	return a.w<b.w;
}

ll n,m;
ll ans;

void kruskal()
{	
	for(ll i=0;i<e.size();i++)
	{
		ll u=find(e[i].u),v=find(e[i].v);
		
		if(u==v)
		{
			continue;
		}
		
		ans+=e[i].w;
		par[u]=v;
	}
	
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	cin>>l>>r;
	
    for(ll i=l;i<=r;i++)
	{
		par[i]=i;
	}
    for(ll i=1;i<=r;i++)  //存边
	{
        ll v=ceil(l*1.0/i)*i; //不小于L的第一个i的倍数
        for(ll j=v;j<=r;j+=i)
		{
            if(j!=v) //非自环
			{
				e.push_back({v,j,v*j/__gcd(v,j)});
			}
        }
    }
    
    sort(e.begin(),e.end(),cmp);
    
    kruskal(); //板子
    
    cout<<ans<<"\n";
    
	return 0;
}

Finished…

发表更新Problem Solutions3 分钟读完 (大约501个字)

题解：洛谷P8074 [COCI2009-2010#7] SVEMIR

虽然这是一道幽默的绿题，但是博主打AtCoder发现自己竟然不会写最小生成树，遂有此文

洛谷

前言

最小生成树

首先来看一下Kruskal最小生成树算法

【模板】最小生成树

将所有的边存下来，并按长度排序

用并查集存储两个点是否在同一棵树上，是则跳过；不是则合并，并将答案加上边长

代码

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>

using namespace std;

#define ll long long

ll n,m;
ll cne; //生成树的边数 

struct edge
{
    ll u,v,w;
}e[2000005];

ll par[100005];
ll ans;
bool f; //是否能够生成 

ll find(ll x) //找根 
{
    return (par[x]==x)?x:par[x]=find(par[x]);	
}

bool cmp(edge a,edge b) //排序 
{
    return a.w<b.w;
}

void kruskal() //kruskal 
{
    
    for(ll i=1;i<=m;i++) //循环每一条边 
    {
        ll u=find(e[i].u),v=find(e[i].v);
        if(u==v) //同根则跳过 
        {
        	continue;
        }
		
        ans+=e[i].w;    
        par[u]=v; //合并 
        cne++;
        if(cne+1==n) //如果边数为点数-1，就结束 
		{
			f=1;
			break;
		}
    }
} 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
    cin>>n>>m;
    for(ll i=1;i<=n;i++) //init 
	{
		par[i]=i;
	}
    for(ll i=1;i<=m;i++)
    {
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    
    sort(e+1,e+m+1,cmp);
    
    kruskal();
    
	if(f==0)
	{
		cout<<"orz\n";
		return 0;
	}
	
    cout<<ans<<"\n";
    
    return 0;
}

思路

本题在上边的Kruskal模板上进行一个减边的优化即可

每个星球用三维坐标 $(x_i,y_i,z_i)$ 来表示，而在两个星球 $A,B$ 之间建造隧道的价格为 $\min{|x_A-x_B|,|y_A-y_B|,|z_A-z_B|}$。

所以考虑三个点 $a, b, c$ $(a_x<b_x<c_x) $ 此时连接 $ab$, $bc$ 更优，意思是说，我们会连的边一定是相邻的

代码

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>

using namespace std;

#define ll long long

ll n,m;
ll cne;

struct edge
{
    ll u,v,w;
} e[2000005];

struct node
{
	ll x,y,z,id;
} a[2000005];

ll par[100005];
ll ans;

ll find(ll x)
{
    return (par[x]==x)?x:par[x]=find(par[x]);	
}

bool cmp1(node a,node b) //以三种坐标分别排序找相邻
{
    return a.x<b.x;
}
bool cmp2(node a,node b)
{
    return a.y<b.y;
}
bool cmp3(node a,node b)
{
    return a.z<b.z;
}

bool cmp(edge a,edge b)
{
    return a.w<b.w;
}

int dis(int x,int y)
{ 
	return min(abs(a[x].x-a[y].x),min(abs(a[x].y-a[y].y),abs(a[x].z-a[y].z)));
}

void kruskal()
{
    
    for(ll i=1;i<=m;i++)
    {
        ll u=find(e[i].u),v=find(e[i].v);
        if(u==v)
        {
        	continue;
		}
		
        ans+=e[i].w;    
        par[u]=v; 
        cne++;
        if(cne+1==n)
		{
			break;
		}
    }
} 

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
    cin>>n;
    for(ll i=1;i<=n;i++) //init 
	{
		par[i]=i;
	}
    for(ll i=1;i<=n;i++)
    {    	
        cin>>a[i].x>>a[i].y>>a[i].z;
		a[i].id=i;
    }
    
    sort(a+1,a+n+1,cmp1);
    for(ll i=1;i<n;i++)
    {
    	e[++m].u=a[i].id;
    	e[m].v=a[i+1].id;
    	e[m].w=dis(i,i+1);
	}
	
	sort(a+1,a+n+1,cmp2);
    for(ll i=1;i<n;i++)
    {
    	e[++m].u=a[i].id;
    	e[m].v=a[i+1].id;
    	e[m].w=dis(i,i+1);
	}
	
	sort(a+1,a+n+1,cmp3);
    for(ll i=1;i<n;i++)
    {
    	e[++m].u=a[i].id;
    	e[m].v=a[i+1].id;
    	e[m].w=dis(i,i+1);
	}
    
    sort(e+1,e+m+1,cmp);
    
    kruskal();
    
    cout<<ans<<"\n";
    
    return 0;
}
发表更新Problem Solutions4 分钟读完 (大约527个字)

题解：洛谷P1041 [NOIP2003 提高组] 传染病控制

感觉我题解越写越水（？？？

受不了，博主开始写错题题解了。。。

洛谷

思路

虽然看到了一坨DP和随机化解法但是不如dfs！

你看那小小的 $n$ 小小的（只有 $300$），所以爆搜甚至不用剪枝

感觉思路也不是非常非常非常困难，dfs算一下最多的不被感染人数再用总数减一下即可

代码

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
#include<bits/stdc++.h>

using namespace std;

struct node
{
	int u,v;
}a[1005];
int head[1005];
int tot;

int dep[1005],chd[1006],par[1005]; //深度，子节点数，父节点 
int cnd[1005]; //i深度下的第几个点 
int cnt[1005][1005]; //深度为i的第j个点 
bool vis[1005]; //是否感染（0为是，1为否）
//这里是因为在感染时考虑一个点如果未被感染，它的子节点不会被感染，求出最大不感染数 

void add(int u,int v) //链式前向星建图 
{
	a[++tot].u=head[u];
	head[u]=tot;
	a[tot].v=v;
}

void getc(int u,int f,int d) //预处理深度子节点和父节点 
{
	dep[u]=d;
	chd[u]=1;
	par[u]=f;
	
	for(int i=head[u];i;i=a[i].u) //直接dfs 
	{
		int v=a[i].v;
		if(v==f)
		{
			continue;
		}
		getc(v,u,d+1);
		chd[u]+=chd[v];
	}
}

void dfs(int u,bool f) //通过dfs来进行不感染或还原（f为1不感染，f为0还原） 
{
	for(int i=head[u];i;i=a[i].u)
	{
		int v=a[i].v;
		vis[v]=f;
		
		if(v==par[u])
		{
			continue;
		}
		
		dfs(v,f);
	}
}

int ans,ans1;

void solve(int d) //算出最多的不感染数 
{	
	for(int i=1;i<=cnd[d];i++) //循环每一个深度 
	{
		if(vis[par[cnt[d][i]]]==1)
		{
			continue;
		}
		
		dfs(cnt[d][i],1); //以该深度的第i个点往下不感染 
		ans+=chd[cnt[d][i]];
		solve(d+1); //下一层 
		ans-=chd[cnt[d][i]]; //还原 
		dfs(cnt[d][i],0);

	}
	
    ans1=max(ans,ans1);
	
}

int n,p;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>n>>p;

	for(int i=1;i<=p;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v),add(v,u);
	}

	getc(1,0,1);
	for(int i=1;i<=n;i++)
	{
		cnt[dep[i]][++cnd[dep[i]]]=i;
	} //预处理 
	
	solve(2); //从第二层开始循环 
	
	cout<<n-ans1<<"\n";

	return 0;
}

发现泄题解还是很水。。。

发表更新Problem Solutions1 分钟读完 (大约201个字)

题解：洛谷P3403 跳楼机

洛谷

同余最短路，话说博主图论很烂，所以来做一下

虽然用了被嘲讽的已经死掉的SPFA，但是其实我觉得SPFA没那么好卡

思路

代码

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<bits/stdc++.h>

using namespace std;

long long h,x,y,z;
long long d[5];
queue<long long> q;
long long dis[100005];
bool vis[100005];

void spfa()
{
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	
	q.push(1);
	dis[1]=1;
	vis[1]=1;
	
	while(!q.empty())
	{
		long long x=q.front();
		q.pop();
		for(long long i=2;i<=3;i++)
		{
			long long y=(x+d[i])%d[1];
			if(dis[y]>dis[x]+d[i])
			{
				dis[y]=dis[x]+d[i];
				if(!vis[y])
				{
					vis[y]=1;
					q.push(y);
				}
			}
		}
		vis[x]=0;
	}
}

long long query(long long x)
{
	long long ans=0;
	for(long long i=0;i<d[1];i++)
	{
		if(x>=dis[i])
		{
			ans+=(x-dis[i])/d[1]+1;
		}
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>h>>d[1]>>d[2]>>d[3];
	sort(d+1,d+4);
	if(d[1]==1||d[2]==1||d[3]==1)
	{
		cout<<h<<"\n";
		return 0;
	}
	
	spfa();
	
	cout<<query(h)<<"\n";

	return 0;
}

Finished…

发表更新Problem Solutions2 分钟读完 (大约356个字)

题解：洛谷P2278 [HNOI2003] 操作系统

由于太弱开始写一些绿题及以上的单题题解

说实话我觉得这身为一道蓝题并不是非常的难qwq

洛谷

思路

题目明摆着“选择优先级最高的先运行”，于是非常一眼的优先队列

直接蠢蠢地模拟即可

（STL模拟水题真好玩（？

代码

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
#include<bits/stdc++.h>

using namespace std;

struct node
{
	int id,st,len,lv; //任务序号，开始时间，长度，优先级，就是输入的部分
    
	bool operator <(const node &a) const //先按优先级排列，否则按开始时间，题目要求
	{
		if(lv==a.lv)
		{
			return st>a.st;
		}	
		else
		{
			return lv<a.lv;
		}
	}
} tsk;

long long tot;
priority_queue<node>q;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	while(cin>>tsk.id>>tsk.st>>tsk.len>>tsk.lv)
	{
        //可以在这个任务开始之前做完的任务先按优先级做完
		while(!q.empty()&&tot+q.top().len<=tsk.st)
		{
			node t=q.top();
			q.pop();
			tot+=t.len;
			cout<<t.id<<" "<<tot<<"\n";
		}
		
        //如果还有未做的任务不能做完，先做一半，再放回去
        //下一轮循环，如果该任务仍然优先级最高，就继续做
		if(!q.empty())
		{
			node t=q.top();
			q.pop();
			t.len=t.len-tsk.st+tot;
			q.push(t);
		}
		
		q.push(tsk); //将新任务放进队列
		tot=tsk.st;
	}
	
    //将剩余任务做完
	while(!q.empty())
	{
		node t=q.top();
		q.pop();
		tot+=t.len;
		cout<<t.id<<" "<<tot<<"\n";
	}
	
	return 0;
}

就没了。

蓝题欸。。。

发表更新Problem Solutions3 分钟读完 (大约398个字)

题解：洛谷P4424 [HNOI/AHOI2018] 寻宝游戏

洛谷首黑（虽然很水，并且小小地借助了题解），所以写一下题解作为巩固

洛谷

思路

非常容易注意到，对于位运算：

  • 当你把某一位的数 $and$ $0$ ，就相当于把这一位数赋值为 $0$
  • 当你把某一位的数 $or$ $1$ ，就相当于把这一位数赋值为 $1$
  • 当你把某一位的数 $and$ $1$ 或者 $or$ $0$ 时，这一位的值不变

所以若要使最终某一位为 $0$，最后一个 $and$ $0$ 要出现在 $or$ $1$ 后面；为 $1$ 同理

后面这个转化借助了一下 StudyingFather 大神的题解思路：

我们设操作序列中 $or=0$ ，$and=1$ ；数字序列从下往上看得到的数为 $x$ ，操作序列从下往上看得到的数为 $y$

这样就将条件转化成：运算最后结果为 $0$ ，当且仅当 $x≤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
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
#include<bits/stdc++.h>

using namespace std;

const long long mod=1000000007;

long long n,m,q;
string a[1005];

struct node
{
	string s;
	long long id;
	
	bool operator <(const node &a) const  //字典序排序
	{
		if(s!=a.s)
 		{
			return s>a.s;
		}
		return id<a.id;
	}  
} p[5005];
long long ans[5005];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>n>>m>>q;
	for(long long i=1;i<=n;i++)
	{
		cin>>a[i];
		for(long long j=0;j<m;j++)
		{
			a[i][j]-='0';
		}
		a[i][m]=1;
	}
	
	for(long long i=0;i<=m;i++)
	{
		p[i].id=i;
		for(long long j=n;j;j--)
		{
			ans[i]=(ans[i]*2+a[j][i])%mod;
			p[i].s+=a[j][i]; //预处理 
		}
	}
	
	ans[m]++;
	sort(p,p+m+1);
	p[m+1].id=m+1;
	
	while(q--)
	{
		string r;
		cin>>r;
		long long id1=0,id2=m+1;
		
		for(long long i=m;i;i--) //找上下界 
		{
			if(r[p[i].id]=='1')
			{
				id1=i;
				break;
			}
		}
		for(long long i=0;i<=m;i++)
		{
			if(r[p[i].id]=='0')
			{
				id2=i;
				break;
			}
		}
		
		if(id1>id2)
		{
			cout<<0<<"\n";
		}
		else
		{
			cout<<(ans[p[id1].id]-ans[p[id2].id]+mod)%mod<<"\n";
		}
	}
	
	return 0;
}
发表更新Problem Solutions3 分钟读完 (大约418个字)

题解：CF1926E Vlad and an Odd Ordering

多么美丽的一道找规律啊！

ps：鄙人太烂了，所以只能写这种入门题的题解。

思路

这道题面非常诈骗，因为只有在奇数的 $2$ 的幂倍时才会有牌被铺开，简易证明如下（十分简单会的可以跳过）：

设 $k=2^n×(2m+1)$ ，因此 $x=k×(2y +1)$，其中 $n,m,y∈ \mathbb {N}$ 。

当且仅当 $m=0$ 时，$k=2^n$，否则 $k>2^n$ 且 $k$ 不为2的幂。

所以

又因为当$m≠0$时，$k>2^n$，所以$x$一定已经被铺开过了，该次操作无效。

所以当且仅当在奇数的 $2$ 的幂倍时才会有牌被铺开。

我们不妨来模拟一下：

设共有7张牌：$[1,2,3,4,5,6,7]$

第一次铺开奇数（即 $2^0×$ 奇数）得到 $[1,3,5,7]$，剩下$[2,4,6]$ ；

第二次铺开 $2^1×$ 奇数 得到 $[2,6]$，剩下$[4]$ ；

第三次铺开 $2^2×$ 奇数 得到 $[4]$，没有剩下。

显而易见，第$n$次会铺开$2^{(n-1)}+2^n×m$，其中 $m∈ \mathbb {N}$，$m+1$表示铺开的是这轮操作里的第$m+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
#include<bits/stdc++.h>

#define mian main() 

using namespace std;
 
int t;
long long n,k;
 
int mian
{
	cin>>t;
	while(t--)
	{
		cin>>n>>k;

		int cnt=0; //cnt 表示这是2的cnt次幂
		while(1)
		{
			long long a=(n+1)/2; //a 表示本次会铺开的牌数
			if(a>=k)
			{
				long long ans=(k-1)*(pow(2,cnt+1))+pow(2,cnt);
				cout<<ans<<"\n";
				break;
			}
			cnt++;
			n-=a;
			k-=a; 
		}
	}
 
	return 0;
}
关注我

链接

分类

最新文章

归档

标签

Combinatorics1
Disjoint Set1
Dynamic Programming3
Euler's totient function1
Game Theory1
Graph Theory2
Monotonic queue1
Number theory1
Ordinary Generating Function1
Segment Tree4
Simulated Annealing1
Society1
Spanning Tree2
Teenagers1
Tree1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.

follow.it

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×