2019南京网络赛 D.Robots 树上期望dp

题目链接：https://nanti.jisuanke.com/t/41301 题意：N个点M条边的有向无环图，1为唯一入度为0的点，N为唯一出度为0的点，现在你从1号点出发，每单位时间，你有相同的概率，走向下一节点或…...

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id1568 李超线段树： 问题： 现在要求你在线动态维护一个二维平面直角坐标系，支持插入一条线段，询问与直线xx0相交的所有线段中交点y的最大/最小值 更新&a…...

链接：https://ac.nowcoder.com/acm/contest/1083/C 来源：牛客网 勾股定理 时间限制：C/C 1秒，其他语言2秒 空间限制：C/C 32768K，其他语言65536K Special Judge, 64bit IO Format: %lld 题目描述 给出直…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41389 题解&#xff1a;马拉车处理回文串&#xff0c;每个位置记录后面每个字符出现的第一个位置&#xff0c;然后把每种字符额贡献加起来即可 #include<bits/stdc.h> using namespace std; typedef long long ll; c…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41391 题解&#xff1a;先找出每一对(pi​,pj​)&#xff0c;那么i&#xff0c; j 记录为 区间[l, r]&#xff0c;则查询就变为&#xff0c;在[L,R]内有多少区间&#xff0c;然后我们离线线段树就可以搞定了&#xff0c;按照…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41392 题解&#xff1a;dp[u] 表示 u这个点向下能到达最深深度的概率&#xff0c;因为对于每个点要找k次&#xff0c;只要其中有一次能到达最深即可&#xff0c;所以我们用容斥的思想&#xff0c;即表示为 1 - 不能到达最深…...

题目链接&#xff1a;https://vjudge.net/problem/FZU-2105 其实我想放银川网络赛的链接&#xff0c;emmm 题解&#xff1a;首先或和与是能相互掩盖的&#xff0c;因此我们就可以把这两者用一个laz标记&#xff0c;laz1表示区间都变为1&#xff0c;laz-1表示区间都为0&#x…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41388 题解&#xff1a;这个题比赛最后也没改对&#xff0c;训练时突然想到有个地方写了emmmm 思路&#xff1a;我们先按照dfs序把每个点跑出来&#xff0c;然后vector记录下每个深度的点&#xff0c;很容易就可以想到&…...

题目链接&#xff1a;https://vjudge.net/problem/HDU-5489 题解&#xff1a;删除m个后的最优的LIS在原序列中肯定存在一段间距大于等于m&#xff0c;那么我们就以这一段作为划分线&#xff0c;以后面第一个数x开始作为后半部分&#xff0c;那么后半部分的LIS我们可以倒着nlo…...

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-750E 题解&#xff1a;哇&#xff0c;原来这个也四个原题。。。。。。维护矩阵的还真是第一次做&#xff0c;这里就说一下CF那题的思路吧 因为最后要2017&#xff0c;那么我们分为5个子序列 空 2 20 201 2017 每…...

构造n * m的螺旋矩阵 讲解&#xff1a;https://wenku.baidu.com/view/7253dc78a26925c52cc5bff4.htm #include <bits/stdc.h> using namespace std; int getnum(int n, int m, int x, int y) {int lev min(min(x, n - 1 - x), min(y, m - 1 - y));int d x y - lev *…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41399 题解&#xff1a;看见的第一思路应该都是差分&#xff0c;但是这个用数组肯定就gg了&#xff0c;所以当时的时候就想到动态开点线段树&#xff0c;mlog(n)但是T了&#xff0c;然后我就把点离散了一下&#xff0c;用点…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41415 题解&#xff1a;对于两边的&#xff0c;要哈希出相应的权重&#xff0c;中间的字符顺序无所谓&#xff0c;只关心是什么字符&#xff0c;所以哈希出每个字符的权重即可。 官方题解&#xff1a; • 但是因为询问有2…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41408 细心细心细心 #include <bits/stdc.h> using namespace std; const int N 1e5 10; struct node {char name[15];int id;int b[5]; }p[N]; int n; int a[10]; bool judge1() {for(int i 1; i < 5; i) {if…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/41402 题解&#xff1a;首先和1联通的糖果屋都能到达&#xff0c;其他不能到达的肯定被恶魔屋挡住了&#xff0c;那就在挡住的所以恶魔屋中选择一个最优的就可以了&#xff0c;怎么算最优呢&#xff0c;因为到达恶魔屋之后&…...

