2016 CCPC Changchun Onsite

2016年11月6日2530

hdu5912.Fraction

计算连分数的答案,直接模拟即可

hdu5914.Triangle

问长度1到n的线段,至少要去掉多少,使得剩下的线段无法构成三角形

\(1\leq n\leq 20\)

斐波那契数列,手算完打表

hdu5916.Harmonic Value Description

定义全排列的权值为相邻两个数的gcd,求1到n的所有全排列中第K小的排列

\(1\leq 2k \leq n\leq 10000\)

容易发现,第k大的全排列的权值为n-2+k

构造方式是将偶数从小到大的k个偶数依次放在数列最前面

hdu5917.Instability

给一个n,m的无向图,求稳定子图的个数。稳定子图定义为包含三元环或三个点的独立集为子图的图。

\(1\leq n\leq 50\)

根据ramsey定理,6个点以上的子图都是稳定子图

所以搜索5个点以下的情况即可

hdu5918.Sequence I

分别给出长度为n,m的正整数序列a,b,问a中有多少个起点q,满足从q开始,间隔为p,长度为m的子序列能和b匹配

\(1\leq n,m,p\leq 100000\)

将a拆成p个子序列,每一个和b做一次kmp

HDU 5919.Sequence II
给一个长为n的数列,m次查询,每次查询一个区间中每一种数在区间中第一次出现的位置的中位数
强制在线 \(1\leq n,m\leq 2*10^5\)
设区间内有K个不同数字,二分一个mid,使得l到mid中恰好有K个不同数字
查询\([l,r]\)中不相同的数字个数可以记录一下每个数字下一次出现的位置\(nxt_i\),问题转化成该区间有多少个nxt大于r
用主席树实现

HDU 5920.Ugly Problem
给一个数字s,要求构造n个回文数的和等于s,n不超过50
\(1\leq s\leq 10^{1000}\)
每次构造一个不超过S的最大回文数

hdu5921.Binary Indexed Tree

求[0,n]中的数组成的所有有序二元组(x,y)的cost的和,cost(x,y)定义为,把x不断减去二进制下的末尾的1,把出现过的数放到集合\(S_x\),y做相同操作得到集合\(S_y\),cost是两集合的并减去交

\(1\leq T\leq 10000,1\leq n\leq 10^{18}\)

令f(x)为x二进制下1的个数

\(ans=\sum\sum\{[f(i)+f(j)]-2f(lcp(i,j))\}\)

分别在二进制下计算两部分对答案的贡献