Dawn-K's Blog

「From ashes to the empire」

「CodeNote」 HDU2546(01背包)

HDU2546 [TOC] 题意电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。输入 ...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 CF455A(简单dp)

CF455A 题目链接 [TOC] 题意给你长为 N 的整数序列a,你可以选择其中一个数ak,你会得到与这个数相同的分数,然后数列中和 ak+1 ak-1相同的数都会被删掉,求最多的分数输入第一行给出一个n 接下来在一行中给出 n个数,第i个数表示ai 输出输出可得到的最多的分数解析这个题肯定是用哈希来表示每个数出现了多少次,然后自小到大遍历,决策....

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 CF1186C(思维+位运算)

CF1186C(思维+位运算) 题目链接中文题意给出两个字符串a,b,将字符串a中所有长度为|b| 的子串都与b相比较,如果它们对应位不同的个数为偶数,则计数器加一.求计数器最后的值. 输入第一行是字符串a,长度不大于1e6 第二行是字符串b,长度不大于 a 输出输出答案. 样例 input input...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 CF1138B(数学+暴力)

CF1138B 题目链接 [TOC] 中文题意给出N(保证是偶数)个人的资料,其中c[i]为1表示此人可以扮演小丑,a[i]为1表示此人可以扮演艺术家,然后让你把这群人分成两组. 有三点要求两组人数必须相等. 第一组的小丑数量必须等于第二组的艺术家数量一个人只能被分在一个组里面输入第一行给出N(2<=n<=...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 CF1034A(数论)

CF1034A [TOC] 题意给你n个数,求最少去掉几个数能让这些数的最大公因数变大输入第一行给出一个n(2<=n<=3e5) 第二行给出n个数,表示a1,a2….an,其中ai表示第i个数输出输出最少删掉的数解析关于一堆数的最大公约数,思路还是唯一分解定理.然后我们发现对于每个质因数,似乎只要把为0的去掉就可以了,但是!!! 如果 ...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 CF1029C(贪心)

CF1029C [TOC] 题意给你n个线段,给出其左右端点,求去掉其中一个边,剩下的线段的最大交集输入第一行给出一个n(2<=n<=3e5) 接下来N行,每一行给出l,r(0<=l<=r<=1e9) 输出输出n-1条边的最大交集. 解析看到这个题我想起了之前做过的一个题(CF1132C),博客链接当时那个题是枚举去掉的...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 CF1027D(dfs+图论)

CF1027D 题意 n间宿舍里有老鼠,老鼠(只有一只)可能出现在任何一间寝室,然后它在第i个寝室里待一秒后一定会跑向第c[i]个寝室,给出在每个寝室布置陷阱的成本,求无论老鼠初始出现在那个寝室,一定会被抓住的最低成本. 输入第一行给出n(1<=n<=2e5) 第二行给出n个数字,每个大小都是[1,1e4],第i个表示c[i],即在第i个寝室布置陷阱的成本 ...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 CF1020C(枚举+贪心)

CF1020C 题目链接 [TOC] 题意这个题的背景是贿赂选民,从而让自己的组织能够上台. 自己组织的编号是1. 然后列出选民想要选的组织,以及收买他们的代价. 求最小代价. 输入第一行给出n,m,表示选民数量和组织数量,组织按照[1,2,3…m]编号,范围都是[1,3000] 然后之后n行选民,每一行给出p,c,表示此位选民想投的组织和收买的代...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 CF 刷题之路

CF 刷题之路人一我百，人十我万。 ——kuangbin 搜集模板 //惯用函数 1 2 ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?g...

Posted by Dawn-K's Blog on August 6, 2019

「CodeNote」 ACW97(约数和+分治)

ACW97 题意 \[给出两个整数A,B,求A^B的约数和,结果对9901取模\] 输入同一行内给出A,B, 0<=A,B<=5e7 且A,B不会同时为0 输出输出(A^B)%9901 分析约数和在之前数论里总结过,直接套用模板即可 \(n的(a1+1)(a2+1)⋅⋅⋅(ak+1)(a1+1)(a2+1)···(ak+1)个正约数的和为：\) \[(p...

Posted by Dawn-K's Blog on August 6, 2019