先放个代码，等改完T3再写思路
代码
#include<bits/stdc++.h>
#define re register
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read()
{
int x = 0, f = 0; char c = getchar();
while(c < '0') f |= (c == '-'), c = getchar();
while(c >= '0') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
int T;
ll L, R;
int sta[100], top;
int main()
{
T = read();
while(T--)
{
L = read(), R = read();
ll cnt = 1, now = 10;
while(R >= now) ++cnt, now *= 10;
now /= 10;
if(R / now > 1)
{
printf("%lld\n", min(R - L + 1, R - now + 1));
}else
{
top = 0;
ll tmp = R;
while(tmp) sta[++top] = tmp % 10, tmp /= 10;
for(re int i = top; i >= 1; --i)
{
if(sta[i] > 1)
{
printf("%lld\n", min(R - L + 1, now));
break;
}else if(sta[i] == 0)
{
printf("%lld\n", min(R - L + 1, R - R / 10));
break;
}else if(i == 1)
{
printf("%lld\n", min(R - L + 1, now));
break;
}
}
}
}
return 0;
}
代码
#include<bits/stdc++.h>
#define re register
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read()
{
int x = 0, f = 0; char c = getchar();
while(c < '0') f |= (c == '-'), c = getchar();
while(c >= '0') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int N = 1e5 + 10;
int n;
ll V;
ll a[N];
ll ans = 0x7ffffffffffffff;
priority_queue< pair<ll, int> > l, r;
int main()
{
double be = clock();
n = read(), V = read();
for(re int i = 1; i <= n; ++i)
{
a[i] = read();
l.push(pair<ll, int>(a[i], i));
r.push(pair<ll, int>(-a[i], i));
}
ans = min(ans, l.top().first + r.top().first );
while(clock() - be <= 950000)
{
for(re int i = 1; i <= 32; ++i)
{
ll tmp = -r.top().first , id = r.top().second ;
if(tmp * 2ll + V < tmp)
{
printf("%lld\n", ans);
return 0;
}
tmp = tmp * 2ll + V;
a[id] *= 2ll;
l.push(pair<ll, int>(a[id], id));
r.pop();
r.push(pair<ll, int>(-tmp, id));
if(l.top().second == r.top().second )
{
ll now = l.top().first ;
l.pop();
ans = min(ans, l.top().first + r.top().first );
l.push(pair<ll, int>(now, r.top().second ));
}else ans = min(ans, l.top().first + r.top().first );
if(ans <= 0)
{
printf("0");
return 0;
}
}
}
printf("%lld\n", max(ans, 0ll));
return 0;
}
代码
#include<bits/stdc++.h>
#define re register
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read()
{
int x = 0, f = 0; char c = getchar();
while(c < '0') f |= (c == '-'), c = getchar();
while(c >= '0') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
return f ? -x : x;
}
const int mod = 998244353;
const int N = 1e5 + 10;
int n, K, W, a[N];
ll d[N][6], C[6][6];
ll D[6][6];
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
ll sum[N << 2], cnt[N << 2][6][6], f[N << 2][6];
void pushup(int k)
{
sum[k] = sum[ls(k)] + sum[rs(k)];
for(re int x = 0; x <= W - 1; ++x)
{
for(re int y = 0; y <= W - 1; ++y)
{
cnt[k][x][y] = cnt[ls(k)][x][y];
}
for(re int y = 0; y <= W - 1; ++y)
{
cnt[k][x][(y + sum[ls(k)]) % W] += cnt[rs(k)][x][y];
}
}
for(re int t = 0; t <= K; ++t)
{
f[k][t] = f[ls(k)][t];
for(re int x = 0; x <= t; ++x)
{
(f[k][t] += f[rs(k)][x] * d[sum[ls(k)]][t - x] % mod * C[t][x] % mod) %= mod;
}
}
}
void motify(int p, int l, int r, ll pos, int val)
{
if(l == r)
{
if(val == 1)
{
++sum[p];
++cnt[p][pos % W][sum[p] % W];
for(re int t = 0; t <= K; ++t)
{
f[p][t] = (f[p][t] + pos * d[sum[p]][t] % mod) % mod;
}
}else
{
for(re int t = 0; t <= K; ++t)
{
f[p][t] = (f[p][t] - pos * d[sum[p]][t] % mod) % mod;
}
--cnt[p][pos % W][sum[p] % W];
--sum[p];
}
return ;
}
int mid = (l + r) >> 1;
if(pos <= mid) motify(ls(p), l, mid, pos, val);
else motify(rs(p), mid + 1, r, pos, val);
pushup(p);
}
ll qpow(ll a, ll b, ll mod)
{
ll ans = 1;
while(b)
{
if(b & 1) ans = ans * a % mod;
b >>= 1;
a = a * a % mod;
}
return ans;
}
int main()
{
for(re int i = 0; i <= 5; ++i)
{
C[i][0] = 1;
for(re int j = 1; j <= i; ++j)
{
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
}
for(re ll i = 0; i <= 1e5; ++i)
{
d[i][0] = 1;
for(re int j = 1; j <= 5; ++j)
{
d[i][j] = d[i][j - 1] * i % mod;
}
}
n = read(), K = read(), W = read();
for(re ll i = 0; i <= 5; ++i)
{
D[i][0] = 1;
for(re int j = 1; j <= 5; ++j)
{
D[i][j] = D[i][j - 1] * i % W;
}
}
for(re int i = 1; i <= n; ++i)
{
a[i] = read();
motify(1, 0, 1e5, a[i], 1);
}
ll inv = qpow(W, mod - 2, mod);
int q = read();
for(re int i = 1; i <= q; ++i)
{
int pos = read(), x = read();
motify(1, 0, 1e5, a[pos], -1);
a[pos] = x;
motify(1, 0, 1e5, a[pos], 1);
ll ans = f[1][K];
for(re ll x = 0; x <= W - 1; ++x)
{
for(re int y = 0; y <= W - 1; ++y)
{
ans -= x * D[y][K] % W * cnt[1][x][y] % mod;
}
}
ans = (ans % mod + mod) % mod;
printf("%lld\n", ans * inv % mod);
}
return 0;
}