题意：

有这样一个有关最大公约数的函数: 函数 f(x, y):

 1{
 2     c=0
 3     当 y>0:
 4     {
 5          c +=1
 6          t = x % y
 7          x = y
 8          y = t
 9      }
10      返回 c * x * x
11}

给出三个正整数n,m,p，你需要计算:

$$ \sum_{i=1}^{n} \sum_{j=1}^{m} \left \lfloor \frac{i*j}{f(i,j))} \right \rfloor $$

n <= 666,666,666, m <= …

http://acm.hdu.edu.cn/showproblem.php?pid=6038

题意：

给出两个序列 a 和 b ，求满足  f[i]= b_{f[a[i]]} 的函数个数。

思路：

分别找两个序列的循环节，这一点是比较容易想到的。

由于点都在0..n-1 或者0..m-1，因此没必要建图跑dfs找循环节，直接while就可以了。

http://acm.hdu.edu.cn/showproblem.php?pid=6034

题意：

有一个仅由小写字母组成的字符串，要求将a..z的字母，对应到0..25，每个数字只能被一个字母对应，得到一个26进制的数，现在问这个数最大是多少。注意不允许有前导0，除非这个数本身就是0.

1230: [Usaco2008 Nov]lites 开关灯

Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1676  Solved: 874 [Submit][Status][Discuss]

Description

Farmer John尝试通过和奶牛们玩益智玩具来保持他的奶牛们思维敏捷. 其中一个大型玩具是牛栏中的灯. N (2 <= N <= 100,000) 头奶牛中的每一头被连续的编号为1..N, 站在一个彩色的灯下面.刚到傍晚的时候, 所有的灯都是关闭的. 奶牛们通过N个按钮来控制灯的开关; 按第i个按钮可以改变第i个灯的状态.奶牛们执行M (1 …

http://acm.hdu.edu.cn/showproblem.php?pid=6043

题意：

n双袜子标号1到n，初始在抽屉里，每天早晨穿一双标号最小的袜子，晚上把脏袜子放到盆里，如果放完之后喷子里已经有了n-1双脏袜子，那么就要洗，然后在第二天晚上放回抽屉里。问第k天穿的是标号为几的袜子。

tags:

• codeforces
• 算法竞赛
• acm
• ACM

http://acm.hdu.edu.cn/showproblem.php?pid=6033

题意：

问最大的x,满足  $$ 10^{x} \geq 2^{m}-1  $$

思路：

看到指数的比较大小，直觉就是取下对数啦

其实直接可以把1忽略，因为2的幂次显然不会出现末尾是0，所以不会影响结果

查了一些资料。。发现不是要装各种插件（还不一定能用，比如和crayon冲突。。就是讲得很不清楚orz。。

又下一个win下的公式编辑器之类的软件是什么鬼啊？

1059: [ZJOI2007]矩阵游戏

Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 5251  Solved: 2512 [Submit][Status][Discuss]

Description

　　小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N

1191: [HNOI2006]超级英雄Hero

Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 5221  Solved: 2356 [Submit][Status][Discuss]

Description

现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等等。 这里，我们把规则稍微改变一下。 …

题目链接：

题目链接

题意：

一段程序，最多5E5个操作，每个操作的格式为 <opt,x> ，opt表示位或，位异或，位与 三种位运算的一种，x表示范围0..1023的数。现在要求将该程序化简至最多 5个操作，使得对于0..1023的输入，输出与该程序同样的结果。

题意：

给出n个点m条边，以及已知的好点和坏点。一个边连接的2个点一定是一好一坏，问是否有合法方案，使得每个点被确定好坏。

思路：

判断二分图。

先染已知的，再染未知的。

题意：

给出n个点，条边的无向图，无重边，无自环。现在要求把所有的无向边换成有向边，使得入度为0的点最少。问最少的入度为0的点是多少。

思路：

对于每个联通快，如果有环，我们可以顺时针连接环上的点，以指向环的方向连接联通快上的其他点，这样就可以保证所有点的入度都不为0. 如果是树形结构，则不可避免得使得一个点的入度为0.

Description

lxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，然后只能使用某个属性值为2的装备攻击boss，然后只能使用某个属性值为3的装备攻击boss……以此类推。 现在lxhgww想知道他最多能连续攻击boss多少次？

题意：

3个岛屿群，每个岛屿群有若干岛屿。现在要在岛屿之间连桥，桥的长度是1，规定2个属于相同岛屿群的岛屿的距离要大于等于3.

思路：

一直在纠结大于等于3的距离的事情。。。其实这句话等价于，同一个岛屿，对于另外两个岛屿群，都最多只能连接1个岛屿。

题目链接

题意：有n个整点，每个点处可以什么都不画，或者画一条垂直方向的直线，或者画一条水平方向的直线。

现在给出n个点的坐标，问最多右多少种不同的图案。(只要有一处不同，就认为两个不同）

tags:

• codeforces
• acm
• vim
• ACM

弄了点比较短的，赛场上用的配置文件orz

 1map <F5> :call Co()<CR>
 2func! Co()
 3    exec "w"
 4    exec "!g++ % -std=gnu++11 -Wall -o %<"
 5    exec "! ./%<"
 6
 7endfunc
 8syntax on
 9set nu
10
11autocmd BufNewFile *.cpp  exec ":call SetTitle()"
12func …

**问题：**给定 ，满足 ，求 的循

环节长度。

原理见广义Fibonacci数列找循环节

这里只说做法

我们先写出递推式的特征式子   x^2 =ax + b,整理得到 x^2-ax-b=0求出 delta = a^2+4b

起因是16长春CCPC遇到了一个全场万人过的主席树题目，然而我不会orz，哭哭

可持久化线段树的本质是很多棵形态完全相同的线段树。

也可以理解成是，保存了不同时刻版本的线段树的数据结构。

题目链接

题意：

给定一个序列 n，有 m次查询，每次查询一个区间[l,r]，求区间中每一种数在区间中第一次出现的位置的中位数，强制在线。

思路：

先分解一下问题，我们要求一段区间位置的中位数，其实可以分解成，求区间中不同数的个数+求区间中第k大的下标。

Description

给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1

],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改