C++博客 | 首页 | 发新随笔 | 发新文章 | 联系 | 聚合

| 管理

2010年2月16日

Blog复活 && 关于输入的一些

最近总是有些创作的欲望……文思如泉涌啊，可能前几天文学青年当多了……

于是，我想起自己还没有一个技术Blog…N久之前的Baidu Blog不适合当技术Blog……

于是我又挖出了这里……话说以前我写的代码还真是烂啊……

这里的内容，目前主要是关于ACM/ICPC 和 TopCoder的一些算法……

今天刷了少许高精度题，用java一一水过……

有一个不为人知的技巧：java的数制转换（2进制~36进制，任意转换）

BigInteger有个方法，toString（int radix），把10进制数转到2~26进制

但是往回转似乎String就没有toBigInteger()的方法了……

java的Scanner有一个叫做nextBigInteger(int radix)的方法，把输入视作radix进制的数，读入后转成10进制的BigInteger

可以用类似sscanf，stringstream的方法

1 import java.util.*;
2 import java.math.*;
3
4 public class Main {
5     public static void main(String[] args) {
6         String a="1234";
7         Scanner cin=new Scanner(a);
8         BigInteger A=cin.nextBigInteger(5);
9         System.out.println(A);
10     }
11 }

输出的就是1234的十进制表示，爽啊……

还有传说中C/C++的猥琐读入法

因为getchar（）速度远远快于Scanf，尽管增加了位运算和加减，但是总体上还是优化很大……

1 inline int nextInt()
2 {
3     int ans=0; char now;
4     for (;;)
5     {
6         now=getchar();
7         if (now<'0' || now>'9') break;
8         ans=(ans<<3)+(ans<<1)+now-'0';
9     }
10     return ans;
11 }
12

POJ3697，从前1200MS，优化了IO后，进入排名榜前列……

posted @ 2010-02-16 23:39 Sweet康阅读(212) | 评论 (0) | 编辑收藏

2008年6月11日

Ural 1021

其实我做过比这还BT的题……SPOJ1296
这个是求两堆数，有没有和为10000的
就是初步考察一下HASH的思想……
貌似Cpp有STL的说，以后学习学习。

#include <iostream.h>;
2

#include <string.h>;
3

bool a[80000];
5

void main(){
7

long n,t,i;
8

cin>>n;
9

memset(a,0,sizeof(a));
10

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

{
12

cin>>t; a[t+40000]=true;
13

}
14

cin>>n; bool ans=false;
15

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

{
17

cin>>t; if (a[50000-t]) {ans=true; break;}
18

}
19

if (ans) cout<<"YES";
20

else cout<<"NO";
21

}
22

posted @ 2008-06-11 19:38 Sweet康阅读(222) | 评论 (0) | 编辑收藏

Ural 1567

水题，写短信一共要摁几下键……不过写的垃圾了点

#include <stdio.h>;
2

void main()
4

{
5

long s=0; char c;
6

while (scanf("%c",&c)!=EOF)
7

{
8

if (c=='a'||c=='d'||c=='g'||c=='j'||c=='m'||c=='p'||c=='s'||c=='v'||c=='y'||c=='.'||c==' ')
9

s++;
10

if (c=='b'||c=='e'||c=='h'||c=='k'||c=='n'||c=='q'||c=='t'||c=='w'||c=='z'||c==',')
11

s+=2;
12

if (c=='c'||c=='f'||c=='i'||c=='l'||c=='o'||c=='r'||c=='u'||c=='x'||c=='!')
13

s+=3;
14

}
15

printf("%d\n",s);
16

}
17

posted @ 2008-06-11 19:11 Sweet康阅读(298) | 评论 (0) | 编辑收藏

Ural 1087

博弈论基础：
大概就是定义必败状态和必胜状态：
由某状态能到达必败状态，这样的状态就是必胜状态
反之，某状态只能到达必胜状态，这样地状态就叫必败状态
比如一堆石子拿1，2，3个，谁拿最后一个谁输
那么1个石子就是必败状态。
2，3，4个石子是必胜状态
5个石子是必败状态……这道题性质类似，使用了记忆化搜索，1Y

