POJ1019 ---简单的数学找规律题

题目大意就是给你这一串数字$11212312341234512345612345671234567812345678912345678910123456789101112345678910……$（未列完）

要我们求出第$n$个数是多少(从左到右看)，例如第2个是1，第三个是$2$，第八个是$2$；

如果仔细观察这一串数字，可以发现他可以还分为很多小串，假设第i小串是$123……i$，假设第$i$小串所占的空间是$a_i$，则通过对比$a_i$与$a_{i+1}$发现，

第$i+1$串只比第$i$串多一个数，即$i+1$，故他们所占的空间差就是第$i+1$所占的空间。

对任意一个数所占的空间很好求，即 $\left \lfloor \log_{10}k+1 \right \rfloor$；

然后就可以求出每一个串的起始位置，通过与n比较就可以确定n出现在那一个串里，最后在求出$n$在这个串里的相对位置，就可以求出该题的解

poj1019 Number Sequenceview raw
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
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int a1[32000] ;        //用来存储每一个串所占的空间
__int64 a[32000] ;    //用来存储每一个串的起始位置
int num[150000];    //打印出最大的一个串
int main()
{
    int i;
    a1[0]=0 ;
    a1[1]=1;
    for ( i = 2 ; i < 32000 ; i ++ )
        a1[i] = a1[i-1] + (int)log10(1.0*i)+1;    //推导详见上文
    a[0]=1;
    for ( i = 1 ; i < 32000 ; i ++ )
        a[i]=a[i-1]+a1[i-1];                    //上一个串的起点加所占空间就是下一个串的起点                
    int k = 1;
    for ( i = 1 ; i < 31300 ; i ++ )
    {//打印最大的一个串
        char str[20];

        str[0]='0';
        int ti = i ;
        int len = 0 ;
        while (ti)
        {
            str[len]=ti%10+'0';
            ti=ti/10;
            len++;
        }
        while ( len -- )
        {
            num[k]=str[len]-'0';
            k++;
        }
    }
    int t;
    cin >> t;
    while ( t-- )
    {
        int mn;
        cin >>mn;
        for ( i =1; i < 32000 ; i ++ )
            if ( a[i]>=mn )
                break;
        if ( a[i] ==mn )
            cout<<1<<endl;
        else
        {//mn-a[i-1]+1就是其在第i-1个串里的相对位置
            cout<<num[mn-a[i-1]+1]<<endl;
        }
    }
    return 0;
}

展开全文 >>

poj1050经典DP的二维形式

题目大意就是给出一个n×n的矩阵，要求在里面找一个子矩阵，使得子矩阵中的元素和是最大的，输出这个最大的元素和

解决这题首先要会求给n个数，问这n个数的最大子串和是多少？这一道题就是把上面的问题拓展到了二维，但解决方法类似

枚举所有的行组合，将这些行压缩成一个数列，进行上述操作就可以了

poj1050 To the Maxview raw
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>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int a[105][105];
int sum[105];
int dp[105];
int main()
{
    int n ;
    while ( cin >> n )
    {
        int i , j , k , t;
        for ( i = 0 ; i < n ; i ++ )
            for ( j = 0 ; j < n ; j ++ )
                cin >> a[i][j] ;
        int sumall = - (1 << 30 );
        for ( i = 0 ; i < n  ; i ++ )
        {
            int sumdp;    
            for ( t = i + 1 ; t <= n ; t ++ )
            {
                for ( j = 0 ; j < n ; j ++ )
                {
                    int sumi = 0 ;
                    for ( k = i ; k < t ; k ++ )
                    {
                        sumi += a[k][j] ;
                    }
                     sum[j] = sumi ;
                    if ( j )
                        sumall = max ( sumall , sumdp = max ( sumdp + sum[j] , sum[j] ) ) ;
                    else
                       sumall = max ( sumall , sumdp = sum[j] ) ;
                }
            }
        }
        cout << sumall << endl ; 
    }
    return 0 ;
}

展开全文 >>

通过POJ1061青蛙的约会来谈扩展欧几里得算法

对于题目中的数据，详见下表

故，可得两只青蛙跳四次就可以在点3处相遇

对于这道题可以知道，当他们相遇时距离原点的位移是相等的，则假设青蛙跳了t次后，则他们相对于原点的位移是

