ACM

题目链接 题意：给出8个点，问能否构成一个8元素集合，使得x1/* *********************************************** Author :111qqz Created Time :2016年03月31日 星期四 13时39分27秒 File Name :code/cf/problem/334B.cpp ************************************************ */ #include #include #include #include #include #include #include #include #include #include #include #include #define fst first #define sec second #define lson l,m,rt«1 #define rson m+1,r,rt«1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair

题目链接 题意：给出n个时间的开始和截止时间，保证没有两个时间的开始或者截止时间相同，问有多少个时间被包含在其他事件中。即aj < ai and bi < bj. 思路：没有两个事件的时间相同很关键。 那么我们可以直接按照开始时间为关键字排序，然后结束时间取之前发生了的（可能还没发生完）时间的结束时间的最大值即可。

题目链接 题意：给出n个互不相同的元素和k，构成一个集合，使得集合中不存在两个元素满足y=kx，问能构成这样的集合的最大size是多少。 思路：set大法好。很重要的一点是题目中明确说每个元素都不重复。然后每次删掉元素x和元素xk，因为这两个元素最多留一个，然后答案+1. 需要注意k=1的特殊情况。

题目链接 题意：有n天的旅行，但是只剩下了m天的旅行记录，记录格式为d[i],h[d[i]]，表示第i个记录是第d[i]天的，高度为h[d[i]]，相邻两天的高度之差的绝对值不超过1.问满足以上条件的最大的h是多少。无解输出impossible. 思路：为了练习二分。 二分高度，然后check是否合法。注意边界，所以可以添加两个点。

题目链接 题意：没图不好描述，有中文题面中文题面，直接看吧。 思路：据说这道题有三种做法。当时比赛一种都不会。 先说一种：做法是把格子看成点，可以到达的相邻格子之间看成有边相连，然后倒过来用并查集判断无向图的连通性。具体做法是：先统计初始所有空的位置，然后把所有要增加的山都加上（先统计空的位置是因为山之后要去掉，而去掉以后要得到该点的标号），然后将所有空的点以及china（设标号为n*m+1）点，和india（设标号为n*m+2）点通过并查集来合并，可以从上往下从左往右，每次只需要判断上面的点和左边的点是否有空，如果有就用并查集合并。china点和india点特殊搞就好。

题目链接 題意：已知一个包含 nn 个元素的正整数集合 SS，设 f(S)f(S) 为集合 SS 中所有元素的异或(XOR)的结果。 如：S={1,2,3}, 则 f(S) = 0f(S)=0。 给出集合 SS，你需要计算 将所有 f(s)进行异或后的值， s⊆S.

题目链接 题意；给出一个字符串，只由小写字母组成，可以任意排列，但是不能减少字符，问最多能得到多少个回文串，答案9+7 思路：排列组合题。 首先考虑无解的情况。统计出每个字母出现的次数，当字符串长度为奇数而且出现次数为奇数的字母的个数多于1个时无解，或者当字符串长度为偶数，出现次数为奇数的字母的个数多于0个时无解。 接下来，由于是回文串，只需要考虑len/2的情况，另一半是一一对应的。 其实就是一共有len/2的元素，其中有一些重复的，然后全排列。 多重元素的排列问题。 答案为(len/2)! % （cnt[1]!）% (cnt[2]!)…即可 哦要先把cnt降序排一下，只考虑cnt[i]>1的元素，然后因为是要考虑一半长度，所以每个cnt[i]/2 那一堆阶乘直接逆元搞就好了。。。。

比赛链接 两题QAQ A：7分钟1A 有n个大人m个小孩乘公交车，票价每人一元，一个大人最多免费带一个小孩，没有大人陪同的小孩不能乘车。 问是否有解，如果有解输出所有乘客付的钱的可能的最小值和可能的最大值。

题目链接 题意：将正整数n(n<=1E9)，拆分成k个（k<=1E9）个**互不相等的正整数，**并且使得k个正整数的乘积最大。如果可以拆分，输出最大乘积，否则输出-1.

