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;
}

 

评论

此博客中的热门博文