阿里云空间可以做网站吗,diy图片制作,wordpress 音乐页面,北京 网站建设B - Milena and Admirer
Problem - B - Codeforces
题目大意#xff1a;
现在给出一个无序序列#xff0c;你可以使用任意次操作将这个无序序列修改为不递减序列#xff0c;操作为你可以使用两个数a和b来替换ai#xff0c;序列就变为了 ai-1#xff0c; a#xff0c;…B - Milena and Admirer
Problem - B - Codeforces
题目大意
现在给出一个无序序列你可以使用任意次操作将这个无序序列修改为不递减序列操作为你可以使用两个数a和b来替换ai序列就变为了 ai-1 abai1。求将这个序列修改为不递减序列的最少操作次数。
我比赛时的错误思路标红的是正确的
对这个序列进行修改操作时应该从后往前进行修改因为他是不递减序列所以我们只要保证后面满足条件然后一直向前调整即可。这个思路是对的但是我刚开始想的是要让操作次数较少应该要尽量2分这个不合理的数让其变为合理的。所以如果是93。我的这个操作就会修改为22233进行3次修改操作。然后我突然发现3333.只会进行两次修改操作。所以思路应该为均分这个不合理的数。让他均分后小于他后面的数均分还能保证他对前面的限制条件放松来使操作次数进一步减小。
代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashMap;/*** ProjectName: study3* FileName: Ex15* author:HWJ* Data: 2023/11/19 23:05*/
public class Ex15 {static int[] arr;static long total 0;static HashMapInteger, Integer map new HashMap();public static void main(String[] args) throws IOException {StreamTokenizer in new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));in.nextToken(); int n (int) in.nval;for (int o 0; o n; o) {total 0;in.nextToken();int m (int) in.nval;arr new int[m];for (int i 0; i m; i) {in.nextToken();arr[i] (int) in.nval;}for (int i m - 2; i 0; i--) {if (arr[i] arr[i 1]) {// 尽量arr[i]均分为arr[i1]的大小。int cnt (arr[i] arr[i 1] - 1) / arr[i 1];total cnt - 1; // 均分为cnt份需要cnt-1次。arr[i] / cnt;}}System.out.println(total);}}
}Colorful Grid
Problem - C - Codeforces
题目大意
现在给出一个方格n行m列你可以将这个方格的任意一条边修改为红色或者蓝色然后需要从11这个点前往到nm这个点要求在前往路程中走完蓝色的边下一次走的边应该为红色的边走完红色的边下一次走的边应该为蓝色。然后在满足这个要求的情况下如果经过了k条边我们则称这次的路程长度为k。边可以重复经过现在给出n m k。问你有没有一个染色方案可以使从起点到终点的路径长度为k。
思路
对于一个方格他的最短路径应该为nm-2然后我们如果要判断k这个路程长度能不能到达那可以想到我们应该走多组无效路程然后一组无效路程应该长度为2。所以k应该和nm-2保持同样的奇偶性。所以他最后可能是多走了奇数组或者偶数组。那么最后就相当于多走一组奇数组或者没有多走偶数组所以我们可以构造一个正方形让他在浪费一组和不浪费的情况下都能前往终点。这里给出代码可以根据代码画图帮组理解
代码
import java.util.HashMap;
import java.util.Objects;
import java.util.Scanner;/*** ProjectName: study3* FileName: Ex16* author:HWJ* Data: 2023/11/20 12:28*/
public class Ex16 {static HashMapEdge, Character map new HashMap();public static void main(String[] args) {Scanner input new Scanner(System.in);int t input.nextInt();for (int o 0; o t; o) {int n input.nextInt();int m input.nextInt();int k input.nextInt();int mn n m - 2; // 所需要使用的最少边数// 因为k如果大于最少边数他就只能一直重复走某些路径 但重复的时候肯定会重复多组边// 一组边会增加两次所以k应该和最少边数保持同样的奇偶性if (k mn || (k % 2) ! (mn % 2)){System.out.println(No);}else {System.out.println(Yes);for (int i 1; i n; i) { // 这里将整个图的边全部染为红色for (int j 1; j m; j) {if (j 1 m) map.put(new Edge(new Node(i,j), new Node(i,j1)), R);if (i 1 n) map.put(new Edge(new Node(i,j), new Node(i1,j)), R);}}map.put(new Edge(new Node(1,1), new Node(2,1)), B);map.put(new Edge(new Node(1,2), new Node(2,2)), B);map.put(new Edge(new Node(1,3), new Node(2,3)), B);map.put(new Edge(new Node(2,2), new Node(3,2)), B);// 构造一个正方行的红蓝圈让他一直在里面绕并且可以在某个半圈或者一圈使退出正方形圈boolean f false;// 这里构造使任意一个退出的地方都一定能走到终点。for (int i 3; i m; i) {map.put(new Edge(new Node(3,i), new Node(3,i1)), f ? R : B);f !f;}for (int i 3; i n; i) {map.put(new Edge(new Node(i,m), new Node(i1,m)), f ? R : B);f !f;}for (int i 1; i n; i) {for (int j 1; j m; j) {System.out.print(map.get(new Edge(new Node(i,j),new Node(i,j1))) );}System.out.println();}for (int i 1; i n; i) {for (int j 1; j m; j) {System.out.print(map.get(new Edge(new Node(i,j),new Node(i1,j))) );}System.out.println();}}}}public static class Edge{Node s;Node e;public Edge(Node s, Node e){this.s s;this.e e;}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Edge edge (Edge) o;return Objects.equals(s, edge.s) Objects.equals(e, edge.e);}Overridepublic int hashCode() {return Objects.hash(s, e);}}public static class Node{int col;int row;public Node(int row, int col){this.col col;this.row row;}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Node node (Node) o;return col node.col row node.row;}Overridepublic int hashCode() {return Objects.hash(col, row);}}
}D. Absolute Beauty
Problem - D - Codeforces
题目大意
给出两个整数序列a和b。得分为|ai - bi|之和。现在你可以进行至多一次操作使得得分最大。操作为选择任意bi 和 bj让其交换位置。
思路
对于a序列和b序列因为得分是计算绝对值且最多只能交换一次所以ai和bi互换位置是对答案没有影响。则我们可以通过互换位置使得任意i位置上的ai一定大于等于bi。
这可以将绝对值表示的意义想象为这个线段的长度。 对于任意几个线段有三个情况。只有第一种情况的交换会使绝对值之和增加。又因为只能进行一次交换操作所以我们应该使第一种情况下的a1尽可能小b2尽可能大。
则答案增量为2*maxb- mina
代码
import java.util.Scanner;/*** ProjectName: study3* FileName: Ex17* author:HWJ* Data: 2023/11/21 9:29*/
public class Ex17 {public static void main(String[] args) {Scanner input new Scanner(System.in);int t input.nextInt();for (int o 0; o t; o) {int n input.nextInt();int[][] a new int[n][2];long total 0;int max 0;int min Integer.MAX_VALUE;for (int i 0; i n; i) {a[i][0] input.nextInt();}for (int i 0; i n; i) {a[i][1] input.nextInt();if (a[i][1] a[i][0]){int tmp a[i][1];a[i][1] a[i][0];a[i][0]tmp;}max Math.max(max, a[i][1]);min Math.min(min, a[i][0]);total a[i][0] - a[i][1];}System.out.println(Math.max(total, total 2L *(max - min)));}}
}E. Sofia and Strings
Problem - E - Codeforces
题目大意
给你两个字符串S和T,数字n和mn和m分别为字符串S和T的长度你可以对字符串S进行操作使其变为字符串T。如果能变为字符串T则输出YES否则输出NO。
操作为
1. 选择 i1 i n)将字符串S这个位置上的字符删掉。
2. 选择 l 和 r ( 1 l r n),将字符串S [ lr] 这段位置上的字符按照字典序进行排序。
思路
因为他是按照字典序进行排序那么字典序小的字符没有办法修改到字典序大的字符后面。
则给出一个样例
S abcdgef
T : efg
遍历TT1为e可以找到它在S的位置为S5S5前面的abcd已经对后序的整个操作是无效的了。
所以修改S T为
S gf
Tfg
遍历TT1为f可以找到它在S的位置为S2S2前面的g对后序的操作是有效的保留。
所以修改S T为
S g
Tg
.........这样的修改策略就可以判断S是否能修改为T。但是如果用遍历来寻找对应位置和是否删除是不明智的因为时间开销太大了。所以我们可以使用队列来实现。因为删除时只删除对应位置和对应位置前面字典序小于当前字典序的字符。满足先进先出的特性位置靠前的先进行删除操作。
代码
import java.util.LinkedList;
import java.util.Scanner;/*** ProjectName: study3* FileName: Ex18* author:HWJ* Data: 2023/11/21 12:01*/
public class Ex18 {public static void main(String[] args) {Scanner input new Scanner(System.in);int t input.nextInt();for (int o 0; o t; o) {int n input.nextInt();int m input.nextInt();String str1 input.next();String str2 input.next();char[] s1 str1.toCharArray();char[] s2 str2.toCharArray();LinkedListInteger[] set new LinkedList[27];for (int i 0; i 27; i) {set[i] new LinkedList();}for (int i 0; i n; i) {set[s1[i] - a].add(i);}boolean loop true;for (int i 0; i m; i) {if (set[s2[i] - a].isEmpty()){loop false;break;}int now set[s2[i] - a].removeFirst();for (int j 0; j s2[i] - a; j) {while (!set[j].isEmpty() set[j].getFirst() now){set[j].removeFirst();}}}System.out.println(loop ? YES : NO);}}
}