A：$(x+mt）\bmod l$

B：$(y+nt）\bmod l$

则可以列方程$(x+mt) -(y+nt)=cl (c为整数)$

则变形得$(m-n)t-cl=y-x$;

题目要求的就是要使等式成立时最小时的正整数t

在解决这个问题前，我们首先就应该知道什么是扩展欧几里得算法

即找出一对整数$(x，y)$，使得$ax+by=gcd(a，b)$。

注意，这里的$x$和$y$不一定是正数，也可能是负数或者$0$.

more >>

展开全文 >>

POJ 1062 昂贵的聘礼 解题报告

题目描述的很清楚，关于答案的由来可以这样看，探险家花50买到编号4的物品，接着拿4和200金币买到编号3，然后拿着3和2000金币买到1，故总共花去了5250金币，并且交易中等级最高的是3，最低的是2，没超过1，故此发可行，故最少花费金币是5250.如果将题目的数据改为

1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 1 1
4 200
50 2 0

则答案不是5250了，因为刚才交易的顺序是4-3-1，而3的等级是1，1的等级是3，两者等级差超过了m（=1），故不能这样交换，则此时交换的顺序应该为4-2-1，此时花费最少金币为8250.

昨天开始做这道题目时感觉好难，因为，还没怎么写图论题，想套模板也不知道怎么套，就是有点思路，但不会写，也许是对图论题目不是很熟，今天AC了几道基本题后，再来做这题，有点感觉了，一次AC

要AC这道题，就要所选路径的等级差小于m，解决这个问题我的办法就是将等级限定在某个闭区间[a,a+m]，明显第一个人的等级必须要在这个区间内。然后就是选择Dijkstra的算法，每次加入点时就更新外面的点的最短路，注意，不在闭区间的点就不用考虑。先前没写过该算法，但好像Prim算法和这好像，就将Prim算法初略该变了一下，同样AC了

poj1062 昂贵的聘礼view raw
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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int cost[100],lowcost[100],level[100];    //各点的的花费，从0到各点最小费用，各点的等级
int change[100][100];                    //拿i换j时还额外要的金币
bool vis[100];                            //确定i是否还要访问
int main()
{
    int m , n ;
    while ( cin >> m >> n ) 
    {
        int i , j , k ;
        for ( i = 0 ; i < n ; i ++ )
            for ( j = 0 ; j < n ; j ++ )
                change [i][j] = ( i == j ? 0 : ( 1 << 20 ) );//初始化，如果不能交换就为最大
        for ( i = 0 ; i < n ; i ++ )
        {//输入数值
            int a , b , c ;
            cin >> a >> b >> c;
            cost[i]=a;
            level[i]=b;
            for ( j = 0 ; j < c ; j ++ )
            {
                int d , e ;
                cin >> d >> e;
                change[i][d-1]=e;
            }
        }
        int minans = (1<<20);//定义结果
        for ( k = level[0] - m ; k != level[0] + 1 ; k ++ )
        {//定义区间早[k，k+m]
            memset(vis,true,sizeof(vis));    //初始化标记数组
            vis[0]=false;                    //0不用访问了
            int sum = 0 ;
            for ( j = 0 ; j < n ; j ++ )
            {
                if ( level[j]<k || level[j]>k+m)
                {//如果不在该区间了。就不用访问了
                    sum ++ ;
                    vis[j]=false;
                }
            }
            for ( i = 0 ; i < n ; i ++ )
                    lowcost[i] = change[0][i] + cost [i] ;//初始化各点到0的最短路（所发金币）
            for ( j = 1 ; j < n - sum ; j ++ )
            {
                int one ;
                int ans = (1 << 30);
                for ( i = 0 ; i < n ; i ++ )
                {//寻找花费金币最少的一点
                    if( vis[i] && ans > lowcost[i] )
                    {
                        ans = lowcost [i] ;
                        one = i;
                    }
                }
                vis [one] =false;
                for ( i = 0 ; i < n ; i ++ )
                {//更新各点的最短路
                    if ( lowcost [i] >( lowcost [one]- cost [one ] +change [one][i] + cost [i]) )
                        lowcost [i] = lowcost [one]-cost [one ] +change [one][i] + cost [i] ;
                }
            }
            for ( j = 0 ; j < n ; j ++ )
            {//遍历从0到n的最短路，寻找所花金币最小的点
                if ( level[j]>=k && level[j]<=k+m&&minans > lowcost [j] )
                    minans = lowcost [j] ;
            }
        }
        cout<<minans<<endl;
    }
    return 0;
}

展开全文 >>

poj1080 人类基因配对

是就是求两基因的相似度，先要在每个基因对中加入若干空格，然后再依次加上匹配度，详见上表，则相似度就是最大的匹配度和

例如对于测试数据一，加上空格则变成

AGTGAT–G
-GT—-TAG

则相似度就是$(-3)+5+5+(-2)+5+(-1)+5=14$，可以证明这是最大的，故为所求

此题为dp,详见代码

poj1080 Human Gene Functionsview raw
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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int map[][5]={    {5,-1,-2,-1,-3},
                {-1,5,-3,-2,-4},
                {-2,-3,5,-2,-2},
                {-1,-2,-2,5,-1},
                {-3,-4,-2,-1,0} };
char str1[105];
char str2[105];
int f[256];
bool vis[105][105];
int ans[105][105];
int DFS ( int x , int y )
{

    int i ;
    int xy=0;
    if ( x == -1 )
    {
        for ( i = 0 ; i <= y ; i ++ )
            xy += map[str2[i]][4] ;
        return xy ;
    }
    if ( y == -1 )
    {
        for ( i = 0 ; i <= x ; i ++ )
            xy += map[str1[i]][4] ;
        return xy ;
    }
    if ( vis[x][y] ) 
        return ans[x][y] ;
    vis[x][y]=true;
    ans[x][y] = max ( DFS ( x - 1 , y - 1 ) + map[str1[x]][str2[y]] , max ( DFS(x,y-1)+map[4][str2[y]] , DFS(x-1,y)+map[str1[x]][4] )) ;
    return ans[x][y] ;
}
int main()
{
    f['A']=0;
    f['C']=1;
    f['-']=4;
    f['G']=2;
    f['T']=3;
    int t ;
    cin >> t ;
    while ( t -- )
    {
        int i , j ;
        int len1 , len2 ;
        cin >> len1 >> str1 ;
        for ( i = 0 ; i < len1 ; i ++ )
            str1[i]=f[str1[i]];

        cin >> len2 >> str2 ;
        for ( i = 0 ; i < len2 ; i ++ )
            str2[i]=f[str2[i]];
        memset ( vis , 0 , sizeof ( vis ) ) ;
        cout << DFS(len1-1,len2-1) << endl ;
    }
    return 0;
}

展开全文 >>

poj1088记忆化搜索

就是从各点进行搜索，并用以数组记录搜索的结果，一遍下次搜索该处时再用
然后遍历一下该数组，找到最大的一个元素

poj1088 滑雪view raw
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
#include<iostream>
#include<cstdio>
using namespace std;
int map[105][105];
int f[][2]={
	{1,0},
	{0,1},
	{-1,0},
	{0,-1}
;
int vis[105][105] ;
int m , n ;
int DFS ( int x , int y )
{
    if ( vis[x][y] != -1 )
        return vis[x][y] ;
    int i ;
    int sum = 1 ;
    for ( i = 0 ; i < 4 ; i ++ )
    {
        int s = x + f[i][0] ;
        int t = y + f[i][1] ;
        if ( s < 0 || t < 0 || s >= m || t >= n )
            continue;
        if ( map[s][t] >= map[x][y] )
            continue;
        sum = max ( sum , DFS ( s , t ) + 1 ) ;
    }
    vis[x][y] = sum ;
    return sum ;
}
int main()
{
    while ( cin >> m >> n )
    {
        int sum = 0;
        int i , j ;
        for ( i = 0 ; i < m ; i ++ )
            for ( j = 0 ; j < n ; j  ++ )
                cin >> map [i][j] ;
        memset ( vis , -1 , sizeof ( vis ) ) ;
        for ( i = 0 ; i < m ; i ++ )
            for ( j = 0 ; j < n ; j  ++ )
                sum = max ( sum , DFS ( i , j ) ) ; 
        cout << sum << endl ;
    }
    return 0 ;
}

展开全文 >>

POJ 1125 Stockbroker Grapevine 解题报告

题目大意是股票经纪人要在一群人中散布一个谣言，而谣言只能在亲密的人中传递，题目各处了人与人之间的关系及传递谣言所用的时间，要求程序给出应以那个人为起点，可以在最短的时间内让所有的人都得知这个谣言。要注意从a到b传递的时间不一定等于从b到a的时间，如果没有方案能够让每一个人都知道谣言，则输出”disjoint”。（有关图的连通性，你懂得！但好像不用考虑这种情况一样能AC，只能说测试数据有点小水！）

题目数据的输入第一行为n，代表总人数，当n=0时结束程序，接着n行，第i+1行的第一个是一个整数t，表示第i个人与t个人的关系要好，接着有t对整数，每对的第一个数是j，表示i与j要好，第二个数是从i直接传递谣言到j所用的时间，数据的输出是两个整数，第一个为选点的散布谣言的起点，第二个整数时所有人得知谣言的最短时间

例如，对于数据1，可知如果从3开始传播，则1，2得知谣言的时间都是2，所用的时间比从1，2开始传播所用的时间要短，故程序的输出时3 2；

poj1125 Stockbroker Grapevineview raw
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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int inf = (1 << 20);    //最大值
int d[105][105];
struct prog
{
    int x,y,d;    //定义起点，终点，所用时间
};
int main()
{
    int n;
    while(cin>>n,n)
    {
        int i,j;

        //先将路径初始化，让d[i][i]=0,d[i][j]=inf;i =/= j;
        for(i=0;i<105;i++)
        {
            for(j=0;j<105;j++)
            {
                if(i==j)
                    d[i][j]=0;
                else
                    d[i][j]=inf;
            }
        }

        //根据输入的数据构造路径，注意题目的起点和终点范围是1……N，而数组是从0开始的，故要把所给的节点-1
        for(i =0;i<n;i++)
        {
            int m;    //从i出发亲密人的个数
            cin>>m;
            for ( j = 0 ; j < m ; j ++)
            {
                int a, b ;        //与i亲密的人及传递谣言的时间
                cin>>a>>b;
                d[i][a-1]=b;
            }
        }

        //Floyd算法，你懂的
        for ( int k = 0 ; k < n ; k ++ )
        {
            for(i = 0 ; i < n ; i ++)
            {
                for ( j = 0 ; j < n ; j ++ )
                {
                    if(d[i][j]>d[i][k]+d[k][j])
                        d[i][j]=d[i][k]+d[k][j];
                }
            }
        }

        prog dij ,pij;//保存谣言散布的地点，终点，及时间，其中dij表示的是题目要求的，而pij表示的从固定点出发散布到某点的最长时间
        dij.d=inf;//初始时将时间初始化为最大（因为要求的是从任意点出发让所有人知道谣言的最短时间）
        for ( i = 0 ; i < n ; i ++ )
        {
            pij.d=0;//将从i散布谣言所用的时间初始化为0（因为此处要求的是从i出发散布谣言的最大时间）
            for ( j = 0 ; j < n ; j ++ )
            {
                if(pij.d<d[i][j])
                {//如果找到从i到j所用的时间要长与目前找到的从i出发用时的时间，则更新pij
                    pij.d=d[i][j];
                    pij.x=i;
                    pij.y=j;
                }

            }
            //如果从i出发用的时间比目前找到的用的最长时间还要短，则更新dij
            if(dij.d>pij.d)
                dij=pij;
        }
        if(dij.d>=inf)//如果dij还一直是最大值，说明并不能让全部人得知谣言，则输出disjoint。但数据比较水，这个判断可省略 Orz
            cout<<"disjoint"<<endl;
        else//输出起点和时间，注意要将起点标号+1
            cout<<dij.x+1<<' '<<dij.d<<endl;
    }
    return 0;
}

展开全文 >>

poj1141 Brackets Sequence(经典DP) 解题报告另附官方测试数据

好久没写解题报告了！
这题的意思很简单，lrj的《算法艺术和信息学竞赛》里动态规划篇的第一个例题。就是给出一个括号串，求出最小的一个规格串，使得括号串是规格串的字串，如果有多个，因为是Special Judge，只用写出一个。一个串属于规格串要求满足下列条件之一

这题一眼就可以看出是DP，因为根据定义，一个问题可以划分为更小的子问题，如果对dp比较熟的话，求加括号数的转移方程可以很容写出，关键是括号家的位置怎么处理记录。我事这样处理的：
另开一个数组，记录dp分成更小的子问题的过程，这个数组的值分两部分，xxxy，我们用个位数表示划分子问题的情况，如果y是-1，表示是去掉两边的括号，y是8表示分裂成两部分。而前面的xxx部分表示划分的区域，最后，开始递推，输出括号的位置。这题有一个trick，就是最后一组数据是空串，而用scanf读取字符串会wa。详细看代码和测试数据

poj1141 Brackets Sequenceview raw
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))

char s[200];
int dp[200][200];
int ac[200][200];//记录放的位置  表示是xxxy  xxx表示参照点 y表示方的括号种类和具体方位 
				//  当y为-1时表示两边去括号  当为8时分开  党为0-3表示括号的种类  详看printto函数
char to[255];	//括号对应转换成整数  方便存储
void printto(int k)
{
	switch(k)
	{
	case 0:printf(")");break;
	case 1:printf("(");break;
	case 2:printf("]");break;
	case 3:printf("[");break;
	}
}
void print(int i,int j)
{
	if(j<i)
		return ;
	if(ac[i][j]==-1)
	{//属于(S)或[S]类型    则先打印正括号 在打印S  最后打印反括号
		printf("%c",s[i]);
		print(i+1,j-1);
		printf("%c",s[j]);
		return ;
	}
	if(ac[i][j]%10==8)
	{//属于AB  分别打印AB
		print(i,ac[i][j]/10);
		print(ac[i][j]/10+1,j);
		return ;
	}

	//其他就属于(S ,[S ,S] ,S)类型  根据括号的位置打印
	if(ac[i][j]/10==i)
	{//属于(S ,[S 类型  先打印正反括号 再打印S
		if(to[s[i]]<2)
			printf("()");
		else
			printf("[]");
		print(i+1,j);

	}
	else
	{//属于S] ,S)类型 先打印S 再打印正反括号
		print(i,j-1);
		if(to[s[j]]<2)
			printf("()");
		else
			printf("[]");
	}
	return ;

}
int main()
{
	to['(']=0;to[')']=1;to['[']=2;to[']']=3;
	while(gets(s))
	{//因为测试数据中有空串  不能用scanf读取字符串，很多人就是wa在这里
		int i,j,k;
		int len=strlen(s);
		zero(dp);
		zero(ac);
		for(i=0;i<len;i++)
		{//初始化
			dp[i][i]=1;
			ac[i][i]=i*10+to[s[i]];
		}
		for(j=1;j<len;j++)
		{
			for(i=0;i+j<len;i++)
			{
				if((to[s[i]]^to[s[i+j]])==1&&((to[s[i]]%2)==0))
				{//如果能够表示成（S）和[S]情况的话
					if(j!=1)
						dp[i][i+j]=dp[i+1][i+j-1];
					else
						dp[i][i+j]=0;
					ac[i][i+j]=-1;
				}
				else
				{
					//表示成(S或者[S  则需要在i位置补全为()S或者[]S
					dp[i][i+j]=dp[i+1][i+j]+1;
					ac[i][i+j]=(i)*10+to[s[i]];
					if(dp[i][i+j]>dp[i][i+j-1]+1)
					{//表示成S)或者S]  则需要在i位置补全为S()或者S[]  ac记录最后一位的数字
						dp[i][i+j]=dp[i][i+j-1]+1;
						ac[i][i+j]=(i+j)*10+to[s[i+j]];
					}
				}
				//划分成A B 两部分向更小的部分递推  此时ac数组记录分开的位置
				for(k=i+1;k<i+j-1;k++)
				{
					if(dp[i][i+j]>dp[i][k]+dp[k+1][i+j])
					{
						dp[i][i+j]=dp[i][k]+dp[k+1][i+j];
						ac[i][i+j]=k*10+8;
					}
				}
			}
		}
		//打印结果
		print(0,len-1);
		printf("\n");
	}
    return 0;
}

展开全文 >>

POJ1142Smith Numbers一道简单的数学题

题目大意就是要你找一个大于n的和数，并且满足他的各位的和与他所有的质因子的各位的和相等的最小的一个数，即此题的Smith Number

例如对于$4937774$，比他大的第一个数是$4937775$

因为$4+9+3+7+7+7+5=42$

又$4937775=3 \times 5 \times 5 \times 65837$

而$3+5+5+6+5+8+3+7=42$

故$4937775$是题目要求的答案。

这是一道纯数学题，可以通过暴力直接得到答案，因为这样的数分布比较密，

不过在做这题时学到了很好的一个思想，分治法，详见代码；

提交1次就A了，刚开始时想复杂了，准备筛选做的，看了一下讨论，好像没必要，可直接暴力

poj1142 Smith Numbersview raw
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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
bool isprime (int k)
{//判断是否是素数
    int t = sqrt ( k + 0.5 );
    for ( int i = 2 ; i <= t ; i ++ )
        if ( k % i == 0 )
            return false;
    return true;
}
int sum(int k)
{//求出该数各位上的和
    int i , s;
    s = 0 ;
    while ( k != 0 )
    {
        i = k % 10 ;
        s += i ;
        k = k / 10 ;
    }
    return s;
}
int cut (int k )
{//分治法思想，如果是素数，就返回sum，否则，就将该数分成两部分，再来求各部分的质因子的sum
    if ( isprime(k) )
        return sum (k);
    for ( int i = (int) sqrt (k + 0.5) ; i >1 ; i -- )
        if ( k % i == 0 ) 
            return cut (i) + cut (k / i) ;
}
int main()
{
    int n;
    while ( cin >> n , n )
    {
        while ( n ++ )
        {
            if (!isprime(n)&&sum(n)==cut(n))
                break;
        }
        cout<<n<<endl;
    }
}

展开全文 >>

poj1191棋盘分割(动态规划)

黑书上面动态规划篇的第二道例题，题目大意很简单，可以记忆化搜索或dp做。最近在训练dp，直接dp做了，但记忆化搜索更简单。黑书上面的动态规划转移方程也写得很简单，用五层for循环嵌套。我的方程和他的略有不同，但大体意思是一样的！

$dp_{kx_{1}y_{1}x_{2}y_{2}}$为下列式子中最小的一个

$dp_{(k-1)x_{1}y_{1}ay_{2}} + dp_{0(a+1)y_{1}x_{2}y_{2}}$ 其中$x_{1}≤a﹤x_{2}$
$dp_{(k-1)(a+1)y_{1}x_{2}y_{2}} + dp_{0x_{1}y_{1}ay_{2}}$ 其中$x_{1}≤a﹤x_{2}$
$dp_{(k-1)x_{1}y_{1}x_{2}a} + dp_{0x_{1}(a+1)x_{2}y_{2}}$ 其中$y_{1}≤a﹤y_{2}$
$dp_{(k-1)x_{1}(a+1)x_{2}y_{2}} + dp_{0x_{1}y_{1}x_{2}a}$ 其中$y_{1}≤a﹤y_{2}$

然后就是5个嵌套的for循环，这题还有一个问题，不知道为什么，我之前用int和__int64都wa了，改成long double才ac了，难道卡在精度上？

poj1191 棋盘分割view raw
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
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))

