牛客 CSP-S 提高组赛前集训营 1 题解

体验还是比较好的 230 只有 100 名差评,没有享受到大样例x

# 比赛实录

6:30:看 T1,这个博弈我好像推不出来SG,这是 ICG 吗?

滚去看 T2,理解题意 5min ,这个乘积怎么维护啊。。。

DP式子推推搞搞搞

宋神 A T1 了

继续搞搞搞

过样例了

跑一组大数据

woc 忘记取模了

修修修

怎么还是负数x

%= 写成 %

终于得到一个看起来还不错的结果

宋神也写完 T2 了

传过去,对拍ing

过了.jpg

宋神 T1 代码传我

搞 T3

这个数据结构我不会啊。。

诶,这好像是图论

边连一连搞搞环行不行啊 这不就是正解吗 QAQ

好像不行x

拿个网络流板子写个 30pt

要下课了第四个数据不写了x

回寝室,10:03看榜,竟然没挂分,怎么只有 100 名 QAQ

# 题解

# 仓鼠的石子游戏

先讨论一堆

石子数为 11 时先手赢, 否则后手赢

可以想成 >1>1 时,先手作出了操作,后手一定有方案应对,最后肯定是先手不能放

扩展到 nn

for(int i = 1; i <= n; ++i)
s ^= (a[i] == 1);
cout << (s?"rabbit\n":"hamster\n");

# 乃爱与城市拥挤程度

fu,if_{u,i}uu 的子树中,k=ik=i 时有多少座城市中的人会认为乃爱天下第一(第一行答案)

hu,ih_{u,i}uu 的子树中,k=ik=i 时受到影响城市的拥挤程度的乘积(第二行答案)

fu,i=1+uvfv,i1 f_{u,i}=1+\sum_{u\rightarrow v} f_{v,i-1}
hu,i=fu,iuvhv,i1 h_{u,i}=f_{u,i}\cdot \prod_{u\rightarrow v} h_{v,i-1}

我写的是换根,不会 up and down QAQ

topfutopf_u 表示除去子树 uu 后,把 uu 的父节点作为根得到的 fftophtoph 同理

topfv,i=fu,i+topfu,i1fv,i1 topf_{v,i}=f_{u,i}+topf_{u,i-1}-f_{v,i-1}
tophv,i=tophu,i1hu,ihv,i1topfu,i1+fu,ifv,i1fu,i toph_{v,i}=\frac{toph_{u,i-1}h_{u,i}}{h_{v,i-1}}\cdot \frac{topf_{u,i-1}+f_{u,i}-f_{v,i-1}}{f_{u,i}}

# 小w的魔术扑克

将数字看作节点,牌看作无向边

考虑一个有 nn 个点,mm 条边的连通块

mnm\ge n 时,连通块的点都可以选中

m=n1m=n-1 时,必有一个点不能被选中

由于询问的是连续值域,所以只要记录每个连通块的最大值和最小值

若存在一个连通块的最大值和最小值都在询问区间中,就是 No,否则是 Yes

对于这种询问可以离线询问,把询问和连通块按照右端点排序,只要维护 maxlmaxl 即可

# Code

A

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl;
using std::make_pair; using std::pair; typedef pair<int, int> pii;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull;

const int N = 1e3 + 10;
int a[N];

int main() {
#ifdef LOCAL
freopen("input", "r", stdin);
#endif
std::ios::sync_with_stdio(0); cout.tie(0);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
rep(i, 1, n) cin >> a[i];
int s = 0;
rep(i, 1, n) s ^= (a[i] == 1);
cout << (s?"rabbit\n":"hamster\n");
}
return 0;
}

B

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl;
using std::make_pair; using std::pair; typedef pair<int, int> pii;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull;

struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
inline char gc() {
#if DEBUG //调试,可显示字符
return getchar();
#endif
if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
return p1 == p2 ? -1 : *p1++;
}
inline bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
template <class T>
inline void read(T &x) {
register double tmp = 1;
register bool sign = 0;
x = 0;
register char ch = gc();
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
if (ch == '.')
for (ch = gc(); isdigit(ch); ch = gc()) tmp /= 10.0, x += tmp * (ch - '0');
if (sign) x = -x;
}
inline void read(char *s) {
register char ch = gc();
for (; blank(ch); ch = gc())
;
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
}
inline void read(char &c) {
for (c = gc(); blank(c); c = gc())
;
}
inline void push(const char &c) {
#if DEBUG //调试,可显示字符
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <class T>
inline void write(T x) {
if (x < 0) x = -x, push('-'); // 负数输出
static T sta[35];
T top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) push(sta[--top] + '0');
}
inline void write(const char *s) {
while (*s != '\0') push(*(s++));
}
template <class T>
inline void write(T x, char lastChar) {
write(x), push(lastChar);
}
} io;

const int N = 1e5 + 10, p = 1e9+7;

int n, K;
std::vector<int> g[N];
int f[N][12];
ll h[N][12];

