# 希望的海洋

Ain't about how fast I get there,ain't about what's waiting on the other side

• 随笔 - 21
• 文章 - 0
• 评论 - 1
• 引用 - 0

2011年9月18日 #

## selective1_2_g 01背包 hdu 2955

#include<iostream>
#include<math.h>
#define M 105
using namespace std;

struct ss {
double p;
int m;
} s[M];

int main() {
int t, i, j, n, sum[M];
double dp[M * M], P;
scanf("%d", &t);
while (t-- && scanf("%lf %d", &P, &n)) {
P = 1 - P;
memset(dp, 0, sizeof (dp));
dp[0] = 1;
sum[0] = 0;
for (i = 1; i <= n; i++) {
scanf("%d %lf", &s[i].m, &s[i].p);
s[i].p = 1 - s[i].p;
sum[i] = sum[i - 1] + s[i].m;
}
for (i = 1; i <= n; i++)
for (j = sum[n]; j >= s[i].m; j--)
dp[j] = max(dp[j], dp[j - s[i].m] * s[i].p);
for (j = sum[n]; j >= 1; j--)
if (dp[j] > P)break;
printf("%d\n", j);
}
return 0;
}

posted @ 2011-09-18 10:30 拥梦的小鱼 阅读(265) | 评论 (0)编辑 收藏

## selective contest1_2_h hdu 1115

1，质量集中在顶点上。n个顶点坐标为(xi,yi)，质量为mi，则重心
X = ∑( xi×mi ) / ∑mi
Y = ∑( yi×mi ) / ∑mi
特殊地，若每个点的质量相同，则
X = ∑xi / n
Y = ∑yi / n

2，质量分布均匀。这个题就是这一类型，算法和上面的不同。
特殊地，质量均匀的三角形重心：
X = ( x0 + x1 + x2 ) / 3
Y = ( y0 + y1 + y2 ) / 3

3，质量分布不均匀。只能用积分来算，不会……

S =( x0*y1 + x1*y2 + x2*y0
- x1*y0 - x2*y1 - x0*y2 ) /2;

# include<iostream>
# include<algorithm>
using namespace std;
const int maxNum = 1000000 +2;

struct point
{
double x, y;
};
struct point data[maxNum];

struct point bcenter(struct point pnt[], int n)【可以用来做模板】
{
point p, s;
double tp, area = 0, tpx = 0, tpy = 0;

p.x = pnt[0].x; p.y = pnt[0].y;

for (int i = 1; i <= n; ++i)
{

s.x = pnt[(i == n) ? 0 : i].x;
s.y = pnt[(i == n) ? 0 : i].y;
tp = (p.x * s.y - s.x * p.y);
area += tp / 2;
tpx += (p.x + s.x) * tp;
tpy += (p.y + s.y) * tp;
p.x = s.x;
p.y = s.y;
}
s.x = tpx / (6 * area);
s.y = tpy / (6 * area);
return s;
}
//OR:

This source is shared by zyd150

#include
<stdio.h>
#include
<math.h>
#define MAX 1000001
struct point{

double x,y;
}
;
int n;
struct point p[MAX],v,ans;
void process(){

int i,j,k;

double s,ss=0;
ans.x
=ans.y=0;

for(i=0;i<n;i++){
j
=(i+1)%n;
v.x
=(p[i].x+p[j].x)/3.0;
v.y
=(p[i].y+p[j].y)/3.0;
s
=(p[i].x*p[j].y-p[i].y*p[j].x)/2.0;
v.x
*=s;v.y*=s;ss+=s;
ans.x
+=v.x;ans.y+=v.y;
}

ans.x
/=ss;ans.y/=ss;

if(fabs(ans.x)<0.000001) ans.x=0;

if(fabs(ans.y)<0.000001) ans.y=0;
printf(
"%.2lf %.2lf\n",ans.x,ans.y);
}

int main(){

int cas,i;
scanf(
"%d",&cas);

while(cas--){
scanf(
"%d",&n);

for(i=0;i<n;i++)
scanf(
"%lf%lf",&p[i].x,&p[i].y);
process();
}

return 0;
}

```#include<stdio.h>
#include<math.h>
#define MAX 1000001
struct point{
double x,y;
};
int n;
struct point p[MAX],v,ans;
void process(){
int i,j,k;
double s,ss=0;
ans.x=ans.y=0;
for(i=0;i<n;i++){
j=(i+1)%n;
v.x=(p[i].x+p[j].x)/3.0;
v.y=(p[i].y+p[j].y)/3.0;
s=(p[i].x*p[j].y-p[i].y*p[j].x)/2.0;
v.x*=s;v.y*=s;ss+=s;
ans.x+=v.x;ans.y+=v.y;
}
ans.x/=ss;ans.y/=ss;
if(fabs(ans.x)<0.000001) ans.x=0;
if(fabs(ans.y)<0.000001) ans.y=0;
printf("%.2lf %.2lf\n",ans.x,ans.y);
}
int main(){
int cas,i;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
process();
}
return 0;
}```

