The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

福大月赛 3月

自己太水了。。。呵呵

A题 打表。。。

#include<iostream>
using namespace std;

/*
int dp[10000001];
int rex[10000];
int rey[10000];

int main()
{
    freopen("out.txt","w",stdin);
    int cnt=0;
    int i,j;
    for(i=1;i<=10000000;++i)
        for(j=i<<1;j<=10000000;j+=i)
            dp[j] += i;
    for(i=220;i<=10000000;++i)
    {
            if(dp[i]<=10000000&&dp[dp[i]]<=10000000&&i==dp[dp[i]]&&i<dp[i])
            {
                cnt++;
                printf("%d,%d,",i,dp[i]);
            }
        
    }

    return 0;
    }
*/


int dp[200][2]={220,284,1184,1210,2620,2924,5020,5564,6232,6368,10744,10856,12285,14595,17296,18416,63020,76084,66928,66992,67095,71145,69615,87633,79750,88730,100485,124155,
122265,139815,122368,123152,141664,153176,142310,168730,171856,176336,176272,180848,185368,203432,196724,202444,280540,365084,308620,389924,319550,430402,356408,
399592,437456,455344,469028,486178,503056,514736,522405,525915,600392,669688,
609928,686072,624184,691256,635624,712216,643336,652664,667964,783556,726104,796696,
802725,863835,879712,901424,898216,980984,947835,1125765,998104,1043096,1077890,
1099390,1154450,1189150,1156870,1292570,1175265,1438983,1185376,1286744,1280565,
1340235,1328470,1483850,1358595,1486845,1392368,1464592,1466150,1747930,1468324,
1749212,1511930,1598470,1669910,2062570,1798875,1870245,2082464,2090656,2236570,
2429030,2652728,2941672,2723792,2874064,2728726,3077354,2739704,2928136,2802416,
2947216,2803580,3716164,3276856,3721544,3606850,3892670,3786904,4300136,3805264,
4006736,4238984,4314616,4246130,4488910,4259750,4445050,4482765,5120595,4532710,
6135962,4604776,5162744,5123090,5504110,5147032,5843048,5232010,5799542,5357625,
5684679,5385310,5812130,5459176,5495264,5726072,6369928,5730615,6088905,5864660,
7489324,6329416,6371384,6377175,6680025,6955216,7418864,6993610,7158710,7275532,
7471508,7288930,8221598,7489112,7674088,7577350,8493050,7677248,7684672,7800544,
7916696,7850512,8052488,8262136,8369864,8619765,9627915,9071685,9498555,9199496,
9592504,9339704,9892936,9363584,9437056}
;

int main()
{
    
int n,m;
    
while(scanf("%d%d",&n,&m)!=EOF)
    
{

        
int t=0;
        
int i;
        
for(i=0;i<=105;i++)
        
{

            
if(dp[i][0]>=n&&dp[i][0]<=m&&dp[i][1]>=n&&dp[i][1]<=m)
                t
++;
        }

        printf(
"%d\n",t);
        
for(i=0;i<=105;i++)
        
{

            
if(dp[i][0]>=n&&dp[i][0]<=m&&dp[i][1]>=n&&dp[i][1]<=m)
                printf(
"%d %d\n",dp[i][0],dp[i][1]);
        }



    }

    
return 0;
}



D题 Cayley公式
n^(n-2)


G非常可恶的动规,还以为要用什么数学方法,DP真是博大精深啊。。。多谢AngelClover的提示
#include<iostream>
#include
<cstdio>
#include
<cmath>
using namespace std;
#define INF 999999999
#define OFFSET 4000
int dp[41][8001];

int main()
{
    
int n;
    
while(scanf("%d",&n)!=EOF)
    
{
        
int i,j;
        
for(i=0;i<=n;i++)
            
for(j=0;j<=8000;j++)
                dp[i][j]
=INF;
        dp[
0][OFFSET]=0;
        
int t;
        scanf(
"%d",&t);
        dp[
1][OFFSET+t]=0;
        dp[
1][OFFSET-t]=0;
    
        
for(i=1;i<=n-1;i++)
        
{
            scanf(
"%d",&t);
            
for(j=OFFSET-100*i;j<=OFFSET+100*i;j++)
            
{

                
if(dp[i][j]!=INF)
                
{

                    dp[i
+1][j+t]=min(dp[i+1][j+t],dp[i][j]+(j-OFFSET)*t);
                    dp[i
+1][j-t]=min(dp[i+1][j-t],dp[i][j]-(j-OFFSET)*t);
                }

            }

            
//for(j=OFFSET-10;j<=OFFSET+10;j++)
            
//{
//
            
//    printf("%d ",dp[i+1][j]);
        
//    }
            
//printf("\n");
        }

        
double res=INF;
        
for(i=0;i<=8000;i++)
        
{

            
if(dp[n][i]<res)
                res
=dp[n][i];
        }

        printf(
"%.2lf\n",res);


    }

    
return 0;


}
I 离线算法 很强大啊,不过我在想 如果可以动态破坏的话,就只能用线段树了么?
感谢cl大牛
#include<cstdio>
#include
<iostream>
#include
<algorithm>