题目链接&#xff1a;https://www.51nod.com/Challenge/Problem.html#problemId1571 现在有一个序列 a1, a2, ..., ana1, a2, ..., an &#xff0c;还有m个查询 lj, rj (1 ≤ lj ≤ rj ≤ n)lj, rj (1 ≤ lj ≤ rj ≤ n) 。对于每一个查询&#xff0c;请找出距离最近的两个元素…...

链接&#xff1a;https://ac.nowcoder.com/acm/contest/163/A 来源&#xff1a;牛客网 题目描述 Fruit Ninja is a juicy action game enjoyed by millions of players around the world, with squishy, splat and satisfying fruit carnage! Become the ultimate bringer of…...

题目链接&#xff1a;https://vjudge.net/problem/HDU-6242 题意&#xff1a;n个点&#xff0c;找到一个圆&#xff0c;满足圆上点的数目大于等于⌈N / 2⌉ 题解&#xff1a;三个不在一条直线上的点确定一个圆&#xff0c;随机到圆上点的概率是1 / 2&#xff0c;那么三次就是…...

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6393 题意&#xff1a;n个点n条边的图&#xff0c;求两点间的最小距离 题解&#xff1a;如果是一个树的话&#xff0c;那么我们就可以倍增dfs序&#xff0c;然后用线段树维护下就可以了这样是nlogn的复杂度&a…...

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-1220D 题意&#xff1a;n个数&#xff0c;如果节点 i 和 j 满足 |i - j | 属于B&#xff0c;则i和j有一条边&#xff0c;问B集合最少删除多少边&#xff0c;使得得到的图是个二分图 题解&#xff1a;根据二分图的…...

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-1220E 题意&#xff1a;n个点m条边的无向连通图&#xff0c;起点s&#xff0c;每个点有权值&#xff0c;求遍历无向图得到的最大权值和。但是不能走回头路&#xff0c;即如果从U走到V那么下一步不可以从V走到U 题…...

题目链接&#xff1a;https://vjudge.net/problem/HDU-6156 题意&#xff1a;区间[L, R]的数&#xff0c;写成k进制(l<k<r)后&#xff0c;如果是回文串&#xff0c;那么f(x,k)k,否则f(x,k)1&#xff0c;对f求和 题解&#xff1a;一看这种题就是数位dp&#xff0c;当时想…...

题目链接&#xff1a;https://vjudge.net/problem/HDU-6153 题意&#xff1a;对于s2的每一个后缀&#xff0c;假设长度为l&#xff0c;在s1出现的次数为k&#xff0c;求l*k的和 题解&#xff1a;我们把两个串都倒过来&#xff0c;变为s1,s2&#xff0c;那么问题就变为&#x…...

题目链接&#xff1a;https://vjudge.net/problem/Gym-100589A 题意&#xff1a;n个点&#xff0c;根节点为1的树&#xff0c;两种操作&#xff0c;1 L y 与根节点距离为L的节点权值全部加上y&#xff0c;2 x x子树的权值总和 题解&#xff1a;对于更新操作&#xff0c;因为更…...

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6731 题意&#xff1a;n个点&#xff0c;m次查询&#xff0c;每次给你一个点&#xff0c;从n个点挑出两个能组成多少直角三角形 题解&#xff1a;假设询问的是点p&#xff0c;直角可能是p也可能是其他两点的某…...

题目链接&#xff1a;https://vjudge.net/problem/HDU-5927 题意&#xff1a;给一棵树,然后每次询问时给出哪些点是不重要的点,让求这棵树上重要的点以及是两个不同的重要的点的lca一共有多少个 题解&#xff1a;我们只需要看给出的每一个不重要的点是不是重要的点就可以了&a…...

