题目链接 题意：有n天的旅行，但是只剩下了m天的旅行记录，记录格式为d[i],h[d[i]]，表示第i个记录是第d[i]天的，高度为h[d[i]],相邻两天的高度之差的绝对值不超过1.问满足以上条件的最大的h是多少。无解输出impossible. 思路：为了练习二分。 二分高度，然后check是否合法。注意边界，所以可以添加两个点。 /* *********************************************** Author :111qqz Created Time :2016年03月30日 星期三 16时53分57秒 File Name :code/cf/problem/538C.cpp …

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

题目链接 題意：已知一个包含 nn 个元素的正整数集合 SS，设 f(S)f(S) 为集合 SS 中所有元素的异或(XOR)的结果。 如：S={1,2,3}, 则 f(S) = 0f(S)=0。 给出集合 SS，你需要计算 将所有 f(s)进行异或后的值, s⊆S. 思路：当集合中元素大于1个的时候，每个元素对都会出现偶数次，对答案的贡献为0. 当集合中只有一个元素的时候，设为x,对答案的贡献为x. /* *********************************************** Author :111qqz Created Time :2016年03月26日 星期六 18时52分14秒 File Name …

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

比赛链接 两题QAQ A：7分钟1A 有n个大人m个小孩乘公交车，票价每人一元，一个大人最多免费带一个小孩，没有大人陪同的小孩不能乘车。 问是否有解，如果有解输出所有乘客付的钱的可能的最小值和可能的最大值。 思路：最小值就是先尽量利用每个大人带一个孩子。最大值就是把所有孩子都给一个大人。 特殊情况是：没有大人的时候，孩子不能乘车，无解。没有小孩的时候，大人没办法免费带孩子，也要特殊考虑。 /* *********************************************** Author :111qqz Created Time :2016年03月24日 星期四 12时24分27秒 File Name …

题目链接 题意：将正整数n(n<=1E9)，拆分成k个（k<=1E9）个**互不相等的正整数，**并且使得k个正整数的乘积最大。如果可以拆分，输出最大乘积，否则输出-1. 思路：其实是道贪心。。容易知道，k个互不相同的正整数的最小的和为sum=(k+1)*k/2，以此来判断是否有解。如果有解。那么找到最大的i，使得从i 开始的连续k个正整数相加的和小于等于n. 由于k不会超过1E5(否则一定无解)，所以可以开个数组存一下拆分的每个数。 然后设此时还需要添加r才能到n,那么贪心得想，一定是给最大的r个每个增加1最后的乘积会最大。这等效于直接将第k-r+1个直接增加r. 注意全程long long 以及： 开了同步以 …

题目链接 题意：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，因为有一半是第一个球比第二个球小的情况。 /* *********************************************** Author :111qqz Created Time …

题目链接 题意：给出n个点，m条边，定义一条路径的价值为【路径长度*(路径终点的度)】，求最大价值。 思路：一月份的时候写过一个回溯。。。TLE22了。。。其实也能猜到是dp..但是无奈不会写。然而其实真的不难== 我们枚举路径的终点，dp[i]表示以点i为终点能得到的最长路径长度。 转移方程：dp[i] = max(dp[i],dp[edge[i][j]]+1); 含义是与i点相连的j点是否要将i点加在以j点为路径末尾的路径的终点，使i点成为新的路径终点。 具体看代码 /* *********************************************** Author :111qqz Created Time …

题目链接 题意：n个点，m（m<n/2）条不能走的边，问最少连多少条边，使得任何两个点之间的距离最多为2. 输出最少的边数和连接的哪些边。 思路： **数据范围很关键。**数据范围很关键。数据范围很关键。 因为m<n/2,每条禁止的边最多禁止两个点，所以禁止的点数<n..那么至少有一个点是和可以和其他所有点相连的。。于是把其他所有点和该点相连即可。 /* *********************************************** Author :111qqz Created Time :2016年03月19日 星期六 10时39分40秒 File Name …

题目链接 题意：给出n和k,给出一个长度为n的字符串表示房间的占用情况（0表示没占用，1表示已占用），从n个房间中找出k+1个，使得k+1中的k个距离k+1个中的1个的距离和最小。 思路：只需要考虑没被占用的位置。所以用pos[]数组记录0的位置。 找到第一个能住下的位置后向前平移即可。 /* *********************************************** Author :111qqz Created Time :2016年03月19日 星期六 00时21分28秒 File Name :code/cf/croc2016/C.cpp …