题解 | 牛客周赛 Round 129
A.小红的大小判断
特判1即可
void solve(){
int n;
cin >> n;
if(n == 1) cout << "equal" << endl;
else cout << "right" << endl;
}
B.小红的大小再判断
先使用reverse(),后用compare()判断即可
void solve(){
string a;
cin >> a;
string b = a;
reverse(b.begin(), b.end());
if(a.compare(b) == 0) cout << "equal";
else if(a.compare(b) < 0) cout << "right";
else cout << "left";
}
C.小红的肥鹅健身房
使用map记录非空元素，后使用set更新非空元素
void solve(){
ll n, m, k, ans = 0, cnt = 0;
cin >> n >> m >> k;
ll mx = -1;
map mp;
set b;
for(int i = 1; i <= n * m; ++i) {
ll t;
cin >> t;
mp[t]++;
if(t != 0) b.insert(t);
}
for(auto i : b){
if(mp[i] > 1) {
cnt += mp[i] / 2;
mp[i + 1] += mp[i] / 2;
if(i + 1 >= k) ans += mp[i] / 2;
b.insert(i + 1);
}
}
cout << cnt << ' ' << ans;
}
D.小红的神秘密码解锁
翻转的结果只与翻转的左边界和右边界有关
如果如果左边界l,a[l] != a[l - 1]那么在翻转之后颜色块将会加一，a[l] == a[l - 1] 在翻转之后颜色块将会减一，右边界同理
至于要预处理一下即可，后计算有多少种可能性
最后加上整体翻转即加一
void solve(){
string a;
cin >> a;
ll cnt1 = 0, cnt2 = 0;
for(int i = 0; i < a.size() - 1; ++i) {
if(a[i] == a[i + 1]) cnt1++;
else cnt2++;
}
ll ans = cnt1 * cnt2 + 1;
cout << ans << endl;
}
E.小红的多维空间冒险
考虑将每一维拆出来，当且仅当 u≠v时对距离有贡献。
所以贡献为 11 的 (u,v) 情况有 (0,1) 和 (1,0)，贡献为 0 的情况的有 (0,0) 和 (1,1)
对于 ans=k的情况，其方案有 C(n,k)⋅2^n，由于 u,v 和 v,u作为同一种情况，所以要最后除以 2
ll mod = 1e9 + 7;
vector fac(1e6 + 5);
//快速幂
ll quickpow(ll a, ll b){
ll ret = 1;
while(b) {
if(b & 1) ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret;
}
//逆元 费马小定理
ll inv(ll x){
return quickpow(x, mod - 2);
}
//组合数计算
ll c(ll a, ll b) {
if(a < b) return 0;
return fac[a] * inv(fac[b]) % mod * inv(fac[a - b]) % mod;
}
void solve(){
fac[0] = 1;
for(int i = 1; i<= 1e6 + 4; ++i)
fac[i] = fac[i - 1] * i % mod;
ll n;
cin >> n;
for(ll k = 1; k <= n; ++k) {
ll ans = c(n, k) % mod * quickpow(2, k) % mod * quickpow(2, n - k) % mod;
ans = ans * inv(2) % mod;
cout << ans << ' ';
}
}
F.小红的魔法树探险
首先进行建树
写出计算期望的式子，为高中课本知识便不多赘述
而后根据题意写出dfs函数
而后进行书上dfs
ll ans = 0, mod = 1e9 + 7;
vector fac(1e6 + 5);
//快速幂
ll quickpow(ll a, ll b){
ll ret = 1;
while(b) {
if(b & 1) ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret;
}
//逆元 费马小定理
ll inv(ll x){
return quickpow(x, mod - 2);
}
void dfs(ll u, ll fa, ll s, ll dep, vector> &g) {
s *= inv(g[u].size());
s %= mod;
if(u > 1) {
ans += s * dep % mod;
ans %= mod;
}
for(auto & v : g[u]) {
if(v == fa) continue;
dfs(v, u, s, dep + 1, g);
}
s *= g[u].size();
s %= mod;
}
void solve(){
fac[0] = 1;
for(int i = 1; i<= 1e6 + 4; ++i)
fac[i] = fac[i - 1] * i % mod;
int n;
cin >> n;
vector> g(n + 1);
for(ll i = 1, u, v; i < n; ++i) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0, 1, 1, g);
cout << ans << endl;
}
有任何问题欢迎大家指出^-^
