本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-09-12 11:44:37

初赛（可能到不了复赛

Day -inf

颓，颓还是颓

Day 1

进考场了，第一题一眼看出时去年第一题，只是改了个问法，连选项都一样，还好我看了解析。

那个基数排序的题，我直接懵逼了，什么宇宙射线，看起来很高级，觉得肯定不能是普通去掉后依然有序，于是蒙了个b。赛后觉得自己是**。

还有一些别的题，什么0*2的n次方，%（-k），输出字符为大O里加一。

其他没啥的了。

Day 不知道多少

教练说66.5，过了，考的还行，安心了。

果然过了，可以去玩喽。

复赛

啊啊啊，山东寄掉了

VP

19:30准时开打，T1不知道什么鬼题，先看的T2,T2分类讨论一下就可以了，自认为很简单，敲了1个小时左右敲完了，大样例也都过了。复杂度$O(n \log n+q\log n)$预计得分100。

开T3，说了好多，最后看见了每个点都能无限走和出度都为一时输出yes，立马想到出度都为一肯定每个点都能走到环，于是干脆搞了一个维护出度的数组和总共出度为一的数量；随便搞一下子，就做到了操作1、3,O(1)，操作2，4，直接暴力边数改，由于我还用了个map记录边有没有。所以复杂度最坏是$O(qm\log m)$，预计得分50。用了大概30个小时。

随后开T4,一眼看上去非常不可做，就没打。

看T1，这个数据范围，我首先就想出了折半搜索，$O(n^2)$可过，于是开敲，敲得过程中发现了思路似乎有些不对，但没有管，40分钟左右就打完了，过了所有大样例，心态非常好。复杂度$O(n^2+nm)$，预计得分100。（结果时间复杂度似乎也错了

预计得分： 100+100+50+0=250

实际得分：0+85+60+0=145（好寄啊，赛后调了大概5天都不知道T2为啥错了，T1思路错了，应该是枚举B,C）

总结

寄寄寄寄寄寄寄寄啊啊啊啊啊啊啊

反转

艹，官方数据好水。

得分：60+95+60+0=215

T1枚举A,B再弄个中转，再枚举C,D能有60分？这复杂度还错了，如果改一个错了的地方，甚至能90？

T2多了10分，发现哪错了，判断 $l2-r2$ 之间有正数也有负数的情况下，直接用了个 max，导致如果 $l1-r1$ 之间只有正数或负数时会出错，设的最小值乘一个很小的正数，和 $l1-r1$ 之间最大正数乘绝对值最大的负数，可能会前者绝对值更小，也就是更大，所以输出了前者。

T3，T4没啥好讲的。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-25 15:22:55

考前

调整心态

试机

1. 敲缺省源
2. 头文件加上cstdio
3. 在每个盘符建个文本，重启看看哪个盘符还在
4. 确认键盘鼠标等无误
5. 编译指令:-O2 -std=c++14 -Wall -Wl,--stack=119845819410
6. 先写好对拍
7. 开自动保存

考时

1. 先读完所有题目
2. 不要死磕一个题，先拿好其他题的部分分
3. 多打表找规律
4. 记得上厕所吃食物
5. 文件名复制
6. vector不要<=size()-1
7. 多卡卡常（说不定呢
8. 自己多造点数据

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-27 19:42:37

寄死了

考前

好像7点0几分就到了，等了好久

试机

先敲了个tarjan缩点（，然后又敲了个字典树，忘了空间怎么开，感觉很慌，开自动保存，开一系列编译命令，打了个缺省源。旁边的人经常看我代码，莫名感觉很慌。

考时

一开始发的密码是solo什么什么的，结果错了，一直到8：40多才有密码，rp--，解压后发现pdf还有个密码，试了试那个密码不对，果断试了solo，果然对了，比别人多出至少15s,rp++

