-
[综合] poj 3469 Dual Core CPU 最小割
题意: 有n个模块在A和B核组成的双核计算机上运行,各个模块在A,B核上的运行时间已知,另外有m个三元组(a,b,w),表示a模块和b模块如果不在一个核上运行要产生w的额外花销,求总的最小花销。 分析: 即把n个模块划分为两个集合,可用求最小割的方法解决。 代码: //poj3469 //sep9...
40
热度 -
[综合] poj 3386 Halloween Holidays 水题
判断下就好,直接贴代码。 //poj3386 //sep9 #include<iostream> usingnamespacestd; intA,a,B,b,P;intjudge() {if(A+B<=P)return1; if(A>B){swap(A,B);swap(a,...
0
热度 -
[综合] poj 2907 Collecting Beepers 邮递员问题暴力解法
题意: 给起点和n个点,求从起点出发经过这n个点每个点至少一次再回到起点的最短路。 分析: 类似邮递员问题,直接用STL枚举访问顺序暴力解决。 代码: //poj2907 //sep9 #include<iostream> #include<algorithm> using...
17
热度 -
[综合] poj 3782 Equal Sum Partitions 模拟水题
题意: 给一序列,把他划分为若干和相等的子序列,求可能的最小和。 分析: 暴力枚举就好,数据弱。 代码: //poj3782 //sep9 #include<iostream> usingnamespacestd; constintmaxN=10024; inta[maxN],n;in...
93
热度 -
[综合] poj 2756 Autumn is a Genius 高精度加减
题意: 求a+b。-10^50000<a,b<32768. 分析: 题目描述很猥琐,其实要用高精度的,用高精度加减模板。 代码: //poj2756 //sep9 #include<iostream> usingnamespacestd; constintmaxN=6000...
72
热度 -
[综合] poj 1719 Shooting Contest 二分图匹配的一种特殊情况
题意: 给一个r行c列的网格,其中一些格子可以选,要选一种方案,满足:1,每行至少选一个。2,每列恰好选一个。 分析: 二分匹配,特殊的地方在于每行至少要选一个。可以先做一次二分匹配,保证每行匹配好,然后对于没匹配的列任意匹配。 代码: //poj1719 //sep9 #include<i...
14
热度 -
[综合] poj 1208 The Blocks Problem 模拟+vector的使用
模拟水题,直接贴代码,主要是vector的使用。 //poj1208 //sep9 #include<iostream> #include<vector> usingnamespacestd; constintmaxN=32; vector<int>v[maxN...
52
热度 -
[综合] poj 2160 Box 模拟
题意: 给6块木板的长度,判断它们是否可以组成一个长方体。 分析: 模拟,首先判断6块木板是否可以分为3组完全相等的木板,再判断这3组木板是否能组成长方体。 代码: //poj2160 //sep9 #include<iostream> #include<algorithm>...
16
热度 -
[综合] poj 2484 A Funny Game 模仿对手做对称状态
水题,直接贴代码。 //poj2484 //sep9 #include<iostream> usingnamespacestd;intmain() {intn;while(scanf("%d",&n)==1&&n){if(n>2)printf("Bob\n...
8
热度 -
[综合] poj 3342 Party at Hali-Bula 判断二分图最大点独立集是否唯一
题意: 给一个二分图,判断最大点独立集是否唯一。 分析: 匈牙利算法。 代码: //poj3342 //sep9 #include<iostream> #include<string> #include<map> usingnamespacestd; const...
61
热度 -
[综合] poj 2663 Tri Tiling 状压dp
题意: 给3*N(N<=30)的矩形,问有多少种用1*2的小矩形铺满的方案。 分析: 同poj2411。 代码: #include<iostream> usingnamespacestd; __int64ans[32][4]; intn,m; __int64dp[2][1<...
55
热度 -
[综合] poj 3420 Quad Tiling 状压dp
题意: 给4*n(n<10^9)的大矩形,问有多少种用1*2的小矩形填满的方案。 分析: 又是铺瓷砖,不过这次n太大,不能再一个一个格的dp了。可以先算出相邻两行的状态转移,再用矩阵来加速n行的状态转移。 代码: //poj3420 //sep9 #include<iostream&g...
27
热度 -
[综合] poj 1704 Georgia and Bob nim博弈
题意: staircasenim。 分析; 水题,贴代码。 代码: //poj1704 //sep9 #include<iostream> #include<algorithm> usingnamespacestd; intn,p[1024];intmain() {int ...
73
热度 -
[综合] poj 1740 A New Stone Game nim变形
题意: 给n堆石子,两人交替,选择一堆石头后先拿去任意颗,再把剩下的放到其他任意堆,最先拿完所有石子赢,问先手必胜还是必败。 分析; 解决此类问题的一种的思路是先构造策略,然后判断此策略能否满足1.必胜态可到必败态。2.必败态无法到必败态。 代码: //poj1740 //sep9 #includ...
17
热度 -
[综合] poj 2311 Cutting Game nim与状态的grundy值
题意: 给一个w*h的矩形,两人轮流只能沿格子的边缘横剪或竖剪,最先剪出1*1的格子的人获胜,问先手必胜还是必败。 分析: 此题要求对grundy值有理解。一个全局状态的grundy值是对游戏中某个状态的有效的描述,grundy值描述了当前状态的所有后继状态,比如n堆石子的nim游戏的grundy值...
83
热度 -
[综合] poj 1220 NUMBER BASE CONVERSION 高精度进制转换
题意: 实现一个高精度数的进制转换。 分析: discuss里找到的精妙简洁模板。 代码: #include<iostream> usingnamespacestd; constintmaxN=600;charori[maxN],ans[maxN]; intt[maxN],A[maxN...
99
热度 -
[综合] poj 2230 Watchcow 欧拉回路
题意: 给一个图,求一种从点1出发,经过所有边恰好两次回到点1的方案,数据保证有解。 分析: 欧拉回路,改下次数就好了。 代码: //poj2230 //sep9 #include<iostream> #include<vector> #include<algorit...
84
热度 -
[综合] poj 3714 Raid 分治法求平面最近点对
题意: 给平面上的n个点,求两点间的最短距离。 分析: 分治法,保存点用vector会tle... 代码: //poj3714 //sep9 #include<iostream> #include<algorithm> #include<cmath> using...
6
热度 -
[综合] poj 2918 Tudoku 数独dfs
题意: 解数独游戏。 分析: 这道数独的数独直接dfs就能过。 代码: //poj2918 //sep9 #include<iostream> usingnamespacestd; chars[12][12]; intboard[12][12]; intCheckSquare[12][...
78
热度 -
[综合] poj 2967 Triangles 排序
题意: 给n跟木棒,问他们是否满足1.其中3根能组成三角形,2.不是任意3根都能组成三角形。 分析: 对于a<=b<=c,他们能组成3角形的充要条件是a+b>c,对整个数组排序后判断即可。这题用c++提交会超时,要用g++。 代码: //poj2967 //sep9 #inclu...
81
热度