Codeforces Beta Round #14 (Div. 2)

Codeforces Beta Round #14 (Div. 2)

http://codeforces.com/contest/14

A

 找最大最小的行列值即可

Codeforces Beta Round #14 (Div. 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 sqr(x) ((x)*(x))
 6 #define maxn 500005
 7 typedef long long ll;
 8 /*#ifndef ONLINE_JUDGE
 9         freopen("1.txt","r",stdin);
10 #endif */
11 
12 string str[55];
13 
14 int main(){
15     #ifndef ONLINE_JUDGE
16         freopen("1.txt","r",stdin);
17     #endif
18     std::ios::sync_with_stdio(false);
19     int n,m;
20     cin>>n>>m;
21     int hangmin=105,hangmax=-1,liemin=105,liemax=-1;
22     for(int i=0;i<n;i++) cin>>str[i];
23     for(int i=0;i<n;i++){
24         for(int j=0;j<m;j++){
25             if(str[i][j]=='*'){
26                 hangmin=min(hangmin,i);
27             }
28         }
29     }
30     for(int i=0;i<n;i++){
31         for(int j=0;j<m;j++){
32             if(str[i][j]=='*'){
33                 hangmax=max(hangmax,i);
34             }
35         }
36     }
37     for(int i=0;i<n;i++){
38         for(int j=0;j<m;j++){
39             if(str[i][j]=='*'){
40                 liemin=min(liemin,j);
41             }
42         }
43     }
44     for(int i=0;i<n;i++){
45         for(int j=0;j<m;j++){
46             if(str[i][j]=='*'){
47                 liemax=max(liemax,j);
48             }
49         }
50     }
51    // cout<<hangmin<<" "<<hangmax<<" "<<liemin<<" "<<liemax<<endl;
52     for(int i=hangmin;i<=hangmax;i++){
53         for(int j=liemin;j<=liemax;j++){
54             cout<<str[i][j];
55         }
56         cout<<endl;
57     }
58 }
View Code

 

B

水题

Codeforces Beta Round #14 (Div. 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 sqr(x) ((x)*(x))
 6 #define maxn 500005
 7 typedef long long ll;
 8 /*#ifndef ONLINE_JUDGE
 9         freopen("1.txt","r",stdin);
10 #endif */
11 
12 int n,x;
13 int a[1005];
14 
15 int main(){
16     #ifndef ONLINE_JUDGE
17       //  freopen("1.txt","r",stdin);
18     #endif
19     std::ios::sync_with_stdio(false);
20     cin>>n>>x;
21     int u,v;
22     for(int i=1;i<=n;i++){
23         cin>>u>>v;
24         if(u>v) swap(u,v);
25         a[u]++,a[v+1]--;
26     }
27     int ans=0x3f3f3f3f;
28     int num=0;
29     for(int i=0;i<=1001;i++){
30         num+=a[i];
31         if(num==n){
32             ans=min(ans,abs(i-x));
33         }
34     }
35     if(ans==0x3f3f3f3f) cout<<-1<<endl;
36     else cout<<ans<<endl;
37 }
View Code

 

C

判断四条线段是否可以构成与坐标轴平行或垂直的正方形,感觉数据有点坑

Codeforces Beta Round #14 (Div. 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 sqr(x) ((x)*(x))
 6 #define maxn 500005
 7 typedef long long ll;
 8 /*#ifndef ONLINE_JUDGE
 9         freopen("1.txt","r",stdin);
10 #endif */
11 
12 map<pair<int,int>,int>mp;
13 map<pair<int,int>,int>::iterator it;
14 map< pair< pair<int,int>,pair<int,int> >,int >book;
15 
16 int main(){
17     #ifndef ONLINE_JUDGE
18         freopen("1.txt","r",stdin);
19     #endif
20     std::ios::sync_with_stdio(false);
21     int a,b,c,d;
22     int flag=0;
23     for(int i=0;i<4;i++){
24         cin>>a>>b>>c>>d;
25         mp[make_pair(a,b)]++;
26         mp[make_pair(c,d)]++;
27         if(a==c&&b==d) flag=1;
28         vector<pair<int,int> >v;
29         v.push_back(make_pair(a,b));
30         v.push_back(make_pair(c,d));
31         sort(v.begin(),v.end());
32         if(book[make_pair(v[0],v[1])]==0){
33             book[make_pair(v[0],v[1])]=1;
34         }
35         else{
36             flag=1;
37         }
38     //    cout<<v[0].first<<" "<<v[0].second<<" "<<v[1].first<<" "<<v[1].second<<endl;
39     }
40     for(it=mp.begin();it!=mp.end();it++){
41         if(it->second!=2){
42             flag=1;
43         }
44     }
45     if(flag){
46         cout<<"NO"<<endl;
47     }
48     else{
49         vector<pair<int,int> >ve;
50         for(it=mp.begin();it!=mp.end();it++){
51             ve.push_back(it->first);
52         }
53         sort(ve.begin(),ve.end());
54         if(ve[0].first==ve[1].first&&ve[2].first==ve[3].first&&
55            ve[0].second==ve[2].second&&ve[1].second==ve[3].second){
56             cout<<"YES"<<endl;
57            }
58         else cout<<"NO"<<endl;
59     }
60 }
61 
62 /*
63 0 0 0 2
64 2 0 2 2
65 0 2 0 0
66 2 2 2 0
67 */
View Code

 

