根据上票状态判断是否投降。4票及以上赞同投降则投降成功。
- $1\leq i \leq 5$
- $1\leq j\leq i,S[j]\in\{Y,N\}$
计数模拟即可。
1
2
3
4
5
6
7
8
9
10
11
| void solve() {
string s;cin >> s;
int y = 0, n = 0;
for (auto c : s) {
if (c == 'Y')y++;
else if (c == 'N')n++;
}
if (y >= 4)cout << "1\n";
else if (n >= 2)cout << "-1\n";
else cout << "0\n";
}
|
使用std::pair声明$n$个变量，进行对于这些变量的$q$个询问，回答其数据类型。
每行输入不超过5000字符
按.分割询问的变量，逐层确定当前的数据类型。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int maxn = 1e6 + 50;
map<string, string>mp;
void solve() {
int n, q;cin >> n >> q;
for (int i = 0;i < n;i++) {
string s1, s2;
cin >> s1 >> s2;
if (s2.back() == ';')s2.pop_back();
mp[s2] = s1;
}
while (q--) {
string s;cin >> s;
s = s + ".";
vector<string>stk;
int p = s.find(".");
int pr = 0;
while (p != -1) {
string t = s.substr(pr, p - pr);
stk.push_back(t);
s = s.substr(p + 1);
p = s.find(".");
}
string typ = mp[stk.front()];
for (int i = 1;i < stk.size();i++) {
string c = stk[i];
vector<int>v;
int pp; // 中点的','位置
int cnt1, cnt2;
cnt1 = cnt2 = 0;
for (int j = 0;j < typ.size();j++) {
if (typ[j] == '<') {
cnt1++;
}
else if (typ[j] == ',') {
cnt2++;
v.push_back(j);
}
else if (typ[j] == '>') {
cnt1--, cnt2--;
if (!cnt1 && !cnt2) {
pp = v.back();
break;
}
v.pop_back();
}
}
if (c == "first") {
typ = typ.substr(5, pp - 5);
}
else {
typ = typ.substr(pp + 1, typ.size() - pp - 2);
}
}
cout << typ << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;cin.get();
while (t--)
solve();
return 0;
}
|
在$\{1,…,n\}\times \{1,…,n\}$的坐标逐渐加入$n\times n$个数，如果即将加入的这个数与已有的形成了三点共线，则该数不能被成功加入，输出一个长度为$n\times n$的01串，表示第$i$个点能否成功加入。
- $1\leq n\leq 1000$
- $1\leq x_i,y_i\leq n$
每行每列都不能拥有超过$2$个点，若某行或某列已经超过2个点则直接判不能加入，用一个$vis$数组记录某点是否能被成功加入，加入新点时，遍历图中已有的点，枚举与图中已有点形成的直线的斜率$(dx,dy)$，$dx$、$dy$互质，从当前点$(x,y)$向两边转移到$(x\pm dx,y\pm dy)$，并标记该处不能被访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1050;
struct point {
int x, y;
};
int X[maxn], Y[maxn];
bool vis[maxn][maxn];
void solve() {
int n;cin >> n;
vector<point>v;
for (int i = 1;i <= n * n;i++) {
int x1, y1;cin >> x1 >> y1;
if (X[x1] + 1 > 2 || Y[y1] + 1 > 2 || vis[x1][y1]) {
cout << "0";
continue;
}
X[x1]++, Y[y1]++;
if (i == 1) {
v.push_back({ x1,y1 });
vis[x1][y1] = true;
cout << "1";continue;
}
for (auto [x2, y2] : v) {
if (y2 == y1 || x2 == x1)continue;
int dx = abs(x2 - x1), dy = abs(y2 - y1), c = (1.0 * (y1 - y2) / (x1 - x2) > 0 ? 1 : -1);
int g = gcd(dx, dy);
dx /= g, dy /= g;
int x = x1, y = y1;
while (x >= 1 && x <= n && y >= 1 && y <= n) {
vis[x][y] = true;
x += dx, y += c * dy;
}
x = x1, y = y1;
while (x >= 1 && x <= n && y >= 1 && y <= n) {
vis[x][y] = true;
x -= dx, y -= c * dy;
}
}
v.push_back({ x1,y1 });
cout << "1";
}
cout << "\n";
}
int main() {
int t = 1;
// cin >> t;cin.get();
while (t--)
solve();
return 0;
}
|
两个玩家拥有$a$和$b$的筹码，在一场公平游戏中全押，等概率成为输家或赢家，若赢家的筹码不少于输家，游戏结束，该局赢家为最终胜利者。否则输家向赢家支付等同于赢家筹码的筹码。问游戏结束时两个玩家分别的胜率是多少（模$998244353$）。
- $1\leq a,b\leq 998244353$
游戏结束时要求赢家筹码不少于输家，另$f(x)$为玩家筹码量为$x$时的胜率，$n$为总筹码数，也就是$a+b$，则有：
$$
f(0)=0,f(n)=1\\
\begin{cases}
f(x)=\frac{1}{2}\times f(0)+\frac{1}{2}\times f(2 x)\quad x\lt n/2\\
f(x)=\frac{1}{2}\times f(n)+\frac{1}{2}\times f(2 x-n)\quad x\geq n/2
\end{cases}
$$
玩家押上$x$筹码后，对方押上$n-x$筹码，若$x\geq n-x$则玩家为赢家时直接胜利，为输家时向对方交付$n-x$筹码，自己留下$x-(n-x)=2\times x-n$筹码，这时候的胜率变为$f(2x-n)$，发生这两种情况的概率都是$0.5$。打表后发现$f(x)=\frac{x}{n}$是线性方程的解。
输出$\frac{a}{a+b}$和$\frac{a}{a+b}$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1)res = res * a % mo998;
b >>= 1;
a = a * a % mo998;
}
return res;
}
ll inv(ll x) {
return qpow(x, mo998 - 2);
}
void solve() {
ll a, b;cin >> a >> b;
ll c = (a + b) % mo998;
cout << a * inv(c) % mo998 << " " << b * inv(c) % mo998 << "\n";
}
|