int main()
{

int T,i,j,num;
struct point re;
scanf("%d",&T);
while(T--)
{
scanf("%d",&num);
for(i = 0; i < num ; i ++)
scanf("%lf %lf",&data[i].x,&data[i].y);

re = bcenter(data,num);
printf("%.2lf %.2lf\n",re.x,re.y);
}
return 0;
}

posted @ 2011-09-18 10:29 拥梦的小鱼 阅读(203) | 评论 (0)编辑 收藏

2011年9月17日 #

## hdu 3591取石子（一堆）

hdu 3591

#include<iostream>
#include
<cstdio>
#include
<cmath>
#include
<cstring>
#include
<string>
#include
<map>
#include
<vector>
#include
<algorithm>
#include
<iomanip>
using namespace std;
int main()
{

int T,count=1;
cin
>>T;

while(T--)

{

int n,k;
cin
>>n>>k;
cout
<<"Case "<<count++<<"";

if((n&1&&k==1)||k>=n)
cout
<<"first"<<endl;

else
cout
<<"second"<<endl;
}

return 0;
}

//cankao others

1.当  K=1时，若N为奇数，则first wins，N为偶数则second wins。

2.当  K>=N时，first wins。

3.当  N>K>1时，情况类似上面提到过的谜题，若first的最先操作使得剩下的水龙头为偶数，如果你能把剩下的取完那就直接胜利，如果不能那就拿走中间的若干个偶数个硬币使得剩下的硬币被分为数目相等的两堆。接着对方对某堆进行操作你就对另一堆进行同样的操作，这时是second wins。first的最先操作使得剩下的水龙头为奇数时同理可证second wins。

posted @ 2011-09-17 19:55 拥梦的小鱼 阅读(333) | 评论 (0)编辑 收藏

2011年9月13日 #

## usaco_clocks dfs/bfs/位运算

摘要: The ClocksIOI'94 - Day 2Consider nine clocks arranged in a 3x3 array thusly: |-------| |-------| |-------| | | | | | | | |---O | |---O | | O | | | | | | | |-------| |-------| |-------| A B C |-------|...  阅读全文

posted @ 2011-09-13 11:40 拥梦的小鱼 阅读(344) | 评论 (0)编辑 收藏

2011年8月24日 #

## usaco_packrec暴搜

摘要: 这道题给了6个图，实际只需考虑5种（后两个相同）。最后一个模型自己没有抽象出来。还是逻辑清晰，比较不容易出错。头开始设许多临时变量，总是不知道具体值是多少，结果一直debug，还一直bug。。⊙﹏⊙b汗。。用4个rec结构记录比较好。最后一个模型，是左边两个，右边两个，然后根据两边上面矩形的高度情况，讨论矩形整体的宽。注意，自己设的变量最好还是写出来吧。此题竖着的边|，分别...  阅读全文

posted @ 2011-08-24 18:21 拥梦的小鱼 阅读(329) | 评论 (0)编辑 收藏

## DS_stack忆往昔——经常做错的一道铁路调度

shit！太弱了!!警醒！这回思路完全正确、结构也很清晰。但是还是会忽略细节。习惯太差！继续打基础！！Go on！Keep up!
stack 模拟，一个数组就可以搞定.
#include<cstdio>
#include
<cstdlib>
#include
<cstring>
#include
<cmath>
#include
<algorithm>

int n,arr[100],stack[100],top=0;
char str[100];

void s2i(char* s)
{

int i=0;

while(*s)

{
arr[i
++]=*s-'0';
s
++;
}

}

void judge(int* ai)
{

int i,*pi=ai;

for(i=1;i<=n;i++)

{

if(*pi==i)

{
pi
++;

continue;
}

else if(*pi>i)//push i
{
stack[top
++]=i;

continue;
}

else if(*pi<i)//pop i
{

if(stack[--top]==*pi)

{
pi
++;
i
--;//忘记此处，这时i没有处理，需恢复
}

else

{
printf(
"no\n");

return;
}

}

}

while(top>0)

{

if(*pi!=stack[--top])

{
printf(
"no\n");

return;
}

else pi++;
}

printf(
"yes\n");
}

