Codeforces Beta Round #69 (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 1000006
 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 unsigned long long ull;
14 
15 
16 int main(){
17     #ifndef ONLINE_JUDGE
18      //   freopen("input.txt","r",stdin);
19     #endif
20     std::ios::sync_with_stdio(false);
21     int n,m;
22     cin>>n>>m;
23     for(int i=n+1;;i++){
24         int flag=1;
25         int j;
26         for(j=2;j<i;j++){
27             if(i%j==0){
28                 break;
29             }
30         }
31         if(j==i) {
32             if(i==m) cout<<"YES"<<endl;
33             else {
34                 cout<<"NO"<<endl;
35             }
36             break;
37         }
38     }
39 }

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 1000006
 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 unsigned long long ull;
14 
15 
16 int main(){
17     #ifndef ONLINE_JUDGE
18      //   freopen("input.txt","r",stdin);
19     #endif
20     std::ios::sync_with_stdio(false);
21     double n,m;
22     char ch;
23     cin>>n>>ch>>m;
24     if(n>=12) n-=12;
25     double ans1,ans2;
26     ans2=6*m;
27     ans1=n*30+0.5*m;
28     cout<<ans1<<" "<<ans2<<endl;
29 }

View Code

C

因为有三个敌人，所以用三进制的方法枚举所有的情况。时间复杂度为O（3^7*7*7）

 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 1000006
 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 unsigned long long ull;
14 
15 map<string,ll>mp;
16 string s[]={"Anka","Chapay","Cleo","Troll","Dracul","Snowy","Hexadecimal"};
17 ll relation[15][15];
18 
19 int book[15];
20 
21 int main(){
22     #ifndef ONLINE_JUDGE
23      //   freopen("input.txt","r",stdin);
24     #endif
25     std::ios::sync_with_stdio(false);
26     int n;
27     string s1,s2,s3;
28     for(int i=0;i<7;i++){
29         mp[s[i]]=i+1;
30     }
31     cin>>n;
32     for(int i=1;i<=n;i++){
33         cin>>s1>>s2>>s3;
34         relation[mp[s1]][mp[s3]]++;
35     }
36     ll a,b,c;
37     cin>>a>>b>>c;
38     int m=3*3*3*3*3*3*3;
39     set<int>se;
40     ll ans1=0x3f3f3f3f;
41     int ans2=0;
42     for(int i=1;i<=m;i++){
43         int j=i;
44         se.clear();
45         int co=1;
46         memset(book,0,sizeof(book));
47         while(j){
48             book[co]=j%3;
49             se.insert(book[co]);
50             co++;
51             j/=3;
52         }
53         if(se.size()==3){
54             int aa=0,bb=0,cc=0;
55             for(j=1;j<=7;j++){
56                 if(book[j]==0) aa++;
57                 else if(book[j]==1) bb++;
58                 else if(book[j]==2) cc++;
59             }
60             ll aaa=a/aa;
61             ll bbb=b/bb;
62             ll ccc=c/cc;
63             if(aaa>bbb) swap(aaa,bbb);
64             if(aaa>ccc) swap(aaa,ccc);
65             if(bbb>ccc) swap(bbb,ccc);
66             if(ccc-aaa<ans1){
67                 ans1=ccc-aaa;
68                 ans2=0;
69                 for(int q=1;q<=7;q++){
70                     for(int w=1;w<=7;w++){
71                         if(relation[q][w]&&book[q]==book[w]){
72                             ans2++;
73                         }
74                     }
75                 }
76             }
77             else if(ccc-aaa==ans1){
78                 int tmp=0;
79                 for(int q=1;q<=7;q++){
80                     for(int w=1;w<=7;w++){
81                         if(relation[q][w]&&book[q]==book[w]){
82                             tmp++;
83                         }
84                     }
85                 }
86                 ans2=max(ans2,tmp);
87             }
88         }
89     }
90     cout<<ans1<<" "<<ans2<<endl;
91 }

View Code

D

要让delta>=0的情况为p-4q>=0。因此可以画出几何图形

以样例一为例子：红色部分就是需要求的概率

 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 1000006
 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 unsigned long long ull;
14 
15 
16 int main(){
17     #ifndef ONLINE_JUDGE
18      //   freopen("input.txt","r",stdin);
19     #endif
20    // std::ios::sync_with_stdio(false);
21     int t;
22     scanf("%d",&t);
23     while(t--){
24         int a,b;
25         scanf("%d %d",&a,&b);
26         if(a==0&&b==0) printf("%.7f
",1*1.0);
27         else if(a==0&&b!=0){
28             printf("%.7f
",0.5);
29         }
30         else if(a!=0&&b==0){
31             printf("%.7f
",1*1.0);
32         }
33         else if(a>=4*b){
34             printf("%.7f
",(a-b)*1.0/a);
35         }
36         else{
37             printf("%.7f
",(a/4.0+2*b)*1.0/(4*b));
38         }
39     }
40 }

View Code

E

先做dfs，dfs的过程中对儿子可获得的最大果子进行排序，优先获取最大的果子，如果遍历完儿子之后自身的果子还有剩，就再对儿子进行一次遍历，这次遍历的目的是消耗儿子自身和自己的果实数量

 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 1000006
 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 unsigned long long ull;
14 
15 vector<int>ve[100005];
16 int a[100005];
17 int n;
18 
19 void dfs(int now,int pre,ll &Max,int &remain){
20     vector<ll>ve_Max;
21     vector<int>ve_remain;
22     for(int i=0;i<ve[now].size();i++){
23         if(ve[now][i]!=pre&&a[ve[now][i]]>0){
24             ll tmp_Max;
25             int tmp_remain=a[ve[now][i]]-1;
26             dfs(ve[now][i],now,tmp_Max,tmp_remain);
27             ve_Max.pb(tmp_Max);
28             ve_remain.pb(tmp_remain);
29         }
30     }
31     sort(ve_Max.begin(),ve_Max.end());
32     Max=0;
33     for(int i=ve_Max.size()-1;i>=0&&remain;i--){
34         Max+=ve_Max[i]+2;
35         remain--;
36     }
37     for(int i=0;i<ve_remain.size()&&remain;i++){
38         Max+=min(remain,ve_remain[i])*2;
39         remain-=min(remain,ve_remain[i]);
40     }
41 }
42 
43 
44 int main(){
45     #ifndef ONLINE_JUDGE
46      //   freopen("input.txt","r",stdin);
47     #endif
48     std::ios::sync_with_stdio(false);
49     cin>>n;
50     for(int i=1;i<=n;i++) cin>>a[i];
51     int u,v;
52     for(int i=1;i<n;i++){
53         cin>>u>>v;
54         ve[u].pb(v);
55         ve[v].pb(u);
56     }
57     int fa;
58     cin>>fa;
59     ll ans=0;
60     dfs(fa,0,ans,a[fa]);
61     cout<<ans<<endl;
62 }

View Code