sunrise__sunrise

题解

未归档(12) 读书笔记(1)

/ 注册

全部文章 / 题解（共372篇）

【每日一题】9月24日[HAOI2008]硬币购物，容斥原理，二进制枚举来自专栏

题目意思你来到一个商店，你带了c1,c2,c3,c4四种面值的硬币，以及购买次数tot。接下来tot行，每行有d1,d2,d3,d4分别对应四种硬币的使用个数上限，以及你想要购买的物品价值数s。询问你有几种合理的方法使用合理的硬币数量购买到价值s的物品？ Solution 正面？处理不来，情况太多...

2020-09-28

1 698

【每日一题】9月23日题目精讲-最后的晚餐(dinner)，递推来自专栏

题目大意存在n对情侣，一共2 * n个人，现在要求每对情侣都不能相邻而坐，有多少种排序的方案。 Solution 首先这是一个环，所以1234与2341是同样的方案，那么从n对情侣中先把男生挑出来共n个人先去坐位子，共(n-1)!个方案。接下来就是把剩下n个人插入进去了。定义dp[i]代表安排完...

2020-09-28

0 942

【每日一题】9月22日[SCOI2009]游戏，LCM，素数筛，完全背包来自专栏

题目意思：给你1 - n的一个序列，你可以随便定义一个长度形成环，过了一段时间会回到1 - n这个状态，问这个时间的集合大小是多少？ Solution 显然这个回到起点的时间就是LCM全部环的长度，问题就变成了，n分隔成若干个数，求他们LCM的种类数。枚举全部的可能一定会T掉，所以转换一下，LCM...

2020-09-27

1 640

【每日一题】9月8日题目-摆渡车，记忆化搜索来自专栏

Solution 中文的题意说的比较清楚，说下膜拜的大佬做法，大佬题解传送门我们需要让整体学生等候时间最短，那么就要遵循几个原则。首先我们对到来时刻升序排序，依次处理。我们暴力搜索下去需要两个函数参数，搭载的人员数量和当前汽车回到起点所在时刻1、如果回来之后没有一个学生在等车，直接跳转到下一个需要...

2020-09-08

2 744

【每日一题】9月4日题目-选择客栈，模拟来自专栏

题目描述给出一维线段长度n，客栈装修颜色k，咖啡店最高的花费p。再给出n个点的装修颜色和咖啡店花费，问你在装修颜色相同的两家店，左右闭区间的情况下，区间咖啡店最小值小于等于p的集合有几个？ Solution 因为咖啡店是顺序给出的，我们直接对着先录取颜色和咖啡店花费，如果当前点的花费小于等于p，那...

2020-09-06

2 764

牛客IOI周赛18-普及组

A、数字计数直接排序，注意要去掉重复，样例坑了一手。其他根据题意翻译就行了 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffa...

2020-09-05

0 643

【每日一题】8月31日题目，二分来自专栏

题目描述给出长度为n 的序列，这个序列得出公式也给出，各个系数以及模数依次给出，自己递推出全部的序列。在得到这个序列基础之上，询问你，是否可以构造一个新的数列，在原数列原来位置的数值只做加减法。得到的新数列需要保证不递减，即后一项不比前一项小。，每两项之间都要符合这个要求，问你符合要求的最小的改变...

2020-08-30

1 698

【每日一题】8月26日Summer Earnings，bitset+两点间距离来自专栏

题目意思给出n个二维坐标点，n<3001，下面依次n行，问最大的圆半径是多少可以保证三个圆心下构成的三个圆最多相切但是不相交。 Solution 纯暴力解法，On^3，枚举点坐标，复杂度太大，一定是超时的，但是思路是三个点距离求最小的，最后外层循环找最大直接枚举点不行，那就换个思路，通过n&...

2020-08-27

0 659

【每日一题】8月27日Is It A Tree?，树形结构来自专栏

Solution 给你一些父子关系，判断这个些点构成的集合是否是一棵树，内存给的很小。使用并查集维护，如果集合内部合并说明形成了环，不是一棵树，多个根节点，也不是一棵树。最后注意特判一下空树的情况就可以过了。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt...

2020-08-27

0 827

【每日一题】8月25日XOR-pyramid，异或，区间dp 来自专栏

题目描述给出n个数，n<5000第二行给出n个数的权值分别是多少，给出f函数的定义，是依次相邻的异或，直到最终函数参数只有一个，得到的值就是参数的值。下面给出q次询问，每次询问给出l，r，问在这个区间中最大的f是什么？ Solution 异或可以抵消，所以枚举起来不是很复杂，我枚举了长度为3...

2020-08-24

0 716