牛客周赛 Round 34 题解 | DEFG
思路见注释
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),a[]=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
int b[]=a.clone();
Arrays.sort(b);
if(b[n-1]==0){
//说明全是0：
for(int i=0;i<n-1;i++){
a[i]=1;
}
a[n-1]=2;
}
boolean head=a[0]==0,tail=a[n-1]==0;
//先处理所有0变成左边的数字或者右边的非零数字，方法就是正着溜一遍，反着溜一遍
for(int i=0,j=-1;i<n;i++){
if(a[i]!=0){
j=a[i];
}
else if(j!=-1){
a[i]=j;
}
}
for(int i=n-1,j=-1;i>=0;i--){
if(a[i]!=0){
j=a[i];
}
else if(j!=-1){
a[i]=j;
}
}
//接下来验证所有数字的陡峭值是不是小于等于1
long sum=0;
for(int i=1;i<n;i++){
sum+=Math.abs(a[i]-a[i-1]);
}
if(sum>1){
System.out.println("-1");
return;
}
if(sum==0){
//此时只能修改首尾的数字，不然陡峭值至少是2了
if(!head&&!tail){
System.out.println("-1");
return;
}
if(head){
a[0]++;
}
else{
a[n-1]++;
}
}
for(int num:a){
System.out.print(num+" ");
}
}
}
验证图是否为二分图即可
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
char c[]=sc.next().toCharArray();
List<Integer> path[]=new List[n];
for(int i=0;i<n;i++){
path[i]=new ArrayList<>();
}
for(int i=0;i<n-1;i++){
int u=sc.nextInt()-1,v=sc.nextInt()-1;
path[u].add(v);
path[v].add(u);
}
System.out.println(find(n,path,c));
}
static String find(int n,List<Integer> path[],char c[]){
//先判断是否有非？的字符，有的话直接开始BFS，否则从0开始赋值并BFS
boolean all=false;
for(char ch:c){
if(ch!='?'){
all=true;
}
}
if(!all){
c[0]='p';
}
Queue<Integer> q=new LinkedList<>();
boolean has[]=new boolean[n];
for(int i=0;i<n;i++){
if(c[i]!='?'){
q.add(i);
has[i]=true;
while(!q.isEmpty()){
int a=q.poll();
for(int b:path[a]){
if(!has[b]){
if(c[a]==c[b]){
return "-1";
}
c[b]=(char)('p'+'d'-c[a]);
has[b]=true;
q.add(b);
}
}
}
break;
}
}
return new String(c);
}
}
思路见注释：
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt(),x=sc.nextInt(),ans[][]=new int[n][m];
//x必定为偶数，那么x mod 4 的取值只能是0或者2
if(x%4==0){
//此时左上角四个都填上x/4，这样每行每列异或为0
ans[0][0]=ans[0][1]=ans[1][0]=ans[1][1]=x/4;
}
else{
//此时需要考虑x==2
if(x==2){
//只有在n和m等于2的时候可以得到{{1,0},{0,1}}，但是题目要求m和n大于等于4，所以直接返回
System.out.println("-1");
return;
}
//可以先考虑左上的边长为3的正方形，分出6个数先保持异或和为0：
//填充反对角6个位置为1
ans[0][1]=ans[0][2]=ans[1][2]=ans[1][0]=ans[2][0]=ans[2][1]=1;
//填充四角，依旧保持异或为0：
ans[0][0]=ans[0][m-1]=ans[n-1][0]=ans[n-1][m-1]=(x-6)/4;
}
for(int a[]:ans){
for(int b:a){
System.out.print(b+" ");
}
System.out.println();
}
}
}
思路： 1、首先如果没有颜色要求，那么就是找自环就行了，每个环内的交换次数就是环大小减1； 2、加上颜色，对于每个环，如果存在两种颜色，那么必定存在某俩可交换的位置是颜色相反的，否则二者所在的集体不构成环，，那么这样的环依旧可以环大小减1次交换到位； 3、对于某个环，如果其中的颜色单一，那么必然需要先从别的环内交换一个另外颜色的字符，之后进行环内交换，最后把换出去的那个再换回来，也就是比多了2步操作； 4、如何进一步减少次数呢？发现可以在纯色环之间进行交换，也就是纯白环可以先跟纯红环交换一个元素，再各自交换完后换回来，那么相当于只加了一个环的2，那么多余的交换次数，就是2倍的max(纯白环数，纯红环数) 5、还有啊，需要特判，非升序且全部纯色，无解
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),idx[]=new int[n];
for(int i=0;i<n;i++){
idx[sc.nextInt()-1]=i;
}
String s=sc.next();
int ans=0,red=0,white=0;
boolean visited[]=new boolean[n];
for(int i=0;i<n;i++){
if(!visited[i]){
int count=1,p=i;
boolean hasRed=s.charAt(i)=='R',hasWhite=s.charAt(i)=='W';
visited[i]=true;
while(!visited[idx[p]]){
count++;
p=idx[p];
visited[p]=true;
if(s.charAt(p)=='R'){
hasRed=true;
}
else{
hasWhite=true;
}
}
ans+=count-1;
if(count!=1){
if(hasRed&&!hasWhite){
red++;
}
else if(!hasRed&&hasWhite){
white++;
}
}
}
}
if(ans!=0){
//此时假如全是一种颜色，但是排列并不是有序的，那么无法交换，无解
char c[]=s.toCharArray();
Arrays.sort(c);
if(c[0]==c[n-1]){
System.out.println("-1");
return;
}
}
System.out.println(ans==0?0:ans+Math.max(red,white)*2);
}
}
待续。。
投递科大讯飞等公司10个岗位 >
