Article

关于差分约束（转载）

（本文假设读者已经有以下知识：最短路径的基本性质、Bellman-Ford算法。） 比如有这样一组不等式：

$$ \begin{cases} X1 - X2 <= 0 \\\\ X1 - X5 <= (-1) \\\\ X2 - X5 <= 1 \\\\ X3 - X1 <= 5 \\\\ X4 - X1 <= 4 \\\\ X4 - X3 <= (-1) \\\\ X5 - X3 <= (-3) \\\\ X5 - X4 <= (-3) \end{cases} $$

(1)

Article

一、引言

　　计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。

Article

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1986

这是一道并查集+树的题，采用Tarjan离线算法

首先BS一下出题的人，也太懒了吧，还要我们看1984题才知道输入

题目的意思是告诉一个节点数为40000的树，问我们两个节点间的距离。实际上就是找出公共父节点，Tarjan算法写挫了很容易TLE，我开始用Vector就写搓了，结果TLE，后来重写，自己写邻接表然后AC了。

Article

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2446

这是一道匹配题，把行数（r）和列数（c）按（r+c）%2分成两组，然后连边，做一次二分图匹配，可以直接用匈牙利算法

匹配数等于两组的元素个数则为YES，否则NO

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
using namespace std;

int py[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
/**
 * 最大二分图匹配
 * 最大二分图匹配 = 最小点覆盖
 * Base 1
 */
#define MAXM 1024 //行
#define MAXN 1024 //列
bool mat[MAXM][MAXN] = {false};…
Article

好久不写代码，省赛之后一直在赶作业和复习。对自己还真没什么信心

话说回来试了一下联系赛

三道水题，虽然钱两题很快，但是竟然多敲了几个没用的字符导致WA掉了，会范这种错误表示最近状态不宜写算法题啊

第三题想水一把结果我推得结论有漏洞+有道难题的服务器让人不爽的程度

Article

int a = 12345678;
//格式为sring输出
Label1.Text = string.Format("asdfadsf{0}adsfasdf",a);
Label2.Text = "asdfadsf"+a.ToString()+"adsfasdf";
Label1.Text = string.Format("asdfadsf{0:C}adsfasdf",a);//asdfadsf￥1,234.00adsfasdf
Label2.Text = "asdfadsf"+a.ToString("C")+"adsfasdf";//asdfadsf￥1,234.00adsfasdf
double b = 1234.12543;
int a = 12345678;
//格式为特殊的string样式输出
Label1.Text =…
Article

这次比赛成绩比预期差

开始Ultramanhu调整IDE

Q Boy从头开始看题

我的任务是倒数看题，最后看的题目是J，I，H，G

我看完J觉得J可做（哈密顿回路），但是需要很长时间。就首先放着继续看题

这时候Q Boy看完A提，觉得A题诗简单的图论，就交给Ultramanhu敲代码了，我大致想了一下J题的思路就开始看H题

Article

树状数组模块

ACM个人模板

POJ 2155 题目测试通过

/**
 * 树状数组模块
 * 下标从0开始
 */
typedef long DG_Ran;
typedef long DG_Num;
const DG_Num DG_MAXN = 1005;

//2^n
DG_Num LowBit(DG_Num n)
{
    return n & (-n);
}
//获取父节点索引
DG_Num DGFather(DG_Num n)
{
    return n + LowBit(n + 1);
}
//获取小的兄弟节点索引
DG_Num DGBrother(DG_Num n)
{
    return n - LowBit(n + 1);
}
//查找增加树状数组前pos项和
//参数(树状数组[in],索引[in],初始赋0即查找前n项和[out])
//复杂度:log(n)
void DGFind(DG_Ran *g,DG_Num pos,DG_Ran…
Article

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3398

题目要我们计算1，0的排列方式总数，并且对任意长的字符串，1的数量大于等于0的数量

我们可以把题目转化为从（0，0）点到（m，n）点的方法总数，且路径不经过y=x-1这条直线

然后我们可以把从（-1，-1）到（m，n）的所有路径按以y=x-1翻转，所得到的路径显然就是经过y=x-1的所有方案

Article

/**
 * 线性筛法求素数表
 * 复杂度: O(n)
 */
const long MAXP = 1000000;
long prime[MAXP] = {0},num_prime = 0;
int isNotPrime[MAXP] = {1, 1};
void GetPrime_Init()//初始化调用
{
    for(long i = 2 ; i <  MAXP ; i ++)
    {
        if(! isNotPrime[i])
            prime[num_prime ++]=i;
        for(long j = 0 ; j < num_prime && i * prime[j] <  MAXP ; j ++)
        {
            isNotPrime[i * prime[j]] = 1;
            if( !(i % prime[j]))…
Article

又是我们的OJ

题目链接：

http://www.cn210.com/onlinejudge/problemshow.php?pro_id=92

Description

tancu likes space travels but he is a poor software developer and will never be able to buy his own spacecraft. That is why he is preparing to steal the spacecraft of Petru. There is only one problem - Petru has locked the spacecraft with a sophisticated cryptosystem based on the ID numbers of the stars from the Milky Way Galaxy. For breaking the system Stancu has to check each subset of four…

Article

http://www.cn210.com/onlinejudge/problemshow.php?pro_id=98

我们的OJ

Description

We say that a set 

$$S = {x1, x2, ..., xn}$$

is factor closed if for any xi ∈ S and any divisor d of xi we have d ∈ S. Let’s build a GCD matrix (S) = (sij), wheresij = GCD(xi, xj) - the greatest common divisor of xi and xj. Given the factor closed set S, find the value of the determinant:

Input

The input contains several test cases. Each test case starts with an integer n (0 < n < 1000),…

Article

链接: http://acm.pku.edu.cn/JudgeOnline/problem?id=1141 题目意思是输入一些括号，补充括号使之成为没有错误的括号就是只能有括号组在括号组里面，不能出现([)]或者([)]一类的情况 方法是DP，有点绕的DP DP方程是 bc[i][j] = min(bc[i][k] + bc[k][j]) 注：bc[i][j]表示字符i和字符j之间需要插入几个括弧 然后尽量多地分割字符串 不解释，贴代码：