本文最后更新于：7 小时前
落地成盒
题目内容
给定一个长度为 n 的整数数组 {a1,a2,…,ana1,a2,…,an}。我们按顺序将相邻元素两两成 “盒”：
- 盒 11 为 (a1,a2)(a1,a2)，盒 22 为 (a3,a4)(a3,a4)，以此类推；
- 若 n 为奇数，则最后一个盒为单元素盒 (an)。
你需要恰好选择 x 个盒，并从每个被选择的盒中选出且仅选出一个数字，使得所有被选数字的和为奇数。判断是否可以做到。
思路
这是一道经典的贪心 + 奇偶性分析题目。代码的核心思路是将问题转化为“在可选范围内，能否凑出奇数个奇数”。
以下是简洁明了的算法解析：
1. 核心思想
要使 $x$ 个数的和为奇数，这 $x$ 个数中必须包含奇数个奇数（例如 1个、3个、5个…），其余的数必须是偶数。
因此，问题转化为：在选出的 $x$ 个盒子中，能否选出 $k$ 个奇数，使得 $k$ 是奇数？
2. 代码逻辑分步解析
第一步：统计盒子的能力
代码遍历数组，将相邻两个数视为一个“盒子”。
oddBox：统计有多少个盒子能选出奇数（只要盒子里有一个奇数即可）。evenBox：统计有多少个盒子能选出偶数（只要盒子里有一个偶数即可）。
- 注意：一个盒子可能既能选奇数也能选偶数（如 {1, 2}），所以两者之和可能大于总盒子数。
第二步：确定“奇数个数 $k$”的合法范围
假设我们在选中的 $x$ 个盒子中，最终拿出了 $k$ 个奇数。那么 $k$ 必须满足以下两个限制：
- 上限限制（资源够不够）： 我们最多只能从
oddBox 个盒子里拿出奇数，且不能超过总共选的 $x$ 个。
- $k \le \min(x, \text{oddBox})$ （对应代码中的
right）
- 下限限制（偶数够不够）： 我们选了 $x$ 个数，其中 $k$ 个是奇数，剩下的 $x-k$ 个必须是偶数。这就要求必须有足够的盒子能拿出偶数。
- $x - k \le \text{evenBox} \implies k \ge x - \text{evenBox}$
- 同时 $k \ge 0$。
- 所以 $k \ge \max(0, x - \text{evenBox})$ （对应代码中的
left）
第三步：判断是否存在解
现在我们要找一个整数 $k$，满足：
- $left \le k \le right$
- $k$ 必须是奇数
代码通过 firstOdd 找到区间 $[left, right]$ 内的第一个奇数。如果这个奇数没有超出右边界 right，说明存在合法的 $k$，输出 Yes，否则 No。
总结
该算法的时间复杂度为 $O(n)$，通过统计每个盒子“能出什么数”，将问题简化为在一个数值区间内寻找奇数的问题。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
int t = in.nextInt();
while (t-- > 0) {
int n = in.nextInt();
int x = in.nextInt();
int oddBox = 0;
int evenBox = 0;
for (int i = 1; i <= n; i += 2) {
int a = in.nextInt();
if (i == n) {
if ((a & 1) == 1) {
oddBox++;
} else {
evenBox++;
}
} else {
int b = in.nextInt();
if (((a & 1) == 1) || ((b & 1) == 1)) {
oddBox++;
}
if (((a & 1) == 0) || ((b & 1) == 0)) {
evenBox++;
}
}
}
int left = Math.max(0, x - evenBox);
int right = Math.min(x, oddBox);
int firstOdd = (left % 2 == 1) ? left : left + 1;
if (firstOdd <= right) {
sb.append("Yes\n");
} else {
sb.append("No\n");
}
}
System.out.print(sb.toString());
}
}
|
最长非重复子串
题目内容
我们定义一个仅由小写字母组成的字符串 s 的奇怪度为：其中的最长非重复子串数量。此处 “数量” 按起止位置计数，不按内容去重。
现在，给定两个整数 n 和 k，要求构造一个长度为 n 、仅由小写字母组成的字符串 s，其奇怪度恰好为 k 。如果无解，则输出 −1。
【名词解释】
非重复子串：每个字符出现的次数不超过 1 次的字符串。例如 “abcg” 是非重复子串，而 “aba” 不是非重复子串（因为 ‘a’ 出现了两次）。
子串：从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。
思路
关键观察
最长非重复子串的长度取决于字符串中连续不同字符的最大个数：
- 全相同字符（如”aaa”）→ 最长非重复子串长度为1
- 交替字符（如”abab”）→ 最长非重复子串长度为2（只有a和b两种字符）
构造策略
情况1：k = n
- 输出n个相同字符（如”aaa…a”）
- 最长非重复子串长度为1，共有n个位置，数量恰好为n ✓
情况2：k < n
- 前k+1个字符交替使用’a’和’b’（如”ababa…”）
- 剩余n-(k+1)个字符全部填充为最后一个字符
- 例如：n=5, k=3 → “ababb”
正确性证明
对于构造的字符串（前k+1位交替，后面全相同）：
- 最长非重复子串长度 = 2（因为只有a和b，且交替出现）
- 长度为2的非重复子串数量 = k
- 交替部分长度为k+1
- 相邻位置对的数量 = (k+1) - 1 = k ✓
- 后面填充相同字符不会产生新的长度为2的非重复子串
时间复杂度
示例验证
| n |
k |
构造结果 |
最长非重复子串 |
数量 |
| 3 |
3 |
“aaa” |
“a” |
3 ✓ |
| 5 |
3 |
“ababb” |
“ab”, “ba”, “ab” |
3 ✓ |
| 4 |
2 |
“abaa” |
“ab”, “ba” |
2 ✓ |
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
StringBuilder sb = new StringBuilder();
if (k == n) {
for (int i = 0; i < n; i++) {
sb.append('a');
}
System.out.println(sb);
return;
}
for (int i = 0; i <= k; i++) {
if ((i & 1) == 0) {
sb.append('a');
} else {
sb.append('b');
}
}
char last = sb.charAt(sb.length() - 1);
while (sb.length() < n) {
sb.append(last);
}
System.out.println(sb);
}
}
|
我即唯一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
| import java.io.*;
import java.util.*;
public class Main {
static final long MOD = 1000000007L;
static final int LOG = 31;
static long tri(long x) {
return x % MOD * ((x + 1) % MOD) % MOD * ((MOD + 1) / 2) % MOD;
}
static long pathSum(int start, long step, int[][] up, long[][] sum) {
long ans = 0;
int x = start;
int b = 0;
while (step > 0) {
if ((step & 1) == 1) {
ans = (ans + sum[b][x]) % MOD;
x = up[b][x];
}
step >>= 1;
b++;
}
return ans;
}
static long cycleSegSum(int cid, int start, int len, ArrayList<int[]> cycleList, ArrayList<long[]> preList) {
if (len == 0) return 0;
int[] nodes = cycleList.get(cid);
int L = nodes.length;
long[] pre = preList.get(cid);
if (start + len <= L) {
return (pre[start + len] - pre[start] + MOD) % MOD;
} else {
return (pre[L] - pre[start] + pre[(start + len) % L] + MOD) % MOD;
}
}
static void solve() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
int[] a = new int[n + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
ArrayList<Integer>[] rev = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) rev[i] = new ArrayList<>();
int[] indeg = new int[n + 1];
for (int i = 1; i <= n; i++) {
rev[a[i]].add(i);
indeg[a[i]]++;
}
boolean[] inCycle = new boolean[n + 1];
Arrays.fill(inCycle, true);
ArrayDeque<Integer> dq = new ArrayDeque<>();
for (int i = 1; i <= n; i++) {
if (indeg[i] == 0) {
dq.add(i);
inCycle[i] = false;
}
}
while (!dq.isEmpty()) {
int u = dq.poll();
int v = a[u];
indeg[v]--;
if (indeg[v] == 0) {
inCycle[v] = false;
dq.add(v);
}
}
int[] cid = new int[n + 1];
int[] pos = new int[n + 1];
int[] dist = new int[n + 1];
int[] entryPos = new int[n + 1];
Arrays.fill(cid, -1);
Arrays.fill(pos, -1);
Arrays.fill(dist, -1);
Arrays.fill(entryPos, -1);
boolean[] vis = new boolean[n + 1];
ArrayList<int[]> cycleList = new ArrayList<>();
ArrayList<Long> cycleSum = new ArrayList<>();
ArrayList<long[]> preList = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (inCycle[i] && !vis[i]) {
ArrayList<Integer> list = new ArrayList<>();
int x = i;
while (!vis[x]) {
vis[x] = true;
pos[x] = list.size();
list.add(x);
x = a[x];
}
int id = cycleList.size();
int m = list.size();
int[] nodes = new int[m];
long[] pre = new long[m + 1];
long total = 0;
for (int j = 0; j < m; j++) {
int u = list.get(j);
nodes[j] = u;
cid[u] = id;
dist[u] = 0;
entryPos[u] = pos[u];
total = (total + u) % MOD;
pre[j + 1] = (pre[j] + u) % MOD;
}
cycleList.add(nodes);
cycleSum.add(total);
preList.add(pre);
}
}
dq.clear();
for (int i = 1; i <= n; i++) {
if (inCycle[i]) dq.add(i);
}
while (!dq.isEmpty()) {
int u = dq.poll();
for (int v : rev[u]) {
if (dist[v] != -1) continue;
if (inCycle[v]) continue;
dist[v] = dist[u] + 1;
cid[v] = cid[u];
entryPos[v] = entryPos[u];
dq.add(v);
}
}
int[][] up = new int[LOG][n + 1];
long[][] sum = new long[LOG][n + 1];
for (int i = 1; i <= n; i++) {
up[0][i] = a[i];
sum[0][i] = i;
}
for (int j = 1; j < LOG; j++) {
for (int i = 1; i <= n; i++) {
int mid = up[j - 1][i];
up[j][i] = up[j - 1][mid];
sum[j][i] = (sum[j - 1][i] + sum[j - 1][mid]) % MOD;
}
}
StringBuilder out = new StringBuilder();
for (int i = 0; i < q; i++) {
st = new StringTokenizer(br.readLine());
int p = Integer.parseInt(st.nextToken());
long k = Long.parseLong(st.nextToken());
int d = dist[p];
if (k <= d) {
out.append(pathSum(p, k, up, sum)).append('\n');
continue;
}
long res = pathSum(p, d, up, sum);
int id = cid[p];
int start = entryPos[p];
int L = cycleList.get(id).length;
long total = cycleSum.get(id);
long m = k - d;
long r = m / L;
int rem = (int) (m % L);
res = (res + tri(r) * total) % MOD;
res = (res + ((r + 1) % MOD) * cycleSegSum(id, start, rem, cycleList, preList)) % MOD;
out.append(res % MOD).append('\n');
}
System.out.print(out);
}
public static void main(String[] args) throws Exception {
solve();
}
}
|