- 博客(99)
- 收藏
- 关注
RSS订阅原创 2013年武科大蓝桥杯校内选拔赛 F gcd和lcm
基本思路还OK。。关键是我直接分解质因数 弄组合去了。。（而且我分解质因数由于素数打表有阴影，从未成功实现过，所以我分解质因数开始也写的暴力十足= =）没想到直接 k1、k2 互质，然后直接数个数n,输出2^n.最后百无聊赖，各种搞不好，导致我去弄gcd函数暴力，很明显的超时。。关键时刻我能说我 求最大公约数怎么写都忘了么T^T....我。。。官方题解
2013-11-14 08:30:26
1161
原创 Codeforces Round #208 (Div. 2) A_ Dima and Continuous Line
点都在一条直线上。输入点的横坐标。输入中相邻两点间有半圆弧。（输入时不按坐标大小而是坐标乱序）判断两点间构成的半圆弧是否相交。假设n个点中 x1 和 x2之间有半圆弧，x3 和 x4 之间有半圆弧。则当满足 程序注释中8种情况时相交。时间复杂度为O(N*N)#include#include#include#include#include#i
2013-10-26 07:40:07
1233
2
原创 poj 3026 Borg Maze (bfs+prim)
题意：在迷宫中找存在的外星人A撒。。开始是一个组织找，后来这个组织可以分裂成 很多组。求找到所有外星人的最小步数。（分裂后，步数计算为所有组织的步数和）思路：因为要保证每个外星人A都找到，加上组织所在起始点S，求最小步数。即求图中 n个点的最小生成树（n=外星人的个数+1）。 bfs找每两点间的距离。
2013-10-24 06:31:19
958
原创 poj 1789 Truck History (最小生成树）
把每个字符串看成点，i和j的距离就是i串和j串中不同字符的个数。#include#include#include#define INF 0x3f3f3f3fusing namespace std;char str[2010][10];int dis[2010],edge[2010][2010];bool vis[2010];int m,ans;int cmp(
2013-10-23 21:55:51
707
原创 hdu 4474 Yet Another Multiple Problem ( bfs + math)
题意：求给定数n的最小的倍数，使其中不包含给出的m个十进制数。状态太多了。。。参看别人的思路，就是在每一位上对可以出现的数进行枚举，然后bfs。。。直到出现第一个节点中m==0，就输出。每个节点记录三个值c：末尾的那个数字m：这个节点所代表的数字对n取模的值f：父节点对于一个节点，如果在其后面加一个数字i，那么新的m值=(m*10 + i
2013-10-21 23:25:08
844
2
原创 ural 1982. Electrification Plan (最小生成树）
#include#include#include#define INF 0x3f3f3f3fusing namespace std;int edge[110][110];int vis[110],dis[110];bool flag[110];int n,k,ans;void prim(){ int u=1,minw; for(int i=1;i<=n;i+
2013-10-21 12:57:22
851
原创 POJ 3461 Oulipo (kmp入门)
上数据结构才学KMP算法。。。刷一道练习题。。。#include#include#include#define M 1000000+10#define N 10000+10using namespace std;char w[N];char t[M];int next[N];int cnt;void get_next(int len){ int
2013-10-19 22:09:12
644
原创 Codeforces Round #205 (Div. 2) B. Two Heaps
题意：要把2*n个两位数分成两堆，使得第一堆上的和第二堆上的两个两位数组成四位数。 求怎么分能使构成的不同的四位数个数最多。分析：如果是2*n个不同的，每堆分n个，最多能组成 n*n个不同的四位数。 但是如果有相同的二位数，那么： 1、相同的两位数重复个数为2，则分在不同堆上构成的四位数多。
2013-10-12 19:50:38
921
原创 cf Round #202 (div.2) C ------------ Mafia
只是觉得这个题用二分枚举过真是太神了。。。还是发下 思路：在最小可能round数(玩家想玩的最大盘数)和最大可能round数(所有玩家想玩盘数的总和) 范围内二分枚举得到最少需要玩的盘数。 只要满足所有玩家不玩的盘数>=当前盘数 && 当前盘数>=玩家想玩的最大盘数。#include#include#in
2013-10-03 13:35:49
827
原创 Codeforces Round #203 (Div. 2) C------Bombs
1、只需要按距离原点的远近排序然后按照规则输出就可以了。昨天居然没看这么水的题= =！2、不过代码写得有点丑。。哎。。。#include#include#include#include#includeusing namespace std;struct node{ int x,y; int step;}t[100010];bool cmp(
2013-10-02 16:58:22
765
原创 Round #203 (Div. 2)B------Resort
思路：把出度大于1的点去掉，以每一个hotel为起点搜索找最长路径。链接：点击打开链接#include#include#includeusing namespace std;int len,fa[100010],sum[100010],maxpath,hotel[100010];int dfs(int x){ if(fa[x]==0) r
2013-10-02 10:37:01
817
原创 Round #203 (Div. 2) A------TL
1、题目链接：点击打开链接2、模拟可过，在100以内枚举也可过。3、昨天居然考虑错了。。。。。被HACK。。。。 我开始写的是 ：找正确解法中的最大值max1和最小值min1，找错误解法中的最小值min2。 if (max1> 2*min1 || min2 显然错了啊，max1是可以大于2*
2013-10-02 09:18:31
979
原创 uva oj 442
题意：一直矩阵的行和列，求给出的矩阵乘法表达式要做多少次基本元素的乘法。分析：stack的应用。1、格式控制题目已给出说明，是回车符。开始判断的时候习惯性的以' \0 ' 作为字符串的结束标志。2、开始没用stack,用了静态链表。3、复习了矩阵乘法的特性。4、数组存每组的信息时，因为多次使用，千万不能忘记清0。STL中的stack#in
2013-09-21 07:29:38
805
原创 uva oj 401
#include#include#includeusing namespace std;char str[100];int main(){ int i,j,flag1,flag2; while(scanf("%s",str)!=EOF) { printf("%s -- ",str); int len=strlen(str);
2013-09-12 21:34:44
727
原创 UVA OJ 457 - Linear Cellular Automata
#include#include#includeusing namespace std;int b[42],c[42];void show(){ for(int i=1;i<=40;i++) { if(b[i]==0) printf(" "); else if(b[i]==1) printf("."); else if(
2013-09-11 23:53:33
795
原创 uva oj 445
#include#include#includeusing namespace std;string ans;int main(){ char c; int i,sum=0; ans=""; int flag=0; while((c=getchar())!=EOF) { if(c=='!') a
2013-09-11 17:32:16
744
3
原创 uva oj 414
#include#include#includeusing namespace std;char s[30];int count[13];int main(){ int n,m,sum,i,j; while(scanf("%d",&n)&&n) { getchar(); memset(count,0,sizeof(count
2013-09-11 17:31:14
739
原创 uva oj 458
#include#include#includeusing namespace std;char in[100];int main(){ int i; while(scanf("%s",in)!=EOF) { for(i=0;in[i];i++) printf("%c",in[i]-7); printf(
2013-09-11 17:30:02
909
原创 uva oj 494
#include#include#include#includeusing namespace std;char s[100000000];int main(){ int i,len,count,flag; //while(fgets(s,100,stdin)!=NULL) while(gets(s)!=NULL) { flag=1;
2013-09-11 17:27:37
685
原创 uva oj 10300
#include#includeusing namespace std;int main(){ int T,i,n,a,b,c,sum; scanf("%d",&T); while(T--) { scanf("%d",&n); sum=0; for(i=0;i<n;i++) {
2013-09-11 17:27:34
732
原创 uva oj 490
#include#include#include#includeusing namespace std;char s[100][102];int main(){ int rear=0,i,j,len=0; while(gets(s[rear++])); for(i=0;i<rear;i++) { if(strlen(s[i])>le
2013-09-11 17:26:23
747
原创 uva oj 488
开始想的是反正每个波浪之间要空行，每个CAS的波浪之间也要空行。就想直接在没输出一个波浪就printf("\n");但是由于最后是以EOF结尾，所以如果这么写就会在最后一个CAS的最后一个波浪后多输空一行。所以应该改成用flag标记是不是该CAS中的最后一个波浪，在新CAS开始之前输出printf("\n")；#include#include#includeusing
2013-09-11 17:25:09
828
原创 UVA OJ 489
#include#include#includeusing namespace std;int vis[100];int main(){ int cas,i,sum,count,len,j,flag,f; while(scanf("%d",&cas)!=EOF) { if(cas==-1) break; char s1[100
2013-09-11 17:15:57
718
原创 Codeforces Round #199 (Div. 2) A ( 简单贪心 )
题目链接：点击打开链接先让我痛哭一下，居然跪在了水题上。。。。还是道水的贪心。。。。T^T。。。找规律找规律。。。。cf都是思维题，记住了！！！！大牛请自动跳过这篇博客，我是写给自己看的。。。。血的教训。。。多么痛的领悟。。。。分析：只可能是三种组合 ： 1 2 4 / 1 2 6 / 1 3 6先判断除了1 2 3 4 6外还有没有别的
2013-09-07 23:27:40
634
原创 hdu 4119 Isabella's Message ( 模拟 )
题目：点击打开链接题意：给一个n*n的矩阵，n为偶数，矩阵由小写字母和'.'组成，'.'表示空格，再给一个n*n矩阵，由'.'和'*'组成，'*'表示洞，'.'表示障碍。现在将2张卡片重合，将能看到的字符从上往下从左往右依次取出组成一个新单词。卡片可以顺时针旋转90度，再取出能看到的单词，一共有4个单词，4个单词再依次组成一个句子，因为卡片是连续转动的，所以4个单词首尾相连，任取一
2013-09-02 18:16:38
750
原创 hdu 1528 Card Game Cheater ( 二分图匹配 )
题目：点击打开链接题意：两个人纸牌游戏，牌大的人得分。牌大：2 hearts (红心) > spades (黑桃) > diamond (方块) > clubs (梅花)。问Eve 能得多少分。(每次得1分)分析：将Eve的每张牌与Adam的所有牌比较，与所有比这张牌小的Adam的牌连边。 然后求最大匹配。
2013-09-01 08:28:22
881
原创 POJ 2485 Highways ( MST 水题 )
题目：点击打开链接题意：求MST里的最长边。偶尔刷刷水题，娱乐一下= =！ans作全局变量居然忘了初始化，这可是多组数据啊。。笨蛋。。。代码：#include#include#include#define INF 0x3f3f3f3fusing namespace std;int g[510][510];int dis[510];int vis[
2013-08-31 20:29:30
645
原创 HDU 1498 50 years, 50 colors (行列匹配+最小顶点覆盖）
题目：点击打开链接题意：每个格子有不同颜色的气球用不同数字表示，每次可选某一行 或某一列来戳气球。每个人有K次机会。求最后哪些气球不能在 k次机会内被戳破。将这些气球的编号按升序输出。分析：行列匹配，每种颜色的气球都要判断，故dfs传参时加一个气球的 编号。感想：1、开始以为要按照最大匹配数按升序排列，昨
2013-08-29 09:55:42
757
原创 hdu 4081 Qin Shi Huang's National Road System (次小生成树的变形)
题目：Qin Shi Huang's National Road SystemQin Shi Huang's National Road SystemTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2049 Acc
2013-08-28 23:51:37
1028
原创 hdu 1507 Uncle Tom's Inherited Land* 【黑白染色+奇偶匹配(1X2的矩形覆盖)】
题目：Uncle Tom's Inherited Land*题意：有一个矩阵，被分成很多小方格。有些小方格有障碍，问最多能在矩阵中 放多少1*2的矩形。分析：黑白染色+奇偶匹配。 把格子染成国际象棋棋盘那种黑白相间。这样就能再矩阵中找出两个不相交的 点集进行二分匹配。把坐标(i,j）按照（i+j)的奇偶分类。每个
2013-08-28 20:30:58
1007
原创 hdu 4616 Game ( 经典树形dp )
GameTime Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 1436 Accepted Submission(s): 452Problem Description Nowadays, there are more and m
2013-08-27 22:51:19
1205
1
原创 hdu 1281 棋盘游戏 ( 行列匹配+求关键点 )
题目：棋盘游戏题意：某些格子若不放子，就无法保证放尽量多的“车”，这样的格子被称做重要点。 求重要点的个数。分析：先求最大匹配，然后拆边，看最大匹配数变不变，变则cnt++,最后cnt数就是 重要点的个数。代码：#include#include#includeusing namespace std;int g[110][
2013-08-27 19:10:13
964
原创 hdu 1179 Ollivanders: Makers of Fine Wands since 382 BC. (最大匹配)
题目：Ollivanders: Makers of Fine Wands since 382 BC.题意：匹配魔法师和魔杖。分析：二分图最大匹配。代码：#include#include#includeusing namespace std;int match[110];int g[110][110];int vis[110];int n,m;bool dfs(i
2013-08-27 18:04:16
751
原创 hdu 1151 Air Raid ( 最小路径覆盖 )
题目：Air Raid题意：一个城镇，所有街道都是单行的且不成环，每个街道与两个路口相连。 求最小数量的伞兵，使他们可以访问所有的路口。伞兵的降落位置不限。分析：实质就是求DAG（有向无环图）上最小路径覆盖。 拆点法建二分图：把所有节点拆成两个，X点集中的i和Y点集中的i'。如果 有边i--->j,则在二分图
2013-08-27 17:38:22
932
原创 hdu 1150 Machine Schedule ( 最小点覆盖 )
题目：Machine Schedule题意：有A、B两种机器，A机器有n(0~n-1)种模式,B机器有m种（0~m-1)模式。有k项工作可以 由A或者B机器中的某种模式完成。当前A、B机器都处于0模式。每次机器换模式都要重启。 问用两种机器完成K项工作所需的最小重启数。分析：最小点覆盖=最大匹配数。 对于每
2013-08-26 19:23:14
726
原创 HDU 1068 Girls and Boys (二分图匹配---最大独立集)
题目：Girls and Boys题意：有N个学生，已知每个学生与其他人的romantic关系，问有多少人没这个关系。 注：只有男生和女生可能有romantic关系。分析：男生和女生分别为两个点集。此题实质为求最大独立集。 最大独立集=顶点数-最大匹配数。(此题由于给出的是每个学生的romantic关系， 所以最大匹
2013-08-26 17:01:39
980
原创 hdu 4619 Warm up 2 ( 二分图最大匹配 )
题目：Warm up 2题意：有横竖两种方式放着的多米诺骨牌，相同方向的不可能重叠，但是横放和竖放的牌可能重叠。 移走重叠的牌使剩下的牌最多。分析：二分图匹配：最大独立点=顶点数-最大匹配数 横放的为一个点集，竖放的为一个点集。代码：
2013-08-26 14:21:44
812
原创 POJ 1330 Nearest Common Ancestors (LCA)
Nearest Common AncestorsTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 14836 Accepted: 7923DescriptionA rooted tree is a well-known data structure in com
2013-08-23 16:35:44
611
原创 poj 3264 Balanced Lineup (简单 RMQ )
Balanced LineupTime Limit: 5000MS Memory Limit: 65536KTotal Submissions: 29174 Accepted: 13743Case Time Limit: 2000MSDescriptionFor the daily milking, Farme
2013-08-23 16:31:09
595
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人