第一题
- 字典序最小的 01 字符串
解题思路:
模拟,统计遇到的连续的1的个数记为num,直到遇到0,如果k>=num,直接将第一个1置为0,将遇到的0置为1,否则将第一个1偏置num-k个位置置为0,遇到的0置为1。
原理是遇到的1,基本都要往后移。有多少个k就可以往后移多少个1,而字典序最小又要求我们优先移动前面的
#include <iostream>
#include <string>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
int num = 0;
int start = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0') continue;
num = 0;
start = i;
num++;
while (i + 1 < n && s[i+1] != '0') {
num++; i++;
}
if (i + 1 >= n) break;
if (k >= num) {
s[start] = '0'; s[start + num] = '1';
k -= num;
i = start;
}
else {
s[start + num - k] = '0'; s[start + num] = '1';
k = 0; break;
}
}
cout << s << endl;
}
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
sc.nextLine();
String str = sc.nextLine();
char[] ch = str.toCharArray();
int num = 0;
int start = 0;
for (int i = 0; i < n; i++) {
if (ch[i] == '0') continue;
num = 0;
start = i;
num++;
while (i + 1 < n && ch[i+1] != '0') {
num++; i++;
}
if (i + 1 >= n) break;
if (k >= num) {
ch[start] = '0'; ch[start + num] = '1';
k -= num;
i = start;
}
else {
ch[start + num - k] = '0'; ch[start + num] = '1';
k = 0; break;
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++)
sb = sb.append(ch[i]);
System.out.println(sb.toString());
}
}
第二题
- 数组子序列的排列
解题思路:
先统计从1开始连续的数的个数和每个数在数组中出现的个数,只统计100000以下的数出现的个数,最后计算规律为n1 + n1n2 + n1n2n3 + … + n1n2…*nm
#include<iostream>
#include <vector>
using namespace std;
const long long mod = 1000000000 + 7;
int main() {
int n;
cin >> n;
vector<long long> nums(n, 0);
vector<long long> num(n, 0);
for (int i = 0; i < n; i++) {
cin >> nums[i];
if (nums[i] < 100000)
num[nums[i]-1]++;
}
int b = 0;
for (int i = 0; i < n; i++) {
if (num[i] == 0) {
b = i; break;
}
}
long long sum = 0;
for (int i = 0; i < b; i++) {
long long sum_in = 1;
for (int j = 0; j <= i; j++) {
sum_in *= num[j];
sum_in %= mod;
}
sum += sum_in;
sum %= mod;
}
sum %= mod;
cout << sum << endl;
}
import java.util.*;
class Main {
public static void main(String[] args) {
long mod = 1000000007L;
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
long[] nums = new long[n];
long[] num = new long[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextLong();
if (nums[i] < 100000)
num[(int)nums[i]-1]++;
}
int b = 0;
for (int i = 0; i < n; i++) {
if (num[i] == 0) {
b = i; break;
}
}
long sum = 0;
for (int i = 0; i < b; i++) {
long sum_in = 1;
for (int j = 0; j <= i; j++) {
sum_in *= num[j];
sum_in %= mod;
}
sum += sum_in;
sum %= mod;
}
sum %= mod;
System.out.println(sum);
}
}
第三题
- 传送树
解题思路
用dfs扫描一遍邻接表即可
#include <iostream>
#include <list>
#include <vector>
#include <climits>
using namespace std;
int dfs(vector<int>& ans, vector<list<int>>& tree, int index) {
if (tree[index].size() == 0) {
ans[index] = 1;
return index;
}
int ret = INT_MAX;
for (int t : tree[index]) ret = min(dfs(ans, tree, t), ret);
ans[index] = ans[ret] + 1;
return min(index, ret);
}
int main() {
int n;
cin >> n;
vector<list<int>> tree(n, list<int>(0));
vector<int> ans(n, 0);
int u, v;
for (int i = 0; i < n - 1; i++) {
cin >> u >> v;
tree[u-1].push_back(v-1);
}
dfs(ans, tree, 0);
for (int index = 0; index < n; index++) {
cout << ans[index] << ' ';
}
cout << endl;
}
import java.util.*;
class Main {
public static int dfs(int[] ans, List<Integer>[] tree, int index) {
if (tree[index].size() == 0) {
ans[index] = 1;
return index;
}
int ret = Integer.MAX_VALUE;
for (int t : tree[index]) ret = Math.min(dfs(ans, tree, t), ret);
ans[index] = ans[ret] + 1;
return Math.min(index, ret);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<Integer>[] tree = new List[n];
for (int i = 0; i < n; i++) tree[i] = new ArrayList<>();
int[] ans = new int[n];
int u, v;
for (int i = 0; i < n - 1; i++) {
u = sc.nextInt();
v = sc.nextInt();
tree[u-1].add(v-1);
}
dfs(ans, tree, 0);
for (int index = 0; index < n; index++) {
System.out.print(ans[index] + " ");
}
System.out.println();
}
}