Codeforces Beta Round #14 (Div. 2)
http://codeforces.com/contest/14
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 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
水题
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
判断四条线段是否可以构成与坐标轴平行或垂直的正方形，感觉数据有点坑
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
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,细节在代码里
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