链接：here~~~分割最多的数，使得分割的数连接在一起，得到原来的数，（分割的数大的放前面，两个数合并 比较此数大于后面的数，否则合并成一个数，不能分割，0不能单独存在）#include<iostream> usingnamespace std;int main() {string s;int i , j , ans = 0;cin >> s;for( i = 0; s[i] ;i = j){for(j = i + 1 ; s[j] == ‘0‘;j ++);if(j - i > i || j - i == i && s[0] < s[i]) ans = 1;else ans ++;}cout << ans << endl; }Vi...
莫队算法链接：传送门 题意：有n个数，m个区间。问区间内有多少个x，x满足x的个数等于x的值的个数（如果x是3，区间内要存在3个3）。 题解：因为a[i]太大，所以要离散化一下，但是不能用map容器，因为map容器多一个log莫队就是离线问题+区间的移动。复杂度是O（(N+M)*√N） 莫队代码还要分块要不然还会TLE，分块大小为sqrt(n) 未分块-TLE代码： 1 #include <cstdio>2 #include <iostream>3 #include <cstring>4 #include <cmath>5 #...
A. Road to Cinema很明显满足二分性质的题目。题意：某人在起点处，到终点的距离为s。 汽车租赁公司提供n中车型，每种车型有属性ci（租车费用），vi（油箱容量）。 车子有两种前进方式 ：①. 慢速：1km消耗1L汽油，花费2分钟。 ②.快速：1km消耗2L汽油，花费1分钟。 路上有k个加油站，加油不需要花费时间，且直接给油箱加满。 问在t分钟内到达终点的最小花费是多少？（租车子的费用） 若无法到达终点，输出-1不谈二分的写法.. 我们...
George is a cat, so he loves playing very much.Vitaly put n cards in a row in front of George. Each card has one integer written on it. All cards had distinct numbers written on them. Let’s number the cards from the left to the right with integers from 1 to n. Then the i-th card from the left contains number pi (1?≤?pi?≤?n).Vitaly wants the row to have exactly k cards left. He also wants the i-...
题目链接：https://cn.vjudge.net/problem/CodeForces-920E题意给一个补图，问各个联通块有几个元素，升序排列 注意maxn=2e5, maxm=2e10思路数据量超大，这本来是并查集专题的一道题 如果用并查集的话，向上维护一个元素个数，但首先离线建图是个问题O(n^2) 这样考虑的话，bfs O(n)就是更好的选择 提交上去TLE，当时写题没仔细算复杂度，set查边+数组判重，加起来貌似O(nlogn+n），至于为什么用set查边，因为数组查边肯定空间太大 ...
传送门终于学会多项式开根了哈哈……反正题解都烂大街了，我就不写了，直接贴代码算了……(犯懒ing) 1/**************************************************************2 Problem: 36253 User: _Angel_4 Language: C++5 Result: Accepted6 Time:29048 ms7 Memory:5944 kb8****************************************************************/ 9 #include<cstdio> 10 #include<cstring> 11 #include<algorithm> ...
include <bits/stdc++.h>using namespace std; int n; int x[200005], y[200005], xr[200005]; int main() { int t; cin >> t; while(t--) { cin >> n; for(int i = 1; i <= n; i++) cin >> x[i]; for(int i = 1; i <= n; i++) { int tmp = 0; if(i == 1) { y[1] = 0; xr[1] = 0 ^ x[1]; continue; } int fuck = 0; for(int j = 0; j < 32; j++) {//逐位分析 fuck |= (((xr[i - 1] >> j) & 1) << j); if((xr[i - 1] >> j) & 1) {//...
题意：要生产n个物品，每个花费时间为x。有两种魔法，每种最多使用1个。其中第一种魔法可以使每个物品生产的花费时间变为ai，相应的花费是bi;第二种魔法可以减少ci个物品，相应的花费是di，并且保证对于i<j ci<=cj 且 di<=dj;#include<bits/stdc++.h> usingnamespace std; longlong b[200050],c[200050],d[200050]; pair<longlong ,longlong>a[200050]; longlong inf=0x3f3f3f3f3f3f3f3f; int main() {longlong n,m,k,x,s;scanf("%...
题目链接：https://codeforces.com/contest/1265/problem/C题意从大到小给出 $n$ 只队伍的过题数，要颁发 $g$ 枚金牌，$s$ 枚银牌，$b$ 枚铜牌，要求：$g < s, g < b$$g + s + d \le \lfloor \frac{n}{2} \rfloor$金牌队伍的过题数大于银牌，银牌队伍的过题数大于铜牌输出颁发奖牌数最多的一种方案。题解根据第三个要求，奖牌一定是按过题数的大小颁发的。金牌只颁发给过题最多数的队伍，可以使 $g < s, g < b$ 最容易满足。接下来...
pii pair<int, int> #define mod 1000000007 #define mp make_pair #define pi acos(-1) #define eps 0.00000001 #define mst(a,i) memset(a,i,sizeof(a)) #define all(n) n.begin(),n.end() #define lson(x) ((x<<1)) #define rson(x) ((x<<1)|1) #define inf 0x3f3f3f3f typedef long long ll; typedef unsigned long long ull; using namespace std; const int maxn = 3e5+5; priority_queue<pii,vector<pii>,greater<pii>>a; i...
定理（Lindstrm–Gessel–Viennot lemma）很简单：学的时候忘了大的行列式怎么算的了。。 然后就可以写题了： 第一道：CodeForces-348D（链接https://vjudge.net/problem/CodeForces-348D） 题意给你个n*m的方阵，有一些点无法通过，然后求从(1,1)到(n,m)走两条路，并且两条路不相交的方案数。 题解：只能向右或者向下走，那么起始点肯定一个向左一个向右，结束点肯定一个从上方过来，一个从左方过来，那么题就成了两个点（1，...
LIS定义： LIS（Longest Increasing Subsequence）最长上升子序列 一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。 对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)， 这里1 <= i1 < i2 < … < iK <= N。 比如，对于序列(1,5,3,4,8)，有它的一些上升子序列，如(1, 8), (3, 4, 8)等等。 这些子序列中最长的长度是4，比如子序列(1, 3, 4, 8). 你的任务，就是对于给定...
This is the hard version of the problem. The difference is the constraint on the sum of lengths of strings and the number of test cases. You can make hacks only if you solve all versions of this task. You are given a string ss, consisting of lowercase English letters. Find the longest string, tt, which satisfies the following conditions:The length of tt does not exceed the length of ss. tt is a pa...
[Codeforces 364D]Ghd(随机算法) 题面 给出n个正整数，在其中选出n/2(向上取整)个数，要求这些数的最大公约数最大，求最大公约数的最大值 分析 每个数被选到的概率\(\geq \frac{1}{2}\)，因此我们随机选t个数x，对于每个数处理出它所能得到的最大答案。显然最大公约数一定是x的一个因数。 先对x进行因数分解。并求出x与所有a[i]的gcd ,看看哪个因数成为x和a[i]的gcd的次数最多，且次数超过n/2 。具体做法是,对于每个因数d[u],记录满...
因为没有重复串，所以把有包含关系的串连边之后是个DAG，也就是二分图，就变成求二分图的最大独立集=n-最小点覆盖=n-最大匹配 关于包含关系，建出AC自动机，然后把串放上去找子串，但是如果每次都一路找到根就会T，所以每次只找最近的一个，并且对于没有结尾id的点承接father的id，这样就O(1)的找到最近子串了 然后再用floyd传递闭包把关系建出图来 然后跑匈牙利，输出方案就是把一个匹配环里同一侧的都dfs标记一下，最后输出没有被...