Educational Codeforces Round 156 (Rated for Div. 2)
A. Sum of Three
解题思路:
如果\(n \leq 6 或 n =9\),无解。
若\(n \% 3 == 0，t = \lfloor\frac{3}{n}\rfloor\):
- 若\(t = 0\)构造\(1,4,n - 5\)
- 否则，构造\(t - 3,t ,t + 3\)
若\(n \% 3 == 1 : 构造1,2，n - 3\)
若\(n \% 3 == 2:构造1,2,n - 3\)
主要就是三个数\(mod\ 3\)的和要等于\(n \% 3\)。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
int n;
scanf("%d", &n);
if (n <= 6 || n == 9)
{
puts("NO");
}
else
{
int t = n / 3;
int res = n % 3;
if (res == 0)
{
if (t % 3 == 0)
{
puts("YES");
printf("1 4 %d\n", n - 5);
}
else if (t % 3 == 1)
{
puts("YES");
printf("%d %d %d\n", t - 3, t, t + 3);
}
else
{
puts("YES");
printf("%d %d %d\n", t - 3, t, t + 3);
}
}
else if (res == 1)
{
puts("YES");
printf("1 2 %d\n", n - 3);
}
else
{
puts("YES");
printf("1 2 %d\n", n - 3);
}
}
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
B. Fear of the Dark
解题思路：
答案半径具有单调性，二分答案。
一共两种情况：两个点被一个圆包住了，两个点分别被一个圆包住了并且两圆相交。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
const double eps = 1e-10;
void solve()
{
double px, py, ax, ay, bx, by;
scanf("%lf %lf %lf %lf %lf %lf", &px, &py, &ax, &ay, &bx, &by);
double l = 0;
double r = 1e9;
auto dist = [&](double x1, double y1, double x2, double y2) -> double
{
double x = x1 - x2;
double y = y1 - y2;
return sqrtl(x * x + y * y);
};
auto cross = [&](double x1, double y1, double x2, double y2, double r)
{
double res = dist(x1, y1, x2, y2);
if (res <= 2 * r)
{
return true;
}
return false;
};
auto check = [&](double mid)
{
double pa = dist(px, py, ax, ay);
double pb = dist(px, py, bx, by);
double sa = dist(ax, ay, 0, 0);
double sb = dist(bx, by, 0, 0);
if ((sa <= mid && pa <= mid) || (sb <= mid && pb <= mid))
{
return true;
}
if (((sa <= mid && pb <= mid) || (sb <= mid && pa <= mid)) && cross(ax, ay, bx, by, mid))
{
return true;
}
return false;
};
while (r - l > eps)
{
double mid = (r + l) / 2;
if (check(mid))
{
r = mid;
}
else
{
l = mid;
}
}
printf("%.12lf\n", l);
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
C. Decreasing String
解题思路:
我们可以先用高斯求和二分出\(pos\)在\(s_r\)这一段中。
那么我们就是要得到从初识字符串中删掉\(r - 1\)个字符后的最小字典序字符串。
如何得到通过删除多个字符操作最小字典序字符串？
从前往后看，如果前面的字符大于后面的字符那么先删 前面的字符。
删完前面的还不够，此时我们的字符串一定是升序字符串，从后面一个个删就行了。
可用单调栈实现。
注意：\(pos\)开$longlong $
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
string s;
cin >> s;
ll pos;
scanf("%lld", &pos);
int n = s.size();
ll l = 0;
ll r = n + 1;
while (l + 1 < r)
{
ll mid = l + r >> 1;
if ((n + (n - mid + 1)) * (mid) / 2 < (ll)pos)
{
l = mid;
}
else
{
r = mid;
}
}
pos -= (n + (n - l + 1)) * l / 2;
int cnt = 0;
stack<char> stk;
for (int i = 0; i < n; i++)
{
while (cnt < l && (stk.size() && (stk.top() > s[i])))
{
cnt++;
stk.pop();
}
if (cnt < l)
{
stk.push(s[i]);
}
else
{
stk.push(s[i]);
}
}
string ans;
while (cnt < l && stk.size())
{
stk.pop();
cnt++;
}
while (stk.size())
{
ans += stk.top();
stk.pop();
}
reverse(ans.begin(), ans.end());
cout << ans[pos - 1];
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}
D. Monocarp and the Set
解题思路：
操作序列下标从\(0 \sim (n - 2)\)。
如果\(s[0] == '?'\)，由于前面只有一个数字，合法排列数一定为零。
往后，如果\(s[i] == '?'\)，意味着这一位有\(i\)中选法，因为前面一定已经有\(i\)个数字。
从后往前考虑对于符号插入位置，如果是\(>\),那就只能插在末尾，如果是\(<\),那就只能插入队头，如果是\(?\)，我们能插入\(i\)个空位中。\(i\)个空位是因为第\(i\)个操作时前民已经有了\(i + 1\)个数字.
对于\(i = 0\)，我们不进行统计和去除，因为\(*0,/0\)。\(s[0] == '?'\),如果我们开始统计了，后面如果要除去他的影响我们难以处理。开始不计算也合法。因为如果\(s[0] 一直等于 '?'\)，答案就一直是零。\(s[0] !='?'\)后，原本就没统计，也不需要去除其影响。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
const int mod = 998244353;
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
{
res = res * a % mod;
}
b >>= 1;
a = a * a % mod;
}
return res;
}
void solve()
{
int n, m;
cin >> n >> m;
n--;
string s;
cin >> s;
ll ans = 1;
for (int i = 1; i < n; i++)
{
if (s[i] == '?')
{
ans = ans * i % mod;
}
}
if (s[0] == '?')
{
puts("0");
}
else
{
printf("%lld\n", ans);
}
while (m--)
{
int idx;
cin >> idx;
char c;
cin >> c;
idx--;
// 如果非首位操作少了一个？
if (idx && s[idx] == '?')
{
ans = ans * qmi(idx, mod - 2) % mod;
}
s[idx] = c;
// 如果非首位操作多了一个?
if (idx && c == '?')
{
ans = ans * idx % mod;
}
if (s[0] == '?')
{
puts("0");
}
else
{
printf("%lld\n", ans);
}
}
}
int main()
{
int t = 1;
while (t--)
{
solve();
}
return 0;
}