welcome
0%

发表于 更新于 分类于

题目1：
问题描述
　　有一长度为N(1<=Ｎ<=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度为2，数目不限。要将这个长度为N的地板铺满，一共有多少种不同的铺法？
　　例如，长度为4的地面一共有如下5种铺法：
　　4=1+1+1+1
　　4=2+1+1
　　4=1+2+1
　　4=1+1+2
　　4=2+2
　　编程用递归的方法求解上述问题。
输入格式
　　只有一个数N，代表地板的长度
输出格式
　　输出一个数，代表所有不同的瓷砖铺放方法的总数
样例输入
4
样例输出
5
代码：

阅读全文 »

发表于 更新于 分类于

set的各成员函数列表如下:

  1. begin()–返回指向第一个元素的迭代器

  2. clear()–清除所有元素

  3. count()–返回某个值元素的个数

    阅读全文 »

发表于 更新于 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>
 
using namespace std;
#define MAXN 1011
 
int n,k;//n=strlen(s);

int Rank[MAXN];
int tmp[MAXN];
char s[MAXN];
int lcp[MAXN],sa[MAXN];
 
/*使用Rank对sa排序*/
bool cmpSa(int i, int j)
{
    if(Rank[i] != Rank[j])return Rank[i] < Rank[j];
    else
    {   /*以下的Rank[t]。已经是以t开头长度小于等于k/2的，
        sa[i]的名次。仅仅是以i开头的后缀。而长度不同*/
        int ri = i+k <=n? Rank[i+k]:-1;
        int rj = j+k <= n ? Rank[j+k]:-1;
        return ri <rj;
    }
}
 
/*计算SA*/
void consa()
{
    /*n=strlen(s);  必要时注明*/
    /*初始化sa和rank保证两点
        1、Rank[i]表示下标为i的是第几大，必须表示出相对大小。能够直接用字符代表其大小
        2、sa[1...n]值为1..n*/
    for(int i=0;i<=n;i++){
        sa[i]=i;Rank[i] = i < n?s[i]:-1;
    }
 
    /*利用长度为k的字符串对长度为2*k的字符串排序*/
    for(k=1;k<=n;k*=2)/*注意此代码中k是全局变量 别乱用,循环必须从1開始，由于0*2=0*/
    {
        sort(sa,sa+n+1,cmpSa);
        tmp[sa[0]] = 0; /*此时tmp仅仅是暂存rank*/
        for(int i=1;i<=n;i++){
            tmp[sa[i]] = tmp[sa[i-1]] +(cmpSa(sa[i-1],sa[i])?1:0);
            /*这一句非常关键，等号右側的sa[i]在此循环里表示第i大的长度小于等于k/2的字符串，
              从而求出第i大的长度小于等于k的字符串的sa[i]*/
        }
        for(int i=0;i<=n;i++){
            Rank[i] = tmp[i];
        }
    }
}
 
void construct_lcp()
{
    //n=strlen(s);
    for(int i=0; i<=n; i++)Rank[sa[i]]=i;
 
    int h=0;
    lcp[0]=0;
    for(int i=0;i<n;i++)
    {
        int j=sa[Rank[i]-1];
 
        if(h>0)h--;
        for(; j+h<n && i+h<n; h++)
        {
            if(s[j+h]!=s[i+h])break;
        }
        lcp[Rank[i]-1]=h;
    }
}
 
int main()
{
    int t,ans;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%s",s);
        n=strlen(s);
        consa();
        construct_lcp();
        for(int i=1;i<=n;i++)
        {
            ans+=n-sa[i]-lcp[i-1];
        }
        printf("%d\n",ans);
    }
    return 0;
 
    return 0;
}
阅读全文 »

发表于 更新于 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
using namespace std;
long long sum=0,f=1;
void judge(string s,int n)
{
	for(int i=0;i<n;i++)
	{
		int flag=1;
		for(int j=i+1;j<n;j++)
		{
			if(s[i]==s[j])
			{
				for(int k=j;k<n-1;k++)
				s[k]=s[k+1];
				n=n-1;
                j=j-1;
				flag++; 
			}	
		}
		f=f*flag;
	}
}
void per(string s,int n,int k)
{
	if(k>=n)
	{
		sum++;
	}
	else
	for(int i=k;i<n;i++)
	{
		swap(s[i],s[k]);
		per(s,n,k+1);
		swap(s[i],s[k]);
	}
}
int main()
{
	string s1;
	cin>>s1;
	judge(s1,s1.length());
	per(s1,s1.length(),0);
	cout<<sum;
}
阅读全文 »

发表于 更新于 分类于

求最大公约数有三种方法一种是辗转相除法，另一种是相减法，还有穷举法。
最大公倍数等于两数乘积/最大公约数。

  1. 辗转相除法
    有两种实现方法一种是递归法另一种是不使用递归
    递归：
1
2
3
4
5
6
int fun(int a,int b)
{
	if(a<b)
	std::swap(a,b);
	return b==0?a:fun(b,a%b);
}
阅读全文 »

发表于 更新于 分类于

#include <bits/stdc++.h>

这个头文件包含以下等等C++中包含的所有头文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream> 
#include <cstdio> 
#include <fstream> 
#include <algorithm> 
#include <cmath> 
#include <deque> 
#include <vector> 
#include <queue> 
#include <string> 
#include <cstring> 
#include <map> 
#include <stack> 
#include <set>
阅读全文 »

发表于 更新于 分类于

在C++中本质上有两种getline函数：

第一种：在头文件中，是iostream类的成员函数。
第二种：在头文件中，是普通函数。

第一种

istream& getline (char* s, streamsize n );
istream& getline (char* s, streamsize n, char delim );
作用是： 从istream中读取至多n个字符(包含结束标记符)保存在s对应的数组中。即使还没读够n个字符，
如果遇到delim 或 字数达到限制，则读取终止，delim都不会被保存进s对应的数组中。

阅读全文 »

发表于 更新于 分类于

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
try(int i)
 {
    if(i>n)
        输出结果;
    else
         {
       for(j = 下界; j <= 上界; j=j+1) // 枚举i所有可能的路径
        {
           if(fun(j)) // 满足限界函数和约束条件
             {
                a[i] = j;
                ... // 其他操作
                 try(i+1);
                 回溯前的清理工作（如a[i]置空值等）;
            }
         }
    }
阅读全文 »

发表于 更新于 分类于

vector的创建

vector q;

vector的使用

v1.push_back(p) 将数组p存放到v1中；
v2.pop_back(q) 将数组q从v2中删除；
v3。size（）大小判断；

阅读全文 »

发表于 更新于 分类于
  1. 初始化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//初始化
int fa[maxn];
void init(int n)
{
    for(int i=0;i<=n;i++)
    fa[i]=i;
}
//查找父节点
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
// 合并
void merge(int i,int j)
{
    fa[find(i)]=find(j);
}
阅读全文 »