2023.02.21 模拟赛小结
目录更好的阅读体验戳此进入
赛时思路
T1
给定 $ k $ 以及序列 $ t $ 个数 $ a_1, a_2, \cdots a_t $，你需要求出最小的 $ k $ 的倍数满足其所有数字都不存在 $ a_1, a_2, \cdots, a_t $。
类似的原题是 Vijos-1065 最小数字倍数，该题要求仅存在对应数。
一道很简单但做得很麻烦的题，首先考虑的是 $ dp(i, j, k) $ 表示前 $ i $ 位最后一位为 $ j $ 然后第 $ i $ 对 $ i + 1 $ 及以后的贡献为 $ k $ 对应的数，这样的时空复杂度卡的都很死，然后写转移的时候发现 $ j $ 是没有意义的，只转移合法的即可，于是去掉一维但时间复杂度不变。
转移及其复杂，需要考虑很多细节，也不知道我咋想出来的，奇奇怪怪。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
/*
37 9
0 1 2 3 4 5 6 7 9
233333 8
2 3 4 5 6 7 8 9
*/
template < typename T = int >
inline T read(void);
bitset < 10 > exist[20];
bitset < 10 > ban;
int K, T;
// basic_string < int > ends[10];
map < int, int > mp;
unordered_set < int > vis;
unordered_set < int > nums;
unordered_set < int > legal;
ll dp[20][1100000];
ll pow10[20];
ll ans(LONG_LONG_MAX);
int main(){
freopen("digit.in", "r", stdin);
freopen("digit.out", "w", stdout);
pow10[0] = 1;
for(int i = 1; i <= 18; ++i)pow10[i] = pow10[i - 1] * 10;
memset(dp, -1, sizeof dp);
K = read(), T = read();
int digitK(0), tmp = K;
while(tmp)++digitK, tmp /= 10;
for(int i = 1; i <= T; ++i)ban[read()] = true;
if(K == 0)printf("%d\n", ban[0] ? -1 : 0), exit(0);
for(int i = 1; i <= 2 * K; ++i){
int val = i;
bool flag(true);
while(val){
if(ban[val % 10]){flag = false; break;}
val /= 10;
}if(flag)legal.insert(i);
}
for(int j = 1; vis.find(K * j % 10) == vis.end(); ++j){
vis.insert(K * j % 10);
// if(!ban[K * j % 10])nums.insert(K * j % 10), mp[K * j % 10] = K * j;
nums.insert(K * j % 10), mp[K * j % 10] = K * j;
}
// dp[0][0][0] = 0;
for(auto num : nums){
if(ban[mp[num] % 10])continue;
dp[1][mp[num] / 10] = mp[num];
// printf("upd dp[%d][%d] = %d\n", 1, mp[num] / 10, mp[num]);
if(!(mp[num] / 10) || legal.find(mp[num] / 10) != legal.end())ans = min(ans, dp[1][mp[num] / 10]);
}if(ans != LONG_LONG_MAX)printf("%lld\n", ans), exit(0);
// exit(0);
for(int i = 1; i <= 18 - digitK; ++i){
for(auto j : nums){
for(int k = 0; k <= 1000000; ++k){
if(!~dp[i][k])continue;
if(ban[(j + k % 10) % 10])continue;
if(j + k % 10 <= 9){
// printf("[%d][%d][%d] => [%d][%d][%d]\n", i, j, k, i + 1, j + k % 10, k / 10 + mp[j] / 10);
dp[i + 1][k / 10 + mp[j] / 10] = dp[i][k] + (ll)mp[j] * pow10[i];
if(!(k / 10 + mp[j] / 10) || legal.find(k / 10 + mp[j] / 10) != legal.end())ans = min(ans, dp[i + 1][k / 10 + mp[j] / 10]);
}else{
// printf("[%d][%d][%d] => [%d][%d][%d]\n", i, j, k, i + 1, (j + k % 10) % 10, k / 10 + mp[j] / 10 + 1);
dp[i + 1][k / 10 + mp[j] / 10 + 1] = dp[i][k] + (ll)mp[j] * pow10[i];
if(!(k / 10 + mp[j] / 10 + 1) || legal.find(k / 10 + mp[j] / 10 + 1) != legal.end())ans = min(ans, dp[i + 1][k / 10 + mp[j] / 10 + 1]);
}
}
}
if(ans != LONG_LONG_MAX)printf("%lld\n", ans), exit(0);
}printf("-1\n");
// int N = read();
// for(int i = 1; i <= 10000; ++i){
// ll val = (ll)N * i;
// int cnt(0);
// while(val){
// exist[++cnt][val % 10] = true;
// val /= 10;
// }
// }
// for(int i = 1; i <= 10; ++i){
// printf("digit %d : ", i);
// for(int j = 0; j <= 9; ++j)if(exist[i][j])printf("%d ", j);
// printf("\n");
// }
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
T2
存在 $ n $ 个任务，每个任务有有效时间 $ [s_i, t_i] $，任务量 $ w_i $，存在一个可变速处理器，其速度为 $ v $ 时处理对应任务的时间就是 $ \dfrac{w_i}{v} $，你需要最小化最大速度使得所有任务可以在规定时间内完成。
大概想出来贪心了，左端点排序然后右端点排序建堆，但是取元素然后区间覆盖的时候一直没太想好怎么处理，主要的问题是卡在了，建树最大实际上应该是 $ t_i $ 而不是 $ n \times w_i $，所以直接建树的话复杂度是正确的，总之就是最后全挂了。。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define EPS (1e-9)
/*
3
5
1 4 2
3 6 3
4 5 2
4 7 2
5 8 1
6
1 7 25
4 8 10
7 10 5
8 11 5
10 13 10
11 13 5
8
15 18 10
20 24 16
8 15 33
11 14 14
1 6 16
16 19 12
3 5 12
22 25 10
*/
template < typename T = int >
inline T read(void);
int N;
struct Task{
ld s, t;
ld w;
friend const bool operator < (const Task &a, const Task &b){
return a.t > b.t;
}
}task[21000];
// class SegTree{
// private:
// int tr[21000000 << 2], lz[]
// public:
// void Pushup(int p){
// }
// }
bool Check(int V){
int curpos(1);
priority_queue < Task > tsk;
ld curT(1.0);
while(true){
if(tsk.empty()){
if(curpos > N)return true;
curT = max(curT, (ld)task[curpos].s);
while(curpos <= N && curT >= (ld)task[curpos].s)tsk.push(task[curpos++]);
}
auto tp = tsk.top(); tsk.pop();
curT = max(curT, (ld)tp.s);
auto nxt = tsk.empty() ? Task{INT_MAX, INT_MAX, INT_MAX} : tsk.top();
if(curT + (ld)tp.w / (ld)V <= nxt.s){
curT += (ld)tp.w / (ld)V;
if(curT - EPS > (ld)tp.t)return false;
}else{
tsk.push(Task{nxt.s, tp.t, tp.w - (nxt.s - curT) * V});
curT = nxt.s;
}
// printf("V = %d, curT = %.5Lf, [%d ~ %d]\n", V, curT, tp.s, tp.t);
while(curpos <= N && curT >= (ld)task[curpos].s)tsk.push(task[curpos++]);
}
}
int main(){
freopen("cpu.in", "r", stdin);
freopen("cpu.out", "w", stdout);
int T = read();
while(T--){
N = read();
for(int i = 1; i <= N; ++i)task[i].s = read(), task[i].t = read(), task[i].w = read();
sort(task + 1, task + N + 1, [](const Task &a, const Task &b)->bool{return a.s < b.s;});
int l = 0, r = 21000000, ans(-1);
while(l <= r){
int mid = (l + r) >> 1;
if(Check(mid))ans = mid, r = mid - 1;
else l = mid + 1;
}printf("%d\n", ans);
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
T3
存在初始全为白色的序列，每次从 $ [1, n] $ 随机一个 $ a $ 再随机一个 $ b $，以 $ \min(a, b) $ 作为 $ l $，以 $ \max(a, b) $ 作为 $ r $，将区间染黑，求 $ k $ 次随机后的期望黑色点个数。
手推了一下次数为 $ 1 $ 的部分分，对了。搓了个假的暴力，过了一点。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MOD (998244353ll)
template < typename T = int >
inline T read(void);
ll N, K;
ll qpow(ll a, ll b){
ll ret(1), mul(a);
while(b){
if(b & 1)ret = ret * mul % MOD;
b >>= 1;
mul = mul * mul % MOD;
}return ret;
}
ll dp[20][20][20];
ll ans(0);
int main(){
freopen("paint.in", "r", stdin);
freopen("paint.out", "w", stdout);
// printf("%lld\n", 17 * qpow(9, MOD - 2) % MOD);
N = read(), K = read();
if(K == 1){
// ll v = (N + 2) >> 1;
// printf("%lld\n", ((v * ((2 * N + 2) % MOD) % MOD - v * (v + 1) % MOD + (N - v) * ((2 * N + 2) % MOD) % MOD - (N + v + 1) % MOD * (N - v) % MOD) % MOD + MOD) % MOD * qpow(N, MOD - 2) % MOD * qpow(N, MOD - 2) % MOD);
printf("%lld\n", (((N + 1) * (N + 1) % MOD * N % MOD - N * (N + 1) % MOD * ((2 * N + 1) % MOD) % MOD * qpow(3, MOD - 2) % MOD - N) % MOD + MOD) % MOD * qpow(N, MOD - 2) % MOD * qpow(N, MOD - 2) % MOD);
exit(0);
}
ll base = qpow(N, MOD - 2) * qpow(N, MOD - 2) % MOD;
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
(dp[1][min(i, j)][max(i, j)] += base) %= MOD;
for(int i = 2; i <= K; ++i){
for(int j = 1; j <= N; ++j){
for(int k = 1; k <= N; ++k){
int l = min(j, k), r = max(j, k);
for(int L = 1; L <= N; ++L){
for(int R = L; R <= N; ++R){
int rl = min(l, L), rr = max(r, R);
(dp[i][rl][rr] += dp[i - 1][L][R] * base % MOD) %= MOD;
}
}
}
}
}
for(int i = 1; i <= N; ++i)
for(int j = i; j <= N; ++j)
(ans += dp[K][i][j] * (j - i + 1) % MOD) %= MOD;
printf("%lld\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
T4
给定序列 $ A_n \(，\) q $ 次询问每次给定 $ p, l, r $ 表示其在 $ p $ 想要值域在 $ [l, r] $ 中切存在于 $ A_n $ 中的每一种数各一个，定义贡献为物品的位置与 $ p $ 的距离，最小化贡献，对于每次询问输出最小值。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
/*
5 4
1 5 3 3 1
3 3 4
4 4 5
2 1 4
5 3 5
*/
template < typename T = int >
inline T read(void);
int N, Q;
int A[210000];
basic_string < int > pos[1100];
// class SegTree{
// private:
// int tr[210000 << 2];
// #define LS (p << 1)
// #define RS (LS | 1)
// #define MID ((gl + gr) >> 1)
// public:
// void Pushup()
// }
int main(){
freopen("magic.in", "r", stdin);
freopen("magic.out", "w", stdout);
N = read(), Q = read();
for(int i = 1; i <= N; ++i)pos[A[i] = read()] += i;
if(N > 5000){
while(Q--){
ll ans(0);
int p = read(), l = read(), r = read();
r = min(r, N);
if(p < l)ans = (ll)(l - p + r - p) * (r - p - (l - p) + 1) / 2;
else if(p > r)ans = (ll)(p - l + p - r) * (p - l - (p - r) + 1) / 2;
else ans = (ll)(p - l + 1) * (p - l) / 2 + (ll)(r - p + 1) * (r - p) / 2;
printf("%lld\n", ans);
}
}
while(Q--){
ll ans(0);
int p = read(), l = read(), r = read();
for(int i = l; i <= r; ++i){
if(pos[i].empty())continue;
int mn(INT_MAX);
auto it = lower_bound(pos[i].begin(), pos[i].end(), p);
if(it != pos[i].end())mn = min(mn, abs(p - *it));
if(it != pos[i].begin())mn = min(mn, abs(p - *prev(it)));
if(it != pos[i].end() && next(it) != pos[i].end())mn = min(mn, abs(p - *next(it)));
ans += mn;
}printf("%lld\n", ans);
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
正解
T1
考虑 $ \bmod{k} $ 意义下，可以考虑 $ dp(i, j) $ 表示前 $ i $ 位模 $ k $ 意义下值为 $ j $ 的数然后进行数位 DP，这样是简单且平凡的。
还有更平凡的做法即进行 bfs，记录前驱以及具体数位值，跑一遍即可。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template < typename T = int >
inline T read(void);
int K, T;
bitset < 10 > ban;
basic_string < int > vals;
bitset < 1100000 > vis;
struct Node{
int p; int val; Node* pre;
};
void Print(Node* p){
basic_string < int > ans;
for(auto cur = p; ~cur->val; cur = cur->pre)
ans += cur->val;
reverse(ans.begin(), ans.end());
for(auto v : ans)printf("%d", v);
printf("\n");
exit(0);
}
void bfs(void){
queue < Node* > cur;
cur.push(new Node{0, -1, npt});
while(!cur.empty()){
auto p = cur.front(); cur.pop();
for(auto i : vals){
if(p->p == 0 && i == 0)continue;
int np = (p->p * 10 + i) % K;
auto nod = new Node{np, i, p};
if(!np)return Print(nod);
if(vis[np])continue;
vis[np] = true;
cur.push(nod);
}
}
}
int main(){
K = read(), T = read();
for(int i = 1; i <= T; ++i)vals += read();
bfs();
printf("-1\n");
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
T2
问题关键在于转换，即不去枚举事件，而去枚举时间，这样贪心更显然且极好维护。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template < typename T = int >
inline T read(void);
int N;
struct Task{
int s, t;
int w;
friend const bool operator < (const Task &a, const Task &b){
return a.t > b.t;
}
}task[21000];
bool Check(int V){
int curpos(1);
priority_queue < Task > tsk;
for(int i = 1; i <= 20000; ++i){
while(curpos <= N && i >= task[curpos].s)tsk.push(task[curpos++]);
int tot(V);
while(!tsk.empty() && tot){
if(i >= tsk.top().t)return false;
// printf("i = %d, Making [%d, %d]\n", )
if(tot >= tsk.top().w)tot -= tsk.top().w, tsk.pop();
else{
auto tp = tsk.top(); tsk.pop();
tp.w -= tot; tot = 0; tsk.push(tp);
break;
}
}
}if(curpos <= N || !tsk.empty())return false;
return true;
}
int main(){
int T = read();
while(T--){
N = read();
for(int i = 1; i <= N; ++i)task[i].s = read(), task[i].t = read(), task[i].w = read();
sort(task + 1, task + N + 1, [](const Task &a, const Task &b)->bool{return a.s < b.s;});
int l = 0, r = 21000000, ans(-1);
while(l <= r){
int mid = (l + r) >> 1;
if(Check(mid))ans = mid, r = mid - 1;
else l = mid + 1;
}printf("%d\n", ans);
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
T3
考虑将问题转化为求每个点被涂黑的期望并利用线性性求和，考虑正难则反，用 $ 1 $ 减去不被涂黑的概率即可，显然 $ k $ 次后为：
\[f(x) = 1 - (\dfrac{(x - 1)^2 + (n - x)^2}{n^2})^k \]暴力求解期望 $ 80\texttt{pts} $，考虑后者应为最高 $ 2k + 1 $ 项的多项式，于是使用拉格朗日插值即可在 $ O(k \log k) $ 或 $ O(k^2) $ 的复杂度内计算，代码略了。
T4
离线询问差分一下算点的贡献就行，奇怪题。
UPD
update-2023_02_21 初稿
标签：return,21,int,2023.02,ret,MOD,小结,void,define From： https://www.cnblogs.com/tsawke/p/17180239.html