905
emmmmm， 这是一次比较有意义的题吧， 最后我的排名很靠前， 但是成绩也不是很如人意。。。
这是第一道题， 一般会比较简单一点， 但却是我三道题中得分最低的一个， 只有30分的暴力分。 当时写的时候直接暴力搜索， 选出所有的情况并记录， 复杂度为 O(T · 2 n )。
我们先看k = 2的特例， 我们可以想到， 在n个位置中放m的小球， 且小球的间距 >= 1, 即留出一个间隔。假设我们就在前m个位置上放上小球而此时的方案数是C（m – 2，n – 2 – (m – 1) ), （C为组合数），
那我们就推广到k的做法， 即0两个球之间间距 >= k – 1， 方案数为C（m – 2， n – 2 – （m – 1）* （k – 1）），由于只用判断方案数的奇偶性， 由卢卡斯定理可得， 在%p的情况下， C（n， m） = C（n % p， m % p）* C（n / p， m / p）；当p = 2时， C（n， m）共有4种情况， 当m >= n 时， C（n， m） = 1； 所以用卢卡斯定理继续递归下去， 当m & n = n， （即n的每一位的1在m中都是1），则C（n， m）的结果为1， 否则为0； 所以该题的正解就是判断((n – 2 – (m – 1) * (k – 1)) & (m – 2)) == m – 2是否成立。
#includeusing namespace std; template < typename T > inline void read(T &x) { x = 0; T ff = 1, ch = getchar(); while(!isdigit(ch)) { if(ch == '-') ff = -1; ch = getchar(); } while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } x *= ff; } int T, n, m, k; int main() { read(T); while(T--) { read(n); read(m); read(k); if(((n - 2 - (m - 1) * (k - 1)) & (m - 2)) == m - 2) puts("Yes"); else puts("No"); } return 0; } 正解
#includeusing namespace std; template < typename T > inline void read(T &x) { x = 0; T ff = 1, ch = getchar(); while(!isdigit(ch)) { if(ch == '-') ff = -1; ch = getchar(); } while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } x *= ff; } int T, n, m, k; bool ans = false; void dfs(int now, int val) { if(now == m + 1) { if(val == n) ans ^= 1; return ; } for(int i = n - (m - now) * k - val; i >= k; --i) { if(now == m && val + i < n) continue; dfs(now + 1, val + i); } } int main() { freopen("phantasm.in", "r", stdin); freopen("phantasm.out", "w", stdout); read(T); while(T--) { read(n); read(m); read(k); dfs(2, 1); if(ans) puts("Yes"); else puts("No"); ans = false; } return 0; } 搜素大法好（30分）
emmmm，标题就省略了， 题意显然易懂， 一个很显然的做法就是用lca求距离， O（n）枚举每一个点求最小值， 时间复杂度为O（n * q * logn）， 有60分的分数。 另有20分的大数据是一条链的情况， 当时就怎么也推不出来， 就导致我的第一题的特殊情况没有判断，这道题的正解是树形DP，
对于有根树，一个点所选择的对应点仅在其子树内的情形， 答案可以通过树形 dp 递推得到。 考虑选择其子树外的点的情形。观察原式可以发现，如果一 个点的父亲的最优选择不是该点，则其在子树外的 最优选择必 然就是其父亲的最优选择。否则，其在子树外的最优选择必然是 其父亲的次优选择。由此，可在 dfs 过程中自上而下推出所有点 在其子树外的最优答案。 对每个点子树内外的最优答案取最小值，即可得到每个点的 答案。 复杂度：O(n)。
#includeusing namespace std; typedef long long ll; const int INF = 1e9 + 7; const int MAXN = 2e5 + 100; const int MAXM = 3e3 + 10; const double eps = 1e-5; template < typename T > inline void read(T &x) { x = 0; T ff = 1, ch = getchar(); while(!isdigit(ch)) { if(ch == '-') ff = -1; ch = getchar(); } while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } x *= ff; } template < typename T > inline void write(T x) { if(x < 0) putchar('-'), x = -x; if(x > 9) write(x / 10); putchar(x % 10 + '0'); } int n, T, c[MAXN], deep[MAXN], f[MAXN][20], dis[MAXN]; int lin[MAXN], tot = 0; struct edge { int y, v, next; }e[MAXN << 1]; inline void add(int xx, int yy, int vv) { e[++tot].y = yy; e[tot].v = vv; e[tot].next = lin[xx]; lin[xx] = tot; } inline void BFS() { queue < int > q; q.push(1); deep[1] = 1; while(!q.empty()) { int x = q.front(); q.pop(); for(int i = lin[x], y; i; i = e[i].next) { if(!deep[y = e[i].y]) { q.push(y); deep[y] = deep[x] + 1; f[y][0] = x; dis[y] = dis[x] + e[i].v; for(int i = 1; i <= 19; ++i) { f[y][i] = f[f[y][i - 1]][i - 1]; } } } } } inline int lca(int x, int y) { if(deep[x] > deep[y]) swap(x, y); for(int i = 19; i >= 0; --i) { if(deep[f[y][i]] >= deep[x]) y = f[y][i]; } if(x == y) return x; for(int i = 19; i >= 0; --i) { if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i]; } return f[x][0]; } inline int dist(int x, int y) { return dis[x] + dis[y] - 2 * dis[lca(x, y)]; } int main() { freopen("skylines.in", "r", stdin); freopen("skylines.out", "w", stdout); read(n); for(int i = 1; i <= n; ++i) { read(c[i]); } for(int i = 1; i < n; ++i) { int u, v, w; read(u); read(v); read(w); add(u, v, w); add(v, u, w); } BFS(); read(T); while(T--) { int u; read(u); int minn = INF; for(int i = 1; i <= n; ++i) { if(i == u) continue; if(dist(u, i) + c[u] - c[i] < minn) minn = dist(u, i) + c[u] - c[i]; } write(minn); puts(""); } return 0; } lca（60分）
题意较难理解， 所以可能好多人没有理解题意导致失分， 首先想到的还是搜索大法， 可能的数列共有 m! 种，答案就是所有情况下数列的权值和 除以情况数。 搜索枚举每种情况并求出其权值和，全部加起来除以 m! 即 可。 复杂度：O(m!)。 可以获得 30 分。
还有对所有 ai 均相等的算法 由于 ai 都相等，则对于任意数列，其权值和均相等 直接输出 m ∗ ai 即可 综上，可以获得 50 分，这可是送的20分。。。
然后大佬们就想到了状态压缩， 一个数列的权值和与数列中数的顺序无关，只与每种数的个 数有关 考虑 dp，状态中需要记录每种数的个数 可以发现，将得到的数列排序后，相邻两数的差只能为 0 或 1 用二进制序列维护原数列的差分数组，即可表示数列中每种 数的个数，f(i, S) 表示生成了 i 个数，已有数列的差分为 S 的方案数 则每种数列出现的概率 PS = f(m,S) /m! 转移时枚举前一个数的大小，修改状态即可 事先预处理出 totS 表示状态 S 所表示的数列的权值和, 最 后的答案即为 ∑ S PStotS 复杂度：O(m · 2 m)。注意做除法时用乘法逆元计算。
#includeusing namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int MAXN = 1e5 + 100; const int MAXM = 3e3 + 10; const double eps = 1e-5; template < typename T > inline void read(T &x) { x = 0; T ff = 1, ch = getchar(); while(!isdigit(ch)) { if(ch == '-') ff = -1; ch = getchar(); } while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } x *= ff; } template < typename T > inline void write(T x) { if(x < 0) putchar('-'), x = -x; if(x > 9) write(x / 10); putchar(x % 10 + '0'); } const ll mod = 998244353; ll n, m, sum[MAXN], a[MAXN], b[MAXN]; ll ans, cnt; bool flag = false; inline void dfs(int now) { if(now == m + 2) { ans += sum[now - 1]; if(ans >= mod) ans %= mod; cnt++; // printf("ans = %d cnt = %d\n", ans, cnt); return ; } for(int i = 1; i < now; ++i) { a[now] = a[i] + 1; sum[now] = sum[now - 1] + b[a[now]]; dfs(now + 1); a[now] = 0; sum[now] = 0; } } int main() { // freopen("kiseki.in", "r", stdin); // freopen("kiseki.out", "w", stdout); read(n); read(m); for(int i = 2; i <= n + 1; ++i) { read(b[i]); if(i != 2 && b[i] != b[i - 1]) flag = true; } if(!flag) { write((m * b[2]) % mod); return 0; } sum[2] = b[2]; a[1] = 1; a[2] = 2; dfs(3); // printf("cnt = %d\n", cnt); for(int i = 0; ; ++i) { if((ans + i * mod) % cnt == 0) { write((ans + i * mod) / cnt); return 0; } } return 0; } 还是搜索啊~
About The Author
bjmayor
程序员，码农，php,python,ios,android,go，产品经理，创业。