SRM 593
DIV1 250pt
题意：有如下图所示的平面，每个六边形有坐标。将其中一些六边形染色，要求有边相邻的两个六边形不能染同一种颜色。给定哪些六边形需要染色，问最少需要多少种颜色。
解法：首先，需要0种颜色和需要1种颜色很容易判断，其次，最多需要3种颜色。易证。
也就是说，难以判断的就是需要2种颜色还是3种颜色。假定只需要染2种颜色，然后将需要染色的六边形染色，看是否会出现矛盾。用DFS染色。
Ps:和官方题解一比，自己写的代码太麻烦了....
tag:染色
/*
* Author: plum rain
* score : 0
*/
#line 11 "HexagonalBoard.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std; typedef vector<string> VS;
VS b;
int n, ans, col[][]; void DFS (int x, int y, int c)
{
if (!(b[x][y] == 'X' && col[x][y] == -)) return ;
col[x][y] = c;
ans = max(ans, );
for (int i = max(, x-); i <= min(n-, x+); ++ i)
for (int j = max(, y-); j <= min(n-, y+); ++ j){
if (i-x != j-y && b[i][j] == 'X'){
DFS (i, j, !c);
ans = max(, ans);
if (col[i][j] == c){
ans = ;
return ;
}
}
}
} class HexagonalBoard
{
public:
int minColors(vector <string> board){
b.clear(); b = board;
n = b.size();
ans = ;
memset (col, -, sizeof(col)); for (int i = ; i < n; ++ i)
for (int j = ; j < n; ++ j){
DFS (i, j, );
if (ans == ) return ;
} return ans;
}
};
DIV1 450pt
题意：有n只兔子，每只兔子跑一圈的时间在范围a[i] ～ b[i]。将兔子分为两组S和T，每只兔子分别跑一圈，每组所用时间等于该组所有兔子消耗时间之和。每组可能的所用时间之差的最大值为x。求x的最小值。
解法：记A为所有a[i]的和，B为所有b[i]的和，记sum = A + B。记所有属于T的兔子的a[i]之和t_a，b[i]之和为t_b，所有属于S的兔子的a[i]之和s_a，b[i]之和为s_b。
每次将兔子分为两组之后，时间之差的最大值为max (t_b - s_a, s_b - t_a)或者max (s_b - t_a, s_b - t_a)。由于考虑到T和S是地位对等的，即如果存在T = {1,3}，S = {2}的情况，也一定存在T = {2}, S = {1, 3}的情况。所以只需要求max (t_b - s_a, s_b - t_a)即可。
max (t_b - s_a, s_b - t_a) = max (t_b - (A-t_a), (B-t_b) - t_a) = max ((t_a+t_b) - A, sum - A - (t_a+t_b))，且要使max值尽量小，则t_a + t_b 尽量接近于sum/2即可。(注意sum和A都是固定值)
也就是说，先用一次动态规划处理出t_a + t_b的所有可能值，然后再找最接近sum/2的一个即可。
tag:math, dp, think, good
/*
* Author: plum rain
* score : 0
*/
#line 11 "MayTheBestPetWin.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl const int maxx = ;
bool dp[maxx+]; class MayTheBestPetWin
{
public:
int calc(vector <int> A, vector <int> B){
CLR (dp); dp[] = ;
int sum = , ta = ;
for (int i = ; i < A.size(); ++ i){
int s = A[i] + B[i];
sum += s; ta += A[i];
for (int j = maxx-s; j >= ; -- j)
if (dp[j]) dp[j+s] = ;
}
int half = sum / ;
while (!dp[half]) -- half;
return (sum - ta - half);
}
};