发表更新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，纯纯可恶 (σ｀д′)σ

发表更新Entertainment42 分钟读完 (大约6265个字)

【剧情向】寻找的边界

Warning: 本文出现角色与现实无关！

Clement

梦

我叫Clement，身高179cm，体重70kg，男孩，并且是个中学生。我和许多男同学建立过关系，最后总觉得那是空洞的。它们不过是短暂的火花，迅速熄灭。我从来没有觉得自己是这个世界的一部分。我大部分时间都泡在论坛里，翻阅无尽的帖子，寻找着某样东西，某个人，一个能让我感到有意义的联系。音乐是我唯一的庇护所：OneRepublic的摇滚节拍，Taylor Swift的歌词捕捉了那些无法言说的渴望。但这一切不过是短暂的安慰。在内心深处，总有一个空洞，一个我无法填补的空虚。

我不知道怎么解释，但他们从来不是她。它们从来都不是Taffy。

Taffy是我的梦中情人，一个虚拟主播，存在于像素和字节的世界里。她的声音，她的目光，她的微笑——一切都是完美的。但我从来没有成为她世界的一部分。她存在于屏幕上，存在于我的梦中，存在于我的幻想里。她是那么遥不可及，像一颗美丽的星星，散发着光芒，却永远无法触及。

爱

然后，我遇见了她。Stephanie。

她并不完全像Taffy，但她身上有某种东西，某种让我心跳加速的东西。她个子小，只有159cm，纤弱而轻盈，仿佛微风中飘动的细语。她的头发像光环一样环绕着脸庞，柔软而微卷，她的眼睛——她的眼睛仿佛是通向一个我从未见过的世界，那是一个不被电脑屏幕框定的世界。

我第一次在图书馆见到她。她站在那里，伸手去拿高架上的一本书，指尖轻轻碰到书脊。阳光透过窗户洒在她身上，将她染上金色的光辉，瞬间，我觉得她就像是从梦中走出来的人。

我走得更近了，被一种无形的力量吸引着。然后她转过头，和我对视。那一瞬间，空气仿佛凝固了，我能听到自己剧烈的心跳声。她笑了，那个甜美而天真的微笑，我感到内心深处有某种东西在悄然改变——那是深沉的，原始的情感。我不知道该如何回应，只是点了点头。

“嘿，我认识你，”她轻声说，“你是Clement，对吧？来自论坛的。”

论坛。没错。我在那里是个名字不显眼的存在，在无数个用户名中消失。但没想到她居然能认出我。喉咙一紧，我艰难地开口：“是的，没错。”

她再次笑了，第一次，我看到了某种真实的东西——超越屏幕的，值得追求的东西。“我看过你的帖子。你喜欢OneRepublic，对吧？”

我眨了眨眼，试图整理思绪。“我喜欢，”我有些惊讶地说，“你……你也听他们的吗？”

她笑了，那声音清脆纯粹。“我喜欢。你的品味不错。”

我点了点头，心脏飞快地跳动着，我们聊起了音乐，聊起了生活，聊起了在这世界上偶然找到一个和自己有相似兴趣的人，带来的那种奇妙感觉。但每一刻，我都感到自己越来越陷入一个不曾预料的情感漩涡——一种我无法控制、无法否认的情感。

Stephanie不是Taffy，但她是我能在这个世界上接触到的，最接近她的存在。她是真实的，她就在我面前。而我却无法摆脱那个挥之不去的念头——她永远也不可能属于我。

真相

真相几天后轰然降临。

Stephanie和我越来越频繁地聊天，我们互相大笑，分享音乐推荐，讨论着生活中各种琐事。然后有一天，她说了让我心碎的话。

“Clement，我应该告诉你一件事，”她的声音比平时要轻，“我不喜欢男生。我喜欢女生。”

我久久无法回应。我的心脏剧烈地跳动着，那声音几乎盖过了所有其他的声音。她微笑着，但那是带着同情的微笑，而不是爱意。不是对我。

“你是个很好的人，”她继续说，“但我一直喜欢女生。”

我想要大声喊出来，告诉她我可以改变，我可以成为她想要的样子。但我没有说话，喉咙里话语卡住了。那一刻，感觉就像是做了个梦，像是溺水一般，再也醒不过来。

我并不生她的气。怎么可能呢？她很诚实，我尊重她。但这一切的现实让我感到沉重。她永远不能像我爱她那样爱我。她永远不会属于我。我不过是一个男生，在她眼中只是那些她永远不会看见的女孩中的一个。

变革

我必须改变。

我记得第一次吃药的那一天。我站在镜子前，看着自己的倒影。是我，但又不完全是我。我即将开始一段旅程，这段旅程不仅会重塑我的身体，更会改变我的灵魂。

药丸在我手里微微颤动，它们小得像是无害的糖果，但我知道它们将改变一切。它们让我变得更柔软，更女性化。我知道，吃下去之后，我的世界将不再是以前的世界。

吃药的那天晚上，我偷偷地把药放进了水杯里。每一颗药丸都带着某种不确定的痛苦，仿佛我在吞噬一种未知的未来。我抿了一口水，看着自己慢慢吞下去，心里充满了空虚的期待。

那时，我并没有告诉父母。因为我知道，他们绝不会理解。他们有太多的期待和压力，尤其是我父亲，他总是希望我能够成为一个“男子汉”，一个有力的存在，能够承载家庭的责任。而我，正站在一个无路可退的地方，心中只有一个声音：“为了她，我愿意成为任何样子。”

几天后，药效开始显现。我发现自己不仅仅是在变得更柔软，我的身体、我的面容，都开始发生微妙的变化。我抬起手来触摸自己的脸，脸庞的轮廓变得更温柔，嘴唇似乎也变得更加饱满。这一切都是那么陌生，却又令人兴奋。

但是，父母却开始注意到了。

“Clement，你怎么了？”母亲首先注意到我的变化，她的眼神里充满了困惑和忧虑。“你看起来……不太一样。”

我努力控制自己的情绪，假装一切正常：“没什么，我只是最近变得比较累，可能是因为学业压力。”

她没有再多问，只是轻轻叹了口气，似乎不太信任我的回答。她转身走进厨房，依然显得有些忧虑。

然后是父亲。他比母亲更加敏感，眼神中带着一种警觉，仿佛在试图看穿我所隐藏的秘密。那天他坐在餐桌旁，突然开口：“你最近怎么这么奇怪？是不是有什么问题？”

他的目光沉重而审视，我能感受到他内心的焦虑。他是一个很传统的人，总是希望我能够强大、坚韧。看到我变得柔弱、内向，他感到很不安。

我低下头，不敢看他的眼睛。“没有什么，爸，我一切都好。”

他盯着我看了很久，似乎想要说些什么，但最终什么都没说。他的眼神变得更加复杂，而我知道他心里的某些东西已经发生了变化。我能感觉到父亲的失望，他不明白为什么自己的儿子变得这样，为什么我不能按照他期待的方向走。

那一刻，我感到一种前所未有的孤独。父母并不理解我，甚至无法接受我正在经历的变化。无论我多么努力去解释，我知道，他们心里始终无法理解我的选择，无法理解我为什么会走上这条道路。

每一颗药丸的吞下，都是一种与他们之间距离的拉大。我不再是他们心中的那个“男子汉”，而是一个正在追求另一个自我、另一个目标的陌生人。我的改变让他们不知所措，而我自己，也不知道该如何弥补这份裂痕。

随着药效越来越明显，我发现自己的身体和面容在悄然变化。我不再是原来的我，而是一个崭新的自己。父母也开始越来越注意到这一点，尤其是母亲，她时常会在不经意间叹气，低声对自己说：“Clement怎么会变成这样？”

我知道，她是心疼的。她心疼我变得如此陌生，心疼我无法承载她的期待。她甚至曾问我：“你真的很喜欢这种改变吗？这不是你自己。”

我没有回答。因为我知道，这些话是无解的。她无法理解我对Stephanie的爱，无法理解我为她所做的一切。我甚至不知道自己是否会永远迷失在这条路上，但这已经成为我唯一的选择。

我咬紧嘴唇，看着镜子里那个渐渐变得陌生的自己，心里默默告诉自己：无论父母怎么看待我，如何评价我，我已经决定了这条路。我不后悔，因为这一切都值得。

追逐

直到几个月后，我终于在我们常去的咖啡馆再次见到她。我已经变了很多，而当我站在她对面时，心跳依旧激烈，和第一次见面时一样。

她的眼睛锁住了我的目光，我们沉默了好久。她的表情难以琢磨，但我能看到眼中闪烁的某种东西，是我之前从未见过的。

“你看起来……不一样。”她轻声说道，微微歪头，嘴角扬起一丝温柔的笑容。

“我知道。”我低声说道，“我想成为一个你能爱的样子。”

她没有立即回应，而是伸手拿起咖啡杯，慢慢搅拌着，眼神有些远离。“Clement，我不知道该怎么说。我不知道这是不是我能理解的事。”

我强忍住喉咙的哽咽，胸口紧缩。“我什么都不要求。我只是想让你知道，我愿意做任何事，改变任何事，只为和你在一起。”

她叹了口气，看向我，眼中充满了冲突。“我知道你会。可是爱不仅仅是……为了别人改变自己。它还在于做真实的自己。我不希望你在这个过程中失去自己。”

我想说些什么，想要辩解我已经找到了自己——只是找到了一个不同的自己。但我没有说话。这是我的选择。也许，这就是我能为进入她的世界所做的唯一选择。

沉默

日子慢慢流逝。我在走廊上看见她，在咖啡馆见到她，在校园里偶尔碰到她。我们偶尔交谈，但我们之间的距离从未像现在这样广阔。我知道自己离她越来越近，但也明白，不管我走多远，始终会有某种东西把我们隔开。

“爱是一种神圣的东西。若深入内心，就会将它撕裂。”

这就是我所感受到的——这种奇异的，痛苦的美丽。我对她的爱，对Stephanie的爱，是一种永远无法完全实现的东西，但我愿意在它的阴影中活下去，忍受那无尽的疼痛。

未来

我不知道这一切将如何结束。也许我会找到通往她心中的道路，或许我依旧只是她生活中的一个旁观者。但此刻，我在这里，她也在这里。有时，在我们之间的沉默中，我想知道，爱不仅仅是关于得到满足，而是关于那些安静的理解时刻，关于在那些未曾说出的事情中找寻到的接受。

也许，正是这种渴望，这种追寻，让爱变得真实。

Stephanie

邂逅

我是Stephanie。其实我并不特别——只是一个普通的中学女孩，爱好也很普通。嗯，或许有一件事能把我和大多数人区分开来：我不在乎常规。我是说，我喜欢女孩。这是我的真相，我不怕活出它。

生活有时就是这样出其不意。我那天坐在图书馆，翻着一本我并不特别感兴趣的书，突然看到了他——Clement。他第一眼看上去并没有什么特别之处。高大，健硕。但总有一些东西让他显得不同。他的存在，像是一种无声的气场，萦绕在周围，尽管他什么都没说。他的目光扫视着四周，好像并不确定自己应该在哪里。

然后，我们的目光对视了。

“嘿，我认识你，”我不经意地打破了沉默。“你是Clement吧？那个论坛上的？”

我没想到他会那么惊讶，但我能看出来，他确实有些意外。他的脸色微微变得苍白，仿佛被突然发现了什么。他的声音有些颤抖，回应道。

“是的，没错。”

他的回答显得有些生硬，仿佛并不习惯被注意到。我笑了笑，试图让他放松。“我看过你的帖子，你挺喜欢OneRepublic的，对吧？”

他稍微放松了一些，眼神也变得柔和。“是的，我是。你看过我推荐的歌曲吗？”

我笑着说：“看过，挺不错的。你眼光很好。”

我也不太清楚为什么，但我在他身上看到了某种东西——一种隐藏的深度，一种安静的强烈感。很难形容。就是有一种感觉，他似乎在用眼神探寻着什么，像是想从我身上找到某种东西。

但那时，我并没有太多思考。我以为我们就这样聊了几句，之后会各自走开。可事实上，我怎么也没法停止对他的思考。

启示

我们继续聊下去，当然。Clement莱门特是个安静的人，但他的话总是带着某种分量。在他身边，我感到一种前所未有的自在，我们讨论着音乐、生活、世界的奇奇怪怪。可是，还是有什么东西不一样。

