hdu 6033 | 2017 Multi-University Training Contest – Team 1 A Add More Zero

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

题意:

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

思路:

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

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

两边对10取对数得到  $$  x\leq \log_{10} 2^{m} $$

右边用换底公式就是  $$ \frac{m}{\log_{2}10 }  $$

 

代码:

 

在wordpress 中输入数学公式

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

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

干脆记录一下必要步骤。只有一步。

  1. 配置mathjax. 加入下面代码到该主题的header.php中 <head>和</head>之间(要放在<?php wp_head(); ?>

     
  • 换行显示(displayed mathematics),它的分隔符是 $$...$$和 \[...\] ,
  • 行内显示(in-line mathematics),它的分割符号是 \\(…\\)   (只有一个\)

 

 

不记得公式语法去latex online 查看即可

 

bzoj 1059: [ZJOI2007]矩阵游戏 (匈牙利算法)

1059: [ZJOI2007]矩阵游戏

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

Description

  小Q是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N
*N黑白方阵进行(如同国际象棋一般,只是颜色是随意的)。每次可以对该矩阵进行两种操作:行交换操作:选择
矩阵的任意两行,交换这两行(即交换对应格子的颜色)列交换操作:选择矩阵的任意行列,交换这两列(即交换
对应格子的颜色)游戏的目标,即通过若干次操作,使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑
色。对于某些关卡,小Q百思不得其解,以致他开始怀疑这些关卡是不是根本就是无解的!!于是小Q决定写一个程
序来判断这些关卡是否有解。

Input

  第一行包含一个整数T,表示数据的组数。接下来包含T组数据,每组数据第一行为一个整数N,表示方阵的大
小;接下来N行为一个N*N的01矩阵(0表示白色,1表示黑色)。

Output

  输出文件应包含T行。对于每一组数据,如果该关卡有解,输出一行Yes;否则输出一行No。

Sample Input

2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0

Sample Output

No
Yes
【数据规模】
对于100%的数据,N ≤ 200
思路:
纠结了一下建图,由于每个黑点可以按照行换,也可以按照列换。所以我建了一个1..n到1..2n的二分图做匹配。
左边集合是n个对角线上的点,右边集合是行号+列号。
但是每次匹配的时候,一个对角线上的点会同时消耗到匹配的行号和列号。。感觉不是很对啊。。。
实际上发现,我们只需要建立一个n到n的二分图就行了。
原因是,如果有解,那么只需要行或者列的一种变换,就可以达到规定的图案。
比如现在(2,5)是1,(2,2)和(5,5)是0,我们只需要连一条边表示(2,5)可以换到(2,2)即可,不需要连表示(2,5)可以换到(5,5)的边
原因是,如果(2,5)换到(5,5),那么(2,2)也跟着换到了(5,2),我们不考虑之前的(2,2)是什么,被换之后的(2,2)必须是1才符合题意,也就是换之前的(5,2)必须是1.
既然(5,2)是1,那么从(5,2)换到(5,5)即可符合条件。

 

BZOJ 1191: [HNOI2006]超级英雄Hero (匈牙利)

1191: [HNOI2006]超级英雄Hero

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

Description

现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目,只有当选手正确回答一道题后,才能进入下一题,否则就被淘汰。为了增加节目的趣味性并适当降低难度,主持人总提供给选手几个“锦囊妙计”,比如求助现场观众,或者去掉若干个错误答案(选择题)等等。 这里,我们把规则稍微改变一下。假设主持人总共有m道题,选手有n种不同的“锦囊妙计”。主持人规定,每道题都可以从两种“锦囊妙计”中选择一种,而每种“锦囊妙计”只能用一次。我们又假设一道题使用了它允许的锦囊妙计后,就一定能正确回答,顺利进入下一题。现在我来到了节目现场,可是我实在是太笨了,以至于一道题也不会做,每道题只好借助使用“锦囊妙计”来通过。如果我事先就知道了每道题能够使用哪两种“锦囊妙计”,那么你能告诉我怎样选择才能通过最多的题数吗?

Input

输入文件的一行是两个正整数n和m(0 < n <1001,0 < m < 1001)表示总共有n中“锦囊妙计”,编号为0~n-1,总共有m个问题。
以下的m行,每行两个数,分别表示第m个问题可以使用的“锦囊妙计”的编号。
注意,每种编号的“锦囊妙计”只能使用一次,同一个问题的两个“锦囊妙计”可能一样。

Output

第一行为最多能通过的题数p

Sample Input

5 6
3 2
2 0
0 3
0 4
3 2
3 2

Sample Output

4
思路: 从题目向2条锦囊妙计连边,注意判重。由于有一道题答错比赛就结束,因此在hung的过程中一旦不能find就直接break掉。

codeforces div 1 443 A. Short Program (位运算的理解)

题目链接:

题目链接

题意:

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

思路 :

关键在于想起,位运算还是按照二进制位的运算。我们考虑每位即可。

如果初始是0,现在变成了1,那么实际上我们并不确定,这个操作是xor 1 还是 or 1

因此我们需要两个初始的数,一个所有二进制位上都是0,另一个所有二进制位上都是1.

也就是0和1023

对于某个二进制位

如果初始的 (0,1)变成了 (1,1),那么说明这个位置上的位运算是or

如果初始的 (0,1)变成了(1,0) 那么说明这个位置上的位运算是xor

如果初始的 (0,1)变成了(0,0) 那么说明这个位置上的位运算是and

如果初始的 (0,1)变成了(1,0) 那么说明这个位置上没有进行位运算操作。

 

 

 

 

 

 

 

2016 ICPC 大连 区域赛 A Wrestling Match (交叉染色法判断二分图)

题意:

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

思路:

判断二分图。

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

注意判掉没有出现的点。

注意有多个联通块。

 

 

 

codeforces #346 div 2 E. New Reform (和图有关的的计数)

题意:

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

思路:

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

因此对于有环的联通块答案为0,没环的答案为1.

 

 

BZOJ 1854: [Scoi2010]游戏 (并查集)

Description

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

Input

输入的第一行是一个整数N,表示lxhgww拥有N种装备 接下来N行,是对这N种装备的描述,每行2个数字,表示第i种装备的2个属性值

Output

输出一行,包括1个数字,表示lxhgww最多能连续攻击的次数。

Sample Input

3
1 2
3 2
4 5

Sample Output

2

HINT

【数据范围】
对于30%的数据,保证N < =1000
对于100%的数据,保证N < =1000000

Source

 

 

思路:

看到了二分图匹配的题解,但是感觉很错啊?

正确的做法是,将武器看成边,将每个武器的2种属性看成点。

使用某种属性,就要消耗一条边。

因此如果一个联通快是树形结构,k个点,k-1条边,因此有一个属性无法被使用。

由于要求是从1开始递增得攻击,因此显然使得属性最大的点不被使用是最优的。

如果一个联通块有环,那么所有的树型都可以被使用。

注意这个联通快有无环影响计数的思维,和codeforces # 440 div2 E. Points, Lines and Ready-made Titles  很像

 

codeforces 439 C – The Intriguing Obsession (和图有关的计数,组合数学)

题意:

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

思路:

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

那么其实,对于每一对岛屿群,是相互独立的。

对于任意一对岛屿群,设两边岛屿的数量分别为a,b

我们可以从两边各取0个,1个,最多取min(a,b)

需要注意的是,选取了端点之后有顺序的区别。

所以对于该对岛屿,答案是SUM{C[a][k] * C[b][k] * k!}   (k属于0..min(a,b) )

对于其他 两对同理。

 

codeforces # 440 div2 E. Points, Lines and Ready-made Titles (和图有关的计数,思维题)

题目链接

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

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

思路:

参考题解

好菜啊不会做,转载一段题解。

bzoj 1854的并查集思路蜜汁契合 // 看完了题解的我这样想道

首先显然可以将图分为若干个联通块。

且慢,哪里来的图? 那就先考虑建图? 不急不急,先来想想看每一个联通块的性质。

如果该联通块中有环的话,肯定每条边都能取到;如果联通块是一棵树,那么必有一条边取不到(具体阐述见上bzoj 1854),所以只需要知道

  1. 这个联通块中有多少条边
  2. 这个联通块是不是环

这两个信息就可以了

那么可以直接上并查集。

什么样的点可以并到一起呢?横坐标相同的或者纵坐标相同的。

有没有环怎么维护呢?看有没有加进去的边的端点本身就在一个集合里。

联通块中边的数目又怎么知道呢?这倒还挺有意思的,其实只要直接看出现过多少个横坐标或者纵坐标就可以了,因为一个横坐标或者一个纵坐标就代表一条可以选的直线,所以这块联通块的贡献就是2^(x+y)者2^(x+y)-1

然后呢?就做完了。

然而呢?比赛结束。一天了。

相关并且有趣的题目:bzoj1854
codeforces #346 div2

vimrc for ACM-ICPC (赛场用)

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

故地重游,rp++

 

广义Fibonacci数列找循环节 (二次剩余)

问题:给定,满足,求的循

环节长度。

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

这里只说做法

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

对于质因数小于等于delta的部分,我们选择暴力求循环节。

暴力求循环节的代码如下:

通常做法是先暴力求出来之后,写进一个表里。

通常不会有很多项。

对于质因数大于delta的部分,我们判断每个质因数是否是delta的二次剩余,如果是,枚举(prime-1)的因子,否则枚举2*(prime+1)的因子。

贴一个板子,需要注意如果是多个函数嵌套的形式,我们只需要从外向里,依次求循环节即可。

 

再补一个,更为常用的,求斐波那契循环节的板子:

 

可持久化线段树学习笔记

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

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

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

如果没有可持久化线段树,那么我们如果需要不同时刻的线段树,无脑的做法可能是,需要多少个时刻的线段树,就建多少棵线段树。

但是空间绝对gg,我们考虑每次修改,其实对于一次修改,线段树上只有很少一部分被修改了,其他部分都一样。

因此,我们很容易想到,我们何不只考虑修改的部分,其他部分共用,以减少时间和空间消耗呢?

  • 可持久化线段树是利用函数式编程的思想,对记录的数据只赋值不修改,每次插入一个数据后保存一个历史版本,然后利用线段树的结构完全相同,可以直接相减的特性进行区间询问。

 

可持久化线段树有几个经典应用,比如求区间第k大  静态区间第k大   动态区间第k大 

静态区间第k大的思想:

  • 首先,给你一颗值为横坐标的线段树,每个节点上存着该值出现了多少次,这样的一颗线段树你会求区间k大值吧.二分即可.
  • 然后,假设区间是数组arr[n],区间长度是n,那么给你n颗线段树,第i颗线段树是第i-1颗线段树插入arr[i]得到.
  • 如果你有了这n颗线段树,想求区间[l,r]中的第k大值,那么你需要在第r颗和第l-1颗线段树的差线段树上作二分,就可以求得区间第k大值.
  • 差线段树很好理解,比如你有一个部分和数组sum,sum[r]-sum[l-1]就是部分和的差,代表区间[l,r]的和,差线段树同理.
  • 现在,可持久化线段树出现为你解决最后一个问题,空间问题.内存很小,不能够存下n颗线段树,但是,第2条中提到,由于第i颗线段是是第i-1颗线段是插入仅一个值得到的,两颗线段树的区别不大,仅有log(n)个节点发生了改变,我们仅仅需要记录这log(n)的数据就可以记录这个增量,这就是可持久化线段树.

以及求区间中不同数的个数   spoj-dquery 求区间中不同数的个数

思想其实和离线线段树是一样的。

在学习可持久化线段树的时候,遇到过一个叫”权值线段树“的概念

其实并不是什么新东西,只不过是把值作为节点来考虑,参考逆序对的线段树|树状数组 求法…(由于是在值域上建立线段树,所以常常需要离散化)

这思想不是很常见么….感觉完全没必要安个名字…以及,怎么不给BIT也起个叫权值BIT啊orz

 

 

参考资料:

知乎-主席树是如何求区间k大的?

可持久化数据结构之主席树

 

 

2016 CCPC 长春 I 题 | hdu 5919 Sequence II (可持久化线段树求区间第k大+可持久化线段树求区间不同数个数)

题目链接

题意:

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

思路:

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

对于求区间中不同数的个数,离线可以随便线段树,树状数组,或者莫队也行(观察到数据范围<=2E5)

在线的话,就只能可持久化线段树了。

看到一些题解中说要倒序处理…但是之前写求区间不同数的个数,我都是倒序处理的啊? (回想一下,当时似乎正序处理也行…

倒序处理是为了,处理到第i个的时候,第i个一定是当前后缀区间中,第一个出现的…

然后第二个问题,求区间中第k大的下标,离线做法不少,在线的话,也可以用可持久化线段树求。

所以感觉就是板子题,可持久化线段树的2个应用放在了一起orz

 

 

 

bzoj 1901: Zju2112 Dynamic Rankings (可持久化线段树,区间动态第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]的值,改变后,程序还能针对改
变后的a继续回答上面的问题。

Input

第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。
分别表示序列的长度和指令的个数。
第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。
接下来的m行描述每条指令
每行的格式是下面两种格式中的一种。
Q i j k 或者 C i t
Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)
表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。
C i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t
m,n≤10000

Output

 对于每一次询问,你都需要输出他的答案,每一个输出占单独的一行。

Sample Input

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

Sample Output

3
6

思路:

现在我们已经会了用可持久化线段树,去做静态区间第k大的问题。

考虑一次修改,修改的元素会影响后面所有建好的线段树,时间代价是无法承受的。

我们考虑root[i]表示的这颗线段树,它保存的是从第一个元素开始插入到第i个元素后的数字区间。也就是说每次我们进行线段树区间相减时,我们是对两个前缀和[1, l – 1]和[1, r]进行了相减。

所以我们需要的是,以一个可以接受的时间代价,维护一个前缀和。

显然是用BIT来维护。

所以带修改的可持久化线段树,本质上应该是BIT套可持久化线段树。