9：10左右看完题目，感觉全都不可做，暴力也很难打，开始思考T1。 先考虑可以光优化C，可以先枚举上下两个边及中间的那条线，如果这条线没有障碍的话，可以分别找出上下两条线往右遇到的第一个障碍，乘起来，再加起来，复杂度就变成 $O(n^4)$ 了，向右第一个障碍和这条线是否有障碍可以预处理，复杂度就变为 $O(n^3)$，在考虑只枚举两条线，上面那条和左边那条，之后对于每个下面的，我们可以预处理，预处理出从上面那条线的+2位置开始，走到下面第一个障碍，所有能够向右扩展的和，处理一个后缀和就可以，复杂度变为 $O(n^2)$

接下来考虑F,可以分别处理右边 第一个的障碍的距离*下面第一个障碍距离，再求个后缀和，就做完了。

想完时时间为9：30左右，9：50就写完了，开始写对拍（还好我写了，不写就完了），10：10左右，写完对拍后，暴力发现马上就错了，把错的那组数据复制下来，试一下，发现又跟std一样了，立马察觉到没有清空，清空后继续拍。拍了一会，又发现错了，复制下来std用试了试又和暴力一样了，发现std也没清空。（太艹了，还好写对拍了

此时已经10：20多了，开T2，最大的错误，每个部分分都不会，很慌，™的打了个$n^m$的暴力，贼难打，还难调，打到12：40多，还没对，非常慌，决定不打了，去看下面的题。

先看的T4,一眼望去只会8分暴力，感觉20分要单调栈，还难调，就没打（丝毫没意识到可以预处理。

打完已经12：50了，检查了一下，准备走

突然被告知延长10分钟，开始想T3，发现链上随机选两个点 $i,j$分别作为起止点，起止点中间军营可以随便放，除这条路径上的其他边也随便选，方案数就为$2^{i-j-1}*2^{m-(i-j)}=2^{m-1}$，于是可以直接做，再加上只选一个点的方案数，感觉没有可以写挂的点，也没测试。啊啊啊啊啊啊啊啊啊啊啊

贴一下我的sb错误： 啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

预计：100+0+10+8=118

洛谷：100+0+0+8=108

小屠零:100+0+0+8=108

落得暴力老哥的分数了，小屠零上显示没到一等奖，但凡我T3检查一下，哎~~~~~~~~~~~~~~~~~~~~~~~~~~

出分了

和自测分数一样，听说T1$n^2m$过了一车，可能没法一等了（108的™到了210多。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-23 22:27:52

题目大意

给你一个序列，定义一次操作为交换任意两个元素，问最少几次操作使得序列变成单调不降，其中值域为 1~4

思路

我的思路有点奇怪。

一眼看去好像可以先把随便一个 1 先交换到最前面，其次是 2,3,4。然后看一下样例二是对的，然而样例一是错的。

样例一发现有两个 1 可以交换到第一个位置，然而我们随机选了一个，实际上是要把第二个 1 换过来，因为 3 正好换到单调不降后它应该在的位置，就节省了操作。

于是大致思路就出来了，对于每个位置，先优先找当前位置上的数应当在的位置范围内，如果有当前位置应当有的数的话，就优先换过来，否则我们默认换第一个。这个东西直接用一个 set 维护即可。

时间复杂度为 $O(n \log n)$，空间复杂度为 $O(n)$

我的代码可能实现的并不好，可以自己实现一下试试。