题目链接&#xff1a;https://codeforces.com/problemset/problem/689/D 题意&#xff1a;有多少区间[l, r]满足&#xff0c;max(al..ar) min(bl..br) 题解&#xff1a;对于先固定l&#xff0c;那么对于max(a)&#xff0c;是一个递增的序列&#xff0c;对于min(b)是一个递减…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/A1538 题解&#xff1a;因为k只有3&#xff0c;所以最多取6次&#xff0c;每次有9种选取可能&#xff0c;所以直接dfs选取即可 #include <bits/stdc.h> using namespace std; typedef long long ll; int b[6][6]; in…...

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-369E 题意&#xff1a;n条线段&#xff0c;m次询问&#xff0c;给出cnt个点&#xff0c;问这些点在多少线段上 题解&#xff1a;如果每个点对于所在的线段上没有影响的话&#xff0c;那么我们就可以建立权值线段树…...

题目链接&#xff1a;https://vjudge.net/problem/Gym-101889I 题意&#xff1a;n个点&#xff0c;m条边&#xff0c;q次询问&#xff0c;每次必须选一边&#xff0c;求最小生成树的权值 题解&#xff1a;我们先跑一边最小生成树&#xff0c;然后按照最小边建树&#xff0c;必…...

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-1228C 题解&#xff1a;把x的每个质因子找出来&#xff0c;计算n&#xff01;对每个因子的贡献 #include <bits/stdc.h> using namespace std; typedef long long ll; const ll mod 1e9 7; const int N …...

题目链接&#xff1a;https://vjudge.net/problem/CodeForces-1228D 题解&#xff1a;我们把每个点哈希&#xff0c;这样就能计算出和每个点连接的其他点的总哈希值&#xff0c;若只有三种哈希值的和&#xff0c;那么就是符合的&#xff0c;当然还有其他很多种做法。 #includ…...

题目链接&#xff1a;https://nanti.jisuanke.com/t/40520 题解&#xff1a;因为他们都是联通的且只有唯一路径&#xff0c;所以不用管之前怎么连的&#xff0c;直接按照他给的查询&#xff0c;带权并查集判断即可 #include <bits/stdc.h> using namespace std; const …...

题目链接:https://vjudge.net/problem/HDU-5923 题解:因为n只有500个&#xff0c;所以我们可以每个点维护一个并查集&#xff0c;所以判断某些点的时候&#xff0c;这些并查集在合起来即可 #include <bits/stdc.h> using namespace std; const int N 510; struct edge…...

题目链接&#xff1a;https://vjudge.net/problem/Gym-102028J 题意&#xff1a;去掉两个矩形&#xff0c;让剩下的矩形覆盖的点最少 题解&#xff1a;使剩下的点少&#xff0c;那么我们就是去掉的两个矩形覆盖的尽可能多&#xff0c;也就是两个矩形各自占据的格子和只有两个…...

题目链接&#xff1a;https://vjudge.net/problem/Gym-102307J The semester has just begun at Universidad Nacional (UNAL). As usual, a group of vandals enjoys bringing chaos to all students and damaging the university facilities. Those guys have been planning…...

题目链接&#xff1a;https://vjudge.net/problem/Gym-101955L 题意&#xff1a;n个圆和 圆(0&#xff0c;0&#xff0c;R) 部分相交&#xff0c;求剩余圆的直径 题解&#xff1a;如果剩余部分存在直径的话&#xff0c;那就是2*R&#xff0c;这个怎么判断呢&#xff0c;对于每…...

题目链接&#xff1a;https://vjudge.net/problem/Gym-102307E 题意&#xff1a;平面上n个点&#xff0c;给定区域的w和d范围&#xff0c;求区域最大的点数 题解&#xff1a;其实和在平面上给定长和宽 是一样的道理&#xff0c;这个只需要对角度排序&#xff0c;然后对于每个…...