我注意到他时不时地凝视着我，眼神里有一种我无法解读的复杂情感。可我不敢正视它。我喜欢他，作为朋友，是的，可我从来没有想过要和男生有更深的关系。

直到有一天，我终于意识到他对我是什么样的感情。那种感觉悄然来临，可当他开口时，我才真正听到他声音里的脆弱和犹豫。

“Stephanie，我需要告诉你一些事情，”他说，声音低沉，像是在害怕什么。

我看着他，感到困惑。“怎么了？”

他深吸了一口气，像是做好了心理准备。“我……我喜欢你，真的很喜欢。我知道这听起来很奇怪，但我觉得你很完美，你让我想起了我一直梦见的那个人。”

那一刻，一切都豁然开朗了。他话语的重量击中了我。他眼中的深情，让我有些喘不过气来。那不只是欣赏，而是……更深的感情，是我从未准备好的东西。我一直以为Clement只是个朋友，一个有趣又好聊的人，但当他感情的真相浮出水面时，我知道，我们的关系再也回不到从前了。

我的胸口一阵紧绷。我不想伤害他，但我也无法对他说谎。

“我很感动，Clement，真的，”我轻声说道。“但是……我喜欢的是女孩。”

话一出口，我看到了他脸上的变化。曾经满怀希望的眼神瞬间黯淡下去，他的眼睛在不知所措中微微眨了眨。

“对不起，”我说，想要收回这些话，但我知道，它们就是事实。“我从来没有喜欢过男生，我一直喜欢的是女孩。”

我们之间陷入了长久的沉默，空气中弥漫着浓重的紧张气息。我看到他在努力理解，试图处理我说的话。就在那一刻，我才意识到，我对他来说是多么重要。

感觉有些不对劲。我不能成为他想要的那个人。但我不能为了迎合别人去改变自己。

变化

那之后，一切似乎都变了。Clement依然来找我，依然和我一起待着，但我能察觉到他身上的细微变化。仿佛他的内心碎了，而他在努力把碎片拼凑回来。

起初，我并不理解到底发生了什么。他变得更安静，更孤单。然后，我注意到了一些奇怪的事情。Clement开始变化。

他开始穿得更女性化，更柔和了。头发变长了，曾经粗糙的皮肤也变得柔滑起来。现在的他，仿佛变得更加纤细。走路的姿态比以前更为流畅。我突然意识到，他似乎变了，变得有些精致，甚至连声音也变得更柔和了，少了之前的那种沉稳和坚定。

我不得不承认，我被吓到了。我无法忽视这些变化，尽管我尽量去忽略。

他正在变，他为了我而变。这既让我感到震撼，又让我有些不安。

有一天，我在走廊上看到他走向我，完全不一样了。他的身体似乎变得更加柔和，轮廓也更女性化了。但我无法否认他为这一切付出的努力。可他的眼神……依然是那种深邃的渴望。是Clement，但又仿佛不是了。

我不知道该怎么感受。难道他真的认为，只有变成这样，才能得到我的爱吗？

对质

直到我们再次在咖啡馆相遇，真相才完全明朗。Clement坐在我对面，他那纤细的手轻轻地放在桌上，目光再次紧紧地盯着我。但这一次，眼神中有着某种别的东西——一种迫切，仿佛他在希望我现在能以不同的方式看待他。

“你看起来……变了，”我轻声说道，不自觉地压低了声音。

Clement微笑了笑，笑得有些无力。“我知道，我是为了你变的。”

他的声音飘然而过，带着一层无形的重压，我一时无法看清其中的意义。我不知道该如何反应。我从未要求过他改变。我从未要求过这一切。

“我想成为你能爱的人，”他低声说道。

我的心为他颤动，但同时又充满了迷茫。这不是我对爱的理解。他变成了另一个人，所有这一切，都是为了我。而我，依然无法对他有那种感觉。

“Clement，”我努力让自己的声音保持冷静，“你还是你。但爱情……不是为了别人去改变自己。它是要做真实的自己。”

他没有立刻回答，只是望着我，眼里充满了期待，仿佛在找寻我眼中的某种希望，某个暗示，证明他并没有完全失去我。但我无法给他那种回应。至少不是以这种方式。

“我知道你这样做是因为想和我在一起，”我继续说道。“但你不必为我改变。你不必成为别人。”

他低下了头，脸上闪过一抹失落。我想安慰他，但我不知道该如何去做。“我不知道我能不能成为另一个人，”他低语道，“但我可以以我能做到的任何方式和你在一起。”

未言

之后，我们没再说太多话。我看到他眼中的渴望，看到他心中那份触手可及却又遥不可及的情感。但我也不知道该如何去感受。我不确定，爱情是否真的能如此痛苦。

我一直喜欢的一句诗是莎士比亚的：“爱情是不改变的，它不会因为变化而改变。 (Love is not love which alters when it alteration finds.) ”

但这是爱情，还是绝望？如果爱情意味着改变你内心最深处的自己，是否还能坚持下去？我不知道答案。甚至不知道Clement是否已经找到自己的答案。

或许，这就是最难忍受的部分。

寻找

在那之后，我意识到，我们两个人都在寻找着某种东西。他在以一种陌生的方式寻找爱，而我则在寻找那已经存在的——我是谁，我爱谁，我该成为什么样的人。

但是，我不禁又在想，看到Clement逐渐成为一个完全不同的形象，我开始怀疑，爱情是否真能足够强大，能够承载这些变化。又或者，像生活中的所有事一样，最终会被时间流逝，变成一段我们都必须背负的记忆。

或许，爱情并不是要改变。或许，爱情应该是接受。

但是，接受……我的思绪，散在了沉默的对视中。

发表更新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;
}

撒花！

发表更新Entertainment9 分钟读完 (大约1296个字)

【论坛体】乐队的主唱与吉他手是？（未完结）

需知

作者：本人&一些群u（大部分都在正文里啦）
修改：Ste女士

首次写，使用群聊天记录改编，可能有点重复，谢谢支持。

9/17/2024 upd: 首更，45条

正文

【校园乐队吧】

#0 鸽子 【楼主】
兄弟萌啊，大瓜听不听

#1 电灯泡专业户
乐队吧说什么瓜不瓜的[放个耳朵.jpg]

#2 King apple
[放个耳朵.jpg]

#3 鱼吐泡泡
[放个耳朵.jpg]，快说

#4 鸽子 【楼主】
我好像看到我们偌大的和谐有爱校园里有情侣了

#5 电灯泡专业户
还以为啥呢，lz没见过情侣是吧

#6 鸽子 【楼主】
但是是那种不太正当的情侣关系

#7 King apple
发生了什么

#8 鱼吐泡泡
速速道来

#9 鸽子 【楼主】
听说是那种，你懂吧。。。
那种在挪威给对方养鸡做鸡汤的那种

#10 鱼吐泡泡
lz别卖关子了

#11 鸽子 【楼主】
但是啊，那个汤不是很纯

#12 King apple
加了料？

#13 鸽子 【楼主】
1

#14 鸽子 【楼主】
就不好奇是谁吗泥萌，还有为啥发在乐队吧
因为这俩就是我大乐队主唱&吉他手啊喂

#15 电灯泡专业户
！！

#16 鸽子 【楼主】
烦死了，我大鼓手当了一辈子背景板[伤心]，恶俗恋爱瓜呢

#17 电灯泡专业户
和贝斯手比呢。
你们不会没有贝斯手吧。

#18 鸽子 【楼主】
等一下我把帖转给贝斯手呢

#19 King apple
好混乱啊

#20 鸽子 【楼主】
不过言归正传，大伙儿都知道她俩吧，哦对，没错，是她俩。

#21 乐队的斐济北
我寻思啥事呢，谈恋爱谈呗，不影响乐队就行了。
欸，等一下…主唱和吉他不都女的吗？
哦，是另一个吉他吗

#22 马大卫世界最帅
什么玩意？

#23 电灯泡专业户
贝斯手小哥哥这么迟钝呢呵。我觉得我大概知道这是怎么个事了，怀疑我和lz认识。lz什么时候开的小号。

#24 鸽子 【楼主】
就是那位icarus 和 antimony，先不爆那么多了，论坛封了办不了正事嗯。
就是，很想辨析一下她们的。。。
你们喜欢长发温柔理性大姐姐T还是短发幼稚园小盆友T！

#25 King apple
我选长发温柔大姐姐

#26 电灯泡专业户
你们女吉他人设不是狂帅酷炸一米八小哥哥吗

#27 马大卫世界最帅
什么玩意？那不我吗，不要cue我ok

#28 电灯泡专业户
回楼上，你不一米七吗

#29 马大卫世界最帅
呃。。

#30 鸽子 【楼主】
其他人呢，长发温柔理性大姐姐T还是短发狂帅酷炸一米八幼稚园小哥哥T

#31 鱼吐泡泡
肯定大姐姐t啊，姐t秒了

#32 鸽子 【楼主】
但是小哥哥说他才是T

#33 鱼吐泡泡
嘴硬罢了

#34 电灯泡专业户
大姐姐T！！大姐姐T！！！

#35 Siri
好多人

#36 鸽子 【楼主】
哇是新人
不过兄弟你的昵称有点眼熟//
不管了，长发温柔理性大姐姐T还是短发狂帅酷炸一米八幼稚园小哥哥T，快回答

#37 Siri
不是锅盖头小哥哥吗，好奇锅盖头小哥哥能帅起来？

#38 武装直升机
我要短发T！我是Antimony永远的公公，你们嬷嬷都退开！

#39 King apple
想看照片

#40 Siri
所以真是那个谁和那个谁吗，她俩真谈啦？不是本尊打假了，只是炽热的友谊的吗？

#41 电灯泡专业户
怎么可能，你又不是本人。
还有哦，有件事lz不知道，我和一个好朋友（白刃姐）放学一起写作业，在半路上也遇到了她俩……在那里打情骂俏哦~
小情侣真的是o(╥﹏╥)o

#42 电灯泡专业户
回#38，不行，要大姐姐T。锅盖头一听就很好嬷。

#43 鸽子 【楼主】
我回来了！刚刚核实了一下，@Siri，你就是icarus吧/fn

#44 Siri
找icarus管我Icarus什么事

#45 鸽子 【楼主】
不大写就不认了，真是邪恶的女人

#46 电灯泡专业户
呵呵呵呵Icarus改名字了。敢做不敢当。
并且听说两个人QQ情侣都绑了哦~~~

后记

帮大家认人：

鸽子：本人，乐队鼓手
电灯泡专业户：Ste，乐队编外
King Apple：伟大的苹果王，群u
鱼吐泡泡：就是鱼吐泡泡，群u
乐队的斐济北：乐队贝斯手
马大卫世界最帅：乐队的主音吉他（男）
Siri：乐队主唱Icarus
Antimony：乐队节奏吉他（女）
武装直升机：同学，坚决维护Antimony为Top

发表更新Study Notes3 分钟读完 (大约383个字)

简单树上问题の笔记

树上差分，dfs栈，dfs做差，树上倍增
有8道题

A.

一棵含N个结点的树，有K条路径，求结点被经过的最大次数。
非常明显的树上差分：对于每一个节点i，都用pre[i]储存这个节点及其所有祖先节点的遍历次数，此时对每一条路径(u,v)进行分析：

  • pre[u]++,pre[v]++;
  • lca(u,v)只被遍历一次，但被加了两次, pre[lca(u,v)]—;
  • lca(u,v)的祖先节点不会被遍历，但被加了两次（还剩一次）,pre[par[lca(u,v)][0]]—;

得到代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=100005;

ll n,k;
vector<ll> e[N];

ll par[N][25];
ll dep[N];

ll ans;

void dfs(ll x,ll f)
{
	par[x][0]=f;
	for(auto y:e[x])
	{
		if(y==f)
		{
			continue;
		}
		dep[y]=dep[x]+1;
		dfs(y,x);
	}
}


ll LCA(ll x,ll y)
{
	if(dep[x]>dep[y])
	{
		swap(x,y);
	}
	
	for(ll i=0;i<20;i++)
	{
		if((dep[x]-dep[y])>>i&1)
		{
			y=par[y][i];
		}
	}
	
	if(x==y)
	{
		return x;
	}
	
	for(ll i=19;~i;i--)
	{
		if(par[x][i]!=par[y][i])
		{
			x=par[x][i],y=par[y][i];
		}
	}
	
	return par[x][0];
}

ll pre[N];

