第一题 789C
CF 789C
题意：求满足题意最大的子段和。
解：对每个$i$存$a_i - a_{i+1}$，然后对于题目-1的限制，序列是正负正负或者负正负正的。最大的子段和可以想到DP做，所以预处理两个正负正负，负正负正的数组，在上面做字段和DP即可。
子段和DP最优解在每一步取。$dp(i)=max(dp(i-1)+c, 0)$有负数的情况，没有就直接$dp(i)=max(dp(i-1)+c, c)$，最后的$dp(n)$不是答案，注意
知识点：写题目一定要把题意抽象化完再做
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
LL n, a[MAXN], b[MAXN], oddz[MAXN], evenz[MAXN];
LL abss(LL x) {return x > 0 ? x : -x;}
void clean() {
}
int solve() {
clean();
for (LL i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (LL i = 1; i < n; i++) b[i] = abss(a[i] - a[i + 1]);
for (LL i = 1; i <= n; i++) oddz[i] = evenz[i] = b[i];
for (LL i = 2; i <= n; i += 2) oddz[i] *= -1;
for (LL i = 1; i <= n; i += 2) evenz[i] *= -1;
LL sum = 0, mks = -4223372036854775807ll;
for (LL i = 1; i < n; i++) sum = max(sum + oddz[i], 0ll), mks = max(mks, sum);
sum = 0;
for (LL i = 1; i < n; i++) sum = max(sum + evenz[i], 0ll), mks = max(mks, sum);
printf("%lld\n", mks);
return 0;
}
int main() {
scanf("%lld", &n), solve();
return 0;
}
第二题 913C
CF 913C
题意：给你$n$瓶柠檬水，给你相对应的每瓶的价格，每瓶的体积分别对应$2^{i−1}$升，给你要买的体积，求出要买的最低价格
解： 我们可以发现相邻瓶的体积是二倍的关系，可以利用这一点，处理出每个体积对应的最低价格，直接扫一遍即可。然后买体积最大的最划算。所以像倍增一样尽可能买体积大的，不够就多买。
知识点：$2^{i}$就要想到一些性质。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const LL MAXN = 30 + 5;
LL n, L, ci[MAXN];
void clean() {
}
int solve() {
clean();
for (LL i = 1; i <= n; i++) scanf("%lld", &ci[i]);
for (LL i = 2; i <= n; i++) if (ci[i - 1] * 2 < ci[i]) ci[i] = ci[i - 1] * 2;
LL ans = 9223372036854775807ll, sum = 0;
for (LL i = n; i; i--) {
LL nd = L / (1 << (i - 1));
L -= nd * (1 << (i - 1)), sum += nd * ci[i];
ans = min(ans, sum + (L > 0) * ci[i]);
}
printf("%lld\n", ans);
return 0;
}
int main() {
scanf("%lld%lld", &n, &L), solve();
return 0;
}
第三题 814C
题意：给你一个长度为$n$的字符串，然后给你$q$个询问，$m$和字符$c$，代表任意修改$m$个字符为$c$后，连续的$c$最长是多长。
解：最优化可以想到 DP 。本题其实相当于选择一个最大的区间使得区间内修改后能全部是$c$。所以可以设$dp(i,j)$为$[i,j]$修改最少次数。但是这里讲一种尺取法，尺取法就是有两个指针$l,r$, 先向右扩展$r$，然后判断$l,r$是否符合条件，如果不符合就把$l$向右扩展，然后得到一个合法区间，取最大值即可。
知识点：抽象题目，简化题目。本题可以抽象为 $q$个询问，在长度为$n$的序列中找到一个最长区间$[i,j]$使得这个区间$m+g=j-i+1, g$为区间内数为$c$的个数。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1500 + 5;
int n, q;
char s[MAXN];
void clean() {
}
int solve() {
clean();
scanf("%s%d", s + 1, &q);
char ch[10];
for (int i = 1; i <= q; i++) {
int m;
scanf("%d%s", &m, ch);
char c = ch[0];
int l = 1, r, len = 0, ans = 0;
for (r = 1; r <= n; r++) {
if (s[r] != c) len++;
if (len > m) {
if (s[l] != c) len--;
l++;
}
ans = max(ans, r - l + 1);
}
printf("%d\n", ans);
}
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}
第四题 777C
题意：给出$n \cdot m$的矩阵，$k$次查询，如果第$l$行到$r$行至少有一列是非递减的，则输出Yes，否则输出No
解：这题时间复杂度有点迷……原矩阵中每一段非递减序列都看作一条线段，询问也看作线段，即转化为线段包含问题。只要有线段包含了询问线段，就可以输出Yes。我们记录每一行开始最长的非递减序列，然后进行去重操作，如果之前的线段包括了这条，这条就可以删去。并且按照行来做，只能前面的包含后面的线段，因为开始位置在递增。然后对于询问直接找就行。优化是如果当前所有线段长度没有询问线段长，就直接输出No。极端数据应该会出一个递减序列来卡。
知识点：时间复杂度这种很迷的直接写就OK
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
vector<int> G[MAXN];
int tot, n, m, q, dp[MAXN], mks;
set<int> s;
pair<int, int > p[MAXN];
void clean() {
mks = 0, tot = 0, ms(dp, 0);
}
int solve() {
clean();
int x;
for (int j = 1; j <= m; j++) G[0].push_back(0);
for (int i = 1; i <= n; i++) {
G[i].push_back(0);
for (int j = 1; j <= m; j++) scanf("%d", &x), G[i].push_back(x);
}
for (int j = 1; j <= m; j++) {
int lst = 1, tmp = 1;
for (int i = 2; i <= n; i++) {
if (G[i][j] < G[i - 1][j]) {
dp[lst] = max(dp[lst], tmp);
tmp = 1, lst = i; continue;
}
tmp++;
}
dp[lst] = max(dp[lst], tmp);
}
for (int whw, i = 1; i <= n; i++) {
whw = dp[i] + i - 1;
mks = max(mks, dp[i]);
if (s.lower_bound(whw) != s.end()) {
} else s.insert(whw), p[++tot] = make_pair(i, i + dp[i] - 1);
}
scanf("%d", &q);
while (q--) {
int f = 0, l, r; scanf("%d%d", &l, &r);
if (r - l + 1 > mks) {
printf("No\n");
continue;
}
for (int i = 1; p[i].first <= l; i++) {
if (p[i].second >= r) {
printf("Yes\n"), f = 1;
break;
}
}
if (!f) printf("No\n");
}
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
第五题 764C
题意：给出一个无根加权树，求出一个点使得这个点为根时每个子树颜色相同。
解：预处理每一个点(包括自己)相连的点颜色总数。然后如果图中每个点相连的点颜色总数不超过2，那么有一个颜色总数为2的点必然会与其他所有颜色总数为2的点相连。枚举一下是否有这样的点即可。如果超过2，那么树中只能有一个超过2的点，并且这个点与其他所有颜色总数为2的点连通。判断一下即可。
知识点：本题与CF 796C相似，都是找点判断信息(度数等)，然后利用信息来解题
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
int n, c[MAXN], df[MAXN], tax[MAXN];
vector<int> G[MAXN];
void ins(int x, int y) {G[x].push_back(y), G[y].push_back(x);}
void clean() {
ms(tax, 0), ms(df, 0);
}
int solve() {
clean();
for (int x, y, i = 1; i < n; i++) scanf("%d%d", &x, &y), ins(x, y);
for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
int f = 0;
for (int i = 1; i < n; i++) if (c[i] != c[i + 1]) f = 1;
if (!f) return printf("YES\n1\n"), 0;
for (int i = 1; i <= n; i++) {
tax[c[i]] = 1, df[i]++;
for (int j = 0; j < (int)G[i].size(); j++) {
int v = G[i][j];
if (!tax[c[v]]) df[i]++;
tax[c[v]] = 1;
}
for (int j = 0; j < (int)G[i].size(); j++) {
int v = G[i][j];
tax[c[v]] = 0;
}
tax[c[i]] = 0;
}
int h2 = 0, mks = 0, pos;
for (int i = 1; i <= n; i++) {
if (df[i] == 2) h2++;
if (mks <= df[i]) {
if (mks > 2) return printf("NO\n"), 0;
mks = df[i], pos = i;
}
}
if (mks > 2) {
int cnt = 0;
for (int j = 0; j < (int)G[pos].size(); j++) {
int v = G[pos][j];
if (df[v] == 2) cnt++;
}
if (cnt == h2) return printf("YES\n%d\n", pos), 0;
else return printf("NO\n"), 0;
} else {
for (int u = 1; u <= n; u++) if (df[u] == 2) {
int cnt = 1;
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (df[v] == 2) cnt++;
}
if (cnt == h2) return printf("YES\n%d\n", u), 0;
}
}
return printf("NO\n"), 0;
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}
第六题 608C
CF 608C
题意：有$n$个灯塔，每个灯塔有属性（坐标，向左的照射范围），所有灯塔坐标两两不同。我们从右往左，对于每个灯塔，其所照射到的所有灯塔都被认定为被破坏。 我们现在可以在所有灯塔的右边，布置一个新的灯塔，位置和范围任意定。 问是否有一种布置灯塔的方案，可以使得被破坏的灯塔数尽可能少，并输出最少破坏的灯塔数。
解：题意中布置一个新的灯塔可以让右边任意连续灯塔破坏。相当于使得第$i$个灯塔，作为没被破坏的最后一个灯塔。 我们这样就可以DP了，每个灯塔可以从他前面攻击范围之外第一个转移。攻击范围之外第一个可以二分得到。
知识点：这种题目抽象化之后要往能否转移方向去思考。比如本题设置$dp(i)$为第$i$个灯塔，作为没被破坏的最后一个灯塔, 之前所有存在灯塔最大值。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
int n, dp[MAXN];
pair<int, int > p[MAXN];
void clean() {
}
int solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].first, &p[i].second);
sort(p + 1, p + 1 + n);
int ans = 1000000000;
for (int i = 1; i <= n; i++) {
int pos = lower_bound(p + 1, p + 1 + n, make_pair(p[i].first - p[i].second, -1)) - p - 1;
dp[i] = dp[pos] + 1;
ans = min(ans, n - dp[i]);
}
printf("%d\n", ans);
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}
第七题 602C
CF 602C
题意：给你一个无向图有一些边，火车可以开在这些边上，而公交车可以开在补图的边上。求一个最优方案使得火车和公交车从1到$n$时间最短。在同一时刻火车和公交车不能在一个点上。
解：这是一个完全图、补图问题，边$1-n$一定存在。所以只要看是火车存在还是公交车存在这条边就可以了，之后就 BFS 一个最短路即可。
知识点：要善于挖掘题目的信息，比如此题如果没有了补图，则本题变为了完全不同的题目。并且数据范围小也是一个重要信息。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 400 + 5;
struct node {
int u, len;
};
int n, m, ma[MAXN][MAXN], k, vis[MAXN];
queue<node> q;
void ins(int x, int y) {ma[x][y] = ma[y][x] = 1;}
void clean() {
ms(vis, 0), ms(ma, 0);
}
int solve() {
clean();
for (int x, y, i = 1; i <= m; i++) scanf("%d%d", &x, &y), ins(x, y);
if (ma[1][n] == 1) k = 1; else k = 0;
vis[1] = 1, q.push((node){1, 0});
while (!q.empty()) {
node &p = q.front(); q.pop();
if (p.u == n) return printf("%d\n", max(1, p.len)), 0;
for (int i = 1; i <= n; i++) if ((ma[p.u][i] ^ k) == 1) {
if (!vis[i]) vis[i] = 1, q.push((node){i, p.len + 1});
}
}
printf("-1\n");
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
第八题 552C
CF 552C
题意：要用质量为$w^0,w^1,w^2……,w^{100}$的砝码各$1$个称出重量$m$，砝码可以放在天平左边也可以放在右边。问是否可以称出。
解：$w \leq 3$时可以表示所有的数$m$。将$m$用$w$进制表示，如果该位不是$0,1$和$w-1$则无解。如果是$w-1$，则这一位的砝码必须加在物体这边，要让当前的$m$加一。
知识点：这种用幂的东西分一个数的和进制有关。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int w, m;
void clean() {
}
int solve() {
clean();
if (w <= 3) return printf("YES\n"), 0;
while (m) {
int tmp = m % w;
m /= w;
if (tmp == w - 1) m++;
if (tmp != w - 1 && tmp != 1 && tmp != 0) return printf("NO\n"), 0;
}
printf("YES\n");
return 0;
}
int main() {
scanf("%d%d", &w, &m), solve();
return 0;
}
第九题 567C
CF 567C
题意：给你一个序列,求序列中长度为$3$的公比为$k$的子序列的个数.
解：三点问题必然枚举中间点$i$，然后只需要找左边$i/k$的个数和右边$ik$的个数，乘法原理即可。注意$i$必须整除$k$才能进行操作。查询方法对每一个权值开vector存权值单调地出现位置，然后要查询一个区间权值出现次数直接在这个vector里二分区间左右端点相减即可。对于开不下，因为总数小，开个map压第一维。
知识点：运用了CF510D的map压第一维。CF987C三点枚举中间点。bzoj 2724记录每种颜色出现的位置单调放在vector里，查询区间的长度即为颜色出现次数。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const LL MAXN = 200000 + 5;
LL n, k, a[MAXN], ans;
map<LL, vector<LL > > ma;
LL getNum(LL x, LL l, LL r) {
return upper_bound(ma[x].begin(), ma[x].end(), r) - upper_bound(ma[x].begin(), ma[x].end(), l - 1);
}
void clean() {
}
int solve() {
clean();
for (LL i = 1; i <= n; i++) scanf("%lld", &a[i]), ma[a[i]].push_back(i);
ans = 0;
for (LL i = 2; i < n; i++) {
if (a[i] % k) continue;
LL q = getNum(a[i] / k, 1, i - 1), h = getNum(a[i] * k, i + 1, n);
ans += q * h;
}
printf("%lld\n", ans);
return 0;
}
int main() {
scanf("%lld%lld", &n, &k), solve();
return 0;
}
第十题 711C
CF 711C
题意：给你一列$n$棵树。给你$m$种颜色，这一列树中有些已经被涂好颜色了，但有些没有涂颜色。现在要给这些没有涂颜色的树上色，对于第$i$颗树，要涂第$j$种颜色，需要消耗$p_{ij}$的颜料。定义这一列树的美丽值为连续相同颜色段的段数。问使得美丽值为$k$的所需消耗的颜料的最小值。
解：刚开始想了区间DP，状态太暴力了。整区间询问的题目就不用区间DP了，直接上最简单的DP即可。
设$dp(i,j,k)$为前$i$棵树美丽值为$j$，$i$位置涂了$k$颜色的最小值
那么当$a_i≠0$时 ($u≠k，1 \leq u \leq m$)
$$dp(i,j,k)=min(dp(i -1,j,k),dp(i-1,j-1,u))$$
当$a_i=0$时 ($u≠k，1 \leq u \leq m$)
$$dp(i,j,k)=min(dp(i -1,j,k),dp(i-1,j-1,u))+p_{ik}$$
初始化所有状态设为$∞$，然后特殊值
当$a_1≠0$时，$dp(1,1,a_1)=0$。当$a_1=0$时，$dp(1,1,k)=p_{1k} (1 \leq k \leq m)$
然后转移即可。
知识点：整区间询问的题目就不用区间DP了，直接上最简单的DP即可。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const LL MAXN = 100 + 5, INF = 4223372036854775807ll;
LL n, m, q, a[MAXN], dp[MAXN][MAXN][MAXN], p[MAXN][MAXN];
void clean() {
for (LL i = 0; i <= 101; i++)
for (LL j = 0; j <= 101; j++)
for (LL k = 0; k <= 101; k++) dp[i][j][k] = INF;
}
int solve() {
clean();
for (LL i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (LL i = 1; i <= n; i++)
for (LL j = 1; j <= m; j++) scanf("%lld", &p[i][j]);
if (a[1] != 0) dp[1][1][a[1]] = 0; else {
for (LL k = 1; k <= m; k++) dp[1][1][k] = p[1][k];
}
for (LL i = 2; i <= n; i++) {
for (LL j = 1; j <= i; j++) {
for (LL k = 1; k <= m; k++) {
if (a[i] == 0) {
dp[i][j][k] = dp[i - 1][j][k] + p[i][k];
for (LL u = 1; u <= m; u++) if (u != k) {
dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - 1][u] + p[i][k]);
}
} else {
if (k != a[i]) continue;
dp[i][j][k] = dp[i - 1][j][k];
for (LL u = 1; u <= m; u++) if (u != k) {
dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - 1][u]);
}
}
}
}
}
LL ans = INF;
for (LL i = 1; i <= m; i++) ans = min(ans, dp[n][q][i]);
if (ans == INF) printf("-1\n"); else printf("%lld\n", ans);
return 0;
}
int main() {
scanf("%lld%lld%lld", &n, &m, &q), solve();
return 0;
}
第十一题 761C
CF 761C
题意：有$n$个串，每个串有$m$个字符，可以由数字，小写字母，和三个符号组成，现在要在这$n$个串中每个串找出一个字符组成一个密码，这密码要求至少要有一个数字，一个字母和一个特殊字符，一开始每个字符串都指在第一个字符，每次移动可以往两边移动，也就是说可以往左右两边移动，要求所得到的密码移动的次数最少。
解：
贪心枚举做法：枚举每个串转到字母、数字、符号的最小花费，然后最后$n^3$综合一下解即可。
DP做法，设$dp(i,j,k,u)$为前$i$行状态为$(j,k,u)$(字母、数字、符号)的最小花费，则直接转移即可。
知识点：能暴力枚举的题目千万别上DP，耗时耗力，最优化问题不过就是1暴力2DP3贪心，想一想即可
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 50 + 5, INF = 1000000000;
int n, m, dp[MAXN][2][2][2], whw[MAXN][3];
char s[MAXN][MAXN];
void clean() {
for (int i = 0; i <= 51; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
for (int u = 0; u < 2; u++) dp[i][j][k][u] = INF;
for (int i = 0; i <= 51; i++)
for (int j = 0; j < 3; j++) whw[i][j] = INF;
}
int solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
dp[0][0][0][0] = 0;
int hf = 0, h0 = 0, ha = 0;
for (int i = 1; i <= n; i++) {
if (s[i][1] == '#' || s[i][1] == '*' || s[i][1] == '&') hf = 1;
if ('0' <= s[i][1] && s[i][1] <= '9') h0 = 1;
if ('a' <= s[i][1] && s[i][1] <= 'z') ha = 1;
dp[i][hf][h0][ha] = 0;
}
for (int i = 1; i <= n; i++) {
int nowl = m, nowr = 2, cnt = 1;
while (nowl >= nowr) {
if (whw[i][0] == INF && (s[i][nowl] == '#' || s[i][nowl] == '*' || s[i][nowl] == '&')) whw[i][0] = cnt;
if (whw[i][1] == INF && '0' <= s[i][nowl] && s[i][nowl] <= '9') whw[i][1] = cnt;
if (whw[i][2] == INF && 'a' <= s[i][nowl] && s[i][nowl] <= 'z') whw[i][2] = cnt;
if (whw[i][0] == INF && (s[i][nowr] == '#' || s[i][nowr] == '*' || s[i][nowr] == '&')) whw[i][0] = cnt;
if (whw[i][1] == INF && '0' <= s[i][nowr] && s[i][nowr] <= '9') whw[i][1] = cnt;
if (whw[i][2] == INF && 'a' <= s[i][nowr] && s[i][nowr] <= 'z') whw[i][2] = cnt;
cnt++, nowl--, nowr++;
}
}
int ans = INF;
for (int i = 1; i <= n; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
for (int u = 0; u < 2; u++) {
dp[i][j][k][u] = min(dp[i][j][k][u], dp[i - 1][j][k][u]);
if (j) dp[i][j][k][u] = min(dp[i][j][k][u], dp[i - 1][0][k][u] + whw[i][0] * ((s[i][1] == '#' || s[i][1] == '*' || s[i][1] == '&') ^ 1));
if (k) dp[i][j][k][u] = min(dp[i][j][k][u], dp[i - 1][j][0][u] + whw[i][1] * (('0' <= s[i][1] && s[i][1] <= '9') ^ 1));
if (u) dp[i][j][k][u] = min(dp[i][j][k][u], dp[i - 1][j][k][0] + whw[i][2] * (('a' <= s[i][1] && s[i][1] <= 'z') ^ 1));
ans = min(dp[i][1][1][1], ans);
}
printf("%d\n", ans);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
第十一题 750C
CF 750C
题意：每个人都有一个$rating$，是一个整数，可以是负数以及$0$，$div1$高于$1900$分 $div2$低于$1899$。有个人参加了$n$场，比赛，但是只记得每一场是$div$几，以及每一场赛后的$rating$的变化量，请问他现在最高可能多少分，如果不可能有符合的情况 输出$Impossible$，如果可以无限大分数，输出$Infinity$
解：本题可以用二分解决。但是这里可以用另一种方法，设当前最开始的$rating=x$, 那么如果出现了一场$div1$，那么他的当前$rating$一定大于$1900$，所以$x + sum \geq 1900$，推导一下就可以是$x \geq 1900 - sum$，$div2$同理。这样可以一步步用区间逼近答案。
知识点：这种题目要求只输出一个答案这样的符合二分条件的题目，要想到二分答案。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int INF = 200000000;
int sum = 0, n, c, d, l, r;
void clean() {
}
int solve() {
clean();
scanf("%d", &n);
l = -INF, r = INF;
for (int i = 1; i <= n; i++) {
scanf("%d%d", &c, &d);
if (d == 1) l = max(l, 1900 - sum);
if (d == 2) r = min(r, 1899 - sum);
sum += c;
}
if (l > r) printf("Impossible"); else {
if (r == INF) printf("Infinity"); else printf("%d\n", sum + r);
}
return 0;
}
int main() {
solve();
return 0;
}
第十二题 740C
CF 740C
题意：题目的要求是构造出一个长度为$ n $的数列, 构造条件是在接下来给出的$ m$ 个子区间中, 要求每一个子区间的$mex$值最大, 然后在这$ m$ 个子区间产生的$mex$值中取最小的输出, 并且输出构造出来的序列
解：永远不会的构造题qwq。。答案就是最小区间长$d$。然后构造一个序列使得每个最小区间都能取到$[0,d-1]$，就是一个$0,1,2,……,d-1,0,1,2,……,d-1$的形式
知识点：
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, m, l, r, ans;
void clean() {
}
int solve() {
clean();
scanf("%d%d", &l, &r), ans = r - l + 1;
for (int i = 2; i <= m; i++) scanf("%d%d", &l, &r), ans = min(ans, r - l + 1);
printf("%d\n", ans);
for (int i = 0; i < n; i++) printf("%d ", i % ans);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
第十三题 373C
CF 373C
题意：有$n$个袋鼠每个袋鼠的口袋里可以放一只体重小于其体重的小于它二分之一重量的袋鼠现在将一些袋鼠放进其它的袋鼠口袋里问最多能见到多少袋鼠。
解：贪心，每个小袋鼠找能装下他的最小袋鼠。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
int n, a[500000 + 5];
void clean() {
}
int solve() {
clean();
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
std::sort(a + 1, a + 1 + n);
int ans = n;
for (int i = n / 2; i; i--) {
if (ans == i) break;
if (a[ans] >= 2 * a[i]) ans--;
}
printf("%d\n", ans);
return 0;
}
int main() {
solve();
return 0;
}
第十四题 379C
CF 379C
题意：给你一个序列，然后序列每个数必须要大于等于自己现在的数并且不能和其他数一样
解：排序之后贪心从小到大赋值即可。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
LL n, ans[300000 + 5];
std::pair<LL, LL > a[300000 + 5];
inline LL max(LL a, LL b) {return a > b ? a : b;}
inline LL min(LL a, LL b) {return a < b ? a : b;}
void clean() {
}
int solve() {
clean();
scanf("%lld", &n);
for (LL i = 1; i <= n; i++) scanf("%lld", &a[i].first), a[i].second = i;
std::sort(a + 1, a + 1 + n);
LL tot = 1, co = 1, lst = 0;
for (LL i = 1; i <= n; i++) {
if (a[i].first == a[i - 1].first) co++; else tot = lst + 1, co = 1;
lst = ans[a[i].second] = max(a[i].first, tot) + co - 1;
}
for (LL i = 1; i <= n; i++) printf("%lld ", ans[i]);
return 0;
}
int main() {
solve();
return 0;
}
第十五题 712C
CF 712C
题意：给你一个长度为$x$的等边三角形，每一秒你能修改一条边的长度，要你修改到长度为$y$的等边三角形，要求修改过程中保证它是一个三角形。
解：从$y$倒推到$x$, 每次将最小边修改为当前最大边，即$c=a+b-1$
知识点：正难则反
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
inline int max(int a, int b) {return a > b ? a : b;}
inline int min(int a, int b) {return a < b ? a : b;}
int x, y;
void clean() {
}
int solve() {
clean();
scanf("%d%d", &x, &y);
int a[10]; a[0] = a[1] = a[2] = y;
int tms = 0;
while (1) {
std::sort(a, a + 3);
if (a[0] >= x && a[1] >= x && a[2] >= x) break;
a[0] = a[1] + a[2] - 1, tms++;
}
printf("%d\n", tms);
return 0;
}
int main() {
solve();
return 0;
}
第十六题 1025C (交换题)
CF 1025C
题意：给出一个01字符串，你可以在任意位置分开字符串，然后将两段字符串翻转后相连，问最长能得到的交替字符串长。
解：将字符串首尾相接，每次切是相当于翻转了环，环内各元素连接并没发生变化，所以在环中找最长交替字符串长就行。直接拼接一个相同字符串在后面，然后求最长交替字符串长即可，用 DP 扫一遍。注意答案不能超过原长度，取$min$
//==========================Head files==========================
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
#define LL long long
#define db double
#define mp make_pair
#define pr pair<int, int>
#define fir first
#define sec second
#define pb push_back
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
//==========================Templates==========================
inline int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
inline LL readl() {
LL x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
int power(int a, int b) {
int ans = 1;
while (b) {
if(b & 1) ans = ans * a;
b >>= 1; a = a * a;
}
return ans;
}
int power_mod(int a, int b, int mod) {
a %= mod;
int ans = 1;
while (b) {
if(b & 1) ans = (ans * a) % mod;
b >>= 1, a = (a * a) % mod;
}
return ans;
}
LL powerl(LL a, LL b) {
LL ans = 1ll;
while (b) {
if(b & 1ll) ans = ans * a;
b >>= 1ll;a = a * a;
}
return ans;
}
LL power_modl(LL a, LL b, LL mod) {
a %= mod;
LL ans = 1ll;
while (b) {
if(b & 1ll) ans = (ans * a) % mod;
b >>= 1ll, a = (a * a) % mod;
}
return ans;
}
LL gcdl(LL a, LL b) {return b == 0 ? a : gcdl(b, a % b);}
LL abssl(LL a) {return a > 0 ? a : -a;}
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
int abss(int a) {return a > 0 ? a : -a;}
//==========================Main body==========================
#define LD "%I64d"
#define D "%d"
#define pt printf
#define sn scanf
#define pty printf("YES\n")
#define ptn printf("NO\n")
inline int read();
inline LL readl();
int power(int a, int b);
int power_mod(int a, int b, int mod);
int gcd(int a, int b);
int abssl(int a);
LL powerl(LL a, LL b);
LL power_modl(LL a, LL b, LL mod);
LL gcdl(LL a, LL b);
LL abssl(LL a);
//==========================Code here==========================
char s[100000 + 5];
int gg[200000 + 5];
int main() {
cin >> (s + 1);
int n = strlen(s + 1);
for (int i = 1; i <= n; i++) {
gg[i] = gg[i + n] = (s[i] == 'b' ? 1 : 0);
}
int lst = 0, tot = 0, ans = 0;
gg[0] = -1;
for (int i = 1; i <= 2 * n; i++) {
if (lst != gg[i]) lst = gg[i], tot++; else {
tot = 1;
}
ans = max(ans, tot);
}
printf("%d\n", min(ans, n));
return 0;
}
第十六题 873B
CF 873B
题意：求一个01字符串中01数量相同最长的子串。
解：将0看作-1然后做前缀和，前缀和相同的位置进行更新。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
int n;
char s[100000 + 5];
std::map<int, int > m;
void clean() {
}
int solve() {
clean();
scanf("%d%s", &n, s + 1);
int qzh = 0, ans = 0;
m[0] = 1;
for (int i = 1; i <= n; i++) {
qzh += (s[i] == '0' ? -1 : 1);
if (m[qzh]) ans = std::max(ans, i - m[qzh] + 1); else m[qzh] = i + 1;
}
printf("%d\n", ans);
return 0;
}
int main() {
solve();
return 0;
}
第十八题 1016D
CF 1016D
题意：输入$n，m$，表示一个矩阵的行数和列数，然后给出矩阵的每行每列的异或值，问是否存在这样的矩阵，存在输出YES并随便输出一个符合条件的矩阵，否则输出NO
解：好水啊，矩阵$n-1$行$m-1$列全填0，然后每一行最后一个填$a_i$, 最后一行前面的填$b_i$，最重要的是$(n,m)$填什么。将最后一行前$m-1$个$b_i$异或和求出该数填什么。然后用上面的$a_i$异或和验证答案，不相同则无解。
知识点：a^x=b中 x=b^a
对于样例的输出构造：
YES
0 0 2
5 3 15
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int MAXN = 100 + 5;
int n, m;
int a[MAXN], b[MAXN], xa = 0, xb = 0;
void clean() {
}
int solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), xa ^= (i != n ? a[i] : 0);
for (int i = 1; i <= m; i++) scanf("%d", &b[i]), xb ^= (i != m ? b[i] : 0);
int whw = a[n] ^ xb;
if ((whw ^ xa) != b[m]) return printf("NO\n"), 0;
printf("YES\n");
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) printf("0 ");
printf("%d\n", a[i]);
}
for (int i = 1; i < m; i++) printf("%d ", b[i]);
printf("%d\n", whw);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
第十九题 988D
CF 988D
题意：找最长的序列,使得该序列的任意两个值的差是$2$的倍数. 输出长度,并输出元素
解：只有3/2/1三种可能。枚举3的情况，2的情况，没有输出1。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
std::set<int > s;
int n, a[200000 + 5], maxd, mind;
void clean() {
maxd = -1000000000, mind = 1000000000;
}
int solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), mind = std::min(mind, a[i]), maxd = std::max(maxd, a[i]), s.insert(a[i]);
for (int i = 1; i <= n; i++) {
for (int j = 0; ; j++) {
int d = (1 << j), lt = a[i] - d, rt = a[i] + d;
if (lt < mind || rt > maxd) break;
if (s.count(lt) && s.count(rt)) {
printf("3\n%d %d %d\n", lt, a[i], rt);
return 0;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; ; j++) {
int d = (1 << j), rt = a[i] + d;
if (rt > maxd) break;
if (s.count(rt)) {
printf("2\n%d %d\n", a[i], rt);
return 0;
}
}
}
printf("1\n%d\n", a[1]);
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}
第二十题 1027C
CF 1027C
题意：给你$n$个边长，让你从中找出四个构成一个矩形，使得该矩形的周长的平方除以面积的值最小。
解：相邻的两种边长里一定有最优解。
证明：原式即为$\frac{(a+b)^2}{ab}$，转化为$\frac{a^2+ab+b^2}{ab}=\frac{a^2+b^2}{ab}+2$，那么就让$\frac{a^2+b^2}{ab}$最小即可，注意到这是一个加的形式，且这个值为定值，根据均值不等式，$\frac{a^2}{ab}= \frac{b^2}{ab}$时有和最小值，即$a=b$时。所以相邻的两种边长里一定有最优解。
知识点：注意自己代码实现不要超过预期的复杂度了。求最小最大的和/积为定值数学问题可以想到均值不等式。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
int n, a[1000000 + 5], tax[1000000 + 5], gg[1000000 + 5], tot;
db mks;
int ans1, ans2;
inline db cal(int a_1, int a_2) {
return (db)(2 * (a_1 + a_2)) * (db)(2 * (a_1 + a_2)) / ((db)a_1 * (db)a_2);
}
void clean() {
}
int solve() {
clean();
scanf("%d", &n);
tot = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]), tax[a[i]]++;
if (tax[a[i]] == 4) {
printf("%d %d %d %d\n", a[i], a[i], a[i], a[i]);
for (int j = 1; j <= i; j++) tax[a[j]] = 0;
for (int j = i + 1; j <= n; j++) scanf("%d", &a[i]);
return 0;
}
}
std::sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) if (tax[a[i]] >= 2) gg[++tot] = a[i], tax[a[i]] = 0;
int z1 = gg[1], z2 = gg[2];
mks = cal(z1, z2), ans1 = z1, ans2 = z2;
for (int i = 3; i <= tot; i++) {
z1 = z2, z2 = gg[i];
db tmp = cal(z1, z2);
if (mks - tmp >= 1e-12) mks = tmp, ans1 = z1, ans2 = z2;
}
printf("%d %d %d %d\n", ans1, ans1, ans2, ans2);
for (int i = 1; i <= n; i++) tax[a[i]] = 0;
return 0;
}
int main() {
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
第二十一题 1008C
CF 1008C
题意：给你一个序列，你可以生成这个序列的任意一个排列，对于某个排列，如果这个排列上某个位置的值大于原序列的值，那么就会产生1的贡献，问你最大能有多少贡献。
解：multiset 记录一下当前可选的值，线性扫一遍找比这个值大一点的数，找到后删除答案加一。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
int n, a[100000 + 5];
std::multiset<int > s;
void clean() {
}
int solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), s.insert(a[i]);
int ans = 0;
for (int i = 1; i <= n; i++) {
std::multiset<int >::iterator it = s.upper_bound(a[i]);
if (it != s.end()) ans++, s.erase(it);
}
printf("%d\n", ans);
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}
第二十二题 977E
CF 977E
题意：在一个无向图中找只有一个圈的环的个数。
解：只有一个圈的环里的点一定度数都为2, 知道这个DFS一下就行了。这题也可以用并查集把连通性求出来再存起来检查联通块里点度数都为2。
知识点：只有一个圈的环里的点一定度数都为2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int MAXN = 200000 + 5;
int fl, n, m, ans, deg[MAXN], vis[MAXN];
std::vector<int > G[MAXN];
inline void ins(int a, int b) {G[a].push_back(b), G[b].push_back(a), deg[b]++, deg[a]++;}
void dfs(int u) {
if (deg[u] != 2) fl = 0;
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (!vis[v]) vis[v] = 1, dfs(v);
}
}
void clean() {
ms(vis, 0), ms(deg, 0), ans = 0;
}
int solve() {
clean();
for (int a, b, i = 1; i <= m; i++) scanf("%d%d", &a, &b), ins(a, b);
for (int i = 1; i <= n; i++) if (!vis[i]) fl = 1, dfs(i), ans += fl;
printf("%d\n", ans);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
第二十三题 1005D
CF 1005D
题意：给你一个字符串,然后让你尽可能多的去分解这个字符串 使得每一个分解出来的子串的和都是3的倍数
解：如果当前一个数已经是3的倍数，直接切开单独成立，这样是最优的
否则比较两个数，如果这两个数的和是3的倍数就切开
考虑三个数的情况，前两个数的的余数可以是${2,2}，{1，1}$，第三个数余数可以是$1,2$，对于这三个数考虑所有情况都能找到3的倍数的段，所以枚举的时候只需要往后枚举至多3次即可。
知识点：对于这种倍数的题目，多想想余数/数字上的规律
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
char s[200000 + 5];
void clean() {}
int solve() {
clean();
int ans = 0, sum = 0, js = 0, n = strlen(s + 1);
for (int i = 1; i <= n; i++) {
sum = (sum + s[i] - '0') % 3, js++;
if ((s[i] - '0') % 3 == 0) {ans++, sum = 0, js = 0; continue;}
if (sum == 0) {ans++, sum = 0, js = 0; continue;}
if (js == 3) {ans++, sum = 0, js = 0; continue;}
}
printf("%d\n", ans);
return 0;
}
int main() {
scanf("%s", s + 1), solve();
return 0;
}
第二十四题 999D
CF 999D
题意：要求改变一个数组,使得模$m$后,结果为$0,1,2,3,…,m-1$都是$n/m$个,每次操作可以选择一个数$+1$,问至少执行多少次,并输出最终的数组
解：把多余的余数的位置拿出来放进set进行增加。枚举余数，如果余数少了，就在set里找严格比他小的那个余数，然后增加即可，要记得删除这个元素。找不到就找最大的余数增加。
知识点：STL 的题目复杂点的应该写清楚再写代码emm，不要老是换数据结构set.begin()是set的最小元素。
本题充分利用负数避免重载运算符。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
LL n, m, a[200000 + 6], b[200000 + 6], tax[200000 + 6];
std::set<std::pair<LL, LL> > s;
void clean() {
ms(tax, 0ll);
}
int solve() {
clean();
for (LL i = 1ll; i <= n; i++) scanf("%lld", &a[i]), b[i] = a[i] % m;
for (LL i = 1ll; i <= n; i++) {
tax[b[i]]++;
if (tax[b[i]] > n / m) s.insert(std::make_pair(-b[i], i)), tax[b[i]]--;
}
LL ans = 0ll;
for (LL i = 0ll; i < m; i++) {
while (tax[i] < n / m) {
std::set<std::pair<LL, LL> >::iterator it = s.upper_bound(std::make_pair(-i, 0ll));
if (it != s.end()) a[(*it).second] += i - (-(*it).first), tax[i]++, ans += i - (-(*it).first), s.erase(it);
else {
std::set<std::pair<LL, LL> >::iterator it = s.begin();
if (it != s.end()) a[(*it).second] += m - (-(*it).first) + i, tax[i]++, ans += m - (-(*it).first) + i, s.erase(it);
}
}
}
printf("%lld\n", ans);
for (LL i = 1; i <= n; i++) printf("%lld ", a[i]);
return 0;
}
int main() {
scanf("%lld%lld", &n, &m), solve();
return 0;
}
第二十五题 1029D
CF 1029D
题意：给你$n$个数求两两拼接后能被$k$整除的数。
解：$O(n^2)$会超时。对于题目条件就是$(a \cdot 10^{len_b}+b) \% k=0$即$(a, b)$合法。
那么我们移项，得$(a \cdot 10^{len_b}) \% k=(k-b \%k) \% k$，那么我们可以把左边存进 map 里然后每次循环右边即可。放进去把所有可能的长度都放进去，一共有 10 个。
查询就查询当前长度是否存在前缀$a$。要小心自己和自己组合的情况。
知识点：余数整除等问题与数学数论密切相关，模的式子什么的可以进行转换(移项等)
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL unsigned long long
#define db double
LL n, k, a[200000 + 5], sm[20];
std::map<LL, LL > ma[20];
void clean() {
}
int solve() {
clean();
for (LL i = 1; i <= n; i++) scanf("%llu", &a[i]);
sm[0] = 1;
for (LL i = 1; i <= 12; i++) sm[i] = 10ll * sm[i - 1];
for (LL i = 1; i <= n; i++)
for (LL ws = 1; ws <= 10; ws++) ma[ws][(a[i] * sm[ws]) % k]++;
LL ans = 0;
for (LL i = 1; i <= n; i++) {
LL ws = 0ll, tmp = a[i];
do {ws++, tmp /= 10;} while (tmp);
ans += ma[ws][(k - a[i] % k) % k];
if (((a[i] * sm[ws]) % k + a[i]) % k == 0) ans--;//自己和自己组合的情况
}
printf("%llu\n", ans);
return 0;
}
int main() {
scanf("%llu%llu", &n, &k), solve();
return 0;
}
第二十六题 152C
CF 152C
题意：给出$n$个长度为$m$的字符串，任意两个字符串可以交换前$k$个字符，交换后字符串变成新的字符串，问最后能产生多少个不同的字符串
解：对于两个串使用$(i,j,k),(i,j,k-1)$可以交换$k$位置的字符串，所以原题转化为求每个位置能改到多少种字符串，乘法原理即可。
知识点：这种直观上不能扫描的都会有结论。或者结论可以辅助扫描。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define ULL unsigned long long
#define db double
LL n, m, ans;
char s[105][105];
std::set<char > st;
void clean() {
}
int solve() {
clean();
ans = 1ll;
for (LL i = 1; i <= n; i++) scanf("%s", s[i] + 1);
for (LL j = 1; j <= m; j++) {
st.clear();
for (LL i = 1; i <= n; i++) st.insert(s[i][j]);
ans = (ans * (LL)st.size()) % 1000000007;
}
printf("%lld\n", ans);
return 0;
}
int main() {
scanf("%lld%lld", &n, &m), solve();
return 0;
}
第二十七题 825E
CF 825E
题意：给你一个DAG，你要为每个点编号1-n使得每条边$(u,v)$编号$u$比$v$小
解：DAG很容易想到拓扑排序，然后每次拓扑排序将拓扑出来的点标号，由于字典序最小，队列换成优先队列。但是这样有问题了，会WA6，原因是如果原图有两个点12和15并且12前面所有点入点为0，并且15连向12，那么此时会将15编号为12，但实际上可能可以将12编号为13，然后15编号为12。我们过早地把15编号导致不是字典序最小。
但是我们发现倒过来做就是对的了。将图反向做拓扑排序，维护大根堆，然后从n开始往下编号。
知识点：这种位置的题目肯定没那么容易被模板 * 过，应该会有一些坑点。很像CF 1064D
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<queue>
#include<cmath>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5;
struct edge {int v, nxt;} ed[MAXN * 2];
int n, m, en, hd[MAXN], ino[MAXN], ans[MAXN];
priority_queue<int, vector<int>, greater<int> > q;
void ins(int x, int y) {ed[++en] = (edge){y, hd[x]}, hd[x] = en, ++ino[y];}
void clean() {
en = 0, ms(hd, -1), ms(ino, 0), ms(ans, 0);
}
int solve() {
cin >> n >> m;
clean();
for (int u, v, i = 1; i <= m; ++i) scanf("%d%d", &u, &v), ins(u, v);
for (int i = 1; i <= n; ++i) if (ino[i] == 0) q.push(i);
int now = 0;
while (!q.empty()) {
int p = q.top(); q.pop();
ans[p] = ++now;
for (int i = hd[p]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
--ino[e.v];
if (ino[e.v] == 0) q.push(e.v);
}
}
for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
第二十八题 525C
CF 525C
题意：给你$n$个棒子，每个棒子可以最多减$1$，请将这些棒子组成矩形，使得矩形面积总和最大。
排序后从大到小贪心，因为棒子可以减一，所以大的可以减成小的，所以如果存在一个$x,x+1$，则可以有一个边为$x$。
知识点：
1、贪心思想
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<set>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
LL n, l[100000 + 5];
void clean() {
}
int solve() {
clean();
cin >> n;
for (LL i = 1; i <= n; ++i) scanf("%lld", &l[i]);
sort(l + 1, l + 1 + n);
LL mul = 1ll, tot = 0ll, ans = 0ll;
for (LL i = n; i >= 1ll; --i) {
if (l[i] - l[i - 1ll] <= 1ll) {
mul *= l[i - 1ll], --i, tot += 2ll;
}
if (tot == 4ll) ans += mul, mul = 1ll, tot = 0ll;
}
cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
第二十九题 991C
CF 991C
题意：两个人吃糖，A每天吃$k$颗糖，B每天吃剩余糖的$10\%$向下取整。A每天先吃，B后吃。问$k$至少为多少，能保证A总共吃的糖大于总量的一半。
玄学，直接暴力复杂度不高，套个二分。
注意奇偶性，n/10不要写成(int)(n*0.1)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
LL n;
bool chk(LL k) {
LL tot = 0ll, tmp = n;
while (tmp) {
if (tmp >= k) tot += k, tmp -= k; else tot += tmp, tmp = 0;
if (tmp >= 10) tmp -= tmp / 10;
}
return tot >= (n + 1) / 2;
}
void clean() {
}
int solve() {
clean();
cin >> n;
LL l = 1, r = n + 1, ans;
while (l < r) {
LL mid = (l + r) >> 1;
if (chk(mid)) ans = r = mid; else l = mid + 1;
}
cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
第三十题 985C
CF 985C
题意：需要造$n$个桶，每个桶需要$k$个木板，任意两个桶之间容积（一个桶中最短的木板的高度）的差距不能超过$l$，然后给你$nk$个木板，第$i$个木板的长度为$a_i$，问能否造出符合条件的$n$个桶，如果能的话问这$n$个桶的容积之和最大是多少，如果不能的话就输出$0$。
解：根据短板效应，本题的限制因数在最小的那一块板和容积的差值。
那么我们可以找到最后一个位置使得$a_p-a_l \leq l$，那么$[1, p]$之间的板子都能作为每个桶的容积(其实只有最小的那一块板影响最后的答案)。假设当前我们取了一个$x$, 那么我们尽可能地让这个$x$影响尽可能小的板，但是不能用光$[1,p]$之间的板。这样就可以扫描贪心了。
注意判无解即为$p < n$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
LL n, k, l, a[100000 + 5];
void clean() {
}
int solve() {
clean();
cin >> n >> k >> l;
for (LL i = 1; i <= n * k; ++i) scanf("%lld", &a[i]);
sort(a + 1, a + 1 + n * k);
if (a[n] - a[1] > l) return printf("0\n"), 0;
LL pos = upper_bound(a + 1, a + 1 + n * k, a[1] + l) - a;
LL ans = 0, whw = 0;
for (LL i = 1; i <= n; ++i) {
ans += a[++whw];
for (LL j = 1; j < k; ++j) {
if (pos - whw - 1 > n - i) ++whw; else break ;
}
}
cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
第三十一题 1092D1
CF 1092D1
题意：给你$n$个位置墙的高度，现在你有$2×1 $砖块，你可以竖直或者水平放置, 问你是否可以使得所有位置高度一样
解：显然每个位置都更新到最大值。可以发现如果相邻的两个的差能被2整除即可通过加2达到同一高度然后再一起加到最大值。所以用栈维护。
本题可以拓展为给定一个$01$串，求翻转任意两个相邻两个位置的01，能否使串全为0/1。
做法相同，这种消除类似括号的要想到用栈来维护。
知识点：
这种消除类似括号的要想到用栈来维护。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
int n, a[200000 + 5], top, st[200000 + 5];
void clean() {
top = 0;
}
int solve() {
clean();
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i) {
if (!top) st[++top] = a[i]; else {
if ((st[top] - a[i]) % 2 == 0) --top; else st[++top] = a[i];
}
}
if (top <= 1) printf("YES\n"); else printf("NO\n");
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
