C++博客-[NKU]sweet @ICPC,TopCoder,and so on

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

Sweet康 — Tue, 16 Feb 2010 15:39:00 GMT

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

于是，我想起自己还没有一个技术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后，进入排名榜前列……

Sweet康 2010-02-16 23:39 发表评论

Ural 1021

Sweet康 — Wed, 11 Jun 2008 11:38:00 GMT

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

1#include <iostream.h>;
2#include <string.h>;
3
4bool a[80000];
5
6void main(){
7long n,t,i;
8cin>>n;
9memset(a,0,sizeof(a));
10for (i=0;i<n;i++)
11{
12cin>>t; a[t+40000]=true;
13}
14cin>>n; bool ans=false;
15for (i=0;i<n;i++)
16{
17cin>>t; if (a[50000-t]) {ans=true; break;}
18}
19if (ans) cout<<"YES";
20else cout<<"NO";
21}
22

Sweet康 2008-06-11 19:38 发表评论

Ural 1567

Sweet康 — Wed, 11 Jun 2008 11:11:00 GMT

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

1#include <stdio.h>;
2
3void main()
4{
5long s=0; char c;
6while (scanf("%c",&c)!=EOF)
7{
8if (c=='a'||c=='d'||c=='g'||c=='j'||c=='m'||c=='p'||c=='s'||c=='v'||c=='y'||c=='.'||c==' ')
9s++;
10if (c=='b'||c=='e'||c=='h'||c=='k'||c=='n'||c=='q'||c=='t'||c=='w'||c=='z'||c==',')
11s+=2;
12if (c=='c'||c=='f'||c=='i'||c=='l'||c=='o'||c=='r'||c=='u'||c=='x'||c=='!')
13s+=3;
14}
15printf("%d\n",s);
16}
17

Sweet康 2008-06-11 19:11 发表评论

Ural 1087

Sweet康 — Wed, 11 Jun 2008 11:00:00 GMT

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

1#include <iostream.h>;
2#include <string.h>;
3int a[10010];
4int b[50];
5int n,m,i,ans;
6
7int get(int k){
8if (a[k]!=0) return a[k];
9int i; a[k]=2;
10for (i=0;i<m;i++)
11if (k-b[i]>=1 && get(k-b[i])==2) {a[k]=1; break;}
12return a[k];
13}
14
15void main(){
16memset(a,0,sizeof(a));
17a[1]=2;
18cin>>n>>m;
19for (i=0;i<m;i++) cin>>b[i];
20ans=get(n);
21cout<<ans<<"\n";
22}

Sweet康 2008-06-11 19:00 发表评论

Ural 1012&&1013

Sweet康 — Wed, 11 Jun 2008 10:05:00 GMT

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

1#include <iostream.h>;
2#include <string.h>;
3
4void main()
5{
6long n,k,i,j,d;
7int a[2000],b[2000],c[2000];
8memset(a,0,sizeof(a));
9memset(b,0,sizeof(b));
10memset(c,0,sizeof(c));
11cin>>n>>k;
12a[0]=1; b[0]=k-1; d=0;
13for(i=2;i<=n;i++){
14for (j=0;j<=d;j++) c[j]=(k-1)*(a[j]+b[j]);
15for (j=0;j<=d;j++) {a[j]=b[j]; b[j]=c[j];}
16j=0;
17memset(c,0,sizeof(c));
18while (true){
19b[j+1]+=b[j]/10;
20b[j]=b[j]%10;
21if (b[j+1]==0&&j>=d) break;
22j++;
23}
24d=j;
25}
26for (i=d;i>=0;i--) cout<<b[i];
27cout<<"\n";
28}
29
30

Sweet康 2008-06-11 18:05 发表评论

Ural 1083

Sweet康 — Tue, 10 Jun 2008 12:55:00 GMT

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

1#include <stdio.h>;
2
3void main(){
4long n;
5long d=0;
6long s=1;
7scanf("%d",&n);
8char c;
9while (scanf("%c",&c)!=EOF)
10if (c=='!') d++;
11int i;
12for (i=n;i>1;i-=d)
13s*=i;
14printf("%d\n",s);
15}

