CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Valentine’s Day
#include <bits/stdc++.h>
#define maxn 10004
using namespace std;
double a[maxn];
int t, n;
int main(void)
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lf", &a[i]);
sort(a + 1, a + n + 1);
double ans = a[n], b = a[n] / (1 - a[n]);
int loc = n - 1;
while (loc && b < 1)
{
ans *= (1 - a[loc] + a[loc] / b);
b += a[loc] / (1 - a[loc]);
loc--;
}
printf("%.10lf\n", ans);
}
}
Welcome Party
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 9;
pair<ll, ll> p[N];
ll t, n;
int main()
{
for (scanf("%lld", &t); t--;)
{
scanf("%lld", &n);
multiset<ll> s0, s1;
for (ll i = 0; i < n; ++i)
scanf("%lld%lld", &p[i].first, &p[i].second), s1.insert(p[i].second);
sort(p, p + n);
ll ans = 1e18;
for (ll i = 0; i < n; ++i)
{
s1.erase(s1.find(p[i].second));
ll val = 2e18;
if (!s0.empty())
{
auto it0 = s0.lower_bound(p[i].first);
if (it0 != s0.end())
{
val = *it0;
if (it0 != s0.begin())
if (abs(p[i].first - val) > abs(p[i].first - *--it0))
val = *it0;
}
else
val = *s0.rbegin();
}
if (!s1.empty())
{
val = max(val, *s1.rbegin());
ans = min(ans, abs(p[i].first - *s1.rbegin()));
}
ans = min(ans, abs(p[i].first - val));
s0.insert(p[i].second);
}
printf("%lld\n", ans);
}
}
Block Breaker
#include <bits/stdc++.h>
#define maxn 2047
using namespace std;
int ans, n, m, q, t, x, y;
bool ed[maxn][maxn];
inline bool check(int x, int y)
{
return ed[x][y] && x != 0 && y != 0 && x != n + 1 && y != m + 1 && (!ed[x - 1][y] || !ed[x + 1][y]) && (!ed[x][y + 1] || !ed[x][y - 1]);
}
int qx[maxn * maxn], qy[maxn * maxn], l, r;
void bfs()
{
l = 1, r = 0;
qx[++r] = x, qy[r] = y;
//ed[x][y]=0;
while (l <= r)
{
int temx = qx[l], temy = qy[l];
// cout<<temx<<" "<<temy<<endl;
ed[temx][temy] = 0;
ans++;
l++;
if (check(temx, temy - 1))
qx[++r] = temx, qy[r] = temy - 1, ed[temx][temy - 1] = 0;
if (check(temx, temy + 1))
qx[++r] = temx, qy[r] = temy + 1, ed[temx][temy + 1] = 0;
if (check(temx - 1, temy))
qx[++r] = temx - 1, qy[r] = temy, ed[temx - 1][temy] = 0;
if (check(temx + 1, temy))
qx[++r] = temx + 1, qy[r] = temy, ed[temx + 1][temy] = 0;
}
}
int main(void)
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d%d", &n, &m, &q);
memset(ed, 1, sizeof(ed));
while (q--)
{
scanf("%d%d", &x, &y);
ans = 0;
if (ed[x][y])
bfs();
printf("%d\n", ans);
}
}
}
Make Rounddog Happy
建立笛卡尔树，在每个区间上做启发式计算。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 9;
struct Node
{
int val, lc, rc, ll, rr;
} tr[N];
int t, n, k;
ll dfs(int l, int r, int m)
{
ll ans = 0;
if (l > r)
return ans;
if (l == m && m == r)
{
if (tr[m].val - 1 <= k)
++ans;
return ans;
}
if (m - l < r - m)
{
for (int i = l; i <= m; ++i)
{
int up = min(tr[i].rr, r), lo = max(m, i + tr[m].val - k - 1);
if (up >= lo)
ans += up - lo + 1;
}
}
else
{
for (int i = m; i <= r; ++i)
{
int lo = max(tr[i].ll, l), up = min(m, k + i + 1 - tr[m].val);
if (up >= lo)
ans += up - lo + 1;
}
}
return ans + dfs(l, m - 1, tr[m].lc) + dfs(m + 1, r, tr[m].rc);
}
int main()
{
for (scanf("%d", &t); t--;)
{
scanf("%d%d", &n, &k);
vector<int> stak, vis(n + 1, 0);
for (int i = 0; i < n; ++i)
{
for (scanf("%d", &tr[i].val); !stak.empty() && tr[stak.back()].val < tr[i].val; stak.pop_back())
tr[i].lc = stak.back();
if (!stak.empty())
tr[stak.back()].rc = i;
stak.push_back(i);
}
for (int i = 0, j = 0; i < n; ++i)
{
for (; j < n && !vis[tr[j].val]; ++j)
vis[tr[j].val] = 1;
tr[i].rr = j - 1;
vis[tr[i].val] = 0;
}
vis.assign(n + 1, 0);
for (int i = n - 1, j = n - 1; i >= 0; --i)
{
for (; j >= 0 && !vis[tr[j].val]; --j)
vis[tr[j].val] = 1;
tr[i].ll = j + 1;
vis[tr[i].val] = 0;
}
printf("%lld\n", dfs(0, n - 1, stak.front()));
}
}