A.Alarm Clock

题意：

一个人要睡 $a$ 分钟， $b$ 分钟后闹钟响。如果响的时候没睡够 $a$ 分钟，会再设 $c$ 分钟后响，并花 $d$ 分钟重新入睡，如果还没睡够则重复上述操作。判断能否睡够 $a$ 分钟，如果能，输出起床时间

题解：

如果 $b \geq a$ ，则睡 $b$ 分钟即可，如果 $d \geq c$ ，则一定不能睡够，其余情况都能睡够，其时间为 $b + (a - b + (c - d - 1) / (c - d) * c)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    if (b >= a)
    {
        printf("%d\n", b);
        return;
    }
    else if (d >= c)
    {
        puts("-1");
        return;
    }
    printf("%lld\n", b + (a - b + (c - d - 1ll)) / (c - d) * c);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Ternary String

题意：

给一个字符串 $s$ ，找到一个子串，要求满足该字串包含 $1、2、3$ 并且是所有满足条件中最短的，输出其长度

题解：

遍历序列，更新 $1、2、3$ 最近一次的位置，包含该位置最短的字串长度就是该位置的下标减去 $1、2、3$ 最新一次最小的那个下标的值，取 $min$ 即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int pre[3];
void solve()
{
    int len = INF;
    string s;
    cin >> s;
    memset(pre, -1, sizeof(pre));
    for (int i = 0; i < s.length(); i++)
    {
        pre[s[i] - '1'] = i;
        int x = *min_element(pre, pre + 3);
        if (x != -1)
            len = min(len, i - x + 1);
    }
    if (len != INF)
        printf("%d\n", len);
    else
        puts("0");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C1.Simple Polygon Embedding

题意：

给定一个边长为 $1$ 的正 $2·n$ 边形，要求能完全将它嵌入的正方形的边长，其中 $n$ 为偶数

题解：

图片说明
以正八边形为例，可以看出 $b$ 即为所求， $b=\frac{a}{tan\angle{OBA}}$ ,其中 $\begin{cases} \angle{OAB}=\angle{OBA} \\ \angle{OAB}+\angle{OBA}+\angle{AOB}=180° \\ \angle{AOB}=\frac{360°}{n} \end{cases}$
因此 $\angle{OBA}=\frac{sin{\frac{\pi}{2}}}{n}$
$b=\frac{a}{tan\ {\frac{sin{\frac{\pi}{2}}}{n}}}=\frac{1}{tan\ {\frac{acrsin{1}}{n}}}$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n;
    scanf("%d", &n);
    printf("%.7f\n", 1 / tan(asin(1) / n));
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C2.Not So Simple Polygon Embedding

题意：

给定一个边长为 $1$ 的正 $2·n$ 边形，要求能完全将它嵌入的正方形的边长，其中 $n$ 为奇数

题解：

图片说明
以六边形为例，作 $\angle{BOC}$ 的垂直平分线 $OD$ ，易证得 $\angle{BOD}=\angle{BAC}$
可以求出AB长度为 $\frac{1}{sin\angle{BAC}}=\frac{1}{sin\frac{\pi}{2n}}$
过 $A$ 作垂线， $AE$ 即为所求， $AE={AB}*{cos\angle{BAE}}$ ,其中可以发现 $\angle{BAE} \in [0,\frac{\pi}{2}-sin{\frac{\pi}{2}}]$ ,求导可得当 $\angle{BAE}=\frac{\angle{BAC}}{2}$ 时最大，于是 $AE={AB}*{cos\frac{\angle{BAE}}{2}}$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double pi = acos(-1);
void solve()
{
    int n;
    scanf("%d", &n);
    double a = pi / (n * 2);
    double r = 1 / sin(a);
    a /= 2;
    printf("%.9lf\n", r * cos(a));
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Multiset

题意：

给定一个长度为 $n$ 的数组 $a_n$ ，有 $q$ 次询问，每次询问给出一个 $k_i$ ，如果 $k_i \geq 0$ ，则把 $k_i$ 插入数组中，如果 $k_i < 0$ ，则删除数组中第 $\left| k_i \right|$ 小的数。最后如果数组中还有数，则任意输出其中一个，否则输出 $0$ 。

题解：

用树状数组来存数组中的所有数，每加入一个数就把它加入到树状数组中。删掉第 $\left| k_i \right|$ 小的数，先用二分在树状数组中找到该值，再从树状数组中删去即可。最终遍历数组判断此时树状数组单点的值是否大于 $0$ ，是则输出，否则输出 $0$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const int INF = 0x3f3f3f3f;
int c[maxn];
inline int lowbit(int x) { return x & (-x); }
void add(int x, int val)
{
    for (; x < maxn; x += lowbit(x))
        c[x] += val;
}
int query(int x)
{
    int res = 0;
    for (; x; x -= lowbit(x))
        res += c[x];
    return res;
}
int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 0, x; i < n; i++)
    {
        scanf("%d", &x);
        add(x, 1);
    }
    while (q--)
    {
        int k;
        scanf("%d", &k);
        if (k >= 0)
            add(k, 1);
        else
        {
            k = -k;
            int l = 1, r = maxn;
            while (l < r)
            {
                int mid = (l + r) >> 1;
                if (query(mid) >= k)
                    r = mid;
                else
                    l = mid + 1;
            }
            add(l, -1);
        }
    }
    if (query(maxn - 1) == 0)
        puts("0");
    else
        for (int i = 1; i < maxn; i++)
            if (query(i) - query(i - 1) > 0)
            {
                cout << i << '\n';
                break;
            }
    return 0;
}

