首页 > 代码库 > 【集训第五天·考试+数位】考试真心用不上算法~~~~~~~~~

【集训第五天·考试+数位】考试真心用不上算法~~~~~~~~~

  早上,考了一堂试,noip2011D2的题,只得了150 。。。。

  T1是一道水题,自己在草稿纸上画画就能推出来,要用到杨辉三角。

  T2有点扯淡。原题http://www.codevs.cn/problem/1138/

  我看数据非常大,本以为是高级数据结构,但自己不会写于是跑了个二分+暴力,想行到竟然50分,他们写的高级数据结构没分。 正解是 二分+前缀优化暴力  。在每次check时先跑一遍所有矿物求出前缀,再循环每个区间,用 (r)-(l-1) 即可。

  T3是一道贪心题,非常好的贪心题目。原题http://www.codevs.cn/problem/1139/

  首先呢,贪心策略肯定是在人多的时候用加速器。但用了加速器后到了下一个路口是否等人?如果等了,用了和没用一样的效果。我们可以预处理出每个站到下一个不用等人的站的位置,记录每个站的下车人数,用前缀和,减去就可以得到在某一阶段的车上人数。循环来寻找某个路上人最多且不用等的时候,ans减去人数即可,由此我们知道需要循环遍历k来消耗完所有的加速器。

  PS:不能一次消耗很多加速器,因为每次用完加速器后,车子需要等人的站要相对变化,所以一次只用一个加速器。

 

  然后,下午学习了数位dp。

  数位dp关键就是考虑限制,记忆化搜索,从高位到低位依次搜索,还是比较见到(比后缀数组好多了,至少我这么觉得)。  关键:把数看成一个串

  下面放两道晚上写的题。

  1.含有13且被13整除的数有多少个

  裸题,加一个限制表明到当前这位是否已经出现13,再加一个限制表明到此位的mod

CODE:

 

技术分享
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int bit[15],dp[15][15][3];
 7 int read(){
 8     char c;int f=1,x=0;c=getchar();
 9     while(c>9||c<0){if(c==-)f=-1;c=getchar();}
10     while(c<=9&&c>=0)x=x*10+c-0,c=getchar();
11     return f*x;
12 }
13 
14 int dfs(int pos,int mod,int have,int limit){
15     if(!pos)return mod==0&&have==2;
16     if(!limit&&dp[pos][mod][have]!=-1)return dp[pos][mod][have];
17     int num=limit?bit[pos]:9;
18     int h,m,ans=0;
19     for(int i=0;i<=num;i++){
20         m=(mod*10+i)%13;h=have;
21         if(have==0&&i==1)h=1;
22         if(have==1&&i!=1)h=0;
23         if(have==1&&i==3)h=2;
24         ans+=dfs(pos-1,m,h,limit&&i==num);
25     }
26     if(!limit)dp[pos][mod][have]=ans;
27     return ans;
28 }
29 
30 int main(){
31     int n,len;
32     while(scanf("%d",&n)!=EOF){
33         memset(dp,-1,sizeof(dp));
34         memset(bit,0,sizeof(bit));
35         len=0;
36         while(n){
37             bit[++len]=n%10;
38             n/=10;
39         }
40         printf("%d\n",dfs(len,0,0,1));
41     }
42 
43     return 0;
44 }
View Code

 

  

  2.平衡数

  枚举作为支点的数的位置,记录到当前位置的和,若最后和为0,则是平衡数

CODE:

技术分享
 1 /*
 2 注释  : 
 3  42 bit[++len]=n%10;  46行应为for(int i=1;i<=len;i++)ans+=dfs(len,i,0,1);
 4 26行应为  if(pos==-1)...... 
 5 为什么??我也想问为什么  :
 6 
 7 数组大小  别人 len++比自己少用一位 
 8 
 9 */
10 #include<cstdio>
11 #include<iostream>
12 #include<cstring>
13 #include<algorithm>
14 #define inf 2147483647
15 using namespace std;
16 int bit[20];
17 long long dp[20][20][2005];
18 long long read(){
19     char c;int f=1;long long x=0;c=getchar();
20     while(c>9||c<0){if(c==-)f=-1;c=getchar();}
21     while(c<=9&&c>=0)x=x*10+c-0,c=getchar();
22     return f*x;
23 }
24 
25 long long dfs(int pos,int o,int sum,int limit){
26     if(pos==0)return sum==0;
27     if(sum<0)return 0;
28     if(!limit&&dp[pos][o][sum]!=-1)return dp[pos][o][sum];
29     int num=limit?bit[pos]:9;long long ans=0; 
30     for(int i=0;i<=num;i++){
31         int next=sum;
32         next+=(pos-o)*i;
33         ans+=dfs(pos-1,o,next,limit&&i==num);
34     } 
35     if(!limit)dp[pos][o][sum]=ans;
36     return ans;
37 }
38 
39 long long solve(long long n){
40     int len=0;
41     while(n){
42         bit[++len]=n%10;
43         n/=10;
44     }
45     long long ans=0;
46     for(int i=1;i<=len;i++)ans+=dfs(len,i,0,1);
47     return ans-len+1;
48 }
49 
50 int main(){
51     int T;
52     scanf("%d",&T);
53     memset(dp,-1,sizeof(dp));
54     while(T--){
55         long long l,r;
56         cin>>l>>r;
57         cout<<solve(r)-solve(l-1)<<endl;
58     }
59     return 0;
60 }
View Code

 

  啊!明天出去考试,考完就要学常规了,好tm恐惧啊。。。。

 

【集训第五天·考试+数位】考试真心用不上算法~~~~~~~~~