Codeforces Beta Round #79 (Div. 2 Only)

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 sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 13000005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<long long,int>pli;
15 typedef pair<char,int> pci;
16 typedef pair<pair<int,string>,pii> ppp;
17 typedef unsigned long long ull;
18 const long long MOD=1e9+7;
19 /*#ifndef ONLINE_JUDGE
20         freopen("1.txt","r",stdin);
21 #endif */
22 
23 int a[105][105];
24 int v[105];
25 
26 int main(){
27     #ifndef ONLINE_JUDGE
28      //   freopen("1.txt","r",stdin);
29     #endif
30     std::ios::sync_with_stdio(false);
31     int n,m;
32     cin>>n>>m;
33     for(int i=1;i<=n;i++) cin>>v[i];
34     int uu,vv;
35     for(int i=1;i<=m;i++){
36         cin>>uu>>vv;
37         a[uu][vv]=a[vv][uu]=1;
38     }
39     int ans=0x3f3f3f3f;
40     for(int i=1;i<=n;i++){
41         for(int j=1;j<=n;j++){
42             for(int k=1;k<=n;k++){
43                 if(i==j||j==k||k==i) continue;
44                 if(a[i][j]==a[j][k]&&a[j][k]==a[k][i]&&a[k][i]==1){
45 
46                     ans=min(ans,v[i]+v[j]+v[k]);
47                 }
48             }
49         }
50     }
51     if(ans==0x3f3f3f3f) cout<<-1;
52     else
53     cout<<ans<<endl;
54 }

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 sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 13000005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<long long,int>pli;
15 typedef pair<char,int> pci;
16 typedef pair<pair<int,string>,pii> ppp;
17 typedef unsigned long long ull;
18 const long long MOD=1e9+7;
19 /*#ifndef ONLINE_JUDGE
20         freopen("1.txt","r",stdin);
21 #endif */
22 
23 
24 int main(){
25     #ifndef ONLINE_JUDGE
26      //   freopen("1.txt","r",stdin);
27     #endif
28     std::ios::sync_with_stdio(false);
29     string str;
30     cin>>str;
31     int ans=0;
32     while(str.length()!=1){
33         int tmp=0;
34         for(int i=0;i<str.length();i++) tmp+=str[i]-'0';
35         ans++;
36         str=to_string(tmp);
37     }
38     cout<<ans<<endl;
39 }

View Code

C

贪心

 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 sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 13000005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<long long,int>pli;
15 typedef pair<int,char> pic;
16 typedef pair<pair<int,string>,pii> ppp;
17 typedef unsigned long long ull;
18 const long long MOD=1e9+7;
19 /*#ifndef ONLINE_JUDGE
20         freopen("1.txt","r",stdin);
21 #endif */
22 
23 int book[35];
24 
25 int main(){
26     #ifndef ONLINE_JUDGE
27      //   freopen("1.txt","r",stdin);
28     #endif
29     std::ios::sync_with_stdio(false);
30     string str;
31     int n;
32     cin>>str>>n;
33     for(int i=0;i<str.length();i++){
34         book[str[i]-'a']++;
35     }
36     if(str.length()<=n) cout<<0<<endl<<endl;
37     else{
38         set<char>se;
39         vector<pic>ve;
40         for(int i=0;i<26;i++){
41             ve.pb({book[i],'a'+i});
42         }
43         sort(ve.begin(),ve.end());
44         for(int i=0;i<ve.size();i++){
45             if(ve[i].first<=n){
46                 n-=ve[i].first;
47                 se.insert(ve[i].second);
48             }
49             else{
50                 break;
51             }
52         }
53         string s="";
54         for(int i=0;i<str.length();i++){
55             if(se.count(str[i])) continue;
56             else s+=str[i];
57         }
58         set<char>ss;
59         for(int i=0;i<s.length();i++){
60             ss.insert(s[i]);
61         }
62         cout<<ss.size()<<endl<<s<<endl;
63     }
64 }

View Code

D

树状数组+离散化

 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 sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 13000005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<long long,int>pli;
15 typedef pair<int,char> pic;
16 typedef pair<pair<int,string>,pii> ppp;
17 typedef unsigned long long ull;
18 const long long MOD=1e9+7;
19 /*#ifndef ONLINE_JUDGE
20         freopen("1.txt","r",stdin);
21 #endif */
22 
23 int n,m;
24 
25 map<int,int>tree;
26 
27 int lowbit(int x){
28     return x&(-x);
29 }
30 
31 void add(int x,int v){
32     while(x<=n+1){
33         tree[x]=(tree[x]+v)%MOD;
34         x+=lowbit(x);
35     }
36 }
37 
38 int getsum(int x){
39     int ans=0;
40     while(x){
41         ans=(ans+tree[x])%MOD;
42         x-=lowbit(x);
43     }
44     return ans;
45 }
46 vector<pii>ve;
47 
48 int main(){
49     #ifndef ONLINE_JUDGE
50      //   freopen("1.txt","r",stdin);
51     #endif
52     std::ios::sync_with_stdio(false);
53     cin>>n>>m;
54     int a,b;
55     for(int i=1;i<=m;i++){
56         cin>>a>>b;
57         ve.pb({b+1,a+1});
58     }
59     sort(ve.begin(),ve.end());
60     add(1,1);
61     for(int i=0;i<m;i++){
62         int s=ve[i].second,t=ve[i].first;
63         int tmp=getsum(t-1)-getsum(s-1);
64         tmp=(tmp%MOD+MOD)%MOD;
65         add(t,tmp);
66     }
67     int ans=getsum(n+1)-getsum(n);
68     cout<<(ans%MOD+MOD)%MOD<<endl;
69 }

View Code