Codeforces Beta Round #14 (Div. 2)
http://codeforces.com/contest/14
A
找最大最小的行列值即可
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define maxn 500005
typedef long long ll;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ string str[]; int main(){
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
int hangmin=,hangmax=-,liemin=,liemax=-;
for(int i=;i<n;i++) cin>>str[i];
for(int i=;i<n;i++){
for(int j=;j<m;j++){
if(str[i][j]=='*'){
hangmin=min(hangmin,i);
}
}
}
for(int i=;i<n;i++){
for(int j=;j<m;j++){
if(str[i][j]=='*'){
hangmax=max(hangmax,i);
}
}
}
for(int i=;i<n;i++){
for(int j=;j<m;j++){
if(str[i][j]=='*'){
liemin=min(liemin,j);
}
}
}
for(int i=;i<n;i++){
for(int j=;j<m;j++){
if(str[i][j]=='*'){
liemax=max(liemax,j);
}
}
}
// cout<<hangmin<<" "<<hangmax<<" "<<liemin<<" "<<liemax<<endl;
for(int i=hangmin;i<=hangmax;i++){
for(int j=liemin;j<=liemax;j++){
cout<<str[i][j];
}
cout<<endl;
}
}
B
水题
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define maxn 500005
typedef long long ll;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ int n,x;
int a[]; int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n>>x;
int u,v;
for(int i=;i<=n;i++){
cin>>u>>v;
if(u>v) swap(u,v);
a[u]++,a[v+]--;
}
int ans=0x3f3f3f3f;
int num=;
for(int i=;i<=;i++){
num+=a[i];
if(num==n){
ans=min(ans,abs(i-x));
}
}
if(ans==0x3f3f3f3f) cout<<-<<endl;
else cout<<ans<<endl;
}
C
判断四条线段是否可以构成与坐标轴平行或垂直的正方形，感觉数据有点坑
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define maxn 500005
typedef long long ll;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ map<pair<int,int>,int>mp;
map<pair<int,int>,int>::iterator it;
map< pair< pair<int,int>,pair<int,int> >,int >book; int main(){
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
int a,b,c,d;
int flag=;
for(int i=;i<;i++){
cin>>a>>b>>c>>d;
mp[make_pair(a,b)]++;
mp[make_pair(c,d)]++;
if(a==c&&b==d) flag=;
vector<pair<int,int> >v;
v.push_back(make_pair(a,b));
v.push_back(make_pair(c,d));
sort(v.begin(),v.end());
if(book[make_pair(v[],v[])]==){
book[make_pair(v[],v[])]=;
}
else{
flag=;
}
// cout<<v[0].first<<" "<<v[0].second<<" "<<v[1].first<<" "<<v[1].second<<endl;
}
for(it=mp.begin();it!=mp.end();it++){
if(it->second!=){
flag=;
}
}
if(flag){
cout<<"NO"<<endl;
}
else{
vector<pair<int,int> >ve;
for(it=mp.begin();it!=mp.end();it++){
ve.push_back(it->first);
}
sort(ve.begin(),ve.end());
if(ve[].first==ve[].first&&ve[].first==ve[].first&&
ve[].second==ve[].second&&ve[].second==ve[].second){
cout<<"YES"<<endl;
}
else cout<<"NO"<<endl;
}
} /*
0 0 0 2
2 0 2 2
0 2 0 0
2 2 2 0
*/
D
枚举删边，然后跑dfs
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define maxn 500005
typedef long long ll;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ int n;
vector<int>ve[];
vector<pair<int,int> >d; int r; int dfs(int pos,int pre){
int len1=,len2=;
int tmp=;
for(int i=;i<ve[pos].size();i++){
if(ve[pos][i]!=pre){
tmp=max(tmp,dfs(ve[pos][i],pos));
if(r>len1){len2=len1,len1=r;}
else{len2=max(len2,r);}
}
}
tmp=max(tmp,len1+len2);
r=len1+;
return tmp;
} int main(){
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif
cin>>n;
int a,b;
for(int i=;i<n;i++){
cin>>a>>b;
ve[a].push_back(b);
ve[b].push_back(a);
d.push_back(make_pair(a,b));
}
int ans=;
for(int i=;i<d.size();i++){
int t1=dfs(d[i].first,d[i].second);
int t2=dfs(d[i].second,d[i].first);
// cout<<t1<<" "<<t2<<" "<<d[i].first<<" "<<d[i].second<<endl;
ans=max(ans,t1*t2);
}
cout<<ans<<endl; }
E
DP,细节在代码里
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define maxn 500005
typedef long long ll;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ ll dp[][][][];///分别表示第i个数，第j个尖峰数，尖峰高度和上升（1）或下降（0） int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
int n,m;
for(int i=;i<;i++) dp[][][i][]=;
for(int i=;i<=;i++){
for(int j=;j<=;j++){
for(int k=;k<=;k++){
for(int l=;l<k;l++){///更新上升的尖峰: 1：下降峰加个上升 2：上升再加一个上升
dp[i][j][k][]+=dp[i-][j-][l][]+dp[i-][j][l][];
}
if(i==){///2步不可能的情况
dp[i][j][k][]=;
}
else{
for(int l=k+;l<=;l++){
///更新下降的尖峰(1:下降峰再加一个下降,2:上升峰加一个下降)
dp[i][j][k][]+=dp[i-][j][l][]+dp[i-][j][l][];
}
}
}
}
}
cin>>n>>m;
ll ans=;
for(int i=;i<=;i++){
ans+=dp[n][m][i][];
}
cout<<ans<<endl;
}