E.Graph Coloring

题意：

给定 $n$ 个点 $m$ 条边的无向图，不保证联通，给每个点标号 $1、2、3$ 。 $1、2、3$ 号点个数分别为 $n1、n2、n3$ 。要求每条边的两点，标号之差绝对值为 $1$ 。
如果存在一种满足条件方案，则输出标点的方案。

题解：

首先可以知道 $1$ 号点只能和 $2$ 号点相连， $2$ 号点可以和 $1、3$ 号点相连， $3$ 号点可以和 $2$ 号点相连，所以可以发现 $1、3$ 号点本质上是相同的，因此可以只看成两种标号，因此问题就转化为二分图染色问题。题目不保证联通，因此对于每个联通块首先要满足不存在奇环，否则肯定不存在满足条件的方案。然后对于每个联通块，将它分为奇数层和偶数层，要求对于每个联通块的其中一个层相加的和刚好等于 $n2$ ，就很类似背包问题，可以用dp来实现。在算每个联通块的时候，可以记录下其中一层的路径，那么最终就将构造 $n2$ 的那一层标为 $2$ ，剩下的贪心标为 $1$ 和 $3$ 即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5005;
const int INF = 0x3f3f3f3f;
vector<int> G[maxn];
int n, m, n1, n2, n3, p[maxn], x[maxn];
int cnt, d1[maxn], d2[maxn];
bool dp[maxn][maxn], rev[maxn];
void dfs(int u)
{
    if (x[u] == 1)
        d1[cnt]++;
    else
        d2[cnt]++;
    for (int v : G[u])
    {
        if (!x[v])
        {
            x[v] = 3 - x[u];
            p[v] = cnt;
            dfs(v);
        }
        else if (x[u] == x[v])
        {
            puts("NO");
            exit(0);
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    scanf("%d%d%d", &n1, &n2, &n3);
    for (int i = 0, x, y; i < m; i++)
    {
        scanf("%d%d", &x, &y);
        x--;
        y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    cnt = 0;
    dp[0][0] = true;
    for (int i = 0; i < n; i++)
        if (!x[i])
        {
            p[i] = cnt;
            x[i] = 1;
            dfs(i);
            for (int j = d1[cnt]; j <= n2; j++)
                dp[cnt + 1][j] |= dp[cnt][j - d1[cnt]];
            for (int j = d2[cnt]; j <= n2; j++)
                dp[cnt + 1][j] |= dp[cnt][j - d2[cnt]];
            cnt++;
        }
    if (!dp[cnt][n2])
    {
        puts("NO");
        return 0;
    }
    puts("YES");
    while (cnt--)
    {
        rev[cnt] = !dp[cnt][n2 - d2[cnt]];
        if (rev[cnt])
            n2 -= d1[cnt];
        else
            n2 -= d2[cnt];
    }
    for (int i = 0; i < n; i++)
    {
        if (rev[p[i]])
            x[i] = 3 - x[i];
        if (x[i] == 2)
            putchar('2');
        else if (n1)
        {
            putchar('1');
            n1--;
        }
        else
            putchar('3');
    }
    puts("");
}

Educational Codeforces Round 87 (Rated for Div. 2)