int inv(ll a){
ll ret = 1;
int n = p - 2;
while(n){
if (n&1) (ret *= a) %= p;
(a *= a) %= p;
n >>= 1;
}
return ret;
}

void dfs1(int u, int fa){
// cerr << u << endl;
rep(k, 0, K) f[u][k] = h[u][k] = 1;
if (g[u].size() == 1 && fa != 0) return;

for (auto v : g[u]){
if (v == fa) continue;
dfs1(v, u);
rep(k, 1, K){
f[u][k] += f[v][k-1], (h[u][k] *= h[v][k-1])%=p;
}
}
rep(k, 0, K) (h[u][k] *= f[u][k])%=p;
}

int ans1[N]; ll ans2[N];
int topf[N][12], tmpf[12];
ll toph[N][12];

void calc(int u, int fa){
ans1[u] = topf[u][K-1] + f[u][K];
ans2[u] = h[u][K] * toph[u][K-1] % p * ans1[u] % p * inv(f[u][K]) % p;
tmpf[0] = 1;
for(auto v : g[u]){
if (v == fa) continue;
topf[v][0] = 1;
rep(k, 1, K) topf[v][k] = f[u][k] + topf[u][k-1] - f[v][k-1];

toph[v][0] = 1;
rep(k, 1, K){
toph[v][k] = toph[u][k-1] * h[u][k] % p * (topf[u][k-1] + f[u][k] - f[v][k-1]) % p * inv(h[v][k-1]) % p * inv(f[u][k]) % p;
}
}

for(auto v : g[u]){
if (v == fa) continue;
calc(v, u);
}
}

int main() {
#ifdef LOCAL
freopen("input", "r", stdin);
#endif
std::ios::sync_with_stdio(0); cout.tie(0);

// cin >> n >> K;
io.read(n), io.read(K);
rep(i, 2, n){
int u, v;
io.read(u), io.read(v);
g[u].push_back(v), g[v].push_back(u);
}

dfs1(1, 0);

// rep(k, 0, K){
// rep(i, 1, n)
// cerr << f[i][k] << ' '; cerr << endl;
// }
// rep(k, 0, K){
// rep(i, 1, n)
// cerr << h[i][k] << ' '; cerr << endl;
// }

rep(k, 0, K) toph[1][k] = 1;
calc(1, 0);

// rep(k, 0, K) cerr << toph[2][k] << ' '; cerr << endl;

rep(i, 1, n)
// cout << ans1[i] << ' ';
io.write(ans1[i], ' ');
// cout << endl;
io.push('\n');
rep(i, 1, n)
io.write(ans2[i], ' ');
// cout << ans2[i] << ' ';
// cout << endl;
io.push('\n');
return 0;
}

C

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl;
using std::make_pair; using std::pair; typedef pair<int, int> pii;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull;
const int N = 1e5 + 10;
int fa[N];
int getf(int x){ return (x == fa[x])?x:(fa[x]=getf(fa[x])); }
std::vector<int> g[N];
int tag[N], min, max;
void dfs(int u){
min = std::min(min, u);
max = std::max(max, u);
tag[u] = 1;
for(auto v : g[u]) if (!tag[v]) dfs(v);
}
struct A{
int l, r, id;
A(){ l = r = id = 0; }
A(int l, int r, int id){ this->l = l, this->r = r, this->id = id; }
};
int ans[N];
bool cmp_r_A(const A& a, const A& b){ return a.r < b.r; }
bool cmp_r_pii(const pii& a, const pii& b){ return a.second < b.second; }
int main() {
#ifdef LOCAL
freopen("input", "r", stdin);
#endif
std::ios::sync_with_stdio(0); cout.tie(0);
int n, k; cin >> n >> k; rep(i, 1, n) fa[i] = i;
std::vector<int> loop;
rep(i, 1, k){
int u, v;
cin >> u >> v;
if (getf(u) == getf(v)){
loop.push_back(u);
} else {
fa[getf(u)] = getf(v);
g[u].push_back(v), g[v].push_back(u);
}
}
for(auto u : loop)
if (!tag[u]) dfs(u);
std::vector<pii> seg;
rep(u, 1, n){
if (!tag[u]) {
min = n + 1, max = 0;
dfs(u);
assert(min <= n);
assert(max > 0);
seg.push_back({min, max});
}
}
int q;
cin >> q;
std::vector<A> ask;
rep(i, 1, q){
int u, v; cin >> u >> v;
if (u > v) std::swap(u, v);
ask.push_back(A(u, v, i));
}
std::sort(seg.begin(), seg.end(), cmp_r_pii); std::sort(ask.begin(), ask.end(), cmp_r_A);
for(int i = 0, j = 0, maxl = 0; i < ask.size(); ++i){
for(; j < seg.size() && seg[j].second <= ask[i].r; ++j) maxl = std::max(maxl, seg[j].first);
if (maxl >= ask[i].l) ans[ask[i].id] = 1;
}
rep(i, 1, q) cout << (ans[i]?"No\n":"Yes\n");
return 0;
}