B~F 题解
首先特判无解的情况，k==1 or k>n 的时候无解，其他情况的，只需要把1-k的数字右移一个即可，时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),k=sc.nextInt();
if(k==1||k>n){
System.out.println("-1");
}
else{
for(int i=0;i<n;i++){
int p=sc.nextInt();
System.out.print((p<=k?p%k+1:p)+" ");
}
}
}
}
先特判一位数，此时有解的前提是数字本身为4的倍数；否则从最后一位枚举后两位，判断后缀是否为4的倍数，时间复杂度O(len(s))
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
String s=sc.next();
int n=s.length();
if(n==1){
System.out.println(Integer.parseInt(s)%4==0?0:-1);
return;
}
for(int i=0;i<n;i++){
if((s.charAt((n+i-2)%n)*10+s.charAt((n+i-1)%n))%4==0){
System.out.println(i);
return;
}
}
System.out.println("-1");
}
}
容易证明，要想让字母不浪费，必须将区间分为三组，第一组全是r，第二组全是e，第三组全是d，且是哪个组的数量越接近，乘积越大，因此根据区间长度，枚举三个数最接近的时候的各种情况，处理处理得到字母不对应的位子的个数，统计时可用前缀和加速运算，（另外需要特判区间长度小于3时，无需修改，因为无论如何子序列都是0），代码实现的时候可以预处理出偏移量数组，核心算法时间复杂度O(n+q)
import java.util.*;
public class Main{
static int move[][][][]={{{{0,0},{0,0},{0,0}}},{{{0,0},{0,0},{0,1}},{{0,0},{0,1},{1,1}},{{0,1},{1,1},{1,1}}},{{{0,1},{1,2},{2,2}},{{0,1},{1,1},{1,2}},{{0,0},{0,1},{1,2}}}};
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
Map<Character,Integer> map=new HashMap<>();
map.put('r',0);
map.put('e',1);
map.put('d',2);
int n=sc.nextInt(),q=sc.nextInt(),pre[][]=new int[n+1][3];
String s=sc.next();
for(int i=1;i<=n;i++){
pre[i]=pre[i-1].clone();
pre[i][map.get(s.charAt(i-1))]++;
}
for(int i=0;i<q;i++){
int l=sc.nextInt(),r=sc.nextInt();
System.out.println(find(pre,l,r));
}
}
static int find(int pre[][],int l,int r){
if(r-l<2){
return 0;
}
l--;
int ans=(int)1e9,d=(r-l)/3;
for(int m[][]:move[(r-l)%3]){
int sum=0;
for(int i=0;i<3;i++){
sum+=d+m[i][1]-m[i][0]-(pre[l+d*(i+1)+m[i][1]][i]-pre[l+d*i+m[i][0]][i]);
}
ans=Math.min(ans,sum);
}
return ans;
}
}
E 小红的树上赋值（easy） and F 小红的树上赋值（hard）
通过观察可知，树可以在每个红色节点头顶处截断，形成若干连通块，连通块内的数字之和为0即可，划分连通块可以一次遍历得到；下边来看如何分配节点的值，为了使得绝对值之和尽可能大，节点值尽可能是绝对值最大数字，且往接近0的方向变化，也就是比在赋值的时候，记录当前总和，总和大于0则填充l否则填充r，直到最后，根据sum的值，选择调整其中的正数或者负数，时间复杂度O(n)
import java.util.*;
import java.io.*;
public class Main{
public static void main(String args[]) throws IOException{
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
String arr[]=bf.readLine().split(" ");
int n=Integer.parseInt(arr[0]),l=Integer.parseInt(arr[1]),r=Integer.parseInt(arr[2]),group[]=new int[n+5];
String s=bf.readLine();
long ans[]=new long[n+5];
List<Integer> path[]=new List[n+5],list[]=new List[n+5];
for(int i=1;i<=n;i++){
path[i]=new ArrayList<>();
list[i]=new ArrayList<>();
group[i]=i;
}
for(int i=0;i<n-1;i++){
arr=bf.readLine().split(" ");
int u=Integer.parseInt(arr[0]),v=Integer.parseInt(arr[1]);
path[u].add(v);
path[v].add(u);
}
find(1,1,path,list,s,new boolean[n+5]);
for(int i=1;i<=n;i++){
if(list[i].size()>0){
if(s.charAt(i-1)=='W'){
for(int a:list[i]){
ans[a]=r>=-l?r:l;
}
}
else{
//为了使得绝对值之和最大，要尽量让每个位置的数字不为0，先用绝对值最大的数字去尝试填充
long sum=0;
for(int a:list[i]){
if(sum<=0){
sum+=r;
ans[a]=r;
}
else{
sum+=l;
ans[a]=l;
}
}
if(sum!=0){
for(int a:list[i]){
if(sum>0&&ans[a]>0||sum<0&&ans[a]<0){
ans[a]-=sum;
break;
}
}
}
}
}
}
for(int i=1;i<=n;i++){
bw.write(ans[i]+" ");
}
bw.flush();
}
static void find(int k,int parent,List<Integer> path[],List<Integer> list[],String s,boolean has[]){
//给相邻的点分组
has[k]=true;
if(s.charAt(k-1)=='R'){
parent=k;
}
list[parent].add(k);
for(int a:path[k]){
if(!has[a]){
find(a,parent,path,list,s,has);
}
}
}
}
京公网安备 11010502036488号