int main()
{

int t,k;
scanf(
"%d",&t);

while(t--)

{
top
=0;
memset(str,
0,sizeof(str));//此三处一再忘记复位，WA无数次。。！！！！！
memset(stack,0,sizeof(stack));
scanf(
"%d",&n);
scanf(
"%s",str);
s2i(str);
judge(arr);
}

return 0;
}

posted @ 2011-08-24 18:14 拥梦的小鱼 阅读(166) | 评论 (0)编辑 收藏

2011年8月19日 #

## Dp poj 1159(multiple solutions)

(1)思路：最长公共子序列：ans=L-LCS(s,^s)
(2)DP 状态：dp[i][j]为i to j，需要加入的字符。初始：dp[i][i]=0
分2种情况：s[i]==s[j]则dp[i][j]=dp[i+1][j-1]
s[i]!=s[j]               =Min(dp[i+1][j],dp[i][j-1])+1
dp[i][j]=cal(i+1,j-1);

return dp[i][j];
}

/*dp[i][j]=MIN(cal(i+1,j-1)+2,cal(i+1,j)+1);
dp[i][j]=MIN(dp[i][j],cal(i,j-1)+1);
*/

dp[i][j]
=MIN(cal(i+1,j)+1,cal(i,j-1)+1);

return dp[i][j];
}
int main()
{

int i,j,k,mid;
scanf(
"%d",&N);

//for(i=0;i<N;i++)
scanf("%s",s);
len
=strlen(s);

//printf("%d\n",len);
mid=len/2;
memset(dp,
-1,sizeof(dp));//unsigned to the utmost
dp[mid][mid]=0;

printf(
"%d\n",cal(0,len-1));

return 0;
}

(3)节省空间，用dp[2][5002]的数组存放。因为i-1用过后，就不再用了

#include<cstdio>
#include
<cstdlib>
#include
<cstring>
#include
<cmath>
#define MIN(a,b) (a)<(b)?(a):(b)

char s[5002];
int dp[2][5002];
int main()
{

int i,j,k,l,N;
scanf(
"%d",&N);
scanf(
"%s",s);

for(i=N-1;i>=0;i--)

for(j=i+1;j<N;++j)

if(s[i]==s[j])dp[i&1][j]=dp[(i+1)&1][j-1];

else dp[i&1][j]=MIN(dp[(i+1)&1][j]+1,dp[i&1][j-1]+1);
printf(
"%d\n",dp[(i+1)%2][N-1]);

return 0;
}

（4）

array[i-1][j]和array[i-1][j-1]

array[j] = array[j-1]+array[j]

#include <stdio.h>
#include
<string.h>
int main()
{

char a[5002];

int f[5002];

int i,j,n,t,tp;
scanf(
"%d%s",&n,a+1);

memset(f,
0,sizeof(f));

for(i=1;i<=n;i++){
tp
=0;    //f[i-1,j-1]复位，一开始忘记了，老是wa，郁闷
for(j=n;j>=1;j--){

if(a[i]==a[j]){
t
=f[j];
f[j]
=tp+1;    //f[i,j]=f[i-1,j-1]+1
tp=t;
}

else{
tp
=f[j];

if(f[j]<f[j+1]) f[j]=f[j+1]; //f[i-1,j]<f[i,j-1]
}

}

}

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

return 0;
}

posted @ 2011-08-19 15:12 拥梦的小鱼 阅读(242) | 评论 (0)编辑 收藏

2011年8月14日 #

## 线性DP 两次最长上升子序列 1836_POJ

n个士兵，选ct个人出队，使得重新排队得到的队伍每个人都可以向左或向右看到无穷远，没有比他高或同样高的视觉障碍（人）。求ct最小值。

## 使剩下的队列满足a1 < a2 < a3 ... < a(i ) <=> a(i+1) > a(i+2) > .. a(n-1) > a(n)

#include<cstdio>
#include
<cstdlib>
#include
<cstring>
#include
<cmath>

int d[1010],rev[1010],index[10];
double hi[1010];

