whix

未归档

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

/ 注册

全部文章 / 未归档（共32篇）

Gone Fishing POJ - 1042

大概思路：贪心+枚举如果直接求解，最难算的就是从一个湖到另一个湖的过程，到底要不要走，要不要在这个湖钓鱼，这就比较难考虑。那么我们可以换一种思维方式。因为人最终肯定是要停止在某一个湖的，那么我们就可以枚举最终停止的湖泊，这样从第一个湖到停止的湖的耗时就确定了。那么，我们就可以认为人可以在湖之间瞬...

2019-09-27

0 619

Codeforces Round #588 C. Anadi and Domino D. Marcin and Training Camp

C题：题意是给你一个无向图，保证无重边，无自环，在每一条边上放一个domino,而且保证对于任意一个点，其边上放的domino的该点一侧的点数相同，然后问你图中能放的domino的最大数量。思路：当n<=6时，每一点所连的边的数量最大为5，而domino的点的数量是可以满足的，所以可以保...

2019-09-24

0 400

解佩尔方程

1.若已知方程x^2-dy ^2=1的最小特解（最小正整数解）x1,y1，那么有迭代公式： xn=xn-1x1+dyn-1y1 yn=xn-1y1+yn-1x1 求出所有的解(xk,yk),可以用矩阵表示如下： |xk|=|x1 dy1| ^(k-1） |x1| |yk| |y1 x1| |y1| ...

2019-08-31

0 661

中国剩余定理

若m1,m2,m3,m4,m5,…,mr是两两互素的正整数，则同余方程组 x=a1(mod m1) x=a2(mod m2) x=a3(mod m3) … x=ar(mod mr) 有模 M=m1m2m3…mr的唯一解，即为中国剩余定理。大概思想就是把解用几个数的和的形式来表示，然后利用拓展欧几里...

2019-08-29

0 485

Evacuation POJ - 3057

题目大意，在一房间里，有多个’.'每个代表一个人，房间的的边界由’X’和’D’组成，分别代表墙和门，而且房间内部保证没有门。现在问题问所有人逃离房间（到达’D’处即表示逃离成功），而且每一扇门一个时间只能允许一个人通过，每个人只能向上下左右移动，每次移动花费一秒。逃离过程中，一个点可以容纳多个人，即...

2019-08-23

0 515

Ilya And The Tree

一开始看题目，完全没有思路，想到用dfs，但一直不知道处理。看了别人的思路，最后写了很久，才AC。大概思路：对于根节点，要么为0，那么不为0，而且根节点一定处于任意一条路中，利用这个性质，我们可以对根节点的状态进行枚举。当根节点为0时，那么每条路上的把一个数变成0的机会已经用掉了。那么只有对此...

2019-08-21

0 407

Colossal Fibonacci Numbers! UVA - 11582

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

2019-08-17

0 479

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