void dfs2(ll x,ll f)
{
	for(auto y:e[x])
	{
		if(y==f)
		{
			continue;
		}
		
		dfs2(y,x);
		pre[x]+=pre[y];
	}
	
	ans=max(ans,pre[x]);
}

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

	cin>>n>>k;
	for(ll i=1;i<n;i++)
	{
		ll x,y;
		cin>>x>>y;
		
		e[x].push_back(y);
		e[y].push_back(x);
	}
	
	dfs(1,0);
	for(ll j=1;j<20;j++)
	{
		for(ll i=1;i<=n;i++)
		{
			par[i][j]=par[par[i][j-1]][j-1];
		}
	}
	
	while(k--)
	{
		ll x,y;
		cin>>x>>y;
		
		ll l=LCA(x,y);
		pre[x]++,pre[y]++;
		pre[l]--,pre[par[l][0]]--;
	}
	
	dfs2(1,0);
	
	cout<<ans<<"\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…

发表更新Overall Editorials7 分钟读完 (大约1070个字)

总结：CSP2024-S模拟赛

A. 人事调动

长得非常像一道模拟，但是由于set会去重，map开的大小会达到 $N^2$ ，所以，我们可以使用multiset（其增删改查时间复杂度近似：O(log N)，即总时间复杂度为O(N log N)）。

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

using namespace std;

#define ll long long

const int N=100005;

int n,q;
int a[N],b[N];
multiset<int> mp[N];
multiset<int> ans;

int main()
{
    freopen("work.in","r",stdin);
    freopen("work.out","w",stdout);
		
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		mp[b[i]].insert(a[i]);
	}
	
	for(int i=1;i<N;i++)
	{
		if(mp[i].empty())
		{
			continue;
		}
		ans.insert(*(--mp[i].end()));
	}
	
	while(q--)
	{
		int c,d;
		cin>>c>>d;
		
		int id=b[c];
		ans.erase(ans.find(*(--mp[id].end())));
		mp[id].erase(mp[id].find(a[c]));
		if(!mp[id].empty())
		{
			ans.insert(*(--mp[id].end()));
		}
		
		if(!mp[d].empty())
		{
			ans.erase(ans.find(*(--mp[d].end())));
		} 
		mp[d].insert(a[c]);
		ans.insert(*(--mp[d].end()));
		
		b[c]=d;
		
		
		cout<<(*ans.begin())<<"\n";
	}
	
	return 0;
}

B. 失意

比较一眼的贪心，以区间左端点从小到大排序，用优先队列从小到大维护右端点，每次队列里有m个元素，就比较一次大小，超过m就把右端点最小的弹出去。每次比较记录此时的最大L和最小R（答案即R-L），最后再循环一边找到符合的m个区间。

注意：要特判答案为0的时候，任意输出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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const ll N=1000005;

ll Num,n,m;
struct node
{
	ll l,r,id;
	bool operator <(node a)
	{
		return l<a.l;
	}
} a[N];

priority_queue<ll> pq;
bool f;

ll ans,id1,id2;

int main()
{
    freopen("failure.in","r",stdin);
    freopen("failure.out","w",stdout);
    
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	cin>>Num;
	
	cin>>n>>m; 
	for(ll i=1;i<=n;i++)
	{
		ll x,y;
		cin>>x>>y;
		a[i]={x,y,i};
	}
	sort(a+1,a+n+1);
		
	for(ll i=1;i<=n;i++)
	{
		pq.push(-a[i].r);
		while(pq.size()>m)
		{
			pq.pop();
		}
		if(pq.size()==m)
		{
			if(-pq.top()-a[i].l>ans)
			{
				ans=-pq.top()-a[i].l;
				id1=a[i].l,id2=-pq.top();
			}
		}
	}
	
	if(id1==0&&id2==0)
	{
		id1=1e9;
	}
	cout<<ans<<"\n";
	
	for(ll i=1;i<=n;i++)
	{
		if(a[i].l<=id1&&a[i].r>=id2)
		{
			cout<<a[i].id<<" ";
			m--;
		}
		if(!m)
		{
			cout<<"\n";
			return 0;
		}
	} 
	
	return 0;
}

C. 位于LIS概率

又是C>>>>>>D，扣C结果在还有3分钟结束的时候想到了正解，错失D大好90pts

70pts的做法就是没有线段树/树状数组优化的正解：求出整个数列的LIS长度mx；对于每个 $i∈{1…n}$ 求出以i结尾与以i开头的LIS长度 $x1$, $x2$ 和数量 $t1$, $t2$ ，如果其 $x1+x2-1=mx$，说明这是一种LIS，i在LIS中的情况数+= $t1\times t2$，最后用快速幂求逆元即可。

用树状数组维护比较短（改成线段树只要改架构就行了）。

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

using namespace std;

#define ll long long

const ll N=1000005,mod=998244353;

ll n,m;
ll a[N],b[N];

ll ans[N];

struct node
{
	ll x,t; //长度，数量
	
} tr[N],pre[N],suf[N];

node mx;

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;
}

void calc(node &x,node y) //合并
{
	if(x.x==y.x)
	{
		x.t=(x.t+y.t)%mod;
	}
	else if(x.x<y.x)
	{
		x=y;
	}
}

void update(ll x,node y)
{
	while(x<=m)
	{
		calc(tr[x],y);
		x+=x&(-x);
	}
}

node query(ll x)
{
	node ret={0,0};
	while(x)
	{
		calc(ret,tr[x]);
		x-=x&(-x);
	}
	
	return ret;
}

int main()
{
    freopen("lis.in","r",stdin);
    freopen("lis.out","w",stdout);
    
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	
	sort(b+1,b+n+1);
	m=unique(b+1,b+n+1)-b-1;
	
	for(ll i=1;i<=n;i++)
	{
		a[i]=lower_bound(b+1,b+m+1,a[i])-b;
	}
	
	for(ll i=1;i<=n;i++)
	{
		pre[i]=query(a[i]-1);
		pre[i].x++;
		calc(pre[i],{1,1});
		update(a[i],pre[i]);
		
		calc(mx,pre[i]);
	}
	
	memset(tr,0,sizeof tr);
	
	for(ll i=n;i;i--)
	{
		a[i]=m-a[i]+1;
		suf[i]=query(a[i]-1);
		suf[i].x++;
		calc(suf[i],{1,1});
		update(a[i],suf[i]);
	}
	
	for(ll i=1;i<=n;i++)
	{
		if(pre[i].x+suf[i].x-1==mx.x)
		{
			ans[i]=pre[i].t*suf[i].t%mod;
		}
	}
	
	ll tt=qpow(mx.t,mod-2);
	for(ll i=1;i<=n;i++)
	{
		cout<<ans[i]*tt%mod<<" ";
	}
	
	cout<<"\n";

	return 0;
}

D. 排队

暴力有90早知道不扣C了

补题之后感觉不是很复杂，不知道做法有没有假掉。

首先由题目我们明确了一些排序规则：

  • 子节点在父节点前面
  • 编号小的的子节点在编号大的子节点前面

因此，我们可以用dfs给每一个节点排序，并用优先队列维护空房间顺序。

对于操作1（来人）：弹出x次优先级最高房间，输出最后一个编号

对于操作2（走人）：我们发现对于被移动的人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
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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=1e5+5;

int n,t;

vector<int> e[N];
int par[N][25];

int id[N];
int tot;
	
bool vis[N];

void dfs(int x,int f)
{
	par[x][0]=f;
	vector<int> son;
	son.clear();
	
	for(auto y:e[x])
	{
		if(y==f)
		{
			continue;	
		}
		son.push_back(y);
	}
	
	sort(son.begin(),son.end());
	for(auto y:son)
	{
		dfs(y,x);
	}
		
	id[x]=++tot;
}

struct node
{
	int v;
	bool operator < (const node &x) const
	{
		return id[v]>id[x.v];
	}
};

priority_queue<node>q;


int main()
{
    freopen("queue.in","r",stdin);
    freopen("queue.out","w",stdout);
    
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>t;
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	
	dfs(1,0);
	
	for(int i=1;i<=20;i++)
	{
		for(int j=1;j<=n;j++)
		{
			par[j][i]=par[par[j][i-1]][i-1];
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		q.push((node){i});
	}
	
	while(t--)
	{
		int op,x;
		cin>>op>>x;
		
		if(op==1)
		{
			int v=0;
			for(int i=1;i<=x;i++)
			{
				v=q.top().v;
				q.pop();
				vis[v]=1;
			}
			cout<<v<<"\n";
			
		}
		else
		{
			int cnt=0;
			for(int i=20;i>=0;i--)
			{
				if(vis[par[x][i]])
				{
					x=par[x][i];
					cnt+=(1<<i);
				}
			}
			
			vis[x]=0;
			q.push((node){x});
		
			cout<<cnt<<"\n";
		}
	}
	
	return 0;
}

END…

发表更新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
发表更新Research2 分钟读完 (大约254个字)

有关“青少年自诩少数群体热潮”的原因与影响

0. 引言

本文的前身是《关于LGBTQIA+群体的社会地位》，因在研究过程中主要接触青少年，并逐渐发现青少年对少数群体的认知更特殊，故更改为本文。

本文以“性少数群体”与“常见精神障碍患者”为例，对近年在信息流通，发展较好的地区形成”青少年自诩少数群体热潮“进行猜想和探究。

”自诩“既包括愿意表达自我，也包括”伪装“或对自我认知的偏差。

1. 原因

我对此现象产生的原因有一下猜测：

  • 家庭影响
  • 同龄人影响（包括学校，好友，网友等）
  • 艺术/文学/影视作品的影响（如讲述少数群体的书籍等）
  • 自发地追寻独特
  • 一种手段（如”少数群体“的名头是否可以带来一些优势）
发表更新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;
}
发表更新Ideas5 分钟读完 (大约710个字)

关于线段树的创新优化（原创）

原创！

这是一件伟大的事情，因为本文的核心诞生于2023年4月12日，距离我开始学习OI仅7个月。
但是当时我还是一名被各种碾压的蒟蒻，于是放弃更新本文，如今，作为略有提升的蒟蒻，我要完善它。

设想

这是对线段树的一个空间优化，因为我当时刚学线段树，还不知道有动态开点这个东西，但是我设想的这个线段树，是完全符合普通线段树的规则，只是略作修改，使其和动态开点线段树一样，变成一棵满二叉树。

哦对了，还有一点很特殊，当时写的线段树都是根为0的，所以左节点是p2+1，右节点是p\2+2。

建树

普通建树

线段树模板中我们使用的建树方式是将父节点/2下放给子节点的

这样，在设置数组的时候我们总共需要n*4的数组（实际上占了4n-1的空间），这样的建树方式简单明了，容易记忆，同时也广为流传。

优化——完全二叉树建树

但是，如果我们把这棵线段树建成完全二叉树，它的空间需求就可以从n4降到n2（实际为定值2n-1）（如图）

经过计算，我们只需要找到不小于现节点区间大小的最小二的幂num，如果现节点区间大小大于num的3/4，则分界点为l+num/2，否则为r-num/4。

代码如下:

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
struct
{
	int sum;
} tree[n<<1]; //线段树
int t=1; //填充

void pushup(ll p)
{
	tree[p].sum=tree[p*2+1].sum+tree[p*2+2].sum;
}

void build(ll p,ll l,ll r)
{
	if(l==r)
	{
		tree[p].sum=t;
		t++;
		return;
	}
	
	//这里可能会使常数大一些
	//就是求不小于r-l+1即区间大小的2的幂 
	int num=pow(2,__lg(r-l+1));
	if((r-l+1)>num)
	{
		num<<=1;
	}
	
	//这个我目前没有证明 
	ll mid;
	if(r-l+1>num/4*3)
	{
		mid=l+num/2-1;
	}
	else
	{
		mid=r-num/4;
	}
	
	build(p*2+1,l,mid);
	build(p*2+2,mid+1,r);
	
	pushup(p);
}

这种建树方法将空间复杂度减少了一半。
事实上，因为完全二叉树的特性，我们也可以用循环建树，代码如下：

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
struct
{
  int sum;
}tree[n<<1];//线段树

void build(ll n)
{
	int num=pow(2,__lg(n));
	if(n>num)
	{
		num<<=1;
	}
	
	int a=2*n-num;
	int b=n;
	int i;
	for(i=2*n-2;a>=1;a--,i--)
	{
		tree[i].sum=a;
	}
	a=2*n-num;
	for(;b>a;b--,i--)
	{
		tree[i].sum=b;
	}
	for(;i>=0;i--)
	{
		tree[i].sum=tree[i*2+1].sum+tree[i*2+2].sum;
	}
}