#include <bits\/stdc++.h>
#define N 500005
#define ll long long
using namespace std;
int n,a[N],vis[N];
\/\/这个函数表示找到值为zhi的数在排完序后应在的区间 
pair<int,int> zhao(int zhi) {
	int ans1=0,ans2=0;
	for(int i=1; i<=n; ++i) {
		if(a[i]==zhi) {
			++ans2;
		}
		if(a[i]<zhi) {
			++ans1;
		}
	}
	return make_pair(ans1+1,ans1+ans2);
}
priority_queue<int> s;
pair<int,int> chu[5];
signed main() {
	cin>>n;
	for(int i=1; i<=n; ++i) {
		cin>>a[i];
	}
	\/\/提前预处理一下，方便O(1)查询 
	chu[1]=zhao(1);
	chu[2]=zhao(2);
	chu[3]=zhao(3);
	chu[4]=zhao(4);
	int lst=1,xian=0;\/\/lst表示当前执行到了lst，xian是为了方便遍历 
	int ans=0;
	for(int qwq=1; qwq<=4; ++qwq) {\/\/qwq表示当前已经排序到了值为qwq的数 
		xian=1;
		set<int> ying;
		for(int i=chu[qwq].second+1;i<=n;++i){
			if(a[i]==qwq)
				ying.insert(i);
			\/\/找到应与当前区间换的数 
		}
		int lstt=lst;
		for(;xian<=chu[qwq].second-chu[qwq].first+1; ++lst,++xian) {\/\/先优先找到换之后还能满足的 
			if(a[lst]==qwq)continue;
			auto it=ying.lower_bound(chu[a[lst]].first);
			bool flag=0;
			if(it==ying.end())\/\/没找到 
				flag=1;
			if((*it)>chu[a[lst]].second)\/\/没找到 
				flag=1;
			if(!flag){\/\/交换并删除 
				swap(a[*it],a[lst]);
				ying.erase(it);
				vis[lst]=1;
			}
			++ans;
		}
		for(lst=lstt,xian=1;xian<=chu[qwq].second-chu[qwq].first+1;++lst,++xian){\/\/再次遍历当前区间，换之前没换的 
			if(a[lst]==qwq)continue;
			if(!vis[lst]){\/\/没有被换过就换 
				swap(a[*ying.begin()],a[lst]);
				ying.erase(ying.begin());
				vis[lst]=1;
			}
		}
	}
	cout<<ans;
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-11-04 10:09:03

题解里怎么都用 trie，让我来篇不用 trie 的题解！

我们先找一下规律，容易发现只要知道了第一个数，那么后面的数就全知道了，现在的问题就是让 $0- n-1$ 中的数全部出现。

我们设构造的数组的第一个为 $k$。 那么：

$b_1=k, b_2=a_1 \oplus b_1,b_3=a_1 \oplus a_2\oplus b_1$.....

以此类推，所以我们发现 $b$ 中的所有数都可以表示为一个数异或上 $b_1$ 的形式。

我们发现直接考虑不太好做，于是我们考虑拆位。

如果说 $0- n-1$ 这些数中第 $j$ 位上有 $sum$ 个 1 的话，我们就必须得让 $b$ 数组最终也有 $sum$ 个 1。所以我们统计一下 $a_1,a_1 \oplus a_2,a_1 \oplus a_2 \oplus a_3...$ 中第j位上有多少个 1，如果说有 1 的个数恰好等于 $sum$，那么第一个数这位上是要填 0 的，因为 $0 \oplus 1=1$，否则就必须填1。

至于为啥有解的话我也不太会证，本来想写个判断的，结果看到题目中没说无解输出什么，就直接输出了。

参考代码实现（写的有点丑）：

#include <bits\/stdc++.h>
#define N 500005
#define M 13000005
#define mod 998244353
#define lowbit(x) (x&-x)
#define ls(x) llll[x]
#define rs(x) rrrr[x]
#define ll long long
\/\/#define int long long 
using namespace std;
int t,n;
int a[N],qian[N],b[N];

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=2;i<=n;++i){\/\/让i从2开始方便一些
		cin>>a[i];
		qian[i]=qian[i-1]^a[i];\/\/处理前缀异或
	}	
	for(int j=0;j<=21;++j){
		if((1<<j)>=n)continue;
		int sum=0;
		for(int i=0;i<n;++i){
			if((i>>j)&1)++sum;
		}
      \/\/统计有应该有多少个1
		int sum1=0,sum2=0;
		for(int i=2;i<=n;++i){
			if((qian[i]>>j)&1)++sum1;
			else ++sum2;
		}
		if(sum1==sum){\/\/如果说1的个数和要求的一样
        ;\/\/那么这位填0
		}
		else
			b[1]+=(1<<j);\/\/否则填1
	}
	ll lst=b[1];
	for(int i=1;i<=n;++i){
		cout<<(lst^a[i])<<' ';\/\/最后已知第一位直接求出每一位
		lst^=a[i];
	}
	return 0;
}
\/*
k a1^k
a1^a2^k
a1^a2^a3^k
*\/

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-11-24 21:47:04

Day -1

这段是在lcez写的，就是有点挤，其他都还行。

面到sym神了，芜湖！

Day 1

芜湖，终于开考了。

8：40看完了四个题，然后我也不知道了（并没有）

8：28准时开题，先看了T1，这不傻帽题吗？

8：29看完题，8：31想出来了，直接排个序后记一下，然后记一个前缀最小，后缀最小，然后比较一下，做完了！

8：38写完了，8：40测完大样例全过了，然后去看了T2!。

T2首先一眼可以算出每个变量等于或不等一开始某个变量的赋值，然后这个东西大概可以扩展域并查集，但是我懒，觉得并查集太难写了，于是建图赋边权。

然后这个东西很奇怪，点不能按每个变量建，得按操作顺序建（就是按第几个操作向第几个操作连边），如果操作为等于（假设a=b），那么就理解为这个操作的值取决于b上次被赋值的操作的位置，于是从当前操作的位置向上次b被赋值的位置连边，边权为1；如果为不等，跟1操作一样的，只不过边权为-1；然后就是等于某个具体的值，这个你可以一开始有三个变量为n+m+1,n+m+2,n+m+3然后连向他们就好了。

那么最终一个点的取值是不是就是这个点在操作中最后一次被赋值的点最终能走到的点，对吧。（有个小细节，一开始我们认为所有变量均被赋值过一遍）

这地方为了方便，我建的是反边。

上面这部分写得挺慢的，大概写到了9：05。

然后就是具体的，怎么才会是U？通过模拟最小的小样例得知，如果说最终一个点不等于这个点，那么这个点得是U，或者说一个点最终等于U，那么它就得是U。

（如果说已经确定一个点等于U了，那么所有等于/不等它的点也都得是U，于是得到一个点是U后，必须遍历它能到达的点都为U）

码码码，到了9：23。欸，小样例过了，然后忘了是第几个样例挂了，U算少了，画了一下图发现，我写的程序是没有错的。然后看了一下，欸，居然有负环！

于是我马上就很慌了，原来不只是自身不等于自身，所有负环都不行啊，这可是难写多了。

但是我又意识到他是一个奇环森林，于是我用了个很sb的行为，用了一个以前听过但是自己从没写过的缩点，就是dfs然后用栈来搞。

写完这个大概10：00了。

它过掉了除最后一个点的所有样例，最后一个大样例它错了，我立马就急了。调调调，最终通过我不懈的输出中间变量(大概10：15意识到的)，最终得出结论我tm找环写错了。

我就不该在考场上写自己不会的啊，于是我立马换成缩点（这地方由于是奇环森林和这个题的特性于是可以建无向边），写写写，10：40过全部大样例了，此时心态良好。

T2写得非常长，177行！

开T3！一眼不会，什么东西，写了个要求一个序列一定严格小于另一个序列。

然后10：47开T4，先想的是一个暴力dp，设$f_{i,j}$表示到了第i个点，已经连续了j天走，能有的能力最大值，转移就考虑每位往后顺移一位，$f_{i,0}$为所有数的最大值，同时清空第二维为k以上的dp数组，然后在每个点上挂一个vector表示以这个点为结尾时的奖励能力值区间有哪些，然后就是一个后缀加。然后没写这个dp，因为想着可以优化。

接着想性质A大概可以矩阵快速幂（但实际上这个是错的），觉得太难写了就没写。性质B大概可以贪心选如果选上优就优（实际上这个也是错的），性质C大概可以直接dp（实际上这个也是错的）（。。。也就是说我的特殊性质想的全是错的，还好只写了B）

继续想那个dp大概可以优化，考虑能不能用线段树优化，考虑到不行（全局往后移这个操作太傻*了，根本没法维护，也没法打标记）

欸，立马意识到可以平衡树，每个点维护一个自身权值，子树max，和子树加的懒标记就可以了，然后每次先都-d，插入就直接往左插，如果子树大小大于k再删掉最后一个点，再搞个子树加上奖励的，就可以了。

想到这是11：25，看了眼有56pts，很激动！于是开写！11：38大概就写完了，我之前从没写过平衡树维护区间加这种懒标记，于是我先自己造了一组最简单的，就是2天，最多走2天，走1天1，1-1天都走有5权值。

一测，果然寄了，输出了5。

直接输出了所有东西啊啊啊，所有东西啊！整棵树都输出了，1号节点和2号节点都没有5的但是最大权值却是5，然后就调了好久。

12：10意识到原来如此，我的0号节点权值应该赋值为-1e18啊，一改，果然过了，然后小样例也过了，大样例WA了（怎么回事呢），原来是一个地方写错了，改了后就过了。然后立马把我的贪心性质B写了上去，然后过大样例了，很安心，觉得有64pts了。

12：20火速回来看T3，首先意识到得写暴力了，不能想太多，于是先把操作序列复制一遍，然后改，如果$a_1==b_1$无解，否则如果$a_1<b_1$那么整个序列都得小于；反之，都得大于。于是先把这个给判掉，然后就想到可以$dp$，设$f_{i,j}$表示第一个序列匹配到了第i个，第二个序列匹配到了第j个，每次可以两个同时往后一个，第一个往后一个或第二个往后一个，然后就行了。

写写写！12：40写完了，惊险！过了大样例。

开始检查，okT1没问题，okT2没问题个鬼啊，自己没检查出来，okT3没问题啊，okT4没问题啊。

立马加上曹神和sym ak noip！

着重检查了第1，2，4题，又测了一遍大样例。

在12：55的时候，老师提醒了建文件夹的问题，还都检查了一遍。我等他检查完我的后又测了一遍最大的大样例，确认没有问题。

12：58时还是不放心，又编译了一遍，都没错，立马删掉exe文件。

13：00 结束了！

出来后本来还想等等sym的，结果没等到，然后就直接出来了，cxm神335！太强了！

于是估分：100+100+35+64=299

在车上，山东代码很快就出了。

先是信友队出了T1数据100，然后等了好久好久云豆出了T1,T4数据100和56。一问原来没有考虑相邻的情况，大样例都过了，希望CCF的数据水一点。

然后云豆又有T3数据了，35，没问题。

回家后洛谷也有了也没挂，hyt说还有核桃，核桃倒是没有挂分299。

之后我突然想起小屠零，一输入，怎么只有前2题数据啊，一看

190!

？我tm这么多民间数据都过了，到你这T2怎么90WA了？ 一检查，md啊啊啊啊啊啊啊啊啊啊啊啊啊啊，多测没清空，因为在上文我用到了$n+m+1,n+m+2$和$n+m+3$，但是没有清空他们导致自己挂了，hyt帮忙拍出来了，结果我改了这个地方后就过了。

1000组大概拍出来30多组错的，希望CCF数据水一点！

同时意识到我T4那个dp是有多sb的行为，第二维如果说改为[j,i]之间都走了那就56分比这好写多了，只用线段树，然后100分离散化一下就做完了。

Day 11-24

出成绩了

100+100+35+64=299

谢谢你CCF!

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-03 22:27:13

寄了

Day -1

下午跟杰神一块走的，大概5：00就到了。吃完饭后去超市买了两瓶百事可乐，之后去试机了。

遇见了hyt，好久没见了，还有myf，和

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-03 18:54:59

Day -1

赶回山外，路上打板子+颓废。到地方比较晚，先去找wfyz的人一块颓，屋里很多人，先打几把王者再说。

过了一会lxn过来了，问我们吃饭在哪吃，她说旁边有夜市可以去那吃，也可以点外卖。我们当然决定去夜市吃，于是回屋收拾东西，然后直接出发。

在经过长时间的寻找后，发现没有什么想吃的东西，要么太贵，要么太难吃。于是回屋点外卖，点了1汉堡+2翅根+可乐，仅需14！非常的便宜啊。吃完后复习板子，然后就去试机了。

试机路上什么人也没遇到，我一进考场就已经要热死了，这里就像开了暖风空调一样，又闷又热。

我一看这个键盘就有问题，这个空格按一边另一边会翘上去，导致我想要按空格必须要按到正中间，这也太难受了吧。于是找老师换，结果老师还说这便宜键盘就这样，只有中间有啥玩意，按旁边没用，于是他又拿起旁边的键盘按空格，发现空格键完好，啪啪打脸。于是立马给我换了个键盘让我试试，我试了一下，空格确实非常的好用啊，于是老师走开了。在敲代码的时候shift tm的按下去上不来了，我以为是我的问题，这次我轻轻的按，结果还是上不来。又找老师换，老师给我键盘哐哐来两下，说好了。我一试，嘿还真变好了，又敲了一遍a+b，又坏了，继续找老师换，终于给我换了。拿到手之后再敲一遍键盘，嗯好用。打开dev想敲代码，md连dev都打不开了，双击打开了dev的属性，找老师，老师不知道咋回事，给我重启了一下还真好了。又敲了一遍a+b后就走了。

去找hyt，跟hyt一块去找绝帆，原来wjr也在这个考场，然后没聊几句就出去了。开始在门外等人，看见了一堆人，忘了有谁了，然后因为时间有点晚了，就走了。路上还被mdy妈妈拦截住，拍了个照，然后又看见了lhy和pry，回到车上都是最后的了。

回到酒店后，去lx屋里摆，其他人貌似在打MC,过了一会lxn不知道怎么神秘穿进来了，抓了所有人，直接要求各回各屋，我就只能回去了。

回到屋后，lmn还在和他们MC联机，然后他们貌似又换了一个阵地，但是我也不想过去了，怕再被抓。睡前又看了看板子。

Day1

早上被lxn敲门敲醒的，都9点了，我以为lmn订闹钟了，结果他没订，她进来让我们赶紧去吃饭说不定还能吃一些，但是我们直接决定不吃了，距离午饭也就不到2h，还不如不吃。于是上午就复习了一下板子。

中午饭要50说是自助餐，结果很难吃。感觉不如点外卖。

下午去车上的时候拿了5瓶水，想着去考场要多喝一些水。到地方后又碰见wyd了，后面也没啥事，就进考场了。

到考场后大概2点，这次监考真严啊，不让碰键盘和鼠标，让我们先解压，解压后就不让动了。大概28的时候有密码了，等输完后正好30。

先开T1,哦感觉是简单题啊，速切！先写了个dp，发现样例2过不去，忘了一堆东西。又写了个更多细节的dp，还是过不去，想到可以2分答案！又想了一下是双log的啊，还带set，想一下能不能优化成单log，发现可以用指针实现，于是愉快的做到了单log，写完还是过不去，哦答案输出反了。改了后就过了，此时都已经3：47了。

T1用了17分钟，接下来必须提速了。看T2,T3，发现T2题面很长，T3比较简短，于是先开T3。看完后，？我咋只会2^n，哦哦可以dp n^3。欸等一下，这不是经典dp吗，可以变成n^2，接下来想一下发现可以用set优化，写完后大样例全过了，但是注意到大样例不是满的，我自己又搞了一组满的，发现跑了1.2s？？？我难道必须线性？思考了一下本质，发现可以直接用一个变量维护，于是愉快的改了一下，再测，只需要0.6s了。

再看T2，发现有加速度，不是？加速度为啥不带单位啊，这我咋搞？感觉很慌，看完题面后，发现最后有公式，感谢ccf。看了一下，第一问是简单的我可以简单求出他是否超速，第二问的话，发现能使他被超速的一定是一段区间，分加速度>0和<=0分讨二分即可。然后相当于选最少的点覆盖每个区间。这个似乎是贪心，好像是右端点排序后直接选最右边的，判断是否有点在区间内，这个可以树状数组，非常的好写。调完小样例后，看第二个咋WA了，哦对应该是按l排序，我傻了。改了之后就过所有样例了。

此时是3：55，检查了5分钟后。4点准时开题，哦哦哦哦。怎么加强了这么多次，先想一次T的一次询问咋做，我会枚举每个数分别为什么的做法！哦，只能过第一个点。再想一下。ai先与18取min！然后先建线段树求出每个区间是谁赢，然后求前缀一定是一颗子树，先向右递归，然后一定是一段前缀是已经确定的或者右子树是新加的。然后大概可以递归求吧，思考一下，可以dp，设$f_i$表示能力为i的可以赢的下标和，$f_{18}$表示新加的能赢的下标和，再分讨一下就能$log^2$了。思考一下能优化单log吗，本质是查询前缀是否有1，还有前缀赋0，我会线段树！log*loglog，哦均摊一下可以set也是这个复杂度，再想一下，我可以开一个数组来表示每一个点是否有值，哦哦！我可以bitset，哦哦值域才18，我可以开一个变量，这样就是单log的了。此时大概是4：40，想一下线性，咋优化都不会啊，我必须dp啊。然后想到5点，不行我得开写了，线性肯定很难啊，写的过程中，5瓶水全喝完了，喝了550ml×5了，哎呦渴死我了！最后5点46样例全过了，哎，测一发64的0.8s（这个自己造的，都没卡满），测一发128 1.6s，咋还正好两倍的啊。不管了，CSP谁卡常啊，觉得可能能过92，再不济也是84啊。

开始检查错误，一个错误没检查出来就出考场了。出来问道hyt300，有人说cxm300没调出来T4，没挂分应该能去WC了。然后谁也没碰到就走了。

然后可能上了20次厕所吧，不知道为啥特别想喝水。

Day 11111111111

机子真厉害啊，挂了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-21 16:08:12

PKUWC Day1

T1看半小时没思路，先看T2发现是数据结构，我爱数据结构！

想做法，先想l=1,可以直接扫描线求虚树。l不等于1呢，一个比较好的想法是改为链chkmx，求对应层数上>=l的个数，发现我貌似可以对一个连续段进行一起做，复杂度正好n两log，m一log。写着写着发现m上也带2log，遂沉思，发现没有更好的做法，先写。写完过不了，调样例，调了30min，终于过了。交！测了1min，后三个点RE,前面的点都过了，开大数组，再等1min，过了，非常激动。立马看T1,认为过T1就是赢！！

T1想了一下，转化为加最少的边使得最大独立集<a，不太会做，a>b+1的时候，答案是好求的，每个连通块连1条边。想一下，怎样加最少的边使得最大独立集-1，可以先每个连通块都连一条，然后就不会了。猜一下每个连通块为一个团，n^3感觉可以过，样例过了，交一下全T。改为300，发现前几个点过了，很激动，改为一个团最多100个点，WA。思考一下，改为连通块个数<=50的时候一个团可以很大，否则最大为100，交一下，过了。

看一下T3，很悠闲，发现第一档很简单，第二档觉得是n^3/w,思考一下可以多加一维0/1，表示目前谁操作，就可以n^2。写tarjan，交一下不过，再交一发还不过，改一下过了，剩下20min坐牢。

出来发现220的分数不是很低，发现别人T2都是n三log，m两log，讲了一下我的做法，发现我的做法n实际上是3log的。

睡觉。

PKUWC Day2

看T1，想许久不会。1分都不会。穿插着看了T2和T3,先写了T3暴力，T2只会nV，写完后思考一下500怎么做，发现dp第二维并不会满，于是用map存第二维写完发现过500了，剩下的都RE，改大数组，5000也过了。发现我这个东西很好卡，可以被卡到nV^2，不管了反正是ioi赛制。

T1依旧不会，最后9min调出t1的16。结束，T1做了3个小时多还是不会。

WC

不会T1

不会T1

不会T1

不会T1

不会T1

不会T1

不会T1

不会T1

不会T1

不会T1

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-06-08 18:57:56

思路

要求出的数量就等于自己买的加免费的，自己购买的就是 $s$ 除以 $c$，而送的就是买的个数除以 $a$ 再乘 $b$，所以代码就出来了。

代码

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
	int t;
	cin>>t;
	while(t--){
		ll s,a,b,c,mai,song;
		cin>>s>>a>>b>>c;
		mai=s\/c;
		song=s\/c\/a*b;
		cout<<mai+song<<endl;
	}
	return 0;
}