http://www.cn210.com/onlinejudge/problemshow.php?pro_id=98
我们的OJ
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:
The input contains several test cases. Each test case starts with an integer n (0 < n < 1000),…
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3757
题目大意
第一行输入n，k，f表示从n个服务器里选k个，传输大小为f（以Mb为单位）的文件
接下来输入每个服务器的吞吐量，带宽和资源消耗（pi，bi，ci）
题目链接： http://acm.pku.edu.cn/JudgeOnline/problem?id=2976
0-1分数规划
最优比例生成树
迭代法
证明：（前几次都是看别人的，这次自己证明）
对于集合s，令l* = max{ a(x) / b(x) } = a(x*) / b(x*).l为所求的最优解，x为对应的集合
注：b(x)必须恒大于0
然后令z(l) = min{ l × b(x) - a(x) }
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2728
和3757一样都是01分数规划的题，不同的是3757是用的二分，这里用的是Prim
0-1背包部分和3757一样
令m(l) = min{∑(1.0 * h[i][j] - l * dis[i][j] )}
h[i][j]是i到j的高度差，dis是距离，把m(l)作为边的权值（黑书上有）
链接: 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之间需要插入几个括弧 然后尽量多地分割字符串 不解释，贴代码：
这道题是我专门为了了解和学习树状数组而写的
这题用树状数组记录翻转次数,然后mod一个2,也可以不断地取反
还要用到二维的树状数组.于是我专门写了个模板用
题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=2155
题意大致是输入语句,Q表示要求输出A(x,y)是1还是0.C表示把(x1,y1)->(x2,y2)间的矩形中所有元素的1变成0,0变成1
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1720
这题纯计算几何就搞定了，开始我写了个很长很长的代码，但是Wa掉，也不知道是代码那里有疏漏还是精度问题
看来我的搜索真的很烂，简单的搜索都搞定的这么痛苦
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1724
题目大意是输入 拥有钱数，城市数，路的数量
然后输入格式是 起点，终点，路长，路费
注册表常用键值意义
[HKEY_CURRENT_USER\Software\Policies\Microsoft\Internet Explorer\Control Panel]
;〖Internet Explorer选项类〗
“HomePage”=dword:00000001 ;禁止更改主页设置〖0=可修改〗
“Cache”=dword:00000001 ;禁止更改Internet临时文件设置〖0=可修改〗
“History”=dword:00000001 ;禁止更改历史记录设置〖0=可修改〗
“Colors”=dword:00000001 ;禁止修改【文字】和【背景】的颜色〖0=可修改〗
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3513
题目大意是输入树状的家庭关系，问怎么买票（买家庭票还是个人票）最省钱并且票的数量最少
这道题是一道Hash+树状DP问题。编码长度相当可观，需要较好的编码能力
我这题编码就犯了几个低级错误，然后算法错误一次，导致了无数的WA
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3309
一道典型的Hash题
题目很好理解。这里不复述
由于输入语句最大数量200000，不用Hash铁定TLE。然后数据量不超过10000，所以必然有很多search和reply的操作。
对于这个稍微做下优化就OK了
/**
* Hash模板
* Based: 0
* template<unsigned long _SZ,class _T, unsigned long *pFun(_T _Off)>
* class _My_Hash_ToInt
* 传入数据大小_SZ,传入类型_T,Hash函数
* 传入类型_T必须重载 = 和 == 符号
* 收录了ELFHash函数
* 主要是为了判重的简化些的模板
* Hash算法性能比较见 http://www.cnblogs.com/lonelycatcher/archive/2011/08/23/2150587.html
*/
const long hashsize = 51071; //Hash表大小(注意修改)
// 各种Hash算法
unsigned int SDBMHash(char *str)
{
unsigned int hash = hashsize;
while (*str)
{
//…题目： http://acm.hdu.edu.cn/showproblem.php?pid=3336
水题一道，主要是测试数据很水
不解释，贴代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
char str[200005];
vector<long>glo_Pos;
int main()
{
int t;
long output,i,n,j;
scanf("%d",&t);
while(t --)
{
output = 0;
glo_Pos.clear();
scanf("%ld %s", &n, str);
for(i = 0; i <…3636 Nested Dolls
题目链接：[http://acm.pku.edu.cn/JudgeOnline/problem?id=3636
](http://acm.pku.edu.cn/JudgeOnline/problem?id=3636)好吧，这题我看了解题报告。而且解题报告有错误的。只考虑w递增，没考虑w值相等的情况。
我自己这里加进去了判断。主要是看解题报告后才知道数据这么弱，就按他的写了
大意是给出N个玩具，要求放k组，其中每组都是大玩偶套小玩偶。在w（宽）和h（高）都大于
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3631
我讨厌这么长的题目
这题是模拟那个Hash算法，有点像我之前转载的那篇文章里提到的Hash
打造最快的Hash表(转) [以暴雪的游戏的Hash为例] 这里是用两个Hash函数算出两个Hash值h1和h2，如果h1位置已经被占用就检查h2位置，如果都被占用就把原来的替换掉再给原来的字符串重新计算映射。这样下去可能出现死循环。会出现死循环就输出
状态压缩+DP
1972的增强版
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2596
题意是给出小于10个的骰子，要求竖着叠成一条，而且每两个相接的骰子相接的面的数字相同
求侧面数字的最大和。如果叠不出来输出0
要注意的是1972题里必须按输入的骰子的顺序叠，而这里可以任意顺序，这样难度就大很多了
为什么我用线段数这么不灵活呢？
大概思路是线段数记录某牛之前的坐标小于这个牛的牛的坐标和和牛的个数
然后其他部分线性数组记录
OK，贴代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 20005
class cow
{
public:
int v;
int pos;
cow(){};
~cow(){};
};
bool cmp(cow a,cow b)
{
return a.v < b.v;
}
cow cw[MAXN];
long long belowXNT[MAXN];//树状数组，保存小于等于某坐标的牛的个数,计算时使用
long long belowXN[MAXN];//一般数组，保存小于等于某坐标和索引的牛的个数…又来发解题报告了
这回是树状DP
/*
* 树状DP
* 首先把数据想象成树状的
* 由于输入数据为树状，不需要构建树
* 可令degree[i]为包括i且以i为根节点的所有子节点数量
* dp[i]为删除i后的最大子节点数量或父亲节点数量 （这里我理解了很久）
*/
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int>chirld[10002];
int dp[10002] = {0}
,degree[10002] = {0}
,isJudged[10002] = {0};
int search(int pos,int &n);
int main()
{
int n,i,a,b;
bool isnone = true;
scanf("%d",&n);…题目链接: http://acm.pku.edu.cn/JudgeOnline/bbs?problem_id=2528
这题又是线段树+离散化
慢慢的对离散化有点感觉了,但是这题我还是错了3次
题目大意是一层一层地叠板子,问最后能看到几块
输入是板子的开始和结束位置
由于输入的是闭区间线段开始我就构造闭区间线段的线段树,但是后来发现很多问题,
在ACM的竞技场上走过了一年。这一年是充满艰难的一年，这一年是充满困惑的一年。这也是充满激情的一年。这之间有欢笑，有惊喜,也有黯然失色的悲伤.苦战一年，却没有拿到任何的成绩， regional的失败让我刻骨铭心也深深感受到了实力的差距。伤感之余也让我想起了我们ECUST的ACM之歌,我又看了一遍，每次看这篇文章都会有种说不出的感动与激情。让我有了继续走下去的力量。明年，再战ACM，等着我们，我们要成为明年名副其实的ACMer。