计数器
11
被IPSC虐傻之后感觉老外的思考方式和国人完全不一样,去找毛子学点黑科技 = =
大概每天能做一两场div1吧……
代码在github里有
【Codeforces Round #305 (Div. 1)】
【A Mike and Frog】题意:给定\(m,h_1,a_1,x_1,y_1,h_2,a_2,x_2,y_2\)每次迭代会使得\(h_1=(x_1h_1+y_1)mod~m,h_2=(x_2h_2+y_2)mod~m\),问最少多少次能同时使得\(h_1=a_1,h_2=b_2\),无解输出-1,数值\(\leq 10^6\)
sol:首先\(O(m)\)暴力找出循环节和首次在循环节中匹配的次数,若中间出现答案则直接输出,否则枚举1的循环节步数,检测2是否可行
【B Mike and Feet】题意:给定长为\(n(n\leq2\times 10^5)\),的序列\(a(a_i\leq10^9)\),求所有长度为i的连续子序列中最小值的最大值
sol:从大到小加入每个数,如果能够形成新的长度的序列那么答案很明显就是这个数,随便维护一下就好了
【C Mike and Foam】题意:一个多重集,支持插入删除和询问互质点对个数,操作数2*10^5,权值5*10^5
sol:考虑到n的答案是\(\sum_{i=1}^n cnt[i][gcd(i,n)=1]=\sum_{d|n}\mu(d)(\sum_{i=1}^{\frac{n}{d}}cnt[di])\),预处理mu和约数,加入删除一个元素的时候枚举约数统计答案,并维护cnt数组
【D Mike and Fish】题意:对平面上的n个点黑白染色,要求同一x或y坐标的黑白颜色数之差不超过一,n和坐标范围<=2e5
sol:很明显建图然后染色然后wa掉,去看题解但是没有看懂,去看棒子的代码惊呆了,想了一中午感觉好像没问题然而还是不知道为什么
【E Mike and Friends】没看 = =
【Codeforces Round #302 (Div. 1)】
【A. Writing Code】题意:n个程序员按顺序写m行程序,第i个程序员的每行代码会有a_i个bug,计算bug数量<=b的方案数模mod,所有数值<=500,mod<=10^9+7
sol:\(dp[i][j][k]\)表示前i个写了j行bug数为k的方案数\(dp[i][j][k]+=dp[i][j-1][k-a[i]]\)
【B. Destroying Roads】题意:给定一张无向联通图,删去尽量多的边使得s_1到t_1的距离不大于l1,s_2到t_2的距离不大于l2,n<=3000,m<=n(n-1),
sol:先求出所有点对的最短路距离,然后枚举剩下的边的公共部分的端点,更新答案
【C. Remembering Strings】题意:给定n个长m的字符串，修改字符(i,j)费用为a_{ij},如果一个字符串的某一位置i上的字符与其他字符串的第i为均不同,则称为"好记的",求让所有字符串好记的最小代价,n,m<=20,a_{i,j}<=10^6
sol:显然状压dp,而且由于字符集大于n,可以任意修改为一个不同的,相同元素产生冲突时,最小费用是他们的和减去最大值,设dp[S]为使得集合S的字符串好记的最小费用,枚举列dp
【D. Road Improvement】题意:给定一棵树,将一些边染成黑色,使得这些边都通过黑边与根联通,分别求以每个点为根的方案数\(mod(10^9+7),n<=2\times 10^5\)
sol:\(dp[u]=\prod_v (dp[v]+1)\)非常显然,我们还要求出每个点向上的答案\(up[v]=\frac{up[u]dp[u]}{dp[v]+1}\),注意由于涉及到加法,除法不能用逆元,而应改处理出前后缀积来计算
【E. Listening to Music】我有E题恐惧症……
【VK Cup 2015 - Round 3 (unofficial online mirror, Div. 1 only)】
这场的题好像比较难……于是只会做3个……
【A. Place Your Ad Here】
分别给定n个和m个线段,m个线段带权,在n和m中各选一个线段,最大化线段的交乘以权值,n,m<=2*10^5,权值<=10^9
sol:vp的时候感觉和bzoj2687很像,于是写了分治,但发现好像没有决策单调性……拍了拍也经常出错,但感觉数据非常难做……于是小范围暴力大范围分治就过掉了……正解似乎是分类讨论线段树?
【C. Idempotent functions】
定义一个函数f:{1..n}->{1..n},定义f^{(k)}(x)为f(f^{(k-1)}(x)),
求最小的k使得f^{(k)}(f^{(k)}(x))=f^{(k)}(x),n<=200
sol:每一位的循环节是独立的,暴力求出来然后lcm
【F. Quest】
给定n个任务,每个任务有有趣值q_i和时间t_i,构造一个所有叶节点都是任务的二叉树,要求有趣值之和最大,且每个任务的t_i加它到根的距离不大于T,n,q_i<=1000,T,t<=100
sol:f[i][j]表示深度为i有j个结点,自底向上dp,转移为f[i][j]=max f[i][j-k-1]+sum(k),f[i+1][(j+1)/2]=max f[i][j]
【Codeforces Round #300】
ABCD太水没什么好讲……
剩下的题人太傻没的讲……
【Codeforces Round #245 (Div. 1)】
挑了一场比较简单的场来治疗一下我的E题恐惧症
【A. Xor-tree】
题意:给定一棵有根树,点带01权,每次可以任选x,将x的子树中深度与x奇偶性相同的点翻转,求到达目标状态的最小操作数,n<=10^5
sol:dfs不多说
【B.Working out】
题意:给定一个n*m的网格图,A要从左上走到右下,B要从左下走到右上,要求他们的路径只有一个点相交,获得的值为他们除去相同部分的路径和,求max,n,m<=1000,a_i<=10^5
sol:dp出来每个点到四个角的max,枚举交点,没了
【C.Guess the Tree】
题意:构造一个n个结点的树,使得每个点的子树大小为c_i,n<=24
sol：显然把c排序后然后枚举每个点的父亲比较靠谱,于是写了一个搜索,于是卡了一下时就过了……标解好像很厉害,似乎是状压+meet in the middle
【D. Tricky Function】
题意:给定序列,定义\(f(i,j)=(i-j)^2+(sum_i-sum_j)^2\),求max f(i,j),n<=10^5,|a_i|<=10^4
sol:把每个视为一个点(i,sum_i),然后就是平面最近点对
【E. Points and Segments】
题意：数轴上有n个线段,决定每个线段的权值为1或-1,使得|每个点的值|<=1,n<=10^5,l,r<=10^9
sol:离散化、连边、黑白染色
【Codeforces Round #309 (Div. 1)】
终于黄了……
【A. Kyoya and Colored Balls】
题意:有k种颜色的球,把它们放成一排,要求颜色i的最后一个出现的位置在i+1最后一个出现位置之前,求方案数
sol:设f[i]为使用前i种颜色的方案数,考虑新增一种颜色,将一个放在最后,其他的插进去,插板法
【B. Kyoya and Permutation】
题意:将一个置换拆分为循环,循环sort,然后整个循环再sort,变为另一个置换,求字典序第k个不动点
sol:打表找规律……不多说了……
【C. Love Triangles】
由于并不能理解题解所以大概是自己题意读错了……于是先坑着……
【D. Nudist Beach】
题意:一张图,可以在某些点中选择一个点集,每个点的权值为 与他相邻的选择的点数/与他相邻的点数,点集的权值为集合中最小的权值,选择最大的点集.
sol:先选择全集,每次贪心把最小的点删去,正确性见官方题解
【Codeforces Round #290 (Div. 1)】
白天会考晚上cf……vp到一半cf还炸了……
【A. Fox And Names】
题意:给定一个字符串序列,对字母表重新排序,使得序列是成字典序排列的
sol:差分约束然后sort,一直wa on test 13的同学可以试一试这个数据
2
ab
a
【B. Fox And Jumping】
题意:给定序列l,c,选择l_i的代价是c_i,选择一个子集使得l的gcd为1且代价最小
sol:dp[i][j]表示前i个数gcd为j的最小代价,转移显然,由于j最多nsqrt(w)种所以可以hash,或者干脆来个map
【C. Fox And Dinner】
题意:给定一张二分图,将它分解为多个环
sol:网络流,每个点的流量为2
【D. Fox And Travelling】
题意:给定一张图,一个点可以被访问当且仅当他的邻居种至多有一个未访问且他没有被访问,求走0..n次的方案数
sol:好麻烦……明天还要会考先不写了
【Codeforces Round #310 (Div. 1)】
这场cf真感人……还好没做……
【A. Case of Matryoshkas】
题意:给定k个俄罗斯套娃,只有小的能套在大的里,每次可以把最外层的套娃拿出或者套上,问把所有套娃合成一个的最小操作次数
sol:由于答案不会超过2n所以模拟即可……注意一下细节
【B. Case of Fugitive】
题意:在x轴上给出n个不相交的线段,你有m个长度分别为a_i的桥,要把每相邻两个线段连起来,若一个桥的两端点分别在两线段内则视为连接,输出方案
sol:相邻两个线段的可行长度是一个区间,把他们以右端点第一关键字左端点第二关键字升序,贪心,每次放可行的最左边的
【C. Case of Chocolate】
题意:给定一个等腰直角三角形,每次会从斜边开始向左或向上染色,直到已染色或边界,输出每次操作染的颜色数
sol:分别用线段树维护两维最值即可,动态节点可以省去离散化
【D. Case of a Top Secret】
题意：在x轴上给出n个点,现在你从a_i逆时针扔出一个长为l的绳子,问最后绳子会缠在哪里
sol:模拟,有循环节膜循环节,没了
【Codeforces Round #286 (Div. 1)】
一场sxbk的round……只有ABD能做……
【A. Mr. Kitayuta, the Treasure Hunter】
题意:一个数轴上有n点带权,给定初始位置,设上次跳的长度为l,每次可以往后跳l-1,l,l+1,求最大价值
sol:f[i][j]表示到达i上一次跳长度为j所能获得的最大价值,j的取值只有sqrt(n)中
【B. Mr. Kitayuta's Technology】
题意:构造一个有向图,使得给定的点对(u,v)可以从u到v
sol:显然我们可以构造一个环直接满足所有点对,而且原图中无关的两组可以被分成两个,若不形成环则ans--
【D. Mr. Kitayuta's Colorful Graph】
题意:给定一个无向图,边带颜色,每次询问两点直接有多少种颜色可以使得他们联通
sol:设某颜色有K条边,那么有O(k)个点相关,O(k^2)个询问,所以复杂度为\(\sum_imin(k_i^2,q)\),满足约束\(\sum_i k_i =m\),你会发现复杂度最多为\(m\sqrt q\)
【Codeforces Round #260 (Div. 1)】
qdez网速感人,做到一半cf上不去了……
【A. Boredom】
题意:给定序列a,每次可以任意选择a_k,并删除a_k和等于a_k-1,a_k+1的数,获得a_k的价值,最大化价值
sol:很显然相邻两种值不能同时选,然后就是一个经典的dp
【B. A Lot of Games】
题意:给定n个字符串,AB轮流加一个字符,要求是某字符串前缀,不能操作者输,游戏将进行k轮,每轮的loser将成为下局的先手,问最终的胜者
sol:注意到为了获得最终的胜利先手是有可能决定自己的输赢的……建出Trie之后f[]g[]表示先手能否获得胜利/失败
【C. Civilization】
题意:给定一个森林,两种操作：1 x 询问x所在数的直径,2 x y连接xy所在的联通块,要求联通后树的直径尽量小
sol:找出每棵树的直径,2操作用并查集维护,合并后的len为max(len[x],len[y],(len[x]+1)/2+1+(len[y]+1/2)
【D. Serega and Fun】
题意:给定序列,设计数据结构支持1 l r,将[l,r]循环位移,2 l r x,询问[l,r]中x出现次数
sol:分块裸题,懒得写了
【Codeforces Round #200 (Div. 1)】
做水Round涨自信
【A. Rational Resistance】
题意:用最少的1欧的电阻凑出a/b欧
sol:额……推一推是一个和gcd类似的东西……
【B. Alternating Current】
题意:两个绳子缠了起来,给出交点处谁在上面,问是否缠上了
sol:好奇怪的题……用栈维护一下……
【C. Read Time】
题意:给定一个无限长的纸带,有n个读写头可以同时移动,现在你要访问m个位置,问最少时间
sol:二分check,考虑使用每个读写头尝试覆盖最前面没有被覆盖的然后贪心向后推
【D. Water Tree】
题意:设计数据结构支持:1子树set1,2点到根set0,3询问某点颜色
sol:nlog^2n树剖裸题,标算是nlogn的,也很简单懒得写了
2015年6月22日 17:08
Orz ZKY 顺便提一下 B题的范围是2*10^5 【捂脸熊】
2015年6月22日 22:50
@zyfzyf: 噗……谢谢提醒……
2015年6月23日 08:42
神犇跟我一起做吧2333
2015年6月23日 12:49
@hzwer: 好啊好啊，学长带我飞~
2015年6月26日 20:01
我从上周开始想刷之后发现我只敢做CF上场数是两位数的那些比赛的老古董QAQ而且还看不懂题QAQ
2015年6月27日 20:11
@CreationAugust: 从div1A题慢慢做,不会看题解,看不懂题……找有道翻译,顺便说一句不建议做div2的AB,太水没意义
2023年4月23日 20:14
crediblebh