A題：

題意：給定一些數(shù)，給定一些往左走和往右走的操作，問(wèn)是否能夠相遇，如果相遇請(qǐng)求出相遇時(shí)間

分析：對(duì)于相鄰兩個(gè)數(shù)，如果大的往左，小的往右就能夠相遇，否則不能相遇，在求出所有相遇當(dāng)中的第一次相遇即可

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 const int maxn=200050; 15 const int INF=1<<30; 16 int a[maxn]; 17 int n; 18 int main() 19 { 20 while(cin>>n) 21 { 22 string s; 23 cin>>s; 24 for(int i=0;i<n;i++) 25 cin>>a[i]; 26 int flag=0; 27 int k; 28 int minx=INF; 29 for(int i=0;i<n-1;i++) 30 { 31 int flag1=0; 32 if(s[i]=='R'&&s[i+1]=='L'&&a[i]<a[i+1]) 33 { 34 flag=1; flag1=1; 35 } 36 else if(s[i]=='L'&&s[i+1]=='R'&&a[i]>a[i+1]){ 37 flag=1; flag1=1; 38 } 39 if(flag1){ 40 int maxt=max(a[i],a[i+1]); 41 int mint=min(a[i],a[i+1]); 42 int t=(maxt-mint)/2; 43 if(t<minx) 44 minx=t; 45 } 46 } 47 if(flag) { 48 cout<<minx<<endl; 49 }else 50 { 51 cout<<"-1"<<endl; 52 } 53 } 54 return 0; 55 } View Code

B題：

題意：＊代表墻，.代表空地，一個(gè)炸彈能夠炸掉橫豎各一列的墻，問(wèn)能否通過(guò)一枚炸彈，讓所有全部變成平地

分析：這是一道Hack點(diǎn)極多的題，我就因?yàn)檫@題被Hack了，Ranting一朝回到解放前。直接模擬即可，但是要注意兩種情況，一個(gè)是沒(méi)有一個(gè)格子是墻壁的情況，還有一種選擇放置炸彈的點(diǎn)不是墻壁的情況

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 const int maxn=1100; 15 int n,m; 16 int vis[maxn],d[maxn]; 17 int main() 18 { 19 while(cin>>n>>m) 20 { 21 char s[maxn][maxn]; 22 for(int i=0;i<n;i++) 23 cin>>s[i]; 24 int flag1=0; 25 for(int i=0;i<n;i++){ 26 for(int j=0;j<m;j++){ 27 if(s[i][j]=='*'){ 28 flag1=1; break; 29 } 30 } 31 } 32 if(!flag1){ 33 cout<<"YES"<<endl; 34 cout<<"1"<<" "<<"1"<<endl; 35 continue; 36 } 37 memset(vis,0,sizeof(vis)); 38 memset(d,0,sizeof(d)); 39 int flag=0; 40 int cnt=0; 41 for(int i=0;i<n;i++) 42 { 43 for(int j=0;j<m;j++){ 44 if(s[i][j]=='*'){ 45 vis[i]++; 46 d[j]++; 47 cnt++; 48 } 49 } 50 } 51 int h,k; 52 for(int i=0;i<n;i++){ 53 for(int j=0;j<m;j++){ 54 if(s[i][j]=='*'){ 55 if(vis[i]+d[j]==cnt+1){ 56 h=i; k=j; flag=1; break; 57 } 58 }else if(s[i][j]=='.'){ 59 if(vis[i]+d[j]==cnt){ 60 h=i;k=j; flag=1; break; 61 } 62 } 63 } 64 if(flag) break; 65 } 66 if(flag){ 67 cout<<"YES"<<endl; 68 cout<<h+1<<" "<<k+1<<endl; 69 }else{ 70 cout<<"NO"<<endl; 71 } 72 } 73 return 0; 74 } View Code

?C題：

題意：0代表休息，1代表學(xué)習(xí)，2代表運(yùn)動(dòng)，3既可以代表學(xué)習(xí)又可以代表運(yùn)動(dòng)，相鄰兩天之間做的活不能一樣，問(wèn)最少休息幾天

