[合集]简单题选做
大家有什么有趣的题目欢迎推荐给我啊!
洛谷博客如果不支持某些 Latex 的渲染我也没治啊。
[Luogu4318]完全平方数
小 X 自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。
这天是小 X 的生日,小 W 想送一个数给他作为生日礼物。当然他不能送一个小 X 讨厌的数。他列出了所有小 X 不讨厌的数,然后选取了第 K 个数送给了小 X。小 X 很开心地收下了。
然而现在小 W 却记不起送给小 X 的是哪个数了。你能帮他一下吗?
K\leq 10^9
考察
Sol 1
发现
所以就考虑先二分,二分完了求一下 >mid
。考虑这个东西怎么求。发现根据容斥,可以知道应该是「有
另一方面,考虑对着每个不含平方因子的数
原理是,根据
这东西可以直接
顺便记录一个很绝的 idea:
Sol 2
根据
然后这东西可以直接杜教筛。于是复杂度就变成了
总结
其实这个东西一定程度上证明了
这其实是可以反演出来的。考虑对左边进行变形,令
其中第三个等号是借助了
这似乎是某次听课听来的内容…但是当时并没有整理这个。想来已经是远古时期的回忆了。
[UVA1614]Hell on the Markets
给出一个数列
\{a_n\} ,保证\forall i, 1\leq a_i\leq i 。求是否可以分成相等的两半,并给出方案。
考虑一个引理。如果
那么综上,在判断
[HNOI2011]数学作业
给定正整数
n,m ,要求计算\text{Concatenate}(n) \bmod \ m 的值,其中\text{Concatenate}(n) 是将1 \sim n 所有正整数 顺序连接起来得到的数。
…考虑递推,那自然是
[Luogu5110]块速递推
求这个数列第 $n$ 项模 $10^9+7$ 的值,一共有 $T$ 组询问。 $1\leq T\leq 5\times 10^7,1\leq n\leq 10^{18}$ 。
朴素的矩乘是
于是考虑预处理一点东西。比较常见的方法当然就是分块来做,预处理
注意到可以借助扩展欧拉定理
[USACO13JAN]Seating G
有一排
n 个座位,m 次操作。A操作:将
a 名客人安置到最左的连续a 个空位中,没有则不操作。L操作:
[a,b] 的客人离开。求A操作的失败次数。
这…大概就是维护区间最长连续和然后再直接线段树上二分吧…发现自从领悟了线段树上二分之后,好多奇怪的线段树题也就都这么回事了…
[UVA1620] Lazy Susan
现在有一个大转盘,上面有
n 个珠子,分别写有1\sim n 之间的正整数。给出这些珠子的排列方式,现在你可以每次翻转连续的四个珠子。问你至少要进行几次操作,才能将这个转盘上的珠子变成
1,2,…,n-1,n 的排列方式。
感觉还是比较有意思的题目?虽然是个结论题 233
首先考虑考虑序列中某段长度为
(1) 该子段无论怎么重排,对
(2) 该子段内部,顺序与逆序两种排布的逆序对数量之和为
(3) 根据
回归到本题,可以知道每次逆序对的变化量肯定是
这题原本的数据范围是
[APIO2012]派遣
在这个帮派里,有一名忍者被称之为 Master。除了Master以外,每名忍者都有且仅有一个上级。为保密,同时增强忍者们的领导力,所有与他们工作相关的指令总是由上级发送给他的直接下属,而不允许通过其他的方式发送。
现在你要招募一批忍者,并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水,同时使得支付的薪水总额不超过你的预算。另外,为了发送指令,你需要选择一名忍者作为管理者,要求这个管理者可以向所有被派遣的忍者发送指令,在发送指令时,任何忍者(不管是否被派遣)都可以作为消息的传递人。管理者自己可以被派遣,也可以不被派遣。当然,如果管理者没有被排遣,你就不需要支付管理者的薪水。
你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平,其中每个忍者的领导力水平也是一定的。
写一个程序,给定每一个忍者
i 的上级B_i ,薪水C_i ,领导力L_i ,以及支付给忍者们的薪水总预算M ,输出在预算内满足上述要求时顾客满意度的最大值。简化版题面:给定一棵树,求
\max_{u\in T}\{L_u\cdot t_u\} 其中设
s 是以u 为根的子树中的某个点集,\mathrm{card} 表示集合的元素个数, 则t_u=\max_s\{\mathrm{card}(s)\cdot [ \sum_{i\in s} c_i\leq m]\}
读题读半天系列x
…发现是暴力,暴力选每个点当根,然后拿一个支持快速合并的数据结构对子树内的点进行合并,选出重量最小的那几个即可。注意到暴力合并的话似乎是要二分…这样一般而言复杂度就变成两个
[Luogu1858]多人背包
01背包的前
k 优解。
考虑暴力做并不简单,一个直观的想法就是再记一维
[SCOI2016]萌萌哒
一个长度为
n 的大数,用s_1s_2s_3 \cdots s_n 表示,其中s_i 表示数的第i 位,s_1 是数的最高位。告诉你一些限制条件,每个条件表示为四个数,l_1,r_1,l_2,r_2 ,即两个长度相同的区间,表示子串s_{l_1}s_{l_1+1}s_{l_1+2} \cdots s_{r_1} 与s_{l_2}s_{l_2+1}s_{l_2+2} \cdots s_{r_2} 完全相同。求本质不同的大数个数。
(以下默认并查集的复杂度是
考虑暴力做当然是对每个位置开一个并查集,然后对于每个修改暴力 for
过去,这样最后答案就是
考虑二进制拆分。对每个位置
总复杂度
[SCOI2010]生成字符串
lxhgww 最近接到了一个生成字符串的任务,任务需要他把
n 个1 和m 个0 组成字符串,但是任务还要求在组成的字符串中,在任意的前k 个字符中,1 的个数不能少于0 的个数。现在 lxhgww 想要知道满足要求的字符串共有多少个,聪明的程序员们,你们能帮助他吗?
这…理论上如果没有个数限制的话就是卡特兰数了吧。
考虑一个转化,从
考虑怎么算这两部分。发现本质上从
[SP19148]Kill them All
$1\leq n\leq 10^6$ 。
回顾历史的时候顺便发现了这道题…
大概就是上个题把 Digo
干掉,那么就变成了从
其中第一个 Digo
干掉的方案数。那么可以知道…这个式子里面前面的都被消掉了,最后只剩一个
[UVA11149]Power of Matrix
给定整数
k 和一个n 阶矩阵A ,求A+A^2+A^3+A^4+\cdots+A^k
这题其实有两种做法。一种做法是
Sol 1
考虑对着这个找规律(雾),大概是考虑分块做,发现原来的式子可以写成:
那么就可以预处理再做了。这样复杂度是
不过既然分块可以,那倍增应该也可以。具体的,可以这么化:
那么这样就可以先预处理出
Sol 2
考虑直接对所有矩阵的和进行递推。计
其中
发现它可以这么转移:
其中
[SDOI2011]打地鼠
打地鼠是这样的一个游戏:地面上有一些地鼠洞,地鼠们会不时从洞里探出头来很短时间后又缩回洞中。玩家的目标是在地鼠伸出头时,用锤子砸其头部,砸到的地鼠越多分数也就越高。
游戏中的锤子每次只能打一只地鼠,如果多只地鼠同时探出头,玩家只能通过多次挥舞锤子的方式打掉所有的地鼠。你认为这锤子太没用了,所以你改装了锤子,增加了锤子与地面的接触面积,使其每次可以击打一片区域。如果我们把地面看做
m\times n 的方阵,其每个元素都代表一个地鼠洞,那么锤子可以覆盖r\times c 区域内的所有地鼠洞。但是改装后的锤子有一个缺点:每次挥舞锤子时,对于这的区域中的所有地洞,锤子会打掉恰好一只地鼠。也就是说锤子覆盖的区域中,每个地洞必须至少有1 只地鼠,且如果某个地洞中地鼠的个数大于1 ,那么这个地洞只会有1 只地鼠被打掉,因此每次挥舞锤子时,恰好有r\times c 只地鼠被打掉。由于锤子的内部结构过于精密,因此在游戏过程中你不能旋转锤子(即不能互换r 和c )。你可以任意更改锤子的规格(即你可以任意规定
r 和c 的大小),但是改装锤子的工作只能在打地鼠前进行(即你不可以打掉一部分地鼠后,再改变锤子的规格)。你的任务是求出要想打掉所有的地鼠,至少需要挥舞锤子的次数。Hint:由于你可以把锤子的大小设置为
1\times 1 ,因此本题总是有解的。
以下是翻车现场,这题根本没有「行列无关」的性质:
一道十分经典的行列无关技巧普及题目。但这题行列无?关比较的深刻。
考虑如果暴力枚举的话,复杂度大概是枚举
r\times c 之后再一个一个打,这样复杂度是O(n^6) ,实现的好一点就可以O(n^4\log^2 n) 。但是,如果这题满足行列无关的话,就可以r 和c 分别枚举。准确来说,对于另一维设为1 ,那么可以只去找这一维的最大值。考虑这么做判断的复杂度就是O(n^3) ,枚举的复杂度是O(n) 。那么最后总复杂度就是O(n^4) 。那么唯一的问题在于如何证明行列无关在这题里面是对的。考虑对于所枚举的锤子大小所覆盖的某个区域,其中有两个点
(a,b) 和(c,d) ,不同行也不同列,但是可以知道(a,b) 和(c,b) 的确定关系,(c,d) 和(c,b) 的确定关系。即我断言,如果(a,b) 和(c,b) 满足同时合法,(c,d) 和(c,b) 也同时合法,那么这三个点就可以同时合法,反之则不可以。考虑这个断言为什么合理。发现每次如果以
(c,b) 为量度去砸,那么(c,d) 和(a,b) 被砸的次数都只会与(c,b) 的地鼠数量有关,因为(c,b) 必须被精确砸完……
编不下去了,就当记结论了
然后就是一个二维差分,然后就没了。
[Luogu1357]花园
小 L 有一座环形花园,沿花园的顺时针方向,他把各个花圃编号为
1 \sim n 。花园1 和n 是相邻的。他的环形花园每天都会换一个新花样,但他的花园都不外乎一个规则:任意相邻
m 个花圃中都只有不超过k 个 C 形的花圃,其余花圃均为 P 形的花圃。请帮小 L 求出符合规则的花园种数对
10^9+7 取模的结果。
发现一共只有两种方格,并且转移只跟
那么显然这东西可以 dfs
预处理出来。然后发现这东西类似于 floyd
的转移矩阵,就可以快速幂了。考虑由于花圃是个环,那么合法的方案就是
void dfs(int x, int u, int s){
if (x == m + 1){
ok[s] = 1 ;
ans.ma[s >> 1][s] = 1 ;
if (u == k && ~s & 1) return ;
ans.ma[(s >> 1)|st[m]][s] = 1 ; return ;
}
dfs(x + 1, u, s) ;
if (u >= k) return ;
dfs(x + 1, u + 1, s | st[x]) ;
}
int main(){
cin >> n >> m >> k ;
for (int i = 1 ; i <= m ; ++ i)
st[i] = (1 << i) >> 1 ;
dfs(1, 0, 0) ; ans = expow(ans, n) ;
for (int i = 0 ; i <= 1 << m ; ++ i)
if (ok[i]) add(res, 1ll * ans.ma[i][i], P) ;
cout << res << '\n' ; return 0 ;
}
[UVA11134]Fabled Rooks
在一个
n\times n (1\leq n\leq 5000 )的棋盘上放置n 个车,每个车都只能在给定的一个矩形(x_{l_i},x_{r_i},y_{l_i},y_{r_i} ) 里放置,使其n 个车两两不在同一行和同一列,判断并给出解决方案。
一道(真正)考察了行列无关知识的题目。
考虑放每个车时行与列显然是无关的,所以就可以分开做。那就是给定一堆区间,每个区间内选一个点使之不被放在同一个位置。贪一波就完了。
[NOI2005]瑰丽华尔兹
舞厅是一个
N 行M 列的矩阵,矩阵中的某些方格上堆放了一些家具,其他的则是空地。钢琴可以在空地上滑动,但不能撞上家具或滑出舞厅,否则会损坏钢琴和家具,引来难缠的船长。每个时刻,钢琴都会随着船体倾斜的方向向相邻的方格滑动一格,相邻的方格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法:如果不施魔法,则钢琴会滑动;如果施魔法,则钢琴会原地不动。艾米丽是个天使,她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行的路程尽量长,这样 1900 会非常高兴,同时也有利于治疗托尼的晕船。但艾米丽还太小,不会算,所以希望你能帮助她。
考虑最朴素的
[BalticOI2008]Elect
现在希望你找出一种方案,你选中的党的席位数要大于总数的一半,并且联合内阁的席位数越多越好。 对于一个联合内阁,如果某个政党退出后,其它党的席位仍大于总数的一半,则这个政党被称为是多余的,这是不允许的。 求最大席位并构造一组解。 $1\leq n\leq 300,1\leq m\leq 10^5$ 。
大概是长个经验?
发现倒着贪心并不是对的…虽然观察数据范围发现
但是发现如果从大到小排完序之后再背包,当前加进去的东西一定是最小的。此时如果出现把这个东西拿出来,剩下的都一定比这个大。所以不难理解这么更新的正确性。
考虑如何记录方案。可以对于每种权值都开一个 bitset
,对于每种权值,第一次更新的时候顺便更新 bitset
(根据单调性这样一定是最合法的那个)。那么最后的复杂度就是
int f[MAXM] ;
int half, sum ;
int i, v, ans, n ;
bitset <MAXN> b[MAXM] ;
pair<int,int> base[MAXN] ;
inline bool cmp(pair<int,int> a, pair<int,int> b){ return a.fr > b.fr ;}
int main(){
cin >> n ; f[0] = 1 ;
for(i = 1; i <= n ; i ++){
scanf("%d", &base[i].fr) ;
sum += base[i].fr, base[i].sc = i ;
}
sort(base + 1, base + n + 1, cmp) ; half = sum >> 1 ;
for(i = 1; i <= n ; i ++){
for (v = sum ; v >= base[i].fr ; v --){
if (!f[v] && f[v - base[i].fr])
b[v] = b[v - base[i].fr], b[v].set(base[i].sc), f[v] = 1 ;
if (v > half && f[v] && v - base[i].fr <= half) ans = max(ans, v) ;
}
}
cout << b[ans].count() << '\n' ;
for (int i = 1 ; i <= n ; ++ i)
if (b[ans][i]) cout << i << ' ' ;
}
[LuoguP1531]鬼子进村
县城里有
n 个用地道相连的房子,第i 个只与第i-1 和第i+1 个相连。这时有m 个消息依次传来:
若消息为
D x
:鬼子将x 号房子摧毁了,地道被堵上。若消息为
R
:村民们将鬼子上一个摧毁的房子修复了。若消息为
Q x
:有一名士兵被围堵在x 号房子中。李云龙收到信息很紧张,他想知道每一个被围堵的士兵能够到达的房子有几个。
降智题,说实话我第一眼觉得那必然是 LCT;又觉得可达性不好统计,然后就懵了 1min
其实是有两种方法的:
Sol 1
考虑暴力线段树维护,修复和拆毁都是单点修改。查询的话自然是查询一个点左边第一个
Sol 2
发下有一个性质并没有很好利用起来(虽然本身就是一个很没用的性质)。每次删除的点一定是之前插入的点。所以考虑对于所有炸毁的点维护一棵平衡树,以
……还有要注意可能本身就被炸了,判一下就好了。这种方法也是
[AT3741] String Problem
给出两个字符串S和T. 通过执行以下操作,判断是否可以将字符串S转换为字符串T.
- 操作 A:删除S中任意位置的字母 A .
- 操作 B:在S的任意位置插入一个字母 B .
S 和 T 的字符都为大写字母,并且 S 和 T 的长度
\le 1000 。
……其实是水题,不过发生了一些奇妙的事情,然后就打算整理一下我的做法?感觉其他人的做法都一毛一样…
大概就是首先根据样例解释的提示,可以想出一个「先加 B 再删 A」的思路,然后发现前半部分就是一个魔改的 LCS,后半部分就只需要记录一下最少要用多少个 B,看看 s 比 t 多的那些字符是否全是 A 就好了。
[Contest Hunter5105] Cookies
圣诞老人共有
m 个饼干,准备全部分给n 个孩子。每个孩子有一个贪婪度,第i 个孩子的贪婪度为g_i 。如果有a_i 个孩子拿到的饼干数比第i 个孩子多,那么第i 个孩子会产生g_i\times a_i 的怨气。给定n 、m 和序列g ,圣诞老人请你帮他安排一种分配方式,使得每个孩子至少分到一块饼干,并且所有孩子的怨气总和最小。
首先不难想到要按照
考虑对于一个状态
注意到次数由于钦定了后
如果让第
[UVA1621] Jumping Around
一条
[0,n] 数轴,一开始在0 处。每次可以选择向左/右以步长为1/2/3 跳到对应位置,分别只能最多跳a,b,c 次,保证a+b+c=n,a>3,b>3,c>3 。求构造一种跳的方案,使得跳到1\sim n 每个位置恰好1 次。
比较有趣的构造题吧…也是化归子问题的构造技巧。
考虑如果
如果
(1)如果
(2)如果
(3)如果
[Luogu3795]钟式映射
设集合
N=M=\left\{x|x\in N_+,x\leq k,k\in N_+\right\} 。设f 为N 到M 的映射。求满足f[f(x)]=x 的不同的映射f 的个数。
说实话…我遇到这种题就会战术后仰然后不会…类似于什么置换啊、复合映射啊,我就蒙圈的很。
考虑新加入一个元素。对于一个
然后就递推即可。
感觉这个式子本质上和错排可能会有点类似。考虑一个
感觉递推思想方面是有类似的吧…自己还是…太不聪明了啊
别找那些理由,就是泥萌的不努力!
[UVA1451]Average
给定一个长度为
n 的01 串,选一个长度至少为L 的连续子串,使得子串中数字的平均值最大。如果有多解,子串长度应尽量小;如果仍有多解,起点编号尽量小。序列中的字符编号为1 ~n ,因此[1,n] 就是完整的字符串。
又到了复习斜率优化的时间了,斜率优化,常读常新。
考虑前缀和一下就转化成了对每个
[HNOI2008]玩具装箱
P 教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。
P 教授有编号为
1 \cdots n 的n 件玩具,第i 件玩具经过压缩后的一维长度为C_i 。为了方便整理,P教授要求:
在一个一维容器中的玩具编号是连续的。
同时如果一个一维容器中有多个玩具,那么两件玩具之间要加入一个单位长度的填充物。形式地说,如果将第
i 件玩具到第j 个玩具放到一个容器中,那么容器的长度将为x=j-i+\sum\limits_{k=i}^{j}C_k 。制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为
x ,其制作费用为(x-L)^2 。其中L 是一个常量。P 教授不关心容器的数目,他可以制作出任意长度的容器,甚至超过L 。但他希望所有容器的总费用最小。对于全部的测试点,
1 \leq n \leq 5 \times 10^4 ,1 \leq L \leq 10^7 ,1 \leq C_i \leq 10^7
大概是斜率优化板板题?考虑方程:
然后考虑拆一下,并且令
那么证明斜率优化可行的基本讨论就是找一个
若
设
也就说当这个式子满足的时候,存在
所以对此可以直接采用斜率优化。注意到
[HAOI2008]硬币购物
共有
4 种硬币。面值分别为c_1,c_2,c_3,c_4 。某人去商店买东西,去了
n 次,对于每次购买,他带了d_i 枚i 种硬币,想购买s 的价值的东西。请问每次有多少种付款方法。
比较常规的容斥题目。考虑由于硬币个数的限制,大概是要做一个多重背包计数,这样复杂度是
考虑更加正经一点的做法。发现虽然硬币个数很多,但是种类很少,同时发现不限制使用次数的方案数是很好计算的,于是考虑容斥。
但是发现背包模型在计算方案时,状态本身具有简并性。 也就是对于任何一个状态
于是容斥一下即可。复杂度
[CF933A]A Twisty Movement
给定一个序列 A,你可以翻转其中的一个区间内的数,求翻转后的序列的最长不下降子序列的长度。(
|A|\le 2000,1\le a_i \le 2 )
自己想了一个暴力做法。大概是对于每个位置
……但其实是可以直接暴力
当然这题也存在一个闲的胃疼的高级做法,就是线段树上分别维护
emmm 启发了一个 Idea 但是自己不会做,惨惨。
[LuoguP6435] 「EZEC-1」数列
给你一个正整数
n ,有数列\{a_n\}:1,2,3,...,n 。分别求相邻两项中左边一项的
a 倍与右边一项的b 倍的和再加上c ,得到一个有n-1 项的新数列:对这个新数列重复上述操作得到若干数列,最后的数列只有一项,求最后这个项对 $p$ 取模的值。 $1\le n\le 10^{18}$,$1\le p \le 10^{14}$,$1 \le a,b\le 10^9$,$0\le c \le 10^9$ 。
…比较有意思的题目?本质上数学题。
考虑直接递推。设
那么也就是
考虑高中数学技巧
那么可以通过差分得到
发现前面很好算,后面是一个等比数列的形式。由于不保证
然后就可以分治做下去了。复杂度
[UVA1611] Crane
输入
n 个数,要求把它变成升序排列,每次操作都可以交换一个长度为偶数的区间的左右两半。要求操作数\leq 2n 。
大概是一道降智题…
考虑一个逐步缩小问题规模的思想。元素从小到大考虑,每次把当前未考虑的数列中最小元素
[LuoguP5007] DDOSvoid 的疑惑
给定一棵以 1 为根的有根树,定义树的一个毒瘤集为一个集合,并且集合中任意两个元素之间不存在祖先与后代关系。
定义一个毒瘤集的毒瘤指数为集合内所有元素的价值之和
要求给定树的所有毒瘤集的毒瘤指数之和,答案对
10^8+7 取模。但这个问题太难了,所以我们考虑化简。
因为点的编号跟它毒瘤指数密切相关,所以我们将会再给出一个整数 T,T = 1 表示 i 号点的毒瘤指数为 i,T = 0,表示所有点的毒瘤指数都是 1。
懵了半天还是不会做……
不难发现这个可以以子树为状态来转移。然后考虑如何将孩子的贡献转移到根,发现需要处理的本质上是合并两棵树的所有毒瘤集。假设两棵树的毒瘤集权值和分别为
那么不难知道要记录一下各自树中毒瘤集的个数。于是考虑从下向上
复杂度
UVA1407 Caves
给定一棵
n 个节点、边带权的树。q 次询问,每次给定一个x ,询问从根出发走多少个点,满足走过的边权和<x 且经过的点最多。点可以重复经过,但只会被计算一次。
一个比较基础的思想是背包,但这时空显然不是背包能做的。这个地方考虑,点数只有
其中第二个转移表达的是这条路径的终点是否在以
发现
BZOJ4160 Exclusive Access 2
给出
n 个点m 条边的无向图,定向得到有向无环图,使得最长路最短。
大概是
令
(X,≤) 是一个有限偏序集,并令m 是反链的最大长度。则X 可以被划分成m 个但不能再少的链。 即:链的最少划分数= 反链的最长长度.。
同时也存在对偶定理:
令
(X,≤) 是一个有限偏序集,并令r 是其最长链的大小。则X 可以被划分成r 个但不能再少的反链。
也就是:
偏序集能划分成的最少的全序集个数等于最大反链的元素个数 。
其中「全序集」指的是这样的一个偏序集
换言之,假设给原图定向,那么根据 dilworth 定理,最长链的长度就是最小的独立集的大小,其中「独立集」的定义为原无向图中距离大于
于是这东西就可以状压了。
POJ3735 Training little cats
现在给你一个长度为
n 的序列,开始这个序列都是 0。对这个序列一共有三种操作:操作 1:输入一个
x ,把x 位置上的值+1 。操作 2:输入一个
x 一个y ,交换x ,y 位置上的值。操作 3:输入一个
x ,把x 位置上的值变成0 。我们接着对这个序列进行
k 次操作。我们把这
k 次操作叫做一轮,现在这个k 个操作进行了m 轮。输出最后的序列。
…矩阵快速幂神题 sto
考虑一开始把这个空的序列记作一个
那么考虑由于
考虑三个操作,以下默认右乘转移矩阵
1、位置
考虑对于
考虑如何使得乘上这个矩阵的某个变形之后,位置
2、交换位置
还是考虑
3、位置
…
注意到上面都是单独进行一个操作的情况。如果出现多个操作冗杂在一起,那么一方面可以建
注意到可以把这
但其实
哦,poj 上多组数据,那没事了(
UVA1437 String painter
给定一个串
s 和一个目标串t 。每次可以将s 的连续一段刷成一个同一个字符。求最少多少次操作使得s 变成t 。
一开始的错误思路:考虑如果两个对应位置的字符相同,那么就可以把这对字符删掉不需要管,剩下的
写了一发之后发现挂了。理了理思路,发现首先有个错误的点,即不一定「删掉不管」是最优的,可能相同的字符会先被覆盖然后再涂上。所以这个思路本来就是错的。之后再考虑,以
所以设 chkmax(g[i], g[i - 1])
即可。为了保证转移全面,直接枚举断点转移即可。
for (int i = 1 ; i <= n ; ++ i) f[i][i] = 1 ;
for (int len = 1 ; len < n ; ++ len)
for (int i = 1 ; i <= n - len ; ++ i){
j = i + len ; f[i][j] = f[i][j - 1] + 1 ;
for (int k = i ; k <= j - 1 ; ++ k)
if (t[j] == t[k])
chkmin(f[i][j], f[k + 1][j - 1] + f[i][k]) ;
}
for (int i = 1 ; i <= n ; ++ i){
g[i] = f[1][i] ;
chkmin(g[i], s[i] == t[i] ? g[i - 1] : P) ;
for (int k = 1 ; k <= i ; ++ k)
chkmin(g[i], g[k - 1] + f[k][i]) ;
}
//为什么总是学不会?
UVA1427 Parade
有一个由
n+1 条横向路和m+1 条竖向路构成的网格图,每条横向路有一个高兴值和经过的时间。现在想从网格的最下方走到最上方,求能得到的最大的高兴值是多少。
走路有限制:不能多次经过同样的路,也不会从下往上走。另外,在每条横向路上所花的时间不能超过
k 。
一开始想的是直接暴力
后来想了想,大概可以定义一个比较靠谱的状态。
好像很简单的样子…但是不能一眼 A 就是罪过吧…
UVA11795 Mega Man's Mission
洛克人最初只有一种武器 “Mega Buster”(这种武器可以消灭特定的一些机器人),你需要按照一定的顺序消灭 n 个其他机器人。每消灭一个机器人你将会得到他的武器(也可能没有得到武器),而这些武器可以消灭特定的机器人。你的任务是计算出消灭所有机器人的顺序总数。注意:一个机器人的武器可能可以消灭自己,但这对最终答案没有影响,因为必须先消灭这个机器人才能够得到他的武器。
其实是很水的题…只是记录一个坑点。遇到这种求顺序总数的时候,我大脑总会选择性宕机…准确来说,显然这题是要预处理一个
这也反映了自己并没有理解认真理解
菜成一坨,GGGGGGGGG。
UVA1625 Color Length
输入两个长度分别是
n 和m 的颜色序列,要求按顺序合并成同一个序列,即每次可以把一个序列开头的颜色放到新序列的尾部。记
L(c) 为关于颜色c 和合并之后的排列的一个函数,定义如下:L(c)=\max_{p\in[1,n+m]\cap \mathbb{Z_+}}\{p~|~color(p)=c\} - \min_{p\in[1,n+m]\cap \mathbb{Z_+}}\{p~|~color(p)=c\} 你的任务是找一种合并方式,使得所有
L(c) 的总和最小。
考虑朴素的状态当然是
考虑一个 trick,提前计算贡献。即虽然其余的都很麻烦,但是可以比较方便地知道有哪些颜色一定没有合并完。所以可以每次转移时,计算还没有合并完的贡献。这样做本质上是把贡献分摊到每个元素上面。因为考虑这种转移,对于每个终止状态,并不关心前面代价转移的形式,只关心代价转移的结果。
于是就预处理一个
UVA1218 Perfect Service
一个网络中有
n 个节点,由n-1 条边连通,每个节点是服务器或者客户端。如果节点u 是客户端,就意味着u 所连接的所有点中有且仅有一台服务器。求最少要多少台服务器才能满足要求。
这题比较水,主要是整理一下,给自己提个醒。如果设
于是考虑因为难以记儿子,所以记父亲。
注意到,其中
UVA12099 The Bookcase
有
n 本书,每本书有一个高度h_i 和一个宽度w_i 。 现在要构建一个3 层的书架,你可以选择将n 本书放在书架的哪一层。设3 层高度(每层书的最大高度)之和为h ,书架总宽度为w ,要求h×w 尽量小。
本质上是要最优化两样东西,宽度和高度。所以不妨让其中一个变得有序,所以考虑先按照
考虑如何设计状态。发现如果某一层有最高的那本书,那么无论怎么放书,这一层的高度都不会再受影响;同时,把每一层的高度和宽度都记下来是没有必要的,于是可以记某一维为某个确切数值时另一维的最小值。具体的,
考虑转移。首先应该定一个顺序,比如第二层高度应该大于第三层,那么此时转移有:
其中第三个决策当且仅当第二层已经有了一本书。
考虑这样
1、
2、
其中第一可行性个比较好理解,第二个最优性剪枝是在说,因为
这么一波剪枝之后似乎就跑的飞快了…似乎是要滚一下第一维的样子。
大概转移and初始赋值这些会有一点细节的样子吧。
UVA10559 Blocks
有
n 个带有颜色的方块,没消除一段长度为x 的连续的相同颜色的方块可以得到x^2 的分数,让你用一种最优的顺序消除所有方块使得得分最多。
大概是比较神仙的
第一感觉肯定就是
于是这就启发(个鬼,这怎么可能想得出来)要多记一维状态
复杂度的话,状态是 我觉得应该是 …剪枝是要剪的,每次只关心和
好的,我又重新写了一下测了一下,觉得应该把访问记忆化结果也算 中间可执行文件还一度被系统给 kill 掉了 。
然后…然后我就加了一个好像很牛逼的剪枝,大概就是判断一下 但似乎应该还是过不了,因为极限可以有15组数据,每组都这个速度肯定跑不进3s鸭。
然后发现这个某个区间是否同色可以预处理,然后就预处理了一下,发现一组快的话只需要
然后又改了一下,发现可以稍微贪一下,「枚举每次有多少个块和右端点一起转移走」显然是最大的那个快最好了。但这并没有快…
删了点重复计算和冗杂判断…发现大概是稳定在
…发现自己是个弟弟,如果要把右边和左边合并的话,那肯定是全都一起合并最优。所以现在大概是真正的
//版本1 最大点 400ms
bool check(int l, int r){
for (int i = r, j = lst[r] ; i >= l ; j = lst[j], i = lst[i])
if (i != j + 1) return 0 ; return 1 ;
}
int solve(int l, int r, int t){
if (l > r) return f[l][r][t] = 0 ;
if (f[l][r][t]) return f[l][r][t] ;
if (l == r) return f[l][r][t] = (t + 1) * (t + 1) ;
if (check(l, r)) return f[l][r][t] = (t + r - l + 1) * (t + r - l + 1) ;//剪枝 1
for (int i = r ; i >= l && base[i] == base[r] ; -- i){
chkmax(f[l][r][t], solve(l, i - 1, 0) + (t + r - i + 1) * (t + r - i + 1)) ;
for (int j = lst[i] ; j >= l ; j = lst[j])
if (base[j] == base[r])
chkmax(f[l][r][t], solve(j + 1, i - 1, 0) + solve(l, j, r - i + 1 + t)) ;
}
return f[l][r][t] ;
}
//版本2 最大点 320- ms
int solve(int l, int r, int t){
if (l > r) return f[l][r][t] = 0 ;
if (f[l][r][t]) return f[l][r][t] ;
if (l == r) return f[l][r][t] = (t + 1) * (t + 1) ;
if (g[r] <= l) return f[l][r][t] = (t + r - l + 1) * (t + r - l + 1) ;
chkmax(f[l][r][t], solve(l, g[r] - 1, 0) + (t + r - g[r] + 1) * (t + r - g[r] + 1)) ;
for (int i = r ; i >= g[r] ; -- i){
register int pq = t + r - i + 1 ;
for (int j = lst[i] ; j >= l ; j = lst[j])
chkmax(f[l][r][t], solve(j + 1, i - 1, 0) + solve(l, j, pq)) ;
}
return f[l][r][t] ;
}
int main(){
cin >> T ; Q = T ;
while (T --){
n = qr() ;
memset(f, 0, sizeof(f)) ;
memset(buc, 0, sizeof(buc)) ;
memset(lst, 0, sizeof(lst)) ;
printf("Case %d: ", Q - T) ;
for (int i = 1 ; i <= n ; ++ i)
lst[i] = buc[base[i] = qr()], buc[base[i]] = i ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = i ; j >= 1 ; -- j)
if (base[i] == base[j]) g[i] = j ; else break ;
cout << solve(1, n, 0) << '\n' ;
}
}
//版本3 200- ms 左右 此时根本不需要判整段是否相同
int solve(int l, int r, int t){
if (l > r) return f[l][r][t] = 0 ;
if (f[l][r][t]) return f[l][r][t] ;
if (l == r) return f[l][r][t] = (t + 1) * (t + 1) ;
//if (g[r] <= l) return f[l][r][t] = (t + r - l + 1) * (t + r - l + 1) ;
chkmax(f[l][r][t], solve(l, g[r] - 1, 0) + (t + r - g[r] + 1) * (t + r - g[r] + 1)) ;
for (int j = lst[g[r]] ; j >= l ; j = lst[j])
chkmax(f[l][r][t], solve(j + 1, g[r] - 1, 0) + solve(l, j, (t + r - g[r] + 1) )) ;
return f[l][r][t] ;
}
UVA1380 A Scheduling Problem
给定一棵树,pks把其中某些边改成了有向边。现在要求把所有边都改成有向边,求最长链的长度最小值。
考虑首先,对于这种带方向性的计算链长,在树上一般都是要分成两部分做。于是不妨令
1、如果对于某个
那么就是比较朴素的转移。
2、如果存在某个
那自然是再分类讨论这条边重定向成
考虑观察一点更深刻的性质。发现如果对于某个
那么就可以考虑,一开始用 vector<int>
将所有无向边连接的儿子给 push_back
进来。对于
假如
\rm G 是一棵树,那么需要的天数是k 或k+1 。k 满足:k 是\rm G 中所有链中一条链能包含的最多顶点数。链的定义:在一条路径
P=(x_1, x_2, …, x_k) 中 ,对于任意的i=1,2,…,k-1 ,总有一条从x_i 指向x_{i+1} 的有向边。
但其实这个定理也可以没有用。因为只需要在外层套一个二分就好了。·
这提示我们只关心最长链是否
注意一个问题,由于这个状态记录的不是子树的最大值(当然也可以多记一个这个),所以如果中有以某点为根,路径长度
bool read_in(){
int u, v ; char w ;
res = cnt = ans = 0 ;
bool ret = 0 ; n = 0 ;
memset(fa, 0, sizeof(fa)) ;
memset(head, 0, sizeof(head)) ;
while (std :: cin >> u){
if (!u) return ret ;
ret = 1, n = std :: max(u, n) ;
while (scanf("%d%c", &v, &w) && v){
fa[v] = u ; n = std :: max(n, v) ;
if (w == 'd') add_e(u, v, 2), add_e(v, u, 1) ;
else if (w == 'u') add_e(u, v, 1), add_e(v, u, 2) ;
else add_e(u, v, 0), add_e(v, u, 0) ;
}
}
return ret ;
}
void dfs(int x, int fa, int len){
ans = std :: max(ans, len) ;
for (int k = head[x] ; k ; k = next(k))
if (to(k) != fa && val(k) == 2) dfs(to(k), x, len + 1) ;
}
bool comp_f(const int & x, const int & y){ return f[x] < f[y] ; }
bool comp_g(const int & x, const int & y){ return g[x] < g[y] ; }
bool do_dp(int x, int fa){
// cout << x << '\n' ;
f[x] = g[x] = 0 ;
int F, G, df, dg ;
for (int k = head[x] ; k ; k = next(k)){
if (to(k) != fa){
if (!do_dp(to(k), x)) return 0 ;
if (!val(k)) son[x].p_b(to(k)) ;
else if (val(k) > 1)
f[x] = std :: max(f[x], f[to(k)] + 1) ;
else g[x] = std :: max(g[x], g[to(k)] + 1) ;
}
}
F = f[x] ; G = g[x] ;
if (son[x].empty()) return (bool)(F + G <= ans) ;
f[x] = ans + 1 ; suf[son[x].size()] = 0 ;
std :: sort(son[x].begin(), son[x].end(), comp_f) ;
for (int i = son[x].size() - 1 ; i >= 0 ; -- i)
suf[i] = std :: max(suf[i + 1], g[son[x][i]]) ;
// debug(suf, 0, n) ;
if (F + suf[0] + 1 <= ans) f[x] = F ;
for (int i = 0 ; i < son[x].size() ; ++ i){
dg = std :: max(G, suf[i + 1] + 1) ;
df = std :: max(F, f[son[x][i]] + 1) ;
if (df + dg <= ans) f[x] = std :: min(f[x], df) ;
}
g[x] = ans + 1 ; suf[son[x].size()] = 0 ;
std :: sort(son[x].begin(), son[x].end(), comp_g) ;
for (int i = son[x].size() - 1 ; i >= -1 ; -- i)
suf[i] = std :: max(suf[i + 1], f[son[x][i]]) ;
// debug(suf, 0, n) ;
if (G + suf[0] + 1 <= ans) g[x] = G ;
for (int i = 0 ; i < son[x].size() ; ++ i){
df = std :: max(F, suf[i + 1] + 1) ;
dg = std :: max(G, g[son[x][i]] + 1) ;
if(df + dg <= ans) g[x] = std :: min(g[x], dg) ;
}
// cout << x << " " << F << " " << G << " " << f[x] << " " << g[x] << '\n' ;
return (bool)(f[x] <= ans || g[x] <= ans) ;
}
int main(){
while (read_in()){
for (int i = 1 ; i <= n ; ++ i){
if (!fa[i]) root = i ;
dfs(i, 0, 0) ; son[i].clear() ;
}
// cout << ans << '\n' ;
/*
for (int i = 1 ; i <= cnt ; ++ i)
cout << to(i) << " " << val(i) << '\n' ;
*/
res = do_dp(root, 0) ; //return 0 ;
//cout << f[i] << " " << g[i] << '\n' ;
// for (int i = 1 ; i <= n ; ++ i)
// if (f[i] + g[i] > ans){ res = 1 ; break ; }
// cout << i << " " << f[i] << " " << g[i] << '\n' ;
cout << (res ? ans + 1 : ans + 2) << '\n' ;
}
return 0 ;
}
UVA12170 Easy Climb
给出一堆山的高度
h_i ,给定一个数d 。除了h_1,h_n 之外,可以任意修改山的高度,设改完之后山的高度是h' ,那么修改的代价是|h-h'| 。求使得任意两座相邻山峰的之间高度差得绝对值不超过d 的最小修改代价。
orz又是性质题,好烦啊怎么一直不会
考虑暴力怎么做。
于是考虑一个深刻的性质。对于一个
发现可以对 map
或者 set
的滥用。
UVA1228 Integer Transmisson
在一个仿真网络中传输一个
n 比特的非负整数k 。各比特从左到右传输,第i 个比特的发送时刻为i 。每个比特的网络延迟总是为0\sim d 之间的整数(因此从左到右第i 个比特的到达时刻为i\sim i+d 之间)。若同时有多个比特到达,实际收到的顺序任意。求实际收到的整数有多少种 ,以及它们的最小值和最大值。
例如,
n=3 ,d=1 ,k=2 (二进制为010
)实际收到的整数的二进制可能是001
(1),010
(2) 和100
(4)。
最小值和最大值都显然可以贪心。考虑求方案数。比较直接的想法就是设
然后就需要洞见一个比较深刻的性质了。考虑如果希望凑出某个数
于是就可以知道,假设第
代码懒得写了
UVA1628 Pizza Delivery
你是一个披萨店的老板,有一天突然收到了
n 个客户的订单。你所在的小镇只有一条笔直的大街,其中位置
0 是你的披萨店,第i 个客户所在的位置为p_i ,如果你选择给第i 个客户送餐,他将会支付你e_i-t_i 元。其中t_i 是你到达他家的时刻。当然,如果你到的太晚,使得
e_i-t_i<0 。你可以路过他家但是不能进去给他送餐,免得他反过来找你要钱。最大化收益。
考虑对于这种每秒代价递增的问题,一般都是代价提前计算。但是这题也不是最朴素的这类问题,因为存在可以放弃某些位置的情况。
然后就是比(我)较(又)神(不)仙(会)的状态设计环节。首先是,根据题面可知不用全部送餐,所以要把「准备送餐给ta」的人数
考虑转移。发现对于一个
然后就刷表就好了?
for (int len = n - 1 ; len ; -- len)
for (int k = 0 ; k <= n - len ; ++ k)
for (int i = 1, j = i + len ; j <= n ; ++ i, ++ j){
//cout << i << " " << j << '\n' ;
for (int p = i + 1 ; p <= j ; ++ p){
chkmax(f[p][j][k + 1][0], f[i][j][k][0] + val[i] - (k + 1) * abs(pos[p] - pos[i])) ;
chkmax(f[p][j][k + 1][1], f[i][j][k][0] + val[i] - (k + 1) * abs(pos[j] - pos[i])) ;
}
for (int q = j - 1 ; q >= i ; -- q){
chkmax(f[i][q][k + 1][1], f[i][j][k][1] + val[j] - (k + 1) * abs(pos[j] - pos[q])) ;
chkmax(f[i][q][k + 1][0], f[i][j][k][1] + val[j] - (k + 1) * abs(pos[j] - pos[i])) ;
}
}
这东西看似是
UVA12105 Bigger is Better
用不超过
n 根火柴摆出一个尽量大的、能被m 整除的数。
大概是个套路?遇到这种被
然后可能是因为脑子抽了,一开始设计的状态是 __int128
也只是大概
然后又尝试用 string
,写了一会儿才意识到 string 自定义的比较函数是按字典…当然也可以写一个大整数类,似乎最多只会带一个 50 的常数。
然后考虑这么设计不行,就只能去最小化贡献,然后手动构造了。考虑
/*
int n, m ;
ll f[N][M], ans ;
int num[10] = {6, 2, 5, 5, 5, 5, 6, 3, 7, 6} ;
int main(){
while (cin >> n){
if (!n) return 0 ; ans = -1 ;
cin >> m ; memset(f, -1, sizeof(f)) ;
for (int i = 0 ; i <= 9 ; ++ i) f[i % m][num[i]] = i ;
for (int j = 2 ; j <= n ; ++ j){
for (int k = 0 ; k <= 9 ; ++ k){
for (int i = 0 ; i < m ; ++ i)
chkmax(f[((i * 10) + k) % m][j + num[k]], f[i][j] * 10 + k) ;
}
}
for (int i = 2 ; i <= n ; ++ i)
chkmax(ans, f[0][i]) ; cout << ans << '\n' ;
}
return 0 ;
}*/
int n, m, T ;
int pw[N], ans[N], f[N][M] ;
int num[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6} ;
int main(){
while (cin >> n){
if (!n) return 0 ;
memset(f, 63, sizeof(f)) ;
int l = 1, r = n, mid, res = 0 ;
printf("Case %d: ", ++ T), cin >> m ;
memset(ans, 0, sizeof(ans)) ; f[0][0] = 0 ;
for (int i = 0 ; i <= n ; ++ i)
for (int j = 0 ; j < m ; ++ j)
if (f[i][j] != 0x3f3f3f3f)
for (int k = 0 ; k <= 9 ; ++ k)
chkmin(f[i + 1][(j * 10 + k) % m], f[i][j] + num[k]) ;
for (res = n + 1 ; f[res][0] > n ; -- res) ;
int p = 0, cost = n ; pw[1] = 1 ; //cout << res << '\n';
for (int i = 2 ; i <= res ; ++ i) pw[i] = pw[i - 1] * 10 % m ;
for (int i = 1 ; i <= res ; ++ i)
for (int j = 9 ; j >= 0 ; -- j){
int t = j * pw[res - i + 1] % m ;
if (num[j] + f[res - i][((m - p - t) % m + m) % m] <= cost){
cost -= num[j] ; (p += t) %= m ; ans[i] = j ; break ;
}
}
//cout << res << '\n' ;
int q = 1 ; while (!ans[q] && q < res) ++ q ;
for (int i = q ; i <= res ; ++ i) printf("%d", ans[i]) ;
if (!res) puts("-1") ; else puts("") ;
}
return 0 ;
}
注意几个细节:
1、最后数字的位数不具有可二分性,所以还是枚举吧。
2、注意可能存在前导
总结
其实学到了许多吧?自己基础一点也不好,所以其实是把别人很早之前付出的努力,再重新付出了一遍。很遗憾,这些题目里面还是有不少无不太会做的题目…
感谢兔队的教导可以让我安心学下去:藏巧于拙,寓快于慢。只要努力,就一定会比昨天的我更优秀吧?
不过,努力和选择同样重要。希望在接下来越来越紧张的时间里面,我可以想清楚自己到底要做些什么题、要学习一些什么知识吧。加油吧!
UVA10891 Game of Sum
有一个长度为
n 的整数序列,两个游戏者A 和B 轮流取数,A 先取。每次玩家只能从左端或者右端取任意数量的数,但不能两边都取。所有数都被取走视为游戏结束,然后统计每个人取走的数之和,作为各自的得分。两个人采取的策略都是让自己得分尽可能高,并且两个人都很机智,求A 得分 -B 得分后的结果。
自己一开始想的
也就是找到与一端边界相邻,且最小的那个对方的决策(
CF493D Vasya and Chess
有一个
n\times n 的国际象棋棋盘。将白后放在(1,1) ,黑后放在(1,n) ,其余位置全都是中立的卒。 双方交替移动。白方先手。 每次移动,后(Queen)可以朝八个方向(上下左右对角线)之一移动任意格,直到碰到另外一个棋子,然后吃掉这个棋子。注意,在本题中,每次移动必须吃掉一个棋子。 当你的皇后被吃了或者你没有棋子可以吃了,就输了。 给出棋盘大小,请问哪方会赢。
发现这种对称位置决策的…一般后手都比较神必,拖,就硬拖。
考虑后手模仿先手的动作,那么如果两者之前相隔为奇数,后手可以模仿先手,发现这么做一定可以吃掉先手。如果相隔为偶数,那先手就要学聪明,移动到
UVA1099 Sharing Chocolate
给出一块长为
x , 宽为y 的矩形巧克力,每次操作可以沿一条直线把一块巧克力切割成两块长宽均为整数的巧克力(一次不能同时切割多块巧克力)。问:是否可以经过若干次操作得到
n 块面积分别为a_1, a_2, ..., a_n 的巧克力。
大力状压,
考虑化简状态。发现固定了巧克力集合
神必 uva 卡我常数。不过也需要记得,对于这种信息 break
。这个技巧确实要记住。
LA4725 Airport
机场上有两个跑道,分别为 W 和 E,每个时刻
i ,W和E都分别有a_i,b_i 架飞机进入跑道。每个跑道的飞机都按顺序从 0 开始排序,每个时刻都允许一架飞机起飞,现要求你安排起飞的飞机,使得任意时刻的飞机的最大编号最小。
这题能比较自然地想到要二分。但是问题在于二分了之后并不知道要怎么去 check。这个地方有个很妙的 idea。就是如果之前有机会要飞,可以不飞,等到什么时候攒到了
LA4094 Wonder Team
There are
n football teams participating in the competitions, each team plays twice (home and away) against each other team. Each team receives three points for a win and one point for a draw. No point is awarded for a loss.When the games are finished, teams are ranked by numbers from
1 ton according to the total points. The rank of each teamt havingp points is one plus the number of teams having more thanp points. It is possible that more than one team have the same ranks. In addition to the Champion (the first ranked team or teams), the Wonder Team is also awarded, if there exists one. The team that has absolutely the highest number of wins (absolutely means no other teams has the same number of wins), absolutely the highest number of goals scored, and absolutely the lowest number of goals conceded, is called the WonderTeam. (WonderTeam should have all these properties.)Your task is to find out the worst possible rank for the Wonder Team.
English problem, English solution!
First of all, I'd like to claim that the 2nd Constraint and 3rd Constraint is no-use, becauce we always can let WT won another team with
Let's assume
Then my train of thought ended up with this:(
Thinking more carefully, if we want to maxmize WT's rank, we have to get other teams' score as high as we can. So we can use a greedy way to construct it : Just let WT's wins actually one more than others. At the same time let WT lose its other games. Also we let other teams won WT one time, and draw with each other.
Then we can find that
And about
So we can cliam that when
CCO 2017 Rainfall Capture
Lucy 有
n 个高度为h_1,h_2,...,h_n 的柱子。她想知道,在所有可能的摆放方案中,所有可能的雨滴量(以r 为单位)是多少。柱子只能竖着摆。接雨滴的定义:满则溢。
比较神仙的 dp,对着代码啃了很久…
考虑直接求雨滴量并不好求,因为要去考虑左右两边的柱子高度。考虑对于一个排布
考虑定义
其中
考虑这个式子的意义。对于任何一个大小为
需要注意的是,这样转移一定是不包含最高那个柱子的,因为当最高的柱子为
于是最后复杂度
int s ;
int n, m ;
int base[N] ;
//bool f[N][M] ;
bitset <M> f[N] ;
int main(){
cin >> n ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = qr(), m = max(m, base[i]) ;
sort(base + 1, base + n + 1) ;
for (int i = 1 ; i < n ; ++ i)
s += base[i] ; f[0][0] = 1 ;
for (int i = 1 ; i < n ; ++ i){
for (int j = 1 ; j <= i ; ++ j)
f[j] |= (f[j - 1] << base[i]) ;
//for (int k = base[i] ; k <= n * m ; ++ k)
// f[j][k] |= f[j - 1][k - base[i]] ;
}
for (int i = s ; i <= n * m ; ++ i)
if (f[n - 1][i]) printf("%d ", i - s) ; return 0 ;
}
UVA1073 Glenbow Museum
对于一个各边长度任意且都平行于坐标轴的多边形,我们可以用这样的方式描述它:考虑它的每一个内角,如果这个内角为
90 度,那么用R 代表它;如果这个内角为270 度,那么用O 代表它。从某个点开始,按照逆时针的顺序读取R 和O ,最后得到一个由O,R 组成的字符串。给定整数
n ,问有多少个长度为n 的O,R 组成的字符串,使得有一个或以上与之对应的多边形,满足这个多边形内部有一点,可以看到这个多边形的所有内角(即,这个点与多边形所有内角顶点的连线都不与多边形的边相交)。
显然最后一定是
第一种
第二种
然而显然这种 dp 是有组合意义的。所以我们分类讨论:
1、尾部不是 O 的方案数,显然就是前面
2、尾部是 O 的方案数,此时第一个位置不能放 O。类似的组合一下就完了。
于是就可以组合数做。处理的时候因为答案过大,所以可以考虑取对数(学到许多)。
CF340E Iahub & Permutations
有一个长度为
n 的排列a ,其中有一些位置被替换成了-1
。你需要尝试恢复这个排列,将-1
替换回数字。 求多少种可行方案使得得到的是一个排列且不存在a_i=i 的位置。
orz 一个十分巧妙的转化,大概就是对于这种带有放置限制的排列问题,比如某个下标不能放置某个数,那么可以将这个排列对应到一个
那么就转化成了,有些行和列已经放了车,整个棋盘对角线不能放车,有多少种本质不同的放车方案数。首先可以发现,如果某行某列有车,这一行一列就可以删掉;同时如果对于某个
这样考虑
复杂度
CF212D Cutting Fence
给出
a[1...n] 。 定义f :f(i,k)=\min_{i\leq j\leq i+k-1}\{a[j]\} 之后有
m 个询问,每个询问给出一个数k ,问所有f(j,k) (1\leq j\leq n-k+1) 的平均值。
首先不难知道要求出每个
考虑两遍单调栈求出每个元素
1、
2、
3、
然后观察这些修改,发现
USACO12 Bovine Alliance G
给出.n 个点m 条边的图,现把点和边分组,每条边只能和相邻两点之一分在一组,点可以单独一组,问分组方案数以上是错误的题意,以下是正确的题意:
题意是给每条边找一个配对的点,要求边
(u,v) 配对的点是u 或v ,且每个点最多只能被一条边配对,求不同方案数。
对着错误的题意思考了半天也不会…觉得首先对于点分组可以直接跑一个第二类斯特林数,但是这样边就没法分配了,因为可能存在边的两个端点在同一个点集内,所以可能需要套一个容斥什么的。推容斥系数可能会很高妙反正我不会。
然后正确的题面的话,考虑问题可以转化成给每条边定向,使得最后整张图每个点的度数都
1、不难发现一个简单环的定向方式总共是
2、考虑去计算一棵树的定向方式。发现随便找一个根,显然哪个点当根对于整棵树的方案数没有影响。考虑如果将所有边都向儿子定向,那么这样一定合法,这是第一种方案。同时,单独把某一条边取反,假设这条边连接的儿子是
发现对于无向图,本质上就是树插环的形态。所以拿一个带权并查集维护即可。有一个坑点,就是如果两个点不在同一个即集合里,边数也要++。