int a[10][10];
int sum[10][10];
long double dp[20][10][10][10][10];
long double count(int x,int y,int m,int n)
{
	long double ans= __int64(sum[m][n]-sum[m][y]-sum[x][n]+sum[x][y]);
	return ans*ans;
}
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		int i,j,k;
		zero(sum);
		int num=0;
		for(i=1;i<=8;i++)
		{
			for(j=1;j<=8;j++)
			{
				scanf("%d",&a[i][j]);
				sum[i][j]=sum[i-1][j]-sum[i-1][j-1]+sum[i][j-1]+a[i][j];
				num+=a[i][j];
			}
		}
		int x,y;
		for(i=1;i<=8;i++)
			for(j=1;j<=8;j++)
				for(x=i;x<=8;x++)
					for(y=j;y<=8;y++)
						dp[0][i][j][x][y]=count(i-1,j-1,x,y);	
		for(k=1;k<n;k++)
		{
			for(i=0;i<=8;i++)
			{
				for(j=0;j<=8;j++)
				{
					for(x=1;x+i<=8;x++)
					{
						for(y=1;y+j<=8;y++)
						{

							int t;
							dp[k][x][y][x+i][y+j]=long double((1)<<30);
							for(t=x;t<x+i;t++)
							{
								dp[k][x][y][x+i][y+j]=min(dp[k][x][y][x+i][y+j],dp[k-1][t+1][y][x+i][y+j]+dp[0][x][y][t][y+j]);
								dp[k][x][y][x+i][y+j]=min(dp[k][x][y][x+i][y+j],dp[k-1][x][y][t][y+j]+dp[0][t+1][y][x+i][y+j]);
							}
							for(t=y;t<y+j;t++)
							{
								dp[k][x][y][x+i][y+j]=min(dp[k][x][y][x+i][y+j],dp[k-1][x][y][x+i][t]+dp[0][x][t+1][x+i][y+j]);
								dp[k][x][y][x+i][y+j]=min(dp[k][x][y][x+i][y+j],dp[k-1][x][t+1][x+i][y+j]+dp[0][x][y][x+i][t]);
							}
						}
					}
				}
			}
		}
		long double ans=1.0*dp[n-1][1][1][8][8]/n-long double(1.0*num/n)*long double(1.0*num/n);
		printf("%.3lf\n",sqrt(ans));
	}
    return 0;
}

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

小龙少，年二十有二。始从文，连考而不中。遂习武，练武场上发一矢，中鼓吏，逐之出。改学IT，自建一变量，用之，烫烫烫烫烫烫烫烫烫烫！