whix

分类

acm(1) codeforces(13) dp(1) java(1) 区域赛真题(2) 图论(20) 字符串(3) 数据结构(4) 数论(37) 未归档(32) 牛客(8) 组合数学(7) 计算几何(1) 题解(9)

/ 注册

全部文章（共139篇）

Choose and divide UVA - 10375

求两个组合数的商，数据大，肯定不能直接算。根据唯一分解定理，每个数可以分解成若干个素数的幂的乘积的形式。可以把分解成的素数的幂记下来，最后知道每个素数的出现次数，依次求幂即可。主要的收获： 1.学会用唯一分解定理 2.复习了欧拉筛 3.pow()的函数原型：double pow(double,d...

2019-08-18

0 514

Colossal Fibonacci Numbers! UVA - 11582

一道数论题数据范围，要用unsigned long long ,输入输出用%llu 还有一个坑，当a=0时，报错。因为这个 runtine error好多次。另外，因为a 一开始就很大，所有用快速幂时，首先就要对a取模。主要是周期的确定。 #include <cstdio> #i...

2019-08-17

0 479

二分图匹配

一.最大匹配：匈牙利算法：总体来说，就是不断找增广路，如果找到 i 可以匹配而没有匹配的点 j ，就将这个点 j 与 i 配对，而如果发现要匹配的点 j 已经和 k 配对了，就对这个点 j 所配对的点 k 进行寻找增广路的操作，看这个点k 能不能另外找到其他的点 x 来替代 j 点来进行配对,如...

2019-08-14

0 490

Divisibility HDU - 3335

要求给你一串数，选出其中相互不具有整除关系的数，问最多可以选多少个数？可以转化为二分图匹配的最大独立集问题的模型，在有整除关系的两个数之间建立边，从而构建整个二分图。这样，满足条件的数，即之间没有边相连的两个数。就满足独立集的定义，求出最大独立集即可。最大独立集=顶点数-最小顶点覆盖=顶点数-最大...

2019-08-14

0 435

Dining POJ - 3281

此题难点在于建图，因为要保证每一头奶牛只能吃它喜欢的一种食物和饮料，且每一食物和饮料只能用一次。一开始把奶牛放中间，食物和饮料放在两边，但这样不能保证一头奶牛只吃一种食物和饮料。因此要采用一种常用的建图方法–拆点建图，把奶牛分成两边，中间权值为1，这样就能保证每一头奶牛只吃一种食物和饮料。其他的创建...

2019-08-10

0 411

ACM Computer Factory POJ - 3436

这个题目的难点在于如何建图，网上的题解大部分是通过拆点来建的，其实也可以不用拆点。把初始条件要求中没有1（可以是0,2，WA了好几次）的机器和人为设立的源点相连，加工后全部为1的机器和人为设立的汇点相连，然后对于每一台机器 i，当作边的终点，从其他机器中找到加工后条件和它初始条件符合的 j（对于p...

2019-08-10

0 433

Farm Tour POJ - 2135

主要是考虑如何转化为网络流问题，要求从起点到终点，再从终点到起点，总的花费最小。相当于从源点到终点走两遍，因为要求每一条边只能走一遍，所以可以以1为每条边的流量，用来限制每一条边只能走一遍，以每条边的路程为花费，再设立一个源点和一个汇点，源点和1号节点之间费用为0，流量为2，n号点和汇点之间的边流量...

2019-08-09

0 504

网络流

最大流：算法： 1.Ford_Fulkerson(F_F算法) 2.EK算法 3.dinic算法 EK: 基于暴力搜索思想的方法，每次都采用bfs去寻找从源点到汇点的增广路，直到找不到，即表示找到了最大流，每次找到一条增广路（找的时候记得存下路径）后，可以求出这条路上的最小流量，即为这条增广路的流...

2019-08-09

0 571

Max Sum Plus Plus HDU - 1024

经典的dp问题，但自己的dp 水平实在太差。首先定义，dp[i][j]表示把前 j 个数分成 i 组的最大值,可以得到状态转移方程： dp[i][j] =max (dp[i][j-1]+s[j],max(dp[i-1][k]+a[j])) （0<=k<=j-1）前面表示s[j]独立成...

2019-07-23

0 409

Currency Exchange POJ - 1860

BellMan 算法解决一直用迪杰斯特拉算法求最短路问题，一看到最短路就思维固定。要根据不同问题的特点用不同的算法。附上代码，对bellman算法理解的不算深刻。 #include <cstdio>//判断最长路径是否有正环 #include <algorithm> u...

2019-07-23

0 363