#include <iostream.h>;
2

#include <string.h>;
3

int a[10010];
4

int b[50];
5

int n,m,i,ans;
6

int get(int k){
8

if (a[k]!=0) return a[k];
9

int i; a[k]=2;
10

for (i=0;i<m;i++)
11

if (k-b[i]>=1 && get(k-b[i])==2) {a[k]=1; break;}
12

return a[k];
13

}
14

void main(){
16

memset(a,0,sizeof(a));
17

a[1]=2;
18

cin>>n>>m;
19

for (i=0;i<m;i++) cin>>b[i];
20

ans=get(n);
21

cout<<ans<<"\n";
22

}

posted @ 2008-06-11 19:00 Sweet康阅读(416) | 评论 (0) | 编辑收藏

Ural 1012&&1013

1009的强化版，要用高精度……结果屡屡WA
后来参考了AC代码……不得不佩服，人家那高精度写的都比我好
整个翻译到了Cpp

#include <iostream.h>;
2

#include <string.h>;
3

void main()
5

{
6

long n,k,i,j,d;
7

int a[2000],b[2000],c[2000];
8

memset(a,0,sizeof(a));
9

memset(b,0,sizeof(b));
10

memset(c,0,sizeof(c));
11

cin>>n>>k;
12

a[0]=1; b[0]=k-1; d=0;
13

for(i=2;i<=n;i++){
14

for (j=0;j<=d;j++) c[j]=(k-1)*(a[j]+b[j]);
15

for (j=0;j<=d;j++) {a[j]=b[j]; b[j]=c[j];}
16

j=0;
17

memset(c,0,sizeof(c));
18

while (true){
19

b[j+1]+=b[j]/10;
20

b[j]=b[j]%10;
21

if (b[j+1]==0&&j>=d) break;
22

j++;
23

}
24

d=j;
25

}
26

for (i=d;i>=0;i--) cout<<b[i];
27

cout<<"\n";
28

}
29

posted @ 2008-06-11 18:05 Sweet康阅读(339) | 评论 (0) | 编辑收藏

2008年6月10日

Ural 1083

求N的阶乘强化版，N！！，N！！！……

#include <stdio.h>;
2

void main(){
4

long n;
5

long d=0;
6

long s=1;
7

scanf("%d",&n);
8

char c;
9

while (scanf("%c",&c)!=EOF)
10

if (c=='!') d++;
11

int i;
12

for (i=n;i>1;i-=d)
13

s*=i;
14

printf("%d\n",s);
15

}

posted @ 2008-06-10 20:55 Sweet康阅读(277) | 评论 (0) | 编辑收藏

2008年6月7日

Ural 1009

访问量很大的说～THX
刚开始读错题了，不允许有2个连续的0，屡屡WA，后来看discuss，发现了个精妙的解法

#include <iostream.h>;
2

int main()
4

{
5

long n,k,i;
6

long f[30];
7

cin>>n>>k;
8

f[0]=k-1;
9

f[1]=k*f[0];
10

for(i=2;i<n;i++) f[i]=(k-1)*(f[i-1]+f[i-2]);
11

cout<<f[n-1];
12

return 0;
13

}

其递推关系的精华大概就是：
定义的f[0]，f[1]都是没有两个连续的0，
f[i]=(k-1)*(f[i-1]+f[i-2]);
也就是说用1..K这K－1个数，后面接上长度为N－1的那些或者可以接上长度为N－2的那些，差一位，用0补足。
精妙，精妙。

posted @ 2008-06-07 10:43 Sweet康阅读(222) | 评论 (0) | 编辑收藏

2008年6月1日

Ural 1079

大意：给你一个递推式，求前N项中最大的那一项
算法：先把这个数列求出来，再动态规划一下……

#include <stdio.h>;
2

#include <string.h>;
3

long a[100010];
5

long b[100010];
6

