重新开始记录点东西。
上周末的比赛，放假了，于是一觉睡到下午。。。比赛由dvorak和BIAOBrother搞定了。。。我只是清明末把题重新刷了一遍。。。
按我做的顺序来。。。
G 超级大水题，判断输入的数据中有木有‘G'，居然放到Regional的site里了，不容易啊，更不容易的是我居然交了两次……5A水题的能力啊！Possible拼成了Possilbe。。。不想说啥了
E 找第k个素因子个数大于等于三的数，很明显的筛素，将答案预处理出来。写了两遍，头一遍是筛出足够多的素数之后，从43开始往后找1000个数，满足含有三个以上的素因子的，判断通过分解来求；第二遍利用一个小技巧，在筛素的过程中统计素因子的个数，每筛掉一个合数，就给它的素因子个数+1，后面就是一样的了。
预处理部分的代码：
bool isNotPrime[N * 10];
int facts[N * 10];
int ans[N] = {30, 42};
int t, n, cnt;
inline void prePrime()
{
for (int i = 2; i < N * 10; i++)
{
if (!isNotPrime[i])
for (int j = i + i; j < N * 10; j += i)
{
isNotPrime[j] = 1;
facts[j]++;
}
}
}
inline void preAns()
{
cnt = 2;
for (int i = 42 + 1; cnt < N; i++)
if (facts[i] >= 3) ans[cnt++] = i;
}
J 水模拟，将图中可以扩散的小写字母扩散，如果两个字母可以同时到达某点，则记录为战争状态'*'。利用一个步数矩阵记录下从起始点（小写字母点）到当前位置的最小步数，起点初始化为0，其他全部是INF。将起点入队，广搜之，对于可以到达的点，如果所需的步数大于那一点的原步数，显然不可能到达；如果步数相等，则说明是一个战争点，标记之，并且以后搜索遇到改点全部跳过；可以证明，除了第一次对INF的处理以外，不会遇到步数小于目的点的情况的。
代码：
int r, c;
int t;
char gra[S][S], ans[S][S];
int stps[S][S];
inline bool judge(int x, int y)
{
return (x >= 0 && x < r && y >= 0 && y < c && gra[x][y] == '.');
}
void bfs()
{
queue<POS> q;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
{
ans[i][j] = gra[i][j];
if (islower(gra[i][j]))
stps[i][j] = 0, q.push(POS(i, j, 0, gra[i][j]));
}
while (!q.empty())
{
sta = q.front();
q.pop();
if (ans[sta.x][sta.y] == '*')
continue;
char type = sta.type;
for (int i = 0; i < 4; i++)
{
int tx = sta.x + MOV[i][0], ty = sta.y + MOV[i][1], stp = sta.stps + 1;
if (!judge(tx, ty))
continue;
if (stps[tx][ty] == stp)
{
if (ans[tx][ty] != type)
ans[tx][ty] = '*';
}
else if (stps[tx][ty] > stp)
{
stps[tx][ty] = stp;
ans[tx][ty] = type;
q.push(POS(tx, ty, stp, type));
}
}
}
}
A，DP，求从当前点到目的点（中间会有能力值变化，不能为0），最少需要多少能力值，暑假集训时的原题改了下题目背景。。。两个思路，二分初始的能力值，然后dp或者搜索到达最后一点，看看过程中能不能保证能力恒大于零；另一个就是从最后一点倒着往前dp，更为直观的写就是从（1，1）点开始像后搜索直到终点，搜索过程中记录一下最优值就行，碰到一个点能力值小于1了，就将它变为1。
代码：
const int S = 512;
const int INF = 0x3f3f3f3f;
int s[S][S];
int dp[S][S];
int t, r, c, ans;
int dfs(int x, int y)
{
if (dp[x][y] < INF)
return dp[x][y];
if (x < r)
dp[x][y] = min(dp[x][y], dfs(x + 1, y) + s[x][y]);
if (y < c)
dp[x][y] = min(dp[x][y], dfs(x, y + 1) + s[x][y]);
return (dp[x][y] = max(dp[x][y], 1));
}
int main()
{
for (scanf("%d", &t); t; t--)
{
scanf("%d %d", &r, &c);
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++)
scanf("%d", &s[i][j]), s[i][j] = -s[i][j];
memset(dp, 0x3f, sizeof (dp));
dp[r][c] = 1;
ans = dfs(1, 1);
printf("%d\n", ans);
}
return 0;
}
B 沾点计算几何的边，查询给定的若干图形的并集包含多少个点。方法N多，可以在读入过程中处理矩阵最后计算，也可以读入过程中记录下图形，枚举所有点，查询其是否在某个图形中。统计正方形里的点最容易，统计圆里的点需要利用x**2 + y**2 <= r**2 ，三角形最麻烦，注意到若一个店O在三角形ABC里面，则S(OAC) + S(OAB) + S(OBC) == S(ABC)，利用叉积计算出四个三角形的面积即可。这里唯一的trick就是对于圆来说，虽然圆心在正半平面，但是有可能它包含了负半平面里面的点，对于输入的坐标进行一下偏移即可，我一开始时偏移超过了矩阵，出了个RE。
代码：
const int N = 256;
const int INF = 0x3f3f3f3f;
char ch;
int t, n, ans;
int mat[N][N];
inline void initMat()
{
memset(mat, 0, sizeof (mat));
}
inline void fillTriangle(int *x, int *y)
{
int a = INF, b = INF, c = -INF, d = -INF;
int realArea = abs((x[1] - x[0]) * (y[2] - y[0]) - (x[2] - x[0]) * (y[1] - y[0]));
for (int i = 0; i < 3; i++)
a = min(x[i], a), b = min(y[i], b), c = max(x[i], c), d = max(y[i], d);
for (int i = a; i <= c; i++)
for (int j = b; j <= d; j++)
{
int sumArea = 0;
for (int k = 0; k < 3; k++)
sumArea += abs((x[k] - i) * (y[(k + 1) % 3] - j) - (x[(k + 1) % 3] - i) * (y[k] - j));
if (sumArea == realArea)
mat[i][j] = 1;
}
}
inline void fillSquare(int x, int y, int l)
{
for (int i = 0; i <= l; i++)
for (int j = 0; j <= l; j++)
mat[x + i][y + j] = 1;
}
inline void fillCircle(int x, int y, int r)
{
for (int i = -r; i <= r; i++)
for (int j = -r; j <= r; j++)
if (i * i + j * j <= r * r)
mat[x + i][y + j] = 1;
}
int main()
{
int x[3], y[3], p;
for (scanf("%d", &t); t; t--)
{
initMat();
scanf("%d", &n);
while (n--)
{
scanf(" %c", &ch);
switch(ch)
{
case 'C':
scanf("%d %d %d", x, y, &p);
x[0] += N >> 1, y[0] += N >> 1;
fillCircle(x[0], y[0], p);
break;
case 'T':
for (int i = 0; i < 3; i++)
scanf("%d %d", x + i, y + i), x[i] += N >> 1, y[i] += N >> 1;
fillTriangle(x, y);
break;
case 'S':
scanf("%d %d %d", x, y, &p);
x[0] += N >> 1, y[0] += N >> 1;
fillSquare(x[0], y[0], p);
break;
defaule:
;
}
}
ans = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
ans += mat[i][j];
printf("%d\n", ans);
}
return 0;
}
D，将一个错误的比赛序列通过最小耗费修正（正确的序列理解为，存在这样一种可能使每个人输赢恰好是这么多场。。。好难说，但是很容易理解）。排序，然后从小到大处理，用sum计算到当前位置i，i位置及其以前位置的所有队伍，至少一共应该赢多少场（这个理解太诡异了），x[i - 1] = 0 + 1 + 2 + ... + i - 1 - sigma(x[j])(j < i - 1)，因为正确的序列显然满足它的任意子序列也是正确的，不然单独来看这一子序列的比赛就不可能得到结果。那么 k 个队伍，互相就可以比试 sigma(i)(0
<= i <k)场，则仅仅是它们之间的比赛就会形成sigma(i)(0 <= i < k)次胜利，而显然每个队伍还会跟k + 1之后的队伍进行比试，所以sigma(x[i]) = sigma(i)，遇到不满足的，将它变换为恰好是剩余量即可（这样的偏移最小）；到了最后一个元素n - 1，应当恰好有sigma(x[n - 1]) == simga(n - 1)，然而由于从小到大计算过程中计算的是下界，因此有可能出现胜利场数大于比赛总场数的情况。因此再从后往前进行一次扫描，计算每个元素的上界。重新计算sum =
(n - 1) + (n - 2) + ... + k - sigma(x[j]) (k < j < n)，这就是当前元素的上界，每个队伍最多能胜这么多场，多了的没处胜去，减掉即可，恰好减到上界以保证耗费最小。
这个题比赛的过程中肯定是想不出来的。。。从下向上扫描时考虑的是前k个队伍的整体下界，而从上向下扫描的时候考虑的是第k个队伍的独立上界，上行和下行代码基本一样但是实际意义完全是不同的。。。这个逻辑很奇葩。
开始时忘了给ans初始化为0WA了一次。。。
代码：
void cal()
{
int sum = 0;
sort(a, a + n);
for (int i = 0; i < n; i++)
{
sum += i;
if (sum <= a[i])
sum -= a[i];
else
ans += sum - a[i], a[i] = sum, sum = 0;
}
sum = 0;
for (int i = n - 1; i >= 0; i--)
{
sum += i;
if (sum >= a[i])
sum -= a[i];
else
ans += a[i] - sum, sum = 0;
}
}
H，组合数的计算。计算同时包含当前数列的最大值和最小值的子列（不一定连续）和子串（一定是连续的）各有多少。
trick是数列中元素全都相等，此时子列数是2 ** n - 1， 子串数是 1 + 2 + ... + n = n * (n + 1) / 2（其实子串数可以不用特判的）。。。对于其他情况，子列数为(2 ** c1 - 1) * (2 ** c2 - 1) * (2 ** (n - c1 - c2))，c1和c2分别是最大值出现的次数和最小值出现的次数，最大值和最小值必然在结果中出现一次，而其他值可以出现可以不出现。不论用不用特判，子串数的计算可以从头开始扫描，碰到最大最小值就更新下下标，当两者同时出现时，每次循环都将ans值加上两个下标中的最小值即可。
输出时忘了取模，WA了两次……
代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f;
const LL MOD = 1000000007;
const int N = 100010;
int t, n;
int mmin, mmax, pos1, pos2;
LL ans1, ans2, cnt1, cnt2;
int a[N];
inline LL quickPow(LL a, int p)
{
LL res = 1;
while (p)
{
if (p & 1) res = res * a % MOD;
p >>= 1;
a = (a * a) % MOD;
}
return res;
}
int main()
{
for (scanf("%d", &t); t; t--)
{
scanf("%d", &n);
mmin = INF, mmax = -INF;
ans1 = ans2 = 0;
cnt1 = cnt2 = 0;
pos1 = pos2 = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", a + i);
mmin = min(mmin, a[i]);
mmax = max(mmax, a[i]);
}
for (int i = 1; i <= n; i++)
{
if (a[i] == mmin) pos1 = i;
if (a[i] == mmax) pos2 = i;
if (pos1 && pos2)
ans1 += min(pos1, pos2);
}
for (int i = 1; i <= n; i++)
{
if (a[i] == mmin) cnt1++;
if (a[i] == mmax) cnt2++;
}
if (mmin == mmax)
ans2 = ((quickPow(2, n) - 1) % MOD + MOD) % MOD;
else
ans2 = ((((quickPow(2, cnt1) - 1) * (quickPow(2, cnt2) - 1)) % MOD) * quickPow(2, n - cnt1 - cnt2)) % MOD;
printf("%lld %lld\n", ans1 % MOD, ans2);
}
return 0;
}
C题，还木有做出来。KM算法只会套模板的日子看来是不再好过了。碰到两个子图的大小不好判别的时候就会有BUG。这题是抢银行……M个人各有一个背包，银行里有N个金库，第i个金库里有X[i]块金子，重量分别为g[i][j]。只有当某个人i的背包容量v[i]恰好可以分解成第j个金库里的某几块金子时，他才会动手抢，问M个人同时出动，每个人都工作，一共可以抢多少金子。。。很明显的二分图最优匹配，建图时处理一下子集和，如果i有抢第j个金库的动机，则在i、j间连一条权值为v[i]的边。最后KM即可。
两个问题：1.处理子集和，很显然枚举是不好滴，那么可以考虑用hash处理的方法（显然是去年数据结构考试题倒数第二题的加强版啊！），将集合的一半枚举之后把所有可能放入一个set里（有劲的话自己写hash……），枚举另一半的可能集合，遇到满足某个值加上set里的某个值恰好等于某个v[i]时，就可以连边啦！
2.KM算法要求m < n，于是竟然超时了！将m < n的判断加进去后却WA了……至今未过……其实我这里觉得奇葩的是，题目中说了每个人在同一时刻都会工作且一个金库最多只能去一个人……不理解m > n时应该输出0还是输出-1啊……题目中又没有说明。。。这么扯……求讲……
终于过了。。。用set进行子集和枚举的时候60s的时限我52s过的，这么扯……那些12s的都是怎么过的呢？改为hash，29s过。后来在hash里面加了个小trick（不清空hash值），可以16s多过，但是题目底下给出的要求（估计是印度现场赛时的时限吧）是10s，还是不行的啊。。。
这是最终代码，KM部分是飞哥敲的。。。于是代码风格跟我上面的完全不同了……
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;
#define MAXN 55
#define MAXM 10000002
#define inf 1000000000
#define _clr(x) memset(x,-1,sizeof(int)*MAXN)
int m, n, maxHold;
int hash_cnt;
int hold[55];
int x[55];
int gold[55][30];
int G[55][55];
int m1[MAXN], m2[MAXN];
int hash[MAXM];
int kuhn_munkras(int m, int n, int mat[][MAXN], int*match1, int* match2) {
int s[MAXN], t[MAXN], l1[MAXN], l2[MAXN], p, q, ret = 0, i, j, k;
for (i = 0; i < m; i++) {
for (l1[i] = -inf, j = 0; j < n; j++)
l1[i] = mat[i][j] > l1[i] ? mat[i][j] : l1[i];
if (l1[i] == -inf) return -1; // 无法匹配!
}
for (i = 0; i < n; l2[i++] = 0);
for (_clr(match1), _clr(match2), i = 0; i < m; i++) {
for (_clr(t), s[p = q = 0] = i; p <= q && match1[i] < 0; p++)
for (k = s[p], j = 0; j < n && match1[i] < 0; j++)
if (l1[k] + l2[j] == mat[k][j] && t[j] < 0) {
s[++q] = match2[j], t[j] = k;
if (s[q] < 0)
for (p = j; p >= 0; j = p)
match2[j] = k = t[j], p = match1[k], match1[k] = j;
}
if (match1[i] < 0) {
for (i--, p = inf, k = 0; k <= q; k++)
for (j = 0; j < n; j++)
if
(t[j] < 0 && l1[s[k]] + l2[j] - mat[s[k]][j] < p)
p = l1[s[k]] + l2[j] - mat[s[k]][j];
for (j = 0; j < n; l2[j] += t[j] < 0 ? 0 : p, j++);
for (k = 0; k <= q; l1[s[k++]] -= p);
}
}
for (i = 0; i < m; i++) {// if处理无匹配的情况!!
if (match1[i] < 0) return -1;
if (mat[i][match1[i]] <= -inf) return -1;
ret += mat[i][match1[i]];
}
return ret;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &m, &n);
maxHold = -inf;
for (int i = 0; i < m; i++) {
scanf("%d", &hold[i]);
maxHold = max(maxHold, hold[i]);
}
for (int i = 0; i < n; i++) {
scanf("%d", &x[i]);
for (int j = 0; j < x[i]; j++)
scanf("%d", &gold[i][j]);
}
memset(G, 0, sizeof (G));
int ans;
for (int i = 0; i < n; i++)
{
int mid = x[i] / 2;
for (int j = 0; j < (1 << mid); j++)
{
int ts = 0;
for (int k = 0; k < mid; k++)
if (j & (1 << k))
ts += gold[i][k];
if (ts <= maxHold)
hash[ts] = hash_cnt;
}
mid = x[i] - mid;
for (int j = 0; j < (1 << mid); j++)
{
int ts = 0;
for (int k = 0; k < mid; k++)
if (j & (1 << k))
ts += gold[i][k + x[i] - mid];
for (int k = 0; k < m; k++)
if (ts <= hold[k] && hash[hold[k] - ts] == hash_cnt)
{
if (m <= n)
G[k][i] = hold[k];
else
G[i][k] = hold[k];
}
}
hash_cnt++;
}
ans = kuhn_munkras(min(m, n), max(m, n), G, m1, m2);
printf("%d\n", ans);
}
}
F和I……题目没看懂……没法做了。。。