题目链接&#xff1a;https://vjudge.net/problem/Gym-102307C 题意&#xff1a;两个字符串的匹配长度能不能达到99%&#xff1b; 题解&#xff1a;因为n为1e5&#xff0c;所以不能直接dp[i][j]表示到(i,j)的最长匹配长度了&#xff0c;因为失配的最多1000&#xff0c;因此dp…...

题目链接&#xff1a;https://vjudge.net/problem/Gym-101981M 题意&#xff1a;求 s的一个子串后面加上t的前缀为回文串并且满足|s| > |t| 的个数 题解&#xff1a;因为牵扯到了前缀和子串的问题&#xff0c;大体就能想到要用到扩展kmp&#xff0c;我们把s倒置&#xff0…...

题目连接&#xff1a;https://vjudge.net/problem/CodeForces-374D 题意&#xff1a;n次操作&#xff0c;先给出m个数&#xff0c;原先有一个空序列&#xff0c;每次操作给出一个数&#xff0c;为1或0都放在后面&#xff0c;为-1时&#xff0c;删除m个位置的数 题解&#xff…...

南京已成炮灰&#xff0c;徐州加油&#xff01; A&#xff1a;java二分 import java.math.*; import java.util.*; public class Main {public static void main(String [] args){Scanner cinnew Scanner(System.in);int t,n;BigInteger z,zn,znjyn,ans,tans,x,XBigInteger.O…...

题目链接&#xff1a;http://codeforces.com/problemset/problem/1225/D 题意&#xff1a;有多少种组合方式&#xff0c;使得两个数相乘 能写成 x^k 的形式 题解&#xff1a;首先x^k&#xff0c;x的每个素因子的数目都是k的倍数&#xff0c;那么我们就对于每个数的素因子个数…...

题目链接&#xff1a;https://codeforces.com/contest/1080/problem/F 题意&#xff1a;有k个线段所属在n个集合中&#xff0c;每次询问a b x y&#xff0c;问是否[a, b]的每个集合中都存在一个线段在[x, y]的范围内 题解&#xff1a;按照每个线段的有区间排序&#xff0c;然…...

题目链接&#xff1a;https://vjudge.net/problem/Kattis-largesttriangle 题意&#xff1a;任意三点的最大三角形面积 题解&#xff1a;首先想到最大的面积应该出现在凸包上&#xff0c;然后就是枚举任意两点&#xff0c;能想到第三点是满足线性的&#xff0c;所以第三点线性…...

/* 题目内容&#xff1a;实现k平均算法的代码&#xff0c;并且通过样例 代码&#xff1a; */ #include <bits/stdc.h> using namespace std; #define eps 1e-8 #define INF 0x3f3f3f3f const int N 1e6 10; int n, k; pair<double, double> a[N], b[N]; vector&l…...

简单的数学运算&#xff1a; 极限运算&#xff1a; limit(f,x,x0): 计算x→x0时函数f的极限。 举例&#xff1a; syms x y1(1x2*sin(x))^(2/x); y2((1x)^0.5-2)/(x^2-2*x-3); y3x^2*sin(1/x)/sqrt(2*x^2-1); f1limit(y1,0) f2limit(y2,3) f3limit(y3,inf…...

简介&#xff1a; Matlab: 美国MathWorks公司出品的商业数学软件。是一种高级技术计算语言和交互式环境。 主要用于&#xff1a; 算法开发 数据可视化 数据分析 数值计算 一、初识matlab 二、matlab数组运算与…...

matlab中的运算和操作主要是以数组为对象的&#xff0c; 数组又包括&#xff1a;数值数组、字符数组、元胞数组等。 一、数值数组的建立&#xff1a; 1. 直接输入法&#xff1a; 逗号&#xff1a;用来分开数组中的行元素。&#xff08;可用空格代替&#xff09; 分号&#…...

一、自定义函数 格式&#xff1a;函数句柄 (自变量列表)函数表达式 例1 定义函数&#xff0c;并计算f(x)在点x-2,1,2.5,3,5.2的值。 f(x)x.^23*x5 x[-2,1,2.5,3,5.2] y1f(x) 二、 m-文件函数&#xff08;子程序&#xff09; 格式&#xff1a;function [y1,y2]ff(x1,x…...