[蓝桥杯][2019年第十届真题]外卖店优先级、修改数组、糖果、特别数的和、等差数列

个人题解链接，历届试题，正在更新中~

外卖店优先级

题目描述
“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ? N。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。

每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0;而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。

如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中;如果 优先级小于等于 3，则会被清除出优先缓存。

给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优 先缓存中。

输入
第一行包含 3 个整数 N、M 和 T。
以下 M 行每行包含两个整数 ts 和 id，表示 ts 时刻编号 id 的外卖店收到一个订单。

输出
输出一个整数代表答案。

样例输入
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2
样例输出
1

思路
一道模拟题，记录上一次收到订单的时间，再按照时间来更新即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {template <typename T> inline void read(T &x) {x = 0; T f = 1;char s = getchar();for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;for(;  isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);x *= f;}
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e6+5;
struct node {int ts, id;bool operator < (const node & a) {return ts < a.ts;}
}e[N];
int ton[N], vis[N], las[N];
int main() {int n, m, t, k; read(n); read(m); read(t);_rep(1, m, i) read(e[i].ts), read(e[i].id);sort(e + 1, e + m + 1);_rep(1, m, i) {if(las[e[i].id] + 1 >= e[i].ts) {ton[e[i].id] += 2;if(ton[e[i].id] > 5) vis[e[i].id] = 1;las[e[i].id] = e[i].ts;} else {k = e[i].ts - las[e[i].id] - 1;ton[e[i].id] = max(0, ton[e[i].id] - k);if(vis[e[i].id] && ton[e[i].id] <= 3) vis[e[i].id] = 0;ton[e[i].id] += 2;if(ton[e[i].id] > 5) vis[e[i].id] = 1;las[e[i].id] = e[i].ts;}}int ans = 0;_rep(1, n, i) {if(las[i] < t) {k = t - las[i];ton[i] -= k;if(vis[i] && ton[i] > 3) ans++;} else if(vis[i]) ans++;}cout << ans << endl;
}

修改数组

题目描述
给定一个长度为 N 的数组 A = [A1, A2, · · · AN ]，数组中有可能有重复出现 的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 A2,A3,··· ,AN。

当修改 Ai 时，小明会检查 Ai 是否在 A1 ? Ai?1 中出现过。如果出现过，则 小明会给 Ai 加上 1 ;如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直 到 Ai 没有在 A1 ? Ai?1 中出现过。

当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。 现在给定初始的 A 数组，请你计算出最终的 A 数组

输入
第一行包含一个整数 N。 第二行包含N个整数A1,A2,··· ,AN

输出
输出N个整数，依次是最终的A1,A2,··· ,AN。

样例输入
5
2 1 1 3 4
样例输出
2 1 3 4 5

思路
并查集，节点的祖先为连续的为使用的节点，每次使用后和下一个点合并。
注意空间要开两倍，要用路径压缩

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {template <typename T> inline void read(T &x) {x = 0; T f = 1;char s = getchar();for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;for(;  isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);x *= f;}
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e6+5;
int a[N], f[N];
int Find(int x) {return f[x] == x ? x : f[x] = Find(f[x]);
}
int main() {int n; read(n);_rep(1, 2*n, i) f[i] = i;_rep(1, n, i) {read(a[i]);int x = Find(a[i]);a[i] = x;f[x] = Find(x+1);}_rep(1, n, i) printf("%d%c", a[i], " \n"[n==i]);
}

糖果

题目描述
糖果店的老板一共有 M 种口味的糖果出售。为了方便描述，我们将 M 种 口味编号 1 ? M。

小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而 是 K 颗一包整包出售。

幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知 道每包内的糖果口味。

给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖 果。

输入
第一行包含三个整数 N、M 和 K。
接下来 N 行每行 K 这整数 T1, T2, · · · , TK，代表一包糖果的口

输出
一个整数表示答案。如果小明无法品尝所有口味，输出 ?1。

样例输入
6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2
样例输出
2

思路
状压dp，把每个礼包用二进制表示，由于或操作没有逆运算，所以只能从前面推到现在。每次都要把为使用到的状态也继承过来，公用数组可以很方便的解决这个问题。转移方程： $dp[j|a[i]] = min(dp[j]+1, dp[j|a[i]]);$

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {template <typename T> inline void read(T &x) {x = 0; T f = 1;char s = getchar();for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;for(;  isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);x *= f;}
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
int a[105];
int dp[(1<<20) + 5];
int main() {int n, m, k, x;scanf("%d %d %d", &n, &m, &k);_rep(1, n, i) {_rep(1, k, j) {read(x);a[i] |= 1<<(x-1);}}memset(dp, 0x3f, sizeof dp);dp[0] = 0;int lim = (1<<m)-1;_rep(1, n, i) {for(int j = 0; j <= lim ; j++) { dp[j|a[i]] = min(dp[j]+1, dp[j|a[i]]);} } if(dp[lim] > n) puts("-1");else cout << dp[lim];
}

特别数的和

题目描述
小明对数位中含有 2、0、1、9 的数字很感兴趣(不包括前导 0)，在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 n 中，所有这样的数的和是多少?

输入
输入一行包含两个整数 n。

输出
输出一行，包含一个整数，表示满足条件的数的和
样例输入
40
样例输出
574

思路：
傻逼题，不谈

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {template <typename T> inline void read(T &x) {x = 0; T f = 1;char s = getchar();for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;for(;  isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);x *= f;}
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
bool pd(int n) {while(n) {if(n % 10 == 2 || n % 10 == 0 || n % 10 == 1 || n % 10 == 9) return 1;n /= 10;}return 0;
}
int main() {int n; read(n);int ans = 0;for(int i = 1; i <= n; i++) {if(pd(i)) ans += i;}cout << ans << endl;
}

等差数列

题目描述
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列，只记得其中 N 个整数。

现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有 几项?

输入
输入的第一行包含一个整数 N。 第二行包含N个整数A1,A2,···,AN。(注意A1 ?AN并不一定是按等差数列中的顺序给出)

输出
输出一个整数表示答案

样例输入
5
2 6 4 10 20
样例输出
10

思路
排序后，公差为所有相邻两项的差的最大公约数，记得特判公差为0

口胡证明：数列中任意的数都可以表示为 $a_n=a_1+(n-1)*d$,相邻两数的差就可以得到 $k*d$,要使d最大，即为求最大公约数。（说了=没说

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {template <typename T> inline void read(T &x) {x = 0; T f = 1;char s = getchar();for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;for(;  isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);x *= f;}
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
int a[100005];
int main() {int n; read(n);_rep(1, n, i) read(a[i]);sort(a + 1, a + n + 1);int x = a[2] - a[1];for(int i = 3; i <= n; i++) {x = __gcd(a[i]-a[i-1], x);}if(x)cout << (a[n] - a[1]) / x + 1 << endl;else cout << n << endl;
}