比赛地址：http://codeforces.com/contest/362
参考链接：http://codeforces.com/blog/entry/9584#comment-150925
A. Two Semiknights Meet
我不喜欢CF的题的一个原因是它的题意太"复杂“，而且有"反人类"倾向。（笑
本题中就有一个表述：
After the meeting the semiknights can move on, so it is possible that they meet again.
初看此题的人可能会忽略这个细节，但是这个此题巧妙解法的一个关键。
先说一般解法
分别用BFS(or DFS)求出骑士A和骑士B所能到达的位置以及到达位置时的时间。
如果A和B都能到达maze[i][j] ！= ‘#’，且时间为Ta和Tb。
如果(Ta - Tb) % 2 == 0时，则可以达成meeting条件，反之不可以。(如果一个骑士先到达位置，则可以重复来回跳从而凑足步数。）
再说巧妙解法：
因为移动规则的限制，每一轮两个骑士的相对位置只会有如下几种情况：x + 4 or x - 4 or y + 4 or y - 4 or 不变
所以如果(A.x - B.x) % 4 == 0 || (A.y - B.y) % 4 == 0，则可以确定A和B可以到达同一点，但这一点可以不为'#'。
如果A和B到达了某一个'#'点，根据上面的条件(meet again)，则我们可以反推A或B到达该点的路径，到达A或B的出生点，从而满足条件。
B. Petya and Staircases
简单题。只需要查找有没有i, i+1, i+2均为dirty stairs的就可以了。
坑点：
- m可能为0
- 木有了
C. Insertion Sort
题意很扭曲。简单表示就是，给你一个序列，让你做插入排序。排序前给你一个机会让你交换两个数的位置，使插入排序使用swap函数的次数最少。请问有几种交换方法，此时使用swap函数的次数是多少。
易得，插入排序使用swap的次数等于序列的逆序数。所以我们交换的目的是减少逆序数。
我们枚举pair(A[i], A[j])，且i < j。此时对于逆序数的变化值为 (A[i+1 ... j-1]中小于j的数的个数) + (A[i+1 ... j-1]中大于i的个数)
这个统计可以使用树状数组来解决。不详细说了。(树状数组 - Wiki)
D. Fools and Foolproof Roads
又是一道题意抽风题。大概题意就是一个国家，分成n个区域，区域之间不联通（也不电信^_^）。现在想用p条路连接区域，将这n个区域连为q个区域。连接两个区域的代价是： min(10^9, S + 1)。S是连接的两个区域中的路径长度之和。
坑：
int可能会溢出，不过不影响最后结果。
min(10^9, S + 1)中的 +1
如果A~B已经有一条路径，我们还可以新建A~B的路径，且花费为1000。（用来凑足路径数的关键。这个条件太扭曲了！怒吐一槽！）
如果简化题意和坑，这题就是一个比较简单的Huffman编码的变种。但是加上这些坑和限制，就有的折腾了。
E. Petya and Pipes
一个明显的最小费用流。小小的处理一下费用上界就可以了。
下面是各种代码
A. Two Semiknights Meet
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define print(x) cout << x << endl
#define input(x) cin >> x
const size_t N = 8;
struct Point {
int x,y;
Point(){}
Point(int ix, int iy): x(ix), y(iy){}
};
char maze[N+5][N+5];
int main()
{
freopen("input.txt", "r", stdin);
int T;
input(T);
while (T--) {
for (int i = 0; i < (int)N; i++) {
scanf("%s", maze[i]);
}
int p = 0;
Point ks[2];
for (int i = 0; i < (int)N; i++) {
for (int j = 0; j < (int)N; j++) {
if (maze[i][j] == 'K') {
ks[p++] = Point(i, j);
}
}
}
int dy = ks[0].y - ks[1].y;
int dx = ks[0].x - ks[1].x;
puts(dy % 4 == 0 && dx % 4 == 0? "YES" : "NO");
}
return 0;
}
B. Petya and Staircases
(n, m) = map(int, raw_input().split())
if m:
dirties = sorted(map(int, raw_input().split()))
if not m:
print 'YES'
elif (dirties[0] == 1 or dirties[-1] == n):
print 'NO'
else:
for i in xrange(m):
p = dirties[i:i+3]
if (len(p) != 3):
continue
else:
if p[0] == p[1] - 1 == p[2] - 2:
print 'NO'
break
else:
print 'YES'
C. Insertion Sort
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define print(x) cout << x << endl
#define input(x) cin >> x
const int SIZE = 5120;
const int INF = 0x3f3f3f3f;
inline int lowbit(int x)
{
return x&(-x);
}
struct BIT//点更新，区间查询
{
int baum[SIZE];
inline void init()
{
memset(baum,0,sizeof(baum));
}
void add(int x,int val)
{
while(x<SIZE)
{
baum[x]+=val;
x+=lowbit(x);
}
}
int sum(int x)
{
int res=0;
while(x>0)
{
res+=baum[x];
x-=lowbit(x);
}
return res;
}
int sum(int a,int b)//查询区间和
{
return sum(b)-sum(a-1);
}
};
int n;
int A[SIZE];
int main()
{
freopen("input.txt", "r", stdin);
BIT bit;
input(n);
for (int i = 0; i < n; i++) {
input(A[i]);
A[i]++;
}
int ans = -INF;
int ans_cnt = -1;
for (int i = 0; i < n; i++) {
bit.init();
bit.add(A[i], 1);
for (int j = i + 1; j < n; j++) {
int adv = 0;
bit.add(A[j], 1);
adv -= bit.sum(0, A[j] - 1);
adv += bit.sum(A[j] + 1, n);
adv += bit.sum(0, A[i] - 1);
adv -= bit.sum(A[i] + 1, n);
if (adv == ans) {
ans_cnt++;
} else if (adv > ans) {
ans = adv;
ans_cnt = 1;
}
}
}
int inv = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (A[j] > A[i]) {
inv++;
}
}
}
print(inv - ans + 1<< ' ' << ans_cnt);
return 0;
}
D. Fools and Foolproof Roads
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <map>
using namespace std;
#define print(x) cout << x << endl
#define input(x) cin >> x
typedef long long llint;
const int SIZE = 100100;
const llint INF = 1000000000LL;
struct Road {
int from, to;
llint cost;
Road(){}
Road(int ifrom, int ito, llint icost): \
from(ifrom), to(ito), cost(icost) {}
};
struct Distinct {
int nr;
llint tot;
Distinct(){}
Distinct(int inr, llint itot): \
nr(inr), tot(itot){}
friend bool operator < (const Distinct& a, const Distinct& b)
{
return a.tot > b.tot;
}
};
int n, m, p ,q;
vector<Road> road_vec, new_road_vec;
int cnc[SIZE];
llint rlen[SIZE];
void init()
{
road_vec.clear();
new_road_vec.clear();
for (int i = 0; i < SIZE; i++) {
cnc[i] = i;
}
memset(rlen, 0, sizeof(rlen));
}
int get_father(int x)
{
if (cnc[x] == x) return x;
else return cnc[x] = get_father(cnc[x]);
}
int make_union()
{
for (int i = 0;i < (int)road_vec.size(); i++) {
int from = road_vec[i].from;
int to = road_vec[i].to;
cnc[get_father(from)] = cnc[get_father(to)];
}
set<int> st;
for (int i = 0; i < n; i++) {
st.insert(get_father(cnc[i]));
}
return st.size();
}
void fill_rlen()
{
for (int i = 0; i < (int)road_vec.size(); i++) {
int from = road_vec[i].from;
int cost = road_vec[i].cost;
rlen[get_father(from)] += cost;
}
}
llint solve()
{
llint res = 0;
priority_queue<Distinct> pq;
for (int i = 0; i < n; i++) {
if (get_father(i) != i) continue;
else {
pq.push(Distinct(i, rlen[i]));
}
}
for (int i = 0; i < p && pq.size() >= 2; i++) {
Distinct a = pq.top();
pq.pop();
Distinct b = pq.top();
pq.pop();
llint cost = min(INF, a.tot + b.tot + 1);
res += cost;
new_road_vec.push_back(Road(a.nr, b.nr, -1));
Distinct c(a.nr, a.tot + b.tot + cost);
pq.push(c);
}
return res;
}
int main()
{
freopen("input.txt", "r", stdin);
int a, b;
llint c;
while(input(n >> m >> p >> q)) {
init();
while (m--) {
input(a >> b >> c);
a--;b--;
road_vec.push_back(Road(a, b, c));
}
int us = make_union();
fill_rlen();
if (us - p > q || us < q) {
print("NO");
continue;
}
llint ans = 0;
int t = 0;
bool need_fill = false;
Road road_fill;
if (us - p < q) {
t = p - (us - q);
p = us - q;
need_fill = true;
}
ans += solve();
if (need_fill && \
road_vec.empty() &&
new_road_vec.empty()) {
print("NO");
continue;
} else if (need_fill) {
road_fill = !road_vec.empty()? road_vec[0]: new_road_vec[0];
}
print("YES");
for (int i = 0; i < t; i++) {
new_road_vec.push_back(road_fill);
}
ans += 1000 * t;
for (int i = 0; i < (int)new_road_vec.size(); i++) {
printf("%d %d\n",
new_road_vec[i].from + 1,
new_road_vec[i].to + 1);
}
//print(ans);
}
return 0;
}
E. Petya and Pipes
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define print(x) cout << x << endl
#define input(x) cin >> x
const int NODE = 1024;
const int EDGE = 180000;
const int INF = 0x3f3f3f3f;
struct edge
{
int dest, flow, cost, next;
edge(){}
edge(int idest, int iflow, int icost, int inext): \
dest(idest),
flow(iflow),
cost(icost),
next(inext){}
};
edge g[EDGE];
int ind;
int head[NODE],pre[NODE];
int dis[NODE];
char visit[NODE];
int n, K;
inline void _addEdge(int st,int end,int flow,int cost)
{
g[ind]=edge(end,flow,cost,head[st]);
head[st]=ind++;
}
inline void addEdge(int st,int end,int flow,int cost)
{
_addEdge(st,end,flow,cost);
_addEdge(end,st,0,-cost);
}
void init()
{
memset(head,-1,sizeof(head));
ind=0;
}
int spfa(int source,int sink)
{
queue<int> q;
memset(dis,0x3f,sizeof(dis));
memset(visit,0,sizeof(visit));
pre[source]=-1;
q.push(source);
visit[source]=1;
dis[source]=0;
while(!q.empty())
{
int now=q.front();
q.pop();
visit[now]=0;
for(int i=head[now];i!=-1;i=g[i].next)
{
int next=g[i].dest;
int cost=g[i].cost;
int flow=g[i].flow;
if(flow>0 && dis[next]>dis[now]+cost)
{
dis[next]=dis[now]+cost;
if(!visit[next])
{
q.push(next);
visit[next]=1;
}
pre[next]=i;
}
}
}
return dis[sink];
}
void MinCostMaxFlow(int source, int sink, int &maxflow, int &mincost)
{
int flow;
maxflow = 0; mincost = 0;
while(1)
{
int cost = spfa(source, sink);
if(cost >= INF) break;
flow = INF;
int now = sink;
while(now != source)
{
flow = min(flow, g[pre[now]].flow);
now = g[pre[now] ^ 1].dest;
}
if (mincost + flow * cost > K) {
maxflow += (K - mincost) / cost;
break;
}
maxflow += flow;
mincost += flow * cost;
now = sink;
while(now != source)
{
g[pre[now]].flow -= flow;
g[pre[now] ^ 1].flow += flow;
now = g[pre[now] ^ 1].dest;
}
}
}
int main()
{
freopen("input.txt","r", stdin);
int a;
input(n >> K);
init();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
input(a);
if (a) {
addEdge(i, j, a, 0);
addEdge(i, j, K, 1);
}
}
}
int flow, cost;
MinCostMaxFlow(1, n, flow, cost);
print(flow);
return 0;
}