只需要处理出每个骑士到达每个位置的最短时间t，接下来他可以通过去另一个位置再回来，所以他在这个位置的时间可以是t+2*k，所以只需要判断每个位置两个骑士到达最短时间的奇偶性即可，注意该位置必须是两个骑士都可以到的。
// Author : JayYe Created Time: 2013-11-15 9:10:00
#include
#include
#include
#include
using namespace std;
struct PP {
int x, y, step;
PP(int x,int y,int step):x(x), y(y), step(step){}
};
int dir[4][2] = {{2,2}, {2, -2}, {-2, 2}, {-2, -2}};
char s[11][11];
void bfs(int x, int y, int stp[11][11], bool vis[11][11]) {
memset(vis, false, sizeof(vis));
vis[x][y] = true;
stp[x][y] = 0;
queue q;
q.push(PP(x, y, 0));
while(!q.empty()) {
PP cur = q.front(); q.pop();
x = cur.x; y = cur.y;
int step = cur.step;
for(int i = 0;i < 4; i++) {
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if(xx >= 0 && xx < 8 && yy >= 0 && yy < 8 && !vis[xx][yy]) {
vis[xx][yy] = true;
q.push(PP(xx, yy, step+1));
stp[xx][yy] = step+1;
}
}
}
}
int stp1[11][11], stp2[11][11];
bool vis1[11][11], vis2[11][11];
int main() {
int t;
scanf("%d", &t);
while(t--) {
memset(vis1, false, sizeof(vis1));
memset(vis2, false, sizeof(vis2));
for(int i = 0;i < 8; i++)
scanf("%s", s[i]);
int tot = 0;
for(int i = 0;i < 8; i++) {
for(int j = 0;j < 8; j++) if(s[i][j] == 'K') {
if(!tot)
bfs(i, j, stp1, vis1);
else
bfs(i, j, stp2, vis2);
tot++;
}
}
bool flag = false;
for(int i = 0;i < 8; i++) {
for(int j = 0;j < 8; j++) if(s[i][j] != '#' && vis1[i][j] && vis2[i][j]) {
if(stp1[i][j]%2 == stp2[i][j]%2) {
// printf("%d %d %d %d\n", i, j, stp1[i][j], stp2[i][j]);
flag = true;
}
}
}
if(flag) puts("YES");
else puts("NO");
}
return 0;
}
来自CODE的代码片
A.cpp
B. Petya and Staircases
水题不多说了。。
C. Insertion Sort
很容易看出题目是要你交换某两个位置，然后使得逆序对最少。
先求出原来的逆序对，如果交换i , j 位置i < j，那么(i+1, j)中比a(i)小的数就不与a(i)成逆序对了，而(i+1, j)中比a(i)大的数就与a(i)成逆序对了，如果可以O(1)求出逆序对的改变值，那么复杂度就是O(n^2)。
前面处理出sum[i][j]表示 a(i+1), ... a(j)中比a(i)小的数有多少，比a(i)大的数就是区间长度减去sum[i][j]。
同理sum2[i][j]表示a(i-1), a(i-2)...a(j)中比a(i)小的数有多少。。其实只需要一个数组= =有了这两个数组就可以很容易求出逆序对的改变值。
// Author : JayYe Created Time: 2013-11-15 9:46:17
#include
#include
#include
using namespace std;
const int maxn = 5000 + 5;
const int INF = 1<<30;
int a[maxn], sum[maxn][maxn], sum2[maxn][maxn];
int main() {
int n;
scanf("%d", &n);
for(int i = 0;i < n; i++)
scanf("%d", &a[i]);
for(int i = 0;i < n; i++) {
sum[i][i] = 0;
for(int j = i+1;j < n; j++) {
sum[i][j] = sum[i][j-1];
if(a[j] < a[i])
sum[i][j]++;
}
sum2[i][i] = 0;
for(int j = i-1;j >= 0; j--) {
sum2[i][j] = sum2[i][j+1];
if(a[i] > a[j])
sum2[i][j]++;
}
}
int tot = 0;
for(int i = 0;i < n; i++) {
for(int j = i+1;j < n; j++) if(a[i] > a[j])
tot++;
}
int mn = INF, ans = 0;
for(int i = 0;i < n; i++) {
for(int j = i+1;j < n; j++) {
int cur = tot + (j-i) - 2*sum[i][j-1] + 2*sum2[j][i+1] - (j-i);
if(a[i] > a[j]) cur--;
else cur++;
if(cur < mn) {
mn = cur; ans = 1;
}
else if(cur == mn) ans++;
}
}
printf("%d %d\n", mn, ans);
return 0;
}
来自CODE的代码片
C.cpp
D. Fools and Foolproof Roads
求出所有联通块和联通块中所有路长度的和，因为告诉了最后的联通块数，所以可以知道要连接确定数目的联通块，其他的路都是只能建立在同一个联通块里，所以只需要考虑怎么连