分析：賽場(chǎng)上沒(méi)有做出來(lái)的dp，寫錯(cuò)一個(gè)地方。dp[i][j]代表前i天，當(dāng)?shù)趇天為j時(shí)的最多活動(dòng)天數(shù)，當(dāng)?shù)趇天為0時(shí)，必須休息，所以dp[i][0]就為前i－1天的最大值，當(dāng)?shù)趇天為1或者3時(shí)，我們考慮若是工作的話，那必須從距離他最近的一個(gè)2或者0再＋1，同理i為2的話也是距離他最近的一個(gè)1或者0再加1，最后減去最大工作天數(shù)即可。非常非常好的一個(gè)題目，值得回味

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 const int maxn=110; 15 int dp[maxn][5]; 16 int a[maxn]; 17 int n; 18 int main() 19 { 20 while(cin>>n) 21 { 22 for(int i=1;i<=n;i++) 23 cin>>a[i]; 24 memset(dp,0,sizeof(dp)); 25 int mx=0; 26 for(int i=1;i<=n;i++){ 27 dp[i][0]=max(dp[i-1][0],max(dp[i-1][1],max(dp[i-1][2],dp[i-1][3]))); 28 if(a[i]==1||a[i]==3) 29 dp[i][1]=max(dp[i-1][0],dp[i-1][2])+1; 30 if(a[i]==2||a[i]==3) 31 dp[i][2]=max(dp[i-1][0],dp[i-1][1])+1; 32 int cnt=max(dp[i][0],max(dp[i][1],dp[i][2])); 33 mx=max(mx,cnt); 34 } 35 cout<<n-mx<<endl; 36 } 37 return 0; 38 } View Code

?D題：

題意：給出每個(gè)結(jié)點(diǎn)父結(jié)點(diǎn)的編號(hào)，求最小修改多少個(gè)數(shù)可以使其成為一課完整的樹

分析：非常好的一個(gè)題目，我們來(lái)考慮何時(shí)是一棵樹。當(dāng)有環(huán)時(shí)必然不能構(gòu)成一棵樹，當(dāng)有孤點(diǎn)時(shí)必然不能構(gòu)成一棵樹。那我們要做的就是破環(huán)，這個(gè)地方就用到了并查集，對(duì)于有環(huán)存在的兩個(gè)結(jié)點(diǎn)，他們通過(guò)并查集查詢出來(lái)的根結(jié)點(diǎn)必定相同，但此時(shí)有一個(gè)結(jié)點(diǎn)還未并入集合，因此只可能是存在環(huán)，這一點(diǎn)很重要，基于此，我們對(duì)每個(gè)環(huán)進(jìn)行破環(huán)，孤點(diǎn)也可以看做一個(gè)自環(huán)。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 const int maxn=200020; 15 int par[maxn],rankl[maxn],a[maxn]; 16 void init(int n) 17 { 18 for(int i=0;i<=n;i++){ 19 par[i]=i; 20 rankl[i]=0; 21 } 22 } 23 int findl(int x) 24 { 25 if(x==par[x]) 26 return x; 27 else 28 return par[x]=findl(par[x]); 29 } 30 void unite(int x,int y) 31 { 32 x=findl(x); 33 y=findl(y); 34 if(x==y) return; 35 if(rankl[x]<rankl[y]) 36 { 37 par[x]=y; 38 }else{ 39 par[y]=x; 40 if(rankl[x]==rankl[y]) rankl[x]++; 41 } 42 } 43 bool same(int x,int y) 44 { 45 return findl(x)==findl(y); 46 } 47 int n; 48 int main() 49 { 50 while(cin>>n) 51 { 52 int root=-1; 53 int cnt=0; 54 init(n); 55 for(int i=1;i<=n;i++) 56 { 57 scanf("%d",&a[i]); 58 if(i==a[i]) root=i; 59 } 60 for(int i=1;i<=n;i++) 61 { 62 int fx=findl(i); 63 int fy=findl(a[i]); 64 if(fx==fy&&i!=root) 65 { 66 if(root==-1) 67 root=i; 68 a[i]=root; 69 cnt++; 70 } 71 unite(fx,fy); 72 } 73 printf("%d\n",cnt); 74 for(int i=1;i<n;i++) 75 printf("%d ",a[i]); 76 printf("%d\n",a[n]); 77 } 78 return 0; 79 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/wolf940509/p/5690562.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces#363 Div2的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。