Codeforces Round #407 (Div. 2)

分析：直接统计装完每一份需要多少个袋子即可

 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 using namespace std;
 5 const int maxn=100000+10;
 6 int a[maxn];
 7 int n,k;
 8 int main()
 9 {
10     while(cin>>n>>k)
11     {
12         int ans=0;
13         for(int i=0;i<n;i++){
14             scanf("%d",&a[i]);
15             if(a[i]%k==0)
16                 ans+=a[i]/k;
17             else
18                 ans+=a[i]/k+1;
19         }
20         if(ans%2==0)
21             ans/=2;
22         else
23             ans=ans/2+1;
24         cout<<ans<<endl;
25 
26     }
27     return 0;
28 }

View Code

B题

分析：非常坑的一道题，需要考虑的边界情况包括|b|>l,b=0,q=0,q=1,q=-1，然后其他的情况直接用map来统计一下就好了qwq

 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "string"
 5 #include "cmath"
 6 #include "vector"
 7 #include "algorithm"
 8 #include "map"
 9 using namespace std;
10 const int maxn=100000+10;
11 long long  a[maxn];
12 long long b,q,l,m;
13 int main()
14 {
15     while(cin>>b>>q>>l>>m){
16         map<long long,long long>mp;
17         for(int i=0;i<m;i++){
18             cin>>a[i];
19             mp[a[i]]=1;
20         }
21         if(abs(b)>l){
22             cout<<"0"<<endl;
23             continue;
24         }
25         if(b==0){
26             if(mp[0]){
27                 cout<<"0"<<endl;
28             }else{
29                 cout<<"inf"<<endl;
30             }
31             continue;
32         }
33         if(q==0){
34             if(mp[b]){
35                 if(mp[0]){
36                     cout<<"0"<<endl;
37                 }else{
38                     cout<<"inf"<<endl;
39                 }
40             }else{
41                 if(mp[0]){
42                     cout<<"1"<<endl;
43                 }else{
44                     cout<<"inf"<<endl;
45                 }
46             }
47             continue;
48         }
49         int cnt=0;
50         if(q==1){
51             if(mp[b]){
52                 cout<<"0"<<endl;
53             }else{
54                 cout<<"inf"<<endl;
55             }
56             continue;
57         }
58         int ans=0;
59         if(q==-1){
60             if(!mp[b])
61                 ans++;
62             if(!mp[-b])
63                 ans++;
64             if(ans!=0){
65                 cout<<"inf"<<endl;
66             }else{
67                 cout<<"0"<<endl;
68             }
69             continue;
70         }
71         while(abs(b)<=l){
72             //if(abs(q)==1)
73                 //flag++;
74             if(!mp[b])
75                 cnt++;
76             //if(flag==2) break;
77             b*=q;
78         }
79             cout<<cnt<<endl;
80     }
81     return 0;
82 }

View Code

C题

分析:计算出最大的f的值，我们需要注意区分奇偶位的正负关系，然后统计出最大的区间即可

 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "string"
 5 #include "cmath"
 6 #include "algorithm"
 7 using namespace std;
 8 const int maxn=100000+10;
 9 long long a[maxn];
10 long long dp1[maxn],dp2[maxn];
11 long long f1[maxn],f2[maxn];
12 int n;
13 int main()
14 {
15     while(cin>>n)
16     {
17         memset(dp1,0,sizeof(dp1));
18         memset(dp2,0,sizeof(dp2));
19         memset(f1,0,sizeof(f1));
20         memset(f2,0,sizeof(f2));
21         for(int i=1;i<=n;i++){
22             scanf("%lld",&a[i]);
23             if(i==1)
24                 dp1[i]=dp2[i]=a[i];
25             else
26                 dp1[i]=dp2[i]=abs(a[i]-a[i-1]);
27         }
28         for(int i=1;i<=n;i++){
29             if(i%2)
30                 dp1[i]*=-1;
31             else
32                 dp2[i]*=-1;
33         }
34         long long ans1=0,ans2=0;
35         for(int i=2;i<=n;i++){
36             f1[i]=max(f1[i-1]+dp1[i],dp1[i]);
37             ans1=max(ans1,f1[i]);
38         }
39         for(int i=2;i<=n;i++){
40             f2[i]=max(f2[i-1]+dp2[i],dp2[i]);
41             ans2=max(ans2,f2[i]);
42         }
43         cout<<max(ans1,ans2)<<endl;
44     }
45     return 0;
46 }

View Code