2022.3.8
題單地址:https://codeforces.com/contest/14

目錄

• A. Letter
• B. Young Photographer【差分】
• C. Four Segments【模擬】
• D. Two Paths【直徑】
• E. Camels【未完成 DP】

A. Letter

求一下左上角的下標，和右下角的下標就好了。

#include<bits/stdc++.h> using namespace std; int n,m; string s[10005]; int main(void) {cin>>n>>m;for(int i=0;i<n;i++) cin>>s[i];int x=1e9,y=1e9,xx=0,yy=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(s[i][j]=='*'){x=min(x,i),y=min(y,j);xx=max(xx,i),yy=max(yy,j);}}}for(int i=x;i<=xx;i++){for(int j=y;j<=yy;j++) cout<<s[i][j];cout<<endl;}return 0; }

B. Young Photographer【差分】

找共同覆蓋的部分

#include<bits/stdc++.h> using namespace std; const int N=1e3+10; int a[N],n,m; int main(void) {cin>>n>>m;for(int i=0;i<n;i++){int l,r; cin>>l>>r;if(l>r) swap(l,r);a[l]++,a[r+1]--;}for(int i=1;i<N;i++) a[i]+=a[i-1];int ans=1e9;for(int i=0;i<N;i++){if(a[i]==n) ans=min(ans,abs(i-m));}if(ans==1e9) puts("-1");else cout<<ans;return 0; }

C. Four Segments【模擬】

#include<bits/stdc++.h> using namespace std; struct node{int x,y,xx,yy;}; set<pair<int,int>>st; vector<pair<int,int>>a; map<vector<pair<int,int>>,int>mp; int main(void) {bool flag=1;for(int i=0;i<4;i++){vector< pair<int,int> >temp;int x,y,xx,yy; cin>>x>>y>>xx>>yy;temp.push_back({x,y});temp.push_back({xx,yy});sort(temp.begin(),temp.end());mp[temp]++;if(x!=xx&&y!=yy) flag=0;//不是一條線if(x==xx&&y==yy) flag=0;//是一個點st.insert({x,y});st.insert({xx,yy});}if(st.size()!=4) flag=0;//點的個數if(mp.size()!=4) flag=0;//不同的線段個數for(auto i=st.begin();i!=st.end();i++) a.push_back(*i);sort(a.begin(),a.end());if(a.size()==4){if(a[0].first!=a[1].first) flag=0;if(a[2].first!=a[3].first) flag=0;if(a[0].second!=a[2].second) flag=0;if(a[1].second!=a[3].second) flag=0;}if(flag) puts("YES");else puts("NO");return 0; }

D. Two Paths【直徑】

題目的意思就是，一個樹，將其分成倆連通塊，求倆連通塊的直徑的乘積的最大值。
枚舉每一條邊，求去掉這條邊后的倆連通塊的直徑，求一個max即可。

#include<bits/stdc++.h> using namespace std; const int N=210; int g[N][N],st[N],n; vector<int>ve[N]; int dfs(int u,int& temp)//求直徑 {int d1=0,d2=0;st[u]=1;for(int i=0;i<ve[u].size();i++){int j=ve[u][i];if(!g[u][j]) continue;if(st[j]) continue;int t=dfs(j,temp);if(t>=d1) d2=d1,d1=t;else if(t>d2) d2=t; }temp=max(temp,d1+d2);return d1+1; } int main(void) {cin>>n;for(int i=1;i<=n-1;i++){int a,b; cin>>a>>b;g[a][b]=1,g[b][a]=1;ve[a].push_back(b);ve[b].push_back(a);}int ans=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(g[i][j])//枚舉所有的線段{g[i][j]=0,g[j][i]=0;int temp1=0,temp2=0;memset(st,0,sizeof st);dfs(i,temp1);memset(st,0,sizeof st);dfs(j,temp2);ans=max(ans,temp1*temp2);g[i][j]=1,g[j][i]=1;}}}cout<<ans;return 0; }

E. Camels【未完成 DP】

總結

以上是生活随笔為你收集整理的Codeforces Beta Round #14 (Div. 2)【未完结】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。