int main(){
7

long i;
8

memset(a,0,sizeof(a));
9

memset(b,0,sizeof(b));
10

a[0]=0; a[1]=1;
11

for (i=2;i<100000;i++)
12

if (i & 1==1) a[i]=a[i>>1]+a[(i>>1)+1];
13

else a[i]=a[i>>1];
14

for (i=1;i<100000;i++)
15

if (b[i-1]<a[i]) b[i]=a[i];
16

else b[i]=b[i-1];
17

long n,t;
18

while (true)
19

{
20

scanf("%ld",&t);
21

if (t==0) break;
22

printf("%ld\n",b[t]);
23

}
24

return 0;
25

}
26

posted @ 2008-06-01 18:26 Sweet康阅读(276) | 评论 (0) | 编辑收藏

Ural 1017

大意：台阶问题：N块东西，摞成台阶（高度严格单调递增）
算法：母函数展开
这个问题相当于求
（1＋x）（1＋x2）（1＋x3）（1＋x4）……的xn次项系数
%0.0lf ……

数貌似有点大，用double能搞定。

#include <stdio.h>;
2

#include <iostream.h>;
3

#include <string.h>;
4

double a[511][511] ;
6

int main(){
8

memset(a,0,sizeof(a));
9

int i,j,n;
10

cin>>n;
11

a[0][0]=1;
12

int t;
13

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

for (j=0;j<=n;j++){
15

a[i][j]+=a[i-1][j];
16

t=j+i;
17

if (a[i-1][j]>0 && t<=n) a[i][t]+=a[i-1][j];
18

}
19

printf("%0.0lf\n",a[n-1][n]);
20

return 0;
21

}

posted @ 2008-06-01 18:06 Sweet康阅读(314) | 评论 (0) | 编辑收藏

Ural 1005

大意就是把一堆东西（N<=20）分两部分，使差最小，当然爆搜了

但是同样的代码，按C提交就AC了，按C＋＋提交就CE……无语，最无语的是这个在我的机器上C＋＋ Builder编译能过啊

初学Cpp，谁好心看看……

16:36:24

#include <stdio.h>;
2

#include <math.h>;
3

long a[30];
5

long m1,m2,n,ans,i;
6

int dfs(int k){
8

if (k==n+1)
9

{
10

long t=fabs(m1-m2);
11

if (t<ans) ans=t;
12

return 0;
13

}
14

m1+=a[k];
15

dfs(k+1);
16

m1-=a[k];
17

m2+=a[k];
18

dfs(k+1);
19

m2-=a[k];
20

return 0;
21

}
22

int main()
24

{
25

scanf("%d",&n);
26

for (i=1;i<=n;i++) scanf("%d",&a[i]);
27

m1=0; m2=0; ans=200000000;
28

dfs(1);
29

printf("%d\n",ans);
30

return 0;
31

}
32

posted @ 2008-06-01 16:37 Sweet康阅读(327) | 评论 (0) | 编辑收藏

Ural 1001

庆祝新blog开张……
CSDN那个blog真的很囧啊……代码近日竟然显示不上了……
Ural 1001：给你一堆数，倒序输出它们的平方根……问题在于：这堆数乱七八糟，不是一行一个，因而很多写法就不能用……

#include <stdio.h>
2

#include <iostream.h>;
3

#include <math.h>
4

#include <string.h>
5

double a[1000000];
6

int s;
7

int get(){
9

double t;
10

while (1<2){
11

t=-1;
12

cin>>t;
13

if (t<0) break;
14

a[++s]=t;
15

}
16

for (int i=s;i>=1;i--){
17

t=sqrt(a[i]);
18

printf("%0.4f\n",t);
19

}
20

return 0;
21

}
22

int main()
24

{
25

memset(a,0,sizeof(a));
26

s=0;
27

get();
28

return 0;
29

}
30

posted @ 2008-06-01 16:17 Sweet康阅读(390) | 评论 (0) | 编辑收藏

仅列出标题

随笔：11 文章：0 评论：0 引用：0

2024年11月

日

一

二

三

四

五

六

常用链接

留言簿(1)

随笔分类(6)

Ural(6) (rss)

随笔档案(11)

文章分类

Ural (rss)

2010年2月16日

2008年6月11日

2008年6月10日

2008年6月7日

2008年6月1日

常用链接

留言簿(1)

随笔分类(6)

随笔档案(11)

文章分类

朋友们

搜索

最新评论

阅读排行榜

评论排行榜