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...
题目链接：C. Pekora and Trampoline
思路：差分，经过仔细思考可以发现，最优解一定是都在1这个位置进行跳跃，因为假设1这个位置上的a[1]=1，那么他会跳到2，也就是具有传递性，直到跳到一个value不为1的地方，这和一开始就在该位置跳是一样的。证明了这个之后，我们进一步思考可以发现，i这个位置，可以对后面[i+2,min(a[i]+i,n)]产生影响，产生的影响是后面这些用跳的次数-1，然后再根据a[i]=1的传递性，如果位置j的value已经降...
