abcdhhhh

ACM

工具(1) 机器学习(1) 离散数学(1) 题解(7)

/ 注册

全部文章 / ACM （共11篇）

BSUIR Open 2017 Finals补题

A 给定一棵 n n n个节点的树（ n ≤ 1000 n\le 1000 n≤1000），需要把所有边定向，使得恰好有m个点没有出边，求方案数。 Solution 记 d p [ u ] [ x ] [ 0 / 1 ] dp[u][x][0/1] dp[u][x][0/1]为以 u u u为...

2021-05-26

0 495

NAIPC 2017补题

D 给定一棵 n ( n ≤ 2 e 5 ) n(n\le 2e5) n(n≤2e5)个点的有根树，每个点有点权，选出一些点，使得这些点的满足大根堆的性质，求最多可以选多少点。如果是一条链，就是求LIS，做法是维护一个单调队列。树的话，其实也可以用单调队列，不过需要对不同儿子节点的队列进行...

2021-05-26

0 644

Jagiellonian U Contest补题

G 一个圆周的 m m m等分点编号分别为 1 ∼ n 1\sim n 1∼n， n n n只蟋蟀分别在编号 A 1 , A 2 , . . . , A n A_1,A_2,...,A_n A1,A2,...,An的点上。每秒，第 i i i只蟋蟀跳到 A i A_i Ai关于 A i +...

2021-05-26

0 553

CCPC2020秦皇岛站总结

Day0 开幕式就听了一大堆发言，就这么过去了。热身赛拿到题面，队友果断切了D题和C题，接下来我们就开始看B。 B题是一个博弈，就是有 n n n堆石子，每堆 A i A_i Ai个，每个回合可以从1~2堆中取任意多个。然后问 L i ≤ A i ≤ R i L_i\le A_i\l...

2021-05-26

1 449

ICPC2020模拟测试赛总结

A 求满足 0 ≤ x ≤ a , 0 ≤ y ≤ b , 0 ≤ z ≤ c , 0 ≤ k ≤ d 0\le x\le a, 0\le y\le b, 0\le z\le c, 0\le k\le d 0≤x≤a,0≤y≤b,0≤z≤c,0≤k≤d的整数 x , y , z , k x,y,z...

2021-05-26

0 541

ICPC2020上海站总结

Day 0 准备工作环境懒得测了，听别的队说是C++14还是C++17的什么特性用不了？反正我们都是C语言码风，不怎么在乎。队友FEZ嫌桌面不好看，换了个阳间的电脑桌面打印机坏了，热身赛结束后又整了半天热身赛 A 初始有 1 ∼ n 1\sim n 1∼n共 n n n个数，每次随...

2021-05-26

0 677

【gym_102878E】Eigen Substring（后缀自动机）

https://codeforces.com/gym/102878/problem/E 题目描述如果字符串 s s s的子串 s [ l . . r ] s[l..r] s[l..r]在 s s s中只出现一次，那么称它为 s s s的特征子串。给定字符串 s s s，询问它的每个前缀的最...

2021-05-26

0 470

【洛谷P2617】Dynamic Rankings（整体二分）

题目链接这是一个动态区间第k大的模板题，主要有两种方法：在线：主席树套树状数组离线：整体二分（更方便）整体二分的题通常需要满足如下条件：单组询问可以二分存在高效的数据结构维护修改对询问的影响（像区间修改就不存在）题目可以离线做（废话）对于该题来说，每个...

2021-05-26

0 610

【gym 101955K】Let the Flames Begin（约瑟夫环问题）

题目链接大意是 n n n个人围成一圈（ID依次为 1 ∼ n 1\sim n 1∼n），每 k k k个人踢掉1个，求第 m m m个被踢掉的人的ID。 1. O ( k log ⁡ n ) O(k\log n) O(klogn)解法（未AC）参考知乎回答按该回答中的方式进行编号，第 ...

2021-05-26

0 581

常系数齐次线性递推

题目链接题目描述数列 { a n } \{a_n\} { an}满足 k k k阶线性递推关系： a n = ∑ i = 1 k f i a n − i ( n ≥ k ) a_n=\sum_{i=1}^kf_ia_{n-i} (n\ge k) an=∑i=1kfian−...

2021-05-26

0 537