感谢 B 题与 J 题的出题人0x3ea 与参与验题的小伙伴，同时感谢老师给予的出题机会以及各位同学的参与。
A：Misaki 与 奇偶数
思路：对于奇偶数的定义是前五位加起来为奇数，后五位加起来为偶数，前5位的取值范围为 ，后五位的取值范围为
枚举统计一下符合要求的数量，取二者之积即可。
标程：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check(ll x){
int sum = 0;
while (x) {
sum += x % 10;
x /= 10;
}
return (sum & 1 ? 1 : 0);//判断奇数偶数
}
void solve(){
ll odd = 0, even = 0;
for(int i = 10000; i <= 99999; i ++){
if(check(i)) even ++;
}
for(int i = 0; i <= 99999; i ++){
if(!check(i)) odd ++;
}
cout << even * odd << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
// cin >> t;
while(t --){
solve();
}
return 0;
}
当然本题是填空题，直接输出答案也可以。
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cout << 2250000000 << '\n';
return 0;
}
B：Misaki 与 密码
思路：按照题意模拟枚举子串的头部尾部即可，注意检验给出的几个条件
标程：
#include<iostream>
using namespace std;
int main(){
cout << 1212 << '\n';
return 0;
}
C：Misaki 与 无限斯达
思路：按照题意模拟即可
标程：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
ll n, m, k, t;
cin >> n >> m >> k >> t;
ll ans = 0;
if(k >= m){
ans += k / m;
k %= m;
}
t = t / n;
for(int i = 1; i <= t; i ++){
k *= 2;
ans += k / m;
k %= m;
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t --){
solve();
}
return 0;
}
D：Misak 与 阶乘
思路：能想到，一个数的末尾 0 都是由因子 2 与因子 5 所提供的，N 的阶乘中因子 2 的数量肯定是足够多的，所以就统计因子 5 的数量即可，最后因为是平方，所以 0 的数量是 5 的因子数量乘以 2 。
标程：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
ll n, m;
cin >> n >> m;
ll ans = 0;
while(n){
ans += n / 5;
n /= 5;
}
ans *= 2;
cout << (ans == m ? "YES\n" : "NO\n");
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t --){
solve();
}
return 0;
}
E：Misaki 与 空竞集训
思路：根据题意，只有在同一个队伍并且性别相同的队员才能住在一起，所有先判断一个队伍是否能住一个双人间，分别用sum1, sum2记录能住的双人间数量和单人间数量。最后要考虑单人全住双人间或者单人间，以及能住双人间的全住双人间，能住单人间的在双人间和单人间选便宜的住。
标程：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
ll n, c1, c2;
cin >> n >> c1 >> c2;
ll sum1 = 0, sum2 = 0;
for(int i = 1; i <= n; i ++){
string s;
cin >> s;
if(s[0] == s[1] || s[0] == s[2] || s[1] == s[2]){
sum1 ++;
sum2 ++;
}
else sum2 += 3;
}
ll ans = min(n * 3 * c1, n * 3 * c2);
ans = min(ans, sum1 * c2 + sum2 * min(c1, c2));
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t --){
solve();
}
return 0;
}
F：Misaki 与 十一进制
思路：一个数是否是 5 的倍数其实只和它的个位数是不是 0 或者 5，可以发现，11 的末尾固定是1，所以说答案其实就是
对 5 取模是不是0。
标程：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
ll n;
cin >> n;
ll ans = 0;
for(int i = 1; i <= n; i ++){
ll a1, a2;
char b;
cin >> a1 >> b;
if(b != 'A') a2 = (b - '0');
else a2 = 10;
ans = (ans + a1 * a2) % 5;
}
if(ans == 0) cout << "YES\n";
else cout << "NO\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t --){
solve();
}
return 0;
}
G：Misaki 与 贪吃蛇
思路：枚举删除的左端点，二分右端点位置，关键是二分的check方式，很容易想到这个是满足二分性的。假设字符串长度为n，删除的子串是 s[l, r] ，那么 如果这个删除方案是合法的时候，s[1, l - 1] + s[r + 1, n] 的字符种类数大于 2 ，那么这个可以用 26 个前缀和维护一下，每次 check 检查 26 种字母在 s[1, l - 1] 和 s[r + 1, n] 是否出现过，如果出现至少两种字母，那么这次的 check 就是成功的。
标程：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cal(char c){
return c - 'a' + 1;
}
void solve(){
string s;
cin >> s;
ll n = s.size();
vector<ll> sum(28);
vector<vector<ll>> pre(28, vector<ll>(n + 1));
for(int i = 1; i <= n; i ++){
ll x = cal(s[i - 1]);
sum[x] ++;
for(int j = 1; j <= 26; j ++){
pre[j][i] = sum[j];
}
}
ll ans = 0;
set<ll> st;
for(int i = 1; i <= n; i ++){
ll x = cal(s[i - 1]);
st.insert(x);
auto check =[&](ll mid) -> bool{
set<ll> sp;
for(int j = 1; j <= 26; j ++){
ll yu1 = pre[j][i - 1];
ll yu2 = pre[j][n] - pre[j][mid];
if(yu1 || yu2) sp.insert(j);
}
return (sp.size() >= 2 ? true : false);
};
ll l = i, r = n;
while(l < r){
ll mid = l + r + 1 >> 1ll;
if(check(mid)) l = mid;
else r = mid - 1;
}
if(check(l)) ans += l - i + 1;
if(st.size() == 2){
ll yu = n - i;
ans += yu * (yu + 1) / 2;
break;
}
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t --){
solve();
}
return 0;
}
H：Misaki 与 魔大大
题意：这里需要转换一下思路，考虑从最终状态往前推，先记录所有的操作，对于每一行/列的操作，只有最后一次操作是有效的，从后往前推，记录n, m等于初始的行数和列数，如果该行/列的最后一次操作为火焰攻击，那么火焰地块加上 n/m 。但是如果第 i 行的最后一次操作之后，列的有效数量就要 - 1，第 i 列的操作同理。最后初始的 n * m 减去火焰地块数量即可。
标程：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
ll n, m, q;
cin >> n >> m >> q;
ll sum = n * m;
vector<ll> r(m + 1), l(n + 1);
vector<array<ll, 3>> op(q + 1);
for(int i = 1; i <= q; i ++){
string s1, s2;
ll x;
cin >> s1 >> s2 >> x;
if(s2 == "row"){
if(s1 == "flame") op[i] = {1, x, 1};
else op[i] = {1, x, 0};
}
else{
if(s1 == "flame") op[i] = {0, x, 1};
else op[i] = {0, x, 0};
}
}
ll ans = 0;
for(int i = q; i >= 1; i --){
auto [x, y, z] = op[i];
if(x == 0){
if(r[y]) continue;
r[y] = 1;
if(z) ans += n;
m --;
}
else{
if(l[y]) continue;
l[y] = 1;
if(z) ans += m;
n --;
}
}
cout << sum - ans << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t --){
solve();
}
return 0;
}
I：Misaki 与 空中回弹
思路：其实本体就是稍微变化一下的LIS问题，假设 ans[i] 是以第 i 个数开头的最长上升子序列，这里可以从后往前维护，初始化 ans[n] 为1，假设当前在第 i 个节点，那么 ans[i] 就是所有满足 的 ans[j] 的最大值，那么这个查询该怎么维护呢？
办法就是线段树维护，先开一棵有 n 个叶子节点的空树，每次查询到 ans[i] 之后把 segmenttree[h[i]] 修改为 ans[i] 即可。
标程：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segtree{
ll n;
vector<ll> a;
segtree(ll _n) : n(_n * 4 + 10), a(n) {}
void pushup(ll u){
a[u] = max(a[u * 2], a[u * 2 + 1]);
}
void modify(ll u, ll l, ll r, ll idx, ll val){
if(l == idx && r == idx){
a[u] = val;
}
else{
ll mid = l + r >> 1ll;
if(idx <= mid) modify(u * 2, l, mid, idx, val);
else modify(u * 2 + 1, mid + 1, r, idx, val);
pushup(u);
}
}
ll query(ll u, ll l, ll r, ll ql, ll qr){
if(ql <= l && r <= qr){
return a[u];
}
else{
ll mid = l + r >> 1ll;
ll ans = 0;
if(ql <= mid) ans = max(ans, query(u * 2, l, mid, ql, qr));
if(r > mid) ans = max(ans, query(u * 2 + 1, mid + 1, r, ql, qr));
return ans;
}
}
};
void solve(){
ll n;
cin >> n;
vector<ll> h(n + 1), ans(n + 1);
for(int i = 1; i <= n; i ++) cin >> h[i];
segtree seg(n);
ans[n] = 1;
seg.modify(1, 1, n, h[n], 1);
for(int i = n - 1; i >= 1; i --){
ans[i] = seg.query(1, 1, n, h[i], n) + 1;
seg.modify(1, 1, n, h[i], ans[i]);
}
for(int i = 1; i <= n; i ++) cout << ans[i] - 1 << ' ';
cout << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
cin >> t;
while(t --){
solve();
}
return 0;
}
J：Masaya 与 赛前改造
思路：首先，如果 那么成功的概率必定是0。
否则的话， 次内改造成功的概率 = 恰好1次改造成功的概率 + ... + 恰好
次改造成功的概率
考虑怎样求恰好 次改造成功的概率。
恰好 次改造成功的概率,就是恰好
次改造成功案数 * 发生这种情况的概率
因为改造成功后立刻停止,所以第 次改造一定是成功的
在前 次改造中，有
次改造成功，
次改造失败，恰好
次改造成功的方案数就是：
，
每一种方案成功的概率就是：
那么总的成功的概率就是：
累加求和即可，注意需要特判改造次数小于 的情况。
标程：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010, mod = 1e9 + 7;
const int Mod = 1e9 + 7, INF = 0x3f3f3f3f;
ll fac[N], inv[N];
ll fastpow(ll a, ll n){
ll base = a, res = 1;
while(n){
if(n & 1) res = (res * base) % mod;
base = (base * base) % mod;
n >>= 1;
}
return res;
}
ll Inv(ll a){
return fastpow(a, mod - 2);
}
ll C(ll n, ll m){
if(n < 0 || m < 0 || n < m) return 0;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void init(ll n){
fac[0] = 1;
for(int i = 1; i <= n; i ++) fac[i] = (i * fac[i - 1]) % mod;
inv[n] = Inv(fac[n]);
for(int i = n - 1; i >= 0; i --) inv[i] = inv[i + 1] * (i + 1) % mod;
}
void solve(){
ll n, x;
cin >> n >> x;
if(n < x) cout << 0 << '\n';
else{
ll ans = 0, INV = Inv(x);
for(int i = x; i <= n; i ++){
ll now = 1;
now = now * fastpow(INV, x - 1) % mod;
now = now * fastpow(x - 1, i - x) % mod * fastpow(INV, i - x) % mod;
now = now * C(i - 1, i - x) % mod;
now = (now * INV) % mod;
ans = (ans + now) % mod;
}
cout << ans << '\n';
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
init(1000000);
cin >> t;
while(t --){
solve();
}
return 0;
}
京公网安备 11010502036488号