2017-10-02-afternoon

T1 最大值(max)

Time Limit:1000ms   Memory Limit:128MB

题目描述

LYK有一本书,上面有很多有趣的OI问题。今天LYK看到了这么一道题目:

这里有一个长度为n的正整数数列ai(下标为1~n)。并且有一个参数k。

你需要找两个正整数x,y,使得x+k<=y,并且y+k-1<=n。并且要求a[x]+a[x+1]+…+a[x+k-1]+a[y]+a[y+1]+…+a[y+k-1]最大。

LYK并不会做,于是它把题扔给了你。

输入格式(max.in)

    第一行两个数n,k。

    第二行n个数,表示ai。

输出格式(max.out)

两个数表示x,y。若有很多种满足要求的答案,输出x最小的值,若x最小仍然还有很多种满足要求的答案,输出y最小的值。

输入样例

5 2

6 1 1 6 2

输出样例

1 4

对于30%的数据n<=100。

对于60%的数据n<=1000

对于100%的数据1<=n<=100000,1<=k<=n/2,1<=ai<=10^9。

 1 #include <cstdio>
 2 
 3 #define LL long long
 4 
 5 inline void read(LL &x)
 6 {
 7     x=0; register char ch=getchar();
 8     for(; ch>'9'||ch<'0'; ) ch=getchar();
 9     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
10 }
11 
12 const int N(100005);
13 LL n,k,r,x,y,a[N],sum[N],ans;
14 
15 int Presist()
16 {
17     freopen("max.in","r",stdin);
18     freopen("max.out","w",stdout);
19     read(n),read(k); r=n-k+1;
20     for(int i=1; i<=n; ++i)
21         read(a[i]),sum[i]=sum[i-1]+a[i];
22     for(x=1; x<=n; ++x)
23       if(ans<sum[r]-sum[x-1]) ans=sum[r]-sum[x-1];
24     for(x=1; x<=n; ++x)
25       if(ans==sum[r]-sum[x-1]) { y=x+k; break; }
26     for(; y<=r; ++y)
27       if(sum[y]-sum[x-1]==ans) break;
28     printf("%I64d %I64d",x,y);
29     return 0;
30 }
31 
32 int Aptal=Presist();
33 int main(int argc,char**){;}
读错题目全挂掉

 处理出以每个点为起点,向后延伸k个单位长度的区间和,和每个点的后缀最大值

 1 #include <cstdio>
 2 
 3 #define LL long long
 4 #define max(a,b) (a>b?a:b)
 5 
 6 inline void read(LL &x)
 7 {
 8     x=0; register char ch=getchar();
 9     for(; ch>'9'||ch<'0'; ) ch=getchar();
10     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
11 }
12 
13 const int N(100005);
14 LL n,k,r,x,y,max,sum[N];
15 LL pos[N],maxn[N],sumk[N];
16 
17 int Presist()
18 {
19     freopen("max.in","r",stdin);
20     freopen("max.out","w",stdout);
21     read(n),read(k); r=n-k+1;
22     for(int i=1; i<=n; ++i) read(sum[i]),sum[i]+=sum[i-1];
23     for(int i=1; i<=r; ++i)
24         sumk[i]=sum[i+k-1]-sum[i-1];
25     for(int i=r; i; i--)
26         if(sumk[i]>maxn[i+1]) maxn[i]=sumk[i],pos[i]=i;
27         else maxn[i]=maxn[i+1],pos[i]=pos[i+1];
28     for(int i=1; i<=r-k; ++i)
29         if(sumk[i]+maxn[i+k]>max) max=sumk[i]+maxn[i+k],x=i,y=pos[i+k];
30         else if(sumk[i]+maxn[i+k]==max) y=y<pos[i+k]?y:pos[i+k];
31     printf("%I64d %I64d",x,y);
32     return 0;
33 }
34 
35 int Aptal=Presist();
36 int main(int argc,char**){;}
AC

T2 吃东西(eat)

Time Limit:2000ms   Memory Limit:1024MB

题目描述

一个神秘的村庄里有4家美食店。这四家店分别有A,B,C,D种不同的美食。LYK想在每一家店都吃其中一种美食。每种美食需要吃的时间可能是不一样的。

现在给定第1家店A种不同的美食所需要吃的时间a1,a2,…,aA。

    给定第2家店B种不同的美食所需要吃的时间b1,b2,…,bB。

以及c和d。

LYK拥有n个时间,问它有几种吃的方案。

输入格式(eat.in)

    第一行5个数分别表示n,A,B,C,D。

    第二行A个数分别表示ai。

    第三行B个数分别表示bi。

    第四行C个数分别表示ci。

    第五行D个数分别表示di。

输出格式(eat.out)

一个数表示答案。

输入样例

11 3 1 1 1

4 5 6

3

2

1

输出样例

2

对于30%的数据A,B,C,D<=50

