因为a比较大，使用高精度去计算必然会TLE。 于是我们可以利用hash的思想，相当于对等式，两边同时取模。 这里我使用了孪生素数来双hash，增加可靠性。 计算多项式直接秦九韶就行（初中知识应该都会）  AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> #define int long long using namespace std; const int p1=1e9+7,p2=1e9+3; int n,m,a[110],b[110]; char str[10010]; vector<int> res; inl...

给定一棵无根树，假设它有n个节点，节点编号从1到n, 求1-n这n个节点，到其他n-1个节点的距离之和。 输入 第一行包含一个正整数n (n <= 100000)，表示节点个数。 后面(n - 1)行，每行两个整数表示树的边。 输出 每行一个整数，第i(i = 1,2,…n)行表示所有节点到第i个点的距离之和。 输入样例 4 1 2 3 2 4 2 输出样例 5 3 5 5  裸的换根。 我们先一次dfs处理出每个节点到子树的距离之和。然后再一次dfs做下换根，方程也很简单，不难推出。  AC代码： #pragma GCC optimize(2) #include<bits/std...

LYK有一个长度为n的序列a。 他最近在研究平均数。 他甚至想知道所有区间的平均数，但是区间数目实在太多了。 为了方便起见，你只要告诉他所有区间(n*(n+1)/2个区间)中第k大的平均数就行了。 输入 第一行两个数n,k(1<=n<=100000,1<=k<=n*(n+1)/2)。 接下来一行n个数表示LYK的区间(1<=ai<=100000)。 输出 一行表示第k大的平均数，误差不超过1e-4就算正确。 输入样例 5 3 1 2 3 4 5 输出样例 4.000  这道题目仔细想一下，不难想到可以二分去做。于是我们考虑二分第k大的平均数。 然后让所有数字...

题目描述 众所周知，9406计算机大佬众多，他们不仅代码能力强，而且都精通物理。物理无处不在，甚至坐电梯的时候，zck和xxr都在讨论若电梯突然失重会怎样。身为文科生的华华和奕奕非常难过，他们决定学习物理，不能让小伙伴们看不起。奕奕现在正在研究一道物理题。 有Q次操作： 若op<mark>1,输入v,t,m,表示在t时刻从无穷高处以初速度v垂直向下抛出一个质量为m的小球。 若op</mark>2,输入v,t。表示询问t时刻所有速度小于等于v的小球的动能之和是多少。 一个速度为v，质量为m的物体的动能等于0.5mvv，为了防止精度误差，设原来的答案是ans,则你只需输出2...

题目链接：抓捕盗窃犯 仔细想一下图的构成就可以看出，一个点一个出度，所以对于每一个联通块比构成环，在环上随便一个点设置哨卡就能抓到联通块所有人。 所以我们找到m个最大的联通块即可。 更复杂的图可以用Tarjan，但是我们这道题直接并查集即可。  AC代码： #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+10; int f[N],n,m,a[N],b[N],res; int find(int x){return x==f[x]?x:f[x]=find(f[x]);}...

题目链接：小D的剑阵  对于每一把剑，我们都有选不选的问题，也就是非黑即白的问题。 于是我们可以想到最小割建图。 先加上所有可以增加的价值，然后减去最小割即可。 然后列出方程，解出小学生都能解的方程就可以了。   AC代码： #include<bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; const int N=1e3+10,M=1e6+10; int s,t,n,q,h[N],res,val[N]; int head[N],nex[M],to[M],w[M],tot=1; inline void ade...

题目链接：流星雨  比较简单的概率dp，我们令dp[i]为第i天，下流星雨的概率，然后就不难递推了。 最后乘以下流星雨的个数即可。  AC代码： #include<bits/stdc++.h> #define int long long using namespace std; const int p=1e9+7; const int N=1e5+10; int n,a,b,x,y,w[N],inv,dp[N],res; int qmi(int a,int b=p-2){ int res=1; while(b){if(b&1) res=res*a%p; b>>=...

题目链接：选点  看似像树形dp，而且还很麻烦。 但是我们可以注意一下，这是二叉树，大小关系为： 左儿子 > 右儿子 > 根 所以如果我们先遍历根，然后往右儿子走，然后往左儿子走，的dfs序。 然后就是求LIS就行了。 比较思维。  AC代码： #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,w[N],ls[N],rs[N],d[N],a[N],cnt; void dfs(int x){ if(!x) return ; a[++cnt]=w[x]; dfs(rs[x]); df...

题目链接：筱玛的迷阵探险 数据量比较小，于是可以想到爆搜，但是复杂度为 2^40，必然不行，于是对于二进制求max，我们可以想到用Trie去维护。 怎么做呢？我们双向dfs，对每一个走到 n/2 步数的节点分别开一个Trie，然后下一次从终点走到这个节点时，然后从这个节点当中的Trie里面去找max。 总复杂度为： 2^20 * 30 完全ok。  AC代码： #include<bits/stdc++.h> using namespace std; const int N=6e6+10; int n,e,g[25][25],t[25][N][2],idx,res; inline v...

题目链接：水图  我们不难想到，我们走到最后一个点之后不用走回来。 所以如果我们需要走回来，那么答案就是所有边的二倍权值和，但是现在我们不需要走回来。 所以我们就是要不走回来的权值和最大，也就是以x为起点的直径。 直接dfs或者bfs即可。  AC代码： #include<bits/stdc++.h> #define int long long using namespace std; const int N=5e4+10; int n,x,res,mx; vector<int> v1[N],v2[N]; inline void add(int a,int b,int ...

Rimi learned a new thing about integers, which is - any positive integer greater than 1 can be divided by its divisors. So, he is now playing with this property. He selects a number N. And he calls this D. In each turn he randomly chooses a divisor of D (1 to D). Then he divides D by the number to o...

给出一个有向无环的连通图，起点为1，终点为N，每条边都有一个长度。 数据保证从起点出发能够到达图中所有的点，图中所有的点也都能够到达终点。 绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。 现在绿豆蛙想知道，从起点走到终点所经过的路径总长度的期望是多少？ 输入格式 第一行: 两个整数 N， M，代表图中有N个点、M条边。 第二行到第 1+M 行: 每行3个整数 a, b, c，代表从a到b有一条长度为c的有向边。 输出格式 输出从起点到终点路径总长度的期望值，结果四舍五入保留两位小数。 数据范围 1...

题目链接：储物点的距离 看似是一道划分树的题目，但是因为没有修改操作，我们直接前缀和即可。 我们用前缀和维护区间的物品总数，以及维护区间物品全部移动到第一个点的花费。 然后就根据 l,r,x之间的关系，推一推式子就行了。  AC代码: #include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10,p=1e9+7; int n,m,a[N],w[N],s[N]; signed main(){ ios::sync_with_stdio(false); cin.tie(nullp...

排列组合 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5948 Accepted Submission(s): 2614 Problem Description 有n种物品，并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有"AB","BA"两种。 Input 每组输入数据有两行，第一行是二个数n,m(1<=m,n<=1...