2 romiqi_new

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 2w+

[2-sat][POI2001]和平委员会

根据宪法,Byteland民主共和国的公众和平委员会应该在国会中通过立法程序来创立。不幸的是,由于某些党派代表之间的不和睦而使得这件事存在障碍。此委员会必须满足下列条件:每个党派都在委员会中恰有1个代表,如果2个代表彼此厌恶,则他们不能都属于委员会。每个党在议会中有2个代表。代表从1编号到2n。 编号为2i-1和2i的代表属于第i个党派。任务:写一程序读入党派的数量和关系不友好的代表对...

2018-10-19 21:55:50

191106CSP(NOI?)模拟及NOI(CSP?)模拟题解

CSP模拟:T1:求∑i=1n∑j=1mCgcd(i,j)B%mod\sum_{i=1}^n\sum_{j=1}^mC_{gcd(i,j)}^B \%mod∑i=1n​∑j=1m​Cgcd(i,j)B​%modn,m≤1e10,B≤mod=9990017n,m\le1e10,B\le mod=9990017n,m≤1e10,B≤mod=9990017莫比乌斯反演,设f(i)f(i)f(i)表...

2019-11-06 18:45:59

191101CSP模拟题解

T1:给定n,k,ln,k,ln,k,l,求nnn个数每个取值[0,l][0,l][0,l],其一个子序列和为kkk的方案数,n,k≤20n,k\le 20n,k≤20补集转化,是个背包,然后状压算方案,dp of dpCode:#include<bits/stdc++.h>#define ll long long#define mod 998244353using nam...

2019-11-01 17:02:06

191026考试题解

T1:求一个网格图从原点出发走n步,每步等概率往上下左右走,最终到达的点和原点之间的欧氏距离的期望打个表可以发现是n,完了具体证明可以推式子或者三角函数#include<bits/stdc++.h>#define mod 998244353#define pii pair<int,int>#define pb push_back#define mp make_...

2019-10-26 16:48:13

191024省选测试题解

T1:有n个不相交矩形障碍,求从原点走到某个目标点的最短路,目标点在x轴上显然矩形的右端点是没用的,我们保留左边即可显然不会往左走,dp一下是n2n^2n2的,用扫描线优化一下即可#include<bits/stdc++.h>#define pb push_back#define ll long long using namespace std;inline int re...

2019-10-24 16:15:59

[LOJ2339][虚树][边分治][树形DP]WC2018:通道

LOJ233944pts暴力就不用讲了两棵树的做法似乎是个套路?先拆距离变成dep1[x]+dep1[y]−2∗dep1[lca1(x,y)]+dis2(x,y)dep1[x]+dep1[y]-2*dep1[lca1(x,y)]+dis2(x,y)dep1[x]+dep1[y]−2∗dep1[lca1(x,y)]+dis2(x,y),然后就可以在第一棵树上从下到上枚举lca,消去lca的影响,...

2019-10-21 17:37:22

191015NOI模拟总结

T1:CF643D解法:是一道模拟题。。。我们可以用一个set维护全局最大值,然后再用n个set维护所有当前点的ans,用这n个set更新全局set即可完成3操作考虑修改的影响,会影响到它和其原来父亲,并且父亲的E会改变从而导致父亲的父亲的答案也改变,新的父亲也是一样的,更新全局答案时注意处理三个点的环的情况,然后就是模拟了Code:#include<bits/stdc++.h&g...

2019-10-16 10:04:44

191012CSP-J模拟题解

T2算答案加成了矩阵的一行然后调了我2个小时T1:求图的仅在一个简单环中的边显然点双Code:#include<bits/stdc++.h>#define pb push_back#define fi first#define se secondusing namespace std;inline int read(){ int res=0,f=1;char ch...

2019-10-12 13:44:28

191007CSP-S模拟题解

博主来口胡联赛组巨佬们的考试题辣T1:给一个序列,保证只有两个数出现了奇数次,求出这两个数数据范围只允许O(n)O(n)O(n)显然考虑出现奇数次的数字和出现偶数次的有什么不同,当然是全部异或起来后出现偶数次的全没了所以先全部异或起来得到两个所求数的异或值,这个异或值某一位为1表示某个数这一位为1而另一个数这一位为0,那就把这一位为1的数再全部异或一遍就完了Code:太傻逼不想写T2:...

2019-10-11 19:26:20

191009NOI模拟题解

T1:给你一个长为n的数组,下标从0开始,每个数都是0…9,你需要回答Q个询问:给出li,ri,求区间[li,ri]中所有数的乘积模10的结果。小A轻松地解决了这道题,现在她想知道:给出n,Q,li,ri,以及每组询问的答案ansi,求原数组有多少种不同的情况?n,q≤100n,q\le100n,q≤100先用中国剩余定理转化为%2和%5的情况,然后分别统计,最后乘起来考虑一个点为0的情...

2019-10-10 10:55:46

