Educational Codeforces Round 66 (Rated for Div. 2)

A题：From Hero to Zero

如果能除k，那么就直接除k就可以了，不能的话就减去n%k，这样循环下来，速度很快，log(n)时间内

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cmath>
 6 typedef long long ll;
 7 using namespace std;
 8 int t;
 9 ll n,k;
10 int main(){
11     scanf("%d",&t);
12     while(t--){
13         scanf("%lld%lld",&n,&k);
14         ll ans=0;
15         while(n!=0){
16             if(n%k==0){n/=k;ans++;}
17             else{
18                  ans+=(n%k);n-=(n%k);
19             }
20         }
21         printf("%lld
",ans);
22     }
23 
24     return 0;
25 }

View Code

B题：Catch Overflow!

这个题首先是很好想的，操作很简单，就是模拟一下栈的运行就ok了！

for是入栈，end是出栈，add是进行一次操作。

首先我们可以知道一点：对于一般的操作直接模拟就ok，但是如果超过了(1ll<<32)怎么办？

我们把栈内最大的数让他不超过(1ll<<32)即可，感觉我的写法有一点点复杂，导致最后跳了很久才跳出来，

下面是一个简介版的代码，来自这场的第二名：

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 using ll = long long;
 5 const ll MAXV = (1ll<<32);
 6 
 7 int main() {
 8     ios_base::sync_with_stdio(false);
 9     cin.tie(0);
10 
11     int n;
12     cin >> n;
13 
14     ll res = 0;
15     vector<ll> stack = {1};
16     for (int i = 0; i < n; ++i) {
17         string str;
18         cin >> str;
19         if (str == "add") {
20             res += stack.back();
21         } else if (str == "for") {
22             ll k;
23             cin >> k;
24             stack.push_back(min(MAXV, k*stack.back()));
25         } else if (str == "end") {
26             stack.pop_back();
27         }
28     }
29     if (res >= MAXV) cout << "OVERFLOW!!!
";
30     else cout << res << '
';
31 }

View Code

感觉我的写法就很不高明啊？？？？？？？而且我在防溢出上面想了很久，就很愚蠢。

下面是我的代码；

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cmath>
 6 typedef long long ll;
 7 using namespace std;
 8 const ll Max=((1ll<<32)-1);
 9 const int maxn=(int)(2e5+100);
10 int t;
11 ll n,ans=0;
12 char sz[110];
13 ll op[maxn],h[maxn];
14 int main(){
15     scanf("%d",&t);
16     int flag=0,cnt=0,qflag=1;
17     op[0]=1;
18     while(t--){
19         scanf("%s",sz+1);
20         if(cnt==0){
21             if(sz[1]=='a'){
22                 ans=ans+1;
23                 if(ans>Max){flag=1;break;}
24             }else {
25                 scanf("%lld", &n);
26                 cnt++;
27                 op[cnt] = (ll) op[cnt - 1] * n;
28                 h[cnt] = 0;
29             }
30         }else{
31             if(sz[1]=='a'){
32                if(qflag==0){
33                    flag=1;break;
34                }else if(ans+op[cnt]>Max){
35                    flag=1;break;
36                }else{
37                    ans+=op[cnt];
38                }
39             }else if(sz[1]=='e'){
40                 cnt--;
41                 if(h[cnt]==0){
42                     qflag=1;
43                 }
44             }else{
45                 scanf("%lld",&n);
46                 cnt++;
47                 op[cnt]=(ll)op[cnt-1]*n;
48                 if(op[cnt]>Max||h[cnt-1]==1){
49                     qflag=0;
50                     h[cnt]=1;
51                 }else{
52                     h[cnt]=0;
53                 }
54             }
55         }
56         //cout<<ans<<endl;
57     }
58     //cout<<ans<<"   "<<Max<<endl;
59     if(flag){printf("OVERFLOW!!!
");}
60     else printf("%lld
",ans);
61     return 0;
62 }
63 /*
64 
65 14
66 add
67 for 64
68 for 64
69 for 64
70 for 64
71 for 64
72 for 4
73 add
74 end
75 end
76 end
77 end
78 end
79 end
80 */

View Code

C题： Electrification

这个题感觉也不是很难想，我们枚举一下这k个点的最右边，那么这k个点的最左边就出来了，然后我们每次取一下中间看一下就ok！

然后更新一下答案，感觉这是一个简单题，但是我还是搞了很久，差不多有20min到30min的样子。

下面是我的代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cmath>
 6 typedef long long ll;
 7 using namespace std;
 8 const int maxn=(int)(2e5+100);
 9 int t,n,k;
10 ll num[maxn];
11 int main(){
12     scanf("%d",&t);
13     while(t--){
14         scanf("%d%d",&n,&k);
15         for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
16         sort(num+1,num+n+1);
17         k++;
18         if(k==1){
19             printf("%lld
",num[1]);
20             continue;
21         }
22         ll ans=(ll)(1e18+100),tmp=0;
23         for(int i=k;i<=n;i++){
24             ll l1=num[i-k+1],r1=num[i];
25             ll res=(r1-l1)/2;
26             if((r1-l1)%2==1) res++;
27             if(res<ans){
28                 tmp=l1+res;
29                 ans=res;
30             }
31         }
32         for(int i=n-k+1;i>=1;i--){
33             ll l1=num[i],r1=num[i+k-1];
34             ll res=(r1-l1)/2;
35             if((r1-l1)%2==1) res++;
36             if(res<ans){
37                 tmp=l1+res;
38                 ans=res;
39             }
40         }
41         printf("%lld
",tmp);
42     }
43     return 0;
44 }
45 /*
46 
47 14
48 add
49 for 64
50 for 64
51 for 64
52 for 64
53 for 64
54 for 4
55 add
56 end
57 end
58 end
59 end
60 end
61 end
62 */

View Code

下面是这样前几名的代码：

就写的很简洁：

 1 #include <algorithm>  
 2 #include <iostream>  
 3 #include <sstream>  
 4 #include <string>  
 5 #include <vector>  
 6 #include <queue>  
 7 #include <set>  
 8 #include <map>  
 9 #include <cstdio>  
10 #include <cstdlib>  
11 #include <cctype>  
12 #include <cmath>  
13 #include <cstring>
14 #include <list>  
15 #include <cassert>
16 #include <climits>
17 #include <bitset>
18 using namespace std;  
19  
20 #define PB push_back  
21 #define MP make_pair  
22 #define SZ(v) ((int)(v).size())  
23 #define FOR(i,a,b) for(int i=(a);i<(b);++i)  
24 #define REP(i,n) FOR(i,0,n)  
25 #define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
26 #define REPE(i,n) FORE(i,0,n)  
27 #define FORSZ(i,a,v) FOR(i,a,SZ(v))  
28 #define REPSZ(i,v) REP(i,SZ(v))  
29 typedef long long ll;  
30 int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
31  
32 const int MAXN=200000;
33  
34 int n,k;
35 int a[MAXN];
36  
37 int solve() {
38     int best=INT_MAX,ret=-1;
39     REP(i,n-k) {
40         int cur=a[i+k]-a[i];
41         if(cur<best) best=cur,ret=a[i]+cur/2;
42     }
43     return ret;
44 }
45  
46 void run() {
47     scanf("%d%d",&n,&k);
48     REP(i,n) scanf("%d",&a[i]);
49     printf("%d
",solve());
50 }
51  
52 int main() {
53     int ncase; scanf("%d",&ncase); FORE(i,1,ncase) run();
54     return 0;
55 }

View Code