更新

普通更新

线段树的更新为：从上至下分发懒惰标记，在从下至上重新pushup。
这里不再赘述。

优化——完全二叉树更新

发表更新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) 这个题解用的是二分，先放在这里吧，回头搞一下咩~

发表更新Overall Editorials / AtCoder5 分钟读完 (大约727个字)

AtCoder Beginner Contest 355 赛后总结

比赛链接

非常美丽地在1h内做完了前4题，结果第五题交互题，死活不对。。。

题解

A. Who Ate the Cake?

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

using namespace std;

#define ll long long

int a,b;

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

	cin>>a>>b;
	if(a!=b)
	{
		cout<<6-a-b<<"\n";
	}
	else
	{
		cout<<-1<<"\n";
	}

	return 0;
}

B. Piano 2

直接排序然后对比即可，就是要注意C数组的大小为n+m，因为这个博主整了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
#include<bits/stdc++.h>

using namespace std;

#define ll long long

int n,m;
int c[205];

map<int,bool> mp;

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

	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>c[i];
		mp[c[i]]=1;
	}
	for(int i=0;i<m;i++)
	{
		cin>>c[i+n];
	}
	
	sort(c,c+m+n);
	
	bool f=0;
	for(int i=0;i<n+m;i++)
	{
		if(mp[c[i]])
		{
			if(f==1)
			{
				cout<<"Yes\n";
				return 0;
			}
			else
			{
				f=1;
			}
		}
		else
		{
			f=0;
		}
	}
	
	cout<<"No\n";
	
	return 0;
}


C. Bingo 2

纯模拟，但是注意卡常。一是要使用break；二是不用初始化，把每个点的值先填上

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

int n,t;
int a[200005];
map<int,int> mp;

int g[2005][2005];

int ans,ans1=1e9;

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

	cin>>n>>t;
	for(int i=0;i<t;i++)
	{
		cin>>a[i];
		mp[a[i]]=i+1;
	}
	
	for(int i=1;i<=n;i++)
	{
		bool f=1; ans=0;
		for(int j=1;j<=n;j++)
		{
			if(!mp[n*(i-1)+j])
			{
				f=0;
				break;
			}
			else
			{
				ans=max(mp[n*(i-1)+j],ans);
			}
		}
		if(f==1)
		{
			ans1=min(ans1,ans);
		}
		f=1; ans=0;
		for(int j=1;j<=n;j++)
		{
			if(!mp[n*(j-1)+i])
			{
				f=0;
				break;
			}
			else
			{
				ans=max(mp[n*(j-1)+i],ans);
			}
		}
		if(f==1)
		{
			ans1=min(ans1,ans);
		}
	}
	
	bool f=1; ans=0;
	for(int i=1;i<=n;i++)
	{
		if(!mp[n*(i-1)+i])
		{
			f=0;
			break;
		}
		else
		{
			ans=max(mp[n*(i-1)+i],ans);
		}
	}
	if(f==1)
	{
		ans1=min(ans1,ans);
	}
	f=1; ans=0;
	for(int i=1;i<=n;i++)
	{
		if(!mp[n*(i-1)+n-i+1])
		{
			f=0;
			break;
		}
		else
		{
			ans=max(mp[n*(i-1)+n-i+1],ans);
		}
	}
	if(f==1)
	{
		ans1=min(ans1,ans);
	}

	cout<<(ans1==1e9?-1:ans1)<<"\n";;
	
	return 0;
}

D. Intersecting Intervals

最水D题。

存一下所有开始时间和结束时间，然后按时间顺序排，注意由于区间左右皆开，所以开始要排在结束前面

然后如果遇到开始时间，ans+现有的未完区间，并且未完区间数+1，否则-1

请开long long

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

using namespace std;

#define ll long long

bool cmp(pair<ll,ll> x,pair<ll,ll> y)
{
    if(x.first==y.first)
	{
		return x.second<y.second;
	}
    return x.first<y.first;
}

ll n,s,t;
vector<pair<ll,ll> > v;

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

    for(ll i=0;i<n;i++)
	{
        cin>>s>>t;
        v.push_back({s,0});
        v.push_back({t,1}); 
    }
    sort(v.begin(),v.end(),cmp);

    ll k=0,ans=0;
    for(ll i=0;i<v.size();i++)
	{
        if(v[i].second==0)
		{
            ans+=k;
            k++;
        }
        else
		{
			k--;
		}
    }
    
    cout<<ans<<"\n";
    
    return 0;
}

E. Guess the Sum

为什么加了输入输出流解绑就会出现输入问题qwq，烦

参考jiangly大神的做法

(=_=) E又>F了

非常匪夷所思地使用了最短路

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

using namespace std;

#define ll long long

int n,l,r; 
int v;
int pre[300005];
queue<int> q;

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

	cin>>n>>l>>r;
	r++;
	
	q.push(l);
	memset(pre,-1,sizeof pre);
	pre[l]=l;
	
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		
		for(int i=1;i<=(1<<n);i*=2)
		{
			for(auto y:{x-i,x+i})
			{
				if(y<0||y>(1<<n))
				{
					continue;
				}
				if(pre[y]==-1)
				{
					pre[y]=x;
					q.push(y);
				}
			}
			if(x&i)
			{
				break;
			}
		}
	}
	
	ll ans=0;
	for(int i=r;i!=l;i=pre[i])
	{
		int b=i,a=pre[i];
		int t=1;
		if(a>b)
		{
			swap(a,b);
			t=-t;
		}
		cout<<"? "<<__lg(b-a)<<" " <<a/(b-a)<<"\n";
		
		int ret;
		cin>>ret;
		ans=(ans+t*ret+100)%100;
	}
	
	cout<<"! "<<ans<<"\n";
	
	return 0;
}

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

using namespace std;

#define ll long long

using namespace std;

ll n,m;
ll a[400005],b[400005],c[400005];
ll par[200005];
ll vis[400005];
ll dp[400005];

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

void merge(ll x,ll y)
{
	x=find(x),y=find(y);
	par[x]=y;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>m;
	for(ll i=1;i<n+m;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
	}
	
	for(ll l=1;l<=10;l++)
	{
		for(ll i=1;i<=n;i++)
		{
			par[i]=i;
		}
		for(ll i=1;i<n+m;i++)
		{
			if(c[i]>l)
			{
				continue;
			}
			if(find(a[i])!=find(b[i]))
			{
				merge(a[i],b[i]);
				if(!vis[i])
				{
					dp[i]+=l;
					vis[i]=1;
				}
			}
			else if(vis[i])
			{
				dp[i]-=l;
				vis[i]=0;
			}
		}
	}
	
	ll ans=0;
	for(ll i=1;i<n+m;i++)
	{
		ans+=dp[i];
		if(i>=n)
		{
			cout<<ans<<"\n";
		}
	}
	
	return 0;
}

G. Baseball

发表更新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;
}

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

发表更新Entertainment18 分钟读完 (大约2712个字)

【惊喜】ZHY&LJCの小窝

Bonjour！这里是💕ZHY💕和💕LJC💕的专属应援组哦~

🌟繁花似锦金婚🌟

🌺锦上添花金婚🌺

🧡繁花似锦是真爱🧡

💖与其说我们磕花锦，不如说磕的是自己理想中爱情的样子💖

🗯沐浴风雨，伴君远方，风雨兼程等一个繁花似锦的时代。🗯

🎉破天下，定风云，锦上添花并肩行🎉

✨月亮和星星不会奔Bastien而来🌙但Clément会💖

🌠流星划过星空🌌 Bastien在Clément心中💖

🔮Clément，愿你前程似锦！🔮

🌙海上月是天上月，Clément人是心上心🌙

💪Clément，永不放弃，坚持到底！💪

👑披金成王，伴Clé远航👑

💖Bastien，美若天仙💖

✨Bastien，璀璨如星✨

👑全班团宠，Bastien👑

《Bastien的校园偶遇》

AKA《花锦圣经》 作者：Stéphanie & Sonia

（原作：《Stéphanie的校园偶遇》作者：Clément）
（声明：本文中任何人物都是虚构人物，重名纯属巧合。）
（再叠甲：本文与原版的炸裂程度差之甚远，若观看时感到不适，请及时对比原版平复心情。）

让我们感谢Stéphanie与Sonia的辛勤付出与为艺术献身的精神，并怀着圣洁之心阅读这篇精彩绝伦的《花锦圣经》！

Let’s thank Stéphanie and Sonia for their hard work and dedication to their art, and read this wonderful Cléstian Bible with a holy heart!

Remercions Stéphanie et Sonia pour leur travail acharné et leur dévouement à leur art, et lisons cette merveilleuse Bible Cléstian avec un cœur saint !

第一章

Clément是我们班跑得最快的男生。

Bastien是我们班跑得最快的男生。

有一次老师让我们跑圈，然后Clément和Bastien跑到了最前面，同学们在后面起哄道：“你们是不是在私奔？”

Bastien本来挺尴尬的。

可Clément说了一句：“我媳妇这么好看，等下被你们抢走了怎么办？”

顿时同学们都炸了……

从此，Clément和Bastien幸福快乐地生活在了一起……

第二章

Clément在校园里散步。

Bastien正在试图打球。

Clément看见了球场上Bastien努力的身影，不禁被迷晃了眼。

他情不自禁地向他奔去，并且逐字逐句地吐出了：
“在你那双又大又亮的眼睛里，我总能捕捉到你的宁静，你的热烈，你的聪颖，你的敏感。”

Bastien听到这美妙绝伦的声音，不禁也扭过头去：
“你也许没有若隐若现的酒窝，但你的微笑一定是月闭花羞，鱼沉雁落。”

从此，Clément和Bastien幸福快乐地生活在了一起……

第三章

又是一个夜晚，外面风雨交加。

Clément的房子里，一群中学生正在开派对。

啊啾~

一位娇小白嫩身形细长的男生打了一个喷嚏，他，就是Bastien。

Clément关切的目光扫了过来，很自然地给Bastien盖上了毛毯。

旁边的同学们一脸惊恐地（划掉）尖叫：“哦！我（nan）们（tong）退（chu）啦（qu）！”

于是，全Clément家犹如炸开了锅似的，一顿喧闹之后，房子里只留下了二人。

两个人面面相觑，深情对视。

Clément薄唇微启，开始不自觉地歌唱他心中最难听的歌——

“因为你与众不同
别人说早我说晚安
变化无穷
犹豫半天不敢说喜欢
因为你与众不同
太复杂能不能变得简单
是天上星星最亮的那一颗
可不可以
可不可以
……”

（这歌是真的 很难听。）

第四章

篮球场上，Bastien正挥洒着汗水。

阳光打在他身上，犹如小说中的主角。

不对，不是“犹如”。他就是主角。Clément生命中的主角。

Clément坐在篮球场的边缘，入神地盯着Bastien。嘴角的微笑十吨的哑铃都压不下去！

Clément的大脑，又开始不自觉地歌唱他心中最难听的歌——

“小猫在对谁↓眨↑眼↓睛→”

（这歌是真的 很难听。）

第五章

夜幕渐渐降下来。

Bastien和他的球友们也打累了。

“脑公~我渴了~~~~” Bastien直接在大家面前向Clément撒娇。
（这段谁写的！叉出去！！！！我在打第五章的时候都替主角受不了了！！！！！！）

“乖，”Clément摸摸Bastien的头，又顺手一楼Bastien纤细的腰肢，“我早就给你买好水啦~”

Clément，歌唱着他心中最难听的歌——

“比起人山人海我，更爱凌晨三点，看向便利店窗外风景（划掉）Bastien~”

（这歌是真的 很难听。）

第六章

可喜可贺，可喜可贺！

Clément，周氏集团的公子，要结婚了！

前所未闻！这周氏集团的公子，向来生人勿近的表现，让人实在不敢相信他拥有了爱人。

这场盛大的婚礼，由Clément的母亲——周太太Sonia主持。

Sonia看看Bastien，总感觉有一种浓烈的既视感。

——哥们你怎么长得这么像我老相好？！

“我的父亲，她叫Stéphanie。不过她在我很小的时候就去世了。”

原来如此。——等等，怎么儿媳是老相好的儿子啊？！

第七章

经过了婚姻的沉淀，他们即将迎来第一个孩子。

Clément一脸爱惜地看着Bastien，而后者专心地看着“新生儿名字-新版国学起名大全-周易起名网”。

