赞
踩
Takahashi eats three plates for breakfast: rice, miso soup, and salad.
His table is long and narrow, so he arranged the three plates in a row. The arrangement is given by a string
S
S
S, where the
i
i
i-th plate from the left is rice if
S
i
S_i
Si is R
, miso soup if
S
i
S_i
Si is M
, and salad if
S
i
S_i
Si is S
.
Determine whether the plate of rice is to the left of the plate of miso soup.
R
, one M
, and one S
.The input is given from Standard Input in the following format:
$S$
Print Yes
if the plate of rice is to the left of the plate of miso soup, and No
otherwise.
RSM
Yes
The plate of rice is at the 1st position from the left, and the plate of miso soup is at the 3rd position from the left. Since the plate of rice is to the left, print Yes
.
米饭在味增汤左边时输出Yes,也就是说读取字符串时,若米饭先出现 味增汤后出现,输出Yes,否则输出No。
#include<bits/stdc++.h> #define int long long using namespace std; string s; void solve() { cin >> s; bool flag = false; for (int i = 0; i < s.size(); i ++ ) { if (s[i] == 'M') { flag = true; } if (s[i] == 'R') { if (flag == false) { cout << "Yes" << endl; return; } else { cout << "No" << endl; return; } } } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }
You are given two strings S S S and T T T consisting of lowercase English letters.
Determine if there exists a pair of integers c c c and w w w such that 1 ≤ c ≤ w < ∣ S ∣ 1 \leq c \leq w \lt |S| 1≤c≤w<∣S∣ and the following condition is satisfied. Here, ∣ S ∣ |S| ∣S∣ denotes the length of the string S S S. Note that w w w must be less than ∣ S ∣ |S| ∣S∣.
问题陈述
给你两个由小写英文字母组成的字符串 S S S 和 T T T 。
请判断是否存在一对整数 c c c 和 w w w ,使得 1 ≤ c ≤ w < ∣ S ∣ 1 \leq c \leq w \lt |S| 1≤c≤w<∣S∣ 和下面的条件都满足。这里, ∣ S ∣ |S| ∣S∣ 表示字符串 S S S 的长度。注意 w w w 必须小于** ∣ S ∣ |S| ∣S∣ 。
The input is given from Standard Input in the following format:
$S$ $T$
Print Yes
if there exists a pair of integers
c
c
c and
w
w
w such that
1
≤
c
≤
w
<
∣
S
∣
1 \leq c \leq w \lt |S|
1≤c≤w<∣S∣ and the condition is satisfied, and No
otherwise.
atcoder toe
Yes
If S S S is split at every two characters, it looks like this:
at
co
de
r
Then, the concatenation of the 2nd characters of the substrings of length at least
2
2
2 is toe
, which equals
T
T
T. Thus, print Yes
.
B题居然没有做出来,我不知道该说这题出的烂还是我审题不仔细,题目要求必须要分割后的字符串 每个字符串内第c个字符串全部加起来与字符串T相等才算匹配成功。
比如T:toe S:atcodere 可以分割成 at co de re ,我以为每个分割后的字符串内第c个字符只要从前向后与T字符串匹配成功就算符合要求,比如举的这个例子里前三个字符里第二个字符加起来就是toe与T字符串匹配,实际上这种情况是不被允许的,这里要求只要用了第二个字符就需要全部加起来,也就是说这里第二个字符构成的字符串就是toee,并不与T匹配,好坑。
这题题意是先分割字符串,从你分割的字符串,选择每个字符串的第c个元素拼起来,看是否与T字符串相同,这里就是注意可能你每隔w个字母分割,最后一个字符串长度并不到w,但当你选择每个字符串的第c个元素时,如果他的长度达到c也需要从最后一个字符串中选出他的第c个元素。
我们利用三层暴力枚举来做,第一层枚举分割的长度i,第二层枚举选择分割后的字符串的第j个元素,第三层将每个字符串的第j个元素加起来,看是否符合要求。
#include<bits/stdc++.h> #define int long long using namespace std; string s, t; void solve() { cin >> s >> t; for (int i = 1; i < s.size(); i ++ ) { for (int j = 0; j < i; j ++ ) { string str; for (int k = j, cnt = 0; k < s.size(); k += i) { str += s[k]; //将每个字符串的第j位元素合并 // if (s[k] != t[cnt]) break; 刚开始以为只需要选出的前t.size()个元素与T匹配即可 // else cnt ++ ; // if (cnt == t.size()) // { // cout << "Yes" << endl; // return; // } } if (str == t) { cout << "Yes" << endl; return; } } } cout << "No" << endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }
There are N N N boxes numbered 1 1 1 to N N N and N N N items numbered 1 1 1 to N N N. Item i i i ( 1 ≤ i ≤ N ) (1 \leq i \leq N) (1≤i≤N) is in box A i A_i Ai and has a weight of W i W_i Wi.
You can repeatedly perform the operation of choosing an item and moving it to another box zero or more times. If the weight of the item being moved is w w w, the cost of the operation is w w w.
Find the minimum total cost required to make each box contain exactly one item.
问题陈述
有 N N N 个编号为 1 1 1 至 N N N 的箱子和 N N N 个编号为 1 1 1 至 N N N 的物品。 i i i 号物品 ( 1 ≤ i ≤ N ) (1 \leq i \leq N) (1≤i≤N) 装在 A i A_i Ai 箱中,重量为 W i W_i Wi 。
您可以重复执行选择物品并将其移动到另一个盒子中的操作 0 次或更多次。如果被移动物品的重量为 w w w ,则操作的成本为 w w w 。
求使每个箱子中正好有一件物品所需的最小总成本。
The input is given from Standard Input in the following format:
N
N
N
A
1
A_1
A1
A
2
A_2
A2
…
\ldots
…
A
N
A_N
AN
W
1
W_1
W1
W
2
W_2
W2
…
\ldots
…
W
N
W_N
WN
Print the minimum total cost required to make each box contain exactly one item.
5
2 2 3 3 5
33 40 2 12 16
35
With the following two moves, you can make each box contain exactly one item:
The total cost of these two moves is 35 35 35. It is impossible to make each box contain exactly one item with a cost less than 35 35 35, so print 35 35 35.
解释一下题意,有编号1 ~ N的N个箱子,有编号1 ~ N的N个物品,现在这N个物品被装在N个箱子里,有的箱子可能装了很多物品,有的箱子可能没装物品。输入的第二行 A 1 . . . A N A_1 ... A_N A1...AN是指第 i i i号物品被装在第 A i A_i Ai个箱子里,第三行是1~N号物品每个物品的重量,也就是操作成本。
显然本题利用贪心来做,由于只有N个物品和N个箱子,则它们可以一一对应,当某一个箱子里放了多个物品时,将多余的物品拿出来必然有空的箱子可以放下它们,那我们只需要存每个箱子当前存放的物品个数,遍历所有箱子拿出多余的物品,使得所有箱子物品个数都为1。在这个过程中总是优先拿出重量最小的物品,最后求得的操作成本就是最优解。关于拿出重量最小的物品,我们利用最小堆实现。
#include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 10; int n, res; int a[N], w[N]; typedef pair<int, int> PII; void solve() { cin >> n; map<int, int> mp; //物品和它所在箱子内有几个物品 for (int i = 1; i <= n; i ++ ) { cin >> a[i]; mp[a[i]] ++ ; //当前箱子存放物品数++ } priority_queue<PII, vector<PII>, greater<PII>> heap; //最小堆存放物品重量和其对应编号 优先利用物品重量排序 for (int i = 1; i <= n; i ++ ) { cin >> w[i]; heap.push({w[i], i}); } //按照物品重量从小到大依次弹出物品,若它存放的箱子里有多个物品,就将当前物品移走 while (heap.size()) { auto t = heap.top(); heap.pop(); if (mp[a[t.second]] > 1) { res += t.first; //操作成本 mp[a[t.second]] -- ; } } cout << res << endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }
There are
N
N
N ants on a number line, labeled
1
1
1 to
N
N
N. Ant
i
i
i
(
1
≤
i
≤
N
)
(1 \leq i \leq N)
(1≤i≤N) starts at coordinate
X
i
X_i
Xi and faces either a positive or negative direction. Initially, all ants are at distinct coordinates. The direction each ant is facing is represented by a binary string
S
S
S of length
N
N
N, where ant
i
i
i is facing the negative direction if
S
i
S_i
Si is 0
and the positive direction if
S
i
S_i
Si is 1
.
Let the current time be 0 0 0, and the ants move in their respective directions at a speed of 1 1 1 unit per unit time for ( T + 0.1 ) (T+0.1) (T+0.1) units of time until time ( T + 0.1 ) (T+0.1) (T+0.1). If multiple ants reach the same coordinate, they pass through each other without changing direction or speed. After ( T + 0.1 ) (T+0.1) (T+0.1) units of time, all ants stop.
Find the number of pairs ( i , j ) (i, j) (i,j) such that 1 ≤ i < j ≤ N 1 \leq i \lt j \leq N 1≤i<j≤N and ants i i i and j j j pass each other from now before time ( T + 0.1 ) (T+0.1) (T+0.1).
问题陈述
在一条标有 1 1 1 至 N N N 的数线上有 N N N 只蚂蚁。蚂蚁 i i i ( 1 ≤ i ≤ N ) (1 \leq i \leq N) (1≤i≤N) 从坐标 X i X_i Xi 开始,朝向正方向或负方向。最初,所有蚂蚁都位于不同的坐标上。每只蚂蚁面对的方向由长度为 N N N 的二进制字符串 S S S 表示,如果 S i S_i Si 为 “0”,则蚂蚁 i i i 面对的是负方向;如果 S i S_i Si 为 “1”,则蚂蚁 i i i 面对的是正方向。
假设当前时间为 0 0 0 ,在 ( T + 0.1 ) (T+0.1) (T+0.1) 个单位的时间内,蚂蚁以每单位时间 1 1 1 个单位的速度向各自的方向移动,直到时间 ( T + 0.1 ) (T+0.1) (T+0.1) 。如果有多只蚂蚁到达同一坐标,它们会互相穿过而不会改变方向或速度。经过 ( T + 0.1 ) (T+0.1) (T+0.1) 个单位的时间后,所有蚂蚁停止。
求从现在起到时间 ( T + 0.1 ) (T+0.1) (T+0.1) 之前,蚂蚁 1 ≤ i < j ≤ N 1 \leq i \lt j \leq N 1≤i<j≤N 和蚂蚁 i i i 及 j j j 互相通过的蚂蚁对 ( i , j ) (i, j) (i,j) 的个数。
0
and 1
.The input is given from Standard Input in the following format:
N
N
N
T
T
T
S
S
S
X
1
X_1
X1
X
2
X_2
X2 …
X
N
X_N
XN
Print the answer.
6 3
101010
-5 -1 0 1 2 4
5
The following five pairs of ants pass each other:
No other pairs of ants pass each other, so print 5 5 5.
补题的时候独立完成了,其实也就是双指针的应用,不过需要正反用两次。
题意就是说找到行进过程中会互相穿过的蚂蚁对数,例如从1走到3和从3走到1的蚂蚁显然会互相穿过,这里也要注意从-1走到1和从3走到1蚂蚁最后都走到1也算互相穿过,因为经过T时间后蚂蚁还会走0.1个时间,就会互相穿过。所以我们可以简单理解为会碰头的蚂蚁对数。
不难发现,所有蚂蚁速率都是相等的,所以相同方向的蚂蚁永远不会碰头,只有不同方向的蚂蚁可能碰头,但如果往右走的蚂蚁本来就在往左走的蚂蚁右边则它们也永远不会碰头,只有当往右走的蚂蚁在往左走的蚂蚁左边也就是说,只有蚂蚁面对面走才有可能碰头。
第二个条件是蚂蚁面对面走在t时间内能走到需要保证它们之间的路程小于2*t。
好了,思路分析完了,如果我们直接暴力枚举每一个蚂蚁,去遍历与他方向相反的蚂蚁看符不符合条件 显然会超时。
不难发现如果坐标最小的往左走的蚂蚁有与其面对面的往右走的蚂蚁,那么剩下所有往左走的蚂蚁都与这个蚂蚁面对面,那么我们可以将蚂蚁按坐标排序,i指针指向向左走的蚂蚁,j指针指向向右走的蚂蚁,当当前j指针指向的右走蚂蚁满足与当前i蚂蚁面对面,则i之后的蚂蚁都与当前j蚂蚁面对面,i+1蚂蚁只用从不满足与i蚂蚁面对面的j蚂蚁开始判断,发现,j指针不用回退,采用双指针。
同理,利用双指针筛去面对面但距离大于2 * t的蚂蚁对数,也是i蚂蚁与j蚂蚁距离大于2 * t必然有i+1蚂蚁与j蚂蚁距离大于2 * t。
#include<bits/stdc++.h> #define int long long using namespace std; const int N = 2e5 + 10; int n, t, cnt; string s; void solve() { cin >> n >> t; cin >> s; vector<int> a, b; for (int i = 0; i < n; i ++ ) { int pos; cin >> pos; //将方向不同的蚂蚁分开记录 if (s[i] == '0') { a.push_back(pos); } else { b.push_back(pos); } } //将行进方向不同的蚂蚁按照初始坐标从小到大分别排序 sort(a.begin(), a.end()); sort(b.begin(), b.end()); //记录对向走的蚂蚁对数 for (int i = 0, j = 0; i < a.size(); i ++ ) { while (j < b.size() && (a[i] - b[j] > 0)) j ++ ; cnt += j; } //排除掉对向走但走不到的情况 for (int i = 0, j = 0; i < a.size(); i ++ ) { while (j < b.size() && (a[i] - b[j] > 0) && ((a[i] - b[j]) > 2 * t)) j ++ ; cnt -= j; } cout << cnt << endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }
There are N − 1 N - 1 N−1 white balls and one black ball. These N N N balls are arranged in a row, with the black ball initially at the leftmost position.
Takahashi will perform the following operation exactly K K K times.
After K K K operations, let the black ball be at the x x x-th position from the left. Find the expected value of x x x, modulo 998244353 998244353 998244353.
What is expected value modulo 998244353 998244353 998244353? It can be proved that the sought expected value will always be rational. Additionally, under the constraints of this problem, it can be proved that if this value is expressed as an irreducible fraction P Q \frac{P}{Q} QP, then Q ≢ 0 ( m o d 998244353 ) Q \not \equiv 0 \pmod{998244353} Q≡0(mod998244353). Therefore, there exists a unique integer R R R such that R × Q ≡ P ( m o d 998244353 ) , 0 ≤ R < 998244353 R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 R×Q≡P(mod998244353),0≤R<998244353. Report this R R R.
问题陈述
有 N − 1 N - 1 N−1 个白球和一个黑球。这些 N N N 球排列成一排,黑球最初位于最左边的位置。
高桥正好要进行下面的操作 K K K 次。
经过 K K K 次操作后,让黑球位于左边第 x x x 个位置。求 x x x 的期望值,模为 998244353 998244353 998244353 。
998244353 998244353 998244353 的期望值是多少?可以证明所求的期望值总是有理数。此外,在本题的限制条件下,还可以证明如果用不可约分数 P Q \frac{P}{Q} QP 表示这个值,那么就是 Q ≢ 0 ( m o d 998244353 ) Q \not \equiv 0 \pmod{998244353} Q≡0(mod998244353) 。因此,存在一个唯一的整数 R R R ,使得 R × Q ≡ P ( m o d 998244353 ) , 0 ≤ R < 998244353 R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 R×Q≡P(mod998244353),0≤R<998244353 。报告这个 R R R .
The input is given from Standard Input in the following format:
$N$ $K$
Print the answer in one line.
2 1
499122178
After one operation, the probabilities that the black ball is at the 1st position and the 2nd position from the left are both 1 2 \displaystyle \frac{1}{2} 21. Thus, the expected value is 3 2 \displaystyle \frac{3}{2} 23.
这个题的题意确实很难理解,感觉是对期望DP还不咋熟悉,我们先来模拟一下第二个样例
这样第一次操作就完成了,接下来进行第二次操作
经过样例推导,我们可以得出几个结论
那么我们就可以列出状态方程 f i f_i fi表示进行完i次操作后黑球仍在第一个位置的概率,显然可以分成两种情况
第i次操作之前(也就是进行第i-1次操作后),黑球本来就在第一个位置
第i次操作之前(也就是进行第i-1次操作后)黑球不在第一个位置了
那么对于第i次操作后黑球仍保留在第一个位置的概率
计算出 f k f_k fk后我们就可以利用 f k f_k fk求出剩下n-1个位置的概率均为 ( 1 − f k ) n − 1 \frac{(1 - f_k)}{n-1} n−1(1−fk),那么他们每个位置的期望就为 ( 1 − f k ) n − 1 × i \frac{(1 - f_k)}{n-1}\times i n−1(1−fk)×i,从位置2~位置n将期望加和为 ∑ i = 2 n ( 1 − f k ) n − 1 × i = ( 1 − f k ) n − 1 ∑ i = 2 n i \displaystyle\sum_{i=2}^{n}\frac{(1 - f_k)}{n-1}\times i = \frac{(1 - f_k)}{n-1}\displaystyle\sum_{i=2}^{n}i i=2∑nn−1(1−fk)×i=n−1(1−fk)i=2∑ni,可以直接等差数列求和解决
tips:又被%mod困扰半天,对一个乘法运算取余的时候不要加括号
#include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 10; const int mod = 998244353; int n, k, ans; int f[N]; int qmi(int a, int b) { int res = 1 % mod; while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } void solve() { cin >> n >> k; int p0 = ((qmi(n, 2) - (2 * n % mod - 2)) * qmi(qmi(n, 2), mod - 2)) % mod; int p1 = (2 * qmi(qmi(n, 2), mod - 2)) % mod; p0 = (p0 + mod) % mod; p1 = (p1 + mod) % mod; //当只进行一次操作时,黑球位于第一个位置概率是p0 f[1] = p0; //cout << (p0 + mod) % mod << " " << p1 << endl; //计算经过k次操作后黑球仍位于第一个位置的概率 for (int i = 2; i <= k; i ++ ) { f[i] = (f[i - 1] * p0 % mod + (((1 - f[i - 1] + mod) % mod) * p1) % mod) % mod; } //计算期望 ans = f[k]; //位于第一个位置的期望 ans = (ans + ((((1 - f[k] + mod) % mod) * qmi(n - 1, mod - 2) % mod) * ((n + 2) * (n - 1) / 2 % mod))) % mod; //剩下n-1个位置的期望 ans %= mod; cout << ans << endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。