int main()
{

int n,tmp=0,i,j,max=0,ct=0;

double db;
scanf(
"%d",&n);

for(i=0;i<n;++i)

{    scanf("%lf",&hi[i]);//双精度浮点数输入须为%lf，而非%f
d[i]=1;
rev[i]
=1;
}

//scanf("%f",&db);

//d[0]=1;
for(i=1;i<n;++i)

{

for(j=0;j<i;++j)

if(hi[j]<hi[i]&&d[j]+1>d[i])
d[i]
=d[j]+1;//正序以i结尾的最长上升子序列长度
}

for(i=n-1;i>=0;--i)

{

for(j=n-1;j>i;--j)

if(hi[j]<hi[i]&&rev[i]<rev[j]+1)
rev[i]
=rev[j]+1;//逆序以i结尾的最长上升子序列长度
}

for(i=0;i<n;++i)

{

if(d[i]+rev[i]>max)//find the highest one int the middle,keep its index in record
{
max
=d[i]+rev[i];
index[
0]=i;
tmp
=0;
}

else if(d[i]+rev[i]==max&&hi[i]==hi[index[0]])//&&hi[i]==hi[index[0]]漏掉则出错。此条件判断是否有两个相等的最高顶点。
{
index[
++tmp]=i;
}

}

ct
=index[0]+1-d[index[0]]+n-1-index[tmp]+1-rev[index[tmp]];//b4 and after of 3 parts:before index[0];between o~tmp;after index[tmp]
for(i=index[0]+1;i<index[tmp];++i)//intermediate part
if(hi[i]<hi[index[0]])ct++;
printf(
"%d\n",ct);

return 0;
}

posted @ 2011-08-14 15:30 拥梦的小鱼 阅读(222) | 评论 (0)编辑 收藏

2011年8月13日 #

## 线性DP——POJ 3276

d[i]=Min{d[i-1]+1,make(i)}//delete vs not delete

#include<cstdio>
#include
<cstring>
#include
<cmath>
#include
<cstdlib>
#define INF 1000000
#define MIN(a,b) (a)>(b)?(b):(a)
int N,L;
char dic[600][26],msg[305];
int f[305];//记录第i位前丢弃的最少字母数

int make(int m)
{

int k,j,ct=0,n=m,t,re=INF;

for(k=0;k<N;++k)

{

if(dic[k][strlen(dic[k])-1]==msg[m])//若写m为n此处n=0,WA
{
n
=m;ct=0;
j
=strlen(dic[k])-1;

while(j>=0)

{

while(n>=0&&msg[n]!=dic[k][j])

{
n
--;
ct
++;
}

if(n>=0&&msg[n]==dic[k][j])n--;//当n小于0时说明此单词比该msgd第n位前的字串长
else break;
j
--;
}

//if(j==-1&&ct+f[n-1]<re)

//{

//    re=ct+f[n-1];

//    //t=n;

//}
if(j==-1)//说明字典中存在以msg【n】结尾的子串=该单词
{

if(n>=0&&ct+f[n]<re)//由于上一个if语句多减了一次1，所以此时perhaps n<0
re=ct+f[n];

else if(n<0&&ct<re)re=ct;//此时说明msg中的该单词恰好是从msg[0]开始的
}

}

}

/*if(re==INF)头开始误导了，想着总是加一，不对。其实是对的，会自己判断选择到达该状态的其他路径，
return f[m-1]==0?0:f[m-1]+1;                                故此处多余
*/

return re;
}

int main()
{

int len,i,j,k;
scanf(
"%d",&N);
scanf(
"%d",&len);
scanf(
"%s",msg);

//for(i=0;i<len;i++)调试时的代码一定要记得注释掉！！！WA两次因此。太suck了

//    printf("%c ",msg[i]);

//printf("\n");

//for(i=0;i<len;i++)

//    printf("%-2d",i);

//printf("\n");
for(i=0;i<N;++i)

{
scanf(
"%s",dic[i]);
}

len
=strlen(msg);
f[
0]=1;//初始状态可能不为1，即第一个字符也可能作为字典单词的最后一个字母，此时该单词位单字母单词
for(i=0;i<N;++i)

if(strlen(dic[i])==1&&dic[i][0]==msg[0])f[0]=0;

for(i=1;i<len;i++)

{
f[i]
=MIN(f[i-1]+1,make(i));
}

printf(
"%d\n",f[len-1]);

}

posted @ 2011-08-13 22:13 拥梦的小鱼 阅读(373) | 评论 (0)编辑 收藏

2011年8月11日 #

## usaco_calflac多行文件中找出最长回文串

摘要: 回文串不考虑除字母以外的字符，并且不区分大小写。strupr()usaco不让用，可能toupper可以。strcat(s1,s2)中s1必须为数组才可以不报错。while(fgets(line,100,fin)!=NULL)读入的一行包括结尾的换行符。注意处理大小写情况。第一种方法在usaco的test8中超时了。第二种，网上查的DP方法，讨论奇偶性，高效简单快捷。（1）暴搜。每读入一行，从此行...  阅读全文

posted @ 2011-08-11 11:23 拥梦的小鱼 阅读(410) | 评论 (0)编辑 收藏