Clément淡淡地说：“你喜欢什么就取什么好了。”

天哪！Clément这个男银实在太有魅力了！云淡风轻的话语，在Bastien的脑海里回荡。真不愧是淡定的男人！

Bastien压住心中的喜悦，清清嗓子。

“那么，我们的孩子，如果是男孩，就叫Stéphanie。如果是女孩，也叫Stéphanie。”

淡淡地，Clément说：“都依你。”

这个时候，Clément的母亲Sonia在门外听到了这段对话。Chloé，她的丈夫，看见她扬起的嘴角，不禁也凑上去听。

“……Stéphanie。”

突然在儿媳口中听到自己老相好名字的Chloé花容失色（？），连忙瞥了一眼Sonia。

——只见Sonia同样花容失色地看向自己。两人心照不宣地闷下了Sté女士是她俩共同老相好的这个事实。

房间里，小情侣兴致勃勃地讨论着未来孩子的名字。

“那么，我们的孩子，就叫Stéphanie吧。”Clément淡淡道。

Bastien看着面前淡定的男银，躲闪了一下娇羞（？啊）的眼神，轻轻地说：“好，就叫Stéphanie……”

第八章

经过了婚姻的沉淀，他们终于迎来了第一个孩子。

Stéphanie咯咯地笑着，Clément把她抱起来，龇着大牙傻乐。完全看不出来曾经大众心中深刻的冰山形象。

Bastien在一边慈爱地看着一大一小。

“呕——”

“yue——”

Bastien连忙把Stéphanie拿开，担忧地看向丈夫。（Sté：？）

Clément口齿不清地冲向卫生间，痛苦地刷牙洗漱。

“她……她把没消化完的奶吐到我嘴里了啊啊啊啊啊啊aaA啊啊啊Aa啊啊啊啊啊啊啊啊啊啊啊啊a”

（科普：小孩子吐奶是正常现象。对于 1 岁以下的宝宝，吐奶是十分正常的，4 月龄左右的宝宝吐奶尤为严重，这和宝宝尚未发育成熟的消化系统以及进食有关系。）

霸道总裁爱上我简介（真的是原简介复制粘贴来的）：

为救父亲，Bastien无奈之下和神秘男人做了天价交易。 五年后，Bastien以演艺新人的身份回归，却被他困在车上威胁不许靠近他女儿一步，否则不介意让他坟头寸草不生！Bastien避他不及，却一再撞到他面前。 后来他将Bastien扣在怀里，眼神冷冽的质问：“一次是偶然，两次是巧合，Bastien，这一次你怎么解释？” Bastien仰头笑得明媚：“这一次，是我步步为营的谋算。” 他以为Bastien谋的是他的心，是周太太的身份，当Clément心甘情愿踏入Bastien的算计，却发现Bastien掩藏了一个惊天的秘密。 “Bastien，你想怎么死？” “雇主大人，有缓刑吗？” “你觉得呢？” 都说婚姻是爱情的坟墓，Bastien的爱情，生于交易，死于欺骗，葬于Clément。 Clément：坟都挖好了，还不死进来！ Bastien：→_→

Clément每天都想官宣：
　　结婚之后，有记者问Clément：花爷您当初是怎么追到Bastien的？
　　Clément默默的翻开一个日记本。
　　追妻日记：
　　一、给宝贝打榜。
　　二、帮宝贝投票。
　　三、为宝贝应援。
　　四、宝贝的电影要包场。
　　五、加入宝贝后援会。

​ ……众所周知，Bastien男神有个宇宙级富豪铁杆粉——周家花爷，Clément！

正文结束。

《Bastien的人生偶遇》作者（们）碎碎念：
🌺锦上添花金婚🌺

写完这些我要吐一年。——作者原注

发表更新Entertainment9 分钟读完 (大约1288个字)

【惊喜】JJH&ZQの国度

Hello！这里是❤️JJH❤️和❤️ZQ❤️的专属墙哟~

❤泉❤中❤大❤蒋❤
❤蒋❤中❤正❤独❤揽❤大❤泉❤
❤蒋❤父❤无❤泉❤子❤
❤孙❤泉❤跳❤蒋❤
❤胡❤邹❤乱❤蒋❤

甲：jjh和zq打羽毛球去了

乙：jjh从了zq

丙：jjh喜欢zq

丁：jjh和zq在一起了

戊：jjh和zq订婚了

己：jjh和zq请大家吃喜糖了

庚：jjh和zq有了

辛：jjh难产而亡了，zq自宫殉情了

壬：jjh和zq葬在一起了

癸：jjh和zq化蝶了

《Zoe与Sam》

一些可以代任何人的纯爱美丽小短打合集，OOC警告！

作者：博主本人qwq

感谢伟大的蓝色图标网站给予我的灵感！如果您想收看纯爱小甜文，请阅读前3段；如果你想看正文，阅读到最后。

Thanks to the great Blue Site for my inspiration! If you want to read some pure lovey dovey, read the first 3 paragraphs; if you want to read the main text, read to the end.

1

“给你变个魔术。”Zoe笑着看着两眼放光的Sam，伸出了空无一物的双手。

“这里面什么都没有，但是……”

Zoe狡黠地挑了挑眉，捏住了Sam的脸，Sam吃痛哇哇叫了两声，与Zoe四目相对。

“……现在，里面有全世界。”

2

Zoe永远记得与Sam当年泡自习室到夜半三更

对面少年眼神疲惫神情坚定，纤细的右手紧握着笔，有着毁灭宇宙的力量。

“怎么样，厉害吧？”Sam问，少年的眼中带着笑意。

Zoe点头，“我们，我们以后一定能拿很多很多奖，成为很厉害很厉害的人……”

3

Sam：“你什么时候喜欢上我的？”

Zoe：“不清楚，就是有一天醒过来发现自己看到你身边的人，不论男女都觉得是情敌，我就知道，我没救了。”

4

挪威的冬天。

Sam浅浅打了个喷嚏。

于是接下来1个月里，饭桌上总会出现金色的鸡汤：薄薄一层晶亮的油，以马丁克里德都自愧不如的完美形态，笼罩着浓郁新鲜的热汤。

“要知道，在挪威养鸡可不是件容易事儿……”，Zoe笑道。

5

Osteria Francescana，摩德纳，意大利。

他们坐在一起吃饭。

Sam小心翼翼地切下装在纯手工制作的瓷盘中撒着使用金箔的半块松饼，再三犹豫过后以轻松的语气开口：“我想你并不需要负责，对吗？这只是一场意外。”

对面，Zoe拿Christofle牌银制餐具的手明显顿了一下。紧接着她摇了摇头：“我不这么认为，这不是一场意外。”

因为我在你的汤里放了迷情剂。

6

人们在神志不清时就有借口，做一些平常做不了的事。

“Little Zoeeeeee~ 我们，来做一些，美妙的事情吧~ 你看这，圆滑的曲线，这，丰满的形体！”

“你太拉了哦……看来得用工具自己做了。”

“不可以~ 这样就没有我们一起做的乐趣了呢！”

“不要当坏孩子哦，Sammy~”

“怎么可能？怎么会这么大！？”

“嘻嘻嘻，现在就让我们愉快的度过这个漫~长~的夜晚吧！”

Zoe将Sam拿着圆规来戳她的手推到一遍，收掉了他的草稿纸，端来3000寸的超大显示器。

“Click, Click…”

“普普通通的平面几何罢了，几何画板一键搞定！”，Zoe依在Sam身上，对着他的耳朵，用性感的低音炮喃喃道。

// 几何画板打钱 —— 作者注

7

Zoe要当文艺青年，因为大家说她长得像高晓松。

于是她开始写短诗。

拜伦说过，学新事物的最好方法是泡妹纸（或汉纸）

所以Zoe写得诗都是关于汉纸的：

​ 最讨厌苦的东西

​ 但你是甜的

​ 所以我吃定你

​ 月亮偷偷钻进了云的怀里

​ 你多久

​ 才能钻进我的被窝里

​ 发芽开花结果

​ 我想把你

​ 埋进怀里

​ 我可以一口吞下整个蛋糕，汉堡和三明治，

​ 但我得偷偷藏起来慢慢品尝的

​ 只有你

8

你知道吗，作者罢工了！

博主要去学习！

算了，祝他们友谊天长地久🙂

Probably the end…

发表更新Overall Editorials / AtCoder3 分钟读完 (大约463个字)

AtCoder Beginner Contest 352 赛后总结

比赛链接

非常难绷地交了6发罚时。。。

题解

A. AtCoder Line

应该没什么好讲的

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

using namespace std;

int n;
int x,y,z;

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

	cin>>n>>x>>y>>z;
	if(x<y)
	{
		swap(x,y);
	}
	if(x>=z&&y<=z)
	{
		cout<<"Yes\n";
	}
	else
	{
		cout<<"No\n";
	}

	return 0;
}

B. Typing

又是双指针，典

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

using namespace std;

string s,t;

int main()
{

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

	cin>>s>>t;
	
	for(int i=0,j=0;i<t.size();)
	{
		while(t[i]!=s[j]&&i<t.size())
		{
			i++;			
		}
		if(i==t.size())
		{
			break;
		}
		cout<<i+1<<" ";
		i++,j++;
	}
	cout<<"\n";

	return 0;
}

C. Standing On The Shoulders

由于头高一定比肩高高，而肩高综合是一定的，因此只需要按照头高和肩高之差拍序，找到差最大的即可。

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

using namespace std;

long long n;
struct node
{
	int a,b,d;
} x[200005];

bool cmp(node a,node b)
{
	return a.d>b.d;
}

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

	cin>>n;
	for(long long i=0;i<n;i++)
	{
		cin>>x[i].a>>x[i].b;
		x[i].d=x[i].b-x[i].a;
	}
	sort(x,x+n,cmp);
	long long ans=0;
	for(long long i=1;i<n;i++)
	{
		ans+=x[i].a;
	}
	ans+=x[0].b;
	
	cout<<ans<<"\n";
	
	return 0;
}

D. Permutation Subsequence

主要是赛时非常抽线地想到了滑动窗口并立刻放弃，转头使用了ST表。

Part1. ST表

说实话，当我看到还有人用线段树时，我意识到我不是一个人。 思路其实很简单，存一下每个元素的索引。答案即是，每连续 k 个元素中最大索引与最小索引之差的最小值。

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

using namespace std;

int n,k,p;
int id[200005];
int ans=1e9;

int f1[200005][20],f2[200005][20]; 

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

	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>p;
		id[p]=i;
	}
	
	//ST表板子部分	
	for(int i=1;i<=n;i++)
	{
		f1[i][0]=f2[i][0]=id[i];
	}
	for(int j=1;(1<<j)<=n;j++)
	{
		for(int i=1;i+(1<<(j-1))<=n;i++)
		{
			f1[i][j]=max(f1[i][j-1],f1[i+(1<<(j-1))][j-1]);
			f2[i][j]=min(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
		}
	}
	
	int s=log2(k);
	for(int i=1;i+k-1<=n;i++)
	{
		ans=min(ans,max(f1[i][s],f1[i+k-1-(1<<s)+1][s])-min(f2[i][s],f2[i+k-1-(1<<s)+1][s]));
	}
	
	cout<<ans<<"\n";
	
	return 0;
}

跑到了49ms，过肯定是能过的

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

using namespace std;

int n,k,p;
int id[200005];
int ans=1e9;

deque<int> mn,mx;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
    cin>>n>>k;
    for(int i=1;i<=n;i++)
	{
        cin>>p;
        id[p]=i;
    }
    
    //滑动窗口板子部分 
   	for(int i=1;i<=n;i++)
   	{
   		//超过k个值了所以这个元素可以丢掉了 
        while(!mn.empty()&&i-mn.front()>=k)
		{
            mn.pop_front();
        }
        while(!mx.empty()&&i-mx.front()>=k)
		{
            mx.pop_front();
        }
        
        //如果放进来的值超过了原来的极值，把原来的极值扔掉 
        while(!mn.empty()&&id[i]<=id[mn.back()])
		{
            mn.pop_back();
        }
        while(!mx.empty()&&id[i]>=id[mx.back()])
		{
            mx.pop_back();
        }
        //直到不超过原来的极值，把它放在最后面维持单调性 
        mn.push_back(i);
        mx.push_back(i);
        
        if(i>=k)
        {
            ans=min(ans,id[mx.front()]-id[mn.front()]);
		}
    }
    
	cout<<ans<<"\n";
    
	return 0;
}

