Ivan has an array consisting of n different integers. He decided to reorder all elements in increasing order. Ivan loves merge sort so he decided to represent his array with one or several increasing sequences which he then plans to merge into one sorted array.Ivan represent his array with increasing sequences with help of the following algorithm.While there is at least one unused number in array ...
Journey题意：给一颗树，边权都为1，从1出发，求走到叶子节点的边权和的期望（每次往孩子遍历的等概率的）思路：从1出发dfs，每个点到下一个点的概率是当前节点的概率乘孩子节点的个数，也就是当前点的边数-1，到叶子节点后计算概率乘边权和然后相加就是了，1节点需要特殊处理一下AC代码：#include "iostream" #include "iomanip" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #in...
题目链接：Codeforces Round #418 (Div. 2) C. An impassioned circulation of affection题意：给你一个字符串，有q个询问，每个询问一个x和一个字符 o。现在让你在原来的字符串上最多改变x个字符，问能构成最长的o子串的长度。题解：一共有26*1500种状态，对于每个状态用双指针滚一滚就行了。 1 #include<bits/stdc++.h>2#define F(i,a,b) for(int i=(a);i<=(b);++i)3usingnamespace std;4 5constint N=1507;6int ans[27][N],n,k,...
A题水题，但是我做麻烦了，因为我不知道字符串内部也可以排序，学到一招#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> usingnamespace std; constint N=1e5+10; constint inf=0x3f3f3f3f; int a[27],b[27]; int main(){int t;cin>>t;while(t--){string p;string s;cin>>p>>s;int i;int l1=s.size();int l2=p.size(); int flag=0;if(l1<l2){cout<<"NO"<<endl;continue;}for(i=0;i<l1...
题目大意： 给你一个序列，一些查询 每次查询区间[L,R]中出现次数大于T的最小的a[i]是多少 题目思路： 一眼主席树 但是这个题目在于如何用好这个条件 2?≤?k?≤?5 假设这个序列长度是1000，k=5 那么就是找出现次数大于200的，但是这样的数字最多有多少个呢？ 很明显 不会超过k个 然后我查询一个区间的数字个数的和的时候，如果小于T，直接退出 然后继续搜下去（这里不会有k<=5的限制，会退出的很快） 这里因为要求最小值 所以每次...
Mister B and Book ReadingCodeForces - 820A 题意：C,V0,V1,A,L。.总共有C页书，第一天以V0速度读，每天加A,但是不能超过V1,并且要从前一天的看到的当前页数的前L页开始读#include<iostream> #include<cstdio> #include<cstring> usingnamespace std; int c,v0,v1,a,l,ans; int main(){scanf("%d%d%d%d%d",&c,&v0,&v1,&a,&l);while(c>0){ans++;if(ans!=1)c+=l;c-=v0;v0=min(v0+a,v1);}printf("%d",ans);return0; }AC 模拟Mister B...
第一次遇到有9题的div2。。。 A题 排序后，伸展两边 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=2e5+10; const int mod=1e9+7; ll a[4]; int main(){ios::sync_with_stdio(false);ll d;cin>>a[1]>>a[2]>>a[3]>>d;sort(a+1,a+4);ll ans=0;ans+=max(0ll,d-a[2]+a[1]);ans+=max(0ll,d-a[3]+a[2]);cout<<ans<<endl;return 0; }View Code B题 写了个臭暴力，因为输入...
题意：给你平面上一些点，求一个凸包的最短直径思路：旋转卡壳，然后搞一下就行了可旋转卡壳求最远点差不多，cur带表的是求出的对锺点，然后与当前的直线p[i]，p[i+1]，求一下距离代码：#include <bits/stdc++.h> usingnamespace std; constdouble eps = 1e-16; int sgn(double x) {if(fabs(x) < eps)return0;if(x < 0)return -1;elsereturn1; } struct point {double x,y;point(int _x = 0,int _y = 0){x = _x;y = _y;}point oper...
题目链接：http://codeforces.com/problemset/problem/461/A题目意思：给出一群由 n 个数组成的集合你，依次循环执行两种操作： （1）每次Toastman得到一个集合，他计算所有数的和，并且将它加入到score里。之后他将这个集合传给Appleman。 （2）Appleman得到的集合如果只有一个数，就把它弃之，否则将这个集合分成 两个不相交且不空的集合，传回给Toastman. 这些操作不断执行直到集合个数变为0，也就是通过使集合都变成只...
Codeforces Round #706 C-Diamond MinerD-Lets Go Hiking C-Diamond Miner题意： 分别给定你一堆在y轴的上的点，和x轴上的点，一个y轴有且只有一个x轴的点和它连接，问最后这些点都互相链接之后，所有点对的距离和最小为多少？ 思路： 我们把所有的点按照距离原点的距离排一下序，画一下图就可以发现，一定是从y轴距离原点最近的点去连此时还未连接的x轴上距离原点最近的点。 把这个四个点放到一个平行四边形中，很明显的两条对角...
暂时只能写签到题，别的题解之后补A.Angle BeatsB.Best Subsequence有点有趣的二分显然二分之后就是找到一个长度恰好为k的合法环了先证明一个引理，如果可以找到一个长度大于k的环一定可以找到一个长度等于k的环固定头尾不动之后就可以使用归纳法证明一个长度大于3的环都可以删掉一个点为啥呢？，因为考虑任意三个连续的点，除非中间的点是最小值，否则都可以删掉这个点很容易证明长度大于3的序列至少存在一组三个连续的点满足中间...
\(\mathcal{Solution}\) 设 \(f_i\) 为到达 \(i\) 的答案，不能到达则为 \(inf\)。 设 \(g_i\) 为考虑完前面的操作时，单独使用当前操作来到达 \(i\) 的最小步数，不能到达则为 \(inf\)。 每次读进一个操作就把 \(g\) dp 一次，然后更新 \(f\)。 具体的：初始化 \(g_i=\left\{\begin{matrix}0,f_i\neq inf\\inf,f_i=inf \end{matrix}\right.\)若 \(g_i\neq y\)，则 \(g_{\left \lceil i+x \right \rceil }=\min(g_{\left \lceil i+...
题目大意：这是一道交互题。给你一个长度为n的字符串，这个字符串是经过规则变换的，题目不告诉你变换规则，但是允许你提问3次：每次提问你给出一个长度为n的字符串，程序会返回按变换规则变换后的字符串，提问3次后你需要猜出这个字符串。解法是学习https://blog.csdn.net/baiyifeifei/article/details/87807822 这个博主的，借用了进制的思想非常巧妙。 解法：对于某个位置的来源位置我们设为x，因为26*26*26>10000，那么x可以唯...
题意n个数里插入k个+号，所有式子的和是多少（取模1000000007） (0?≤?k?<?n?≤?105)。分析1.求答案，考虑每个数作为i位数（可为答案贡献10的i-1次方，个位i=1，十位i=2，...，最多n-k位）：那么它及后面 共i个数 之间不能有加号。且只有前n-i+1个数可以作为i位，如果是an-i+1作为i位，那么后面都不能有加号，k个加号在a1到an-i+1之间，所以有C(n-i,k)次贡献（这么说怪怪的→_←），就是几种情况。a1 a2 a3 ... an-i+1 ... an如果是...
枚举，三分。首先，这$n+1$个人一定是连续的放在一起的。可以枚举每一个起点$L$，然后就是在$[L,R]$中找到一个位置$p$，使得$p4最优，因为越往两边靠，距离就越大，在中间某位置取到最优解，所以三分一下就可以了。#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stac...