如何利用NAS做网站,温州网站专业制作,西安自助建站系统,长沙微营销第一题
字典序最小的 01 字符串
解题思路#xff1a;
模拟#xff0c;统计遇到的连续的1的个数记为num#xff0c;直到遇到0#xff0c;如果knum#xff0c;直接将第一个1置为0#xff0c;将遇到的0置为1#xff0c;否则将第一个1偏置num-k个位置置为0#xff0…第一题
字典序最小的 01 字符串
解题思路
模拟统计遇到的连续的1的个数记为num直到遇到0如果knum直接将第一个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[i1] ! 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[i1] ! 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
#includeiostream
#include vector
using namespace std;const long long mod 1000000000 7;int main() {int n;cin n;vectorlong long nums(n, 0);vectorlong 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(vectorint ans, vectorlistint 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;vectorlistint tree(n, listint(0));vectorint 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, ListInteger[] 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();ListInteger[] 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();}
}
