over 6 years ago
嘟噜噜... 还有一个月就NOIP了，AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧
简单写点弱鸡题解， 第一是督促一下作业进度，第二呢也可以来熟悉一下输入法。岂不是很妙。
FoxAndMountainEasy
关键词：小学数学
算法简述
可以根据高度差来计算出U和D的数量，这里在计算的时候要处理一些非法的情况。由于还要满足这个条件，找到模式串中前缀最小的一个位置，计算它是否可行就行了。
一点点小代码
class FoxAndMountainEasy {
public:
string possible(int n, int h0, int hn, string history) {
int num = 0; //history中U的个数
for (int i = 0; i < history.size(); ++i) if (history[i] == 'U') ++num;
int U, D; // U D 的个数
if ((n + hn - h0) & 1) return "NO";
U = (n + hn - h0) / 2;
D = n - U;
if (U < 0 || D < 0) return "NO"; //去掉不可到达的情况
if (num > U || history.size() - num > D) return "NO"; //如果history中的U或D超过了实际的数量就不合法
int lim = h0 + U - num;
for (int i = 0; i < history.size(); ++i) { //还要满足h[i] >= 0 这个条件 计算最小的前缀是否可行
if (history[i] == 'U') ++lim;
else --lim;
if (lim < 0) return "NO";
}
return "YES";
}
};
Incubator
关键词：Dilworth定理，二分图匹配
算法简述
这个题目模型非常显然，就是要求一个最大的点集使得点集中任意两点在DAG中不可达。这是一个经典的问题，就是求这张DAG的最长反链。这个只要对DAG求传递闭包后计算最小链覆盖即可，求DAG最小链覆盖是个更加经典的问题，就不赘述了。
一点点小代码
int a[100][100];
int link[100];
bool vis[100];
int n;
int find(int x) { //匈牙利算法
REP(i, 0, n - 1) if (vis[i] && a[x][i]){
vis[i] = 0;
if (link[i] == -1 || find(link[i])) {
link[i] = x;
return true;
}
}
return false;
}
class Incubator {
public:
int maxMagicalGirls(vector<string> love) {
CL(a, 0);
n = love.size();
REP(i, 0, n - 1) REP(j, 0, n - 1) a[i][j] = (love[i][j] == 'Y');
REP(k, 0, n - 1)
REP(i, 0, n - 1)
REP(j, 0, n - 2) a[i][j] |= (a[i][k] & a[k][j]);//对DAG求传递闭包，这是应用Dilworth定理非常重要的一步
CL(link, 0xff);
int match = 0;
REP(i, 0, n - 1) {
CL(vis, 1);
match += find(i);
}
return n - match; //DAG传递闭包的最小链覆盖等于点数 - 最大匹配
}
};
XorAndSum
关键词：异或方程组、贪心
题目简述
给你个数，你可以进行若干次操作，每次操作有如下两步：
- 选择两个数
- 将保持不变，并将替换为
其中为异或运算。
你可以进行若干次操作，使得最终个数之和尽可能大。
算法简述
熟悉异或方程组的话，就能一眼看出来，这个题目就是给定了一组线性基，要你求个和最大数，且这些数组成的线性基等价于它。这个问题就分为两步，第一步就是把这个线性基求出来，第二步就是求这个线性基能生成的最大的个数(其中是这个线性基的秩)。这个在求线性基的时候只要把每个数的最高位当成主元来消就可以了。这样消出来的线性基就可以用贪心的方法来求出最大的个数了。当然还有个小问题，如果秩小于怎么办，这种情况只要把多出来的那些数都定为这组基能产生的最大的数就可以了。
一点小代码
vector<LL> base; //线性基
LL highbit(LL x) {
for (int i = 60; i >= 0; --i) if (x & (1LL << i)) return (1LL << i); //计算最高位
}
void add(LL x) { //往线性基里加元素
for (int i = 0; i < base.size(); ++i) {
LL p = highbit(base[i]);
if (x & p) x ^= base[i];
}
if (!x) return;
LL p = highbit(x);
for (int i = 0; i < base.size(); ++i) {
if (base[i] & p) base[i] ^= x;
}
base.PB(x);
}
class XorAndSum {
public:
long long maxSum(vector<long long> number) {
base.clear();
int n = number.size();
REP(i, 0, n - 1) add(number[i]);
LL sum = 0, ans = 0;
int m = base.size();
REP(i, 0, m - 1) sum ^= base[i];
ans = sum * (n - m + 1); //对于超出线性基秩的部分 全都取最大的
sort(base.begin(), base.end());
REP(i, 0, m - 2) ans += (sum ^ base[i]); //贪心地选择最优的
return ans;
}
};
over 6 years ago
嘟噜噜... 还有一个月就NOIP了，AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧
简单写点弱鸡题解， 第一是督促一下作业进度，第二呢也可以来熟悉一下输入法。岂不是很妙。
ICPCBalloons
关键词：枚举、贪心。
算法简述
因为大小气球之间不能切换，所以每个题目都要去确定用大气球还是小气球。这里就是一个指数的枚举就行了。之后判断可不可行就是一个贪心的问题了。把两个集合的元素都按照大小排序，然后调整一下就好了。
一点点小代码
vector<int> L, M; //尺寸为L的气球和M的气球
vector<int> A; // A题的人数
int calc(vector<int> A, vector<int> B) { //计算 A与B两个集合要符合条件的最小代价
int sa = 0, sb = 0;
for (int i = 0; i < A.size(); ++i) sa += A[i];
for (int i = 0; i < B.size(); ++i) sb += B[i];
if (sb > sa) return -1;
int sum = 0;
for (int i = 0; i < B.size(); ++i) {
int x = 0; if (i < A.size()) x = A[i]; //这里使用贪心的想法 把两个集合从小到大配对
if (x < B[i]) sum += B[i] - x;
}
return sum;
}
int check(int S) { //计算当选取大小气球的方案为S的时候的最小代价
vector<int> X, Y;
REP(i, 0, A.size() - 1) if (S & (1 << i)) X.PB(A[i]);
else Y.PB(A[i]);
sort(X.begin(), X.end(), greater<int>());
sort(Y.begin(), Y.end(), greater<int>());
int ans1 = calc(L, X), ans2 = calc(M, Y);
if (ans1 != -1 && ans2 != -1) return ans1 + ans2;
return -1;
}
class ICPCBalloons {
public:
int minRepaintings(vector<int> balloonCount, string balloonSize, vector<int> maxAccepted) {
L.clear(); M.clear();
A = maxAccepted;
for (int i = 0; i < balloonCount.size(); ++i) if (balloonSize[i] == 'L')
L.PB(balloonCount[i]);
else M.PB(balloonCount[i]);
sort(L.begin(), L.end(), greater<int>());
sort(M.begin(), M.end(), greater<int>());
int ans = -1;
REP(i, 0, (1 << A.size()) - 1) {//枚举每个题用大气球还是小气球
int x = check(i);
if (x != -1)
if (ans == -1 || x < ans) ans = x;
}
return ans;
}
};
CircleGame
关键词：简单几何、SG函数
算法简述
题目说了所有的圆只会相互包含，不会相交，所以就可以先把这个图形搞成树的结构。每次的操作就相当于选择树上的一个节点然后把这个点到根路径上的点全都删掉，谁不能删谁输。一看数据范围才50， 于是就可以直接算sg了。随便暴力就可以了。令为以为根的子树中进行博弈的sg。那么在计算的时候就可以枚举选择了哪个点，然后把这个点到的路径上的点删掉，递归下去求sg就好了。
一点点小代码
struct node {
int x, y, r;
}a[100];
bool operator < (const node &A, const node &B) {
return A.r < B.r;
}
int f[100], n;
int dist(int x, int y) { //计算距离
return (a[x].x - a[y].x) * (a[x].x - a[y].x) + (a[x].y - a[y].y) * (a[x].y - a[y].y);
}
bool inside(int x, int y) { //判断第x个圆是否在第y个圆内
return dist(x, y) <= a[y].r * a[y].r;
}
bool isanc(int x, int y) { //暴力判断x是否是y的祖先
if (!y) return false;
if (y == x) return true;
return isanc(x, f[y]);
}
int sg[100];
vector<int> ch[100];
int dp(int);
int mex(vector<int> A) { //计算mex
set<int> S;
for (int i = 0; i < A.size(); ++i) S.insert(A[i]);
REP(i, 0, 100) if (S.find(i) == S.end()) return i;
}
int rec(int x, int a) {//把选的点到根的链断开 分别计算新子树的sg
int last = 0;
int sum = 0;
while (f[a] != x) {
for (int i = 0; i < ch[x].size(); ++i) if (ch[x][i] != last) sum ^= dp(ch[x][i]);
last = x;
x = f[x];
}
return sum;
}
int dp(int a) { //记忆化搜索计算每棵树的sg值
if (sg[a] != -1) return sg[a];
vector<int> A;
REP(b, 1, n) if (isanc(a, b)) A.PB(rec(b, a));
return sg[a] = mex(A);
}
class CirclesGame {
public:
string whoCanWin(vector<int> x, vector<int> y, vector<int> r) {
n = x.size();
CL(sg, 0xff);
REP(i, 0, n - 1) a[i + 1].x = x[i], a[i + 1].y = y[i], a[i + 1].r = r[i];
CL(f, 0);
sort(a + 1, a + n + 1);
REP(i, 1, n) ch[i].clear();
REP(i, 1, n) REP(j, i + 1, n) if (inside(i, j)) { //把圆组成的树给构出来
f[i] = j;
ch[j].PB(i);
break;
}
int sg = 0;
REP(i, 1, n) if (!f[i]) {
sg ^= dp(i);//把所有树的根节点的SG值异或起来
}
if (sg) return "Alice";
else return "Bob";
}
};
Orienteering
关键词：最小割
题目简述
给你一棵个点的树，其中有不超过个特殊的点，现在从这些特殊的点中随机选出个点。任选一个起点和终点，在树上遍历完个点的最短路程是, 求的期望大小。
算法简述
首先要解决的问题是，如果给你了一些点，如何求遍历所有点的最小花费。
这个显然就是求出这些点的生成树，总花费就是这个生成树每条边长度的两倍减去这棵树直径。
由于期望是线性的，可以把这两部分分开来算。
- 计算生成树上的边的期望条数，这个只要对每条边计算其出现在生成树上概率即可。
- 计算生成树直径的期望，这个不是那么直观，可以先枚举树上直径的两个端点，计算其作为直径时的概率。因为一棵树可能有多个直径，我们同样还要限制这个直径是字典序最小的。那么其他点能够出现在树上有什么条件呢？实际上只要满足
$$|AB| \ge max \left( |AC|, |BC| \right)$$
这里还有一个小细节就是说，等号能不能取到。这里只要再去判一下字典序就可以了。
一点小代码
const int N = 2600;
int n, m; // 地图大小
int num; // Check Point 个数
int cp[N]; // 记录所有的Check Point
int id[51][51]; // 每个点的编号
char G[51][51]; //储存地图 . * #
int d[N][N]; //计算两点之间的最短路
double c1[N]; //C(i, K) / C(num, K)
double c2[N]; //C(i, K - 2) / C(num - 2, K - 2)
bool pd(int x, int y) { //判断(x,y)是否是合法的格子
return x < n && y < m && x >= 0 && y >= 0 && G[x][y] != '#';
}
void dfs(int x, int y, int *f, int d) { //计算从(x, y)出发到每个点的最短路
f[id[x][y]] = d;
if (pd(x + 1, y) && f[id[x + 1][y]] == -1) dfs(x + 1, y, f, d + 1);
if (pd(x - 1, y) && f[id[x - 1][y]] == -1) dfs(x - 1, y, f, d + 1);
if (pd(x, y + 1) && f[id[x][y + 1]] == -1) dfs(x, y + 1, f, d + 1);
if (pd(x, y - 1) && f[id[x][y - 1]] == -1) dfs(x, y - 1, f, d + 1);
}
bool check(int i, int j, int k) { //计算加入点k是否会影响直径i j的合法性
int da = d[cp[i]][cp[j]], db = d[cp[i]][cp[k]], dc = d[cp[k]][cp[j]];
return (da > db || (da == db && k > j)) && (da > dc || (da == dc && k > i));
}
class Orienteering {
public:
double expectedLength(vector<string> field, int K) {
CL(d, 0xff);
n = field.size(); m = field[0].size();
num = 0;
int tot = 0;
REP(i, 0, n - 1)
REP(j, 0, m - 1) {
id[i][j] = ++tot;
G[i][j] = field[i][j];
if (G[i][j] == '*') cp[++num] = tot;
}
c1[num] = 1;
PER(i, num - 1, 0) c1[i] = c1[i + 1] / (i + 1) * (i + 1 - K); // 计算系数1
c2[num - 2] = 1;
PER(i, num - 3, 0) c2[i] = c2[i + 1] / (i + 1) * (i - K + 3); // 计算系数2
REP(i, 0, n - 1) REP(j, 0, m - 1) dfs(i, j, d[id[i][j]], 0);
double ans = 0;
REP(i, 1, tot - 1)
REP(j, i + 1, tot) if (d[i][j] == 1) { //枚举每条树边
int x = 0; // 在一侧的Check Point个数
REP(k, 1, num) if (d[i][cp[k]] <= d[j][cp[k]]) ++x;
ans += 2.0 * (1.0 - c1[x] - c1[num - x]);
}
REP(i, 1, num - 1)
REP(j, i + 1, num) { //枚举 cp[i], cp[j] 作为直径
int x = 0; // 符合条件的k的个数
int dia = d[cp[i]][cp[j]]; //直径长度
REP(k, 1, num) if (check(i, j, k)) ++x;
ans -= c2[x] * dia * K * (K - 1) / num / (num - 1);
}
return ans;
}
};
over 6 years ago
嘟噜噜... 还有一个月就NOIP了，AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧
简单写点弱鸡题解， 第一是督促一下作业进度，第二呢也可以来熟悉一下输入法。岂不是很妙。
Stamp
关键词：枚举、动态规划。
题目简述
给你一个长度为的空白的纸带，再给你一个目标带，每个位置可能是R、G、B三种颜色的一种，或者是一个*，代表这里可以是任意颜色。为了完成目标，你需要先确定一个长度L，然后进行若干次染色操作，每次你可以选择一个颜色C以及一段长度为L的区间，将其全部染成C，同时这个操作还需要保证这个区间在染色之前不存在除了C以外的颜色。假定你进行了K次操作，那么总花费就是， 求最小花费。 。
算法简述
这个题显然就是先去枚举L，然后判断L是否可行，这里不知道是不是可以用贪心，我是用一个很暴力的DP来解决的。令代表前i个位置都涂好了，其中最近一次染的区间是,所用颜色是的最小花费。直接暴力转移就可以了。这个做法比较直接和暴力。
一点点小代码
bool check(int l, int r, int c) {
REP(i, l, r) {
if (a[i] == -1) continue;
if (a[i] != c) return false;
}
return true;
}
int dp(int L) {
REP(i, 1, n) REP(j, 0, 2) f[i][j] = 1000;
REP(i, L, n) {
REP(j, 0, 2) {
if (!check(i - L + 1, i, j)) continue;
REP(k, 0, 2)
getmin(&f[i][j], f[i - L][k] + 1);
REP(k, i - L + 1, i - 1) getmin(&f[i][j], f[k][j] + 1);
}
}
return min(min(f[n][0], f[n][1]), f[n][2]);
}
class Stamp
{
public:
int getMinimumCost(string desiredColor, int stampCost, int pushCost)
{
map<char, int> S;
S['*'] = -1;
S['R'] = 1;
S['G'] = 2;
S['B'] = 0;
n = desiredColor.size();
REP(i, 1, n) a[i] = S[desiredColor[i - 1]];
int ans = 1e9;
REP(i, 1, n) {
int x = dp(i);
if (x != -1) getmin(&ans, i * stampCost + x * pushCost);
}
return ans;
}
};
Ear
关键词：几何，枚举、小学数学
题目简述
在坐标系上有一些红点和一些蓝点，其中红点都在X轴上，蓝点都在X轴上方。对于一个由4个红点(A B C D)和两个蓝点(P, Q)组成的集合，我们定义它为"Ear"当且仅当它们满足下面的条件：
- B, C严格在线段AD内。
- P点在X轴上的投影严格在AD内，Q点在Y轴上的投影严格在BC内。
- Q点严格在三角形PAD内。
（脑补一下这个就是个耳朵，例如下图：
现在给你一些红点和蓝点，求总共有多少只"Ear"。
算法简述
类似这样的几何计数题，首先要确定枚举的对象。相对来说P和Q这两个点的限制比较复杂（要求Q在三角形内），那么就先把P、Q两个点先枚举一下，然后再枚举D点。看看现在哪些东西是已经确定下来了。首先这个C点的位置就已经确定下来了，C只有可能在Q投影和D之间，而且C点的位置不受A B影响（因为A B两个点都在Q的投影左侧）。接下来考虑A点的位置，因为有个限制是Q在三角形PAD之内，所以A点一定在直线PQ与X轴交点的左侧。需要注意的是，A点还有一个限制就是A要在P点投影的左侧。接下来B的位置就简单了，B一定在A点和Q点投影之间。现在就可以计算数量了，一个等差数列求和就行啦。
一点点小代码
string X, Y, Z;
stringstream F;
const int N = 310;
int rx[N], bx[N], by[N];// 红的X坐标以及蓝的坐标
int n;
int area(int x1, int y1, int x2, int y2) { // 计算叉积
return x1 * y2 - x2 * y1;
}
int findL(int a) { // 计算第a个蓝点在X轴投影左侧最近的一个红点
REP(i, 1, n) if (rx[i] >= bx[a]) return i - 1;
return n;
}
int findR(int a) { // 计算第a个蓝点在X轴投影右侧最近的一个红点
PER(i, n, 1) if (rx[i] <= bx[a]) return i + 1;
return 1;
}
int intersect (int a, int b) { //计算第a个蓝点和第b个蓝点所成直线在X轴上的截距
REP(i, 1, n) if (rx[i] >= bx[a] || area(bx[a] - rx[i], by[a], bx[b] - rx[i], by[b]) <= 0) return i - 1;
return 0;
}
class Ear {
public:
long long getCount(vector<string> redX, vector<string> blueX, vector<string> blueY) {
int m = 0, t;
{ // 先处理一下格式
X = Y = Z = "";
for (int i = 0; i < redX.size(); ++i) X += redX[i];
for (int i = 0; i < blueX.size(); ++i) Y += blueX[i];
for (int i = 0; i < blueY.size(); ++i) Z += blueY[i];
F.clear();
F << X;
n = 0;
while (F >> t) rx[++n] = t;
F.clear();
F << Y;
while (F >> t) bx[++m] = t;
F.clear();
F << Z;
m = 0;
while (F >> t) by[++m] = t;
}
sort(rx + 1, rx + n + 1);// 对红点坐标排序
LL ans = 0;
REP(P, 1, m) // 枚举P点
REP(Q, 1, m) { // 枚举Q点
if (by[Q] >= by[P]) continue;
int RA = min(intersect(Q, P), findL(P)); //A点可行的范围
int RB = findL(Q); // B点可行的范围
int LC = findR(Q); // C点可行的范围
REP(D, 1, n) { //枚举D点
if (bx[Q] >= rx[D] || bx[P] >= rx[D]) continue; //P Q点要在D点左侧
if (area(bx[Q] - rx[D], by[Q], bx[P] - rx[D], by[P]) >= 0) continue; //Q要在PD左侧
int a1 = RB - RA;
int num = RA;
ans += (2LL * a1 + num - 1) * num * (D - LC) / 2; //等差数列求和
}
}
return ans;
}
};
Surrounding Game
关键词：最小割
题目简述
一个人在一个棋盘上玩游戏，想要占领一个格子有两个方法：
- 在这个格子放一个棋子。
- 这个格子周围(四联通)的格子中都有棋子。
在中放棋子需要花费，占领能获得。求一种放置棋子的方法，使得总收益(收益 - 花费)最大。
算法简述
这种题一看就是个网络流的模型。这个最小割的构图还是比较妙的。
首先把图黑白染色，就构成了一个二分图。然后把每个点都拆成两个，左边的点拆成，到连一条容量为的边，到连一条容量为的边。右边的点如法炮制，拆成, , 之间连一条的边，到连的边。
既然已经把两边的边都连好了，那么就可以来连中间的边了，对于每一对相邻的点，我们在和之间都连上一条的边。这样来跑个最小割，用总收益减去最小割就是答案了。
那么这个构图为什么是对的呢。考虑保留每一个收益的话需要割掉哪些边，发现这个条件正好和题目要求的条件相同：
- 把这个格子的花费边割掉
- 把这个格子相邻的格子的花费边割掉
一点小代码
void addadj(int x, int y) { // 给相邻的点连边
if (x) ae(id[x][y] * 2 - 1, id[x - 1][y] * 2, inf), ae(id[x][y] * 2, id[x - 1][y] * 2 - 1, inf);
if (y) ae(id[x][y] * 2 - 1, id[x][y - 1] * 2, inf), ae(id[x][y] * 2, id[x][y - 1] * 2 - 1, inf);
if (x < n - 1) ae(id[x][y] * 2 - 1, id[x + 1][y] * 2, inf), ae(id[x][y] * 2, id[x + 1][y] * 2 - 1, inf);
if (y < m - 1) ae(id[x][y] * 2 - 1, id[x][y + 1] * 2, inf), ae(id[x][y] * 2, id[x][y + 1] * 2 - 1, inf);
}
class SurroundingGame {
public:
int maxScore(vector<string> cost, vector<string> benefit) {
CL(head, 0);
cnt = 1;
n = cost.size(), m = cost[0].size();
int tot = 0;
REP(i, 0, n - 1)
REP(j, 0, m - 1) id[i][j] = ++tot; //给网格中所有点标号
s = 2 * tot + 1; t = s + 1;// 设置源点和汇点
int sum = 0;
REP(i, 0, n - 1) REP(j, 0, m - 1) sum += val(benefit[i][j]);
REP(i, 0, n - 1) //建图
REP(j, 0, m - 1)
if ((i & 1) ^ (j & 1)) ae(s, 2 * id[i][j] - 1, val(cost[i][j])),
ae(2 * id[i][j] - 1, 2 * id[i][j], val(benefit[i][j])), addadj(i, j);
else ae(2 * id[i][j] - 1, t, val(cost[i][j])),
ae(2 * id[i][j], 2 * id[i][j] - 1, val(benefit[i][j]));
return sum - dinic();
}
};
over 6 years ago
over 6 years ago
about 7 years ago
