codeforces edu #51 C. Vasya and Multisets (思维题)

题目链接

题意:有n个数,现在要分成2个集合,使得2个集合中,仅出现1次的数的个数相同,问是否有解,以及具体的分法。

思路:

一开始考虑出现多个的数的思路麻烦了,比如对于出现2次的某个数x,与其一个集合中分得一个,使得两个结合中,仅出现1次的数的个数各+1,还不如都放在同一个集合中,使得仅出现1次的数的个数不增加。

因此思路是这样的:

先考虑出现1次的数的个数,如果为偶数,那么均分,然后把其他出现多次的数全都放在第一个集合;

如果出现1次的数的个数为奇数,我们还是尽可能均分,然后不妨假设第一个集合中的只出现1次的数的个数比第二个集合中多1个。

我们现在需要让第二个集合中,仅出现一次的数增加一个。

什么样的数可以满足这个条件呢? 出现2次的数是不行的,因为这会使得两个集合中的数字各自+1

因此需要至少有一个出现3次或者以上的数。

具体见代码:

 

codeforces div 1 443 A. Short Program (位运算的理解)

题目链接:

题目链接

题意:

一段程序,最多5E5个操作,每个操作的格式为 <opt,x> ,opt表示位或,位异或,位与 三种位运算的一种,x表示范围0..1023的数。现在要求将该程序化简至最多 5个操作,使得对于0..1023的输入,输出与该程序同样的结果。

思路 :

关键在于想起,位运算还是按照二进制位的运算。我们考虑每位即可。

如果初始是0,现在变成了1,那么实际上我们并不确定,这个操作是xor 1 还是 or 1

因此我们需要两个初始的数,一个所有二进制位上都是0,另一个所有二进制位上都是1.

也就是0和1023

对于某个二进制位

如果初始的 (0,1)变成了 (1,1),那么说明这个位置上的位运算是or

如果初始的 (0,1)变成了(1,0) 那么说明这个位置上的位运算是xor

如果初始的 (0,1)变成了(0,0) 那么说明这个位置上的位运算是and

如果初始的 (0,1)变成了(1,0) 那么说明这个位置上没有进行位运算操作。

 

 

 

 

 

 

 

codeforces # 440 div2 E. Points, Lines and Ready-made Titles (和图有关的计数,思维题)

题目链接

题意:有n个整点,每个点处可以什么都不画,或者画一条垂直方向的直线,或者画一条水平方向的直线。

现在给出n个点的坐标,问最多右多少种不同的图案。(只要有一处不同,就认为两个不同)

思路:

参考题解

好菜啊不会做,转载一段题解。

bzoj 1854的并查集思路蜜汁契合 // 看完了题解的我这样想道

首先显然可以将图分为若干个联通块。

且慢,哪里来的图? 那就先考虑建图? 不急不急,先来想想看每一个联通块的性质。

如果该联通块中有环的话,肯定每条边都能取到;如果联通块是一棵树,那么必有一条边取不到(具体阐述见上bzoj 1854),所以只需要知道

  1. 这个联通块中有多少条边
  2. 这个联通块是不是环

这两个信息就可以了

那么可以直接上并查集。

什么样的点可以并到一起呢?横坐标相同的或者纵坐标相同的。

有没有环怎么维护呢?看有没有加进去的边的端点本身就在一个集合里。

联通块中边的数目又怎么知道呢?这倒还挺有意思的,其实只要直接看出现过多少个横坐标或者纵坐标就可以了,因为一个横坐标或者一个纵坐标就代表一条可以选的直线,所以这块联通块的贡献就是2^(x+y)者2^(x+y)-1

然后呢?就做完了。

然而呢?比赛结束。一天了。

相关并且有趣的题目:bzoj1854
codeforces #346 div2

hdu 3193 find the hotel (思维题)

hdu3193题目链接

题意:给出n个price 和distance,找到一个集合,集合中的每对在全集中找不到比他price和distance都要小的元素。小于是严格的。

思路:一开始以为找到最小值就好。。。结果漏洞百出。。这题还找不到题解。。。大概是太简单了。。? 看了一份代码大概看明白了。。。

codeforces #346 div 2 D. Bicycle Race (思维,计算几何,公式)

题目链接
题意:给出n+1个点,每次由i点到i+1点,每段线段之间保证不同向或者反向,第一个点和最后一个点保证重合。路径围城的封闭图形中间都是水,问有多少个危险点,使得如果在这个点忘记转弯就会掉进水里。

思路:搞了半天没搞出来qaq

 

From the track description follows that Maria moves the way that the water always located to the right from her, so she could fall into the water only while turning left. To check if the turn is to the left, let’s give every Maria’s moves directions a number: moving to the north — 0, moving to the west — 1, to the south — 2 and to the east — 3. Then the turn is to the left if and only if the number of direction after performing a turn dir is equal to the number before performing a turn oldDir plus one modulo 4.

This solution has complexity O(n).

 

以及还有一个O(1)的做法。。太神啦。。。

One can solve this problem in alternative way. Let the answer be equal to x (that means that the number of inner corners of 270 degrees equals x, but the number of inner corners of 90 degrees to n - x). As soon as the sum of the inner corners’ values of polygon of n vertices is equal to 180 × (n - 2), thenx × 270 + (n - x) × 90 equals to 180 × (n - 2). This leads us to , being the answer for the problem calculated in O(1).

 

hdu 4451 Dressing (计数,思维题)

http://acm.hdu.edu.cn/showproblem.php?pid=4451
题意:N clothes, M pants and K shoes,然后给出p个不合法的搭配,形式是“clothes x pants y” or “pants y shoes z”.” 问有多少种合法的方案。
思路:一开始觉得是容斥。。当然可以。。但是实际上,不合法的搭配的形式比较简单,每种不合法的发配都是两个两个的不合法,以及每种不合法的形式都有pants,那么我们就可以通过先确定pants,对于每种pants,方案数就是能和当前pants搭配的clothes数,乘以能和当前pants搭配的shoes数,然后累加每种pants的答案即可。

codeforces 560 C. Gerald’s Hexagon (思维,几何)

题意:给定一个六边形的六条边的长,问能分割成多少个单位正三角形.

 

分割不好办,那我们就反着来,先补成一个包含这个六边形的正三角形.

对于边长为a的正三角形,显然我们可以分割成a*a个单位正三角形

大正三角形的边长为连续的三条边的和

而要减掉的三个小三角形的边长为与之前连续的三条边的起始边的序号的奇偶性相同的三条边.

就是说如果求和的时候求的是前三条边,那么三个要减掉的小三角形的边长就是第一,三,五条边.

如果求和的时候求的是后三条边,那么三个要减掉的小三角形的边长就是第二,第四,第六条边.