2018 HDU多校第四场赛后补题
自己学校出的毒瘤场。。吃枣药丸
hdu中的题号是6332 ～ 6343。
K. Expression in Memories
题意：
判断一个简化版的算术表达式是否合法。
题解：
注意细节即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int n; char s[505];
int main () {
int T; cin>>T;
for ( ; T; --T) {
scanf("%s",s+1),n=strlen(s+1),s[0]='+';
if (s[1]=='?') s[1]='9';
bool ok=1;
for (int i=2; i<=n; ++i) {
if (s[i]=='+'||s[i]=='*') {
if (s[i-1]=='+'||s[i-1]=='*') {ok=0; break;}
} else
if (s[i]>='0'&&s[i]<='9') {
if (s[i-1]=='0'&&(s[i-2]=='+'||s[i-2]=='*')) {ok=0; break;}
} else
if (s[i]=='?') {
if (s[i-1]=='+'||s[i-1]=='*') s[i]='9'; else
if (s[i-1]=='0') {
if (s[i-2]=='+'||s[i-2]=='*') s[i]='+';
else s[i]='9';
} else
if (s[i-1]>='1'&&s[i-1]<='9') s[i]='9';
}
}
if (s[n]=='+'||s[n]=='*'||s[1]=='+'||s[1]=='*') ok=0;
if (n>=2) {
if (s[1]=='0'&&s[2]>='0'&&s[2]<='9') ok=0;
}
if (!ok) puts("IMPOSSIBLE");
else {
for (int i=1; i<=n; ++i) printf("%c",s[i]);
puts("");
}
}
return 0;
}L. Graph Theory Homework
题意：
给你一张每个点有点权的完全图。从点\(i\)走到点\(j\) \(（i≠j）\)的代价为 \(\lfloor \sqrt {|wi-wj|} \rfloor\)
球从\(1\)走到\(n\)的最小代价。
题解：
一个不等式： \(\lfloor \sqrt {a} \rfloor + \lfloor \sqrt {b} \rfloor \geq \lfloor \sqrt {a+b} \rfloor\)
则，从\(1\)不经过任何点直接到\(n\)是最优的。
代码：
#include <bits/stdc++.h>
#define N 100010
using namespace std;
int w[N],w2[N];
int main () {
int T,n;
scanf("%d",&T);
while (T--) {
scanf("%d",&n);
for(int i=1; i<=n; ++i) scanf("%d",&w[i]);
printf("%d\n",(int)sqrt(abs(w[n]-w[1])));
}
return 0;
}D. Nothing is Impossible
题意：
没有题意，至今还不知道最终的题意。
题解：
没有题解，只需要大胆猜想，无需证明，取最小的几个\(bi\)使得\(\prod {(bi + 1)} \leq m\)就行了。能取到的最多个数就是答案。
代码：
#include <bits/stdc++.h>
using namespace std;
int b[105];
int main()
{
int T, n, m, x;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
int ans = n; long long now = 1;
for (int i = 1; i <= n; i++) scanf("%d%d", &x, &b[i]);
sort(b + 1, b + 1 + n);
for (int i = 1; i <= n; ++i) {
if (now * (b[i] + 1) > m) {ans = i - 1; break;}
now *= (b[i] + 1);
}
printf("%d\n", ans);
}
return 0;
}E. Matrix from Arrays
题意：
给你一个\(L\)个元素的数组\(A\)，根据题意构造一个无限矩阵，并进行q次询问，询问一个有限矩阵内的元素和。
题解：
容易发现，构造出来的无限矩阵是一个循环矩阵。当\(L\)是奇数时，矩阵每\(LL\)个元素循环；当\({L}*{L}\)是偶数时，矩阵每\({2L}*{2L}\)个元素循环。
这样我们就可以预处理处一个很小（边长\(80\)以内)的矩阵，然后做一下前缀和。
最后询问的时候留给我们解决的也不多了。
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int L, Q; ll A[20], M[90][90], s1[90], s2[90], sum;
ll calc (int x, int y, ll ret = 0) {
ll k1 = (x + 1) / (2 * L), k2 = (y + 1) / (2 * L);
ll o1 = (x + 1) % (2 * L), o2 = (y + 1) % (2 * L);
ret += sum * k1 * k2;
if (o1) ret += s1[o1 - 1] * k2;
if (o2) ret += s2[o2 - 1] * k1;
for (int i = 0; i < o1; ++i) {
for (int j = 0; j < o2; ++j) ret += M[i][j];
}
return ret;
}
int main () {
int T; cin >> T;
for ( ; T; --T) {
cin >> L;
for (int i = 0; i < L; ++i) cin >> A[i];
int cursor = 0;
for (int i = 0; i < 4 * L; ++i) {
for (int j = 0; j <= i; ++j) {
M[j][i - j] = A[cursor];
cursor = (cursor + 1) % L;
}
}
sum = 0;
for (int i = 0; i < 2 * L; ++i) {
for (int j = 0; j < 2 * L; ++j) sum += M[i][j];
}
memset(s1, 0, sizeof s1);
memset(s2, 0, sizeof s2);
for (int i = 0; i < 2 * L; ++i) {
for (int j = 0; j < 2 * L; ++j) s1[i] += M[i][j];
if (i) s1[i] += s1[i - 1];
}
for (int j = 0; j < 2 * L; ++j) {
for (int i = 0; i < 2 * L; ++i) s2[j] += M[i][j];
if (j) s2[j] += s2[j - 1];
}
cin >> Q;
for ( ; Q; --Q) {
int l, u, r, d;
scanf("%d%d%d%d", &l, &u, &r, &d);
printf("%lld\n", calc(r, d) - calc(r, u - 1) - calc(l - 1, d) + calc(l - 1, u - 1));
}
}
return 0;
}J. Let Sudoku Rotate
题意：
有一个合法的\(4\)阶数独，某人随机把几个“宫”分别逆时针翻转了几次，先给出现在的数独，问那个人总共最少转了几次。
题解：
如果你够大胆，就去爆搜吧；如果你不够大胆，就去\(dlx\)吧！
反正都能过，可能是因为合法情况太少的缘故
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 17, M = 5;
int n, m, ans, a[N][N], tmp[M][M]; char s[N];
int R[N][N], C[N][N];
void rotating_lalala (int r, int c) {
int _u = r * m, _d = _u + m, _l = c * m, _r = _l + m;
for (int i = _u; i < _d; ++i)
for (int j = _l; j < _r; ++j) tmp[j - _l][m - (i - _u) - 1] = a[i][j];
for (int i = _u; i < _d; ++i)
for (int j = _l; j < _r; ++j) a[i][j] = tmp[i - _u][j - _l];
}
bool exam (int r, int c) {
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
int x = r * m + i, y = c * m + j;
if (R[x][a[x][y]]) return 0;
if (C[y][a[x][y]]) return 0;
}
}
return 1;
}
void fig (int r, int c, int d) {
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
int x = r * m + i, y = c * m + j;
R[x][a[x][y]] += d, C[y][a[x][y]] += d;
}
}
}
void dfs (int r, int c, int cnt) {
if (cnt >= ans) return;
if (c == m) c = 0, ++r;
if (r == m && c == 0) {ans = cnt; return;}
if (exam(r, c)) fig(r, c, 1), dfs(r, c + 1, cnt + 0), fig(r, c, -1);
rotating_lalala(r, c);
if (exam(r, c)) fig(r, c, 1), dfs(r, c + 1, cnt + 1), fig(r, c, -1);
rotating_lalala(r, c);
if (exam(r, c)) fig(r, c, 1), dfs(r, c + 1, cnt + 2), fig(r, c, -1);
rotating_lalala(r, c);
if (exam(r, c)) fig(r, c, 1), dfs(r, c + 1, cnt + 3), fig(r, c, -1);
rotating_lalala(r, c);
}
int main () {
int T; cin >> T; m = 4, n = 16;
for ( ; T; --T) {
for (int i = 0; i < n; ++i) {
scanf("%s", s);
for (int j = 0; j < n; ++j) {
if (s[j] >= '0' && s[j] <= '9') a[i][j] = s[j] - '0';
else a[i][j] = s[j] - 'A' + 10;
}
}
ans = 64;
memset(R, 0, sizeof R), memset(C, 0, sizeof C);
dfs(0, 0, 0);
cout << ans << endl;
}
return 0;
}B. Harvest of Apples
题意：
求\(\sum_{i=0}^{m} {C_{n}^{i}}\)，\(n，m\)都是\(1e5\)范围，还有\(1e5\)组询问。
题解：
早就见识过这个东西的厉害。但一起一直不知道怎么做。也不知道有没有柿子。然后就去\(OEIS\)了一发，结果什么都没有。。
OEIS大法失灵了还是我等蒟蒻不会用。
考场上想过离线，也想过\(n\)和\(n-1\)，\(m\)和\(m-1\)的关系，但是就没有想到莫队。
首先，设\(S(n, m) = \sum_{i=0}^{m} {C_{n}^{i}}\)，利用杨辉三角那个公式，我们有柿子：
\(S(n, m) = S(n, m - 1) + C_{n}^{m}\)
\(S(n, m) = 2 * S(n - 1, m) - C_{n-1}^{m}\)
这样我们发现，等式两边给出的两对关系，让我们真的可以愉快地搞莫队了。而且很好码，双倍的快乐嘻嘻嘻
转移复杂度是\(O(1)\)的。
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100005, mo = 1e9 + 7, inv2 = 500000004;
int n, siz, l, r; ll ret, fac[N], inv[N], ans[N];
struct que {
int l, r, i;
bool operator < (const que &o) const {
return (r - 1) / siz == (o.r - 1) / siz ? l < o.l : r < o.r;
}
} a[N];
ll ksm (ll b, ll p) {
if (p < 2) return p ? b : 1;
ll t = ksm(b, p >> 1); t = t * t % mo;
return p & 1 ? t * b % mo : t;
}
ll C (int n, int r) {
if (r < 0 || n < r) return 0;
return fac[n] * inv[r] % mo * inv[n - r] % mo;
}
void ppw () {
fac[0] = 1;
for (int i = 1; i < N; ++i) fac[i] = fac[i - 1] * i % mo;
inv[N - 1] = ksm(fac[N - 1], mo - 2);
for (int i = N - 2; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % mo;
}
void add (int x, bool o) {
if (!o) ret -= C(r, l + 1);
else ret = ret * 2 - C(r - 1, l);
ret = (ret + mo) % mo;
}
void rem (int x, bool o) {
if (!o) ret += C(r, l + 1);
else ret = (ret + C(r - 1, l)) * inv2;
ret = ret % mo;
}
int main () {
cin >> n, siz = sqrt(n + 0.5), ppw();
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &a[i].r, &a[i].l);
a[i].i = i;
}
sort(a + 1, a + 1 + n);
ret = 0;
for (int i = 0; i <= a[1].l; ++i) {
ret = (ret + C(a[1].r, i)) % mo;
}
ans[a[1].i] = ret;
l = a[1].l, r = a[1].r;
for (int i = 2; i <= n; ++i) {
for ( ; l > a[i].l; ) --l, add(l, 0);
for ( ; r < a[i].r; ) ++r, add(r, 1);
for ( ; l < a[i].l; ) rem(l, 0), ++l;
for ( ; r > a[i].r; ) rem(r, 1), --r;
ans[a[i].i] = ret;
}
for (int i = 1; i <= n; ++i) printf("%lld\n", ans[i]);
return 0;
}G. Depth-First Search
题意：
给出一棵\(n\)个节点的无根树和一个长度为\(n\)的排列\(B\)。问有多少种dfs序在字典序上小于这个排列。
题解：
运用题解里提到的“逐位确定”的思想。
首先，我们要知道，根的编号小于\(B[1]\)的方案数有多少种。
不妨假设从\(r\)开始\(（r<B[1]）\)，那么可以树形dp出总方案数。
表达式为\(ans[r] = \prod (cntchild[i])! = deg[r] * \prod_{i \neq r} \ (deg[i]-1)!\)。
那么，根节点比\(B[1]\)小的总答案为\(ans1 = (\prod_{i<B[1]} deg[i]!) * (\prod_{i \geq B[1]} \ (deg[i]-1)!)\)。
那如何统计以\(B[1]\)为根的序列方案呢？
Notice，逐位确定。
首先不妨先将每个点的子节点排个序。
然后假设现在处于节点\(x\)，并假设\(x\)的所有祖先（包括自己）恰好组成了\(B\)的某个前缀，设是\(B[i]\)。
设达成这种状态的方案数为\(pp\)（这个信息可以从父节点传下来）。（其实这里说的状态是根据匹配的前缀长度来划分的，若有两个合法序列\(A1\)，\(A2\)，设\(A1\)和\(B\)的最长公共前缀为\(l1\)，\(A2\)和\(B\)的最长公共前缀为\(l2\)，\(l1=l2\)，则它们属于同种状态，否则算不同种）
那么，如果\(B[i+1]\)是\(x\)的某个子节点，显然，我们可以确定比\(B[i+1]\)小的\(x\)的子节点数\(cnt\)，剩余的\(x\)的子点数\(res\)。那对于此种状态，合法的序列数又增加了
\[delta = cnt * (res)! * \prod_{son[x,j] \neq B[i+1]} f[son[x,j]] * pp \]
其中\(f[k]\)表示在以\(k\)为根的子树中有多少种序列（任意），可以预处理出来。
需要注意，也许把一个子树搜完了，整棵树并没有被搜完。所以还要关注其他子树（即搜索下一个等于\(B[nxt]\)的子节点，直到不可能找到这种子节点为止，此时贡献已计算完毕，退出即可）。这样转化成了相同的问题。但是如果dfs了一个子树（同时贡献也计算完了），就要把这棵子树的贡献删掉。快速搜索和删除贡献要用高效的数据结构维护，比如树状数组。注意，删除贡献这一步非常重要，需要仔细考虑。
最后注意程序一定要高效。这个题常数好像挺大的。本地还会爆栈。
代码：
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1000005, mo = 1e9 + 7;
int n, A[N], siz[N];
int tot, lnk[N], nxt[N << 1], son[N << 1];
ll ans, tmp, fac[N], inv[N], f[N];
vector <int> g[N];
void add (int x, int y) {
nxt[++tot] = lnk[x], lnk[x] = tot, son[tot] = y;
}
ll ksm (ll b, ll p) {
if (p < 2) return p ? b : 1;
ll t = ksm(b, p >> 1); t = t * t % mo;
return p & 1 ? t * b % mo : t;
}
void pre (int x, int p) {
siz[x] = 1, f[x] = 1;
for (int j = lnk[x]; j; j = nxt[j]) {
if (son[j] == p) continue;
g[x].push_back(son[j]);
pre(son[j], x);
siz[x] += siz[son[j]];
f[x] = f[x] * f[son[j]] % mo;
}
f[x] = f[x] * fac[g[x].size()] % mo;
}
struct bit {
int siz; vector <int> c;
void init (int x) {siz = x, c.clear(), c.resize(x + 1);}
void add (int x) {for ( ; x <= siz; x += x & (-x)) ++c[x];}
void remove (int x) {for ( ; x <= siz; x += x & (-x)) --c[x];}
int count (int x, int ret = 0) {for ( ; x > 0; x -= x & (-x)) ret += c[x]; return ret;}
} bt[N];
int sear (int x, int v) {
int ret = 0;
for (int i = 19; ~i; --i) {
if (ret + (1 << i) - 1 >= g[x].size()) continue;
if (g[x][ret + (1 << i) - 1] < v) ret += 1 << i;
}
return ret - 1;
}
bool dfs (int x, int no, ll pp) {
int num = no, cnt = g[x].size(); ll prod = 1;
for (int i = 0; i < cnt; ++i) {
prod = prod * f[g[x][i]] % mo;
bt[x].add(i + 1);
}
for (int i = 0, suit, y; i < cnt; ++i) {
suit = sear(x, A[num + 1]);
ans += pp * prod % mo * fac[cnt - 1 - i] % mo * bt[x].count(suit + 1);
ans %= mo;
++suit; if (suit >= cnt) return 0;
y = g[x][suit];
if (y != A[num + 1]) return 0;
bt[x].remove(suit + 1);
prod = prod * ksm(f[y], mo - 2) % mo;
if (!dfs(y, num + 1, pp * prod % mo * fac[cnt - 1 - i] % mo)) return 0;
else num += siz[y];
}
return 1;
}
void ppw () {
fac[0] = 1;
for (int i = 1; i < N; ++i) fac[i] = fac[i - 1] * i % mo;
inv[N - 1] = ksm(fac[N - 1], mo - 2);
for (int i = N - 2; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % mo;
}
int main () {
ppw();
int T; cin >> T;
for ( ; T; --T) {
scanf("%d", &n), tot = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &A[i]);
siz[i] = f[i] = lnk[i] = 0;
g[i].clear();
g[i].resize(0);
}
for (int i = 1; i <= n * 2; ++i) nxt[i] = 0;
for (int i = 1, x, y; i < n; ++i) {
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
}
ans = 0, tmp = 1;
pre(A[1], 0);
for (int i = 1; i <= n; ++i) {
if (i == A[1]) tmp = tmp * fac[g[i].size() - 1] % mo;
else tmp = tmp * fac[g[i].size()] % mo;
}
for (int i = 1; i < A[1]; ++i) ans = (ans + tmp * (g[i].size() + 1)) % mo;
for (int i = 1; i <= n; ++i) {
sort(g[A[i]].begin(), g[A[i]].end());
bt[A[i]].init(g[A[i]].size());
}
dfs(A[1], 1, 1);
printf("%lld\n", ans);
}
return 0;
}毒瘤题，补不动！。。