跑到了14ms的绝佳成绩

但其实我觉得这两种方法都可以算正解吧（？

它们的板子都是黄题。

To Be Continued…

发表更新Study Notes3 分钟读完 (大约456个字)

【笔记】Wheelock's Latin 001

咕了很久，直到五一假期才来写qwq

莫名其妙地染上了拉丁瘾，都是因为Duolingo…（也可能是因为这本叫做《罗马十二帝王传》的八卦小册子）

很多人都推荐Wheelock，所以就找了一本来学。

发音相关

说实话因为拉丁语已经死了，所以它的“发音”某种程度上并不重要，但是有些关于发音的符号还是很重要的。

  • 拉丁语中元音的发音有长和短两种，长音用长音符号（字母上方的短横）标出（比如ā）

书中表明应当把长音符号当作拼写的 部分来记忆，因为它所指示的发音区别往往对于含义极为关键（例如 Iiber 是名词，意为“书”，而 līber 是形容词，意为“自由的”）

  • 还有就是重音符，书中说会标明，因为希望读者可以学会正确的朗读拉丁语词汇

第一课

动词；第一和第二变位法动词；现在时主动态的不定时、直陈式和命令式；翻译

动词 (verbum)

和英语一样，拉丁语的动词有5个特征：人称 (persōna)，数 (numerus)，时态 (tempus)，语气/式 (modus)，语态 (vōx)。

拉丁语有3个人称（一，二，三），6个时态（现在时，将来时，未完成时，完成时，将来完成时，过去完成时），3种式（直陈式，命令式，虚拟式）以及2种语态（主动态，被动态）

总体来说和英语其实非常相似

变位 (coniugāre)

发表更新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…

发表更新Overall Editorials / Codeforces7 分钟读完 (大约1026个字)

Codeforces Round 943 (Div. 3) 赛后总结

比赛链接

我服了做得太烂了。。。

还差36分变绿，死一会儿。。。

题解

A. Maximize?

典，暴力枚举即可

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
#include<bits/stdc++.h>
 
using namespace std;
 
int t,x;
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
 
	cin>>t;
	while(t--)
	{
		cin>>x;
		int mx=0,id=0;
		for(int i=1;i<x;i++)
		{
			if(__gcd(x,i)+i>mx)
			{
				mx=__gcd(x,i)+i;
				id=i;
			}
		}
		cout<<id<<"\n";
	}
 
	return 0;
}

B. Prefiquence

双指针，也很典

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<bits/stdc++.h>
 
using namespace std;
 
int t,n,m;
string a,b;
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
 
	cin>>t;
	while(t--)
	{
		cin>>n>>m>>a>>b;
		int cn1=b.size(),cn2=a.size();
		int i=0,j=0;
		while(i<cn1&&j<cn2)
		{
			if(a[j]==b[i])
			{
				j++;
			}
			if(j==cn2)
			{
				break;
			}
			i++;
		}
		cout<<j<<"\n";
	}
	return 0;
}

C. Assembly via Remainders

比较简单的构造，保证每个$a[i-1]>x[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
#include<bits/stdc++.h>
 
using namespace std;
 
int t;
int n;
long long x[505],a[505];
long long pre;
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
 
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=2;i<=n;i++)
		{
			cin>>x[i];
		}
		a[1]=x[2]+1;
		for(int i=2;i<=n;i++)
		{
			a[i]=a[i-1]+x[i];
			while(a[i]<=x[i+1])
			{
				a[i]+=a[i-1];
			}
		}
		for(int i=1;i<=n;i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<"\n";
	}
 
	return 0;
}

D. Permutation Game

与zhy女士讨论的思路甚至是对的。

大概是一个类似于线性dp的思路，以min(循环节长度, $k$ )为循环，这样循环大小不会超过 $2×10^5$

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

using namespace std;

long long t;
long long n,k,pb,ps;
long long a[200005],p[200005];
bool vis[200005];

long long score(long long x,long long k)
{
	memset(vis,0,sizeof vis);
	
	long long mx=0,sum=0;
	while(!vis[x]&&k>0) //如果第一个循环节没有循环完并且还没有走k步
	{
		vis[x]=1;
		mx=max(mx,sum+k*a[x]);
        //sum+k*a[x]是走到这个点就不动了，与下一层循环里的再走一步再停下进行比较
		sum+=a[x]; //走一步
		k--; //还剩几步
		x=p[x]; //下一个
	}
	
	return mx;
}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    
	cin>>t;
	while(t--)
	{
		long long n,k,pb,ps;
		cin>>n>>k>>pb>>ps;
		for(long long i=1;i<=n;i++)
		{
			cin>>p[i];
		}
		for(long long i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		long long A=score(pb,k),B=score(ps,k);
		if(A>B) //比较
		{
			cout<<"Bodya\n";
		}
		else if(A<B)
		{
			cout<<"Sasha\n";
		}
		else
		{
			cout<<"Draw\n";
		}
	}
	
	return 0;
}

E. Cells Arrangement

烂透构造题hmm，你知道我看到代码时有多崩溃吗=(

oh，原来读题读错了，人家让我求max，我搁这儿求min。。。（笑不出来

虽然有很多别的构造方式但是这里介绍一下官方题解的最短方法

注意到：

$n=2$ 时，随便放即可

n=2.png

$n=3$ 时，在上一个的基础上最外圈的上面填一个点，与剩下两个的距离不相等且不等于1

n=3.png

$n=4$ 同理

在一张 $n×n$ 的图里，我们一共可以得到 $1$ ~ $2(n-1)$ 的 $2(n-1)$ 个不同曼哈顿距离对角线上的点与右下产生所有偶数距离，与右下上一个点产生所有奇数距离

其实也没有很难qwq，代码不需要注释了吧…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>

using namespace std;

int t,n;

int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n-2;i++)
		{
			cout<<i<<" "<<i<<"\n";
		}
		cout<<n-1<<" "<<n<<"\n"<<n<<" "<<n<<"\n";
	}
	
	return 0;
}

F.Equal XOR Segments

感觉这次的题都有点浓厚数学的成分

本题我借鉴了一下题解，发现 $k>3$ 是没有必要的，因为我们可以把任意连续三个异或和相同的序列合并成一个，即 $x⊕x⊕x=x$，这样就可以减少两个子序列

同时 $k=2$ 时， $x⊕x=0$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>

using namespace std;

long long t;
long long n,q;
long long a[200005];

map<long long,vector<long long> > id;

int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>q;
		
		for(auto &i:id)
		{
			i.second.clear();
		}
		id[0].push_back(0);
		
		for(long long i=1;i<=n;i++)
		{
			cin>>a[i];
			a[i]^=a[i-1]; //异或前缀和
			id[a[i]].push_back(i);
		}
		
		while(q--)
		{
			long long l,r;
			cin>>l>>r;
			
            //如果头尾的异或和一样，那么说明这个序列可以被分成2个异或和相等的区间
			if(a[r]==a[l-1])
			{
				cout<<"YES\n";
				continue;
			}
            
           	//我们将[l,r]分为[l,s],[s+1,t]和[t+1,r], 我们必须检查a[l-1]=a[t]和a[s]=a[r]
            //同时满足s<t
			long long t= *--lower_bound(id[a[l-1]].begin(),id[a[l-1]].end(),r);
			long long s= *lower_bound(id[a[r]].begin(),id[a[r]].end(),l);
			
			if(t>s)
			{
				cout<<"YES\n";
			}
			else
			{
				cout<<"NO\n";
			}
		}
		cout<<"\n";
	}
}

G&H.Division + LCP

一个简化版一个强化版，合一起做

这题似乎需要一种名字叫做 Z函数(扩展kmp) 的东西

【模板】扩展 KMP/exKMP（Z 函数）

  • Z函数可以解决的问题：

    线性求解字符串str以第i位开始的后缀与str的最长公共前缀(LCP)，Z[i]表示第i位开始的后缀与str的最长公共前缀

然后这个题目说让我们求把这个字符串分成k段的LCP最大值，其中有一个子段一定是原字符串的前缀，所以最后得到的k个子段也肯定是原字符串的前缀

如果 $k$ 不大于 $\sqrt{n}$ ，那么只需要枚举不超过 $\sqrt{n}$ 次；否则用二分算答案即可。

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

using namespace std;

int t,n;
int z[200005];
int ans[200005];

void Z(string s) //Z函数
{
	int l=0,r=0;
 	for(int i=1;i<n;i++)
    {
        if(i<=r&&z[i-l]<r-i+1)
        {
            z[i]=z[i-l];
        }
        else
        {
            z[i]=max(0,r-i+1);
            while(i+z[i]<n&&s[z[i]]==s[i+z[i]])
            {
                z[i]++;
			}
        }
        if(i+z[i]-1>r)
        {
            l=i,r=i+z[i]-1;
		}
    }
}

int f(int len) //计算不小于len长度的最长前缀总数
{
	int cnt=1;
	for(int i=len;i<n;)
	{
		if(z[i]>=len)
		{
			cnt++,i+=len;
		}
		else
		{
			i++;
		}
	}
	return cnt;
}

int main()
{
//  freopen(".in","r",stdin);
//	freopen(".out","w",stdout);

	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	cin>>t;
	while(t--)
	{
		memset(z,0,sizeof z);
		memset(ans,0,sizeof ans);
		
		int l,r;
		string s;
		cin>>n>>l>>r;
		cin>>s;
		
		Z(s);
		
//		for(int i=0;i<n;i++)
//        {
//        	cout<<z[i]<<" ";
//		}
//		cout<<"\n";
		
        //如果k>sqrt(n)，那么len<sqrt(n)
		int sq=ceil(sqrt(n));
		for(int i=sq;i>0;i--) //直接枚举即可
		{
			int cn=f(i);
			ans[cn]=max(ans[cn],i);
		}
		for(int i=n-1;i>0;i--)
		{
			ans[i]=max(ans[i],ans[i+1]);
		}
        
        //如果k<sqrt(n)
		for(int i=1;i<=sq;i++)
		{
			int L=0,R=n/i;
			while(L<R)
			{
				int mid=(L+R+1)/2;
				if(f(mid)>=i)
				{
					L=mid;
				}
				else
				{
					R=mid-1;
				}
			}
			ans[i]=L;
		}
		for(int i=l;i<=r;i++)
		{
			cout<<ans[i]<<" ";
		}
		cout<<"\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;
}

就没了。

蓝题欸。。。

发表更新Overall Editorials / AtCoder9 分钟读完 (大约1284个字)

AtCoder Beginner Contest 350 赛后总结

比赛链接

RT。这十分恶毒的Microsoft Defender在我使用美丽的Dev-c++和Code::Blocks时疯狂地弹弹窗让我扫描病毒威胁，又由于洛谷在线IDE的格式非常不自动化（指tab要自己tab）因此是我罚时+=5*5min，(╯▔皿▔)╯。

赛时没做出来的会全码写注释

题解

A. Past ABCs

依旧非常简单，不多说了放代码。

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

using namespace std;

string s; 

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	cin>>s;
	if(s[0]=='A'&&s[1]=='B'&&s[2]=='c')
	{
		int t=(s[3]-'0')*100+(s[4]-'0')*10+s[5]-'0';
		if(t>=1&&t<350&&t!=316)
		{
			cout<<"Yes\n";
			return 0;
		}
	}
	cout<<"No\n";

	return 0;
}

B. Dentist Aoki

这个题面真的好癫qwq

按题目模拟就行了没有什么思维含量，但是身为一名蒟蒻，还是交了一遍罚时，原因：没有本地运行代码导致for循环的起始写错了。其实可以用来熟悉bitset的使用（？），遂放一篇bitset的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>

using namespace std;

int n,q;
bitset<1005> b;

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

	cin>>n>>q;
    for(int i=0;i<q;i++)
    {
        int t;
        cin>>t;
        b.flip(t);
    }
    cout<<n-b.count()<<"\n"; //如果在一开始将bitset初始化为全1，就输出b.count()
    
	return 0;
}

C. Sort

好了，就是这道令我罚时+=4的题力！（蠢蠢的很安心

四发都错在没有将swap了之后的id更改，谁能想到atcoder给的样例一个都查不出来（气

非常直白，存一下每个 $a_i$ 的索引，再遍历，如果 $a_i≠i$ 那么就把 $a_i$ 和 $a$ 中值为 $i$ 的元素交换，然后用vector存即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>

using namespace std;

