jsoi2008专题

P1197 [JSOI2008]星球大战~写题笔记

题目：https://www.luogu.org/problemnew/show/P1197 #include<iostream>#include<algorithm>#include<cstring>#include<cstdio>using namespace std;// 倒过来求解// 将全部有通道的点以边的形式存起来，将所有要攻击的点存起来// 先将所有要拆除的点排除在外

bzoj1570: [JSOI2008]Blue Mary的旅行

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1570 思路：把每天当作一层，一层包含n个点，每层向下一层在原图中有边相连的点连边，表示一天能走一条边，每天的n点向汇连边枚举天数，每次加一层，满流即输出答案 #include<cstdio>#include<cstring>#include<iostream>#includ

[JSOI2008] 最大数题解线段树

[JSOI2008] 最大数传送门题目描述现在请求你维护一个数列，要求提供以下两种操作：查询操作。语法：Q L 功能：查询当前数列中末尾 L L L 个数中的最大的数，并输出这个数的值。限制： L L L 不超过当前数列的长度。 ( L > 0 ) (L > 0) (L>0) 插入操作。语法：A n 功能：将 n n n 加上 t t t，其中 t t t

[bzoj1014]：[JSOI2008]火星人prefix

传送门这个题我一眼秒，然后发现好像是查询好像变成了 O(log2n) O(log^2n) 然后发现数据范围说查询操作不超过10000次，然后就觉得应该是正解了。。然后调试了超级久。。。再然后就WA了3个点。。最后发现我调试的时候为了方便，质数只取到了1000，然后取到1e9+7，就过了。。我们来说正解吧。 emmmm，一句话题解吧。 Splay+Hash+二分好像

[bzoj1013]：[JSOI2008]球形空间产生器sphere

传送门这个题提示太给力了。。。提示：给出两个定义：1、球心：到球面上任意一点距离都相等的点。2、距离：设两个n为空间上的点A, B的坐标为(a1, a2, …, an), (b1, b2, …, bn)，则AB的距离定义为：dist = sqrt( (a1-b1)^2 + (a2-b2)^2 + … + (an-bn)^2 ) 从这个题的提示中，我们已经可以看出来这个题的算法了

1013: [JSOI2008]球形空间产生器sphere（高斯消元）

Description 　　有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在，你被困在了这个n维球体中，你只知道球面上n+1个点的坐标，你需要以最快的速度确定这个n维球体的球心坐标，以便于摧毁这个球形空间产生器。 Input 　　第一行是一个整数n(1<=N=10)。接下来的n+1行，每行有n个实数，表示球面上一点的n维坐标。每一个实数精确到小数点后6位，且其绝对

bzoj 1012: [JSOI2008]最大数maxnumber（树状数组）

Description 　　现在请求你维护一个数列，要求提供以下两种操作：1、查询操作。语法：Q L 功能：查询当前数列中末尾L 个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、插入操作。语法：A n 功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。限制：n是

[BZOJ 1013][JSOI2008]球形空间产生器sphere：高斯消元

点击这里查看原题设球心坐标为（x1,x2,x3,…,xn），某个点的坐标为(y1,y2,y3,…,yn），点到球心的距离为L，那么 L2=(y12−2∗x1∗y1+x12)+(y22−2∗x2∗y2+x22)+(y32−2∗x3∗y3+x32)+...+(yn2−2∗xn∗yn+xn2) L^{2}=({y_{1}}^{2}-2*x_{1}*y_{1}+{x_{1}}^{2})+

JSOI2008最大数--数据结构

这道题有三个做法呢第一个就是普通的线段树太懒了不打了第二个可以单调栈+二分维护一个单调递减的单调栈每次加入数的时候把这个数前面小于它的都删掉然后查询的时候二分找到最前面的在所求范围内的但是话说这种方法好像被加强的数据卡了？？？我也不带了优化了泥萌自己优化一下看能不能过··· 不过这种比较新颖的想法应该都是对着卡才能卡过吧而且代码很短思路清晰也不容易

BZOJ 1012[JSOI2008]最大数maxnumber （线段树解法）

1012: [JSOI2008]最大数maxnumber Time Limit: 3 Sec Memory Limit: 162 MB Submit: 11164 Solved: 4883 [ Submit][ Status][ Discuss] Description 　　现在请求你维护一个数列，要求提供以下两种操作：1、查询操作。语法：Q L 功能：查询当

【JSOI2008】bzoj1013 球形空间产生器

Description 　　问题描述：有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在，你被困在了这个n维球体中，你只知道球面上n+1个点的坐标，你需要以最快的速度确定这个n维球体的球心坐标，以便于摧毁这个球形空间产生器。 Input 　　第一行是一个整数，n。　　接下来的n+1行，每行有n个实数，表示球面上一点的n维坐标。每一个实数精确到小数点后6位，且其绝对值都不超过20

【bzoj 1012】[JSOI2008]最大数maxnumber（线段树||st表）

1012: [JSOI2008]最大数maxnumber Time Limit: 3 Sec Memory Limit: 162 MB Submit: 8663 Solved: 3798 [ Submit][ Status][ Discuss] Description 　　现在请求你维护一个数列，要求提供以下两种操作：1、查询操作。语法：Q L 功能：查询当前数列中末尾L

【bzoj 1015】[JSOI2008]星球大战starwar（并查集）

1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec Memory Limit: 162 MB Submit: 5523 Solved: 2541 [ Submit][ Status][ Discuss] Description 　　很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，