Sweet康 2008-06-10 20:55 发表评论

Ural 1009

Sweet康 — Sat, 07 Jun 2008 02:43:00 GMT

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

1#include <iostream.h>;
2
3int main()
4{
5long n,k,i;
6long f[30];
7cin>>n>>k;
8f[0]=k-1;
9f[1]=k*f[0];
10for(i=2;i<n;i++) f[i]=(k-1)*(f[i-1]+f[i-2]);
11cout<<f[n-1];
12return 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补足。
精妙，精妙。

Sweet康 2008-06-07 10:43 发表评论

Ural 1079

Sweet康 — Sun, 01 Jun 2008 10:26:00 GMT

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

1#include <stdio.h>;
2#include <string.h>;
3
4long a[100010];
5long b[100010];
6int main(){
7long i;
8memset(a,0,sizeof(a));
9memset(b,0,sizeof(b));
10a[0]=0; a[1]=1;
11for (i=2;i<100000;i++)
12if (i & 1==1) a[i]=a[i>>1]+a[(i>>1)+1];
13 else a[i]=a[i>>1];
14for (i=1;i<100000;i++)
15if (b[i-1]<a[i]) b[i]=a[i];
16 else b[i]=b[i-1];
17long n,t;
18while (true)
19{
20scanf("%ld",&t);
21if (t==0) break;
22printf("%ld\n",b[t]);
23}
24return 0;
25}
26

Sweet康 2008-06-01 18:26 发表评论

Ural 1017

Sweet康 — Sun, 01 Jun 2008 10:06:00 GMT

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

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

1#include <stdio.h>;
2#include <iostream.h>;
3#include <string.h>;
4
5double a[511][511] ;
6
7int main(){
8memset(a,0,sizeof(a));
9int i,j,n;
10cin>>n;
11a[0][0]=1;
12int t;
13for (i=1;i<=n;i++)
14for (j=0;j<=n;j++){
15a[i][j]+=a[i-1][j];
16t=j+i;
17if (a[i-1][j]>0 && t<=n) a[i][t]+=a[i-1][j];
18}
19printf("%0.0lf\n",a[n-1][n]);
20return 0;
21}

Sweet康 2008-06-01 18:06 发表评论

Ural 1005

Sweet康 — Sun, 01 Jun 2008 08:37:00 GMT

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

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

初学Cpp，谁好心看看……

16:36:24

1#include <stdio.h>;
2#include <math.h>;
3
4long a[30];
5long m1,m2,n,ans,i;
6
7int dfs(int k){
8if (k==n+1)
9        {
10        long t=fabs(m1-m2);
11        if (t<ans) ans=t;
12        return 0;
13        }
14m1+=a[k];
15dfs(k+1);
16m1-=a[k];
17m2+=a[k];
18dfs(k+1);
19m2-=a[k];
20return 0;
21}
22
23int main()
24{
25scanf("%d",&n);
26for (i=1;i<=n;i++) scanf("%d",&a[i]);
27m1=0; m2=0; ans=200000000;
28dfs(1);
29printf("%d\n",ans);
30return 0;
31}
32

Sweet康 2008-06-01 16:37 发表评论

Ural 1001

Sweet康 — Sun, 01 Jun 2008 08:17:00 GMT

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

1#include <stdio.h>
2#include <iostream.h>;
3#include <math.h>
4#include <string.h>
5double a[1000000];
6int s;
7
8int get(){
9double t;
10while (1<2){
11t=-1;
12cin>>t;
13if (t<0) break;
14a[++s]=t;
15}
16for (int i=s;i>=1;i--){
17t=sqrt(a[i]);
18printf("%0.4f\n",t);
19}
20return 0;
21}
22
23int main()
24{
25memset(a,0,sizeof(a));
26s=0;
27get();
28return 0;
29}
30
31

Sweet康 2008-06-01 16:17 发表评论