商城网站静态模板下载,教育培训东莞网站建设,做网站虚拟主机规格,wordpress主题 印刷难度#xff1a;普及/提高−#xff1b;
题意#xff1a;
石头、剪刀、布游戏#xff0c;先给出 n n n 轮已经知道的其中一人的对局情况#xff0c;例如样例#xff1a;
5
P - 布
P - 布
H - 石头
P - 布
S - 剪刀另外一人#xff0c;只允许修改一次机会的情况下…难度普及/提高−
题意
石头、剪刀、布游戏先给出 n n n 轮已经知道的其中一人的对局情况例如样例
5
P - 布
P - 布
H - 石头
P - 布
S - 剪刀另外一人只允许修改一次机会的情况下求最多可以赢的局面数量。
分析
题意理解了我感觉就是很简单可以用双指针做也可以用前缀和分开两段来做。这里讲述前缀和分两段的分别统计贡献的方式来做。
根据题意可知手势一旦确定为 x x x那么只允许在后面第 k k k 次发生了修改为 y y y那么贡献(胜利的局数)就是 k [ x ] 1 ∼ x k [ y ] x ∼ n k[x]_{1 \sim x} \ \ k[y]_{x \sim n} k[x]1∼x k[y]x∼n其中 k k k 数组可以用前缀和来完成。
参考代码
#include bits/stdc.h
#define ll long longconst int N 100050;
int h[N], s[N], p[N], n;int mx(int a, int b) // 为了让代码看起来简短一些
{if (a b)return a;return b;
}int main()
{std::ios::sync_with_stdio(false), std::cin.tie(nullptr);std::cin n;for (int i 1; i n; i){h[i] h[i - 1], s[i] s[i - 1], p[i] p[i - 1];char ch;std::cin ch;if (ch H)h[i];if (ch S)s[i];if (ch P)p[i];}int ans 0;for (int i 1; i n; i) // [1-i], [i1,n] 找出区间内最长的两段ans mx(ans, mx(h[i], mx(s[i], p[i])) mx(h[n] - h[i], mx(s[n] - s[i], p[n] - p[i])));std::cout ans \n;return 0;
}
