本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-18 21:39:28

思路：

考虑贪心。

对于11这种请况，因为第一个是 $1$ 且第二个也是 $1$，又因为要让先手尽可能的小，所以先手只选一个 $1$，而后手选的话就选两个。
对于10这种情况，第一个是 $1$ 第二个是 $0$，$0$选跟没选一样，这里先手选，后手不选，为什么后面再说。
对于0000...01，我们发现只要 $0$ 的个数 $\ge 2$ 那么不管是先手先去还是后手先取都能让后手先取到 $1$，证明如下：

当有两个的时候，此时，若后手取，就只取一个 $0$，然后再让先手取一个，那么就能让后手先取 $1$，而先手先取就直接把两个 $0$ 去掉就可以了。 当有 $>2$ 个 $0$ 时，那么我们可以取掉一些转化为两个的（大不了就先手取一个，后手取一个，一直到 $2$）。

那么我们发现若101这种请况后手取了10那么先手就只能把最后一个 $1$ 给拿了，但其实它可以不拿，所以10这种情况就后手不取 $0$，先手取 $0$。

Code:

#include <bits\/stdc++.h>
using namespace std;
int T;
int n;
int a[200010];
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i)
			scanf("%d", &a[i]);
		int i = 1, ans = 0;
		bool is_ = false;
		while (i <= n) {
			if (a[i] == 0) {
				int cnt = 1;
				int j = i;
				while (j < n && a[j + 1] == 0) ++j, ++cnt;
				if (cnt >= 2) {
					i = j + 1;
					is_ = true;\/\/一段长度>=2的0之后一定是后手先取，所以设成这轮先手不取
					continue;
				}
			}
			if (!is_) {\/\/先手取
				if (a[i] == 1) {
					++ans;
					if (i < n && a[i + 1] == 0 && a[i + 2] == 1) i = i + 2;
					else ++i;
				} else {
					if (i < n && a[i + 1] == 0) i = i + 2;
					else ++i;
				}
			} else is_ = false;
			if (i > n) break;
			if (a[i] == 1) {\/\/后手取
				if (i < n && a[i + 1] == 1) i = i + 2;
				else ++i;
			} else {
				if (i < n && a[i + 1] == 1) i = i + 2;
				else ++i;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-06-09 08:42:40

题解思路：

因为当钱数是 $x$ 时收益为 $\max\{a_i-b_ix, 0\} \times x$。

因为这个 $\max$ 不好化简，那么不妨设 $a_i - b_i \times x \ge 0$。

当第 $i$ 个票价为 $x$，则收益为： $$(a_i-b_ix)x$$ $$=a_ix-b_ix^2$$

把第 $i$ 个的票价增加 $1$，就变成了： $$(a_i-b_i(x+1))(x+1)$$ $$=a_i(x+1)-b_i(x+1)^2$$ $$=a_ix+a_i-b_ix^2-2b_ix-b_i$$

发现把第 $i$ 个票价增加 $1$，比原来多了 $a_i-2b_ix-b_i$。

那么就贪心的选多的最多的，即 $a_i-2b_ix-b_i$ 最大的。

扩展完之后再把扩展完的下一个增加的收益放到堆里即可。

CODE:

#include <bits\/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
int a[100010], b[100010], cnt[100010];
priority_queue<pair<ll, int>> q;
ll ans;\/\/开long long！

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i], &b[i]);
	for (int i = 1; i <= n; ++i) {
		q.push({a[i] - 2 * b[i] - b[i]});\/\/初始值
	}
	for (int i = 1; q.size() && i <= k; ++i) {
		auto t = q.front();
		q.pop();
		if (t.first < 0) break;
		ans += t.first;\/\/加上这段增加的值
		cnt[t.second]++;\/\/增加了一个
		q.push({a[i] - 2 * (cnt[t.second] + 1) * b[i] - b[i], t.second});\/\/增加完之后放上
	}
	printf("%lld\n", ans);
	return 0;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                ctj
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-07-22 15:33:58

$$\color{darkblue}\colorbox{CAEBFB}{\large\boxed{\texttt{洛谷颜色对照表}}}$$

