基础专题

1.hdu 1028 Ignatius and the Princess III 整数划分

 1 #include<stdio.h>
 2 __int64 dp[121][121];
 3 int main()
 4 {
 5     __int64 i,j,k,n,m;
 6     for(i=0;i<=120;i++)
 7         for(j=0;j<=120;j++)
 8             dp[i][j]=0;
 9     for(i=1;i<=120;i++)
10     {
11         dp[i][1]=1;
12         dp[1][i]=1;
13     }
14     for(i=1;i<=120;i++)
15         for(j=1;j<=120;j++)
16         {
17             if(i<j)
18                 dp[i][j]=dp[i][i];
19             else if(i>j)
20                 dp[i][j]=dp[i-j][j]+dp[i][j-1];
21             else if(i==j)
22                 dp[i][j]=1+dp[i][j-1];
23         }
24     while(scanf("%I64d",&n)>0)
25     {
26         printf("%I64d
",dp[n][n]);
27     }
28     return 0;
29 }

View Code

2.hdu 1133 Buy the Ticket

这道题，以前没有用java的时候，还没有ac。

题意：有n个人手上有50元，m个人手上有100元。售票员手上没有零钱，所以必须要拥有50元的人先买。在任何时候，都要满足

50的人数>=100的人数才能满足题意要求。而且，每个人是不一样的，所以针对拥有50元或者 100 的人又是有序的。

思路：dp[ i ] [ j ] 代表前 i 个人中，有 j 个50元的人已经买票了。

if( j > i - j ) dp[ i ] [ j ] = dp[ i -1] [j -1 ] + dp[i - 1] [ j ]; 讨论第i 个人是50元还是 100元。

else dp[ i ] [ j ] = dp[ i-1 ] [ j-1 ];//此时只能由50元的人买票了.

由于有序，所以dp[n+m][n]*c[n]*c[m]; c[ ]代表阶乘.

//输入上要注意一下，m未必<=n，所以这样的情况，直接为0.

 1 //package mywork;
 2 
 3 import java.util.*;
 4 import java.math.BigInteger;
 5 import java.io.*;
 6 
 7 public class Main {
 8 
 9     static BigInteger c[] = new BigInteger[101];
10     static BigInteger dp[][]= new BigInteger[202][202];
11                                           
12     public static void main(String[] args) {
13         // TODO Auto-generated method stub
14         fun();
15         int t=1;
16         Scanner cin  = new Scanner(System.in);
17         while(cin.hasNext()){
18             int n = cin.nextInt();
19             int m = cin.nextInt();
20             if(n==0&&m==0)break;
21             if(m>n){
22                 System.out.println("Test #"+t+":");
23                 t++;
24                 System.out.println("0");
25                 continue;
26             }
27             BigInteger hxl = dp[n+m][n].multiply(c[n]).multiply(c[m]);
28             System.out.println("Test #"+t+":");
29             System.out.println(hxl);
30             t++;
31         }
32     }
33     static void fun(){
34         c[0] = BigInteger.ONE;
35         for(int i=1;i<=100;i++)
36             c[i] = c[i-1].multiply(BigInteger.valueOf(i));
37         
38         for(int i=0;i<=200;i++){
39             for(int j=0;j<=200;j++)
40             dp[i][j] = BigInteger.ZERO;
41         }
42         dp[1][1]=BigInteger.ONE;
43         for(int i=2;i<=200;i++){
44             for(int j=1;j<=i;j++){
45                 if(j>i-j)
46                     dp[i][j] = dp[i-1][j].add(dp[i-1][j-1]);
47                 else dp[i][j] = dp[i-1][j];
48             }
49         }
50     }
51 }

View Code

3.poj 3088 Push Botton Lock

 1 // I want to say fuck!
 2 题意： 给n个数字(1<=n<=11) ,从中选出 k 个元素，对于每一种情况，k个元素，求能分出几种集合。
 3        一个元素只能在一个集合，一个集合中的元素是无序的，集合与集合之间是有序的。
 4        这个是一种特殊的数转化过来的。
 5 思路： n中选k个就有Cn1  Cn2 Cn3 .... Cnn这些情况。
 6        对于每一种情况，求dp[i][j]代表，有i个元素，j个集合，则满足递推式
 7        dp[i][j]=j*dp[i-1][j]+dp[i-1][j-1];
 8        当然，集合与集合直接是无序的，所以最后的时候，要乘 阶乘j.(集合的个数）
 9 #include<stdio.h>
10 typedef __int64 LL;
11 
12 LL dp[101][101];
13 LL ans[13][13];
14 LL nima[12]={1};
15 
16 void Init()
17 {
18     int i,j;
19     for(i=1;i<=11;i++) nima[i]=nima[i-1]*i;
20     for(i=0;i<=11;i++) ans[i][0]=1;
21     for(i=1;i<=11;i++)
22     {
23         for(j=1;j<=11;j++)
24         {
25             if(j==1) ans[i][1]=i;
26             else if(j==i) ans[i][i]=1;
27             else ans[i][j]=ans[i-1][j-1]+ans[i-1][j];
28         }
29     }
30     dp[1][1]=1;
31     for(i=2;i<=100;i++)
32         for(j=1;j<=i;j++)
33         {
34             dp[i][j]=j*dp[i-1][j]+dp[i-1][j-1];
35         }
36 }
37 int main()
38 {
39     int T,i,j,n,t;
40     LL sum,hxl;
41     Init();
42     scanf("%d",&T);
43     for(t=1;t<=T;t++)
44     {
45         scanf("%d",&n);
46         sum=0;
47         for(i=1;i<=n;i++)
48         {
49             hxl=0;
50             for(j=1;j<=i;j++)
51                 hxl=hxl+dp[i][j]*nima[j];
52             sum=sum+hxl*ans[n][i];
53         }
54         printf("%d %d %I64d
",t,n,sum);
55     }
56     return 0;
57 }

View Code

4.poj 1496 Word Index

  1 /*写得很糟
  2   用了一个所谓的字符串哈希，发现以前神马都不管用。
  3   ar 和 bc 都是同样的hash值。(⊙o⊙)…，不想改太多，就加了了
  4   字符串判断了。
  5   其实，由于长度<=5 而且 字母不会出现相同，用二进制哈希就很好了。
  6   那么其他方法？？
  7 */
  8 #include<iostream>
  9 #include<stdio.h>
 10 #include<cstring>
 11 #include<string>
 12 #include<cstdlib>
 13 using namespace std;
 14 
 15 struct node
 16 {
 17     int x;
 18     int val;
 19     char str[7];
 20     struct node *next;
 21 }f[100007];
 22 void insert(int x,int num,char c[])
 23 {
 24     int k=x%100007;
 25     node *p;
 26     p=f[k].next;
 27     while(p!=NULL && (p->x!=x ||strcmp(p->str,c)!=0))
 28     {
 29         p=p->next;
 30     }
 31     if(p==NULL)
 32     {
 33         p=(struct node*)malloc(sizeof(struct node));
 34         p->next=f[k].next;
 35         f[k].next=p;
 36         p->x=x;
 37         strcpy(p->str,c);
 38         p->val=num;
 39     }
 40 }
 41 int found(int x,char c[])
 42 {
 43     int k=x%100007;
 44     node *p;
 45     p=f[k].next;
 46     while(p!=NULL && (p->x!=x || strcmp(p->str,c)!=0) )
 47     {
 48         p=p->next;
 49     }
 50     if(p!=NULL) return p->val;
 51     return 0;
 52 }
 53 unsigned int ELFHash(char *str)
 54 {
 55     unsigned int hash = 0;
 56     unsigned int x = 0;
 57     while (*str)
 58     {
 59         hash = (hash << 4) + (*str++);
 60         if ((x = hash & 0xF0000000L) != 0)
 61         {
 62             hash ^= (x >> 24);
 63             hash &= ~x;
 64         }
 65     }
 66     return (hash & 0x7FFFFFFF);
 67 }
 68 void Init()
 69 {
 70     int i,j,s,t,k,tom=0,hxl;
 71     for(i=0;i<100007;i++)
 72     {
 73         f[i].next=NULL;
 74         f[i].val=f[i].x=0;
 75         f[i].str[0]='';
 76     }
 77     char A='a'-1;
 78     char b[10];
 79     for(i=1;i<=26;i++)
 80     {
 81         b[0]=i+A;
 82         b[1]='';
 83         hxl=ELFHash(b);
 84         ++tom;
 85         insert(hxl,tom,b);
 86     }//one
 87     for(i=1;i<=26;i++)
 88     {
 89         for(j=i+1;j<=26;j++)
 90         {
 91             b[0]=A+i;
 92             b[1]=A+j;
 93             b[2]='';
 94             hxl=ELFHash(b);
 95             ++tom;
 96             insert(hxl,tom,b);
 97         }
 98     }//two
 99     for(i=1;i<=26;i++)
100         for(j=i+1;j<=26;j++)
101             for(k=j+1;k<=26;k++)
102             {
103                 b[0]=A+i;
104                 b[1]=A+j;
105                 b[2]=A+k;
106                 b[3]='';
107                 hxl=ELFHash(b);
108                 ++tom;
109                 insert(hxl,tom,b);
110             }//three
111     for(i=1;i<=26;i++)
112     {
113         for(j=i+1;j<=26;j++)
114         {
115             for(k=j+1;k<=26;k++)
116             {
117                 for(s=k+1;s<=26;s++)
118                 {
119                     b[0]=i+A;
120                     b[1]=j+A;
121                     b[2]=k+A;
122                     b[3]=s+A;
123                     b[4]='';
124                     hxl=ELFHash(b);
125                     ++tom;
126                     insert(hxl,tom,b);
127                 }
128             }
129         }
130     }//four
131     for(i=1;i<=26;i++)
132     {
133         for(j=i+1;j<=26;j++)
134         {
135             for(k=j+1;k<=26;k++)
136             {
137                 for(s=k+1;s<=26;s++)
138                 {
139                     for(t=s+1;t<=26;t++)
140                     {
141                         b[0]=i+A;
142                         b[1]=j+A;
143                         b[2]=k+A;
144                         b[3]=s+A;
145                         b[4]=t+A;
146                         b[5]='';
147                         hxl=ELFHash(b);
148                         ++tom;
149                         insert(hxl,tom,b);
150                     }
151                 }
152             }
153         }
154     }//five
155 
156 }
157 int main()
158 {
159     Init();
160     bool flag;
161     char a[10];
162     int i,j,k;
163     while(scanf("%s",a)>0){
164         k=strlen(a);
165         flag=false;
166         for(i=0;i<k;i++)
167         {
168             for(j=i+1;j<k;j++)
169                 if(a[i]>=a[j])flag=true;
170         }
171         if(flag==true){
172             printf("0
");
173             continue;
174         }
175         k=ELFHash(a);
176         k=found(k,a);
177         printf("%d
",k);
178     }
179     return 0;
180 }

View Code

5.poj 1942 Paths on a Grid Cn+m n

 1 #include<stdio.h>
 2 typedef __int64 LL;
 3 
 4 int main()
 5 {
 6     LL n,m,k,sum,i,j;
 7     while(scanf("%I64d%I64d",&n,&m)>0)
 8     {
 9         if(n==0&&m==0)break;
10         k=n+m;
11         if(n>m) n=m;
12         sum=1;
13         for(i=1,j=k;i<=n;i++,j--)
14             sum=sum*j/i;
15         printf("%I64d
",sum);
16 
17     }
18     return 0;
19 }

View Code

6.fzu 2020 组合

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 LL pow_mod(LL a,LL b,LL p)
 9 {
10     LL ans=1;
11     while(b)
12     {
13         if(b&1) ans=(ans*a)%p;
14         b=b>>1;
15         a=(a*a)%p;
16     }
17     return ans;
18 }
19 LL C(LL a,LL b,LL p){
20     if(a<b) return 0;
21     if(b>a-b) b=a-b;
22     LL i,sum1=1,sum2=1;
23     for(i=0;i<b;i++){
24         sum1=(sum1*(a-i))%p;
25         sum2=(sum2*(b-i))%p;
26     }
27     return (sum1*pow_mod(sum2,p-2,p))%p;
28 }
29 LL Lucas(LL n,LL m,LL p)
30 {
31     LL ans=1;
32     while(n&&m&&ans)
33     {
34         ans=(ans*C(n%p,m%p,p))%p;
35         n=n/p;
36         m=m/p;
37     }
38     return ans%p;
39 }
40 int main()
41 {
42     int T;
43     scanf("%d",&T);
44     while(T--){
45         LL n,m,p;
46         scanf("%lld%lld%lld",&n,&m,&p);
47         if(p==1){
48             printf("0
");
49             continue;
50         }
51         printf("%lld
",Lucas(n,m,p));
52     }
53     return 0;
54 }

View Code

 1 /**
 2  题意：C(n,m)%p;  (1<=m<=n<=10^9 ,m<=10^4,m<p<10^9);
 3 
 4  Lucas定理的运用。
 5  Lucas(n,m,p)=C(n%p,m%p)%p*Lucas(n/p,m/p,p); p为素数.
 6  
 7  {
 8  纠正一个错误
 9  for(i=1,j=n;i<=m;i++,j--)
10  sum=(sum*j/i)%p;
11  如果没有取模和溢出的条件下，这样做是可以的。
12  但是，取模就不对啦。例子C(10,4)%107。
13  }
14  后来知道，用了一个叫做乘法逆元的东东。
15 【定义】若整数a,b,p, 满足a·b≡1(mod p).则称a 为b 模p 的乘法逆元, 即a=b- 1mod p.其中, p 是模数。
16  乘法逆元有解的前提是gcd(b,p)=1;由于题意p为素数，那就肯定成立了.
17  应用到组合数中来就是:
18  a!/[b!*(a-b)!] % p == a! * [b!*(a-b)!]-1 %p 
19  ???
20  
21 **/
22 #include<iostream>
23 #include<stdio.h>
24 #include<cstring>
25 #include<cstdlib>
26 using namespace std;
27 typedef long long LL;
28 
29 LL pow_mod(LL a,LL n,LL p)
30 {
31     LL ans=1;
32     while(n)
33     {
34         if(n&1) ans=(ans*a)%p;
35         n=n>>1;
36         a=(a*a)%p;
37     }
38     return ans;
39 }
40 void solve(LL n,LL m,LL p)
41 {
42     LL i,sum1=1,sum2=1;
43     for(i=0;i<m;i++)
44     {
45         sum1=(sum1*(n-i))%p;
46         sum2=(sum2*(m-i))%p;
47     }
48     LL ans=(sum1*pow_mod(sum2,p-2,p))%p;
49     printf("%lld
",ans);
50 }
51 int main()
52 {
53     int T;
54     LL n,m,p;
55     scanf("%d",&T);
56     while(T--){
57     scanf("%lld%lld%lld",&n,&m,&p);
58     n=n%p;
59     if(p==1){
60         printf("0
");
61         continue;
62     }
63     solve(n,m,p);
64     }
65     return 0;
66 }

View Code