int n;
int a[200005],id[200005];
vector<pair<int,int> > s;

int main()
{
	cin>>n ;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		id[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=i)
		{
			swap(a[i],a[id[i]]);
			s.push_back({i,id[i]});
			id[a[id[i]]]=id[i];
		}
	}
	cout<<s.size()<<"\n" ;
	for(int i=0;i<s.size();i++)
	{
		cout<<s[i].first<<" "<<s[i].second<<"\n";
	}
	
	return 0 ;
}

D. New Friends

某位zhy同学没有开龙龙导致WA掉，让我们恭喜他

就是让每一个连通图都变成完全图，所以使用 冰茶几 并查集维护，求出把所有图变成完全图之后的总边数，再减掉原有的变数即可。

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

using namespace std;

long long n,m;
long long par[200005],cnt[200005];
long long ans;

long long findf(long long x)
{
	return (par[x]==x)?x:par[x]=findf(par[x]);
}

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

	cin>>n>>m;
	for(long long i=1;i<=n;i++)
	{
		par[i]=i;
	}
	for(long long i=0;i<m;i++)
	{
		long long a,b;
		cin>>a>>b;
		par[findf(a)]=findf(b);
	}
	for(long long i=1;i<=n;i++)
	{
		cnt[findf(i)]++;
	}
	
	for(long long i=1;i<=n;i++)
	{
		ans+=(cnt[i]-1)*cnt[i]/2;
	}

	cout<<ans-m<<"\n";
	
	return 0;
}

E. Toward 0

学校刚教完概率与期望，我却不会做，是__导致我这样的

看到1e18的数据范围直接被MLE劝退，愣是没有想到其实可以用map，是__导致我这样的！

骰子只有1-6的点数，所以每次到的值都是可以写作 $⌊\frac{𝑛}{2^𝑖3^𝑗5^𝑘}⌋$ （因为 $⌊\frac{⌊\frac{n}{x}⌋}{y}⌋=⌊\frac{⌊\frac{n}{y}⌋}{x}⌋=⌊\frac{n}{xy}⌋$ ）

所以我们就可以聪明地使用map数组dp，得到以下递推公式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>

using namespace std;

long long n,a,x,y;
map<long long,double> dp;

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

	cin>>n>>a>>x>>y;
	dp[0]=0;
	for(long long i=1;i<=n;i*=2)
	{
		for(long long j=1;i*j<=n;j*=3)
		{
			for(long long k=1;i*j*k<=n;k*=5)
			{
				dp[n/(i*j*k)]=0; //先新建可能取到的dp索引对应的dp数组的位置（因为使用map）
			}
		}
	}
	
	for(map<long long,double>::iterator i=dp.begin();i!=dp.end();i++)
	{
		if(!i->first)
		{
			continue;
		}
		double p=x+dp[i->first/a],q=6.0*y; //p是选择/a的期望，q是选择抛骰子的期望
		for(int j=2;j<=6;j++)
		{
			q+=dp[i->first/j];
		}
		q/=5;
		i->second=min(p,q); //递推，最小代价
	}

	cout<<fixed<<setprecision(6)<<dp[n]<<"\n";

	return 0;
}

F. Transpose

非常经典的栈，试问Atcoder，为何E>F。

其实感觉难度不是很大，不知道为什么是绿并F题，但话说我一直都很讨厌这种 (((()))(()) 的题QAQ

同样也是直接模拟，但是首先利用栈来记录这个字符串所有括号的位置和字母是否最终被反转

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

using namespace std;

string s;
int p[500005]; //用于配对左括弧和右括弧的位置
stack<int> st; //用于存储左括弧

void output(int x,int y)
{
	if(x<=y)
	{
		for(int i=x;i<=y;i++)
		{
			if(s[i]=='(')
			{
				if(p[i]!=i+1) //如果括号组内不为空
				{
					output(p[i]-1,i+1); //整体翻转输出
				}
				i=p[i]; //跳到下一组
			}
			else
			{
				cout<<s[i];
			}
		}
	}
	else
	{
		for(int i=x;i>=y;i--)
		{
			if(s[i]==')')
			{
				if(p[i]!=i-1)
				{
					output(p[i]+1,i-1); //整体翻转输出
				}
				i=p[i]; //跳到下一组
			}
			else
			{
				cout<<s[i];
			}
		}
	}
}


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

	cin>>s;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='(')
		{
			st.push(i);
		}
		else if(s[i]==')')
		{
			p[st.top()]=i;
			p[i]=st.top();
			st.pop();
		}
		else
		{
            //如果这个字符在奇数个括号组里，就说明它会被大小写反转,偶数则会被反转回来
			if(st.size()&1)
			{
				if(s[i]>='a'&&s[i]<='z')
				{
					s[i]-='a'-'A';
				}
				else
				{
					s[i]-='A'-'a';
				}
			}
		}
	}
	output(0,s.size()-1);
	cout<<"\n";
	
	return 0;
}

G. Mediator

一道被建议评橙的G题（现在是蓝），Atcoder怎么总能水暴力（？

于是投喂一篇暴力（它甚至不需要吸氧就能过我真的

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
// Let us water a brute force ! 
#include<bits/stdc++.h>

using namespace std;

const long long mod=998244353;

long long n,q;
vector<long long> e[200005];
bool t[200005];

void geti(long long &op,long long &u,long long &v,long long xl) //如题
{
	op=1+(((op*(1+xl))%mod)%2);
	u=1+(((u*(1+xl))%mod)%n);
	v=1+(((v*(1+xl))%mod)%n);
}

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

	cin>>n>>q;
	long long xl=0;
	
	while(q--)
	{
		memset(t,0,sizeof t);
		
		long long op,u,v;
		cin>>op>>u>>v;
		
		geti(op,u,v,xl);
		
		if(op==1)
		{
			e[v].push_back(u);
			e[u].push_back(v); //存边
			continue;
		}
		
		for(long long i:e[u]) //遍历与u相邻的点
		{
			t[i]=1;
		}
		
		bool flag=0;
		for(long long i:e[v])
		{
			if(t[i]) //判断是否与v相邻
			{
				cout<<i<<"\n";
				xl=i;
				flag=1;
				break;
			}
		}
		if(!flag) //否则输出0
		{
			cout<<0<<"\n";
			xl=0;
		}
	}

	return 0;
}

好吧下面是正解

使用启发式合并。如果两个点有一个共同的邻点，那么有三种可能：

  1. u是v的祖父
  2. v是u的祖父
  3. u和v是兄弟

所以依然使用带权并查集进行维护。

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

using namespace std;

const long long mod=998244353;

long long n,q;
vector<long long> e[200005];
int f[200005],par[200005],siz[200005];
//分别为点i的父亲，点i的根，点i的深度

void geti(long long &op,long long &u,long long &v,long long xl)
{
	op=1+(((op*(1+xl))%mod)%2);
	u=1+(((u*(1+xl))%mod)%n);
	v=1+(((v*(1+xl))%mod)%n);
}

void dfs(int x) //遍历并确定每个点的父亲节点
{
    for(auto i:e[x])
    {
        if(i==f[x])
        {
            continue;
		}
        f[i]=x;
        dfs(i);
    }
}

int query(int x,int y)
{
    if(f[x]==f[y]&&f[x]) //如果两点为兄弟节点
    {
        return f[x];
	}
    if(f[f[x]]==y) //x的祖父为y
    {
        return f[x];
	}
    if(f[f[y]]==x) //y的祖父为x
    {
        return f[y];
	}
    return 0;
}

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

void merge(int x,int y) //合并
{
    int fx=find(x),fy=find(y);
    if(fx==fy)
    {
        return;
	}
    par[fy]=fx;
    siz[fx]+=siz[fy];
    siz[fy]=0;
}

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

	cin>>n>>q;
	for(int i=1;i<=n;i++) //初始化
	{
		par[i]=i;
		siz[i]=1;
	}
	
	long long xl=0;
	
	while(q--)
	{		
		long long op,u,v;
		cin>>op>>u>>v;
		
		geti(op,u,v,xl);
		
		if(op==1)
		{
			if(siz[find(u)]<siz[find(v)])
			{
				swap(u,v);
			}
			e[v].push_back(u);
			e[u].push_back(v);
			f[v]=u;
			merge(u,v);
			dfs(v);
			continue;
		}
		
		xl=query(u,v);
		cout<<xl<<"\n";
	}

	return 0;
}

wow写完啦！！！！！

感谢观看呀

发表更新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;
}
发表更新Film Reviews36 分钟读完 (大约5468个字)

【影评】001 - DogMan 狗神（2023）

首发于鄙人的知乎专栏

注意：本人影评新手，写法不是很成熟，尽可能表达自己的想法，希望给点支持(´▽｀)，写东西有点乱七八糟会说很多突发奇想，修改意见请从四面八方来

嘿朋友，今天来说部新电影，于2023年底上映的（其实7月就出了），吕克贝松的DogMan狗神。

（太爱咕咕了这篇影评写了1+个月。。。）

概述

先来说说导演吕克贝松。这哥们儿曾经导演了Léon这个杀手不太冷这样的神片。如今的吕克贝松已经是纯粹的好莱坞大片导演了（吕先生，您还记得您说一生只拍10部电影咩？），但欧洲人多少有点欧洲人的风范，一是对人性宗教等大话题的解读与探讨，二是其相比精致而文艺的画风，这两点都在狗神里明显地体现出来。一直以来，吕克贝松对人物情感线的处理是很漂亮的，尤其是复杂而罕见的情感和心理（把犯罪拍出人情味），这也是狗神的亮点之一。但是本片距离吕克贝松这个杀手不太冷的巅峰时期有一定差距，使得本片略低于预期。当然老吕选角还是很好的哈，你们法国人怎么都那么会选角。

老吕

再来说说主演小哥CLJ卡莱伯兰德里琼斯，作为一名前超英迷，第一次见到他是在新x战警系列里的海妖（太可爱了当时），后来发现这哥们儿热衷于演cult movies（邪典电影，这个翻译挺难绷的），比如说Nitram，讲的是1996年澳大利亚塔斯马尼亚州亚瑟港大屠杀，Antiviral病毒抗体，还有些别的我没看过，但都很小众，评分分化比较严重。其实CLJ的演技真的没话说，包括在本片里他的演绎可以把观众完全地带进去，而不会感到这个演员想要突出角色的什么特点之类的目标，一个角色真真正正成了一个个体。但是希望CLJ选片技术再高一点，片子再烂点演技也撑不出高分啊（哭。反正我觉得他是欧美85后90后里很有前途很有个人特色的一位了。

so卡哇伊の海妖最后说一下整体观感。

豆瓣：8.1/10

IMDB：6.7/10

个人评价：7.2/10 豆瓣高攀不起算了，但是IMDB没到7分看得怪难受的

缺点：故事老套，立意不够深刻，有很多狗（对不起对不起但是我怕狗）

优点：（几乎所有演员包括狗都）演技炸裂，艺术处理非常漂亮，故事治愈且爽，有很多狗（怎么不算呢）

DogMan不算一个极好的电影，但是如果可以的话，这个电影值得一看，某些部分的处理还是远高于如今的好莱坞平均水平的，鉴于2023年底2024年初烂片超多（都是些不足6分甚至不足4分的好莱坞答辩）。其次我真心觉得它比某些看起来分很高的电影要好（不拉踩所以我就不说名字了咳咳）。

最后关于小丑和本片的比较，我喜欢很多代的小丑和其电影，比较观看也是一个很有趣的方法，但是我不认为小丑可以作为一个打压本片的理由，本片主角的做法、态度和很多方面与小丑有别，也许是另一面的小丑，但绝不是比不上小丑。当然这是我自己的看法。

细评

Partout où il y a un malheureux, Dieu envoie un chien. — Lamartine
Wherever there’s an unfortunate person, God sends a dog. — Lamartine
哪里有不幸的人，哪里就有上帝派来的狗。— 拉马丁
来自影片开始

好了咱来讲讲剧情。 接下来我会按大概时间顺序讲剧情，边讲内容边做评价，可能有点啰嗦，但是为了让不熟悉电影内容的朋友们也能体会到，见谅。

1.DOG MAN

道格拉斯出生于一个教徒家庭，但是他的父亲以组织斗狗谋生，不给狗狗喂食。道格偷偷喂食被哥哥发现并举报，从而被父亲关进狗笼，母亲不堪重负选择离家。哥哥在狗笼上挂了一个横幅写着：IN THE NAME OF GOD，而道格看到的是DOG MAN。

