- 博客(101)
- 收藏
- 关注
RSS订阅转载 loj2064[HAOI2016]找相同字符
题意：给你两个字符串，问其中各取一个子串，有多少对相同？n<=20W。标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=1000005; 5 ll ans; 6 int p,np,cnt,fa[N]...
2018-06-26 10:21:00
148
转载 USACO18DEC Platinum
standing out from the field给你n个串，对于每个串求出只包含在这个串中的本质不同的子串？后缀自动机，建树，对于每一个点打上包含在哪个串中的标记。叶子都是前缀，直接在sam_build时预处理；其余的dfs一遍，由于x是son[x]的后缀，故x的状态由son[x]影响，如果son[x]有出现在不同串中的，标记x为-1。 1 #includ...
2018-06-23 10:46:00
127
转载 CF566E Restoring Map
题意：乱序给你树上的每一个节点与之相距<=2的节点集合（并不知道这具体是哪个节点）。还原整棵树。标程： 1 #include<bits/stdc++.h> 2 #define P pair<int,int> 3 #define fir first 4 #define sec second 5 using namesp...
2018-06-20 23:36:00
261
转载 bzoj4237稻草人
题意：给你一个田地，问左下角和右上角有稻草人并且内部除了边界都没有稻草人的矩形数。标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 int read() 4 { 5 int x=0,f=1;char ch=getchar(); 6 while (ch<'0'...
2018-06-19 23:33:00
119
转载 loj2472[九省联考2018]IIIDX
题意：要求构造一个d的排列使得满足d[i/k]<=d[u]且字典序最大。标程（bzoj上并不能过）： 1 #include<bits/stdc++.h> 2 #define mid ((l+r)>>1) 3 using namespace std; 4 const int N=500005; 5 const int ep...
2018-06-19 10:08:00
102
转载 loj2471[九省联考2018]一双木棋
题意：在一个n*m的棋盘上，A和B轮流放置棋子。一个位置能够放置棋子当且仅当它上面没有棋子并且它的上面和左边一格都已经放了棋子（不难发现是一个上三角阶梯状）。每个格子有两个权值，当A在上面放置棋子时A获得a[i][j]的得分，B同理。A和B用最优策略，A想要A-B最大，B想要B-A最大（即使A-B最小）。问最后A-B为多少？标程： 1 #include<bits...
2018-06-13 20:45:00
105
转载 bzoj2395 [Balkan 2011]Timeismoney
题意：每条边有两个权值a，b，求图的最小二元和乘积生成树（即该树的sum_a*sum_b最小）。标程： 1 #include<bits/stdc++.h> 2 #define P pair<ll,ll> 3 #define fir first 4 #define sec second 5 using namespace std;...
2018-06-13 18:25:00
114
转载 loj2573[TJOI2018]数字计算
题意：操作1：x=x*m，输出x%mod。2.x/=map[m]。m即第m次操作，保证该次操作为1操作，并且每个操作最多只会被删一次。q<=1e5。线段树维护操作信息的乘积，删除把对应位置的权改成1。标程： 1 #include<bits/stdc++.h> 2 #define mid ((l+r)>>1) 3 using nam...
2018-06-13 14:15:00
102
转载 Atcoder arc093
D-Grid Components在一个100*100的网格图上染色，问黑格四连通块的个数为A，白格四连通块的个数为B的一种构造方案？（A,B<=500）将整个平面分成50*100的两部分，分别以黑白为背景，一块背景算一个连通块，然后在一种背景上用另一种颜色上去点彩，连通块大小为1，无八连通。 1 #include<bits/stdc++.h> ...
2018-06-12 20:57:00
121
转载 CF533A Berland Miners
题意：给你一棵树，每个点有一定高度hi。需要选择k个点放进k个人，每个人的高度为si。第i个人能够放进x点当且仅当从根到x的路径上的高度最小值>=si。现在你最多只能选择一个节点增加一定的高度使其满足要求，问最小代价？n<=5e5。标程： 1 #include<bits/stdc++.h> 2 #define mid ((l+r)&g...
2018-06-12 19:07:00
67
转载 loj2001[SDOI2017]树点染色
题意：给你一棵树，一开始每个点上的颜色互不相同。三种操作：op1：x到根的路径上的点都染上一种新的颜色。op2：设一条路径的权值为val(x,y)，求x到y路径的val。op3：询问x的子树中最大的到根路径val。n<=1e5。标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 typed...
2018-06-12 13:45:00
128
转载 loj2000[SDOI2017]数字表格
题意：f为Fibnacci数列。求$\prod_{1<=i<=n,1<=j<=m} f[gcd(i,j)]$.n,m<=1e6.标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mo...
2018-06-12 09:35:00
110
转载 Atcoder arc092
E-Both Sides Merger给你一个序列，支持两种操作，直到序列中只有一个数时停下来，使得剩下数最大，并输出选数方案。操作1：扔掉一个最前端或最后端的元素。操作2：选取一个不在边界上的元素，取其相邻两个数的和替换它，并删去它相邻的两个数。n<=1000,|ai|<=1e9。结论1：最后留下的数是原序列若干个数的和，并且这些数的下标同奇偶。证明：一...
2018-06-11 21:09:00
186
转载 bzoj4826[hnoi2017]影魔
题意：每次询问一个区间[l,r]，问[l,r]中的每一对(i,j)能够贡献多少总加成？给定序列a是1~n的一个排列，也就是a[i]两两不同。设z=max{a[i+1],a[i+2],...,a[j-1]}，若z<min(a[i],a[j])，加成p1；若min(a[i],a[j])<z<max(a[i],a[j])，加成p2。n<=20W。标程：...
2018-06-10 11:51:00
100
转载 bzoj4827 [hnoi2017]礼物
题意：给你两串珠子，求将其中一串珠子进行加一个整数c和旋转操作后，最小的$\sum_{i=1}^{n}(x[i]-y[i+k]+c)^2$。标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mod=998244353...
2018-06-10 08:56:00
84
转载 CF755G PolandBall and Many Other Balls/soj 57送饮料
题意：长度为n的序列，相邻两个或单独一个可以划分到一个组，每个元素最多处于一个组。问恰好分割成k(1<=k<=m)段有多少种方案？标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mod=998244...
2018-06-09 11:15:00
178
转载 PKUSC订正
Day1 T2：最大前缀和枚举答案集合（不直接枚举答案数，相当于状态的离散化），这个集合成为答案当且仅当存在方案使得答案集合的排列后缀和>=0（如果<0就可以去掉显然更优），答案补集的前缀和<0（不能再延伸）。预处理方案数。最后统计的时候注意要枚举答案子集的第一个元素，它不需要满足后缀和>=0。O(2^n*n)。 1 #include<bit...
2018-06-08 16:36:00
71
转载 bzoj3237 连通图
题意：在一个无向图上每次删去少量边，问是否还连通？标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 int read() 4 { 5 int x=0;char ch=getchar(); 6 while (ch<'0'||ch>'9') ch=getch...
2018-06-07 18:39:00
100
转载 uoj207 共价大爷游长沙
题意：动态树上支持加入路径、删除路径、询问一条边是否被当时存在的所有路径经过？标程： 1 #include<bits/stdc++.h> 2 #define P pair<int,int> 3 using namespace std; 4 int read() 5 { 6 int x=0;char ch=getchar(...
2018-06-06 13:22:00
77
转载 USACO18FEB Platinum
SlingShot 求数轴上从x到y的最短路（ 边长为1），有若干个从xi到yi长度为ti的传送门，每次只能选择其中一个使用。即求min(|x-y|,min{|a-x|+|b-y|+c})，拆开绝对值，根据相对位置分开讨论，转换成二维数点问题。MLE的主席树版本： 1 #include<bits/stdc++.h> 2 #define P pair<...
2018-06-01 22:59:00
104
转载 PKUSC加油加油加油！
一句话，把学过的掌握的甚至还未掌握的，都用上吧！1.题目不要再再再看错了！在纸上记下关键字。2.记得有预处理这个东西可以降低复杂度！3.仔细阅读数据范围，取值范围的0要注意！4.不要每次像开新题一样去开啊，肯定有一些题目可以联想到其他题。5.推性质一定要推完整。6.平时题目一定要多做，这是一个积累。量变与质变。7.在PKU卡时是一个不理智的行为。8.每道题...
2018-06-01 22:10:00
107
转载 arc098F Donation
题意：给你一张无向图，一开始携带有W元钱。走到x点，必须满足W>=Ax。可以选择在当前所在点捐献Bi的贡献（如果W<Bi，就不能做），并将此点标记。问标记完所有点，需要至少携带多少钱（最小W）？n<=1e5。标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef l...
2018-05-31 19:11:00
333
转载 arc098E Range Minimum Queries
题意：给你一个n个数的数组，每次能够选取连续的长度为K的子序列，取出其中任意一个最小元素。一共操作Q次。问取出的元素中Max-Min最小是多少？标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=2005; 4 const int inf=0x3f3f3f3f;...
2018-05-31 15:51:00
175
转载 hdu6089 Rikka with Terrorist
题意：n*m的平面内有K个不安全点，Q个询问位置在(x,y)的人能走到多少个点？走到：(x,y)和(x',y')之间的矩形中不包含不安全点。标程： 1 #include<bits/stdc++.h> 2 #define mid ((l+r)>>1) 3 using namespace std; 4 int read() 5 {...
2018-05-31 10:42:00
139
转载 bzoj1568 Blue Mary
题意：P:加入一条一次函数。Q：询问x位置的最大函数值。标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=200005; 4 int q,x,n; 5 double Tk[N],Tb[N],b,k,ans; 6 char s[10]; 7 void ad...
2018-05-30 23:18:00
64
转载 arc098D Xor Sum 2
题意：给你一个数列，问有多少对(l,r)满足A[l]+A[l+1]+...+A[r]=A[l]^A[l+1]^...^A[r]？标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=200005; 5 int n,l...
2018-05-30 19:49:00
125
转载 CF843D Dynamic Shortest Path
题意：给你一张有向图。Q：询问1到x点的最短路。C：钦定l条边x1,x2,...,xl的权值+1。n<=2e5。标程： 1 #include<bits/stdc++.h> 2 #define P pair<ll,int> 3 using namespace std; 4 int read() 5 { 6 int x=...
2018-05-30 19:49:00
257
转载 CF840E In a Trap
题意：给你一棵节点带权树。q个询问，每次询问u到v的路径上max(a[i]^dis(i,v))?保证u是v的祖先，i是u->v路径上的点。n,ai<=5e4。标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 int read() 4 { 5 int x=0,f=...
2018-05-30 13:30:00
102
转载 CF431E Chemistry Experiment
题意：有n个试管，有高度为hi的水银。操作1：将试管x中的水银高度改成y。操作2：将体积为v的水注入试管，求水位的高度？n,q<=1e5。标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=1e5+5; 5 ...
2018-05-29 21:08:00
225
转载 CF421D Bug in Code
题意：n个人每人选择了另外不相同的两个人。问有多少对(x,y)使得这n个人中至少有p个选择了至少其中之一？标程：那就不写了吧。题解：容斥统计Ax表示有多少个人选择了x。一般来说有Ax+Ay>=p，那么(x,y)姑且认为被选择了p次以上。有一些(x,y)是会被同时选的，这些会被同时选的满足Ax+Ay-Ax,y>=p。这些最多只有n个。排个序，...
2018-05-29 21:01:00
86
转载 CCPC-WFinal-女生专场
1001：CCPC直播 字符串处理，几个if语句1002：口算训练 前缀和处理<=根号n的因数，大于根号n的因数每个数至多有一个，用vector存下每个大因数的位置，map离散化。查询的时候lower_bound看是否存在即可。1003：缺失的数据范围 式子单调增，二分答案。防溢出，需要double。1004：寻宝游戏 神奇dp dp[i][j][x]...
2018-05-28 21:16:00
151
转载 CF915F Imbalance Value of a Tree
题意：给你一棵树，求所有点对(i,j)之间链上的最大点权-最小点权的总和？标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=1000005; 5 struct node{int u,v,w;}e[N]; 6 ...
2018-05-28 18:46:00
74
转载 soj考试2
T1：子图给你一棵带点权的树，对于所有i∈[1,m]，问树上是否存在连通子图的权值和=i？n<=3000,m<=100000。朴素的背包树形dp有nm的复杂度，bitset也无处优化。但是从根往叶子考虑，必经根的连通块权值和很好用bitset维护。每个点的bitset表示经过rt和该点子树及之前已访问点的连通块权值和可能值。类似树形dp的合并。树分治。时间...
2018-05-28 10:27:00
110
转载 bzoj3192 [JLOI2013]删除物品
题意：给你两个栈，给你一开始的分配。每次移动一个栈顶的元素放到另一个栈顶花费1。并且你可以删除一个栈顶元素，花费0。问你从大到小删除所有数的花费。n1+n2<=1e5。标程： 1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 typed...
2018-05-26 23:03:00
61
转载 CF802C Heidi and Library(hard)
题意：一共有n天每天一个请求，要求借一本书，即刻归还。图书馆中最多存k本书，多了就要扔掉。第i本书的价格为c[i]。问满足所有请求的最小买书花费？n<=200。标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=205; 4 const int inf=0...
2018-05-25 21:02:00
105
转载 CF850E Random Elections
题意：一共有n个人，要在三个人中选prefer，一开始他们心中都会想好他们的排名（共6种），之后给出的判断不会矛盾。规则如下：一共有三轮，分别是a->b,b->c,c->a，每个人选1，表示prefer前者，选0表示prefer后者。这样形成一个n位的二进制x。定义函数f(x)={0，1}：1表示这一轮中前者赢，0表示后者赢。有性质：f(x^((1<<n...
2018-05-25 19:23:00
90
转载 CF538G Berserk Robot
题意：一个机器人在一个无穷大的网格图中，每秒能够上下左右走一步。它的行走方向序列是长度为l的循环。给你n个线索，包括ti：时间，xi，yi走到的坐标。让你构造出行走的方向序列？标程： 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const ...
2018-05-25 16:10:00
338
转载 CF773E Blog Post Rating
题意：有一篇博客。一共有n个人，心中有他们期望该博客得到的赞数a[i]。当某个时刻该博客的获赞数<a[i]，则该人会使得赞数+1，当赞数>a[i]，该人会使得赞数-1，当赞数=a[i]，不做任何改变。对于1<=k<=n，询问1~k个人按一定的顺序给该博客从0开始点赞或点踩，该博客的最大获赞数。-1e5<=a[i]<=1e5,n<=1e5。...
2018-05-25 11:03:00
364
转载 CF886F Symmetric Projections
题意：给你平面上n个点，问有多少条过原点的直线，使得这些点在该直线上的投影（做垂直，对应点）形成对称图形？n<=2000。标程: 1 #include<bits/stdc++.h> 2 #define P pair<int,int> 3 using namespace std; 4 const int inf=0x3f3f3f3...
2018-05-24 23:42:00
151
转载 CF475F meta-universe
题意：给你一个无限大矩形中有一些planet，每次可以选择某一没有planet的行或列分割开矩形（分割开以后要求矩形不为空）。问最后能分割成几个矩形？标程： 1 #include<bits/stdc++.h> 2 #define P pair<int,int> 3 #define fir first 4 #define sec sec...
2018-05-24 14:39:00
201
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人