P9041[PA2021]Fiolki2题意给一个\(n\)个点\(m\)条边的DAG和一个常数\(k\)。定义\(f(l,r)\)表示最多选择不相交路径条数，满足起点\(s\in[1,k]\)，终点\(t\in[l,r]\)。对所有的\(x\in[0,k]\)，求出有多少\([l,r]\subseteq(k,n]\)使得\(f(l,r)=x\)。\(n\le10^5,m

题目给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M<=m*p，则称这个数列是完美数列。现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。输入格式：输入第一行给出两个正整数N和p，其中N（<=105）是输入的正整数的个数，p（<=109）是给

T1P11474[COCI2024/2025#3]公交车/Autobus愤怒，从红升橙足以说明其恶心，考场上调了半小时才过。这道题的车能够开\(24\)小时，并且他能从前一天开到第二天，由于它只能开\(24\)小时，所以说发车时间的时刻晚于或等于到达时间，说明他开了一天，由于这个，所以我们要处理\(3\)天的

消失之物发现背包顺序无关，那么就支持\(O(n)\)撤销任何一个物品。时间复杂度\(O(nm)\)。当然也有唐氏的线段树分治和多项式解法，强行带个\(\log\)。code#include<bits/stdc++.h>#include<bits/extc++.h>//usingnamespace__gnu_pbds;//usingnamespace__gnu_cxx;usingn

hahaha，太菜了，成功垫底力。rank3,T1100pts,T20pts,T30pts.T1好像是神必贪心，写了个不知道对不对的做法，反正过了大样例，就这样吧。T2不会，写了个\(2^n\timesn\logm\)的暴力，可能是dpor图论？T3没读懂题。总结：菜。upd:T1过了，T2边权只有0/1我打什么dijkstra啊？T3是送分题？inte

碎碎念不去做专题做这个是吧？

还没打完数学专题呢就来打这个了。（其实是不会多项式）难度大概升序。GivingAwards注意到一个关键信息：每对人只会被提到一次。所以一定有解。考虑卡bug，假如\(a\)欠\(b\)钱，那么就先让\(b\)取钱再让\(a\)取钱，建边dfs即可，注意图不连通。点此查看代码#include<bits/stdc++.h>usi

题意\(n\)个物品，体积\(v_i\)价值\(w_i\)，做01背包，\(n\le10^6,m\le5\times10^4,v_i\le300\)。原题忘了叫啥了。分析发现\(v_i\)非常小，考虑把物品按照体积分类，逐类处理。对于体积为\(i\)的物品，我们肯定要按照价值从大到小取。将这些物品排序做前缀和，设选前\(i\)

Preface期末周闲的没事写一场小白月赛我会在代码一些有必要的地方加上注释，签到题可能一般就不会写了.以下是代码火车头：#include<iostream>#include<algorithm>#include<cstring>#include<cmath>#include<vector>#include<set>#include<queue>#include<map>

A-aaaadaa(abc384A)题目大意给个长度为n的字符串，以及两个字母a和b，要求把字符串中不是a的字符全部都变成b。解题思路一个循环判断一下就行了。代码#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;chara,b;cin>>n>>a>>b;st

Preface随便v的一场，这场难度不高呢，感觉有些小水，不如前面几场的难度，反而字符串那题更难一些。我会在代码一些有必要的地方加上注释，签到题可能一般就不会写了.以下是代码火车头：#include<iostream>#include<algorithm>#include<cstring>#include<cmath>#include<vector>

题解：P11179[ROIR2018Day1]管道监控秒秒题。没有题解呢，来发一发。建议降蓝。思路发现往下匹配路径不好处理，于是反转每个路线的字符串，然后从下往上移动覆盖，这样定了一个方向。若只输出最小值，就从下往上dp，发现可以\(n^3\)处理，猜测正解设两维状态，\(\Theta(n)\)合并。第一

Preface只能说阅读理解能力有待提高，\(B\)题看了半天愣是看不懂一点。只能跳了。依旧是复习篇，感觉队友当时开出来的\(dp\)难度不低，感慨张神的强大。我会在代码一些有必要的地方加上注释，签到题可能一般就不会写了.以下是代码火车头：#include<iostream>#include<algorithm>#i

思路这是一个典型的背包问题。我们可以设\(dp_{j}\)为武器总强度为\(j\)的情况下的最小花费。于是，根据背包问题的模型我们就能得出：\[dp_j=\max_{1\lei\len}dp_{j-c_i}+p_i\]最终，答案就为第一个大于等于\(P\)的\(dp_j\)的下标\(j\)。时间复杂度为\(O(Tn

题意有\(n=x+y+z\)个人，每个人有\(x_i\)个金币，\(y_i\)个银币，\(z_i\)个铜币，你需要选择\(x\)个人获得其金币，\(y\)个人获得其银币，\(z\)个人获得其铜币，求获得币数量的最大值。\(n\le10^5\)分析不妨先钦定所有人都选金币，然后令\(a_i=y_i-x_i,b_i=z_i-x_i\)分别表示将这

A-DailyCookie(abc382A)题目大意给定一个长度为N的字符串，有很多.和@，一共有D天，每天会使一个@变成.，问D天之后有几个.解题思路数一下有几个.，答案会加D个.。代码voidsolve(){intn,d;strings;cin>>n>>d>>s;cout<<count(s.begin(),s.end(),'.

20241028A.铁路2题意简述给一棵树，每次跳一条简单路径，定义\(f(x,y)=\min(\texttt{x到y经过的简单路径长度})\)求\(\sum\limits_{i=1}^n\sum\limits_{j=1}^nf(i,j)\)思路注意到，一定存在到直径端点的方案，找到直径，搜索即可CodecodeconstintN=5e5+10;intn;ve

\(\mathbf{Luogu\Atcoder}\)页面题目难度设置紫，从上向下排刷。ABC133F离线后树上差分。设四元组\(\langleu,c,v,w\rangle\)表示从\(u\)点开始到根，颜色是\(c\)的权值全部替换成\(v\)，答案需要加/减。设\(f_u\)表示从\(u\)到根颜色与\(u\)相同的点的个数，\(

线性基的定义：若干\(0,1\)向量的集合\(s\)，使得\(\forall\overrightarrow{v}\ins\)，不存在\(p_1,p_2\cdotsp_k(\overrightarrow{v_{p_i}}\ne\overrightarrow{v})\)，使得\(\oplus_{1\lei\lek}\overrightarrow{v_{p_i}}=\overrightarrowv\)。线性基可以类比于平

上一个写的太多了，卡爆了。所以再开一个。P4321随机漫游一道综合多种算法的好题。首先按照图上随机游走的套路，再依据\(n\)很小的限制，可以设出\(dp\)方程：设\(f_{s,u}\)表示当前走过的点集为二进制数\(s\)，当前在\(u\)点，再走完所有点的期望步数。那么显然有\(f_{(1<<

状态很不好，恼了。虚拟机太卡了，根本交不上去。flandre发现选取的肯定是从大到小排序后的一个后缀，然后就做完了，时间复杂度\(O(n\logn)\)。点此查看代码#include<bits/stdc++.h>usingnamespacestd;#definerep(i,s,t,p)for(inti=s;i<=t;i+=p)#definedrep(i,s,t,p

2023ICPC亚洲区域赛南京站The2ndUniversalCup题解更新至7题Preface住院了，在医院闲得无聊自己V了一场。这场复习赛，貌似半年前还是一年前打过一次，只过了4个题。今日来还愿了。但有些题还是不会做，真的唐。我会在代码一些有必要的地方加上注释，签到题可能一般就不会写了.

更新日志概念将所有询问离线下来，对这个整体进行二分答案。思路通用的思路是，考虑对于单个问题，如何二分答案。然后将所有二分答案压缩到一次二分答案之中。更详细地，我们将所有询问储存在一起，每次二分答案时，将询问分成两类：当前mid已满足的和未满足的。那么，下一次二分时，答

更新日志思路和一维没有多大区别。插入时，双重循环，分别循环两个维度。查询时同理。细节如果查询区间和用二维前缀和的方法即可。模板structfenwick{lldat[N][N];intlowbit(intx){returnx&-x;}voidadd(intx,inty,llv){for(inti=x;i<=n;

赛时坠机了，赛后把F做出来了。。刚开始做不出来，后来注意到样例输出了长度为\(n-2\)的询问，启发我对于每个相邻数对\((i,i+1)\)，将其删去再进行询问，其中\(i\)为奇数，共消耗\(50\)次。然后我们对输出的两个数\(x,y\)进行讨论：如果\(x,y\)满足\(x=\fracn2,y=\fracn2