给定一个长度为 的字符串,字符 o
表示 Good
,字符 -
表示 Fair
,字符 x
表示 Poor
。
问这个字符串是否满足下面的要求:
至少有一个 Good
没有 Poor
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
string s;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin >> s;
bool flagO = false;
bool flagX = false;
for (int i = 0; i < s.length(); i++)
if (s[i] == 'o')
flagO = true;
else if (s[i] == 'x')
flagX = true;
if (flagO && !flagX)
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
给定两个 的矩阵 。两个矩阵都是完全由数字 构成的。
问能否通过不限制次数地旋转 ,使得两个矩阵满足:“对于每一个 矩阵中为 的位置, 矩阵的对应位置都是 ”
一次对 旋转的旋转操作就是:“用旧 的 作为新 的 ”。
显然最多转三次,那就暴力转就是了。需要注意看清题意,不是要求完全相同。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[105][105], aa[105][105], b[105][105];
bool check()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (aa[i][j] == 1 && b[i][j] != 1)
return false;
return true;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> b[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
aa[i][j] = a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] = aa[i][j];
if (check())
{
cout << "Yes\n";
return 0;
}
for (int t = 1; t <= 3; t++)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
aa[n + 1 - j][i] = a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] = aa[i][j];
if (check())
{
cout << "Yes\n";
return 0;
}
}
cout << "No\n";
return 0;
}
给定 个盒子,和无限张空白的卡片。盒子编号为 。初始所有盒子都是空的。
紧接着进行 次操作,每次操作如下方式描述:
1 i j
:往 号盒子里放入一个写上了数字 的卡片。
2 i
:输出 号盒子里有哪些卡片(按升序排序)。
3 i
:输出哪些盒子中包含写了 的卡片(按升序排序)。
对于所有的 类操作:、。
对于所有的 类操作:
对于所有的 类操作:
set
和 multiset
用法模板题。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, q;
multiset<int> box[212345];
set<int> card[212345];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
while (q--)
{
int op, i, j;
cin >> op >> i;
if (op == 1)
{
cin >> j;
box[j].insert(i);
card[i].insert(j);
}
else if (op == 2)
{
for (auto x : box[i])
cout << x << " ";
cout << "\n";
}
else if (op == 3)
{
for (auto x : card[i])
cout << x << " ";
cout << "\n";
}
}
return 0;
}
给定一个字符串 。初始 1
.
进行 次操作:
1 x
:添加一个数字 x
到 的末尾。2
:删除 开头的数字3
:输出当前 的值数据范围:
显然加数字和删数字的操作是个队列操作。问题关键在于怎么实时计算当前数字 的值。假设当前 的值为 。
可以预处理 ,我的做法时实时得到最高位的贡献,通过 和 来调整即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
int INV10;
int q, now, firstBase;
queue<int> s;
// a^b (mod p)
long long quick_pow(long long a, long long b, long long p)
{
long long res = 1;
while (b)
{
if (b & 1)
res = (res * a) % p;
b = b >> 1;
a = (a * a) % p;
}
return res;
}
// 求 x 在模 p 意义下的逆元(要求 p 是一个质数)
long long inv(long long x, long long p)
{
return quick_pow(x, p - 2, p);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
INV10 = inv(10, MOD);
cin >> q;
now = 1;
firstBase = 1;
s.push(1);
while (q--)
{
int op, x;
cin >> op;
if (op == 1)
{
cin >> x;
s.push(x);
now = (now * 10 + x) % MOD;
firstBase = firstBase * 10 % MOD;
}
else if (op == 2)
{
now = ((now - s.front() * firstBase % MOD) % MOD + MOD) % MOD;
s.pop();
firstBase = firstBase * INV10 % MOD;
}
else if (op == 3)
{
cout << now << "\n";
}
}
return 0;
}
Taka 和 Aoki 正在玩一种棋。初始两个人分别处于位置 与位置 。然后两个人交替操作,Taka 先手。
如果某个人到达了位置 ,那么他就赢得了比赛。求 Taka 赢得比赛的概率()。
数据范围好小,想怎么搞就怎么搞。
两个人的位置都只会前进不会后退,可以用 表示达成“Taka 走到 ,Aoki 走到 这个局面” 的概率。
那么显然可以递推,从小到大枚举当前局面,把所有的投骰子可能性对应的目标局面算出来,增加目标局面的概率。
最终统计所有 Taka 获胜局面的概率之和就好。
#include <bits/stdc++.h>
#define PII pair<int, int>
#define int long long
using namespace std;
const int MOD = 998244353;
int n, A, B, P, Q;
int inv[15];
int p[105][105];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
inv[1] = 1;
for (int i = 2; i <= 10; i++)
inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
cin >> n >> A >> B >> P >> Q;
p[A][B] = 1;
for (int a = A; a <= n; a++)
{
for (int b = B; b <= n; b++)
{
if (a == n || b == n)
break;
for (int i = 1; i <= P; i++)
{
for (int j = 1; j <= Q; j++)
{
int nowp = inv[P] * inv[Q] % MOD; // 当前情况概率
p[min(a + i, n)][min(b + j, n)] =
(p[min(a + i, n)][min(b + j, n)] + p[a][b] * nowp) % MOD;
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
ans = (ans + p[n][i]) % MOD;
cout << ans % MOD << "\n";
return 0;
}
给定一个 的大网格。有 个格子上写了数字,第 个写了数字的格子是第 行的第 列,写上的数字是 。所有其它格子上写的数字都是 。
如果在网格中钦定一个位置 ,可以算出和它同一行同一列的 个格子上写的数字之和。
请找到这个和的最大值是多少。(即选择那个位置可以使同一行同一列的所有格子上数字之和最大)
挺小,先离散化一下方便后续处理。
显然这里比较麻烦的是如果选择了第 行与第 列,那么除了“第 行的所有数字之和”与“第 行的所有数字之和”外,还要减去 上的数字(按这个方法,这个位置被行列各算了一次)。
如果一行行枚举,选择了当前行后,显然要找到去掉了这一行的影响之后的最大的“列之和”,来构成选择当前行时的最优解。
可以考虑用一个线段树来维护每一列的元素之和。做到第 行时,就把这一行的数对“列之和”的影响消除,并把 行时消除的影响加回去。这样每个数都只被最多进行了一次消除和恢复。时间复杂度没问题。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
const int MAXN = 412345;
const int INF = 2000000000;
struct SegTree
{
int sum[MAXN * 4], maxx[MAXN * 4];
void build(int o, int l, int r)
{
if (l == r)
{
sum[o] = maxx[o] = 0;
return;
}
int mid = (l + r) >> 1;
build(o * 2, l, mid);
build(o * 2 + 1, mid + 1, r);
sum[o] = sum[o * 2] + sum[o * 2 + 1];
maxx[o] = max(maxx[o * 2], maxx[o * 2 + 1]);
}
int query_max(int o, int l, int r, int ql, int qr)
{
if (l > qr || r < ql)
return -INF;
if (ql <= l && r <= qr)
return maxx[o];
int mid = (l + r) >> 1;
return max(query_max(o * 2, l, mid, ql, qr), query_max(o * 2 + 1, mid + 1, r, ql, qr));
}
int query_sum(int o, int l, int r, int ql, int qr)
{
if (l > qr || r < ql)
return 0;
if (ql <= l && r <= qr)
return sum[o];
int mid = (l + r) >> 1;
return query_sum(o * 2, l, mid, ql, qr) + query_sum(o * 2 + 1, mid + 1, r, ql, qr);
}
void add(int o, int l, int r, int x, int t)
{
if (l == r)
{
maxx[o] += t;
sum[o] += t;
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
add(o * 2, l, mid, x, t); // 左右分别更新
else
add(o * 2 + 1, mid + 1, r, x, t);
sum[o] = sum[o * 2] + sum[o * 2 + 1];
maxx[o] = max(maxx[o * 2], maxx[o * 2 + 1]);
}
} st;
struct Point
{
int r, c, x;
};
Point p[212345];
vector<int> v;
vector<Point> rowP[412345]; // 第i行有哪些点
int rowSum[412345]; // 每行之和
int colSum[412345]; // 消除掉第i行后的每列之和
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> p[i].r >> p[i].c >> p[i].x;
v.push_back(p[i].r);
v.push_back(p[i].c);
}
sort(v.begin(), v.end());
int maxC = 0, maxR = 0;
for (int i = 1; i <= n; i++)
{
p[i].r = lower_bound(v.begin(), v.end(), p[i].r) - v.begin() + 1;
p[i].c = lower_bound(v.begin(), v.end(), p[i].c) - v.begin() + 1;
//cout << p[i].r << "," << p[i].c << ":" << p[i].x << endl;
maxR = max(maxR, p[i].r);
maxC = max(maxC, p[i].c);
rowP[p[i].r].push_back(p[i]);
rowSum[p[i].r] += p[i].x;
}
st.build(1, 1, maxC);
for (int i = 1; i <= n; i++)
st.add(1, 1, maxC, p[i].c, p[i].x);
int ans = 0;
for (int i = 1; i <= maxR; i++)
{
// 恢复上一行的影响
for (auto now : rowP[i - 1])
st.add(1, 1, maxC, now.c, now.x);
// 消除当前行对列的影响
for (auto now : rowP[i])
st.add(1, 1, maxC, now.c, -now.x);
//cout << i << ":" << rowSum[i] << "~" << st.maxx[1] << endl;
ans = max(ans, rowSum[i] + st.maxx[1]);
}
cout << ans << "\n";
return 0;
}
/*
1e9 x 1e9 的格子
n(2e5)个地方填了数
其他地方都是0
可以任选选择一个位置 (R,C),计算同行同列的所有数之和。
找到最大的
*/