对于另外30%的数据n<=1000。

对于100%的数据1<=n<=100000000,1<=A,B,C,D<=5000,0<=ai,bi,ci,di<=100000000。

 1 #include <algorithm>
 2 #include <cstdio>
 3 
 4 inline void read(int &x)
 5 {
 6     x=0; register char ch=getchar();
 7     for(; ch>'9'||ch<'0'; ) ch=getchar();
 8     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
 9 }
10 const int N(5233);
11 int n,na,nb,nc,nd,sa,sb,sc;
12 int a[N],b[N],c[N],d[N],ans;
13 
14 int Presist()
15 {
16     freopen("eat.in","r",stdin);
17     freopen("eat.out","w",stdout);
18     read(n),read(na),read(nb),read(nc),read(nd);
19     for(int i=1; i<=na; ++i) read(a[i]); std::sort(a+1,a+na+1);
20     for(int i=1; i<=nb; ++i) read(b[i]); std::sort(b+1,b+nb+1);
21     for(int i=1; i<=nc; ++i) read(c[i]); std::sort(c+1,c+nc+1);
22     for(int i=1; i<=nd; ++i) read(d[i]); std::sort(d+1,d+nd+1);
23     for(int i=1; i<=na; ++i)
24     {
25         sa=a[i]; if(sa>n) break;
26         for(int j=1; j<=nb; ++j)
27         {
28             sb=sa+b[j]; if(sb>n) break;
29             for(int p=1; p<=nc; ++p)
30             {
31                 sc=sb+c[p]; if(sc>n) break;
32                 for(int q=1; q<=nd; ++q)
33                 {
34                     if(sc+d[q]>n) break;
35                     else ans++;
36                 }
37             }
38         }
39     }
40     printf("%d
",ans);
41     return 0;
42 }
43 
44 int Aptal=Presist();
45 int main(int argc,char**){;}
30分 暴力

 sum记录C D 每种时间出现的次数,枚举 i,j 判断 n-a[i]-b[j] 的次数

 1 #include <algorithm>
 2 #include <cstdio>
 3 
 4 #define LL long long
 5 
 6 #define max(a,b) (a>b?a:b)
 7 #define min(a,b) (a<b?a:b)
 8 
 9 inline void read(LL &x)
10 {
11     x=0; register char ch=getchar();
12     for(; ch>'9'||ch<'0'; ) ch=getchar();
13     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
14 }
15 const int N(5233);
16 LL n,food[5][N],f[5][N],ans;
17 int sum[200000005];
18 bool flag;
19 
20 inline void violence_30()    //50^4,暴力判断 30分 
21 {
22     for(int i=1; i<=food[1][0]; ++i)
23       for(int j=1; j<=food[2][0]; ++j)
24         for(int p=1; p<=food[3][0]; ++p)
25           for(int q=1; q<=food[4][0]; ++q)
26           ans+=(food[1][i]+food[2][j]+food[3][p]+food[4][q]<=n);
27 }
28 inline void violence_another_30()    // 分组背包 n*(ABCD)枚举 
29 {
30     for(int i=0; i<=n; ++i) f[0][i]=1;
31     for(int k=1; k<5; ++k)
32       for(int i=0; i<=n; ++i)
33         for(int j=1; j<=food[k][0]; ++j)
34         if(i>=food[k][j]) f[k][i]+=f[k-1][i-food[k][j]];
35     ans=f[4][n];
36 }
37 inline void no_wa_and_all_ac()     
38 {
39     LL minn=2e8+5,maxx=-1;
40     for(int i=1; i<=food[3][0]; ++i)
41         for(int j=1; j<=food[4][0]; ++j)
42         {
43             sum[food[3][i]+food[4][j]]++;
44             minn=min(minn,food[3][i]+food[4][j]);
45             maxx=max(maxx,food[3][i]+food[4][j]);
46         }
47     for(int i=minn; i<=maxx; ++i) sum[i]+=sum[i-1];
48     for(int i=1; i<=food[1][0]; ++i)
49       for(int j=1; j<=food[2][0]; ++j)
50        if(n-food[1][i]-food[2][j]>=0) 
51           ans+=sum[ min(maxx,n-food[1][i]-food[2][j]) ];
52 }
53 
54 int Presist()
55 {
56     freopen("eat.in","r",stdin);
57     freopen("eat.out","w",stdout);
58     read(n); for(int i=1; i<5; ++i) read(food[i][0]);
59     for(int i=1; i<5; ++i)
60       for(int j=1; j<=food[i][0]; ++j)
61           read(food[i][j]);
62     for(int i=1; i<5; ++i)
63         if(food[i][0]>50) flag=1;
64     if(n<=1000) violence_another_30();
65     else if(!flag) violence_30();
66     else no_wa_and_all_ac();
67     printf("%I64d",ans);
68     return 0;
69 }
70 
71 int Aptal=Presist();
72 int main(int argc,char**){;}
AC

T3 分糖果(candy)

Time Limit:1000ms   Memory Limit:128MB

题目描述

总共有n颗糖果,有3个小朋友分别叫做L,Y,K。每个小朋友想拿到至少k颗糖果,但这三个小朋友有一个共同的特点:对3反感。也就是说,如果某个小朋友拿到3颗,13颗,31颗,333颗这样数量的糖果,他就会不开心。(也即它拿到的糖果数量不包含有一位是3)

LYK掌管着这n颗糖果,它想问你有多少种合理的分配方案使得将这n颗糖果全部分给小朋友且没有小朋友不开心。

例如当n=3,k=1时只有1种分配方案,当n=4,k=1时有3种分配方案分别是112,121,211。当n=7,k=2时则不存在任何一种合法的方案。

当然这个答案可能会很大,你只需输出答案对12345647取模后的结果就可以了。

输入格式(candy.in)

    第一行两个数表示n,k。

输出格式(candy.out)

一个数表示方案总数。

输入样例

99999 1

输出样例

9521331

对于30%的数据n<=100

对于50%的数据n<=1000。

对于另外30%的数据k=1。

对于100%的数据3<=n<=10^10000,1<=k<=n/3,且n,k不包含前导0。

 1 #include <cstdio>
 2 
 3 #define LL long long
 4 inline void read(LL &x)
 5 {
 6     x=0; register char ch=getchar();
 7     for(; ch>'9'||ch<'0'; ) ch=getchar();
 8     for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
 9 }
10 LL n,k,ans;
11 
12 inline bool if_cant(LL x)
13 {
14     for(; x; x/=10)
15         if(x%10==3) return 1;
16     return 0;
17 }
18 
19 int Presist()
20 {
21     freopen("candy.in","r",stdin);
22     freopen("candy.out","w",stdout);
23     
24     read(n),read(k);
25     for(LL t,i=k; i<=n; ++i)
26     {
27         if(if_cant(i)) continue;
28         for(LL j=k; j<=n-i; ++j)
29         {
30             if(if_cant(j)) continue;
31             t=n-i-j;
32             ans+=(t>=k&&(!if_cant(t)));
33         }
34     }
35     printf("%I64d
",ans);
36     return 0;
37 }
38 
39 int Aptal=Presist();
40 int main(int argc,char**){;}
50分暴力

数位DP

 1 #include<cstdio>
 2 #include<cstring>
 3 
 4 #define N 10003
 5 
 6 using namespace std;
 7 
 8 const int mod=12345647;
 9 
10 char s[N];
11 int a[N],b[N],dp[N][3][2][2][2];
12 
13 void ADD(int &i,int j)  {  i+=j; if(i>=mod) i-=mod; }
14 
15 int main()
16 {
17     freopen("candy.in","r",stdin);
18     freopen("candy.out","w",stdout);
19     scanf("%s",s+1); int len1=strlen(s+1);
20     for(int i=1;i<=len1;++i) a[i]=s[i]-'0';
21     scanf("%s",s+1); int len2=strlen(s+1);
22     for(int i=1;i<=len2;++i) b[i+len1-len2]=s[i]-'0';
23     dp[0][0][0][0][0]=1;
24     int i,j,k,l,t,I,J,K,L,T;
25     for(i=0;i<len1;i++)
26       for(j=0;j<3;j++)
27         for(k=0;k<2;k++)
28           for(l=0;l<2;l++)
29             for(t=0;t<2;t++)
30                 if(dp[i][j][k][l][t])
31                   for(int s1=0;s1<=9;s1++)
32                     if(s1!=3)
33                       for(int s2=0;s2<=9;s2++)
34                         if(s2!=3)
35                           for(int s3=0;s3<=9;s3++)
36                             if(s3!=3)
37                             {
38                                 I=i+1;
39                                 J=j*10+a[i+1]-s1-s2-s3;
40                                 if(J<0 || J>2) continue;
41                                 if(!k && s1<b[i+1]) continue;
42                                 K=(k || s1>b[i+1]);
43                                 if(!l && s2<b[i+1]) continue;
44                                 L=(l || s2>b[i+1]);
45                                 if(!t && s3<b[i+1]) continue;
46                                 T=(t || s3>b[i+1]);
47                                 ADD(dp[I][J][K][L][T],dp[i][j][k][l][t]);                    
48                             }
49     int ans=0;
50     for(k=0;k<2;k++)
51         for(l=0;l<2;l++)
52             for(t=0;t<2;t++)
53                 ADD(ans,dp[len1][0][k][l][t]);
54     printf("%d",ans);                        
55 }
AC
——每当你想要放弃的时候,就想想是为了什么才一路坚持到现在。
原文地址:https://www.cnblogs.com/Shy-key/p/7653232.html