现在位置: 首页 > 算法 > 文章
2018年01月17日 算法 ⁄ 共 891字 暂无评论
记忆化搜索。。 对每个点能走的最远进行记录,如果走过,直接返回上一层。。 最后遍历找出最大值。。 <span style="font-size:18px;">#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; struct node{ int q,w; }s[104][105]; int a,b; int yy[105][105]; int map[4][2]={1,0,-1,0,0,1,0,-1}; int dfs(int c,int d) { if(s[c][d].w!=1)...
阅读全文
2018年01月17日 算法 ⁄ 共 1122字 暂无评论
先按di排序,(从小到大)。然后依次完成合同,若发现第i个合同无法在截止日期前完成,便从之前已经完成的任务中选一个aj最大的合同,付钱来使得这个合同尽快完成。 #include<cstring> #include<cstdio> #include<iostream> #include<queue> #include<algorithm> using namespace std; struct node {     int q;     int w;     bool operator < (const node& t) const {         return...
阅读全文
2018年01月17日 算法 ⁄ 共 382字 暂无评论
题意为求出只由0,1组成的并且是所给数倍数的数, 广搜。。 因为首位不能为0,因此必为1;所以搜索的下一层为上一层的10倍和10倍加1; #include<stdio.h> #include<string.h> #include<iostream> using namespace std; __int64 s[9999999]; __int64 r; void show(int q) { int i,j; s[0]=1; j=0; i=0; while(i>=j) { r=s[j]; if(r%q==0) { printf("%I64d\n",r); return ; } r=r*10...
阅读全文
2018年01月17日 算法 ⁄ 共 834字 暂无评论
一道比最基础的并查集有优化的题; l         并查集的优化 1、Find_Set(x)时 路径压缩寻找祖先时我们一般采用递归查找,但是当元素很多亦或是整棵树变为一条链时,每次Find_Set(x)都是O(n)的复杂度,有没有办法减小这个复杂度呢?答案是肯定的,这就是路径压缩,即当我们经过"递推"找到祖先节点后,"回溯"的时候顺便将它的子孙节点都直接指向祖先,这样以后再次Find_Set(x)时复杂度就变成O(1)了,如下图所示;可见,路径压...
阅读全文
2018年01月17日 算法 ⁄ 共 1131字 暂无评论
一个简单的单词翻译的题,我是使用字典序做的; 由于输入的问题 ,,WA,WA,,, 都是泪; #include <iostream> #include <string.h> #include <stdio.h> using namespace std; struct node{ int chile[26]; bool qq; char uu[11]; node() { qq=0; memset(chile,0,sizeof(chile)); memset(uu,0,sizeof(uu)); } }t[300001]; int index=1; void show(char ...
阅读全文
2018年01月17日 算法 ⁄ 共 839字 暂无评论
对于此问题有两种策略 1、最快的带最慢的和次慢的 2、最快和次快带最慢和次慢 此链接有详细解释点击打开链接 <span style="font-size:18px;"><span style="font-size:24px;">#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; int s[1050]; int main() { int a; scanf("%d",&a); for(int i=0;i<a;i++) s...
阅读全文
2018年01月15日 算法 ⁄ 共 837字 评论关闭
【题意】 有n个方块,现用红黄蓝绿四种颜色将他们染色,要求红色的方块和蓝色的方块个数均为偶数个,求方案数 mod 10007 【输入】 第一行一个t,表示有t组数据 每组数据一个数字表示n 【输出】 对于每组数据,输出一个输出表示方案数 用一个2位的2进制数表示红色方块和蓝色方块的奇偶性,发现染i个的方案数只跟染i-1个的方案数有关 所以可以用矩阵来搞一搞 program poj3734; type square=array [1..4,1..4] of longint; c...
阅读全文
2018年01月15日 算法 ⁄ 共 1369字 评论关闭
【题意】 侦察兵YYF要通过一条布有地雷的路,他从1出发,每次有p的几率前进1格,1-p的几率前进两个,现已知所有地雷的位置,求YYF不踩中地雷的几率 【输入】 多组数据 每组数据第一行n、p 接下来一行n个数字表示地雷的位置 【输出】 YYF不踩中雷的几率 f[i]表示在没有地雷的情况下,走i距离的几率 可得f[i]=f[i-1]*p+f[i-2]*(1-p) 类似斐波那契的一个公式 构造一个矩阵   p   1 1-p 0 这个矩阵的i次方的(1,1)既是f[i] 然后按...
阅读全文
2018年01月15日 算法 ⁄ 共 1460字 评论关闭
【题意】 将n个字符串任意顺序任意位置排列,求对应位置相同字母最多有多少个 【输入】 多组数据 每组数据第一行一个数n 接下来n行每行一个字符串 数据以n=0结束 【输出】 对于每组数据 输出一个数字表示答案 状压dp 因为n很小,所以可以用二进制表示每个字符串是否用过 program poj2817; var n,i,j,k,l,count,o:longint; tot:array [0..1] of longint; dl,last:array [0..1,0..1024] of longint; square:array [0.....
阅读全文
2018年01月15日 算法 ⁄ 共 899字 评论关闭
【题意】 给定n个立方体的高度,求最大矩形面积 【输入】 多组数据,数据以单独一行一个0结束 每组数据一行,第一个数字为n,接下来n个数字表示个立方体的高度 【输出】 对于每组数据,输出一个数表示最大矩形面积 单调栈 从左到右从右到左扫描两次,出栈的时候计算最大面积 很不幸的wa,思路不够全面 program poj2559; var tot,n,i,j,k,s,e:longint; now,ans:int64; h,stack:array [0..100001] of int64; begin re...
阅读全文