您的位置: 首页  >  IT文章  >  Codeforces Round #521 (Div. 3)

Codeforces Round #521 (Div. 3)

分类: IT文章 • 2025-01-26 22:07:55

 A.Frog Jumping

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <set>
 6 #include <map>
 7 #include <vector>
 8 #include <queue>
 9 #include <stack>
10 #include <cmath>
11 #include <cstdlib>
12 
13 using namespace std;
14 typedef long long LL;
15 typedef unsigned long long ull;
16 const int INF = 2147000000;
17 const LL inf = 1e18;
18 const int maxn = 1e5 + 100;
19 const double eps = 1e-9;
20 LL gcd(LL a, LL b){
21     if(!b)return a;
22     return gcd(b, a%b);
23 }
24 LL lcm(LL a, LL b){
25     return a/gcd(a,b)*b;
26 }
27 int n,q;
28 int a, b , k;
29 
30 int main(){
31         scanf("%d",&q);
32         for(int i = 1; i <= q; i++){
33             scanf("%d%d%d",&a,&b,&k);
34             int dep = a - b;
35             LL ans;
36             if(k % 2 == 1){
37                 ans = (LL)dep*(k/2) + a;
38             }else{
39                 ans = (LL)dep* (k/2);
40             }
41             printf("%I64d
",ans);
42         }
43 return 0;
44 }
View Code

 B.Disturbed People

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <set>
 6 #include <map>
 7 #include <vector>
 8 #include <queue>
 9 #include <stack>
10 #include <cmath>
11 #include <cstdlib>
12 
13 using namespace std;
14 typedef long long LL;
15 typedef unsigned long long ull;
16 const int INF = 2147000000;
17 const LL inf = 1e18;
18 const int maxn = 1e5 + 100;
19 const double eps = 1e-9;
20 LL gcd(LL a, LL b){
21     if(!b)return a;
22     return gcd(b, a%b);
23 }
24 LL lcm(LL a, LL b){
25     return a/gcd(a,b)*b;
26 }
27 int n,q;
28 int a[maxn],b[maxn];
29 
30 int main(){
31     scanf("%d",&n);
32     for(int i =1 ;i<=n;i++){
33         scanf("%d",&b[i]);
34         a[i]=b[i];
35     }
36 
37     int ans = 0;
38     for(int i = 2 ; i<n; i++){
39         if(a[i]==0&&a[i-1]==1&&a[i+1]==1){
40             ans++;
41             a[i+1]=0;
42         }
43     }
44     for(int i =1;i<=n;i++){
45         a[i] = b[i];
46     }
47     int ans2= 0;
48     for(int i = n-1; i>=2; i--  ){
49         if(a[i]==0&&a[i-1]==1&&a[i+1]==1){
50             ans2++;
51             a[i-1]=0;
52         }
53     }
54     printf("%d
",min(ans,ans2));
55 return 0;
56 }
View Code

C.Good Array

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <set>
 6 #include <map>
 7 #include <vector>
 8 #include <queue>
 9 #include <stack>
10 #include <cmath>
11 #include <cstdlib>
12 
13 using namespace std;
14 typedef long long LL;
15 typedef unsigned long long ull;
16 const int INF = 2147000000;
17 const LL inf = 1e18;
18 const int maxn = 2e5 + 100;
19 const double eps = 1e-9;
20 LL gcd(LL a, LL b){
21     if(!b)return a;
22     return gcd(b, a%b);
23 }
24 LL lcm(LL a, LL b){
25     return a/gcd(a,b)*b;
26 }
27 int n,q;
28 LL sum[maxn];
29 struct Node{
30     int a,id;
31     bool operator <(const Node& rhs)const{
32         return a< rhs.a;
33     }
34 }a[maxn];
35 int main(){
36     scanf("%d",&n);
37     for(int i =1 ;i<=n;i++){
38         scanf("%d",&a[i].a);
39         a[i].id = i;
40     }
41     if(n==2){
42         printf("0
");
43         printf("
");
44         return 0;
45     }
46     sort(a+1,a+1+n);
47     for(int i =1;i<=n;i++)
48         sum[i]=sum[i-1]+a[i].a;
49 
50     vector<int>ans;
51     for(int i = n-1;i>=1;i--){
52         if(a[n].a == sum[n-1]-a[i].a){
53             ans.push_back(a[i].id);
54         }
55     }
56     if(a[n-1].a == sum[n-2]){
57         ans.push_back(a[n].id);
58     }
59     printf("%d
",ans.size());
60     for(int i = 0;i<ans.size();i++){
61         printf("%d ",ans[i]);
62     }
63     printf("
");
64 return 0;
65 }
View Code

D.Cutting Out

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <set>
 6 #include <map>
 7 #include <vector>
 8 #include <queue>
 9 #include <stack>
10 #include <cmath>
11 #include <cstdlib>
12 
13 using namespace std;
14 typedef long long LL;
15 typedef unsigned long long ull;
16 const int INF = 2147000000;
17 const LL inf = 1e18;
18 const int maxn = 2e5 + 100;
19 const double eps = 1e-9;
20 LL gcd(LL a, LL b){
21     if(!b)return a;
22     return gcd(b, a%b);
23 }
24 LL lcm(LL a, LL b){
25     return a/gcd(a,b)*b;
26 }
27 int n,k;
28 int s[maxn],a[maxn],b[maxn],ans[maxn];
29 struct Node{
30     int num,id;
31     bool operator <(const Node &rhs)const{
32         return num > num;
33     }
34 }node[maxn];
35 int Max=-1;
36 bool check(int mid){
37     int num = 0;
38     for(int i = 1; i<=Max; i++)
39         b[i] = node[i].num;
40     for(int i = 1; i <= Max; i++){
41         while(b[i]>=mid){
42             b[i]-=mid;
43             num++;
44         }
45     }
46     if(num>=k)
47         return true;
48     return false;
49 }
50 int main(){
51     scanf("%d%d",&n,&k);
52     for(int i = 1; i<=n;i++){
53         scanf("%d",&a[i]);
54         Max = max(Max,a[i]);
55         node[a[i]].num++;
56         node[a[i]].id=a[i];
57     }
58     sort(node+1,node+1+Max);
59     int l = 1,r = n;
60     int ANS = 1;
61     while(l<=r){
62         int mid = l+(r-l)/2;
63         if(check(mid)){
64             ANS=mid;
65             l = mid+1;
66         }else
67             r=mid-1;
68     }
69    // printf("!!%d
",ANS);
70     for(int i =1 ;i<=Max;i++)
71         b[i]=node[i].num;
72     int j = 0;
73     for(int i = 1; i <=Max;i++){
74         while(j<k&&b[i]>=ANS){
75             j++;
76             b[i]-=ANS;
77             ans[j]=node[i].id;
78         }
79     }
80     for(int i = 1; i<=k;i++){
81         printf("%d ",ans[i]);
82     }
83 return 0;
84 }
View Code

E.Thematic Contests

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <set>
 6 #include <map>
 7 #include <vector>
 8 #include <queue>
 9 #include <stack>
10 #include <cmath>
11 #include <cstdlib>
12 
13 using namespace std;
14 typedef long long LL;
15 typedef unsigned long long ull;
16 const int INF = 2147000000;
17 const LL inf = 1e18;
18 const int maxn = 2e5 + 100;
19 const double eps = 1e-9;
20 LL gcd(LL a, LL b){
21     if(!b)return a;
22     return gcd(b, a%b);
23 }
24 LL lcm(LL a, LL b){
25     return a/gcd(a,b)*b;
26 }
27 int n;
28 int a[maxn],num[maxn];
29 vector<int>V;
30 int main(){
31     scanf("%d",&n);
32     for(int i = 1; i <= n; i++){
33         scanf("%d",&a[i]);
34         V.push_back(a[i]);
35     }
36     sort(V.begin(),V.end());
37     V.erase(unique(V.begin(),V.end()),V.end());
38 
39     for(int i = 1; i <= n; i++){
40         int pos = lower_bound(V.begin(),V.end(),a[i]) - V.begin() + 1;
41         num[pos]++;
42     }
43     sort(num+1,num+1+V.size());
44     int ans = 0;
45     for(int i = 1; i <= n; i ++){
46         int last = i,res = 0;
47         int pos = lower_bound(num+1,num+1+V.size(),i) - num;
48         while(pos <= V.size()){
49              res += last;
50              last = 2*last;
51              pos = lower_bound(num+pos+1, num+1+V.size(),last) - num;
52         }
53         ans = max(ans, res);
54     }
55     printf("%d
",ans);
56 return 0;
57 }
View Code

F1.Pictures with Kittens (easy version)

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <set>
 6 #include <map>
 7 #include <vector>
 8 #include <queue>
 9 #include <stack>
10 #include <cmath>
11 #include <cstdlib>
12 
13 using namespace std;
14 typedef long long LL;
15 typedef unsigned long long ull;
16 const int INF = 2147000000;
17 const LL inf = 1e18;
18 const int maxn = 200 + 100;
19 const double eps = 1e-9;
20 LL gcd(LL a, LL b){
21     if(!b)return a;
22     return gcd(b, a%b);
23 }
24 LL lcm(LL a, LL b){
25     return a/gcd(a,b)*b;
26 }
27 int n,k,x;
28 int a[maxn];
29 LL f[maxn][maxn];
30 
31 int main(){
32     scanf("%d%d%d",&n,&k,&x);
33     for(int i = 1; i<=n;i++){
34         scanf("%d",&a[i]);
35     }
36     memset(f,-1,sizeof(f));
37     for(int i =1 ;i<=k;i++)
38         f[i][1]=a[i];
39 
40     for(int i = 1; i<=n;i++){
41         for(int j = 2; j <=x;j++){
42             for(int l = i-1;l>=max(1,i-k);l--){
43                 if(f[l][j-1]!=-1){
44                     f[i][j]=max(f[i][j],f[l][j-1]+a[i]);
45                 }
46             }
47         }
48     }
49     LL ans = -1;
50     for(int i = n; i >= max(n-k+1,1); i--){
51         if(f[i][x]!=-1){
52             ans = max(ans,f[i][x]);
53 //            printf("%d
",i);
54         }
55     }
56     printf("%I64d
",ans);
57 return 0;
58 }
View Code

F2.Pictures with Kittens (hard version)

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <set>
 6 #include <map>
 7 #include <vector>
 8 #include <queue>
 9 #include <stack>
10 #include <cmath>
11 #include <cstdlib>
12 
13 using namespace std;
14 typedef long long LL;
15 typedef unsigned long long ull;
16 const int INF = 2147000000;
17 const LL inf = 1e18;
18 const int maxn = 5000 + 100;
19 const double eps = 1e-9;
20 LL gcd(LL a, LL b){
21     if(!b)return a;
22     return gcd(b, a%b);
23 }
24 LL lcm(LL a, LL b){
25     return a/gcd(a,b)*b;
26 }
27 int n,k,x;
28 int a[maxn];
29 LL f[maxn][maxn];
30 
31 int main(){
32     scanf("%d%d%d",&n,&k,&x);
33     for(int i = 1; i<=n;i++){
34         scanf("%d",&a[i]);
35     }
36     memset(f,-1,sizeof(f));
37     deque<int>q;
38 
39     for(int i =1 ;i<=k;i++){
40         f[i][1]=a[i];
41     }
42     q.push_back(0);
43     for(int j = 2; j <= x; j++){
44         for(int i = 1; i <= n; i++){
45             while(!q.empty()&&i-q.front()>k)
46                 q.pop_front();
47             if(q.empty())
48                 f[i][j] = -1;
49             else
50                 f[i][j] = f[q.front()][j-1] + a[i];
51            // printf("%d %d
",i,q.front());
52             while(!q.empty()&&f[q.back()][j-1] < f[i][j-1])
53                 q.pop_back();
54             if(f[i][j-1]!=-1)
55                 q.push_back(i);
56         }
57         q.clear();
58     }
59     LL ans = -1;
60     for(int i = n-k+1; i <= n; i++){
61         if(f[i][x]!=-1){
62             ans = max(ans,f[i][x]);
63         }
64     }
65     printf("%I64d
",ans);
66 return 0;
67 }
View Code

相关推荐