首页 > 代码库 > Codeforces Round #363 (Div. 2)A-D
Codeforces Round #363 (Div. 2)A-D
699A
题意：在一根数轴上有n个东西以相同的速率1m/s在运动，给出他们的坐标以及运动方向，问最快发生的碰撞在什么时候
思路：遍历一遍坐标，看那两个相邻的可能相撞，更新ans
#include<cstdio>int n,num[200100];char s[200100];int main(){ scanf("%d",&n); scanf("%s",s+1); for(int i=1;i<=n;i++) scanf("%d",&num[i]); int ma=0x3f3f3f3f; for(int i=1;i<n;i++) if(s[i]==‘R‘&&s[i+1]==‘L‘) if(num[i+1]-num[i]<ma) ma=num[i+1]-num[i]; if(ma==0x3f3f3f3f) printf("%d\n",-1); else printf("%d\n",ma/2); return 0;}699B
题意：给出一个由.或者*表示的矩阵，.表示空，*表示墙，现在要用一个炸弹来置于矩阵的某个位置炸掉所有的墙，炸弹的破坏范围是其所置位置的那一行以及那一列，问是不是有可能用一个炸弹就能全部炸掉
思路：首先记录每一行以及每一列的炸弹个数，然后遍历整个矩阵，看这个位置能炸掉的墙是不是等于全部的墙。
#include<cstdio>const int MAXN=1010;int n,m;char s[MAXN][MAXN];int c[MAXN],l[MAXN];int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",s[i]+1); int num=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(s[i][j]==‘*‘) c[i]++,l[j]++,num++; bool flag=false; int x,y; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ int sum=s[i][j]==‘*‘?c[i]+l[j]-1:c[i]+l[j]; if(sum==num) flag=true,x=i,y=j; } if(flag) printf("YES\n%d %d\n",x,y); else printf("NO\n"); return 0;}699C
题意：Vasya有一个n天的假期，假期里面他可以做3件事
1.休息
2.做算法竞赛
3.做运动
但是每一天的情况都会导致他可以做的选择不同，
情况0：他只能休息
情况1：他可以休息也可以做算法竞赛
情况2：他可以休息也可以去运动
情况3；他可以休息，也可以做算法竞赛或者去运动
另外还有一个限制条件：他不喜欢连续两天运动或者连续两天做算法竞赛
问：在以上情况下，他休息天数最少可以是多少天？
思路：这可是非常简单的DP类型啊，滚动DP？没什么好说的，就是注意一下递推的细节，比如不论是哪一天他都是可以选择休息。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn=110;int n;int a[maxn];int dp[maxn][3];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=0;i<=n;i++) for(int j=0;j<=3;j++) dp[i][j]=0x3f3f3f3f; dp[0][0]=0; for(int i=1;i<=n;i++) { dp[i][0]=dp[i-1][0]+1; dp[i][0]=min(dp[i-1][1]+1,dp[i][0]); dp[i][0]=min(dp[i-1][2]+1,dp[i][0]); if(a[i]==1){ dp[i][1]=min(dp[i-1][0],dp[i-1][2]); }else if(a[i]==2){ dp[i][2]=min(dp[i-1][0],dp[i-1][1]); }else if(a[i]==3){ dp[i][1]=min(dp[i-1][0],dp[i-1][2]); dp[i][2]=min(dp[i-1][0],dp[i-1][1]); } } int ans=0x3f3f3f3f; dp[n][1]=min(dp[n][1],dp[n][2]); ans=min(dp[n][0],dp[n][1]); printf("%d\n",ans); return 0;}699D
题意：给出n个点的父节点，如果他的父节点为自己，那可以理解为他是根，问最少要改变几棵树的父节点可以使得他们之间形成一颗树。并且输出改变后每个点的父节点
思路：首先需要通过dfs染色找出图中的连通分量到底有多少个，图中每个连通分量有2种结构，一种是树结构，一种是存在环，如果它是树结构，我们找出它的根节点就可以了，如果它是环，我们找出环上的任意一点。如果存在树结构，那么就其他树或者环并到这颗树的根节点下，如果不存在树结构，那就改变某个环，使它成为树，其他环并到它的父节点下
#include<cstdio>#define N 200005int a[N],v[N],h[N],fa[N],ans,cnt,root;int dfs(int u){ v[u]=cnt;//标记为当前访问 if(!v[a[u]])return a[u]=dfs(a[u])==-1?a[u]:a[a[u]]; if(v[a[u]]==cnt&&a[u]!=u)return a[u]=-1;//存在环，标记为-1说明其父节点需要更改 return a[u]=a[a[u]]==-1?a[u]:a[a[u]];}int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); fa[i]=a[i]; if(a[i]==i)root=i; } cnt=0; for(int i=1;i<=n;i++){ if(!v[i]){ cnt++; dfs(i); if(++h[a[i]]==1) ans++; } } printf("%d\n",ans-(root>0)); for(int i=1;i<=n;i++) if(a[i]==-1||i==a[i]&&i!=root)printf("%d ",root?root:root=i); else printf("%d ",fa[i]); return 0;}
Codeforces Round #363 (Div. 2)A-D