送温暖场。
最后一题没写纯属脑抽了。
A - Omkar and Bad Story
不难发现有负数时一定无解。其余时候最简单的构造就是输出 (0,1,2,cdots,200)。
时间复杂度 (O(n))。
code
#include <bits/stdc++.h>
const int MX = 1e5 + 23;
void solve(){
int n; std::cin >> n;
int ok = 1;
for(int i = 1 ,r = 0; i <= n ; ++i){
std::cin >> r;
if(r < 0) ok = 0;
}
if(!ok){
puts("NO");
return ;
}
puts("YES
201");
for(int i = 0 ; i <= 200 ; ++i)
printf("%d%c" ,i ,"
"[i == 200]);
}
int main(){
int T;
std::cin >> T;
while(T--) solve();
return 0;
}
B - Prinzessin der Verurteilung
只会暴力，显然字符串长度不会超过 (3)，且长度为 (n) 的字符串最多有 (O(n^2)) 个不同子串，直接枚举即可。
时间复杂度 (O(n^2))。
code
#include <bits/stdc++.h>
const int MX = 1e5 + 23;
char ok1[26][26][26];
char ok2[26][26];
char ok3[26];
void solve(){
int n; std::cin >> n;
std::string s; std::cin >> s;
for(int i = 0 ; i < n ; ++i){
ok3[s[i] - 'a'] = 1;
if(i >= 1) ok2[s[i - 1] - 'a'][s[i] - 'a'] = 1;
if(i >= 2) ok1[s[i - 2] - 'a'][s[i - 1] - 'a'][s[i] - 'a'] = 1;
}
for(int i = 0 ; i < 26 ; ++i){
if(!ok3[i]){
printf("%c
" ,'a' + i);
goto end;
}
}
for(int i = 0 ; i < 26 ; ++i){
for(int j = 0 ; j < 26 ; ++j){
if(!ok2[i][j]){
printf("%c%c
" ,'a' + i ,'a' + j);
goto end;
}
}
}
for(int i = 0 ; i < 26 ; ++i){
for(int j = 0 ; j < 26 ; ++j){
for(int k = 0 ; k < 26 ; ++k){
if(!ok1[i][j][k]){
printf("%c%c%c
" ,'a' + i ,'a' + j ,'a' + k);
goto end;
}
}
}
}
end:
for(int i = 0 ; i < n ; ++i){
ok3[s[i] - 'a'] = 0;
if(i >= 1) ok2[s[i - 1] - 'a'][s[i] - 'a'] = 0;
if(i >= 2) ok1[s[i - 2] - 'a'][s[i - 1] - 'a'][s[i] - 'a'] = 0;
}
}
int main(){
int T;
std::cin >> T;
while(T--) solve();
return 0;
}
C - Diluc and Kaeya
好神的题。
- 首先这个比率一定是确定的值，每部分比率相同，所以应当每一段都等于全局的比率即 (frac{cnt_0}{cnt_1})。
- 贪心能分就一定会分成两部分。
故我们可以写出如下代码。
复杂度 (O(n log n))（使用了 map）。
code
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define LL long long
const int MX = 5e5 + 23;
char s[MX];
int cnt[MX];
std::map<LL ,int> mp;
int gcd(int a ,int b){return b ? gcd(b ,a % b) : a;}
void solve(){
mp.clear();
int n; std::cin >> n;
scanf("%s" ,s + 1);
for(int i = 1 ; i <= n ; ++i){
cnt[i] = cnt[i - 1] + (s[i] == 'D');
int a = 0 ,b = 0;
int c = gcd(cnt[i] ,i - cnt[i]);
a = cnt[i] / c ,b = (i - cnt[i]) / c;
LL id = a * 1000000LL + b;
printf("%d%c" ,++mp[id] ,"
"[i == n]);
}
}
int main(){
int T;
std::cin >> T;
while(T--) solve();
return 0;
}
D - Omkar and Medians
记得有谁讲过这个套路。
考虑每一回合的中位数的变化趋势，应该是要么不变，要么变成比它大/小的第一个数。
故可以写出如下代码：
时间复杂度 (O(n log n))。
code
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
const int MX = 2e5 + 23;
int a[MX];
void solve(){
int n; std::cin >> n;
std::set<int> S;
int las = 0;
int ok = 1;
for(int i = 1 ,cur ; i <= n ; ++i){
std::cin >> cur;
if(i == 1) ;
else{
if(cur == las) continue;
if(cur > las){
auto k = S.upper_bound(las);
if(k == S.end() || cur <= *k){
;
}
else{
ok = 0;
}
}
if(cur < las){
auto k = S.lower_bound(las);
if(k == S.begin() || *std::prev(k) <= cur){
;
}
else ok = 0;
}
}
S.insert(cur);
las = cur;
}
puts(ok ? "YES" : "NO");
}
int main(){
int T;
std::cin >> T;
while(T--) solve();
return 0;
}
E - Omkar and Forest
简单题，不懂为啥放这位置。
不难发现，如果原图中存在一个非 0 位置，那么整张地图就是确定的。方案即 (2^w)，(w) 为 # 的数量。
否则全图都是 #，此时答案是 (2^w-1)。
时间复杂度 (O(nm))。
code
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define LL long long
const int MX = 2000 + 3;
const LL MOD = 1e9 + 7;
LL qpow(LL a ,LL b ,LL p = MOD){
LL ans = 1;
while(b){if(b & 1) ans = ans * a % p;
a = a * a % p ,b >>= 1;
}return ans;
}
char str[MX][MX];
void solve(){
int n ,m;
std::cin >> n >> m;
int possible = 0;
for(int i = 1 ; i <= n ; ++i){
scanf("%s" ,str[i] + 1);
for(int j = 1 ; j <= m ; ++j){
possible += str[i][j] == '#';
}
}
if(possible == n * m){
printf("%lld
" ,qpow(2 ,possible) - 1);
}
else{
printf("%lld
" ,qpow(2 ,possible));
}
}
int main(){
int T;
std::cin >> T;
while(T--) solve();
return 0;
}
F - Omkar and Akmar
也是个简单题。
打表/手玩/归纳法证明：不论怎么操作都是后手必胜，所以游戏等价于他们随便乱放的方案数。
枚举最终的方案中的空格数量，假设确定了图中任意一个位置是填 A 还是 B，那么其余要填的 AB 就已经被确定了。
现在就只要对放空格的方案计数了。加入要放 (i) 个则答案是 (inom{n-i}{i}+inom{n-i-1}{i-1})。为何？
先不考虑环，我们把每一个空格都与前面的位置缩成一个，还原方案就是选择某些位置把它展开成两个，此部分方案数 (inom{n-i}{i})。
发现我们漏算的是开头的位置作为空位的方案数，我们按照同样的思路补算即可，此部分方案数 (inom{n-i-1}{i-1})。
然后我们还需要乘以 ((n-i)!)。
注意一点是，空位的奇偶性是确定的，不合法的方案不能算上
时间复杂度 (O(n))。
code
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define LL long long
#define int long long
const int MX = 1e6 + 23;
const LL MOD = 1e9 + 7;
int win[MX][2][2] ,fac[MX] ,inv[MX];
void init(){
fac[0] = 1 ,inv[0] = inv[1] = 1;
for(int i = 1 ; i < MX ; ++i) fac[i] = 1LL * fac[i - 1] * i % MOD;
for(int i = 2 ; i < MX ; ++i) inv[i] = 1LL * (MOD - MOD / i) * inv[MOD % i] % MOD;
for(int i = 2 ; i < MX ; ++i) inv[i] = 1LL * inv[i] * inv[i - 1] % MOD;
}LL C(int n ,int m){return 1LL * fac[n] * inv[m] % MOD * inv[n - m] % MOD;}
LL calc(int n ,int k){
return (C(n - k ,k) + C(n - k - 1 ,k - 1)) % MOD;
}
signed main(){
init();
int n; std::cin >> n;
int ans = 0;
if(n % 2 == 0){
ans = (ans + 2LL * fac[n]) % MOD;
}
for(int i = 1 + (n % 2 == 0) ; 2 * i <= n ; ++i){
LL way = calc(n ,i);
if((i & 1) == (n & 1)) ans = (ans + 2LL * fac[n - i] % MOD * way) % MOD;
}
printf("%lld
" ,ans);
return 0;
}
总结
简单场，