A – Treasure Chest (abc299 a)
题目大意
给定一个包含 |*.
的字符串,其中|
两个,*
一个,问*
是否在两个|
之间。
解题思路
找到两个|
的下标(l, r)以及 *
的下标(mid),看看是否满足 (l 即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
string s;
cin >> n >> s;
int l = s.find('|'), r = s.find('|', l + 1), m = s.find('*');
if (m > l && m
B – Trick Taking (abc299 b)
题目大意
给定(n)个人的卡片,颜色为 (c_i),数字为 (r_i)。
如果其中有颜色为 (T)的牌,则该颜色中数字最大的卡片对应的人赢。如果没有,则颜色为第一个人的卡牌颜色(即(c_0))中数字最大的卡片对应的人赢。
问谁赢。
解题思路
按照题意的两种情况,分别判断即可。
神奇的代码
#include
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, t;
cin >> n >> t;
int maxx = 0;
int win = 0;
bool ok = false;
vector c(n);
for(int i = 0; i > c[i];
ok |= (c[i] == t);
}
if (!ok)
t = c[0];
for(int i = 0; i > r;
if (c[i] == t){
if (maxx
C – Dango (abc299 c)
题目大意
定义一种字符串(s)的等级(X)(是一个正整数), 满足仅包含 -o
,且头或尾仅一处为-
,其余都为o
。其等级(X)为 o
的数量。
给定一个字符串(T),问其子串的最大等级。
解题思路
依次遍历字符串(T),遇到两个 -
时期间就有一个等级。
然后再考虑从头到第一个-
的子串,从最后一个-
到尾的子串的等级。
注意单纯的一个-
并不是合法的((0)不是正整数)
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
string s;
cin >> n >> s;
int la = 0;
int ans = 0;
for(int i = 0; i
D – Find by Query (abc299 d)
题目大意
交互题。
这里有个长度为(n)的(01)字符串 (s) ,其中(s_1 = 0, s_n = 1) 。
你可以询问(s_i)的值。
输出一个位置 (p)满足 (s_p neq s_{p + 1})。
给定字符串长度(n),你最多问20次。 (n leq 2 times 10^5)。
解题思路
感觉好像和某次 (cf)的交互题很像。
注意题意保证了(s_1 = 0, s_n = 1)。
首先询问中间位置(mid = frac{n}{2}),如果(s_{mid} = 1),由于(s_n = 1),最坏情况很有可能这后半部份都是 (1),显然我们不该去问。但因为 (s_1 = 0, s_{mid} = 1),所以前半部份必定有一处(s_p = 0, s_{p + 1} = 1)。 反之(s_{mid} = 0)的情况同理。
这样,通过一次询问,我们可以把答案保证存在的区间砍半了。那最多砍 (log n)次就找到结果了。由于 (n leq 2 times 10^5),所以不会超过(20)次。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
int l = 1, r = n;
while(l + 1 > 1;
cout > ok;
if (ok)
r = mid;
else
l = mid;
}
cout
E – Nearest Black Vertex (abc299 e)
题目大意
给定一张图,要求给点涂黑白色,要求至少有一个黑点,且满足(k)个要求。
每个 要求 ((p_i, d_i))表示点 (p_i)距离黑点的最近距离恰好为 (d_i)。
点数、边数 (leq 2000)
解题思路
注意边数只有(2000)。
我们可以对每个要求的 (p_i)进行 (BFS),把距离其小于 (d)的点都标记为白色。
然后再对每个要求的 (p_i)进行 (BFS),把距离其为(d)的且未被标记为白色的点标记为黑色。
如果有个要求没有找到可以被涂黑色的点,就无解了。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector> edge(n);
for(int i = 0; i > u >> v;
-- u, -- v;
edge[u].push_back(v);
edge[v].push_back(u);
}
int k;
cin >> k;
vector forbid(n);
vector col(n);
vector> rule(k);
auto BFS = [&](int s, int d){
if (d == 0)
return;
vector dis(n, -1);
queue team;
dis[s] = 0;
team.push(s);
while(!team.empty()){
int u = team.front();
forbid[u] = 1;
team.pop();
for(auto &v : edge[u]){
if (dis[v] != -1)
continue;
dis[v] = dis[u] + 1;
if (dis[v] > p >> d;
-- p;
BFS(p, d);
}
bool ok = true;
auto paint = [&](int s, int d){
vector dis(n, -1);
queue team;
dis[s] = 0;
team.push(s);
while(!team.empty()){
int u = team.front();
team.pop();
if (!forbid[u] && dis[u] == d){
col[u] = 1;
return true;
}
for(auto &v : edge[u]){
if (dis[v] != -1)
continue;
dis[v] = dis[u] + 1;
if (dis[v]
F – Square Subsequence (abc299 f)
题目大意
给定一个字符串(s),问有多少个串 (t),满足 (tt)是 (s)的一个子序列。
解题思路
首先不考虑拼接,即问字符串(s)中本质不同的子序列数量。这个难点在于如何不算重。一个方法就是规定一种子序列映射到字符串的方式。
容易想到的就是最近匹配,就是判断字符串(t)是不是字符串 (s)的子序列时,对依次对每个 (t_i)进行最近的匹配,能匹配(s_j)就匹配上 。我们就按照这个方式去计算,每个本质不同的子序列就只算到一次。
即设 (dp[i])表示以 (i)结尾的本质不同的子序列数量,设 (pos)表示最大的 (j)满足 (j 且 (s_{pos} == s_i),那么 (dp[i] = sum_{j = pos}^{i} dp[j])
同样,我们可以按照此方式解决算重问题。从上述问题转到这个问题,一个自然的想法是设(dp[i][j])表示串 (tt)中,前一个 (t)的末尾在 (i),后一个 (t)的末尾在 (j)(显然有 (s_i == s_j))的子串数量。
为方便叙述,设 (tt)为 (t_1 t_2) ,即(T_{10}T_{11}..T_{1n}T_{20}T_{21}…T_{2n}),(nxt(i, j))表示 (s_i)后第一个 字符是 (j)的位置。
考虑初始状态,如果我们枚举第一个字母是(k)的话,那么 (i = nxt(0, k)),而 (j)的话感觉难以确定,它可以在任意的 (a_j = k)处,区别可能是串 (t)的长度不同。因此我们得枚举(j)的位置。
确定了初始状态 (dp[i][j] = 1)后,然后就枚举下一个字母 (k),由于采取的是最近匹配的原则,那么下一个匹配位置就分别是 (nxt(i, k))和 (nxt(j, k)),即 (dp[nxt(i, k)][nxt(j,k)] += dp[i][j]),转移式子即为此。
最后累计答案时,因为采取最近匹配的原则,我们只对满足 (nxt(x, s_{i}) = j)的 (dp[x][y])( (y geq j)即可)进行累加。
总的来说,就是设(dp[i][j][k])表示 (t_2)开头在 (s_i), (t_1)末尾在(s_j), (t_2) 末尾在(s_k)的方案数。
转移式子 (dp[i][nxt(j, c)][nxt(k, c)] += dp[i][j][k]),
答案(ans = sum_{i = 1}^{n} sum_{nxt(j, s_i) == i} sum_{k = i}^{n} dp[i][j][k])
总的时间复杂度是 (O(n^3))
神奇的代码
#include
using namespace std;
using LL = long long;
const int mo = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
string s;
cin >> s;
int n = s.size();
vector> nxt(n);
array pos;
pos.fill(-1);
for(int i = n - 1; i >= 0; -- i){
nxt[i] = pos;
pos[s[i] - 'a'] = i;
}
int ans = 0;
for(int st = 1; st > dp(n, vector(n, 0));
int first = s[st] - 'a';
int l = pos[first], r = st;
dp[l][r] = 1;
for(int i = l; i = r)
continue;
dp[nl][nr] += dp[i][j];
if (dp[nl][nr] >= mo)
dp[nl][nr] -= mo;
}
}
for(int i = l; i = mo)
ans -= mo;
}
}
}
cout
G – Minimum Permutation (abc299 g)
题目大意
给定一个长度为(n),仅包含数字 (1 sim m)的数组(a),问其字典序最小的一个子序列,是一个排序。
解题思路
从左到右依次考虑数组(a),对于当前的数字(a_i),一个朴素的想法是,选不选它,如果不选它,剩下的序列还能不能组成一个排列,如果不能,则一定要选它,那问题就剩下如何判断能不能组成,以及如果不一定选择,该怎么办。
能不能组成一个排列,就是看剩下序列的数字包不包含还没选择的数,设还没选择的数为(left)。
然后对于不是一定要选的数,我们可以先存起来,这样就有一个由满足要求的(a_i)组成的候选集合。
继续往右遍历,会遇到第一个不满足要求的位置(a_r),此时可以从候选集合里选数字最小的数,放到答案里,此时(left)就少了一个数。
因为(left)是判断某个数是不是一定要选的条件,当(left)少一时,说明这个条件变得更容易满足,因此(a_r)可能会满足,因此可以继续往右边遍历,往候选集合里添加新的数。而之前满足要求的还是满足。
由此就循环就可以得到最终答案了。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector a(n);
vector cnt(m + 1);
int ok = 0;
auto add = [&](int x, int val){
if (cnt[x] == 0)
ok ++;
cnt[x] += val;
};
auto sub = [&](int x, int val){
cnt[x] -= val;
if (cnt[x] == 0)
ok --;
};
for(auto &i : a){
cin >> i;
add(i, 1);
}
vector ans;
vector used(m + 1, 0);
priority_queue> candidate;
int target = m;
int l = -1;
for(int i = 0; i
赛后发现是道原题,去年的时候做过。
当时的思路更朴素,首先把第一个数(a_0)放入答案末尾,然后依次考虑之后的每个数(a_i)和答案的末尾的数 (ans_{back})比较,如果 (a_i ,且之后还有一个 (a_j(j > i) == ans_{back})的话,那么当前的 (ans_{back})可以扔掉(仍能保证后续能构造出一个排列),一直扔掉直到(a_i > ans_{back})或者不存在 (a_j(j > i) == ans_{back}),此时把 (a_i)放到答案末尾。
然后依次考虑就可以了。时间复杂度是(O(n))的。
简短的代码
#include
using namespace std;
typedef long long LL;
const int N = 1e6 + 8;
int a[N], cnt[N];
bool used[N];
int ans[N], cur;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> m >> n;
for(int i = 1; i > a[i];
cnt[a[i]] ++;
}
cur = 0;
for(int i = 1; i 0 && cnt[ans[cur]] && ans[cur] >= a[i]){
used[ans[cur]] = false;
-- cur;
}
++ cur;
ans[cur] = a[i];
used[a[i]] = true;
}
for(int i = 1; i
Ex – Dice Sum Infinity (abc299 h)
题目大意
解题思路
神奇的代码
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net