1,有一个连起来的项链,每个珠子都有一种颜色(所有颜色共有m种),珠子共有n个,需要给出一个最小的长度l,从某个位置开始连续l个,包含了所有的m种颜色。 从任意位置断开后变成链,处理时最后求余在化为圆形。 最简单的方法枚举,但是需要O(n3) 因此考虑. color[x],为地x个珠子的颜色。 若记s(j,i)为起点为j,长度为i的颜色集合。 ans[j][i]为从j长度为i的颜色个数。 idx=j+i-1>n ? i+j-1%n+1;i+j-1; 若color[idx] not in s(j,idx-1); ans[j][idx]=ans[j][idx-1]+1; s[j][idx]=s[j][idx-1] s[j][idx] push color[j] 否则 ans[j][idx]=ans[j][idx-1]; s[j][idx]=s[j][idx-1] 此时复杂度接近时间O(n2),空间O(n2),如果用set类则空间复杂度为O(n2longn),难以承受。 此时需要使用BitSet. 继续阅读 >>


张续 15/10/23 23:04:04
1.现在将,有颜色的球放在一条直线上,球的颜色只有红色,黑色,并且每种球都是无限多的。如过现在一行球共有n个,那么没有三种相同颜色球相连的共有多少种? 当前球数为n时。 An 前两种球颜色相同。Bn 前两种球颜色不同。 我的思路:递推 A3 = B3 = 2; An = B(n-1)(n>3);Bn = A(n-1) + B(n-1); #include <iostream> using namespace std; int main(){ int an=2,bn=2; int i=2,n,tmp; for(cin>>n ; i<n ;i++){ tmp = an; an = bn; bn = an + bn; } cout << an + bn << endl; return 0; } 2.有一个数组序列,共有n个数字,先给出一个sum,需要得到所有的数字序列中的两个数a,b,有a+b = sum。 我的思路: 继续阅读 >>


张续 15/10/23 22:40:02
有N个灯放在一排(编号从1到m),如果对灯执行n此i操作(i = 1,2,3....n),对于一次i操作的定义如下,将一次i操作定义为,(将编号为i的倍数的灯进行翻转,开到关,关倒开),那么如果开始所有灯都是关闭的,那么进行n次操,之后,会有多少个灯是打开的。 我的思路: 解法一:模拟. #define max_n 10000001 int vis[max_n]; int solve_first(int n){ int i,j,count=0; memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++){ for(j=1;i*j<=n;j++){ vis[i*j]=!vis[i*j]; } } for(i=1;i<=n;i++){ count +=vis[i]; } return count; }解法二: (1)被操作奇数次的灯状态发生改变,偶数次数状态不变,因此只需求编号为i的灯的操作次数的奇偶性。 不难证明i 当i是 继续阅读 >>


张续 15/10/23 13:20:12
1.一维空间之中(L),存在若干条线,表示为(l,r)[r>=l],指从l到r的线,这条线长度为r-l,给定n条这样的线,他们之间如果相交,那么长度就是最后的表现形式,如: (2,8) (1,5) ,则长度为8-1+1=9。  (3,6) (3,4) ,侧长度为6-3+1=4。 这样,求出所有的n条线的总长度。 输入: n,以后有n个输入每一个为a,b (b>=a) 但是不保证两次输入间的位置关系。输出: 线段总长度。 我的思路: 首先考虑两个线段的情况,发现可能分离,或者合并,但是还有可能有新的线段在这两个线段之间使得原本分离的两条线段合并。因此需要确定可能合并的线段要先给线段按 起点排序,然后从前向后处理,这时分离的线段不能合并,而且合并线段只能和已处理的末尾点在最后的线段进行合并,然后替换最后的线段。重复直到所有线段处理完毕。 排序好的线段有三种情况; (1)新的线段与最后线段分开,对于总长增加度则为新的线段长度,并且新的线段为最后的线段。 (2)新的线段被最后线段包含,对于总长增 继续阅读 >>


张续 15/10/23 12:19:09
#include <stdio.h> #include <string.h> #define MAX_N 100000 #define INF (-(MAX_N)) typedef float Type; int ol,or; Type _min,_max,_sum,v; Type sumv[MAX_N],minv[MAX_N],maxv[MAX_N],addv[MAX_N],setv[MAX_N]; Type max(Type a,Type b){ return a > b ? a : b; } Type min(Type a,Type b){ return a < b ? a : b; } void initVal(){ _min = MAX_N; _max = -100; _sum = 0; } void maintain(int o,int l,int r){ 继续阅读 >>