题目链接 题意：n（n<=300）个球，每个球上标有一个标号(a[i]<=300)，从中拿一个，不放回，再拿一个，问第一个球上的数字严格大于第二个球上的数字的概率。 思路：古典概型。总数为n*(n-1)/2…然后标号最大300，不妨用cnt[i]统计标号为i的球的个数。从小往大扫一遍cnt,cnt[i]对分子的贡献就是cnt[i]*cur。。cur 为 sum{cnt[1]..cnt[i-1]}; 最后注意将分子除以2，因为有一半是第一个球比第二个球小的情况。

题目链接 题意：给出n个点，m条边，定义一条路径的价值为【路径长度*(路径终点的度)】，求最大价值。 思路：一月份的时候写过一个回溯。。。TLE22了。。。其实也能猜到是dp..但是无奈不会写。然而其实真的不难== 我们枚举路径的终点，dp[i]表示以点i为终点能得到的最长路径长度。

题目链接 题意：n个点，m（m<n/2）条不能走的边，问最少连多少条边，使得任何两个点之间的距离最多为2. 输出最少的边数和连接的哪些边。 思路： **数据范围很关键。**数据范围很关键。数据范围很关键。

题目链接 题意：给出n和k，给出一个长度为n的字符串表示房间的占用情况（0表示没占用，1表示已占用），从n个房间中找出k+1个，使得k+1中的k个距离k+1个中的1个的距离和最小。

题目链接 题意：长度为n的初始为1，2,3…n的序列，最多进行k次两个数交换，变换后的序列中最懂能有多少逆序对。 思路：贪心得想。。每次变最外层的对答案贡献最多。 以及，最能能变化n/2次。

题目链接 题意：2×2的格子，有三个位置分别放”A“ “B” “C” ，一个位置为空。只有和空位相邻位置上的字母能移动到空位。没有其他移动规则。现在给出两个状态。问能否互相转化。 思路： 貌似可以dfs…？但是一共才2*2，可以直接暴力枚举。 手写一种变换最多能有12种。

题目链接 题意：设条件A为一个数恰好是k个互不相同的b的整数次幂的和，问某一个区间内满足条件A的数的个数是有多少个。 Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2: 17 = 24+20, 18 = 24+21, 20 = 24+22.

题目链接 题意：将一个10进制数x按照2进制展开后得到的值设为f(x)…现在给出a,b（10^9）问【0，b】中满足f[x]<=f[a]的数的个数。 思路：先算出f[a]，然后我们发现f(x)最大也就10*2^10=10240，数组可以存下，搞之。和上一道题类似，我们不关心两个f函数的值具体是多少，只关心它们的相对大小情况，所以还是可以合并成一个变量。然而我用两个变量为什么错了，不懂==

hdu5642题目链接 题意：问长度为n的仅由26个小写字母组成的合法字符串有多少个。如果某个字符连续出现四次或以上，则这个字符串为非法。否则为合法。 思路：当时以为是组合数学的题。。。推了半天公式还是还是gg… 现在学了数位dp..果然是数位dp里很简单的一种。。。 dp[i][j][k]表示长度为i，最后一个字符对应的数字为j，最后一个字符出现了k次的方案数。

题目链接 题意：找到某区间中平衡数的个数。所谓平衡数是指，存在某个位置，使得两边的力矩相等。举个例子，比如14326，如果把4作为中间，那么左边=11=1，右边=31+22+62=19。 思路：枚举中间的pivot，注意个位数也是平衡数（就是认为两边的力矩都是0了），所以每一个位置都可能是平衡位置，枚举的时候从1到len… 一开始我是分别记录两边的值，非常浪费空间，然而发现其实没必要。我们只关心左右是否相等，而不关心左右的值到底是多少，所以可以把两边的值带符号合并成一个值（pivot左边为+，pivot右边为负）。如果最后为0，说明左右相等。

题目链接 题意：问某区间中，round number 的个数是多少。所谓round number，当且仅当一个数的二进制表示中，‘0’的个数大于等于‘1’的个数。 思路：简单数位dp..和windy数那道题类似，都是不允许前导0.。。所以在dfs中要加一维判断前面是否有非0的数。。。