zoj专题
数论ZOJ 2562
题意：给定一个数N，求小于等于N的所有数当中，约数最多的一个数，如果存在多个这样的数，输出其中最大的一个。 分析：反素数定义：对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数。 性质一:一个反素数的质因子必然是从2开始连续的质数。 性质二:p=2^t1*3^t2*5^t3*7
zoj 1721 判断2条线段（完全）相交
给出起点，终点，与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离，然后最短路。 2点可达条件：没有线段与这2点所构成的线段（完全）相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;
zoj 3228 ac自动机
给出一个字符串和若干个单词，问这些单词在字符串里面出现了多少次。单词前面为0表示这个单词可重叠出现，1为不可重叠出现。 Sample Input ab 2 0 ab 1 ab abababac 2 0 aba 1 aba abcdefghijklmnopqrstuvwxyz 3 0 abc 1 def 1 jmn Sample Output Case 1 1 1 Case 2
ZOJ Monthly, August 2014小记
最近太忙太忙，只能抽时间写几道简单题。不过我倒是明白要想水平提高不看题解是最好的了。 A 我只能死找规律了，无法证明 int a[50002][2] ;vector< vector<int> > gmax , gmin ;int main(){int n , i , j , k , cmax , cmin ;while(cin>>n){/* g
ZOJ 3324 Machine(线段树区间合并）
这道题网上很多代码是错误的，由于后台数据水，他们可以AC。 比如这组数据 10 3 p 0 9 r 0 5 r 6 9 输出应该是 0 1 1 所以有的人直接记录该区间是否被覆盖过的方法是错误的 正确方法应该是记录这段区间的最小高度（就是最接近初始位置的高度），和最小高度对应的最长左区间和右区间 开一个sum记录这段区间最小高度的块数，min_v 记录该区间最小高度 cover
【ZOJ】3362 Beer Problem 最小费用流
传送门：【ZOJ】3362 Beer Problem 题目分析：这道题本来应该很快就AC的，但是！因为我以前犯的一个致命错误导致我这题一天了到现在才调出来！唉。。失策。。貌似给的模板也有这个错误。。。马上就去改。。但是这个错误竟然还能过掉那么多的题。。害我还要一题一题的改回去。。 本题就是赤裸裸的最小费用流。 新建汇点t（源点即1），将所有的n-1个城市和汇点建边，容量为无穷大，
【ZOJ】2332 Gems 最大流——判断满流
传送门：【ZOJ】2332 Gems 题目分析：首先我们设立源点s，汇点t，s向所有宝石建边，容量为题目中给出的，然后所有可行的转换，向两个宝石之间建无向边，容量为INF，接下来所有的宝石向自己相应的类型建边，容量INF，所有的宝石向自己相应的颜色建边，容量INF。最后，所有的类型以及颜色向汇点建边，容量为题目中给出的。最后跑一遍最大流，如果满流，说明所有的宝石都成功的限制条件下分给了男主
【ZOJ】2532 Internship 最小割——关键割边
传送门：【ZOJ】2532 Internship 题目分析：题目意思很明显，问你能否增加一条边的容量使得流量增加，就是让求关键割边。关键割边怎么求？首先按照题意建图跑一遍最小割。之后在残余网络上进行dfs，将从源点s出发能到的点标记为1，将从汇点t出发能到的点重标记为2。一条边为关键割边当且仅当它为正向边且弧头标记为1，弧尾标记为2。 PS：注意dfs的细节，s出发沿正向残余网络，t出发
【ZOJ】2071 Technology Trader 最大权闭合子图
传送门：【ZOJ】2071 Technology Trader 题目分析：最大权闭合子图问题。源点向订单建边，容量为利益，汇点向组件建边，容量为成本，原图所有边变成容量无穷大的边，最后跑一遍最小割，订单利益和减去最小割容量就是最大净利润。 输出方案就从源点跑一遍dfs，能从源点到达的所有点都标记上。然后看从源点出发的边的弧尾是否被标记，被标记表示被使用，然后再看从汇点出发的点，如果被标记
【ZOJ】2539 Energy Minimization 最小割——项目分配问题
传送门：【ZOJ】2539 Energy Minimization 题目分析：还是项目分配问题，还是曾经的味道TＵT 再次请出神奇的函数： 再看看题目中的函数： 惊人的相似啊有木有！简直就是稍作修改就好了。。 因为Xi只能取0或1，所以最终我们可以将所有的Xi分成两个集合：Xi取1的集合，Xi取0的集合。 假设源点S和Xi取1的集合相连，汇点T和Xi取0的集合相
【ZOJ】3874 Permutation Graph 【FFT+CDQ分治】
传送门：【ZOJ】3874 Permutation Graph 题目分析： 容易知道一个个连通块内部的标号都是连续的，否则一定会有另一个连通块向这个连通块建边，或者这个连通块向另一个连通块建边。而且从左到右左边的连通块内最大的标号小于右边连通块内最小的标号。 然后我们可以构造dp方程： dp[n]=n!−i!∗dp[n−i] \qquad \qquad dp[n] = n! - i! *
【ZOJ】3881 From the ABC conjecture【暴力容斥】
传送门：【ZOJ】3881 From the ABC conjecture 复杂度大概 O(N0.67) O(N^{0.67})，我也不会算www，首先转换一下（我们是根据积性函数打表找规律得到的，也可以推出来）使得： g(N)=∏pi ϵ N(pia+1) g(N)=\prod_{pi~\epsilon ~N} (pi^a+1) 暴力展开发现贡献为： h(N)=
【ZOJ】3889 Making Sequence【构造】
传送门：【ZOJ】3889 Making Sequence 根据题意构造即可。ZOJ月赛我们抢的第二个FBwww my code: my~~code: #include <bits/stdc++.h>using namespace std ;typedef unsigned long long ULL ;const int MAXN = 205 ;ULL n , a , b , s ,
ZOJ 3715 Kindergarten Election
题意： n个人投票 唯一一个票数最多的人当选 1想当选 他可以通过给别人糖让不选他的人选他 问 最少需要多少糖 思路： 由于n比较小 可以枚举1当选时得了多少票 这样就可以贪心的使用糖 如果1当选时有i票 那么所有人都要先保证选票数<i 而且还要保证至少一个人<i-1 因为1还会投出一票 保证上述条件下 如果1票数已经超过i 则说明这次枚举是失败的 如果不
ZOJ 2362 Beloved Sons
题意： 将男孩和女孩配对 让月老开心度最高 （我把题目改得真洋气…） 思路： KM不解释… 代码： #include<cstdio>#include<cstring>#include<algorithm>#define oo 99999999#define M 410using namespace std;int t,n,m,ans;int link[M],
ZOJ 1992 Sightseeing Tour
题意： 判断混合图欧拉回路 思路： （欧拉回路整理 参考 http://zhyu.me/acm/zoj-1992-and-poj-1637.html 和 http://blog.csdn.net/zxy_snow/article/details/6230223） 1.无向图：图连通，且图中均为偶度顶点。 2.有向图：图连通，且图中所有顶点出入度相等。 3.混合图：混合图欧拉回
ZOJ 3430 Pizza schedule
题意： 给你一串编码后的单词和一篇文章 问 编码前文章中出现了几个单词 思路： 根据题意反编码 然后AC自动机跑一下 转化字符时候注意长度 因为可能转换出'\0' 所以转完后再求strlen会出错 注意 ZOJ的char默认是signed char 所以转码后要么存在unsigned char数组里 要么用int数组存 否则会错的！！ 因为signed char
最长公共上升子序列(LCIS)ZOJ 2432
立方算法: #include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#define M 505using namespace std;typedef long long LL;LL a[M],b[M];int dp[M][M];int main(){//freopen("in.txt","
The Problems of zoj By watashi
2902.Ten drops 2960.Re-rejudge 3051.Playing Poker 3058.Circle and Ring 3073.Bernstein Polynomial 3150.Dareda? 3227.Perfect Cherry Blossom 3229.Shoot the Bulle
九度考研真题 浙大 2010-2浙大1006：ZOJ问题
//题目1006：ZOJ问题 #include<iostream> #include<string.h> using namespace std; int main() { char s[1010]; char a[1010];//开始部分 char b[1010]; //中间部分 char c[1010];//后部分 int num1=0,n
zoj 3508 The War 贪心
士兵有一个拿武器的重量的范围，给出几种武器的重量，问如何才能让更多的士兵装备武器，求出最大的人数 Description A war had broken out because a sheep from your kingdom ate some grasses which belong to your neighboring kingdom. The counselor of y
zoj 3792 Romantic Value（最小割下边数最小）
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5300 大致题意：给出一个无向图，以及起点与终点。要删除一些边使得起点与终点不连通，在删掉边的权值之和最小的情况下要求删除的边数尽量少。求出一个比值：剩余边数权值和/删除的边数。 思路：删除边的权值之和最小显然是求最小割即最大流。但同时要求删除边数最少，解决方法是
第二次选拔——ZOJ
简单，不多说。 Description 读入一个字符串，字符串中包含ZOJ三个字符，个数不一定相等，按ZOJ的顺序输出，当某个字符用完时，剩下的仍然按照ZOJ的顺序输出。 Input 题目包含多组用例,每组用例占一行，包含ZOJ三个字符，当输入“E”时表示输入结束。 1<=length<=100。 Output 对于每组输入,请输出一行，表示
ZOJ 3886 Nico Number (线段树)
题目地址：ZJU 3886 这个题需要想到一点，因为对一个数x不断取模的话，而且设定他小于模才会进行取余操作的话，那么最多只会进行logx次，因为每次取模都会使x最少折半。然后想到了这点就很好做了。对于区间取模更新操作可以直接暴力更新，维护一个最大值，如果这个区间的最大值小于模的话， 就不用继续向叶子更新了。然后其他的大于模的就更新到叶子节点。 然后对于NicoNumber来说，只有6，2的幂
ZOJ 1586 QS Network （MST）
建图：给你的n*n矩阵不是直接的花费，而是边花费，总花费=边花费+两个端点的花费。之后模版走起 /************************************************ Author: fisty* Created Time: 2015/2/28 14:16:51* File Name : E.cpp*******************************