GOD→DOG

到这里就是电影第一次呼应片名，这个横幅反过来的镜头特别有趣，但顺嘴一提，正是因为这个镜头导致片名叫做DOG MAN而不是对应中文翻译更符合电影的一些铺垫的DOG GOD（狗神），然而DOG MAN其实更能描绘出主角的人情味，其作为一个拥有伟大心灵的普通人的质感。顺嘴一提，一开始看到这个片名（指狗神）我以为又是什么国产的喜剧电影（你能感受到吧），中西方对于神的认知其实是有很大差别的，给我最明显的一种感觉就是西方很多神有关的故事都提到苦难与救赎，中国像玉皇大帝王母娘娘之类的就有一种与人间的隔绝感和冷淡。当然我不是学神学的哈。

一次一只狗狗生了一窝小狗，父亲端来枪想要解决，道格用身体挡下，断了一根手指，双腿没有知觉。道格拿出母亲曾经藏好的带有警车海报的杂志给一只狗狗看，将断指放进哥哥扔进来的手帕里交给它，狗狗跑出去准确无误地找到警车，将父亲与哥哥带走，救出道格。父亲在狱中自杀，哥哥在8年后出狱被狗们围攻杀死。

林肯鲍威尔

好吧我承认，道格小时候的演员比CLJ好看（但是这个演员林肯鲍威尔Lincoln Powell可能暂且只有这一个作品，前途一片光明啊）。这里第一次展现出道格类似于超能力，其实看完电影我就在想这是不是意味着DogMan也是一个所谓的”超英“（spider-man, iron man, antman之类的），但是他又与当代超英截然不同。道格没有替天行道、拯救世界，他不是个疯子不是个英雄，也没有将善或恶走到极端。这和现如今很多非主流的超英和反超英作品（比如The Boys黑袍纠察队）所表达的：超级英雄也有人情世故。所以相比而言其实我更喜欢DogMan这个名字。话说回来，道格父亲和哥哥的这个结局颇有爽文气质。

2.道格的双腿几乎残废，只有非常紧急的情况下才能起身，并且每走一步都在走向死亡，因为子弹打中了他的脊柱。道格被送到福利院，遇到了一名员工萨尔玛，萨尔玛给他讲莎士比亚，教他化妆，表演戏剧，使他不在孤独。

And remember, if you can play Shakespeare, you can play anything.
记住，如果你能演莎士比亚，你就能演任何角色。

我真的很爱这句台词。影片中有很多Drag Queen元素，但我并不觉得道格是一个“异”装癖，相反，他可以扮演任何一个角色，这些角色寄托了他在童年不幸而悲惨的生活里的唯一希望。“扮演”贯穿了道格短暂的一生，从罗密欧到玛丽莲梦露，道格在这些角色里逃脱世俗，以此表达自我。而一路走来，几乎都是女性在给予他关注，因此，他选择用女装来寄托希望和慰藉。

可不久后，萨尔玛被一个剧团聘用，离开了福利院。后来几年里，道格一直关注着萨尔玛，把她的各种经历做成了一本书。萨尔玛表演后，他来到后台送出了这本精美的书，萨尔玛激动地亲吻了他，可就在道格准备表白之际，萨尔玛的丈夫走来，原来萨尔玛已有身孕。

夸大微表情

你们舔狗不要再舔了。道格和萨尔玛夫妇对话的时候，对萨尔玛夫妇是仰拍，这似乎是道格的视角，然而对道格也是仰拍，怼脸拍，所以这时应该并不是双方对视的逻辑，而镜头逐渐拉近道格的脸，既是放大他的微表情，大概也想说，此后道格只能孤身一人了，他的生活里只有他自己了。

3.道格回到了工作5年的流浪狗收容所，拼命恨锤自己的腿，冒着生命危险站了起来，吼叫着，流浪狗们跑出笼子，像家人一样聚在他身边。道格决心把所有精力都放在狗狗们身上，于是他剪掉长发，不再打扰萨尔玛。

诶嘛，有点吓人

欸哟，开始爽片了。道格在电影里起立的次数不多，这是其中之一，萨尔玛是一个对道格影响很大的角色，她是善良的，没有做错什么。道格从未把他人有意无意带给自己的苦难奉还给他们或是给无辜的群众，道格没有让苦难压倒自己的理智，而最终，他还是和狗狗有着共鸣。

4.政府决定关闭流浪狗收容所，将流浪狗转移，卖掉这块地。道格没有为难他们，自己带着所有狗狗搬进了废楼里。狗狗的食物是很大一笔开销，没有政府的补贴，道格必须要出去赚钱，可是因为他的残疾，处处碰壁。直到他来到一家剧场，舞台上的变装演员让他找到了归属感，在他的恳求下，获得了一首歌的表演时间。他卸下助力器，画上女性妆扮，但一开口，老板和其他观众都为之动容。就这样，他找到了他的事业。

Singing~

其实从此可以看到道格并非一个完全不讲理的人。他和很多角色（特别是小丑）一种完全疯癫且做事的逻辑非常混乱的特点截然不同，可以说，道格未必是一个“精神病”或“厌世主义者”。他没有因家庭而痛恨社会，甚至找到了自己的事业。刚刚说了，“扮演”贯穿了道格短暂的一生，如此，变装舞会让他在一瞬间拜托了其他人对他的忽略和歧视，这使他有一次起身离开轮椅。这一段我还挺喜欢的，挺振奋人心的，虽然我之前没有听歌过这些歌（孤陋寡闻了哎呀）

电影原声带｜狗神 DOGMAN - 歌单 - 网易云音乐，可以参考一下这位佬的歌单。

5.可惜他的工资还是不够补全开销。偶然，道格发现狗狗可以听懂他说话，非常精确，像超能力一样。于是他借用狗狗们从富人家偷取金银珠宝。保险公司调监控发现这些流浪狗，从而找到了在变装秀唱歌的道格，并声称自己是他的狂热粉丝，但是道格出于直觉没有介绍他的邀请。保险公司的职员一路跟随道格来到废楼，职员告诉他，他可以不报警，只需要道格把珠宝归还。在职员的手枪威胁下，道格告诉了他保险箱密码。随后，道格邀请他共进晚餐，然后职员就成了狗狗们的加餐。

发现狗狗大盗

好了，你们最喜欢的汪汪队立大功来了哟。话说这其实很神奇，因为自古以来其实有很多作品（比如电影小说动画片）都体现过人与狗的亲密关系，但相比于生活中和过去的作品里爱狗人士把狗狗当成孩子，又亲又抱的，道格似乎并没有曾与狗狗们如此温馨的亲密的接触，相反，他们是互相理解，互相信任，并肩作战的战友，搭档（虽说道格也称呼狗子们为Kids），并且保持独立。我个人觉得这一段不太出彩，这个职员也没做啥伤天害理咋就没了，而且你这劫富行为多少有点难评了，可能要提示大家道格是个罪犯？亦或者体现他与伊芙琳等人的思路的不同？这样显得道格其实有点天真

6.一天，隔壁洗衣房的玛莎托一个电工送来了一只流浪狗，电工表示最近附近的黑帮一直在收保护费，玛莎已无力承担，希望道格可以帮助她。第二天，道格确定好黑老大的位置，派一条狗叼来电话，另一只狗冲进来咬在黑老大的裆部，黑老大不得不屈服，答应道格不再骚扰玛莎。当晚，黑老大逼问电工出道格的位置之后，带着黑帮来报仇。此时道格画上了玛丽莲梦露的装扮，忽然一声枪响，道格借监控看到了黑帮的动作，于是站了起来，拿出猎枪，准备恶战一场。因为流浪狗体型小加地形优势，很快，只剩下黑老大一个了。黑老大拿着枪靠近道格，而道格已经体力透支，但这一次，上帝站在了道格的一边，黑老大的子弹用完了，于是整个黑帮被团灭。

I wanna be loved by you—Marilyn Monroe
I wanna be loved by you, just you
And nobody else but you
I wanna be loved by you alone
Boop-boop-de-boop!

玛丽莲梦露装扮

这一段要比杀小职员的情节好十分甚至九分，毕竟黑吃黑。虽然这个枪战场面非常的好莱坞，但是无伤大雅。这个玛丽莲梦露的妆造就很有感觉。插播一个很奇怪的联想，就是看到这段时我想到了玛丽莲曼森（一个摇滚歌手），他的名字就是将玛丽莲梦露和著名的连环杀手查尔斯曼森组合而成，形成一种矛盾感。虽说道格和查尔斯曼森迥然不同，但他的“向死而生”和梦露的性感也形成矛盾感。但是这段演唱很可爱其实。这个黑吃黑情节除了爽还有一个两点就是道格的传奇（宗教）色彩：

If it’s God’s will, I guess God is not on your side today.
如果这是上帝的旨意，我猜上帝今天没站在你这边

上帝终于站在了道格这一边。看起来为了主角光环服务，实际上，道格经历了很多不幸，越多的不幸，就会有越神奇的幸运。说到这里，我又跳跃地想到了震惊的张艺谋还好好拍电影时期的《活着》（也就是余华的《活着》），对“塞翁失马焉知非福”的幸运与不幸和活着的意义的讨论很好，但和本片的联系不大，这里不多赘述。

7.道格带着流浪狗逃走，半路被警察拦截，看到一卡车的狗，警察也不知所措，一个眼神，狗狗们仿佛得到了指令，迅速离开， 警察把道格带回警局，心理医生伊芙琳前来审问他，因为他此时正式异装。伊芙琳告诉他，自己有一个孩子，前夫是个瘾君子，还总是骚扰她，道格就讲述了他的过去，因为他认为，两人有共同点：都在承受苦难。流浪狗归来解救了道格。道格解除助力器和轮椅，一步一步走向教堂，倒在十字架的阴影下。最后，一只杜宾犬守在伊芙琳家附近，保护这个和道格一样经历苦难的人。

帅帅的杜宾

这其实是穿梭在整个故事中的线索，但在时间上是最后发生的，这个结尾真的是整个电影里艺术感最强的镜头。最后，伊芙琳和杜宾犬的结尾是对片头拉马丁的话的呼应，有人说很生硬，但我觉得很好，这其实是我没有想到的结尾。然后，这是道格全片最后一次起身。

I can walk, but only to my death. Very Shakespearean, don’t you think?
我能走，但只能走向死亡。很有莎士比亚的风格，你觉得呢？

十字架--耶稣

最终，道格选择走向死亡，向死而生，倒在十字架的阴影里

Here I am. For you. I am standing for you. I am standing for you!
我来了 等你 我站着等你 我站着等你！

我看到了一个很有意思的讲解，传送门](https://zhuanlan.zhihu.com/p/675932456))，讲到了里面很常出现的歌的作者[Édith Piaf](https://zhuanlan.zhihu.com/p/687399917/[伊迪丝·琵雅芙（法国女歌手、演员）_百度百科 (baidu.com)](https://baike.baidu.com/item/伊迪丝·琵雅芙/709742))，一个悲剧色彩但不惧死亡的人。

Piaf人生中最后一次采访，记者问：“你会怕死吗？”
Piaf：“我更怕寂寞。”
(选自上面那一篇文章)

Édith Piaf--玫瑰人生 La Vie En Rose

道格从未孤身一人，在他的《玫瑰人生》里…

Autumn star — Juliette Besson
♪ Let us throw effortlessly in a dream ♪
♪ Be the comfort that I need ♪
♪ 让我们毫不费力地进入梦乡 ♪
♪ 成为我所需要的慰藉 ♪

总结

整个电影给予了我一种边界消失的美感，破碎而颠倒，DOG可以是GOD，上帝可以是残疾人，是罪犯，狗可以是朋友、家人。也有一种绝望与希望并存的美好，小丑都给人一种疯子的魅力，但且走过道格的一生，这是另一种魅力，是且歌且行，是精神的自由，是人性的光辉。

吕克贝松可能想抨击父权，人类对动物的迫害（比如大战黑帮用的都是捕兽夹之类的东西），主流超级英雄，想带来治愈，救赎，自由。可以表达的东西很多，但就像阿凡达2：水之道一样，导致立意不够深入人心。但是足够鸡汤了哈哈哈（）

下期预告

失控玩家？疯狂的麦克斯狂暴之路？奥本海默？美丽心灵？

也可以写点Cult

吐槽蛛网夫人也可以qwq

当然你得再等1个月=P

发表更新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

×

×