UVA10891 Game of Sum 题目描述 有一个长度为n的整数序列，两个游戏者A和B轮流取数，A先取。每次玩家只能从左端或者右端取任意数量的数，但不能两边都取。所有数都被取走视为游戏结束，然后统计每个人取走的数之和，作为各自的得分。两个人采取的策略都是让自己得分尽可能高，并且两个人都很机智，求A得分-B得分后的结果。 输入包含多组... [阅读全文]

题解 LuoGu P4147 玉蟾宫 最大子矩阵问题 悬线法 学习笔记 题目描述 这片土地被分成N*M个格子，每个格子里写着'R'或者'F'，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。 现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着'F'并且面积最大。 但是rainbow和freda的OI水平都弱爆了，找不出这块土地... [阅读全文]

P3708 koishi的数学题 题目描述 Koishi想了一道简单数学题 输入一个整数n 设 ​ 你需要输出f(1),f(2)...f(n) 。 按照套路，Koishi假装自己并不会做这道题，就来求你帮忙辣。 输入一个正整数n。 输出： 一行用空格分隔的n个整数f(1),f(2)...f(n) 输入样例：10 输出样例： 9 16 22 25 29 27 29 2... [阅读全文]

题解 LuoGu P1471 方差 题目描述 蒟蒻HansBug在一本数学书里面发现了一个神奇的数列，包含N个实数。他想算算这个数列的平均数和方差。 输入格式： 第一行包含两个正整数N、M，分别表示数列中实数的个数和操作的个数。 第二行包含N个实数，其中第i个实数表示数列的第i项。 接下来M行，每行为一条操作，格式为以下两种之一： 操作1：1 x y k ，表示将第... [阅读全文]

题解 Luogu P1967 货车运输 题目描述 A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。 输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道 路。 接下... [阅读全文]

题解 Luogu P1314 聪明的质监员 小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 n 个矿石，从 1到n 逐一编号，每个矿石都有自己的重量 wi 以及价值vi 。检验矿产的流程是： 1 、给定m 个区间[Li,Ri]； 2 、选出一个参数 W； 3 、对于一个区间[Li,Ri]，计算矿石在这个区间上的检验值Yi： 这批矿产的检验结果Y... [阅读全文]

线段树学习笔记 已知一个数列，你需要进行下面两种操作 1.将某区间每一个数加上x 2.求出某区间每一个数的和 线段树，即是将一个整区间分解成几小区间，保存多个子区间值以便查询时节约时间的数据结构。而LazyTag的设置使在单点修改节约了时间。 L1 1-10(1) / \ L2... [阅读全文]

建树 结点数为N 边数为M 根节点S log2N 为树的最大深度 int log2N=log(1.0*N)/log(2.0)+0.5; 通过DFS预处理出树与深度 inline void dfs(int x,int f){ V[x]=1; D[x]=D[f]+1; F[X][0]=f; for(int i=Last[x];i;i=e[i].next){ if(V[x]) continue; dfs(e[i].to,x); } } 朴素算法 DFS 复杂度O(N) 求LCA(A,B)... [阅读全文]

图的存储 邻接矩阵 初始化 G[i][j]=inf G[i][j] = v 表示 从点i与点j有边，权值为v; 有向图存一遍，无向图存两遍，重边取最小（吧） 适用于稠密图 领接表 定义一个Last[N]数组用于存储某点最新连接的边号 int Last [N],cnt = 0; struct Edge{ int to,v,next; } E[M] ; 加边： inline void add (int from,int to,int... [阅读全文]