给定一个长度为 的字符串,判断是否是给定的几种字符串之一。
#include <bits/stdc++.h>
using namespace std;
string s[] = {"ACE", "BDF", "CEG", "DFA", "EGB", "FAC", "GBD"};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
string str;
cin >> str;
for (int i = 0; i < 7; i++)
if (str == s[i])
{
cout << "Yes\n";
return 0;
}
cout << "No\n";
return 0;
}
给定一个 行 列的二维字符画,#
表示黑色,.
表示白色。
对于每个 的字符画,如果满足下面的条件,我们就说那是一个 Tak 码(写题解时我反应过来,大概就是类似二维码):
问字符画中有多少个 Tak 码,输出每个 Tak 码的左上角字符坐标。
暴力枚举每个 字符画,判断是否满足条件。
#include <bits/stdc++.h>
using namespace std;
int n, m;
char g[105][105];
bool check(int x, int y)
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (g[x + i][y + j] != '#')
return false;
for (int i = 6; i < 9; i++)
for (int j = 6; j < 9; j++)
if (g[x + i][y + j] != '#')
return false;
for (int i = 0; i < 4; i++)
if (g[x + i][y + 3] != '.')
return false;
for (int i = 0; i < 4; i++)
if (g[x + 3][y + i] != '.')
return false;
for (int i = 5; i < 9; i++)
if (g[x + i][y + 5] != '.')
return false;
for (int i = 5; i < 9; i++)
if (g[x + 5][y + i] != '.')
return false;
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> g[i][j];
}
}
for (int i = 1; i + 8 <= n; i++)
{
for (int j = 1; j + 8 <= m; j++)
{
if (check(i, j))
{
cout << i << " " << j << "\n";
}
}
}
return 0;
}
在苹果超市里有 个卖家和 个买家。
第 个卖家卖一个苹果的价格为 元或更高。
第 个买家买一个苹果的价格为 元或更低。
找到满足下面条件的最小的 $X:
条件:“能接受 元卖出苹果的商家数量”大于等于“接受 元买入的买家数量”
通过样例,很容易看出来 只有可能是某个出现过的数、或者某个出现过的数加一或减一。
那么可能的答案数量最多只有 也就是 级别。对于每个备选答案,我们可以通过两次二分找到几个卖家愿意卖,几个买家愿意买。最终时间复杂度显然是可以接受的。
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[212345];
int b[212345];
set<int> c;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
c.insert(a[i]);
c.insert(a[i] - 1);
c.insert(a[i] + 1);
}
for (int i = 1; i <= m; i++)
{
cin >> b[i];
c.insert(b[i]);
c.insert(b[i] - 1);
c.insert(b[i] + 1);
}
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
for (int X : c)
{
int aCnt = upper_bound(a + 1, a + n + 1, X) - a - 1; // cnt(a[i]<=X)
int bCnt = b + m + 1 - lower_bound(b + 1, b + m + 1, X); // cnt(a[i]>=X)
if (aCnt >= bCnt)
{
cout << X << "\n";
break;
}
}
return 0;
}
/*
aCnt 为几个人 X 元会价
bCnt 为几个人 X 元会买
aCnt >= bCnt
*/
给出一个只包含 (
、)
、?
的非空字符串 ,每个 ?
都可以用 (
或 )
来替换,假设有 个问好,显然有 种替换方案。问有多少种替换方案使得最终的序列为合法的括号序列。
答案可能很多,求方案数对 取模后的结果。
比较经典的括号序列 dp。
如果单单考虑 表示长度为 的前缀有几种匹配的方案是不行的。
对于
((?...
,这样的序列。因为这里第三个问号不管怎么选都没法使得长度为 的前缀合法。但不同的选择方案的意义显然是不同的(((...
需要后面有三个多余的)
,而(()...
只需要后面有一个多余的)
。
可以考虑 表示长度为 的前缀有多少种方案有 个多余的 (
。
如果有多余的
)
后面怎么也找补不回来了,所以只需要考虑前面提供多少个多余的(
按这个思路,转移也很好想了,细节可以看下面的代码。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
string s;
int n;
// 前i个字符,余下j个左括号没匹配时的方案数
int dp[3005][3005];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
n = s.length();
s = "^" + s + "$";
dp[0][0] = 1;
for (int i = 1; i <= n; i++)
{
if (s[i] == '(')
{
dp[i][0] = 0;
for (int j = 1; j <= i; j++)
dp[i][j] = dp[i - 1][j - 1];
}
else if (s[i] == ')')
{
for (int j = 0; j <= i; j++)
dp[i][j] = dp[i - 1][j + 1];
}
else if (s[i] == '?')
{
dp[i][0] = 0;
for (int j = 1; j <= i; j++)
dp[i][j] = dp[i - 1][j - 1];
for (int j = 0; j <= i; j++)
dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD;
}
}
cout << dp[n][0] << "\n";
return 0;
}
有 个三维立方体,互相之间可以相切,但不能相交(任意两个立方体交集的体积都为 )。
给定每个立方体的某个大对角线的两个端点的坐标:。
求每个立方体跟多少个立方体相切(交集的表面积不为 )。
这题的数据范围看上去非常唬人, 到了 。
但实际上考虑到立方体之间互不相交。所以对于 这个三维范围内的每个小立方体来说,必然最多属于某一个大立方体。小立方体最多只有 个,可以直接暴力枚举每个小立方体被哪个大立方体拥有。
小立方体:对于整数 ; 为一个小立方体。
两个大立方体相切,实际上等价于存在相切的两个小立方体分别属于不同的大立方体。而每个小立方体最多只跟 个小立方体相切。因此可以考虑枚举每个小立方体 及相邻的小立方体 ,如果这两个小立方分属于大立方体 与大立方体 ,就说明 与 相切。
这样我们可以找到最多 组大立方体相切的关系。计算去重后数量输出即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
int id[105][105][105];
set<int> e[MAXN + 5]; // 记录 i 与哪些重叠
int dx[] = {1, -1, 0, 0, 0, 0};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
int x, y, z, xx, yy, zz;
cin >> x >> y >> z >> xx >> yy >> zz;
//写题解时发现不需要这三个 if
if (x > xx)
swap(x, xx);
if (y > yy)
swap(y, yy);
if (z > zz)
swap(z, zz);
for (int X = x + 1; X <= xx; X++)
for (int Y = y + 1; Y <= yy; Y++)
for (int Z = z + 1; Z <= zz; Z++)
id[X][Y][Z] = i;
}
for (int i = 1; i <= 101; i++)
for (int j = 1; j <= 101; j++)
for (int k = 1; k <= 101; k++)
{
int now = id[i][j][k];
if (now == 0)
continue;
for (int fx = 0; fx < 6; fx++)
{
int nxt = id[i + dx[fx]][j + dy[fx]][k + dz[fx]];
if (nxt == 0 || nxt == now)
continue;
e[now].insert(nxt);
}
}
for (int i = 1; i <= n; i++)
{
cout << e[i].size() << "\n";
}
return 0;
}
有 个物品。每个物品可以是“易拉罐、常规罐子、开罐器”三个种类中的一种。用 来描述第 个物品:
你现在可以从 个物体中选出 个,求获得的幸福值之和最大为多少。
F 题居然也有这么简单的题目,简单贪心就好了。
首先考虑不使用开罐器的情况,肯定是选择幸福值最大的最多 个易拉罐,所有其他易拉罐都可以不用管了。
接下来如果要常规罐子则必然要使用开罐器,如果使用开罐器必然贪心选次数最多的。那么按照次数从大到小一个个累计选择就好。
还没选到 个物品时开罐器可以直接拿。已选了 个物品时,多选一个开罐器,显然要丢掉一个已选的罐子,这里必然贪心丢幸福值最低的罐子即可。
每选择一个开罐器带来的效果是开罐次数可以增加。当还有开罐次数时,如果还没到 个物品,直接开一个幸福值最高的常规罐子就好了,如果已经到了 个物品,就丢掉一个已选的幸福值最低的罐子,然后开一个幸福值最高的常规罐子就好了。因为每个物品只被考虑了 次,所以时间复杂度肯定够的。
整体下来思维难度比较小,细节相对需要注意得比较多。下面的代码没有考虑可以优化的细节(比如选了 个物品后,如果“当前幸福值最高的常规罐子”比“幸福值最低的已选易拉罐”的幸福值还要低,就不用做了)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
vector<int> ptc; // 易拉罐
vector<int> rc; // 罐头
vector<int> co; // 开罐器(每一个对应的次数)
priority_queue<int> q; // 选了哪些快乐值的罐子
bool cmp(int x, int y)
{
return x > y;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int t, x;
cin >> t >> x;
if (t == 0)
ptc.push_back(x);
if (t == 1)
rc.push_back(x);
if (t == 2)
co.push_back(x);
}
sort(ptc.begin(), ptc.end(), cmp);
sort(rc.begin(), rc.end(), cmp);
sort(co.begin(), co.end(), cmp);
int sum = 0; // 已选之和
int ans = 0; // 答案
int cnt = 0; // 已选数量
int coAll = 0; // 还能开几个普通罐子
for (int i = 0; i < min((int)ptc.size(), m); i++)
{
q.push(-ptc[i]);
sum += ptc[i];
cnt++;
}
ans = max(ans, sum);
for (int i = 0, j = 0; i < co.size(); i++)
{
if (cnt < m)
{
coAll += co[i];
cnt++;
}
else if (!q.empty())
{
sum -= -q.top();
cnt--;
q.pop();
coAll += co[i];
cnt++;
}
else
{
break;
}
// 直接放
while (cnt < m && coAll > 0 && j < rc.size())
{
sum += rc[j];
cnt++;
coAll--;
q.push(-rc[j]);
j++;
}
// 替换
while (cnt == m && coAll > 0 &&
j < rc.size() && !q.empty() &&
rc[j] > -q.top())
{
sum -= -q.top();
q.pop();
sum += rc[j];
q.push(-rc[j]);
coAll--;
j++;
}
ans = max(ans, sum);
}
cout << ans << "\n";
return 0;
}
对于一棵有 个节点的树,节点编号为 。
找到满足下述条件的三元组 的数量:
数据范围:
对于题目的要求,归根结底就是:
草稿纸上画画后很容易发现,对于每一组满足条件的 必然能找到一个唯一的点 使得以 为根时三个点分属于不同的子树。
那么一个直观的想法就是枚举每个点 为根时的贡献。假设 为根时的子树分别为 :
那么此时三个点分属三个子树的方案数简单一容斥就出来了~
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
vector<int> e[212345];
int siz[212345];
int mid[212345];
int ans;
int all;
int cal(int n)
{
int all = (n) * (n - 1) * (n - 2) / 6; // n-1个点三点对数量
if (n < 3)
all = 0;
return all;
}
void dfs(int u, int fa)
{
siz[u] = 1;
int sub = 0; // 需要减去的
for (int v : e[u])
{
if (v == fa)
continue;
dfs(v, u);
sub += cal(siz[v]);
sub += (n - 1 - siz[v]) * siz[v] * (siz[v] - 1) / 2;
siz[u] += siz[v];
}
int temp = n - siz[u];
sub += cal(temp);
sub += (n - 1 - temp) * temp * (temp - 1) / 2;
mid[u] = all - sub;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
all = cal(n - 1);
for (int i = 1; i <= n - 1; i++)
{
int a, b;
cin >> a >> b;
e[a].push_back(b);
e[b].push_back(a);
}
dfs(1, 0);
for (int i = 1; i <= n; i++)
{
ans += mid[i];
}
cout << ans << "\n";
return 0;
}
Taka 决定给 个人都取个昵称,第 个人希望自己的外号是 。
Taka 不希望有重复的昵称,讨论后每个人除了同意自己昵称为 也同意自己昵称为多个 连起来。
Taka 从 号到 号一个个取昵称,按照下面的步骤来给第 i 个人取昵称:
输出
考虑什么情况下才会出现重复的名字。
显然 与 可能会产生冲突,但是 与 之间不可能产生冲突。
我们可以通过某些字符串算法算出每个昵称的最小循环节,那么最小循环节不同的昵称之间不可能产生冲突。
对于每种最小循环节,找到对应的是哪些字符串。一个个考虑分配:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int n;
string s[MAXN + 5];
int z[MAXN + 5];
void exKMP(string &s)
{
z[0] = 0;
for (int l = 0, r = 0, i = 1; i < s.length(); i++)
{
// s[i...r] == s[i-l...r-l]
if (i <= r && z[i - l] < r - i + 1)
z[i] = z[i - l];
else
{
z[i] = max(0, r - i + 1);
while (i + z[i] < s.length() && s[z[i]] == s[i + z[i]])
z[i]++;
}
if (i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
}
unordered_map<string, vector<int>> sv;
int ans[MAXN + 5];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> s[i];
// 计算每个最短循环节有哪些字符串
for (int i = 1; i <= n; i++)
{
exKMP(s[i]);
int len = s[i].length();
int now = len; // 最短循环节长度
// 没必要优化了,反正整个跑完也就 2e5,不用优化成根号的时间复杂度
for (int j = 1; j < s[i].length(); j++)
{
if (len % j == 0 && z[j] == len - j)
{
now = j;
break;
}
}
string x = s[i].substr(0, now); // s[i]的最短循环节
sv[x].push_back(i);
}
for (auto it = sv.begin(); it != sv.end(); it++)
{
unordered_set<int> used; // 已有哪些倍率
unordered_map<int, int> pre; // 上一个 d 倍被扩充为了 pre[d] 倍
used.insert(0);
// 枚举当前循环节的所有字符串(s[i])
for (int i : it->second)
{
int d = s[i].length() / (it->first).length(); // 目前是 d 倍循环节
int now = pre[d]; // 尝试 now 倍 (kd 倍)
while (used.find(now) != used.end())
now += d;
pre[d] = now;
/*
没必要把中间所有的 pre[xd] = now
如果 d=1 时,now 达到了 30,那说明之前就把 1~29 倍的都踩过了
可能 pre[2~29] 之前不是 30,但感性理解一下,整个的均摊增长不会太快
从另一个角度,大数据想必也很难造,实践下来只记录较小的d也可以很快过,可以看下面的第二份代码
*/
used.insert(now);
ans[i] = now / d; // k
}
}
for (int i = 1; i <= n; i++)
cout << ans[i] << " ";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
...
int main()
{
...
for (auto it = sv.begin(); it != sv.end(); it++)
{
unordered_set<int> used;
// 只处理 d <= 10 的情况~~~~~
int pre[11] = {};
used.insert(0);
for (int i : it->second)
{
int d = s[i].length() / (it->first).length();
int now = d;
// 只处理 d <= 10 的情况~~~~~
if (d <= 10)
now = pre[d];
while (used.find(now) != used.end())
now += d;
// 只处理 d <= 10 的情况~~~~~
if (d <= 10)
pre[d] = now;
used.insert(now);
ans[i] = now / d; // k
}
}
...
}