比赛链接: https://ac.nowcoder.com/acm/contest/43084
A - Monster Killer
题目大意
小莫在玩一个打怪游戏, 给定n个怪物的攻击力a和buff概率x; 初始情况下小莫的攻击力m为0, 按照小莫必须按照给的顺序打怪, 打怪时会出现三种情况: 一是m=a, 小莫可以打败怪物; 二是m>a, 小莫虽然也可以打败怪物, 但是会有概率x使得攻击力-1; 三是m<a, 小莫无法打败怪物, 但是会有概率x使得攻击力+1; 问小莫打败所有怪物所用回合数的期望, 对分数取模;
解题思路
这是一道概率dp, 状态表示: dp[i][j]表示小莫以攻击力j从第i个怪物开始打通关的期望; 状态计算为: 对于j=a, dp[i][j] = dp[i+1][j] + 1; 对于j>a, dp[i][j] = dp[i+1][j-1] * x + dp[i+1][j] * (1-x) + 1; 对于j<a, dp[i][j] = dp[i + 1][a] + (a-j) / x + 1; 从状态计算来看这是一个倒推的过程i要从n到1进行遍历, 需要注意的是, 对于每个怪物, 我们都要从0到1001遍历攻击力, 而不能只遍历到这只怪物的攻击力;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 10, mod = 998244353;
int dp[N][N];
int f[N], p[N];
int n, m, res;
int qmi(int a, int b, int c) {
int res = 1;
while (b) {
if (b & 1) res = res * a % c;
a = a * a % c;
b >>= 1;
}
return res;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
int maxn = 0;
for (int i = 1; i <= n; i++) {
cin >> f[i] >> p[i];
p[i] = p[i] * qmi(100, mod - 2, mod) % mod;
}
for (int i = n; i >= 1; i--) {
for (int j = 0; j < 1010; j++) {
if (j < f[i]) {
dp[i][j] = (dp[i + 1][f[i]] + (f[i] - j) * qmi(p[i], mod - 2, mod) + 1) % mod;
}
else if (j == f[i]) {
dp[i][f[i]] = (dp[i + 1][f[i]] + 1) % mod;
}
else if (j > f[i]) {
dp[i][j] = (dp[i + 1][j - 1] * p[i] + dp[i + 1][j] * (mod + 1 - p[i]) + 1) % mod;
}
}
}
cout << dp[1][0];
return 0;
}
C - Roll the Circle
题目大意
给定两个圆的半径, 两个圆是外切的, 问第二个圆绕着第一个圆转一圈回到起点需要自身转几圈, 结果以分数形式呈现, 取最简形式;
解题思路
找规律, 答案就是(a+b) / b;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 10, mod = 998244353;
int n, m;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
signed main(){
int T;
cin >> T;
while (T--) {
int a, b;
cin >> a >> b;
a = a + b;
int x =gcd(a, b);
a /= x, b /= x;
cout << a << '/' << b << endl;
}
return 0;
}
E - Merging Stones
题目大意
给定n个石堆, 每个石堆都有各自的石子数量; 现在我们可以从中挑选两个石堆并将其合并, 然后会获得一定的分数; 设石子数量为x和y, 则新石堆的数量为x+y, 获得的分数为x*y; 最终只剩一个石堆时问可以获得的最大分数为多少;
解题思路
虽然看题意非常像区间dp, 但是本题并不要求两个石堆要相邻, 并且n的数据范围到了1e4, 区间dp一定会超时; 所以我们可以从贪心的角度出发; 设数字a< b< c, 我们该怎么合并才能获得最大分数呢, (a+b)+c, a+(b+c)以及b+(a+c); 你会发现a+(b+c)这种组合方式所获得的分数是最多的, 因为如果你想用较低的石子数去获得尽量高的分数, 方法只能是让他和一个尽量大的数合并; 如果我们先让a和b合并, 因为a很小所以说(a+b)c和bc的区别并不大; 所以这是本题贪心的关键;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n;
priority_queue<int> q;
signed main(){
cin>>n;
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
q.push(a);
}
int res=0;
while(q.size()!=1){
int x,y;
x=q.top(), q.pop();
y=q.top(), q.pop();
int c=x+y;
q.push(c);
res+=x*y;
}
cout<<res;
}
H - Substrings
题目大意
给定一个字符串, 问其中字符串"fyt"出现了多少次
解题思路
签到题不多嗦;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 10, mod = 998244353;
int n, m;
signed main() {
string s;
cin >> n >> s;
int ans = 0;
for (int i = 0; i < n - 2; i++)
{
if (s[i] == 'f')
{
if (s[i + 1] == 'y' && s[i + 2] == 't')
ans++;
}
}
cout << ans << endl;
return 0;
}
J - Two Kings
题目大意
小莫和安姐玩游戏, 在一个坐标图中给出小莫和安姐的位置, 两人下一次行动可以到达以自身为中心的2*2的正方形边缘的8个点上; 这也意味着如果小莫走到了安姐的行动范围内, 那个安姐下一步就可以抓住小莫, 反过来安姐就会被小莫抓住(初始情况下两人互不在各自的行动范围内); 现在小莫要到达一个目的地, 设该目的地在坐标图右边无限远的地方, 如果安姐能组织小莫到达目的地, 那么安姐就会赢, 反之小莫赢; 先给定两人的坐标, 小莫先走, 问谁会赢;
解题思路
由题意得, 如果小莫在安姐右边, 那个安姐肯定追不上小莫; 如果两个的x坐标相同, y坐标不同也是小莫赢, 如果安姐在上面, 小莫就往右下跑, 反之就往左上跑, 安姐也肯定追不上; 所以我们只讨论小莫在安姐左边的情况: 如果小莫在安姐的左上方, 那么小莫的最优解肯定是往左上跑, 而安姐如果也往左上跑就会平行一直追不上, 所以安姐的最优解是竖直往上去拦截, 这时候你会发现安姐无法在小莫到达之前拦住他, 小莫在左下方的情况也同理; 所以安姐能赢的情况只能是小莫在安姐的正左边, 然后我们发现如果两人之间距离只有2的时候, 小莫只要往右走就会进入安姐的行动范围, 所以安姐必赢; 但是当两人距离为3时, 小莫可以先正右方走一步, 这样安姐就遇到了相同的处境, 只要往左走一步就会进入小莫的行动范围, 所以小莫必赢; 所以我们发现当距离是2的倍数时安姐赢, 反之小莫赢;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 10, mod = 998244353;
int n, m, maxn, num;
double res;
void solves() {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 >= x2) {
cout << "Walk Alone" << endl;
}
else {
if (y1 == y2) {
if ((x2 - x1) % 2 == 0) cout << "Salix Leaf" << endl;
else cout << "Walk Alone" << endl;
}
else cout << "Walk Alone" << endl;
}
}
signed main() {
int t;
cin >> t;
while (t--)
solves();
return 0;
}
L - Phigros
题目大意
小莫正在打音游, 对于某首歌来说最终的分数由两部分组成, 最终分数是这两部分的分数相加后四舍五入所得; 第一部分是每个节奏点所获得的分数, 对于每个节奏点有四种状态: perfect的得分是900000/n, good是585000/n, 而bad和miss不得分; 其中n指的是节奏点的总个数; 第二部分是连击的奖励分数, 连击长度指的是只由perfect和good组成的最长连续序列的长度m, 奖励分数为100000*m/n; 现在给出小莫前k个节奏点的情况, 假设之后的所有节奏点都是perfect, 问小莫这首歌所获得的分数为多少;
解题思路
一道简单的模拟题不多嗦了;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 10, mod = 998244353;
int n, m, maxn, num;
double res;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
string s;
cin >> s;
if (s == "perfect") {
num++;
res += 1.0 * 900000 / n;
}
else if (s == "good") {
num++;
res += 1.0 * 585000 / n;
}
else {
maxn = max(maxn, num);
num = 0;
}
}
int k = n - m;
res += 1.0 * k * 900000 / n;
if (num + k > maxn) maxn = num + k;
res = res + 1.0 * 100000 * maxn / n + 0.5;
cout << res;
return 0;
}
N - Walk Alone's Conjecture
题目大意
给定一个数n, 让我们找出两个数x和y满足以下两个条件: 一是y-x=n; 二是x和y具有相同个数的质因子;
解题思路
根据第一个条件我们可以设一个数a, 让y=an, x=(a-1)n; 这样就满足了y-x=n; 又因为对于一个数c=ab, c的因数是a的因数和b的因数取并集然后再加上ab; 现在x和y都有n, 所以我们只要让a和a-1具有相同个数的质因子即可; 如果n是一个偶数, 那我们直接让x=n, y=2*n即可, 因为2就是n的因数, 故总的个数不变; 所以接下来我们只考虑n为奇数的情况: 为了控制总的质因子个数, 我们不能让a是n的因数, 因为a一定是奇数, a-1就是偶数, x会比y多一个质因子2; 然后为了控制a的质因子个数, 我们索性就让a本身是个质数, 这样a比a-1多一个质因子就是a本身, 而a-1比a多一个质因子是2; 但是a-1可能还会有其他的质因子, 所以我们必须保证这些质因子同时也是n的质因子; 因此我们设a为不是n的质因子的最小的质数, 这样小于n的质数一定都是n的质因子, 也就是说即使a-1包含多个质因子, 也一定都是n已经包含的质因子; 根据计算一般用前10个质数就可以找到答案了;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 10, mod = 998244353;
int n, m, maxn, num;
int ans[] = { 3,5,7,11,13,17,19,23,29,31,37,41,43,47 };
void solves(){
cin >> n;
if (!(n & 1)) cout << n << ' ' << 2 * n << endl;
else{
for (int i = 0; i < 11; i++) {
if (n % ans[i] != 0) {
cout << (ans[i] - 1) * n << ' ' << ans[i] * n << endl;
break;
}
}
}
}
signed main(){
int t;
cin >> t;
while (t--)
solves();
return 0;
}