/*
x是排好序的去掉的数
q[i].ID是询问的原本位置
q[i].kth是询问第kth个数
q按kth排序
ans就是答案
*/



#define MAX 50000
#define INF 0x7FFFFFFF

using namespace std;

struct Node
{
    
int ID;
    
int kth;
    
bool operator < (Node p) 
    
{
        
return kth<p.kth;
    }

}
;

int n;
int x[MAX];

int m;
Node q[MAX];

int ans[MAX];

int main()
{

    
while(scanf("%d",&n)!=EOF)
    
{
        
for(int i=1;i<=n;i++) scanf("%d",&x[i]);
        x[
++n]=INF;
        sort(x
+1,x+n+1);

        
int nn=1;
        
for(int i=2;i<=n;i++if(x[i]!=x[nn]) x[++nn]=x[i];
        n
=nn;

        scanf(
"%d",&m);
        
for(int i=1;i<=m;i++)
        
{
            scanf(
"%d",&q[i].kth);
            q[i].ID
=i;
        }

        sort(q
+1,q+m+1);
        
for(int i=1,j=1;i<=m;i++)//i代表第几个询问
        {
            
while(x[j]-j<q[i].kth)
                j
++;
            ans[q[i].ID]
=(j-1)+q[i].kth;
        }

        
for(int i=1;i<=m;i++
            printf(
"%d\n",ans[i]);
        putchar(
'\n');
    }


    
return 0;
}


J题 动态规划 n^3水掉。。。 应该是有更好的方法,还要继续学习啊
#include<iostream>
#include
<algorithm>
#include
<cstdio>
#include
<cstring>
using namespace std;



#define INF 999999999
int dp[1001][1001];
char str[2000];
int c[1001];

int cc(int i,int j)
{
int res=0;
if(str[i]!='(')
res
+=c[i];
if(str[j]!=')')
res
+=c[j];
return res;
}


int main()
{

while(scanf("%s",str+1)!=EOF)
{

int i,j;
int n=strlen(str+1);
for(i=1;i<=n;i++)
{

for(j=i+1;j<=n;j++)
dp[i][j]
=INF;
}

for(i=1;i<=n;i++)
scanf(
"%d",&c[i]);
if(n&1)
{
printf(
"-1\n");
continue;
}

for(i=1;i<=n-1;i++)
dp[i][i
+1]=cc(i,i+1);
for(i=3;i<=n-1;i+=2)//i为区间长度
{

for(j=1;j<=n-i;j++)
{
int k;
int temp=INF;
for(k=2;k<i;k+=2)
{
if(dp[j][j+k-1]+dp[j+k][j+i]<temp)
temp
=dp[j][j+k-1]+dp[j+k][j+i];
}

dp[j][j
+i]=min(temp,dp[j+1][j+i-1]+cc(j,j+i));
}

}

printf(
"%d\n",dp[1][n]);

}

return 0;
}


关于本题的另一个解法:
 初始state=0
遇到'(' state++;
遇到')' state--
如果当前state<0说明')'比这个'('多
然后就要把')'变成'('
这部贪心把花费最小的')'变成'('
这样一遍后'('的个数会>=')'
然后反向过来反过来弄一遍
这样'('就==')'了
就得到解了
比如
( ( ) ) ) (
123456
下面的是花费
那么到
( ( ) ) )
这个状态的时候是不是就<0了
就是不合法了
就变成
( ( ( ) )了
这样就>0了,而且花费最少
然后最终变成
( ( ( ) ) (
然后反过来
               (
的时候就不合法了

改成
                 )
然后就变成
((()))
就是答案了

posted on 2010-03-21 23:58 abilitytao 阅读(140) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理