20191112测试总结

T1搞得心态崩了。。。

T1:WOJ4816

发现按照字典树的dfs序来就可以构成一个合法的序列。

但是由于trie树要爆空间,所有我们直接sort就可以了。

千万不要随便使用ios::sync_with_stdio(false),我不会告诉你我因为这个调了半天

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, num, b[1000005], c[1000005], ans[1000005][2];
struct node
{
    int id;
    string s;
    bool operator<(const node &bb) const
    {
        return s < bb.s;
    }
} a[1000005];
char buf[1 << 21];
int p1 = -1;
const int p2 = (1 << 21) - 1;
void flush()
{
    fwrite(buf, 1, p1 + 1, stdout);
    p1 = -1;
    return;
}
void pc(char x)
{
    if (p1 == p2)
        flush();
    buf[++p1] = x;
    return;
}
void write(int x)
{
    char buffer[10];
    int len = -1;
    if (x >= 0)
    {
        do
        {
            buffer[++len] = (x % 10) | 48;
            x /= 10;
        } while (x);
    }
    else
    {
        pc('-');
        do
        {
            buffer[++len] = -(x % 10) | 48;
            x /= 10;
        } while (x);
    }
    while (len >= 0)
        pc(buffer[len--]);
    return;
}
int main()
{
    scanf("%d", &n);
    for (register int i = 1; i <= n; ++i)
    {
        a[i].id = i;
        cin >> a[i].s;
    }
    sort(a + 1, a + n + 1);
    for (register int i = 1; i <= n; ++i)
    {
        b[a[i].id] = i;
        c[i] = a[i].id;
    }
    for (register int i = 1; i <= n; ++i)
        if (b[i] != i)
        {
            ++num;
            ans[num][0] = i;
            ans[num][1] = c[i];
            swap(b[i], b[c[i]]);
            swap(c[b[i]], c[b[c[i]]]);
        }
    write(num);
    pc('\n');
    for (register int i = 1; i <= num; ++i)
    {
        write(ans[i][0]);
        pc(' ');
        write(ans[i][1]);
        pc('\n');
    }
    flush();
    return 0;
}

T2:WOJ4817

公式不好打,直接放solution。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
int n, m, x, cnt, t[100005], num[100005], sum[100005], rt[100005];
struct tree
{
    int l;
    int r;
    int sum;
} tr[7500005];
void add(int y, int &x, int l, int r, int w)
{
    x = ++cnt;
    tr[x] = tr[y];
    ++tr[x].sum;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (w <= mid)
        add(tr[y].l, tr[x].l, l, mid, w);
    else
        add(tr[y].r, tr[x].r, mid + 1, r, w);
    return;
}
int query(int id, int l, int r, int ql, int qr)
{
    if (!id)
        return 0;
    if (ql == l && qr == r)
        return tr[id].sum;
    int mid = (l + r) >> 1;
    if (qr <= mid)
        return query(tr[id].l, l, mid, ql, qr);
    if (ql >= mid + 1)
        return query(tr[id].r, mid + 1, r, ql, qr);
    if (ql <= mid && qr >= mid + 1)
        return query(tr[id].l, l, mid, ql, mid) + query(tr[id].r, mid + 1, r, mid + 1, qr);
}
int check(int k)
{
    int res = 0;
    int pos = lower_bound(t + 1, t + n + 1, k) - t;
    res = sum[pos] - (k / x) * (n - pos + 1);
    res += query(rt[pos], 0, x, k % x + 1, x);
    return res;
}
int solve(int s)
{
    int l = 0, r = t[n], ans = 0;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid) > s)
            l = mid + 1;
        else
            r = mid;
    }
    ans = l;
    return max(ans - s, 0LL);
}
signed main()
{
    scanf("%lld%lld%lld", &n, &m, &x);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &t[i]);
    sort(t + 1, t + n + 1);
    for (int i = 1; i <= n; ++i)
        num[i] = t[i] / x;
    for (int i = n; i >= 1; --i)
    {
        sum[i] = sum[i + 1] + num[i];
        rt[i] = rt[i + 1];
        add(rt[i + 1], rt[i], 0, x, t[i] % x);
    }
    for (int i = 1; i <= m; ++i)
    {
        int s;
        scanf("%lld", &s);
        printf("%lld\n", solve(s));
    }
    return 0;
}

T3:WOJ4818

又是计数题。。。

我们只需要算出每个数在每个数位的结果再求和就好了。

需要配合各种前缀和和预处理,这里就不写了,反正计数题慢慢推就对了

#include <iostream>
#include <cstdio>
#define mod 998244353
using namespace std;
int n, k, ans, num[500005], a[500005], c[500005], cnt[500005], sum[500005], inv[500005];
char s[500005];
int ksm(int aa, int kk)
{
    int bb = 1;
    while (kk)
    {
        if (kk & 1)
            bb = (long long)bb * aa % mod;
        aa = (long long)aa * aa % mod;
        kk >>= 1;
    }
    return bb;
}
int C(int aa, int bb)
{
    if (bb < aa || aa < 0)
        return 0;
    return (long long)num[bb] * inv[aa] % mod * inv[bb - aa] % mod;
}
int main()
{
    scanf("%d%d%s", &n, &k, s);
    for (int i = 0; i < n; ++i)
        a[i + 1] = s[i] ^ 48;
    cnt[0] = 1;
    for (int i = 1; i <= n; ++i)
        cnt[i] = (long long)cnt[i - 1] * 10 % mod;
    num[0] = 1;
    inv[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        num[i] = (long long)num[i - 1] * i % mod;
        inv[i] = ksm(num[i], mod - 2);
    }
    for (int i = n - 1; i >= 1; --i)
        c[i] = (c[i + 1] + (long long)cnt[n - i - 1] * C(k - 1, i - 1) % mod) % mod;
    for (int i = 1; i <= n; ++i)
        c[i] = (c[i] + (long long)cnt[n - i] * C(k, i - 1) % mod) % mod;
    for (int i = 1; i <= n; ++i)
        ans = (ans + (long long)c[i] * a[i] % mod) % mod;
    printf("%d", ans);
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注