fzu专题
fzu 2277 Change 线段树
Problem 2277 Change Time Limit: 2000 mSec Memory Limit : 262144 KB Problem Description There is a rooted tree with n nodes, number from 1-n. Root’s number is 1.Each node has a value ai.
fzu 2275 Game KMP
Problem 2275 Game Time Limit: 1000 mSec Memory Limit : 262144 KB Problem Description Alice and Bob is playing a game. Each of them has a number. Alice’s number is A, and Bob’s number i
【FZU】1921 栀子花开 线段树果题
Problem 1921 栀子花开 Accept: 216 Submit: 745 Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Description 这是一个栀子花开的季节，也是一个离别的季节，四年一千多个日日夜夜，那校园的角角落落，留下了我们沉思的身影；那上百次的成绩排名表，印证了我们深深浅浅不断进步的
【FZU】2171 防守阵地 II 线段树
Problem 2171 防守阵地 II Accept: 96 Submit: 360 Time Limit: 3000 mSec Memory Limit : 32768 KB Problem Description 部队中总共有N个士兵，每个士兵有各自的能力指数Xi，在一次演练中，指挥部确定了M个需要防守的地点，指挥部将选择M个士兵依次进入指定地点进行防守任务，获得
【FZU】2105 Digits Count 线段树
传送门：【FZU】2105 Digits Count 题目分析：与、或、异或三种操作都是每一位相互独立的，所以可以将线段树建四棵，分别对应一位，and和or操作相当于覆盖操作，xor操作相当于反转操作，就和普通的线段树方法类似，设立两个lazy标记即可。查询的时候求得每一位的1的个数*权重（1，2，4，8），全部累加就是答案。 代码如下： #include <cst
FZU 1894（单调队列第一发）
题意：参加志愿者选拔的同学们排队接受面试官们的面试。参加面试的同学们按照先来先面试并且先结束的原则接受面试官们的考查。 输入含义1CNAME RP_VALUE名字为NAME的人品值为RP_VALUE的同学加入面试队伍。(名字长度不大于5，0 <= RP_VALUE <= 1,000,000,000)2G排在面试队伍最前面的同学面试结束离开考场。3Q主面试官John想知道当前正在接受面试的队伍中
FZU 2122(KMP)
/*FZU 2122(简单字符串匹配，KMP算法)题目大意：就是给你3个字符串，第一个是模式串(用该串在文本串中去查找与之相同的串)即子串，第二个字符串是去替换在文本串（即主串）已找到相同的子串，从而最后输出产生的新串，如果没有找到，就原样输出文本串(即主串)，第三个字符串就是文本串(即主串)个人解题思想：就是用KMP算法找到子串在主串中的位置，然后首先用相同字符“~”去替换主串中找到的
FZU 2111【 Min Number】
Description Now you are given one non-negative integer n in 10-base notation, it will only contain digits ('0'-'9'). You are allowed to choose 2 integers i and j, such that: i!=j, 1≤i<j≤|n|, here |
FZU 1082【最大黑区域】
Description 二值图像是由黑白两种像素组成的矩形点阵，图像识别的一个操作是求出图像中最大黑区域的面积。请设计一个程序完成二值图像的这个操作。黑区域由黑像素组成，一个黑区域中的每个像素至少与该区域中的另一个像素相邻，规定一个像素仅与其上、下、左、右的像素相邻。两个不同的黑区域没有相邻的像素。一个黑区域的面积是其所包含的像素的个数。 Input 输入由多个测试例组成。每个
FZU 1227【鸡毛信问题】
Description 大革命时期，地下党组织的联络图是一个树状结构。每个党员只和一个比他高一级的负责人单线联系，但他可以与若干个比他低一级的直接下属党员联系。紧急情况通常用鸡毛信传递。假设容易复制鸡毛信，但传递1 次鸡毛信需要1 个单位时间。试设计一个算法，计算从总负责人开始，传递鸡毛信到每个党员手中最少需要多少时间。 对于给定的地下党组织的联络图，计算从总负责人开始，传递鸡毛信到每个党员
FZU 2155 盟国
Problem 2155 盟国 Problem Description 世界上存在着N个国家，简单起见，编号从0~N-1，假如a国和b国是盟国，b国和c国是盟国，那么a国和c国也是盟国。另外每个国家都有权宣布退盟（注意，退盟后还可以再结盟）。 定义下面两个操作： “M X Y” ：X国和Y国结盟 “S X” ：X国宣布退盟 Input 多组case。 每组cas
FZU 2187 扫描线
和HDU 1255差不多 这次是求只被覆盖一次的矩形面积和 修改callen函数即可 data[k].len表示被覆盖的纵长度 data[k].key表示被只被覆盖一次的纵长度 #include "stdio.h"#include "string.h"#include "stdlib.h"#include "math.h"#include "iostream"#inc
FZU 2148（计算几何）叉积模板
题目链接：点击打开链接 题目分析：凸四边形个数判断，枚举法。 Sacb+Sabd+Sacd=Sbcd； 则为凹多边形。 题目总结：i，j，k，l一多，j++写成i++ wa了好几炮 此题可为为模板了 #include <cmath>#include <cstdio
fzu——Problem 2125 简单的等式
Problem Description 现在有一个等式如下：x^2+s(x,m)x-n=0。其中s(x,m)表示把x写成m进制时，每个位数相加的和。现在，在给定n，m的情况下，求出满足等式的最小的正整数x。如果不存在，请输出-1。 Input 有T组测试数据。以下有T(T<=100)行，每行代表一组测试数据。每个测试数据有n（1<=n<=10^18），m(2<=m<=16)。
fzu——Problem 2124 吃豆人（bfs）
Problem Description 吃豆人是一款非常经典的游戏，游戏中玩家控制吃豆人在地图上吃光所有豆子，并且避免被怪物抓住。 这道题没有怪物，将游戏的画面分成n*m的格子，每格地形可能为空地或者障碍物，吃豆人可以在空地上移动，吃豆人每移动一格需要1s时间，并且只能朝上下左右四个方向移动，特别的是吃豆人还能吐出舌头，舌头每移动一格需要0.1s时间，舌头只可以走直线。不必考虑吃豆人转身所需
fzu—— Problem 2129 子序列个数
Problem Description 子序列的定义：对于一个序列a=a[1],a[2],......a[n]。则非空序列a'=a[p1],a[p2]......a[pm]为a的一个子序列，其中1<=p1<p2<.....<pm<=n。 例如4,14,2,3和14,1,2,3都为4,13,14,1,2,3的子序列。 对于给出序列a，请输出不同的子序列的个数。(由于答案比较大，请将答案mod 1
FZU - 2115 多项式积分
题意： Description 给定一个关于x(小写字母)的多项式，求其关于x的一阶积分，结果按降幂输出，要求结果为最简多项式。输出的多项式符合一般书写规则，即有如下特性： 多项式由单项式相加或相减组成，单项式可以表示成ax^b的形式，其中a、b均为整数，b为大于等于0的整数,a不能为0，特别的，当b等于1时，省略”^1”，写做ax，当b等于0时，写作a，而当a的值为±1时，1必须省略。多项
FZU - 2024 LCS EditStep
题意： 给定a，b两个字符串，长度Len(1 <=Len<=1000)，分别求出这两个字符串的LCS长度和EditStep。其中： LCS为两个字符串的最长公共子串。 EditStep为，通过增加一个字符，或者删除一个字符，或者替换一个字符使得a串与b串相同需要的操作个数。 思路：LCS就不说了，EditStep就是：ans[i][j]表示str1的前i,str2的前j的最少步数，三种情
FZU - 2085 幸运图
题意： 我们认为，如果一个无向图不存在自环和重边，那么它就是幸运图 现在，给你一个无向图，判断它是否是幸运图。 #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MAXN = 1005;int n,m;int G[M
FZU 2020 组合 Lucas的应用
题意：给出组合数C(n,m), 表示从n个元素中选出m个元素的方案数。例如C(5,2) = 10, C(4,2) = 6.可是当n,m比较大的时候，C(n,m)很大！于是xiaobo希望你输出 C(n,m) mod p的值! Lucas的证明：点击打开链接 #include <iostream>#include <cstdio>#include <cstring>using namesp
FZU 2019 排列
题意：给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。 思路：枚举起点终点是O(n^2)是会超时的，是中位数的话证明：大于他的和小于他的数是相等的，那么扫描一遍b左边，大于的的话cnt++,否则cnt--,如果cnt==0的话，证明这一边有一个答案，然后再记录cnt值出现的情况，然后扫描一遍b的右边，大于的话cnt--
FZU 2018 计数 快速幂取模
题意：对于方程 x^x = a(mod p), PH想知道对于[0,p-1]内的数，有多少个这样的x满足这个方程。请注意，虽然对于0^0的值有争论，甚至不一定有意义，可是在本题中，PH认为0^0 = 1。 #include <iostream>#include <cstdio>#include <cstring>using namespace std;const int MAXN = 1
FZU 1888三角形问题II
题意：给定平面上的N 个点的坐标，现在你的任务是统计任意3个点构成的三角形的面积和的值。枚举就能过了 用到了海伦公式： 假设在平面内，有一个三角形，边长分别为a、b、c，三角形的面积S可由以下公式求得： 而公式里的p为半周长（周长的一半）： #include <iostream>#include <cstdio>#include <cstring>#in
FZU - 2138 久违的月赛之一 (二分)
Problem Description 好久没举月赛了，这次lqw给大家出了5道题，因为hsy学长宣传的很到位，吸引了n个DDMM们来做，另一位kk学长说，全做对的要给金奖，做对4题要给银奖，做对3题要给铜奖。统计数据的时候，发现每题分别在n个人中有n1、n2、n3、n4、n5个人通过，lqw灵机一动，问kk：“你猜，这次至少会有多少个人获奖？”由于题目太简单了，每题的通过人数一定大于等于最
fzu 1050 Number lengths
题目链接：fzu 1050 Number lengths 题目大意：计算n!有多少位数。 解题思路：ans = log10(n!) = ∑(1≤i≤n)log(i). #include <stdio.h>#include <math.h>const int N = 1000005;int n, d[N];void init() {double sum = 0;fo