PPFish de OI

勿在浮沙筑高台。

[ppfishoi-blog]

博客已搬迁。

http://pppfish.com

虽然没什么人看0 0 但是还是发一下。

这里不会更新了。

[ppfishoi-blog]

[Codeforces #120(Div. 2)]  E. Counter Attack

题目大意

给你一张反图N个点M条边，（N，M <= 2 * 10 ^ 5），图上存在的边实际上不存在，图上不存在的边实际上存在。

求图的联通块个数以及每个联通块中的点。

分析

从反面考虑。我们对于一个点，把那些没有连“反边”的点加入到和他的同一个联通块中。O(n)把所有点遍历一遍。

最后剩下的联通块大概就只有几千个了。我们遍历所有的边，把u和v对应的联通块的Link[x][y]++，如果Link[x][y] = size[x] * size[y]，说明x和y这个联通块不相连了。最后输出即可。

#include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int maxn = 500005; const int maxl = 3005; int n, m; int sz = 0; int size[maxl]; struct Unionset { int p[maxl], sz_all; int sz_[maxl]; void init() { for (register int i = 1; i <= sz; i++) { p[i] = i; } sz_all = sz; } int find(int x) { if (p[x] == x) return x; else return p[x] = find(p[x]); } void Union(int x, int y) { int t1 = find(x), t2 = find(y); if (t1 != t2) { p[t1] = t2; sz_all --; } } }; Unionset us; int link[3005][3005]; int parent[maxn]; bool vis[maxn], vs[maxn]; vector<int> g[maxn]; vector<int> t[maxn]; vector<int> cng; vector<pair<int, int> > edge; void input() { int x, y; scanf("%d%d", &n, &m); for (register int i = 1; i <= m; i++) { scanf("%d%d", &x, &y); edge.push_back(make_pair(x, y)); g[x].push_back(y); g[y].push_back(x); } } void solve() { for (register int i = 1; i <= n; i++) { if (!vis[i]) { sz ++; size[sz] = 0; memset(vs, false, sizeof(vs)); for (register int j = 0; j < g[i].size(); j++) { vs[g[i][j]] = true; } for (register int j = 1; j <= n; j++) { if (!vs[j] && !vis[j]) { t[sz].push_back(j); vis[j] = true; size[sz] ++; parent[j] = sz; } } } } for (register int i = 0; i < edge.size(); i++) { int x = parent[edge[i].first], y = parent[edge[i].second]; link[x][y] ++; link[y][x] ++; } us.init(); for (register int i = 1; i <= sz; i++) { for (register int j = i + 1; j <= sz; j++) { if (link[i][j] != size[i] * size[j]) { us.Union(i, j); } } } printf("%d\n", us.sz_all); memset(vis, false, sizeof(vis)); for (register int i = 1; i <= sz; i++) { if (!vis[i]) { int cn = 0; for (register int j = 1; j <= sz; j++) { if (us.find(j) == us.find(i)) { vis[j] = true; cn += size[j]; } } printf("%d ", cn); for (register int j = 1; j <= sz; j++) { if (us.find(j) == us.find(i)) { for (register int k = 0; k < t[j].size(); k++) { printf("%d ", t[j][k]); } } } printf("\n"); } } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif input(); solve(); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

[ppfishoi-blog]

Codeforces #310 (Div. 2)

A. Case of the Zeros and Ones

给定一个长度小于2 * 10 ^ 5的01串，每一次操作可以把一对相邻的01删除，问到不能操作时最短的串长度。

分析

统计串中0个数x和1个数y，答案为len - min(x, y) * 2

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 200005; int n; char s[maxn]; void input() { scanf("%d", &n); scanf("%s", s); } void solve() { int l = 0, r = 0; int len = strlen(s); for (register int i = 0; i < len; i++) { if (s[i] == '0') { l ++; } else { r ++; } } int ans = len - 2 * min(l, r); printf("%d\n", ans); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif input(); solve(); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

B. Case of Fake Numbers

给定n (n <= 1000)，有n个转轮，每个转轮上有0 ... n - 1这n个齿。每次顺时针转动第奇数个转轮(+1)，逆时针转动第偶数个转轮(-1)，问可不可以达到0 ... N - 1这样的状态？

分析

每n次是一个循环，模拟即可。

#include <cstdio> #include <algorithm> using namespace std; const int maxn = 1005; int n, a[maxn]; void input() { scanf("%d", &n); for (register int i = 1; i <= n; i++) { scanf("%d", &a[i]); } } void solve() { int cn = 0; bool flag = true; while (flag) { for (register int i = 1; i <= n; i++) { if (i & 1) { a[i] ++; if (a[i] == n) a[i] = 0; } else { a[i] --; if (a[i] == -1) a[i] = n - 1; } } flag = false; for (register int i = 2; i <= n; i++) { if (a[i] - 1 != a[i - 1]) { flag = true; break; } } cn ++; if (cn >= 9000) break; } if (flag) printf("No\n"); else printf("Yes\n"); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif input(); solve(); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

C. Case of Matryoshkas

有n个套娃，规定两种操作

1. 一种是把一个（或者一堆）套娃放到另外一个套娃里面，这个套娃不能被其他的套娃套住

2. 把一个套娃打开，取出它之中套娃

给定一开始的套娃状态，每一堆的嵌套关系，求把套娃恢复到从大往小套住的最少操作次数。

分析

可以发现，我们想尽量少套的话，就是尽量利用“已经套好且顺序符合要求的”被其他套住。但是显然，如果只要套娃里面有一个顺序不对，那么就要全部拆开。

对于N个套住的套娃，全部拆开要N - 1次。

那么我们对输入的数据，找到编号为1的套娃所在的组，看是否有类似1, 2, ... K这样连续被套住的套娃出现，如果有，那么这就是唯一一堆不用被拆开的。

其他的每一堆都要全部拆开，因为套其他的套娃的时候外面不能有套娃覆盖。

时间复杂度O (K)

#include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100005; int n, k; vector<int> g[maxn]; void input() { int x, y; scanf("%d%d", &n, &k); for (register int i = 1; i <= k; i++) { scanf("%d", &x); for (register int j = 1; j <= x; j++) { scanf("%d", &y); g[i].push_back(y); } } } void solve() { int ans = 0, cn = 1; for (register int i = 1; i <= k; i++) { if (g[i][0] != 1) { ans += g[i].size() - 1; } else { for (cn = 1; cn < g[i].size(); cn++) { if (g[i][cn] - 1 != g[i][cn - 1]) break; } ans += g[i].size() - cn; } } ans += n - cn; printf("%d\n", ans); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif input(); solve(); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

D. Case of Fugitive

有n个岛，第i个岛的范围是[li, ri]，保证li > ri-1，有m座桥，每座桥的长度为a[i]。一座桥可以架在岛i 和 i + 1之间当且仅当a[i] ∈ [li + 1 - ri, ri + 1 - li]，问是否可以在每两座相邻的岛之间都架设一座桥。

分析

把问题转换一下，实际上就是有m个数和n - 1个区间，问是否存在一一对应的关系。

其实二分图可以做的但是n特别大。显然不行，只能贪心。

我们先把区间按左端点从小到大双关键字排序，然后把a从小到大排序。

建立一个区间的堆，排序方式为按右端点从小到大排序。

遍历a数组，对当前的a[i]，我们把所有的左端点小于a[i]的区间全部扔进堆中，然后取出堆顶，也就是右端点最小的区间。如果当前的a[i]比这个右端点大，那么这个区间是没有答案的。因为a已经从小到大排序，显然。把a数组遍历完，统计最后

在这里我用set实现的。注意如果用set的话，区间不能忽略idx的排序，否则就不能存下重复的区间啦。

#include <set> #include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> #include <functional> using namespace std; const int maxn = 200005; int n, m; pair<long long, long long> island[maxn]; pair<long long, int> a[maxn]; struct data { long long l, r; int idx; bool operator < (const data& rhs) const { return make_pair(make_pair(r, l), idx) < make_pair(make_pair(rhs.r, rhs.l), rhs.idx); } }; bool cmp(const data& lhs, const data& rhs) { if (lhs.l == rhs.l) return lhs.r < rhs.r; else return lhs.l < rhs.l; } data g[maxn]; void input() { cin >> n >> m; for (register int i = 1; i <= n; i++) { cin >> island[i].first >> island[i].second; } for (register int i = 1; i <= m; i++) { cin >> a[i].first; a[i].second = i; } for (register int i = 2; i <= n; i++) { g[i - 1].l = island[i].first - island[i - 1].second; g[i - 1].r = island[i].second - island[i - 1].first; g[i - 1].idx = i - 1; } } int ans[maxn]; set<data> AnsSet; void solve() { sort(g + 1, g + n, cmp); sort(a + 1, a + m + 1); memset(ans, -1, sizeof(ans)); if (n - 1 > m) { printf("No\n"); return; } int cn = 1, cn_i = 0; for (register int i = 1; i <= m; i++) { while (cn < n && g[cn].l <= a[i].first) { AnsSet.insert(g[cn]); cn ++; } if (!AnsSet.empty()) { set<data>::iterator it = AnsSet.begin(); if (it->r >= a[i].first) { ans[it->idx] = a[i].second; AnsSet.erase(it); cn_i ++; } else { printf("No\n"); return; } } } if (cn_i == n - 1) { printf("Yes\n"); for (register int i = 1; i < n; i++) { printf("%d ", ans[i]); } } else { printf("No\n"); } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif input(); solve(); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

但是很可惜最后unrated了。呵呵

[ppfishoi-blog]

[SGU189] Perl-like Substr

题目大意

        一个小型俄罗斯公司H&H决定冲击国际社会以完善他们自己的脚本语言。你被雇佣来参与完成这个工程，你的任务非常简单——码出“子串”的功能部分。

        “子串”功能要用到一下几种操作：

        $value= substr($string, begin, count);

        $value= substr($string, begin);

        substr($string,begin, count) = $newstring;

        substr($string,begin) = $newstring;

        $string(‘$’是一个变量的前缀)表示原本的串。begin表示子串的开头:如果begin>=0，表示左数第begin个(以0为第一个)，begin<0代表右数第begin个(以-1为第一个)。count表示子串的长度，如果count>0,表示从begin开始count个字符，如果count<0，表示从begin开始数除了最后-count个字符其他都属于子串。count不等于0。

        “substr”除了可以取出子串，还可以将子串代替为其他的新串。

输入格式：

        第一行包括两个自然数N(1<=N<=20)——代表初始化有N行和M(1<=M<=300)——输入u余下有M行。接下来的N行表示变量的初始化(没有一行长度>=10000),以如下形式：

        $name= “value”;

name是变量的名称(总是有一个前缀$)，由最多20个字母/数字组成。接下来是一个‘=’号，在接下来是变量的内容value，用一对“”括起来，内容由字母/数字/空格/逗号/点/连字符/下划线/冒号/叹号/问号组成。value的长度不大于255，$name,”=”,”value”之间可以有若干个空格。行末以分号结尾。

接下来的M行包括如下6种操作：

1.      print($name);输出变量name的内容；

2.      print(substr($name, begin,count));输出子串的内容；

3.      $name1 = $name2;将name2的内容赋给变量name1；

4.      $name1 = substr($name2, begin,end);将子串的内容赋给name1；

5.      substr($name1, begin1, count1)= substr($name2, begin2, count2);将前一段子串的内容替换成后一段子串的内容；

6.      substr($name1, begin1, count1)= $name2;用后一个变量的内容代替前一段子串。

        变量名和类似print,substr这样的操作名中不包含空格，其他任何地方都有可能有若干个空格。每行以分号结尾，每一行长度不超过255。后面M行中出现的在前N行中没有定义过的变量同一视作空串””。输入中变量个数不大于100。在操作过程中，每个变量的内容长度不超过1000。

        substr取得的子串保证不为空。

        变量名区分大小写。

输出格式：

        输出程序的运行结果，每一行对应一个print()操作。输出不允许添加额外的字符。

分析

TM怎么又是字符串处理我日了狗。

用map来保存每个变量，用string的substr函数来处理大部分操作。

记得随时吞空格。

#include <map> #include <ctime> #include <cstring> #include <iostream> #include <cstdio> #include <string> #include <algorithm> using namespace std; const int maxl = 20005; const int inf = 0x3f3f3f3f; int n, m; map<string, string> vari; string clr(string cn) { int l = 0, r = cn.size() - 1; while (cn[l] == ' ' || cn[l] == ';') l++; while (r > 0 && cn[r] == ' ' || cn[r] == ';') r--; return cn.substr(l, r - l + 1); } void input() { static char nm[maxl], vl[maxl]; static string nm_s, vl_s; scanf("%d%d\n", &n, &m); for (register int i = 1; i <= n; i++) { scanf("%[^=]s", nm); nm_s = nm, nm_s = clr(nm_s); getchar(); gets(vl); vl_s = vl, vl_s = clr(vl_s); vari[nm_s] = vl_s.substr(1, vl_s.size() - 2); } } int Read(string& str) { int x, f = 1, cn = 0; while (str[cn] < '0' || str[cn] > '9') { if (str[cn] == '-') f = -1; cn ++; } x = 0; while (str[cn] >= '0' && str[cn] <= '9') { x = x * 10 + str[cn] - '0'; cn ++; } return x * f; } string Substr(string str, int& x, int& y) { int cn = 0, ed; string cn_s, ret; while (str[cn - 1] != '(') cn ++; while (str[cn] == ' ') cn ++; cn_s = str.substr(cn, str.size() - cn), cn = 0; while (cn_s[cn] != ',') cn ++; ret = clr(cn_s.substr(0, cn)); while (cn_s[cn] == ' ' || cn_s[cn] == ',') cn ++; cn_s = cn_s.substr(cn, cn_s.size() - cn), cn = 0; while (cn < cn_s.size()) { if (cn_s[cn] == ',' || cn_s[cn] == ')') break; else cn ++; } x = Read(cn_s); if (x < 0) x = vari[ret].size() + x; if (cn_s[cn] == ')') return ret; cn ++; cn_s = clr(cn_s.substr(cn, cn_s.size() - cn)); y = Read(cn_s); if (y < 0) y = vari[ret].size() - x + y; return ret; } string get_s(string variname) { if (variname[0] == '$') return vari[variname]; else { int x, y = inf; string ret = Substr(variname, x, y); // cout << ret << " " << x << " " << y << endl; return vari[ret].substr(x, y); } } void solve() { int l, r; string cn_s, en_s; char cn, s[maxl]; for (register int i = 1; i <= m; i++) { cn = ' '; while (cn == ' ') cn = getchar(); if (cn == 'p' || cn == 'P') { scanf("%[^(]s", s), getchar(); gets(s); r = strlen(s) - 1; while (s[r] != ')') r --; cn_s = s, cn_s = clr(cn_s.substr(0, r)); cout << get_s(cn_s) << endl; } else if (cn == '$') { scanf("%[^=]s", s), getchar(); cn_s = "$"; cn_s += s; cn_s = clr(cn_s); gets(s); en_s = s; en_s = clr(en_s); vari[cn_s] = get_s(en_s); } else if (cn == 's' || cn == 'S') { scanf("%[^=]s", s), getchar(); cn_s = 's'; cn_s += s; cn_s = clr(cn_s); gets(s); en_s = s; en_s = clr(en_s); l = r = inf; string s1 = Substr(cn_s, l, r), s2 = get_s(en_s); string& res = vari[s1]; res.replace(l, r, s2); } } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif input(); solve(); fprintf(stderr, "%.3lf s\n", (double) clock() / CLOCKS_PER_SEC); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

[ppfishoi-blog]

[SGU188]  Factory Guard

题目大意

就是一大堆人围着一个0 ... 999的圆绕圈，每一分钟走v，相向而行相遇了（不一定是整点）就ask a question，问每个人ask的次数

分析

模拟即可。

对于一个正向行走和一个逆向行走的，我们分正向行走的是否经过0点来判断。

#include <cstdio> #include <algorithm> using namespace std; const int maxn = 25; const int len = 1000; int n, t; int l[maxn], pr[maxn], v[maxn]; int ans[maxn]; void input() { scanf("%d%d", &n, &t); for (register int i = 1; i <= n; i++) { scanf("%d", &l[i]); } for (register int i = 1; i <= n; i++) { scanf("%d", &v[i]); } } void solve() { for (register int k = 1; k <= t; k++) { for (register int i = 1; i <= n; i++) { pr[i] = l[i]; l[i] += v[i]; } for (register int i = 1; i <= n; i++) { for (register int j = 1; j <= n; j++) { if (v[i] > 0 && v[j] < 0) { if (pr[i] < pr[j] && l[i] >= l[j]) { ans[i] ++; ans[j] ++; } else if (pr[i] > pr[j] && l[i] - len >= l[j]) { ans[i] ++, ans[j] ++; } } } } for (register int i = 1; i <= n; i++) { l[i] = (l[i] + len) % len; } } for (register int i = 1; i <= n; i++) { printf("%d ", ans[i]); } printf("\n"); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif input(); solve(); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

[ppfishoi-blog]

[POJ1741] Tree

题目大意

给出一个N <= 10000的，求树中Dist(X, Y) <= K的点对(X, Y)个数

分析

经典的树分治。

我们把整个树根据重心来分成子树处理，根据重心的性质，树的个数是O(Log N)

因为这棵树的子树会递归的进行处理，路径经过子节点的会在接下来的递归中计算到，所以我们只要路径经过当前根节点的点对(X, Y)。

对于当前根节点为T的子树，我们统计每个节点到根的深度Depth(i)，那么满足条件的点对个数为：

| (x, y), Depth(x) + Depth(y) <= K && Lca(x, y) == T |

= | (x, y), Depth(x) + Depth(y) <= K | - | (x, y), Depth(x) + Depth(y) <= K && Lca(x, y) != T |

我们把所有点的Depth按照大小排序，可以用O(n)的方法求出这些个数，具体方法是，对排序后的Depth数组设立左端点和右端点两个指针L, R，如果当前的Depth(L) + Depth(R) <= K，那么答案增加R - L，L右移一位，否则R左移一位，直到L == R为止。

最后复杂度 O(N Log^2 N)

#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int maxn = 10005; const int maxm = 20005; const int inf = 0x3f3f3f3f; int n, k; void Read(int& x) { char t = getchar(); while (t < '0' || t > '9') t = getchar(); x = 0; while (t >= '0' && t <= '9') { x = (x << 3) + (x << 1) + t - '0'; t = getchar(); } } struct Graph { int dep[maxn], top; bool vis[maxn]; int fst[maxn], _index; int size[maxn], f[maxn], p[maxn]; int u[maxm], v[maxm], w[maxm], nxt[maxm]; void Init() { _index = -1; memset(fst, -1, sizeof(fst)); memset(vis, false, sizeof(vis)); } inline void addedge(int x, int y, int _w) { _index ++; u[_index] = x, v[_index] = y, w[_index] = _w; nxt[_index] = fst[x]; fst[x] = _index; } void Centroid(int cnt, int pre, int& ret, const int sum) { int Max = 0; size[cnt] = 1; for (register int i = fst[cnt]; i != -1; i = nxt[i]) { if (v[i] != pre && !vis[v[i]]) { Centroid(v[i], cnt, ret, sum); size[cnt] += size[v[i]]; if (size[v[i]] > size[Max]) { Max = v[i]; } } } f[cnt] = max(size[Max], sum - size[cnt]); if (ret == -1 || f[ret] > f[cnt]) { ret = cnt; } } void getdep(int cnt, int pre, int depth) { dep[++top] = depth; for (register int i = fst[cnt]; i != -1; i = nxt[i]) { if (!vis[v[i]] && v[i] != pre) { getdep(v[i], cnt, depth + w[i]); } } } inline int calc(int cnt, int d) { int ret = 0; top = 0; getdep(cnt, 0, d); sort(dep + 1, dep + top + 1); int l = 1, r = top; while (r > l) { if (dep[l] + dep[r] <= k) { ret += r - l; l ++; } else { r --; } } return ret; } void Process(int cnt, int& ans) { int cn = -1; ans += calc(cnt, 0); vis[cnt] = true; for (register int i = fst[cnt]; i != -1; i = nxt[i]) { if (!vis[v[i]]) { cn = -1; ans -= calc(v[i], w[i]); Centroid(v[i], cnt, cn, size[v[i]]); Process(cn, ans); } } } }; Graph TreeGraph; void input() { TreeGraph.Init(); int x, y, v; for (register int i = 1; i <= n - 1; i++) { Read(x), Read(y), Read(v); TreeGraph.addedge(x, y, v); TreeGraph.addedge(y, x, v); } } void solve() { int ans = 0, cn; TreeGraph.Centroid(1, 0, cn, n); TreeGraph.Process(cn, ans); printf("%d\n", ans); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif while (scanf("%d%d", &n, &k) == 2) { if (n == 0 && k == 0) break; input(); solve(); } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

[ppfishoi-blog]

[SGU185] Two Shortest

题目大意

在一个N <= 400的无向图上输出两条不相交的最短路

分析

一开始试着先输出一条然后删除，再求一条。WA on Test 20

这样有可能第一条求出了这个图的某一条“割”，那么就求不出第二条最短路了。

我们把所有可能在最短路上的点建一个网络流，每条边的流量为1，如果最大流 >= 2，那么存在这样两条最短路，正确性显然。

输出的时候找那些流量为0的流，然后输出，再把这些流的流量设为1即可。

P.S. 注意Dinic的标号和当前流量优化，要不TLE成狗。

#include <cstdio> #include <queue> #include <cstring> #include <algorithm> using namespace std; const int maxn = 410; const int inf = 0x3f3f3f3f; int n, m; bool inq[maxn], Flag[maxn][maxn]; int q[maxn << 3], head, rear; int Src[maxn][maxn], Flow[maxn][maxn]; int Dis[maxn], Id[maxn]; inline void Read(int &x) { char t = getchar(); while (t < '0' || t > '9') t = getchar(); x = 0; while (t >= '0' && t <= '9') { x = (x << 3) + (x << 1) + t - '0'; t = getchar(); } } void input() { int x, y, w; scanf("%d%d", &n, &m); memset(Src, inf, sizeof(Src)); for (register int i = 1; i <= m; i++) { Read(x), Read(y), Read(w); Src[x][y] = Src[y][x] = w; } } void Spfa() { int cn; memset(inq, false, sizeof(inq)); memset(Dis, inf, sizeof(Dis)); head = 0, rear = -1; q[++rear] = 1; Dis[1] = 0; inq[1] = true; while (rear >= head) { cn = q[head]; head ++; for (register int i = 1; i <= n; i++) { if (Src[cn][i] != inf && Dis[i] > Dis[cn] + Src[cn][i]) { Dis[i] = Dis[cn] + Src[cn][i]; if (!inq[i]) { q[++rear] = i; inq[i] = true; } } } inq[cn] = false; } } bool Label() { int cn; memset(Id, -1, sizeof(Id)); head = 0, rear = -1; q[++rear] = n; Id[n] = 0; while (rear >= head) { cn = q[head]; for (register int i = 1; i <= n; i++) { if (Flow[i][cn] && Id[i] == -1) { Id[i] = Id[cn] + 1; q[++rear] = i; } } head ++; } return Id[1] != -1; } inline int Dinic(int cnt, int Max) { int ret = 0, cn; if (cnt == n || Max == 0) return Max; for (register int i = 1; i <= n; i++) { if (Flow[cnt][i] && Id[i] == Id[cnt] - 1) { cn = Dinic(i, min(Max, Flow[cnt][i])); Max -= cn; ret += cn; Flow[cnt][i] -= cn; Flow[i][cnt] += cn; if (Max == 0) break; } } Id[cnt] = -1; return ret; } inline void Prt(int cnt) { printf("%d", cnt); if (cnt == n) { putchar('\n'); return; } else { putchar(' '); } for (register int i = 1; i <= n; i++) { if (Flag[cnt][i] && !Flow[cnt][i]) { Flag[cnt][i] = Flag[i][cnt] = false; Flow[cnt][i] = Flow[i][cnt] = 1; Prt(i); return; } } } void BuildFlow() { for (register int i = 1; i <= n; i++) { for (register int j = 1; j <= n; j++) { if (i != j && Src[i][j] != inf && Dis[j] == Dis[i] + Src[i][j]) { Flow[i][j] = 1; Flag[i][j] = true; } } } } void solve() { int cnFlow = 0; Spfa(); BuildFlow(); while (Label()) { cnFlow += Dinic(1, inf); if (cnFlow >= 2) break; } if (cnFlow < 2) { printf("No solution\n"); } else { Prt(1); Prt(1); } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif input(); solve(); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

[ppfishoi-blog]

[SGU183] Painting the balls

题目大意

给你一串长度为n的球，对其中一些球进行染色，每一个球染色的代价为Ci，要保证每连续m个球中至少有两个球染色，求最小总代价。

分析

动态规划，F[i][j]代表最后一个染i，倒数第二个染i - j，且前面的全部满足要求的最小总代价

那么转移方程则是

F[i][j] = min{F[i - j][k] + C[i]} , j + k < m

保证不出现倒数第三个和最后一个中间长度超过m的情况

F[i][j] = min{F[i][j], F[i - j][0]} , i - 1 < m

序列前面几个的特殊情况。

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 10001; const int maxm = 101; const int inf = 0x3f3f3f3f; int n, m; short c[maxn]; int f[maxn][maxm]; void input() { scanf("%d%d", &n, &m); for (register int i = 1; i <= n; i++) { scanf("%d", &c[i]); } } void solve() { int ans = inf; memset(f, inf, sizeof(f)); for (register int i = 0; i <= m - 1; i++) f[i][0] = c[i]; for (register int i = 1; i <= n; i++) { for (register int j = 1; j <= m - 1; j++) { if (i - j < 0) break; for (register int k = 0; k <= m - 1; k++) { if (j + k > m || (k == 0 && i - 1 >= m)) continue; f[i][j] = min(f[i][j], f[i - j][k] + c[i]); } if (i - j >= n - m + 1) ans = min(ans, f[i][j]); } } printf("%d\n", ans); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif input(); solve(); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

[ppfishoi-blog]

[SGU182] Open the Brackets

题目大意

给出一个带括号的逻辑表达式，输出等效的不带括号的表达式

输入的表达式保证只有a到j这些字母，输入长度不超过2048，输出不能超过32768

分析

我们观察到字母个数少，那么枚举2^10种取值，对于使表达式结果为真的取值，我们按照这样的规律输出，对于一个字母x，在这个组合中的值如果为0，输出”!x”，否则输出”x”，字母间用&连接，不同的表达式间用||连接。

为什么可以呢？手推一个式子大概就明白了。因为每一个由&连接而成的表达式都是连在一起计算的，然后||的运算就不用多说了吧。

P.S

如果碰到了类似 b&!b 这样的式子显然是没有取值是可以让它为真的。那么在最后就得特判一下咯。否则PE on Test #3。

福利

送上gen.py一枚，帮我成功找到上述错误。

#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int maxl = 2049; const int q[9][9] = { {1, 1, 1, 1, 1, 1, 1, 1, 0}, // 0 ! {0, 0, 0, 0, 0, 0, 1, 1, 0}, // 1 || -> | {0, 1, 0, 1, 1, 1, 1, 1, 0}, // 2 & {0, 0, 0, 0, 0, 0, 1, 1, 0}, // 3 <=> -> = {0, 0, 0, 0, 0, 0, 1, 1, 0}, // 4 => -> > {0, 0, 0, 0, 0, 0, 1, 1, 0}, // 5 # {1, 1, 1, 1, 1, 1, 1, 1, 0}, // 6 ( {0, 0, 0, 0, 0, 0, 1, 1, 0}, // 7 ) {0, 0, 0, 0, 0, 0, 0, 0, 0} }; vector<char> g; bool vis[maxl]; int f[maxl]; int stn[maxl], sto[maxl], tn, to; char exp[maxl]; int calc(char *s) { int cn; tn = to = 0; for (register int i = 0; s[i]; i++) { if (s[i] >= 'a' && s[i] <= 'j') { stn[++tn] = f[s[i]]; } else { if (s[i] == '!') cn = 0; else if (s[i] == '|') cn = 1; else if (s[i] == '&') cn = 2; else if (s[i] == '=') cn = 3; else if (s[i] == '>') cn = 4; else if (s[i] == '#') cn = 5; else if (s[i] == '(') cn = 6; else if (s[i] == ')') cn = 7; else cn = 8; while (to && !q[cn][sto[to]]) { if (sto[to] == 0) { stn[tn] = 1 ^ stn[tn]; } else if (sto[to] == 1) { stn[tn - 1] = stn[tn] | stn[tn - 1]; tn --; } else if (sto[to] == 2) { stn[tn - 1] = stn[tn] & stn[tn - 1]; tn --; } else if (sto[to] == 3) { stn[tn - 1] = (stn[tn] == stn[tn - 1]); tn --; } else if (sto[to] == 4) { stn[tn - 1] = (stn[tn - 1] <= stn[tn]); tn --; } else if (sto[to] == 5) { stn[tn - 1] = stn[tn - 1] ^ stn[tn]; tn --; } to --; } if (cn == 7 && sto[to] == 6) to --; else sto[++to] = cn; } } return stn[tn]; } void input() { int cn = -1; scanf("%s", exp); for (register int i = 0; exp[i]; i++) { if (exp[i] >= 'a' && exp[i] <= 'j') { exp[++cn] = exp[i]; if (!vis[exp[i]]) { g.push_back(exp[i]); vis[exp[i]] = true; } } else if (exp[i] == '|' && exp[i + 1] == '|') { exp[++cn] = '|'; i ++; } else if (exp[i] == '<' && exp[i + 1] == '=' && exp[i + 2] == '>') { exp[++cn] = '='; i += 2; } else if (exp[i] == '=' && exp[i + 1] == '>') { exp[++cn] = '>'; i ++; } else { exp[++cn] = exp[i]; } } exp[cn + 1] = '.'; exp[cn + 2] = 0; sort(g.begin(), g.end()); } bool fst = true; void dfs(int cnt) { if (cnt == g.size()) { bool ret = calc(exp); if (ret) { if (!fst) { printf("||"); } for (register int i = 0; i < g.size(); i++) { if (!f[g[i]]) printf("!"); printf("%c", g[i]); if (i != g.size() - 1) printf("&"); } fst = false; } return; } f[g[cnt]] = 1; dfs(cnt + 1); f[g[cnt]] = 0; dfs(cnt + 1); } void solve() { dfs(0); if (fst) { for (register int i = 0; i < g.size(); i++) { printf("!%c&%c", g[i], g[i]); if (i != g.size() - 1) printf("||"); } } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif input(); solve(); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

from random import* f = open("input.txt", "w") len = randint(1, 100) In = 0 f.write('%c' % choice(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'])) for i in xrange(len): cn = choice(['&', '#', '||', '<=>', '=>', '!', '.']) if (cn == '.'): if In == 0: f.write('%s' % choice(['&', '#', '||', '<=>', '=>'])) f.write('(') In = 1 else: f.write(')') In = 0 f.write('!%c' % choice(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'])) elif (cn == '!'): f.write('%s' % choice(['&', '#', '||', '<=>', '=>'])) f.write('!%c' % choice(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'])) else: f.write('%s%c' % (cn, choice(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']))) if In == 1: f.write(')')

[ppfishoi-blog]

[Uva11691] Allergy Test

题目大意

作为一个志愿者，你将接受一个过敏症测试。测试的目标是检测出所有对你有刺激作用的过敏原。每一种过敏原有一个特定的D，表示你将持续D天产生过敏反应当且仅当你对这种过敏原过敏。过敏反应可以看做在你接触过敏原的一瞬间开始。测试的安排表上每天有两个事件。

1．在每天早上8点，你将接触至多一个过敏原。

2．在每天晚上8点，你将接受关于过敏反应的检测。

显然，假如你同时有因为两个以上的过敏原刺激产生的过敏反应，你是分辨不了关于它们的信息的。

在已经给定了每种过敏原的D值的条件下，你想用尽量少的天数结束这个实验——注意，实验计划不能临时改变，必须预先确定，也就是说你不能根据之前是否产生了过敏反应来决定之后是否安排接触过敏原。

分析

我们用二进制压缩状态，代表每一个过敏原是否检测过。

我们令F[s][k]代表s状态下，最后一个状态还持续药效的时间为k时的最小总时间。这个最小时间代表的是，最后一个过敏原的结束时间与倒数第二个结束时间的差值。

那么我们知道，我们必须给这最后一个过敏原留下至少一天的单独时间，否则这个过敏原不能被检测出来。

因此我们有这样的转移，对于当前状态st，且st & (1 << cn)，我们考虑将cn过敏原进行转移，对于f[st][j]，新的状态ed = st ^ (1 << cn)，那么

d[cn] < j 时，我们要尽量把cn放到左边，那么就是伸出来一天。

f[ed][1] = min(f[ed][1], f[st][j] + 1)

d[cn] > j 时，我们给最后一个过敏原留一天的暴露时间。

f[ed][d[cn] - j + 1] = min(f[ed][d[cn] - j + 1], f[cn][j] +  d[cn] - j + 1)

搞定！

P.S 考场分析题目特点，果断随机化AC

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxl = (1 << 20) + 5; const int maxk = 25; const int inf = 0x3f3f3f3f; int k, ans = inf, lm; int f[maxl][8], d[maxk]; void input() { scanf("%d", &k); lm = 1 << k; for (register int i = 1; i <= k; i++) { scanf("%d", &d[i]); } memset(f, inf, sizeof(f)); } void solve() { int cn; for (register int i = 1; i <= k; i++) { f[1 << (i - 1)][d[i]] = d[i]; } for (register int l = 0; l < lm; l++) { for (register int i = 1; i <= k; i++) { if (l & (1 << (i - 1))) continue; cn = l ^ (1 << (i - 1)); for (register int j = 1; j <= 7; j++) { if (f[l][j] != inf) { if (d[i] < j) { f[cn][1] = min(f[cn][1], f[l][j] + 1); } else { f[cn][d[i] - j + 1] = min(f[cn][d[i] - j + 1], f[l][j] + d[i] - j + 1); } } } } } ans = inf; for (register int i = 1; i <= 7; i++) { ans = min(ans, f[lm - 1][i]); } printf("%d\n", ans); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t --) { input(); solve(); } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

[ppfishoi-blog]

[SGU178] Golden Chain

题目大意

有个人估计是没钱了。手里有条金项链。

这条金项链由N根链组成，在这N天内，要保证每天都要付一根链，也可以在一天多付一些，然后用之前已经付出去的链来找零。

切割一次的意思是，如果在x的地方切割，就分成了长度为x - 1，1，n - x三段。

求最少切割几次，才能使这N天内每天都至少有一根链可以付出去。

e.g. 当N = 5时，将项链分成1，1，3三段，前两天把两个为1的付出去，第三天付3，然后将前面两天的两根1拿回来，后两天付这两根1的，满足要求。

分析

题目真不容易看懂啊。

对于样例，分成两段显然不行对吧。那么大概对这个题目有所体会了。我们要做的就是让这些分出的1的链“物尽其用”

设切割x次，每一次切割的地方不同（SB才会切一个地方），那么分成了2x + 1段。其中有x段长度为1的链。

那么前x天可以保证可以了。

对于第x + 1天，那么我们最好的方法就是在第x + 1天付出长度为x + 1的链，然后拿回来之前的x串长度为1的链。这样保证2x + 1天都满足要求（已经放了2x + 1条）

那么在2x + 2天放2x + 2条，拿回之前的2x + 1条，4x + 3天满足要求。

同理4x + 4天放4x + 4条，8x + 8天放8x + 8条。

那么就是切割x次，有x条1的链，x + 1条其他链，最多可以撑得天数是：

>>> x + 1 * (x + 1) + 2 * (x + 1) + 4 * (x + 1) ... + 2 ^ x * (x + 1)

等差数列求和对吧...

>>> x + (2 ^ (x + 1) - 1) * (x + 1)

>>> 2 ^ (x + 1) * (x + 1) - 1

枚举最小满足天数的x即可。

[ppfishoi-blog]

[SGU173] Coins

题目大意

存在一个长度为K - 1的向量A，对于一串连续的N个硬币Ci，选择从X开始的K个连续硬币，进行以下操作：

1. 将这K个硬币整体平移一位

2. 对于这K个硬币从1到K-1，如果Ci为1而且Ai为1，则将第K个硬币翻转一次。

题目给出N，M，K，L。

N代表硬币串长度，M代表操作次数，并给出了每次操作的K个硬币开始的硬币X和操作次数Di（1 <= Di <= 10 ^ 6）。

接下来还给出了L个长度为K的向量对，分别是一个起始向量操作一次后对应的向量，并保证可以由这L个向量推出向量A。

给出最后的向量，求出初始向量。

分析

花了一两天仔细看了矩阵的一些知识，这个题也不算什么了

写了两个多小时，还是有一些细节打错的地方。

1. 首先求出向量A，根据题目所保证的，我们用L个向量对列出异或方程组，求解即可

2. 对于每一次变换，我们列出每一次变换变换矩阵T，

对于更长的向量A，形式也类似。至于为什么嘛？因为对于每次变换的第K个元素，其实是一个模2意义下的初始向量与A向量的乘积和，xor的意义其实也就是不进位加法。

好了！然后对这个变换矩阵T进行快速幂，然后ST = E，求解这个线性方程组，就可以推出每一次变换的初始矩阵，完美解决。

#include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int maxm = 205; const int maxn = 205; const int maxl = 205; struct conv { char st[maxn], ed[maxn]; bool operator < (const conv& rhs) const { int t = strcmp(st, rhs.st); if (t != 0) return t < 0; else return strcmp(ed, rhs.ed) < 0; } bool operator == (const conv& rhs) const { return strcmp(st, rhs.st) == 0 && strcmp(ed, rhs.ed) == 0; } bool operator != (const conv& rhs) const { return !(*this == rhs); } }; int n, m, k, l; int A[maxn]; int st[maxn], en[maxn]; conv exp[maxl]; pair<int, int> ops[maxm]; char Status_Cn[maxn]; int g[maxl][maxn]; void input() { int cn = 0; scanf("%d%d%d%d", &n, &m, &k, &l); for (register int i = 1; i <= m; i++) { scanf("%d%d", &ops[i].first, &ops[i].second); } for (register int i = 1; i <= l; i++) { scanf("%s%s", exp[i].st, exp[i].ed); } cn = 0; sort(exp + 1, exp + l + 1); for (register int i = 1; i <= l; i++) { if (exp[i] != exp[i - 1]) { exp[++cn] = exp[i]; } } l = cn; scanf("%s", Status_Cn + 1); for (register int i = 1; Status_Cn[i]; i++) { Status_Cn[i] = Status_Cn[i] - '0'; } for (register int i = 1; i <= l; i++) { exp[i].st[k] = exp[i].st[0]; for (register int j = 0; j < k; j++) { exp[i].st[j] = exp[i].st[j + 1]; } exp[i].st[k] = 0; g[i][k] = (exp[i].ed[k - 1] - '0') ^ (exp[i].st[k - 1] - '0'); for (register int j = 0; j < k - 1; j++) { if (exp[i].st[j] == '1') { g[i][j + 1] = 1; } } } } void gauss(int sol[maxn], int len, int tot) { int cn; for (register int i = 1; i <= len; i++) { cn = i; for (register int j = i; j <= tot; j++) { if (g[j][i]) { cn = j; break; } } if (cn != i) { for (register int j = 1; j <= len + 1; j++) { swap(g[cn][j], g[i][j]); } } for (register int j = i + 1; j <= tot; j++) { if (g[j][i]) for (register int q = i; q <= len + 1; q++) { g[j][q] ^= g[i][q]; } } } for (register int i = len - 1; i >= 1; i--) { for (register int j = i + 1; j <= len; j++) { g[i][len + 1] ^= (g[i][j] && g[j][len + 1]); } } for (register int i = 1; i <= len; i++) { sol[i] = g[i][len + 1]; } } struct matrix { int r, c; int m[maxn][maxn]; matrix() { memset(m, 0, sizeof(m)); for (register int i = 1; i <= maxn - 1; i++) m[i][i] = 1; } void operator = (const matrix& rhs) { memset(m, 0, sizeof(m)); r = rhs.r, c = rhs.c; for (register int i = 1; i <= c; i++) { for (register int j = 1; j <= r; j++) { m[i][j] = rhs.m[i][j]; } } } matrix operator * (const matrix& rhs) { matrix ret; memset(ret.m, 0, sizeof(ret.m)); ret.c = c, ret.r = r; for (register int i = 1; i <= ret.c; i++) { for (register int j = 1; j <= ret.r; j++) { for (register int q = 1; q <= r; q++) { ret.m[i][j] += m[i][q] * rhs.m[q][j]; ret.m[i][j] &= 1; } } } return ret; } matrix operator ^ (int q) { matrix ret, cn = *this; ret.r = r, ret.c = c; while (q) { if (q & 1) { ret = ret * cn; } cn = cn * cn; q >>= 1; } return ret; } void prt() { for (register int i = 1; i <= c; i++) { for (register int j = 1; j <= r; j++) { printf("%d ", m[i][j]); } printf("\n"); } } }; void solve() { matrix op, op_cn; op.c = op.r = k; memset(op.m, 0, sizeof(op.m)); for (register int i = 1; i <= k - 1; i++) op.m[i + 1][i] = 1; op.m[1][k] = 1; for (register int i = 2; i <= k; i++) op.m[i][k] = A[i - 1]; for (register int i = m; i >= 1; i--) { op_cn = op; op_cn = op_cn ^ ops[i].second; for (register int j = 1; j <= k; j++) { en[j] = Status_Cn[ops[i].first + j - 1]; } memset(g, 0, sizeof(g)); for (register int j = 1; j <= k; j++) { for (register int p = 1; p <= k; p++) { g[j][p] = op_cn.m[p][j]; } } for (register int j = 1; j <= k; j++) { g[j][k + 1] = en[j]; } gauss(st, k, k); for (register int j = 1; j <= k; j++) { Status_Cn[ops[i].first + j - 1] = st[j]; } } for (register int i = 1; i <= n; i++) { printf("%d", Status_Cn[i]); } printf("\n"); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif input(); gauss(A, k - 1, l); solve(); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

[ppfishoi-blog]

[Codeforces #308 (div. 2)] Vanya and Scales

题目大意

Vanya has a scales for weighing loads and weights of masses w0, w1, w2, ..., w100 grams where w is some integer not less than 2(exactly one weight of each nominal value). Vanya wonders whether he can weight an item with mass m using the given weights, if the weights can be put on both pans of the scales. Formally speaking, your task is to determine whether it is possible to place an item of mass m and some weights on the left pan of the scales, and some weights on the right pan of the scales so that the pans of the scales were in balance.

分析

思路是对的，但是FST了...

把M转换成W进制后，实际上就是看每一位是否是0或者为1，或者说，每一位加上1以后是否为0或是1

贪心地从低位到高位进行即可。

#include <cstdio> #include <algorithm> using namespace std; int w, m; int p[105]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif scanf("%d%d", &w, &m); int cn = 0; while (m) { p[++cn] = m % w; m /= w; } bool flag = true; for (register int i = 1; i <= cn; i++) { if (p[i] >= w) { p[i] = 0; p[i + 1] ++; } if (p[i] == w - 1) { p[i + 1] ++; } else if (p[i] > 1) { flag = false; } } if (flag) printf("YES\n"); else printf("NO\n"); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

[ppfishoi-blog]

[POJ1160] 四边形不等式学习笔记

还是以POJ1160作例子。

We define that f[i][j], means the minimum cost of k (k = 1 ... j) when set i post offices and the last post office is not greater than j And we define w[i][j], means the minimum cost of k (k = i ... j), when set ONE post office between i and j

Part 1. Quadrilateral Inequality of Array W

We can find that, for i <= i' <= j <= j', we have: >>> w[i][j] + w[i'][j'] <= w[i'][j] + w[i][j'] >>> w[i][j] - w[i'][j] <= w[i][j'] - w[i'][j']  (*) How to prove it?

First we concentrate on how Array W was calculated: w[i][j] = w[i][j - 1] + dis(j, (i + j) / 2)

First we prove w[i][j] + w[i + 1][j + 1] <= w[i + 1][j] + w[i][j + 1] (j > i) >>> w[i][j + 1] - w[i][j] >= w[i + 1][j + 1] - w[i + 1][j] >>> dis(j + 1, (i + j + 1) / 2) >= dis(j + 1, (i + j + 2) / 2) Obviously it's true, so we have: w[i][j] + w[i + 1][j + 1] <= w[i + 1][j] + w[i][j + 1]  (*1) And we have, w[i][j] <= w[i'][j'] (i >= i', j <= j')  (*2)

If we have (*1) and (*2), so (*) is true So, w[i][j] + w[i'][j'] <= w[i'][j] + w[i][j']

Part 2. Quadrilateral Inequality of Array F

Then we prove f[i][j] obey Quadrilateral Inequality, we have i < i' <= j < j' >>> f[i][j] + f[i'][j'] <= f[i'][j] + f[i][j'] (*3) If f[i'][j] was expanded by x, and f[i][j'] was expanded by y

1. i < i' < j < j' , x < y ,  >>> i < x < y < j < j' >>> f[i'][j] + f[i][j'] = f[i' - 1][x] + w[x + 1][j] + f[i - 1][y] + w[y + 1][j'] >>>                     = f[i' - 1][x] + f[i - 1][y] + w[x + 1][j] + w[y + 1][j'] >>>                     >= f[i' - 1][x] + f[i - 1][y] + w[x + 1][j'] + w[y + j][j] >>>                     >= f[i'][j'] + f[i][j] Other situation under i < i' < j < j' are similar.

2. When i < i' = j < j' , x < y, (*3) -> f[i][j] + f[j][j'] <= f[j][j] + f[i][j'] Cause f[j][j] = 0, so we should prove f[i][j] + f[j][j'] <= f[i][j'] If f[i][j] was expanded by x, f[j][j'] was expanded by y

i < x <= y < j < j' >>> f[i][j] + f[j][j'] = f[i - 1][x] + f[j][y] + w[x + 1][j] + w[y + 1][j'] >>>                    <= f[i - 1][x] + f[j][y] + w[y + 1][j] + w[x + 1][j'] >>>                    <= f[i - 1][x] + w[y + 1][j] + w[x + 1][j'] >>>                    <= f[i][j'] + w[y + 1][j] >>>                    <= f[i][j']

Part 3. How can we know s[i][j - 1] <= s[i][j] <= s[i + 1][j] ?

Conclusion: Iff when Array W and F both obey Quadrilateral Inequality,                     s[i][j - 1] <= s[i][j] <= s[i + 1][j]

Accept Code (0ms)

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxv = 305; const int inf = 0x3f3f3f3f; int v, p; int Sum[maxv], a[maxv], f[maxv][maxv], s[maxv][maxv], w[maxv][maxv]; int abs(int x) { if (x <= 0) return -x; else return x; } void input() { memset(f, inf, sizeof(f)); memset(w, inf, sizeof(w)); for (register int i = 1; i <= v; i++) { scanf("%d", &a[i]); Sum[i] = Sum[i - 1] + a[i]; } } void init() { int cnt; for (register int i = 1; i <= v; i++) { for (register int j = i; j <= v; j++) { cnt = (i + j) >> 1; w[i][j] = a[cnt] * (cnt - i + 1) - (Sum[cnt] - Sum[i - 1]) + Sum[j] - Sum[cnt - 1] - a[cnt] * (j - cnt + 1); } } for (register int i = 0; i <= v; i++) { f[i][i] = 0; s[i][i] = i - 1; s[p + 1][i] = v; } } void solve() { // f[i][j] -> the minimum cost when i post offices are placed, and the last is NOT GREATER than j for (register int len = 2; len <= v; len++) { for (register int i = 1; i <= p; i++) { int j = i + len - 1; if (j > v) break; // s[i][j - 1] <= s[i][j] <= s[i + 1][j] for (register int k = s[i][j - 1]; k <= s[i + 1][j]; k++) { if (f[i][j] > f[i - 1][k] + w[k + 1][j]) { f[i][j] = f[i - 1][k] + w[k + 1][j]; s[i][j] = k; } } } } printf("%d\n", f[p][v]); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif while (~scanf("%d%d", &v, &p)) { input(); init(); solve(); } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

[ppfishoi-blog]

[POJ1160] Post Office

题目大意

给出n个村庄的坐标，在k个村庄上建立邮局，使每个村庄到最近的邮局距离和最小

分析

带权中位数+DP

我们设w[i, j]为在 i - j 这段范围内建立一个邮局的区间最小距离和

w[i, j]用带权中位数处理

f[i, j]为建立了i个邮局，且最后一个邮局不超过 j 的最小距离和

然后就有转移方程

f[i, j] = min{ f[i - 1][k] + w[k + 1][j] | i - 1 <= k < j }

时间复杂度O(n ^ 3)，等我学习完四边形不等式优化再来补充一下。

Accept Code

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxv = 305; const int inf = 0x3f3f3f3f; int v, p; int Sum[maxv], a[maxv], f[maxv][maxv], w[maxv][maxv]; int abs(int x) { if (x <= 0) return -x; else return x; } void input() { memset(f, inf, sizeof(f)); memset(w, inf, sizeof(w)); f[0][0] = 0; for (register int i = 1; i <= v; i++) { scanf("%d", &a[i]); Sum[i] = Sum[i - 1] + a[i]; } } void init() { int cnt; for (register int i = 1; i <= v; i++) { for (register int j = i; j <= v; j++) { cnt = (i + j) >> 1; w[i][j] = a[cnt] * (cnt - i + 1) - (Sum[cnt] - Sum[i - 1]) + Sum[j] - Sum[cnt - 1] - a[cnt] * (j - cnt + 1); } } } void solve() { // f[i][j] -> the minimum cost when i post offices are placed, and the last is NOT GREATER than j for (register int i = 1; i <= p; i++) { for (register int j = 1; j <= v; j++) { for (register int k = 0; k < j; k++) { f[i][j] = min(f[i][j], f[i - 1][k] + w[k + 1][j]); } } } printf("%d\n", f[p][v]); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif while (~scanf("%d%d", &v, &p)) { input(); init(); solve(); } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }

[ppfishoi-blog]

[SGU171] Sarov Zones

题目大意

参加俄罗斯的数学奥林匹克全国赛是需要先参加区域赛的，因此每年XXX州都会有许多学生为了参加全国赛而先去参加各地的区域赛。

今年共有K个区域举办比赛且编号为i的区域给予了XXX州N[i]名的参赛名额，因此XXX州今年将有N=N[1]+N[2]+...N[K]名学生参赛。

各区域赛和各学生都有自己的等级，当参赛学生等级大于他所参加的区域赛等级时，他将会受到全国赛的邀请。

此外还给出了N名参赛学生的体重，XXX州的当局者希望自己州能够参加全国赛的学生的总体重最大（真不知道他是怎么想的）。

请编程帮助他决定各参赛学生应该前往哪个区域参赛。

分析

We use a greedy algorithm

Sort zone by N, and sort students by W We try to push the students who has maximum W to the zone and they will be chosen, if they enter zone i, we guarantee the abs(P - Qi) is the minimum

Then for the rest students, we push them into the non-full zone with the most Q, because they will not be chosen and they should make the possibility that the students behind him are chosen maximum

"牺牲自己 成就他人"

[ppfishoi-blog]

[SGU167] I-Country

题目大意

在一个N * M的矩阵中（N, M <= 15），每一个格子有权值，选择一块连续的区域，保证区域内每一个点到区域内另外任意一个点只要通过两种移动方式（上下左右）便可以到达，并使权值和最大，输出选择方案。

分析

一开始题目没看太懂。

后来看懂了，写出DP方程

>>> f[i][j][k][h][l][r]

代表到第i行，选取j到k的格子，l和r是否已经向内凸，总共选取了h个的最大权值和

然后就是几种情况的转移了，大概就是对于当前一行和上一行左右端点的一些判断，一开始分情况分得很细，但是错的很惨。其实这大概是一个思路吧，类似这样的题目要学会从反面情况去去除非法情况，剩下的都是合法转移。

要记录方案？我们对开一个和 f 同样大小的数组，压位记录他的前驱，最后输出即可！

复杂度 O(n^2 * m^5)

#include <ctime> #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int maxn = 16; const int maxl = 226; int n, m, k; int g[maxn][maxn]; int f[maxn][maxn][maxn][maxl][2][2]; int pr[maxn][maxn][maxn][maxl][2][2]; int ansi, ansj, ansk, ansh, ansl, ansr; int stack[100], top; void prt(int x) { top = 0; do { stack[++top] = x % 10; x /= 10; } while (x); for (register int i = top; i >= 1; i--) { putchar('0' + stack[i]); } } int zip(int a, int b, int c, int d, int e, int f) { int ret = 0; ret = (ret << 5) + a; ret = (ret << 5) + b; ret = (ret << 5) + c; ret = (ret << 10) + d; ret = (ret << 1) + e; ret = (ret << 1) + f; return ret; } void input() { scanf("%d%d%d", &n, &m, &k); for (register int i = 1; i <= n; i++) { for (register int j = 1; j <= m; j++) { scanf("%d", &g[i][j]); g[i][j] = g[i][j] + g[i][j - 1]; } } } vector< pair<int, int> > Ans; void prt() { int cnt; while (ansh) { for (register int i = ansj; i <= ansk; i++) { prt(ansi); putchar(' '); prt(i); putchar('\n'); } cnt = pr[ansi][ansj][ansk][ansh][ansl][ansr]; ansr = cnt & 1; cnt >>= 1; ansl = cnt & 1; cnt >>= 1; ansh = cnt & ((1 << 10) - 1); cnt >>= 10; ansk = cnt & ((1 << 5) - 1); cnt >>= 5; ansj = cnt & ((1 << 5) - 1); cnt >>= 5; ansi = cnt & ((1 << 5) - 1); } } int ans; inline void Process(const int& i, const int& j, const int& ck, const int& l, const int& r, const int& pj, const int& pk, const int& pls, const int& prs, const int& cnth, const int& len, const int& cnt) { if (j < pj && pls) return; if (ck > pk && prs) return; if (j > pj && l == 0) return; if (ck < pk && r == 0) return; if (l == 0 && pls == 1) return; if (r == 0 && prs == 1) return; if (f[i - 1][pj][pk][cnth][pls][prs] + cnt > f[i][j][ck][cnth + len][l][r]) { f[i][j][ck][cnth + len][l][r] = f[i - 1][pj][pk][cnth][pls][prs] + cnt; pr[i][j][ck][cnth + len][l][r] = zip(i - 1, pj, pk, cnth, pls, prs); } if (cnth + len == k && f[i][j][ck][cnth + len][l][r] > ans) { ans = f[i][j][ck][cnth + len][l][r]; ansi = i, ansj = j, ansk = ck, ansh = cnth + len, ansl = l, ansr = r; } } void solve() { int r, q, cnt; for (register int i = 1; i <= n; i++) { for (register int len = 1; len <= m; len++) { for (register int l = 1; l <= m; l++) { r = l + len - 1; if (r > m) break; cnt = g[i][r] - g[i][l - 1]; for (register int p = 1; p <= m; p++) { for (register int q = p; q <= m; q++) { if (!(l <= q && r >= p)) continue; for (register int h = 0; h <= k; h++) { if (h + len > k) break; for (register int s = 0; s <= 1; s++) { for (register int t = 0; t <= 1; t++) { for (register int e = 0; e <= 1; e++) { for (register int y = 0; y <= 1; y++) { Process(i, l, r, s, t, p, q, e, y, h, len, cnt); } } } } } } } } } } printf("Oil : %d\n", ans); prt(); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif input(); solve(); fprintf(stderr, "%.3lf s\n", (double) clock() / CLOCKS_PER_SEC); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; }