D

枚举删边,然后跑dfs

Codeforces Beta Round #14 (Div. 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 sqr(x) ((x)*(x))
 6 #define maxn 500005
 7 typedef long long ll;
 8 /*#ifndef ONLINE_JUDGE
 9         freopen("1.txt","r",stdin);
10 #endif */
11 
12 int n;
13 vector<int>ve[205];
14 vector<pair<int,int> >d;
15 
16 int r;
17 
18 int dfs(int pos,int pre){
19     int len1=0,len2=0;
20     int tmp=0;
21     for(int i=0;i<ve[pos].size();i++){
22         if(ve[pos][i]!=pre){
23             tmp=max(tmp,dfs(ve[pos][i],pos));
24             if(r>len1){len2=len1,len1=r;}
25             else{len2=max(len2,r);}
26         }
27     }
28     tmp=max(tmp,len1+len2);
29     r=len1+1;
30     return tmp;
31 }
32 
33 int main(){
34     #ifndef ONLINE_JUDGE
35         freopen("1.txt","r",stdin);
36     #endif
37     cin>>n;
38     int a,b;
39     for(int i=1;i<n;i++){
40         cin>>a>>b;
41         ve[a].push_back(b);
42         ve[b].push_back(a);
43         d.push_back(make_pair(a,b));
44     }
45     int ans=0;
46     for(int i=0;i<d.size();i++){
47         int t1=dfs(d[i].first,d[i].second);
48         int t2=dfs(d[i].second,d[i].first);
49       //  cout<<t1<<" "<<t2<<" "<<d[i].first<<" "<<d[i].second<<endl;
50         ans=max(ans,t1*t2);
51     }
52     cout<<ans<<endl;
53 
54 
55 }
View Code

 

E

DP,细节在代码里

Codeforces Beta Round #14 (Div. 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 sqr(x) ((x)*(x))
 6 #define maxn 500005
 7 typedef long long ll;
 8 /*#ifndef ONLINE_JUDGE
 9         freopen("1.txt","r",stdin);
10 #endif */
11 
12 ll dp[25][15][5][2];///分别表示第i个数,第j个尖峰数,尖峰高度和上升(1)或下降(0)
13 
14 int main(){
15     #ifndef ONLINE_JUDGE
16        // freopen("1.txt","r",stdin);
17     #endif
18     int n,m;
19     for(int i=1;i<5;i++) dp[1][1][i][1]=1;
20     for(int i=2;i<=20;i++){
21         for(int j=1;j<=10;j++){
22             for(int k=1;k<=4;k++){
23                 for(int l=1;l<k;l++){///更新上升的尖峰: 1:下降峰加个上升   2:上升再加一个上升
24                     dp[i][j][k][1]+=dp[i-1][j-1][l][0]+dp[i-1][j][l][1];
25                 }
26                 if(i==2){///2步不可能的情况
27                     dp[i][j][k][0]=0;
28                 }
29                 else{
30                     for(int l=k+1;l<=4;l++){
31                         ///更新下降的尖峰(1:下降峰再加一个下降,2:上升峰加一个下降)
32                         dp[i][j][k][0]+=dp[i-1][j][l][0]+dp[i-1][j][l][1];
33                     }
34                 }
35             }
36         }
37     }
38     cin>>n>>m;
39     ll ans=0;
40     for(int i=1;i<=4;i++){
41         ans+=dp[n][m][i][0];
42     }
43     cout<<ans<<endl;
44 }
View Code

 

上一篇:十种排序代码


下一篇:牛客网——打印路径