给 个小写字母组成的字符串,如果有一个或多个字符串恰好是 and
, not
, that
, the
, 或 you
,就输出 Yes
,否则输出 No
。
#include <bits/stdc++.h>
#define int long long
using namespace std;
string x, s[5] = {"and", "not", "that", "the", "you"};
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
bool flag = false;
for (int i = 1; i <= n; i++)
{
cin >> x;
for (int j = 0; j < 5; j++)
if (x == s[j])
flag = true;
}
if (flag)
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
给定一个 行 列的字符画 ,表示一个地图。
字符画中 1~9
表示炸弹(数字即炸弹的威力),#
表示墙,.
表示空地块。
如果一面墙到炸弹的曼哈顿距离小于等于该炸弹的威力,那么这面墙就会被炸弹炸毁。
请输出所有炸弹爆炸后的地图。
数据范围这么小,直接对每个炸弹暴力枚举每个位置是否会被炸掉就好。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int r, c;
char g[25][25];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> r >> c;
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++)
cin >> g[i][j];
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++)
{
if ('0' <= g[i][j] && g[i][j] <= '9')
{
for (int x = 1; x <= r; x++)
for (int y = 1; y <= c; y++)
if (g[x][y] == '#' &&
abs(x - i) + abs(y - j) <= g[i][j] - '0')
{
g[x][y] = '.';
}
}
}
for (int i = 1; i <= r; i++)
{
for (int j = 1; j <= c; j++)
{
if (g[i][j] == '#')
cout << g[i][j];
else
cout << '.';
}
cout << "\n";
}
return 0;
}
给定 只袜子,第 只袜子的颜色为 。
颜色一样的两只袜子可以组成一双,求最多能组成多少双袜子。
显然如果统计好了每种颜色的数量,那么答案就是“每个数量除以 下取整”之和。
统计每种颜色的数量这里因为颜色对应的数字范围太大,所以直接开计数数组肯定不行。有很多做法可以处理,比如排序后遍历算数量。比如离散化后再处理之类都可以。
这里给出用 STL
的 map
处理的做法。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[512345];
map<int, int> m;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
m[a[i]] = m[a[i]] + 1;
}
int ans = 0;
for (pair<int, int> x : m)
ans += x.second / 2;
cout << ans << "\n";
return 0;
}
对于一个长度为偶数的数字字符串,如果将其以某种方式重排列后可以让前半部分与后半部分相同,我们就说这个字符串是快乐的!
比如 20230322
可以重排列为 02320232
,此时前后两部分都是 0232
。所以我们可以认为 20230322
是快乐的。
现在给你一个数字字符串 ,求他有多少个子串是快乐的。
假设子串 是快乐的,显然必然满足以下结论: 中的每种数字字符的出现次数都是偶数
由此容易想到,如果统计了每个前缀的每种数字字符的出现次数。比如 sum[i][dig]
表示 中,数字 的出现总次数。
那么 是快乐的就等价于,对于任意的 dig
,sum[r][dig] - sum[l-1][dig]
是偶数。
由此我们就有了 的做法。
进一步观察可以发现 sum[r][dig] - sum[l-1][dig]
是偶数就等价于 sum[r][dig]
与 sum[l-1][dig]
奇偶性相同。
所以 “以 结尾的快乐子串数量”就等价于“r
前面有多少个 i
满足 sum[i][0~9]
与 sum[r][0~9]
奇偶性相同”。
因为只需要考虑奇偶性,所以可以考虑把每种 0~9
的奇偶性都压缩成一个整数表示,整数二进制的 位表示 出现次数对 取模的结果。这样处理后计数会非常方便。当然如果你就用一个 0/1
字符串作为 key
丢到 map
里也是没问题的的。
#include <bits/stdc++.h>
#define int long long
using namespace std;
string s;
int cnt[512345][10];
int now[512345];
int preCnt[(1 << 10)];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
int n = s.length();
s = "^" + s;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < 10; j++)
cnt[i][j] = cnt[i - 1][j];
cnt[i][s[i] - '0']++;
now[i] = 0;
for (int j = 0; j < 10; j++)
if (cnt[i][j] % 2 == 1)
now[i] = now[i] | (1 << j);
}
preCnt[0] = 1;
int ans = 0;
for (int i = 1; i <= n; i++)
{
ans += preCnt[now[i]];
preCnt[now[i]]++;
}
cout << ans << endl;
return 0;
}
对于一个长度为 的序列 , 为 内的整数。
对于每个为 的元素 ,都会挑选一个 内的整数替代。
显然不同替代方案下,整个序列第 小的元素值都会不同,求第 小元素的期望值。
期望不就是“每种答案乘以对应的概率”之和嘛,那么枚举所有可能的答案,计算出对应的概率不就好了。
假设我们钦定答案为 ,那么显然可以通过当前非 0
的数 、、 的数量来判断概率是否为 。
如果概率非 ,很好算出最多还能加多少个大于 的数和小于 的数。而我们有一些 等着分配,就来算算对于每个分配方案有多少种可能性。
比如如果有 个 ,需要分配 个到 ,分配 个到 ,剩下的都变为 。那么可能的方案数就是 。除以总的方案数 就是对应的概率了。
这种做法需要先 枚举所有的 ,然后 枚举所有的大于 、小于 数量划分方案。然后用预处理好的组合数及幂数 算出对应的概率即可。
总的时间复杂度 ,粗略一算,哪怕 和 都是 ,最后也不过就是 8e9
,甚至模拟以下发现常数还挺小,最后只需要 2e9
就跑得完。一看时限 4sec
,简直就是为我这个做法而定的。
但是写完后,2000
个 0
的极限数据在 上必须要跑 6sec
。于是,悲。
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
#define PII pair<int, int>
using namespace std;
const int MOD = 998244353;
int n, m, k;
int a[2005];
int C[2005][2005];
int PO[2005][2005];
int cnt0;
vector<int> el;
int p[2005]; // p[i]:第k名为i的概率
// 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);
C[0][0] = 1;
for (int i = 1; i <= 2000; i++)
for (int j = 0; j <= i; j++)
{
if (j == 0 || j == i)
C[i][j] = 1;
else
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
for (int i = 0; i <= 2000; i++)
{
PO[i][0] = 1;
for (int j = 1; j <= 2000; j++)
PO[i][j] = (PO[i][j - 1] * i) % MOD;
}
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] == 0)
cnt0++;
else
el.push_back(a[i]);
}
sort(el.begin(), el.end());
for (int x = 1; x <= m; x++)
{
int lt = lower_bound(el.begin(), el.end(), x) - el.begin();
int gt = el.end() - upper_bound(el.begin(), el.end(), x);
int eq = el.size() - lt - gt;
if (lt > k - 1 || gt > n - k)
{
p[x] = 0;
continue;
}
p[x] = 0;
// cout << x << ": " << p[x].first << "/" << p[x].second << endl;
int ltMore = min(k - 1 - lt, cnt0); // 还能有最多几个小于x的
int gtMore = min(n - k - gt, cnt0); // 还能有最多几个大于x的
for (int lt0 = 0; lt0 <= ltMore; lt0++)
{
int base = C[cnt0][lt0] * PO[x - 1][lt0] % MOD;
for (int gt0 = 0; gt0 <= gtMore && gt0 + lt0 <= cnt0; gt0++)
{
int eq0 = cnt0 - lt0 - gt0;
p[x] = (p[x] + base * C[cnt0 - lt0][gt0] % MOD *
PO[m - x][gt0]) %
MOD;
// cout << lt0 << " ~ " << eq0 << " ~ " << gt0 << "=" << C[cnt0][lt0] * PO[x - 1][lt0] % MOD * C[cnt0 - lt0][gt0] % MOD * PO[m - x][gt0] % MOD << endl;
// cout << C[cnt0][lt0] << "," << PO[x - 1][lt0] << endl;
// cout << C[cnt0 - lt0][gt0] << "," << PO[m - x][gt0] << endl;
}
}
}
int ans = 0;
for (int x = 1; x <= m; x++)
ans = (ans + x * p[x]) % MOD;
// cout << ans.first << " " << ans.second << "\n";
cout << ans * inv(PO[m][cnt0], MOD) % MOD << "\n";
return 0;
}
考虑到 ,做一点点小转换就变成了
而求 就不像 需要把所有 分为三类 、、 了。只需要把 分为两类 、。这样最后枚举划分时就从 降到了 。然后就能过了。