A题 http://codeforces.com/problemset/problem/699/A
非常的水，两个相向而行，且间距最小的点，搜一遍就是答案了。
#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
int x;char ch;
}s[+];
bool cmp(node& a,node& b)
{
return a.x<b.x;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
getchar();
;i<n;i++)
scanf("%c",&s[i].ch);
;i<n;i++)
scanf("%d",&s[i].x);
sort(s,s+n,cmp);
int ans = 0x3f3f3f3f;
;i<n;i++)
{
].ch == 'R')
{
].x)/;
ans = min(ans,dis);
}
}
if(ans == 0x3f3f3f3f)
printf("-1\n");
else
printf("%d\n",ans);
}
;
}
B题 http://codeforces.com/problemset/problem/699/B
讲道理 也是水题 然而我在实现的时候 实现不好这个问题 然而梦天2333 毕竟天神啪啪啪随便写写就A了。
这个代码是参考网上的思路搞的，关键是一个V数组和一个C数组记录，行和列的情况。
还有读入字符串的时候要小心的，因为它题目中默认的地图是从1开始的，如果直接scanf ma[i]这样读进来 就是每行都从0开始了，和题意不符
scanf();//输入的一个小技巧
其实思路和它标程是一样的，就是没码出来。
#include <cstdio>
#include <cstring>
#define mem0(x) memset(x,0,sizeof(x))
][];
],C[];
int tot,fi,fj,n,m;
bool judge()
{
;i<=n;i++)
{
;j<=m;j++)
{
int cur = R[i] + C[j];
if(ma[i][j] == '*') cur--;
if(tot == cur)
{
fi = i, fj = j;
return true;
}
}
}
return false;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
mem0(R);
mem0(C);
;i<=n;i++)
scanf();//输入的一个小技巧
tot = ;
;i<=n;i++)
;j<=m;j++)
if(ma[i][j] == '*')
{
R[i] ++;
C[j] ++;
tot++;
}
if(judge())
printf("YES\n%d %d\n",fi,fj);
else
printf("NO\n");
}
;
}
C题 http://codeforces.com/problemset/problem/698/A
dp，小心一下 任何一种情况下都是能选择休息的。
#include <cstdio>
#include <map>
#include <queue>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define mem0(x) memset(x,0,sizeof(x))
#define mem1(x) memset(x,-1,sizeof(x))
typedef long long LL;
const int INF = 0x3f3f3f3f;
int a;
][];
int main()
{
int n;
scanf("%d",&n);
;i<=n;i++)
{
scanf("%d",&a);
)
{
dp[i][] = max(max(dp[i-][], dp[i-][]), dp[i-][]);
}
)
{
dp[i][] = max(max(dp[i-][],dp[i-][]),dp[i-][]);
dp[i][] = max(dp[i-][], dp[i-][]) + ;
}
)
{
dp[i][] = max(max(dp[i-][],dp[i-][]),dp[i-][]);
dp[i][] = max(dp[i-][], dp[i-][]) + ;
}
else
{
dp[i][] = max(max(dp[i-][],dp[i-][]),dp[i-][]);
dp[i][] = max(dp[i-][], dp[i-][]) + ;
dp[i][] = max(dp[i-][], dp[i-][]) + ;
}
}
;
;i<;i++)
maxn = max(maxn, dp[n][i]);
printf("%d\n",n-maxn);
;
}
D题 http://codeforces.com/problemset/problem/698/B
这题挺难想的当时。先思考整个问题，无非是由若干个环和若干棵树来组成了最初的图。
如果都是树，那么很好解决，选一棵树作为主树，其他的树根直接链接到主树的根上就解决问题了，修改次数应该是根结点的总数目-1。
如果都是环，那么，把某个环的某个结点接到自己身上，形成一棵树之后，其他的环直接接上来就好了。
如果是环和树都有，那么只要把环接到主树上就好了。
#include <cstdio>
#include <map>
#include <queue>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define mem0(x) memset(x,0,sizeof(x))
#define mem1(x) memset(x,-1,sizeof(x))
typedef long long LL;
const int INF = 0x3f3f3f3f;
];
];
int uf_find(int x)
{
if(x==pa[x]) return x;
return pa[x] = uf_find(pa[x]);
}
int main()
{
int n,cnt,root;
scanf("%d",&n);
//uf_init
;i<=n;i++) pa[i] = i ;
cnt = , root = ;
;i<=n;i++)
{
scanf("%d",&a[i]);
if(i == a[i])
{
cnt++,root = i;
}
else
{
int fx = uf_find(i);
int fy = uf_find(a[i]);
if(fx == fy) a[i] = i,cnt++;//成环
else pa[fx] = fy;
}
}
)
{
;i<=n;i++)
{
if(i == pa[i])
{
root = i;
break;
}
}
cnt++;
}
printf();
;i<=n;i++)
{
if(i == a[i]) a[i] = root;//根只能有一个
printf("%d%c",a[i],i==n?'\n':' ');
}
;
}