Problem A Launch of Collider
题目大意
在x轴上有n个点，坐标均为偶数。每个点或向左移动或向右移动，每秒移动距离为1。
使所有点同时开始移动，求最早有点相遇的时间或无解。
解题分析
对于每一个向右移动的点，找右边最近的一个向左的点。向左移动同理。
正反扫两遍即可。
参考程序
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std; #define N 200008
#define V 1008
#define E 60008
#define lson l,m,rt<<1
#define rson m,r+1,rt<<1|1
#define clr(x,v) memset(x,v,sizeof(x));
#define LL long long
//#define debug
const int mo = ;
const int inf = 0x3f3f3f3f;
const int INF = ;
/**************************************************************************/
int n;
char s[N];
int a[N],ans[N];
int main(){
scanf("%d",&n);
scanf("%s",s+);
for (int i=;i<=n;i++) scanf("%d",&a[i]);
int x=-;
for (int i=;i<=n;i++)
if (s[i]=='R') x=a[i];
else
{
if (x==-) ans[i]=INF;
else ans[i]=(a[i]-x)/;
}
x=-;
for (int i=n;i>=;i--)
if (s[i]=='L') x=a[i];
else
{
if (x==-) ans[i]=INF;
else ans[i]=(x-a[i])/;
}
int res=INF;
for (int i=;i<=n;i++) res=min(res,ans[i]);
printf("%d\n",res==INF ? - : res); #ifdef debug
system("pause");
#endif
}
Problem B One Bomb
题目大意
有一个n*m的矩形，每一个格子为空地或者为墙壁。 （n,m<=1000）
现在要某点放置一颗炸弹，炸掉所有的墙壁。炸弹的爆炸范围为该点的上下左右两条直线。
给出一种方案或无解。
解题分析
记录一下每行的墙壁数，每列的墙壁数。
枚举每个点是否放置炸弹即可。
参考程序
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std; #define N 1000008
#define V 1008
#define E 60008
#define lson l,m,rt<<1
#define rson m,r+1,rt<<1|1
#define clr(x,v) memset(x,v,sizeof(x));
#define LL long long
//#define debug
const int mo = ;
const int inf = 0x3f3f3f3f;
const int INF = ;
/**************************************************************************/ int n,m,num;
int x[V],y[V],mp[V][V];
int main(){
scanf("%d%d",&n,&m);
num=;
for (int i=;i<=n;i++){
char s[V];
scanf("%s",s+);
for (int j=;j<=m;j++)
if (s[j]=='*'){
x[i]++;
y[j]++;
mp[i][j]=;
num++;
}
}
int ok=;
int tx,ty;
for (tx=;tx<=n;tx++){
for (ty=;ty<=m;ty++){
int now;
if (mp[tx][ty]) now=x[tx]+y[ty]-; else now=x[tx]+y[ty];
if (now==num){
ok=;
break;
}
}
if (ok) break;
}
if (ok) printf("YES\n%d %d\n",tx,ty); else printf("NO\n"); #ifdef debug
system("pause");
#endif
}
Problem C Vacations
题目大意
一个小朋友每天可以选择休息或者网上打比赛或者去体育馆玩，但不能两天都刷题或者都玩耍。
给定每天是否网上有比赛，体育馆是否开。
问小朋友n天内最少需要休息几天。
解题分析
dp[i][0~2] 表示第i天干某事的最少休息天数。
分情况讨论转移。
参考程序
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std; #define N 100008
#define V 1008
#define E 60008
#define lson l,m,rt<<1
#define rson m,r+1,rt<<1|1
#define clr(x,v) memset(x,v,sizeof(x));
#define LL long long
//#define debug
const int mo = ;
const int inf = 0x3f3f3f3f;
const int INF = ;
/**************************************************************************/
int min(int x,int y,int z){
if (x<=y && x<=z) return x;
if (y<=x && y<=z) return y;
if (z<=x && z<=y) return z;
}
int dp[N][],ok[N][];
int n;
int main(){
scanf("%d",&n);
for (int i=;i<=n;i++){
int x;
scanf("%d",&x);
if (x==){
ok[i][]=;
ok[i][]=;
ok[i][]=;
}
if (x==){
ok[i][]=;
ok[i][]=;
ok[i][]=;
}
if (x==){
ok[i][]=;
ok[i][]=;
ok[i][]=;
}
if (x==){
ok[i][]=;
ok[i][]=;
ok[i][]=;
}
}
for (int i=;i<=n;i++){
if (ok[i][]){
dp[i][]=min(dp[i-][],dp[i-][],dp[i-][])+;
}
else dp[i][]=INF;
if (ok[i][]){
dp[i][]=min(dp[i-][],dp[i-][]);
}
else dp[i][]=INF;
if (ok[i][]){
dp[i][]=min(dp[i-][],dp[i-][]);
}
else dp[i][]=INF;
}
printf("%d\n",min(dp[n][],dp[n][],dp[n][]));
#ifdef debug
system("pause");
#endif
}
Problem D Fix a tree
题目大意
有n个点，给定一个序列f[i]表示i号点的父亲为f[i]。
要求改变最少的f[i]，使得这n个点形成一棵树。
解题分析
从每个为搜索过的点开始沿着f[i]开始搜索，如果与之前的点形成了环，说明这些点形成了一个连通块，若形成的环不是自环，则环中的某个点需要改变f[i]，从而形成一棵树。
处理出所有的联通块后，假设有x个。
若其中的某个连通块的有自环j，则需改变x-1次，将其他连通块中的某个环中点f[i]改为j。
若没有自环，则需改变x次，将某个环中点改为自环，其他同上处理。
参考程序
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std; #define N 200008
#define V 200008
#define E 60008
#define lson l,m,rt<<1
#define rson m,r+1,rt<<1|1
#define clr(x,v) memset(x,v,sizeof(x));
#define LL long long
//#define debug
const int mo = ;
const int inf = 0x3f3f3f3f;
const int INF = ;
/**************************************************************************/
int n,tmp,lx=;
int f[V],dfn[V],instack[V];
int ans[V];
void dfs(int x){
if (dfn[x]){
if (instack[x]==lx) ans[++ans[]]=x;
return;
}
instack[x]=lx;
dfn[x]=++tmp;
dfs(f[x]);
}
int main(){
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d",&f[i]); for (int i=;i<=n;i++){
lx++;
if (!dfn[i]) dfs(i);
}
lx=-;
for (int i=;i<=ans[];i++)
if (f[ans[i]]==ans[i]) lx=ans[i];
if (lx==-){
printf("%d\n",ans[]);
for (int i=;i<ans[];i++)
f[ans[i]]=ans[i+];
f[ans[ans[]]]=ans[ans[]];
}
else
{
printf("%d\n",ans[]-);
for (int i=;i<=ans[];i++)
f[ans[i]]=lx;
}
for (int i=;i<=n;i++) printf("%d%c",f[i],i==n?'\n':' '); #ifdef debug
system("pause");
#endif
}