$$ \def\rraystretch{1.2} \begin{array}{|c|l|l||c|l|l|} \hline 颜色名称 & 十六进制编码 & \text{RGB对应值} & 颜色名称 & 十六进制编码 & \text{RGB对应值} \\ \hline \color{#52C41A}\text{AC绿} & \text{52C41A} & \text{(82,196,26)} & \color{#FE4C61}\text{入门红} & \text{FE4C61} & \text{(254,76,97)} \\ \hline \color{#E74C3C}\text{WA红} & \text{E74C3C} & \text{(231,76,60)} & \color{#F39C11}\text{普及-橙} & \text{F39C11} & \text{(243,156,17)} \\ \hline \color{#9D3DCF}\text{RE紫} & \text{9D3DCF} & \text{(157,61,207)} & \color{#FFC116}\text{普及黄} & \text{FFC116} & \text{(255,193,22)}\\ \hline \color{#FADB14}\text{CE黄} & \text{FADB14} & \text{(250,219,20)} & \color{#52C41A}\text{普及+提高 绿} & \text{52C41A} & \text{(82,196,26)} \\ \hline \color{#052242}\text{TLE黑} & \text{052242} & \text{(5,34,66)} & \color{#3498DB}\text{提高+省选-蓝} & \text{3498DB} & \text{(52,152,219)} \\ \hline \color{#052242}\text{MLE黑} & \text{052242} & \text{(5,34,66)} & \color{#9D3DCF}\text{省选紫} & \text{9D3DCF} & \text{(157,61,207)} \\ \hline \color{#052242}\text{OLE黑} & \text{052242} & \text{(5,34,66)} & \color{#0E1D69}\text{NOI黑} & \text{0E1D69} & \text{(14,39,105)} \\ \hline \color{#0E1D69}\text{UKE蓝} & \text{0E1D69} & \text{(14,29,105)} & \color{#BFBFBF}\text{未评定灰} & \text{BFBFBF} & \text{(191,191,191)} \\ \hline \hline \color{#8E44AD}\text{紫名} & \text{8E44AD} & \text{(142,68,173)} & \color{#52C41A}\text{排行绿} & \text{52C41A} & \text{(82,196,26)} \\ \hline \color{#E74C3C}\text{红名} & \text{E74C3C} & \text{(231,76,60)} & \color{#F39C11}\text{排行橙} & \text{F39C11} & \text{(243,156,17)} \\ \hline \color{#E67E22}\text{橙名} & \text{E67E22} & \text{(230,126,34)} & \color{#FADB14}\text{排行黄} & \text{FADB14} & \text{(250,219,20)} \\ \hline \color{#5EB95E}\text{绿名} & \text{5EB95E} & \text{(94,185,94)} & \color{#E74C3C}\text{排行红} & \text{E74C3C} & \text{(231,76,60)}\\ \hline \color{#0E90D2}\text{蓝名} & \text{0E90D2} & \text{(14,144,210)} & \color{#52C41A}\text{通过钩绿} & \text{52C41A} & \text{(82,196,26)} \\ \hline \color{#BFBFBF}\text{灰名} & \text{BFBFBF} & \text{(191,191,191)} & \color{#E74C3C}\text{不通过叉红} & \text{E74C3C} & \text{(231,76,60)} \\ \hline \hline \color{#E74C3C}\text{吉利红} & \text{E74C3C} & \text{(231,76,60)} & \color{#E74C3C}\text{官方比赛红} & \text{E74C3C} & \text{(231,76,60)} \\ \hline \color{#5EB95E}\text{中平绿} & \text{5EB95E} & \text{(94,185,94)} & \color{#054310}\text{团队比赛绿} & \text{054310} & \text{(5,67,16)} \\ \hline \color{#000000}\text{凶兆黑} & \text{000000} & \text{(0,0,0)} & \color{#3498DB}\text{个人比赛蓝} & \text{3498DB} & \text{(52,152,219)} \\ \hline \hline \color{#8E44AD}\text{ACM制紫} & \text{8E44AD} & \text{(142,68,173)} & \color{#5EB95E}\text{Rated绿} & \text{5EB95E} & \text{(94,185,94)} \\ \hline \color{#F1C40F}\text{IOI制黄} & \text{F1C40F} & \text{(241,196,15)} & \color{#5EB95E}\text{未开始绿} & \text{5EB95E} & \text{(94,185,94)} \\ \hline \color{#F1C40F}\text{乐多制黄} & \text{F1C40F} & \text{(241,196,15)} & \color{#E74C3C}\text{已结束红} & \text{E74C3C} & \text{(231,76,60)} \\ \hline \color{#F39C11}\text{OI制橙} & \text{F39C11} & \text{(243,156,17)} & \color{#52C410}\text{进行中*} & \text{暂时无} & \text{暂时无} \\ \hline \hline \color{#EFEFEF}\text{背景灰} & \text{EFEFEF} & \text{(239, 239, 239)} & \color{#7F7F7F}\text{小字灰} & \text{7F7F7F} & \text{(127,127,127)} \\ \hline \hline \color{#0E90D2}\text{按钮蓝} & \text{0E90D2} & \text{(14,144,210)} & \color{#3498DB}\text{链接蓝} & \text{3498DB} & \text{(52,152,219)} \\ \hline \color{#DD514C}\text{按钮红} & \text{DD514C} & \text{(221,81,76)} & \color{#3498DB}\text{通过率蓝} & \text{3498DB} & \text{(52,152,219)} \\ \hline \hline \color{#FFE169}\text{金钩黄} & \text{FFE169} & \text{(255,225,105)} & \color{#F5CECD}\text{背景粉} & \text{F5CECD} & \text{(245,206,205)} \\ \hline \color{#5EB95E}\text{绿钩绿} & \text{5EB95E} & \text{(94,185,94)} & \color{#C9E7C9}\text{背景绿} & \text{C9E7C9} & \text{(201,231,201)} \\ \hline \color{#3498DB}\text{蓝钩蓝} & \text{3498DB} & \text{(52,152,219)} & \color{#CAEBFB}\text{背景蓝} & \text{CAEBFB} & \text{(202,235,251)} \\ \hline \hline \color{#3498DB}\text{题目来源蓝} & \text{3498DB} & \text{(52,152,219)} &\color{#7F7F7F}\text{灰色} & \text{7F7F7F} & \text{(127,127,127)} \\ \hline \color{#E74C3C}\text{题目算法红} & \text{E74C3C} & \text{(231,76,60)}& \color{#FFFFFF}\text{白色} & \text{FFFFFF} & \text{(255,255,255)} \\ \hline \color{#52C41A}\text{题目地点绿} & \text{52C41A} & \text{(82,196,26)}& \color{#000000}\text{黑色} & \text{000000} & \text{(0,0,0)} \\ \hline \end{array} $$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-07-31 11:37:47

路虽远题解

题意：

给你一个 $n$ 个点 $m$ 条边的图，从一个节点出发到另一个节点时可能要等红绿灯，可以闯黄灯 $g$ 次，要在 $k$ 条边上添加限速，限速会使小 $X$ 经过这条边的时间变长，求小 $X$ 从第一个节点到第 $n$ 个节点的最短时间。

Subtask0

可以直接爆搜，让后每次就记录当前时间，当前节点，以及还剩多少条边需要限速，以及还可以闯多少次黄灯，因为可以通过每个灯的时间算出来当前是哪个灯，然后判断要不要闯黄灯，以及需要等多长时间。

得分：$20pts$。

Subtask1

因为只有绿灯，而且无法闯红灯，没有限速，那么就直接对原图跑最短路就可以了。

加上前面的 Subtask 可以拿 $25$ 分。

Subtask2

没有黄灯，也就是无法闯黄灯。

那么考虑如何做限速。

因为相当于修改 $k$ 条边的边权，那么可以考虑分层图。

那么可以考虑都限速，然后建 $m - k$ 层，每层由不限速的边连起来，这样到达最后一层中相当于第一层的的 $n$ 个点（后面统称为终点），就相当于一定有 $k$ 条边是限速的（因为最多走 $m - k$ 条不限速的边）。

然后再把每一层的终点向最后一层的终点连一条边权为 $0$ 的边连起来，这样能保证走不足 $m - k$ 条不限速的边可以直接到达。

最后就输出到达终点的最短距离即可，因为 spfa 会被卡，所以要用堆优化的 dijkstra。

加上前面的 Subtask 可以拿 $50$。

Subtask3

其实可以使用三维的 dijkstra，每一维分别表示当前是那个点，当前还剩多少条边可以不限速，当前还可以闯多少黄灯。

设当前时刻为 $t$。

• 1.若还可以不限速：

• 2.若不可以不限速：

同上，只不过把通过的时间改为限速的权值即可。

则有两种情况：

• 1.不闯黄灯，则判断当前时刻当前路口是否为绿灯，若是则可以直接冲过去，权值为不限速的权值，否则就加上等红绿灯的时间，也就是灯亮的总时间减去当前时刻 $t$，也就是总时间减去已经过去的时间。
• 2.闯黄灯，那么当前是绿灯或者黄灯时间，那么可以直接冲过去，否则再加上等红绿灯的时间即可。

按照权值跑 dijkstra 即可。

#include <bits\/stdc++.h>

using namespace std;

#define int long long

const int N = 110, M = N << 1;
const int INF = 1ll << 60;

int n, m, k, g;
int a[N], b[N], c[N], dist[N][N][N];
int h[N], e[M], ne[M], p[M], q[M], idx;

struct Node {
    int x, y, z, w;
    const bool operator<(const Node &x) const{
        return w > x.w;
    }
};
priority_queue<Node> q1;

void add(int a, int b, int n, int m) {
    e[idx] = b, p[idx] = n, q[idx] = m, ne[idx] = h[a], h[a] = idx++;
}

void update(int x, int y, int z, int w) {
    if (dist[x][y][z] > w) {
        dist[x][y][z] = w;
        q1.push({x, y, z, w});
    }
}

void dijkstra() {
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= k; ++j)
            for (int k = 0; k <= g; ++k)
                dist[i][j][k] = INF;

    dist[1][0][0] = 0;
    q1.push({1, 0, 0, 0});

    while (!q1.empty()) {
        auto u = q1.top();
        q1.pop();
        int x = u.x, y = u.y, z = u.z, w = u.w, now = w % (a[x] + b[x] + c[x]);
        if (dist[x][y][z] < w) continue;
        for (int i = h[x]; ~i; i = ne[i]) {
            int v = e[i];
            if (y < k) {
                if (now < a[x]) update(v, y + 1, z, w + p[i]);
                else update(v, y + 1, z, w + a[x] + b[x] + c[x] - now + p[i]);
                if (z < g) {
                    if (now < (a[x] + b[x])) update(v, y + 1, z + 1, w + p[i]);
                    else update(v, y + 1, z + 1, w + a[x] + b[x] + c[x] - now + p[i]);
                }
            }
            if (now < a[x]) update(v, y, z, w + q[i]);
            else update(v, y, z, w + a[x] + b[x] + c[x] - now + q[i]);
            if (z < g) {
                if (now < (a[x] + b[x])) update(v, y, z + 1, w + q[i]);
                else update(v, y, z + 1, w + a[x] + b[x] + c[x] - now + q[i]);
            }
        }
    }
}

