ACM

Atcoder - Flip and Rectangles(图形递推)

Atcoder - Flip and Rectangles(图形递推)
题意:给你两行相等长度的字符串,你有R\G\B三种颜色可选,颜色可以涂一个1*2的矩形,要么横要么竖,不能存在两个相邻矩形颜色相同,给出的字符串代表的是矩形可以摆放的方向。求最多有多少种涂色的方法。题解:这个要在草稿纸上画一画自己分类讨论一下才能好理解,比赛的时候画是画了,但是由于代码写的太low导致出了bug,赛后补了。要注意特判前面第一个对后面的影响,到了后面就都是规律了。代码:#includ... 继续阅读 »
ACM

CDOJ - 1401 谭爷的黑暗沙拉 (隔板法)

CDOJ - 1401 谭爷的黑暗沙拉 (隔板法)
题目意思就是说,给你n种食材,食材供应无限,然后要你选择k种食材做成一个沙拉,两份沙拉不同,当且仅当k重量食材的种类或配比不同。普通的隔板法不允许有空组出现,而且容易理解,但是这里用到了分组为空的情况,所以我们先来举个例子介绍下允许分组为空隔板法:> 假设我们有10个小球,将其放入3个盒子,盒子可以为空,请问共有多少种放法?利用隔板法,我们只能在10个小球中间的9个位置插入隔板来分组,但是这... 继续阅读 »
ACM

HDU - 5120 Intersection(数学,两圆相交面积)

HDU - 5120 Intersection(数学,两圆相交面积)
题目的意思是给你一个大圆一个小圆,这两个圆组成一个环,然后有两个环处在不同的坐标位置,求这两个环相交的面积。相交面积=S大环∩大环-S大环∩小环*2+S小环∩小环,如下图所示:那么两个环之间相交的面积怎么求呢?如上图,两个圆相交的面积=S扇形OrAB-S三角形OrAB+S扇形ORAB-S三角形ORAB扇形面积怎么求?我们知道两个圆心之间的距离是可以求出来的,R、r都知道,三边都知道那么用余弦定理可... 继续阅读 »
ACM

POJ 1845 Sumdiv(唯一分解+递归二分+快速幂+大数模)

POJ 1845 	Sumdiv(唯一分解+递归二分+快速幂+大数模)
题目意思是,给出一个底数和他的幂,请计算这个数的所有因素之和。下面对四个知识点进行梳理:1、唯一分解定理:定义:任何一个大于1的自然数N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积A=p1^a1 * p2^a2 * p3^a3 *...* pn^an,这里p1<p2<p3......<pn均为质数,其中指数ai是正整数。这样的分解称为N的标准分解式。由于 A... 继续阅读 »
ACM

POJ 1006 Biorhythms(同余定理)

POJ 1006 Biorhythms(同余定理)
题目的意思是,给定三个周期,23,28,33,然后给出这三个周期在一年内上次出现最高峰的日期,分别为:p,e,i。再给出一个当前日期d。请计算从当前d开始往后,下次三个周期重合的时间距离现在是多少天。注意,如果下次周期重合的时间小于等于d都是不可用的。代码:乱搞版本StatusAcceptedTime63msMemory644kBLength557LangG++#include <... 继续阅读 »
ACM

HYSBZ 1045 - 糖果的传递(数学思维)

HYSBZ 1045 - 糖果的传递(数学思维)
数学真的是太奇妙了。n个人分糖果,这里我们先计算平均数。得到平均数之后,我们用原来的糖果减去平均数,这样就是每个人需要支出的糖果数。我们把这些数看成是价值,然后排序,找到中位数,把每个人都变成中位数会产生一个价值,把这些价值加起来就是总共的价值啦。代码:StatusAcceptedTime2176msMemory9104kBLength572LangC++#include <ios... 继续阅读 »
ACM

HDU 6016 - Count the Sheep(小思维)

HDU 6016 - Count the Sheep(小思维)
给出一些成对的公羊与母羊,他们之间是朋友关系(给出的关系是双向的),请列出有多少种四只羊之间的关系(这个关系是单向的,也就是说顺时针转一圈和逆时针转一圈来数都算不同的关系)。一开始直接dfs暴力,然后无限RE(vector数组开小)和TLE,后来直接计算,以当前点的边减去1再乘以相邻点的边数减去1的值之后再乘以2就是他们的所有关系数就AC了。代码:StatusAcceptedTime670msMe... 继续阅读 »
ACM

HDU 5969 扫雷(排列组合)

HDU 5969 扫雷(排列组合)
这题看似很难排列,但是递推一下就能发现规律(当然,我是看了题解,毕竟最近智商下线)。我们用一个数组dp[]模拟每列放置的地雷数,这样每列最多只能放置2个。枚举第一列的个数,然后通过第一个格子递推第二个格子,这样一直递推下去就行。题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=5965代码:StatusAcceptedTime218msMemory164... 继续阅读 »
ACM

SCU-2090 单色三角形(计数)

SCU-2090	 单色三角形(计数)
题意:找具有三条边颜色相同的三角形数这个题数据比较水,直接暴力也能过,不过@freeloop建议我们用单色三角形理论去计算,于是看了别人的题解。大致就是先求出非单色三角形数目,然后用总的减去非单色三角形。总的数目是C(n,3),非单色三角形我们只需要遍历每个点,看看他的边是否具有同样颜色(这里要注意除以2,因为遍历三角形另外点的时候具有重复计算)就可以了。题目地址:http://acm.scu.e... 继续阅读 »
ACM

BZOJ-1008 越狱(排列组合+快速幂)

BZOJ-1008 越狱(排列组合+快速幂)
题意:这个是中文,不用解释了吧。因为每个人有m种宗教可以信仰,那么一共有m^n种排列情况。而不发生越狱的情况只能是,第一个人选择m的一种,第二个人有m-1种选择,后面为了不同,都是m-1种选择,共m*(m-1)^(n-1)种。由于幂太大,达到连大数都存不下了,所以这里需要用到快速幂来计算。快速幂其实就是把一个带幂的数拆分一下,幂为偶数的时候可以除一半,把底数多一个,奇数的时候先拆一个出来使幂变成偶... 继续阅读 »