张续 15/04/04 11:00:47
任何一个大于1的自然数n都可以携程都可以写成若干个大于等于2小于等于n的质数之和,并不只有一种形式.例如9就有四种形式. 9 = 2 + 5 +2 = 2 + 3 +2 +2 = 3 + 3 +3= 2+ 7 方法一: 直接进行搜索(输入限制很大). 方法二: 构造下列母函数. G(x) = (1+x^2+x^4+x^6+.....x^(x/2)) (1+x^3+x^6+x^9+...x^(x/3))*......... 说明: 对于没一部分 x^m (1 = x^0) 第 i 部分则是选择第i个质数pirme[i]的个数 最后只需要求得x^n项的系数即可. 然而对于求多个质数则使用筛法来求. 对于一个素数i,其所有的倍数都不是素数, 使用该方法进需要将所有x<n/2 的所有质数的倍数排除,则剩下的 m < n m!=x为质数. 给出代码: #include <cstring> #include <cstdio> #include <vector> us 继续阅读 >>


张续 15/03/23 20:53:32
1.我们将一个有序数组(n个元素)从i(号位置)之前放到n位置之后形成的数组为有序循环数组。 2.数组 1 2 4 5 6 7 8    的有序循环数组有   1 2 4 5 6 7 8 (元数组是位置0处的有序循环数组).   2 4 5 6 7 8 1    4 5 6 7 8 1 2   5 6 7 8 1 2 4   6 7 8 1 2 4 5    7 8 1 2 4 5 6   8 1 2 4 5 6 7 3.我们要在有序循环数组中找到一个元素出现的位置(此处假设每个元素出现次数小于等于一)。 a.顺序差 O(n)  b.(二次)二分查找O(2logn) ~ O(logn)。 此处先说明一下二分查找. 若数组有序那么我们取首个位置为l,最后位置为r,中间位置为m=(l+r) /2,要找的元素为val  l<=r时 若A [ m] ==val则找到. 若A[m]>val 则在左边找l=m-1; 若A[m]<val则在右边找r=m+1; 重复过程直到找到. 有下列. 在0 2 继续阅读 >>


张续 15/03/22 16:56:21
1.对抗搜索 在对弈中经常会遇到可能性很多而有没有规律的情况,这时可以对所有后续情况进行分析,选择当前对自己最有利的一中情况. 如果两方A,B进行对弈,计算现在局面的分数(对A和B),如果两方处于对立,那么一定在一方分数高的同时另一方分数会低( 每方都希望局面对自己有利),因此此时进计算A的分数,B的分数可以由A的分数反应(A高B低,A低B高),如果两个人足够 聪明(知道N局以后可能的所有局面,此时用搜索来列举),每一步都会选择对自己有利的后续局面进行操作.若果此时从结果像 最开始推,那么决策这一定会选择更有利的上一步进行来进行决策,而当前的所处换将则是由对方的上一步决策导致的. 现在记A的分数(决策效果)为分数,A希望自己获得更高的分数记MAX方,B希望自己能获得更高的分数(A获得更低的分数) 记做MIN方. 若果现在已经计算出了最下面一层的分值,由A操作那么A会对B创造的局面采取最优的决策(导致倒数第二层),以此操作,到上面的n次操作O(P) P=A,B 操作,那么 他知道自己的决策会形成怎样的 继续阅读 >>


张续 15/03/07 21:23:11
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct t_type{ int hight; int blance; int val; struct t_type * lchild; struct t_type * rchild; }node; node * clue[200]; int clue_index=0; int max(int a,int b){ return a > b ? a : b; } node* get_node(){ node* newnode = (node*)malloc(sizeof(struct t_type)); newnode->lchild = newnode->rchild = NULL; 继续阅读 >>


张续 15/03/06 13:02:46
1.在图中一条边包含有两个结点。 2.一个结点可能相关n条边 因此我们可以把每一个结点包含的边放到同意集合之中(此处已链表存放,此时用顶点v作为集合的表示,即为链表表头) 其中一个边,和该边具有的两个结点作为集合中的一个元素。 x nx n ny y,编号为n的边的相关的两个结点x,y,nx是指向下一个与x相关的元素,ny是指向与y相关的元素 按照上述方法讲一个无向图划分为n个顶点为标识的集合。 具体实验(建立(包含了插入) 和遍历) #include<stdio.h> #include<stdlib.h> #define max_n 100 typedef struct v{ int ismark; int u; struct v * nextu; int v; struct v * nextv; }vex; int m,n; vex* g[max_n]={NULL,NULL,NULL,NULL 继续阅读 >>


张续 14/12/02 11:51:31