Educational Codeforces Round 32【A,B,C】

A。

水题

 1 #include<bits/stdc++.h>
 2  
 3 using namespace std;
 4 #define int long long 
 5 int arr[25000];
 6 signed main(){
 7     int n;
 8     cin>>n;
 9     for(int i=1;i<=n;i++){
10          cin>>arr[i];
11     }
12     int ans=0;
13     for(int i=2;i<n;i++){
14         if(arr[i]>max(arr[i-1],arr[i+1])){
15             ans++;
16         }else if(arr[i]<min(arr[i-1],arr[i+1])){
17             ans++;
18         }
19     }
20     cout<<ans;
21     return 0;
22 }

B题

思维

 1 #include<bits/stdc++.h>
 2  
 3 using namespace std;
 4 #define int long long 
 5 int arr[25000];
 6 signed main(){
 7     int n;cin>>n;
 8     string s;
 9     cin>>s;int l=0,d=0,u=0,r=0;
10     for(int i=0;i<s.size();i++){
11         if(s[i]=='L'){
12             l++;
13         }else if(s[i]=='R'){
14             r++;
15         }else if(s[i]=='D'){
16             d++;
17         }else{
18             u++;
19         }
20     }
21     cout<<max(min(min(l,r),min(d,u))*4,2*min(l,r)+2*min(d,u));
22     return 0;
23 }

C题思维

题意：

題意：字符串任意k長度子串都要包含某個字母，問長度k最小為多少。

題解：先預處理把相同字母之間的長度都存到一個數組裏（這裏註意最前面和最後面的處理），都要包含某個字母，那麽我們肯定要取數組裏面的最大值，然後把最大值比較一下，取下最小值就OK啦。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 2000000
 4 #define inf 1<<30 
 5 vector<int> v[N];
 6 signed main(){
 7     int sum=inf;
 8  
 9     string str;cin>>str;
10     int len=str.size();
11     for(int i=0;i<26;i++){
12         v[i].push_back(0);
13     } 
14     for(int i=0;i<str.size();i++){
15         v[str[i]-'a'].push_back(i+1);
16     }
17     for(int i=0;i<26;i++){
18         v[i].push_back(str.size()+1);
19     }
20     for(int i=0;i<26;i++){
21         int t=0;
22         for(int j=1;j<v[i].size();j++){
23             t=max(t,v[i][j]-v[i][j-1]);
24         }    
25         if(!t) continue;
26         sum=min(t,sum);
27     }
28     cout<<sum;
29     return 0;
30 }