signed main() {
    memset(h, -1, sizeof(h));
    scanf("%lld%lld%lld%lld", &n, &m, &k, &g);
    k = m - k;

    for (int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);

    for (int i = 1; i <= m; ++i) {
        int u, v, p, q;
        scanf("%lld%lld%lld%lld", &u, &v, &p, &q);
        add(u, v, p, q);
        add(v, u, p, q);
    }

    dijkstra();
    int ans = INF;

    for (int i = 0; i <= k; ++i)
        for (int j = 0; j <= g; ++j)
            ans = min(ans, dist[n][i][j]);

    if (ans == INF) puts("-1");
    else printf("%lld\n", ans);

    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-26 13:50:14

CF Round #734(Div.3) F,Equidistant Vertices

题意：

洛谷题目链接

CF题目链接

给定一棵有 $n$ 个点的树，要求选出 $k$ 个点，使得这 $k$ 个点两两距离相同。

输入数据有 $t$ 组（ $1 \leq t \leq 10$ ），每组数据第一行有两个数 $n$ 和 $k$ （ $2 \leq k \leq n \leq 100$ ），意义如上，下面 n−1 n-1n−1 行每行有两个数 u,vu,vu,v 代表有一条边连接 u,vu,vu,v 两个点，对于每组数据，输出方案数，答案对 $10^9+7$ 取模。

题解思路：

我们先特判一下，当 $k \le 2$ 的时候，那么他们的距离是相同的。

当 $k=3$ 时，只有他是有分叉的，才有可能使得这三个点两两距离相同。那么他们的距离就是他们分叉的距离两两相同。

所以当 $k \ge 3$ 时，他们的结果是一样的。

还有一个隐含条件，就是这些点不在同一子树里。

那么组合数就不可做了。

而我们发现 $n$ 很小，所以我们可以枚举分叉点，我们就求他离分叉点有多远的点的个数。

我们设距离为 $d$，那么我们就统计离分叉点距离为 $d$ 的点的个数。

记为 $c_1,c_2,c_3,...,c_k$，其中 $k$ 是子树的个数。

那么我们设 $dp_{i,j}$ 表示前 $i$ 个分支，并选了 $j$ 个点。

那么状态转移方程为： $$dp_{i,j} = (dp_{i-1,j} + dp_{i-1,j-1} \times c_i)$$ 那么时间复杂度为 $\mathcal{O(n^2 k)}$。

并且我们还可以把 $i$ 这一维给优化掉。

因为这道题的范围很小，所以我们可以用floyd求最短路。

AC CODE：

#include <bits\/stdc++.h>
using namespace std;
const int mod = 1000000007;
const int N = 110;
int n, k, g[N][N];
int cnt[N], dp[N];
void solve() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			g[i][j] = (i == j) ? 0 : mod;
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		g[u][v] = g[v][u] = 1;
	}
	if (k == 2) {
		printf("%d\n", n * (n - 1) \/ 2);
		return;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int d = 1; d <= n; d++) {
			for (int j = 1; j <= n; j++)
				cnt[j] = 0;
			for (int u = 1; u <= n; u++)
				if (g[i][u] == d) {
					for (int v = 1; v <= n; v++)
						if (g[i][v] == 1 && g[i][u] == g[i][v] + g[v][u]) {
							cnt[v]++;
						}
				}
			for (int j = 1; j <= k; j++)
				dp[j] = 0;
			dp[0] = 1;
			for (int j = 1; j <= n; j++)
				if (cnt[j] > 0) {
					for (int l = k; l >= 1; l--)
						dp[l] = (dp[l] + 1ll * dp[l - 1] * cnt[j]) % mod;
				}
			ans = (ans + dp[k]) % mod;
		}
	}
	printf("%d\n", ans);
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		solve();
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-26 20:21:32