[CF1137F][LCT][树状数组]Matches Are Not a Child's Play

CF1137FLCT神题。。。首先三操作显然就是两个二操作然后我们考虑一操作会造成什么影响我们将权值最大的那个点看作根,一个点进行一操作后,他到根节点这条路径就会最后被删除,其他的点删除顺序不变,这很显然考虑这段链,一定是从原来的最大值那一头删到当前最大值这一头,那我们就把新的最大值作为根,这就很像LCT了所以我们把会从下到上按顺序删除的链看成实链,那么不同链之间的影响只与链上最大值有...

2019-10-06 16:55:02

191005CSP模拟题解

T1:对于每条边,求删了这条边原图能否成为二分图,点边规模2e6解法:首先判掉无奇环和一个奇环的情况一条边合法当且仅当其属于所有奇环的交集且不属于任何一个偶环(会构成新的奇环)那就弄个dfs树,对于每条返祖边树上差分一下,奇环+1偶环-1,最后看差分值是否为奇环个数即可Code:#include<bits/stdc++.h>using namespace std;inli...

2019-10-05 17:08:54

191003NOI模拟题解

T1:题目大意:给你一张图,每条边有边权,要求保留边权和尽量大的边使得每个点至多有一条出边和至多一条入边,点数200,边数5000解法:显然的二分图最小费用流,可行流即可不需要最大流Code:#include<bits/stdc++.h>#define ll long longusing namespace std;inline int read(){ int res=...

2019-10-05 16:43:36

公告

博主忙于训练,暂时只更新考试题解,偶尔会更一点之前做的题的题解

2019-10-05 16:39:55

190930模拟题解

T1:你在跟朋友玩一个记忆游戏。朋友首先给你看了n个长度相同的串,然后从中等概率随机选择了一个串。每一轮你可以询问一个位置上的正确字符,如果能够凭借已有的信息确定出朋友所选的串,那么游戏就结束了,你的成绩就是所用的轮数。由于你实在太笨,不会任何策略,因此你采用一种方法,每次等概率随机询问一个未询问过的位置的字符。现在你想知道,在这种情况下,你猜出结果所需的期望次数。状压DP,预处理一个f...

2019-10-02 17:08:03

[LOJ2197][线段树][凸包][三分]SDOI2014:向量集

LOJ2197和UOJ191unknown类似我们知道点积等于一个向量的长度乘以另一个向量在这个向量上的投影的长度那么如果我们把范围限制在180°内,则这个函数是单峰的,那就可以线段树维护上下凸壳,查找的时候三分但是直接维护会T飞,因为需要合并,复杂度很高换一种方法,我们是从左到右依次加入的,那就意味着如果我们要查询线段树的一个节点的话,那这个节点对应的区间一定被填满了,所以我们可以在填...

2019-09-29 23:19:33

[BZOJ3203][凸包][三分]SDOI2013:保护出题人

OJ挂,链自找由题目的特性可知,我们可以把血量求前缀和,然后视为同时攻击则每次的yiy_iyi​可以表示为sum[i]−sum[j−1]x[i]−(i−j)∗d(1≤j≤i−1)\frac{sum[i]-sum[j-1]}{x[i]-(i-j)*d}(1\le j\le i-1)x[i]−(i−j)∗dsum[i]−sum[j−1]​(1≤j≤i−1)直接求就是n2n^2n2考虑优化,发现...

2019-09-29 22:07:00

[BZOJ1074][计算几何][搜索]SCOI2017:折纸

OJ挂,链自找一直在想正做的做法,然后当场去世反着做就好做多了,对于每个询问点,我们找出其被翻回去后处于哪个位置,然后从这两个点递归下去继续找,需要及时判断合法性,即一个点是否处于当前直线的右侧,如果在显然不行,因为右边的会被往左边翻,所以这个位置实际上最后是空的点的对称就利用直线垂直:k1∗k2=−1k1*k2=-1k1∗k2=−1搞即可Code:#include<bits/st...

2019-09-29 22:00:28

[BZOJ3199][半平面交][最短路]SDOI2013:逃考

BZOJ挂,链自找很容易发现两个点连线的中垂线就是划分两个点控制区域的直线那对于每个点处理处它与其他所有点的连线的中垂线,加上边界四条线做半平面交即可知道这个点的控制区域然后这个点与所有剩下的直线所代表的点连边,跑最短路即可Code:#include<bits/stdc++.h>#define eps 1e-9#define db double#define mp ma...

2019-09-29 21:55:53

[LOJ2008][半平面交]SCOI2015:小凸想跑步

LOJ2008把每个三角形的面积用叉积表示,每个三角形和0,1,p0,1,p0,1,p组成的三角形组合可以列出n−1n-1n−1个不等式,然后把不等式转成直线做半平面交即可Code:#include<bits/stdc++.h>#define db long doubleusing namespace std;inline int read(){ int res=0,f=...

2019-09-29 21:52:30

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。