Educational Codeforces Round 159 (Rated for Div. 2)
A - Binary Imbalance
解题思路:
有一对\((0,1)\)，那么\(0\)就能无限增长。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
typedef pair<ll, ll> pii;
const ll mod = 998244353;
ll n, m;
ll a[N];
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
int a = 0;
int b = 0;
for (int i = 0; i < n - 1; i++)
{
if (s[i] != s[i + 1])
{
puts("YES");
return;
}
}
for (auto c : s)
{
if (c == '1')
{
a++;
}
else
{
b++;
}
}
if (a >= b)
{
puts("NO");
}
else
{
puts("YES");
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - Getting Points
解题思路:
全部留到最后几天做。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
typedef pair<ll, ll> pii;
const ll mod = 998244353;
ll n, m;
ll a[N];
void solve()
{
ll n, p, l, t;
cin >> n >> p >> l >> t;
ll a = 1 + (n - 1) / 7;
ll ans = 0;
ll b = a / 2;
ll base = (l + 2 * t);
ll res = 0;
ll cnt = 0;
if (a & 1)
{
res = b * (base) + t + l;
cnt = b + 1;
}
else
{
res = b * base;
cnt = b;
}
// cout << res << endl;
if (res >= p)
{
ans = ((p + base - 1) / base);
}
else
{
ans = cnt + ((p - res) + l - 1) / l;
}
cout << n - ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Insert and Equalize
解题思路:
对\(a\)排个序，设\(b[i] = a[i + 1] - a[i]\)，我们得到数组\(b[1\sim (n - 1)]\)。
\(x = gcd(b)\)，此时根据此\(x\)计算数组\(a\)中的最小运算次数一定数最少的。
如果我们可以加入\(a[n + 1] = a[n] - x\),那么最小运算次数\(+ 1\)；同理，若\(a[n + 1] = a[n] - 2 * x\)，那么$ + 2$。
如果直到\(a[n + 1] = a[n] - (n - 1) * x\)都已经存在，那么\(a[n + 1] = a[n] + x\)。
因为\(a[n + 1] = a[n] + x\),最小运算次数$ + n$，且一定合法。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
set<int> s;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
s.insert(a[i]);
}
sort(a.begin() + 1, a.end());
int g = 0;
for (int i = 2; i <= n; i++)
{
g = gcd(g, a[i] - a[i - 1]);
}
// cout << g << endl;
if (g == 0)
{
puts("1");
return;
}
ll t = 0;
bool f = false;
for (int i = 1; i < n; i++)
{
if (!s.count(a[n] - i * g))
{
f = true;
t = a[n] - i * g;
break;
}
}
ll ans = 0;
for (int i = 1; i <= n; i++)
{
ans += (a[n] - a[i]) / g;
}
if (f)
{
ans += (a[n] - t) / g;
}
else
{
ans += n;
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Robot Queries
解题思路:
对于每一次查询，我们分三段判断\((1,l -1),(l ,r),(r+1,n)\)。
我们记录每个出现过的坐标是在第几步出现的\(pos[{x,y}] = i\)。
对于\((1,l-1)和(r + 1,n)\)我们可直接二分判断是否存在\((x,y)\)。
对于\((l,r)\)，由于题目要求，我们要进行一些变换。
设\((l-1)步到达的坐标为(a_1,b_1)，第r步到达的坐标为(a_2,b_2)\)。
一个区间段中无论正序倒序走，\(x\)轴和\(y\)轴最后的偏移量都是不变的。
目标位置到第\((l - 1)\)步位置的偏移量为\((x - a_1,y - b_1)\)。
第\(r\)步道减去这些偏移量为\((a_2 - (x - a_1),b_2 - (y - b_1))\)
\(x_1 = a_2 - (x - a_1),y_1 = b_2 - (y - b_1)\)。
\((x_1,y_1)\)，就是转换后我们正序走该走到的位置。
我们二分判断该位置是否存在即可。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;
#define fi first
#define se second
void solve()
{
int n, m;
cin >> n >> m;
string s;
cin >> s;
map<pii, vector<int>> v;
s = ' ' + s;
v[{0, 0}].push_back(0);
map<int, pii> pos;
int x = 0;
int y = 0;
for (int i = 1; i <= n; i++)
{
if (s[i] == 'U')
{
y++;
}
else if (s[i] == 'D')
{
y--;
}
else if (s[i] == 'L')
{
x--;
}
else
{
x++;
}
v[{x, y}].push_back(i);
pos[i] = {x, y};
// cout << i << ' ' << x << ' ' << y << endl;
}
for (int i = 1; i <= m; i++)
{
int x, y, l, r;
cin >> x >> y >> l >> r;
if (v[{x, y}].size())
{
auto idx = *(v[{x, y}].begin());
if (idx < l)
{
puts("YES");
continue;
}
idx = *v[{x, y}].rbegin();
if (idx >= r)
{
puts("YES");
continue;
}
}
int a1 = pos[l - 1].fi;
int b1 = pos[l - 1].se;
int a2 = pos[r].fi;
int b2 = pos[r].se;
int x1 = a2 + a1 - x;
int y1 = b2 + b1 - y;
// cout << a1 << b1 << endl;
// cout << a2 << ' ' << b2 << endl;
// cout << x1 << ' ' << y1 << endl;
if (v[{x1, y1}].size())
{
auto it = lower_bound(v[{x1, y1}].begin(), v[{x1, y1}].end(), l);
if (it != v[{x1, y1}].end())
{
int idx = *it;
if (idx >= l && idx <= r)
{
puts("YES");
continue;
}
}
}
puts("NO");
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
E - Collapsing Strings
解题思路:
\(s1 = aabba,s2 = abbcc\),我们发现剩下\(aacc\)。
观察得到规律:\(C(a,b) = len(s1) + len(s2) - 2 *len(a_{pre} == b_{suf})\)。就是减去二者前后缀公共部分。
先将所有字符长度累加起来。
\(trie\)树插入所有字符串，记录每个前缀出现的次数。
将每个字符逆序后一一查询，减去对应前后缀相同长度的代价。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;
#define fi first
#define se second
int tr[N][26];
ll cnt[N];
int idx;
void insert(string s)
{
int p = 0;
for (auto c : s)
{
int u = c - 'a';
if (!tr[p][u])
{
tr[p][u] = ++idx;
}
p = tr[p][u];
cnt[p]++;
}
}
ll query(string s)
{
ll res = 0;
int p = 0;
for (auto c : s)
{
int u = c - 'a';
if (!tr[p][u])
{
return res;
}
p = tr[p][u];
res += cnt[p] * 2;
}
return res;
}
void solve()
{
int n;
cin >> n;
vector<string> v;
ll ans = 0;
for (int i = 1; i <= n; i++)
{
string s;
cin >> s;
v.push_back(s);
ans += 2 * (ll)s.size() * n;
insert(s);
}
for (auto &s : v)
{
reverse(s.begin(), s.end());
ans -= query(s);
}
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}