A - T-shirt
Code
void solve()
{
int a, b, c, x;
cin >> a >> b >> c >> x;
if(x <= a) printf("%.12lf\n", 1.0);
else if(x <= b)
{
double res=c;
res /= (b-a);
printf("%.12lf\n",res);
}
else printf("%.12lf\n",0.0);
}
B - Minimize Ordering
Code
void solve()
{
string s; cin >> s;
sort(s.begin(), s.end());
cout << s;
}
C - 1111gal password
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll n, dp[N][10];
int siz(ll n) {int len = 0;while (n){len++;n /= 10;}return len;}
int main()
{
cin >> n; int len = siz(n);
for (int i = 1; i <= 9; i++) dp[1][i] = 1;
for (int i = 2; i <= n; i++)
for (int j = 1; j <= 9; j++)
if (j == 1) dp[i][j] = (dp[i - 1][j] % mod + dp[i - 1][j + 1] % mod) % mod;
else if (j == 9) dp[i][j] = (dp[i - 1][j] % mod + dp[i - 1][j - 1] % mod) % mod;
else dp[i][j] = (dp[i - 1][j] % mod + dp[i - 1][j - 1] % mod + dp[i - 1][j + 1] % mod) % mod;
ll res = 0;
for (int i = 1; i <= 9; i++) res = (res % mod + dp[n][i] % mod) % mod;
cout << res;
return 0;
}
D - ABC Transform(二叉树/递归)
题目描述
解题思路
思路请参考Hanasakiii的题解,这里只对令人疑惑的地方进行记录
问:为什么是%3
?
由图可知变换总是ABC ABC这样循环的 所以是%3
Code
#include <bits/stdc++.h>
using namespace std;
string s;
long long solve(long long t, long long k)
{
if (t == 0) return 1LL * (s[k] - 'A');
if (k == 0) return 1LL * (s[0] - 'A' + t) % 3;
return (solve(t - 1, k / 2) + k % 2 + 1) % 3;
}
int main()
{
cin >> s;
int q; cin >> q;
while (q--)
{
long long t, k; cin >> t >> k;
cout << char('A' + solve(t, k - 1)) << '\n';
}
return 0;
}
E - (∀x∀)
题目描述
解题思路
思路请参考Hanasakiii的题解
对于一个字符串s,字典序小于s的数量决定于s的前一半字符(偶数为长度n / 2,奇数为(n + 1) / 2)
如ABCD
取决于AB
, ABACD
取决于ABA
所以可以将给定的字符串s分为两半来做
其中对于奇数长度的字符串,分为一半后,需要将left翻转后的字符right减去首元素
如ABACD
分为一半后,left = ABA, rihgt = (ABA的翻转 - 首元素) = BA。
最后需要一个特判,left + right <= s
的话,需要再加1
Code
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
void solve()
{
int n; cin >> n;
string s; cin >> s;
string t = s;
string left = t.substr(0, (n + 1) / 2), right = left;
reverse(right.begin(), right.end());
if (n & 1) right.erase(right.begin());
int cnt = 0;
for(auto ch : left) cnt = (cnt * 26 + ch - 'A') % mod;
if (left + right <= s) cnt = (cnt + 1) % mod;
cout << cnt << '\n';
}
int main()
{
int t; cin >> t;
while (t--) solve();
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)