CF Round #739 (Div 3) F, Nearest Beautiful Number

题意：

给定数据组数 $t$，每组数据包含正整数 $n$、$k$，求满足 $x\geq n$ 的最小正整数 $x$，使 $x$ 是个 $k$-beautiful 数。

一个正整数是个 $k$-beautiful 数，当且仅当其无前导零的十进制数值表示中，不同的数字不超过 $k$ 个。

数据满足 $1 \leq t \leq 10^4$，$1 \leq n \leq 10^9$，$1\leq k \leq 10$。

题解思路：

我们发现答案的数和 $n$ 数位是相同的。 所以这道题不用考虑位数。 而 $n$ 的位数也不是很长，所以我们乱搞一下就可以了。

AC CODE：

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
int vis[11];
vector<int> d;
int n, k;
bool dfs(int x\/*搜到了第x位*\/, bool larger\/*前x位是不是大于n的前x位*\/, int cnt\/*前x位有多少种不同的数字*\/, int num\/*答案*\/) {
	if (x == d.size()) {
		\/\/ 输出
		printf("%d\n", num);
		return true;\/\/可行。
	} else {
		for (int i = larger ? 0 : d[x]\/*大于的话就可以从0开始，否则从d[x]开始*\/; i <= 9; i++) {
			vis[i] += 1;
			int ncnt = cnt;
			if (vis[i] == 1) ncnt += 1;\/\/若他只出现过一次，那么不同数的个数+1
			if (ncnt <= k\/*没有超过k个不同的数*\/ && dfs(x + 1\/*到了下一位*\/, larger | (i > d[x])\/*判断*\/, ncnt, num * 10 + i\/*把i插到答案里面*\/)\/*可行*\/) {
				return true;\/\/也可行。
			}
			vis[i] -= 1;\/\/回溯。
		}
		return false;\/\/不可行。
	}
}
void solve() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i <= 9; i++) vis[i] = 0;
	d.clear();\/\/清空
	while (n) {
		d.push_back(n % 10);
		n \/= 10;
	}
	reverse(d.begin(), d.end());
	dfs(0, 0, 0, 0); \/\/ 当前的前缀有没有大于n的前缀
}
int main() {
	int T;
	scanf("%d", &T);
	while (T --) {
		solve();
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-26 20:22:50

这个也是F2的做法。

CF Round #739 (Div 3) F, Nearest Beautiful Number

题意：

给定数据组数 $t$，每组数据包含正整数 $n$、$k$，求满足 $x\geq n$ 的最小正整数 $x$，使 $x$ 是个 $k$-beautiful 数。

一个正整数是个 $k$-beautiful 数，当且仅当其无前导零的十进制数值表示中，不同的数字不超过 $k$ 个。

数据满足 $1 \leq t \leq 10^4$，$1 \leq n \leq 10^9$，$1\leq k \leq 10$。

题解思路：

我们发现答案的数和 $n$ 数位是相同的。 所以这道题不用考虑位数。 而 $n$ 的位数也不是很长，所以我们乱搞一下就可以了。

AC CODE：

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
int vis[11];
vector<int> d;
int n, k;
bool dfs(int x\/*搜到了第x位*\/, bool larger\/*前x位是不是大于n的前x位*\/, int cnt\/*前x位有多少种不同的数字*\/, int num\/*答案*\/) {
	if (x == d.size()) {
		\/\/ 输出
		printf("%d\n", num);
		return true;\/\/可行。
	} else {
		for (int i = larger ? 0 : d[x]\/*大于的话就可以从0开始，否则从d[x]开始*\/; i <= 9; i++) {
			vis[i] += 1;
			int ncnt = cnt;
			if (vis[i] == 1) ncnt += 1;\/\/若他只出现过一次，那么不同数的个数+1
			if (ncnt <= k\/*没有超过k个不同的数*\/ && dfs(x + 1\/*到了下一位*\/, larger | (i > d[x])\/*判断*\/, ncnt, num * 10 + i\/*把i插到答案里面*\/)\/*可行*\/) {
				return true;\/\/也可行。
			}
			vis[i] -= 1;\/\/回溯。
		}
		return false;\/\/不可行。
	}
}
void solve() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i <= 9; i++) vis[i] = 0;
	d.clear();\/\/清空
	while (n) {
		d.push_back(n % 10);
		n \/= 10;
	}
	reverse(d.begin(), d.end());
	dfs(0, 0, 0, 0); \/\/ 当前的前缀有没有大于n的前缀
}
int main() {
	int T;
	scanf("%d", &T);
	while (T --) {
		solve();
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-27 09:32:51

题解思路：

我们要构造一个 $01$ 串 $s$，使得 $s$ 的长度是 $\le 2\cdot t$，使得 $k$ 最小。 $k$ 指的是 $s_i = s_{i + k}$，那么 $k$ 就是 $s$ 的周期。 那么当 $t$ 是全零或者全一的，那么直接输出 $t$ 就可以了。 否则输出 $0101...01$，因为 $k=2$，最小的了。

#include <iostream>
using namespace std;
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        string s;
        cin >> s;
        bool ok = false, ok2 = false;
        for (auto x : s)
        {
            if (x == '1')
                ok = true;
            else
                ok2 = true;
        }
        if (!ok || !ok2)\/\/全0或者全1
        {
            cout << s << endl;
            continue;
        }
        for (int i = 0; i < s.size(); ++i)\/\/输出01
            printf("01");
        putchar('\n');
    }
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-27 10:15:37

题解思路：

我们就设 $a>b$。

那么当 $x<a$，那么 $x \bmod a$ 就是无效操作。

而 $x \bmod b + \bmod a$ 中 $\bmod a$ 也是无效的。

那么 $x \bmod b = x \bmod b \bmod a$

那么 $a$ 和 $b$ 的 $\operatorname{lcm}$，若 $x \bmod\operatorname{lcm} = 0$。

那么就相当于 $x \bmod a = 0$ 并且 $x \bmod b = 0$。

当 $x = \operatorname{lcm} + 1$。

那么 $x \bmod a = 1,x \bmod b = 1$。

当 $x = \operatorname{lcm} + a - 1$。

那么 $x \bmod a = a - 1,x \bmod b = x \bmod a - 1$。

那么一般情况 $x = [k \cdot \operatorname{lcm}$ ~ $k \cdot \operatorname{lcm} + a - 1]$ 里的 $x\mod a$ 和 $x\mod b$ 是相同的，否则就是不同的。

那么对于一个区间 $[l,r]$ 我们要看这里面有多少个 $\operatorname{lcm}$，那么我们就用前缀。

那么就是 $(sum_{r \div \operatorname{lcm}} - sum_{l \div \operatorname{lcm}}) \times (\operatorname{lcm} - a)$。

但我们少加了一些值，那么我们要再加上 $r \bmod \operatorname{lcm} - a + 1$。

但 $l$ 这部分多加了，所以我们要减去 $l \bmod \operatorname{lcm} - a$。

AC CODE：

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
int T;
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        ll a, b, q;
        cin >> a >> b >> q;
        if (a < b)
            swap(a, b);
        ll lcm = a * b \/ __gcd(a, b);
        ll len = lcm - a;
        while (q--)
        {
            ll ans = 0;
            ll l, r;
            cin >> l >> r;
            ll x = r \/ lcm - l \/ lcm;
            ans += x * len;
            r %= lcm;
            if (r >= a)
                ans += r - a + 1;
            l %= lcm;
            if (l > a)
                ans -= l - a;
            cout << ans << ' ';
        }
        puts("");
    }
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-27 11:02:03

题解思路：

我们对于 $c$ 相同的看成一个数。 那么我们倒着扫描，那么只要能放就放就可以了。

AC CODE：

#include <bits\/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 5;
int n, k, cnt;
int a[N], b[N], p[N], fp[N], num[N];
vector<int> zz[N];
inline void init()
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i)
	{
		int x;
		cin >> x;
		++num[x];
	}
	for (int i = 1; i <= k; ++i)
	{
		int x;
		cin >> x;
		if (!p[x])
			p[x] = ++cnt, fp[cnt] = x;
		a[cnt] += num[i];
		while (num[i]--)
			zz[cnt].push_back(i);
	}
	for (int i = 1; i <= n; ++i)
		b[i] = fp[i] - fp[i + 1];
	int x = 0;
	for (int i = cnt; i >= 1; --i)
	{
		if (!a[i])
			x += b[i];
		else
			b[i] += x, x = 0;
	}
}
int main()
{
	init();
	vector<vector<int>> ans;
	vector<pair<int, int>> now, last;
	for (int i = cnt; i >= 1; --i)
	{
		if (!a[i])
			continue;
		last.push_back({i, a[i]});
	}
	while (!last.empty())
	{
		int val = 0, z = 0;
		vector<int> res;
		for (auto &x : last)
		{
			int id = x.first, w = x.second;
			val += b[id];
			b[id] += z;
			int mi = min(x.second, val);
			w -= mi;
			val -= mi;
			while (mi--)
				res.push_back(id);
			if (w)
				now.push_back({id, w}), z = 0;
			else
				z = b[id];
		}
		ans.push_back(res);
		last = now;
		now.clear();
	}
	cout << ans.size() << '\n';
	for (auto &x : ans)
	{
		cout << x.size() << ' ';
		for (auto y : x)
		{
			cout << zz[y].back() << ' ';
			zz[y].pop_back();
		}
		cout << '\n';
	}
	return 0;
}