牛客周赛 Round 61(思维、组合数)

牛客周赛 Round 61(思维、组合数)

整体不是很难，想明白细节即可。

A. Letter Song ~ 致十年后的我们

注意题意，不考虑闰年，直接Y+10即可。

#include<bits/stdc++.h>using namespace std;int main(){int a, b, c;scanf("%d-%d-%d", &a, &b, &c);printf("%d-%02d-%02d\n", a+10, b, c);return 0;
}

B. 简单图形问题 - 0123

显然，边长是整数的等边三角形，面积不可能为整数。只需要判断是否为正方形即可。

#include<bits/stdc++.h>using namespace std;int main(){int ncase;cin >> ncase;while(ncase--){long long n;cin >> n;long long a = sqrt(n);if(a * a == n) cout << 0 << endl;else cout << 3 << endl;}return 0;
}

C. 小红的机器人构造 - Ⅰ+Ⅱ+Ⅲ(思维，组合数)

1. 对于UD 和 LR是两个相对独立的维度，互不影响，可以分开考虑。
2. 对于是否能达到目标点，用 x 轴方向举例：
   • X < 0 时，一个指令D 可以让 X - 1，判断 D 的个数是否大于等于 |X| 即可
   • X > 0 时，一个指令U 可以让 X + 1, 判断 U 的个数是否大于等于 |X| 即可
   • 同理，判断 y轴是否满足。如果 x 和 y 同时满足，则为YES。
3. 对于YES的情况，考虑方案数，用 x 轴方向举例：
   • 设 $C_X$ 表示指令X必须保留的个数。
   • X < 0 时，说明必须保留 |X| 个指令 D，此时 $C_D=|X|$，$C_U=0$。
   • X > 0 时，说明必须保留 |X| 个指令 U，此时 $C_U=|X|$，$C_D=0$。
   • 除必须要保留的指令外，剩下的指令 U 和指令 D 需要考虑删除。
   • 设$V(X) = $ 指令 X 的个数 ， $cnt(X)=V(X)-C_X$ ，即 $cnt(X)$ 表示指令X最多要删除的个数。
   • 显然，多保留一个指令 U，就需要多保留一个指令 D。枚举每一种多保留指令的情况，即可。
   • 设 $cnt(U)>cnt(D)$，$cur=cnt(U)-cnt(D)$，其中 $cur$ 就表示 U 必须要删除的指令个数，其他的均可以选择保留一对UD or 删除。
   • 在这种情况下，在 x 轴方向上，贡献的方案数为：${\sum }_0^{cnt(D)}C[V(D),i]\ast C[V(U),i+cur]$，其中 $C[X,Y]$ 表示在 X 中选择 Y 个组合数。
   • 当 $cnt(D)>cnt(U)$ 时，贡献的方案同时。
   • 在 y 轴方向上，贡献的方案同上。
   • 最终答案 = x 轴方向贡献的方案 * y 轴方向贡献的方案。

#include<bits/stdc++.h>
#define ll long long
using namespace std;const ll mod = 1e9 + 7;
const int maxn = 1e6 + 5;
const string op = "UDRL";ll qpow(ll a, ll b){	// 快速幂ll res = 1;while(b){if(b & 1) res = res * a % mod;a *= a;a %= mod;b >>= 1;}return res;
}ll f[maxn], p[maxn];
ll C(ll a, ll b){	// 计算C(a,b)return f[a] * p[b] % mod * p[a-b] % mod;
}int main(){f[0] = 1;for(int i = 1; i < maxn; i++) f[i] = f[i-1] * i % mod;for(int i = 0; i < maxn; i++) p[i] = qpow(f[i], mod-2); // 费马小定理求逆元int ncase;cin >> ncase;while(ncase--){int n, x, y;cin >> n >> x >> y;string s, ss;cin >> s;ll u = 0, d = 0, l = 0, r = 0;map<char, ll> v;for(auto c : s){if(c == 'U' && x > 0) x--, ss = ss + c; else if(c == 'U') u++;else if(c == 'D' && x < 0) x++, ss = ss + c; else if(c == 'D') d++;else if(c == 'L' && y < 0) y++, ss = ss + c; else if(c == 'L') l++;else if(c == 'R' && y > 0) y--, ss = ss + c; else r++;v[c]++;}if(x != 0 || y != 0) cout << "NO" << endl; // 判断是否可以走到终点else{cout << "YES " << ss << " "; // 当前的ss是最小串，即udlr是最多删除 ll cnt1 = 0, cnt2 = 0;if(u < d) swap(u, d), swap(v['U'], v['D']); // D > U时，交换即可，对于计算方案数ll cur = u - d;for(ll i = 0; i <= d; i++){ll tmp = C(v['U'], i+cur) * C(v['D'], i) % mod;cnt1 = (cnt1 + tmp) % mod;}if(l < r) swap(l, r), swap(v['L'], v['R']); // 同上cur = l - r;for(int i = 0; i <= r; i++){ll tmp = C(v['L'], i+cur) * C(v['R'], i) % mod;cnt2 = (cnt2 + tmp) % mod;}ll res = cnt1 * cnt2 % mod;cout << res << endl;} }return 0;
}

D. 小红的差值构造 - easy+hard+extreme (思维)

看极限版本的数据范围，显然是结论题。

对于 l > n 的情况，显然把 y 或 x 落在 n 的中间是最佳的。

对于 l < n 的情况，把 l+1 这个区间和 n 这个区间的中间重叠时为最佳。

对于上述两种情况，可以选择几组（n，l），手动移动一下重叠区间即可，注意考虑奇偶。

#include<bits/stdc++.h>
#define ll long long
using namespace std;int main(){int ncase;cin >> ncase;while(ncase--){ll n, l;cin >> n >> l;l++;if(l > n){ll x = (n+1) / 2;cout << x - l + 1 << " " << x << " " << x * (x-1) + ((n&1) ? 0 : x) << endl;}else{ll x = (n - l) / 2;ll res = (x+1) * x + ((n-l) & 1 ? x+1 : 0);ll t = (l - 2) / 2;res = res + (t+1) * t + ((l-2) & 1 ? t+1 : 0);cout << n/2-t+1 << " " << n/2-t+1 + l - 1 << " " << res << endl;}}return 0;
}