Educational Codeforces Round 35 (Rated for Div. 2)

时间：2019-03-31 22:00:09 阅读：132 评论：0 收藏：0 [点我收藏+]

Educational Codeforces Round 35 (Rated for Div. 2)

A

模拟

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 5000005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int a[100005];
24 
25 
26 int main(){
27     std::ios::sync_with_stdio(false);
28     int n;
29     cin>>n;
30     int x=0x3f3f3f3f;
31     for(int i=1;i<=n;i++){
32         cin>>a[i];
33         x=min(x,a[i]);
34     }
35     int Min=0x3f3f3f3f;
36     int pre=-1;
37     for(int i=1;i<=n;i++){
38         if(a[i]==x){
39             if(pre==-1) pre=i;
40             else Min=min(Min,i-pre),pre=i;
41         }
42     }
43     cout<<Min<<endl;
44 }

View Code

B

二分

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 5000005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int n,a,b;
24 
25 bool Check(int mid){
26     int sum=a/mid;
27     sum+=b/mid;
28     if(sum>=n) return true;
29     return false;
30 }
31 
32 int main(){
33     std::ios::sync_with_stdio(false);
34     cin>>n>>a>>b;
35     int L=0,R=min(a,b),mid;
36     while(L<=R){
37         mid=L+R>>1;
38         if(Check(mid)){
39             L=mid+1;
40         }
41         else{
42             R=mid-1;
43         }
44     }
45     cout<<R<<endl;
46 }

View Code

C

题意：有三个灯，A将开启这些灯。这些灯一会亮一会不亮。如果第i个灯在第x秒开启，那么它仅在第x,x+ki,x+2*ki……秒时是亮的。 A想要打开灯，使每秒至少有一个灯是亮的。 A想要选择三个整数a，b，c，在第a秒接通第一个灯，在第b秒接通第二个灯，在第c秒接通第三灯，并且在从max（a，b，c）开始的每秒中，至少有一个灯将是亮的。问A是否可以做到。

思路：直接模拟就可以。。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 5000005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int book[1505];
24 
25 int main(){
26     std::ios::sync_with_stdio(false);
27     int a,b,c;
28     cin>>a>>b>>c;
29     book[a]++;
30     book[b]++;
31     book[c]++;
32     if(book[1]) cout<<"YES"<<endl;
33     else if(book[2]>=2) cout<<"YES"<<endl;
34     else if(book[3]>=3) cout<<"YES"<<endl;
35     else if(book[2]&&book[4]>=2) cout<<"YES"<<endl;
36     else cout<<"NO"<<endl;
37 }

View Code

D

题意：给你一个长度为n的序列，有m次操作。每次翻转[l,r]的区间，每次操作后询问序列逆序对个数的奇偶性。

思路：通过多次模拟可以发现一个规律：

1、区间翻转时，区间内的逆序对的个数不影响区间外的逆序对的个数

2、区间翻转，正序对和逆序对数量交换。所以可以判断区间序对数的奇偶性

发现这规律做题就容易了，直接上树状数组搞搞就行

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 5000005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int tree[1505],a[1505];
24 int m,n;
25 int lowbit(int x){return x&(-x);}
26 void add(int x){while(x<=n){tree[x]+=1;x+=lowbit(x);}}
27 int ask(int x){int sum=0;while(x){sum+=tree[x];x-=lowbit(x);}return sum;}
28 
29 
30 int main(){
31     std::ios::sync_with_stdio(false);
32     cin>>n;
33     for(int i=1;i<=n;i++){
34         cin>>a[i];
35     }
36     int sum=0;
37     for(int i=n;i;i--){
38         sum+=ask(a[i]);
39         add(a[i]);
40     }
41     cin>>m;
42     int x,y;
43     int ans=sum&1;
44     for(int i=1;i<=m;i++){
45         cin>>x>>y;
46         int len=y-x+1;
47         len=len*(len-1)/2;
48         if(len&1) ans^=1;
49         if(ans) cout<<"odd"<<endl;
50         else cout<<"even"<<endl;
51     }
52 }

View Code

E

题意：给定 n，m（n>=m），先给出m个数，然后让你补全剩下的n-m个数，使的字典序最大且可以通过栈使它变成1-n的顺序序列

思路：先判断给定的数能不能通过模拟栈的方法顺序输出，可以的话就从大到小补全小于栈顶元素且未出现过的数。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define IT set<ll>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 5000005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=998244353;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 int a[200005];
24 stack<int>st;
25 
26 int main(){
27     std::ios::sync_with_stdio(false);
28     int n,m;
29     cin>>n>>m;
30     for(int i=1;i<=m;i++){
31         cin>>a[i];
32     }
33     int k=n-m;
34     int i=1;
35     int co=1;
36     int flag=0;
37     while(i<=m){
38         if(co!=a[i]){
39             st.push(a[i]);
40             i++;
41         }
42         else{
43             co++;
44             i++;
45             while(!st.empty()&&st.top()==co){
46                 co++;
47                 st.pop();
48             }
49         }
50     }
51     if(!st.empty()){
52         int pre=st.top();
53         st.pop();
54         while(!st.empty()){
55             if(pre>st.top()){
56                 flag=1;
57                 break;
58             }
59             pre=st.top();
60             st.pop();
61         }
62     }
63     if(flag==1){
64         cout<<-1<<endl;
65     }
66     else{
67         int i=1;
68         int co=1;
69         while(i<=m){
70             if(co!=a[i]){
71                 st.push(a[i]);
72                 i++;
73             }
74             else{
75                 co++;
76                 i++;
77                 while(!st.empty()&&st.top()==co){
78                     co++;
79                     st.pop();
80                 }
81             }
82         }
83         while(!st.empty()){
84             int tmp=st.top();
85             st.pop();
86             for(i=tmp-1;i>=co;i--){
87                 a[++m]=i;
88             }
89             co=tmp+1;
90         }
91         for(int i=n;i>=co;i--) a[++m]=i;
92         for(int i=1;i<=m;i++){
93             cout<<a[i]<<" ";
94         }
95     }
96 }

View Code

F

明天补上

G

明天补上

Educational Codeforces Round 35 (Rated for Div. 2)

原文：https://www.cnblogs.com/Fighting-sh/p/10633378.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)