貌似又活了，有多余的名额分配下来了qwq，开心。不过内容就不改了，看看也好，好运气不是每次都能撞上的qwq。 Update:2020.6.17 好吧，还是凉了qwq。心态有点炸。。。 Update:2020.6.23 一.前言 作为一个whk生，在信竞上打拼了3年，从懵懵懂懂连c++是个啥都不知道，到现在的水平，感觉也挺不错啦！ 唯一的遗憾就是时运不佳，CSP2019不慎考炸后，又恰逢疫情然后SCOI延迟，延迟期间又恰逢疫情二次爆发，导致有资格参加SCOI的人数剧减。于是。。。哈哈哈。。。 尽量把心态调整过来吧。。。 作为一个前辈，自然也想留下点什么，证明我来过（哲学）。然后，希望未来在大学...

一.闲话 哎，之前开C的时候，发现有点计算几何的味道，就打算放放，开D，结果发现D是数论，于是就决定搞出来了。然后一直Wa。。。debug了几个小错误后，实在没发现错了。。。结果后面rejudge就过了？？？/xk 二.题解 首先，这题几个结论: 1.我们不会选两个相同的数（除了用1来补满和以外） 这个证明就不说了，很naive 2.我们放的数一定是放的一个质数的k次方。 为啥呢？ 我们分析下，假如我们放了一个数那么，其实，等价于我们分别放了两个数(甚至我们单独放这两个数的答案可能还要大点。。。)，然后，由于恒成立，所以贪心来看，我们用更小的代价，换到了更大的收益，那么要获得最大收益肯定是用的...

注意，答案直接向下取整！！！ 被这个玩意儿坑了，好惨啊。。。 关于这道题，我们先来看看m是奇数怎么做。 很明显，我们可以考虑枚举中位数，然后判断其是否可行即可。这样，我们先对所有物品按价值从小到大排序。 那么，如果一个物品可以作为中位数，当前仅当存在一种方案，从这个物品的左边选个物品，再从它右边选个物品，他们的容积和加上该物品的容积小于等于背包容积v。那么，我们明显只需要贪心去取，每次取最小的几个即可。 那么，我们设表示，我们从i号点左/右取个物品的最小容积和。 对于这个，我们直接开个优先队列，使得优先队列的元素是当前最小的个元素即可。 那么，枚举i时，我们只需要判断下是否小于等于v，即可。 ...

挺简单的一道概率dp+简单数论+简单容斥题目。 由于是编译器小白，枚举了n次编译器qwq。。。 c++的同学建议用clang++17那个编译器qwq 一.概率dp+简单数论部分 比较容易想到的，我们设表示当前gcd为i，期望步后到达1 初始化 然后，我们来推下转移方程: 明显的有， 那么，我们只要分两种情况分开讨论即可。 注意到，当且仅当,也即是共有个 当时，即我们设 那么将原转移方程移项后有: 因为n和al的值都可以O(1)获得，那么，我们只需要计算出al就好了。 我们直接枚举j肯定不行的，会T惨，那么，我们考虑枚举 因为，有一定是i的约数，所以我们枚举i的所有约数即可 设当前枚举的为...

嗯，这次比赛证明了，打得快不一定排名就高。。。qwq大佬们的程序跑得好快啊 A.夹娃娃 狂爆手速拿下一血，成就感++ 题目就是给你个数列，让你求若干个区间的和。 直接预处理出前缀和，然后回答完事。。。 代码: #include <bits/stdc++.h> using namespace std; const int N=1e5+1; int s[N]; int main(){ int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;++i){ scanf("%d",&s[...

贴一波谷歌翻译~ 注意，这题中每个方便面的分发是唯一的 由于本人英语和语文辣鸡，所以完美将此题看错。。。 出题人告诉我们：每次我们将一个大小为N的方便面分块时，我们要尽量使得所有的块小，而不是任意分成等差数列。 由于我看错了题，所以我们先来讲讲分成任意等差数列怎么做。（大雾） 我们设dp[i]表示大小为i的面最多可以分多少次。 那么，如果我们要求dp[i]的值，就需要枚举所有等差数列了。因为T很小只要判断够快，就貌似可行的（没试过） 但是，这样明显不够优秀，我们考虑直接预处理枚举等差数列。 我们先枚举首项，然后依次算当前等差数列的和，若大于n，就break掉就行了。 但是，这么做的复杂度是...

一.闲话 最近准备省选，好久没写题解了qwq，今天的比赛挺有意思的，就来写几道题吧,qwq 二.题解 G.Mathematical Modelling Class 这道题只要读懂题其实挺简单的。但是貌似没几个人读然后被我这个菜鸡拿了一血（大雾） 题目大意： 有n个人，将每个人划分进A,B两组中的一组，第i个人划分进A组后，对A组的贡献为ai；划分进B组后，对B组的贡献为bi(ai,bi={0,1}),求是否存在一种方案，使得A组划分进了个人，B组划分进剩下的人，且A，B组的总贡献一样。若存在输出任意一种划分方式，若不存在输出-1。 读题后，我们发现，其实，一共只有四种人，即: 1.ai=0,b...

qwq，这个比赛的C题，当n=18的时候，我这边的答案是7(第一次分成5+6+7,然后5,6,7都可以分两次，所以总共7次)，但是AC程序的答案是6，qwq 是菜鸡读错题了吗qwq

今天状态不好啊，净是犯小错误qwq A.小A买彩票 一道签到题。 注意到，概率=不亏的方案数/总方案数 而，总方案数=(每次从1,2,3,4中选一个，选n次) 那么，我们只需要计算的就是不亏的方案数了。 我们注意到，n很小，而且，最多可以获得的也才元(先不考虑支付的元) 那么，这个明显可以使用dp统计方案数。 我们设dp[i][j]，表示前i次抽奖中，不考虑支付的3*i元的情况下，获得j元的方案数。 那么我们只需要分当前中的是1元,2元,3元,4元四个情况考虑转移即可。 最后，我们直接统计获得的钱数不小于3*n的方案数之和即可。 复杂度: 代码: #include<bits/stdc++...

这题我们要这么考虑： 如果一种货币可以被另外的一种或多种货币表示的话，那么这种货币明显就是不必要的。 而答案，明显就是所有必要货币的个数。 那么，我们来考虑下怎么做。 首先，很容易发现的是，面值最小的货币一定是必要的，因为它不可能被其它货币表示。 然后，我们再同样的，看面值次小的，这时，我们有两种情况： 1.次小的可以被最小的表示，即次小的是最小的倍数。那么次小的就是不必要的 2.次小的不能被最小的表示，那么明显，它也就不能被其它的货币表示了，所以它就是必要的 那么，我们就可以按这个思路依次推导下去。。。 我们设dp[i]表示面值i能否被当前的已选择的必要货币表示 我们先将所有货币的面值由小到...

这次比赛真的。。。槽点满满啊。。。A,C,D,E都有问题。。。（害我罚时高到飞起） A.第k小数 读完题，我：这nlogn直接艹，问题不大！ 然后。。。 段错误*n 我:??? 然后，天真的以为sort出锅了，码了个基排。。。 然后。。。 段错误*n 我:??? 之后，自暴自弃，数组开个1e7，于是。。。 答案正确。 我:??? emmm，这题，没啥技巧，sort被卡了，直接上无脑基排吧。。。 注意分正数和负数两个情况讨论 代码: #include<bits/stdc++.h> using namespace std; const int N=1e7+1; int a[N],d[...