原博客链接：https://blog.nowcoder.net/n/16c41ade73cd41d6bcf1b058de58786b

A

模拟

import java.util.*;
import java.io.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[]args) throws IOException{
        int a = sc.next().length(),b = sc.next().length();
        if(a==6||b==6) {
            System.out.println(-1);
		}
		else {
			System.out.println(Math.abs(a-b)+1);
		}
	}
}

B

分类讨论。特判0，1各一个的情况。

import java.util.*;
import java.io.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[]args) throws IOException{
        int n=sc.nextInt();
		char []s = ("*"+sc.next()).toCharArray();
		int []cnt = new int [2];
		for(int i=1;i<=n;i++) {
			cnt[s[i]-'0']++;
		}
		if(cnt[0]==n||cnt[1]==n) {
			System.out.println(0);return;
		}
		if(cnt[0]==cnt[1]&&cnt[1]==1) {
			System.out.println(-1);return;
		}
		if(cnt[0]==cnt[1]) System.out.println(2);
		else System.out.println(1);
	}
}

C

枚举 右端点 , 显然不会左移，故可二分or双指针。

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65535);
	static StreamTokenizer st = new StreamTokenizer(bf);
	public static void main(String[]args) throws IOException{
		int n=I();long ans=0;
		long []a = new long[n+2];
		for(int i=1;i<=n;i++) {
			int x=I();
			a[i] = a[i-1]+x;
		}
           int p=2;
		for(int i=1;i+2<=n;i++) {
			int l=i+1;
            while(p<n && (a[i]>=a[p]-a[i] || a[p]-a[i]<= a[n]-a[p]))
			    p++;
            ans += n-p;
		}
		System.out.println(ans);
	}
	
	static int I() throws IOException{
		st.nextToken();
		return (int)st.nval;
	}
}

D

巨大多分类讨论。当心负数。

import java.util.*;
import java.io.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[]args) throws IOException{
        int t=sc.nextInt();
        long ans=0;
        while(t-->0){
            int n=sc.nextInt();
			long a=sc.nextInt(),b=sc.nextInt();
			int []cnt = new int [6];
			cnt[0]=cnt[1]=0;
			ans=0;
			for(int i=1;i<=n;i++) {
				int x= sc.nextInt();
				cnt[x%2]++;
			}
			if(a<0&&b<0) {
				for(int i=0;i<2;i++) {
					ans += a*(cnt[i]-1)*cnt[i]/2;
				}
				ans += b*cnt[0]*cnt[1];
			}
			else if(a<0&&b>=0) {
				for(int i=0;i<2;i++) {
					ans += a*(cnt[i]-1)*cnt[i]/2;
				}
				if(cnt[0]>0&&cnt[1]>0) ans += b;
			}
			else if(a>=0&&b<0) {
				ans = b*cnt[0]*cnt[1];
				if(ans==0) {
					ans = (n-1)*a;
				}
			}else {
				if(cnt[0]==0||cnt[1]==0) ans=(n-1)*a;
				else {
					if(a<b) {
						if(n>=2) ans=b+(n-2)*a;
					}
					else {
						ans=(n-1)*b;
					}
				}
			}
			System.out.println(ans);
        }
	}
}

E

离散化+树状数组。

先 一下看哪些结点满足条件 但不满足条件 ，这样删除该结点子孙的子树可能会使其成为支撑结点，设该类结点为半支撑结点。

第二次 ，对于当前结点，看是否有祖先半支撑结点，满足删除当前结点子树可以转化成支撑结点，将这些结点统计进答案，并删除当前节点子树的支撑点数量。

需满足： ,即 ，其中 表示该节点下层结点权值和， 为结点权值，可用树状数组查询。由于数据范围达到 ，需离散化。

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65535);
	static StreamTokenizer st = new StreamTokenizer(bf);
	static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
	static int n,m,maxn=200005,inf = 0x3f3f3f3f;
	static long ans=0,mod=(int)1e9+7,INF=(long)2e18;
	public static void main(String[]args) throws IOException{
		new Task().main();
		pw.flush();
	}
	
	static int I() throws IOException{
		st.nextToken();
		return (int)st.nval;
	}

	static class Task{
		void main()throws IOException{
			int t=1;
			//t=sc.nextI();
			while(t-->0) solve();
		}
		
		int []a = new int [maxn];
		Vector<Vector<Integer>>g = new Vector<>();
		int []cnt = new int[maxn];//自下向上的稳定点数量（包含自身）
		long []s2 = new long [maxn];//当前结点下层结点权值之和
		boolean []tf = new boolean[maxn];//条件1
		boolean []df = new boolean[maxn];//条件2
		Map<Long,Integer> mp = new HashMap<>();
		Vector<Long> vv = new Vector<>();
		BIT tr = new BIT();
		long ans2=0;
		
		private void solve() throws IOException {
			n=I();
			for(int i=1;i<=n;i++) a[i]=I();
			for(int i=0;i<=n;i++) g.add(new Vector<>());
			for(int i=1;i<=n;i++) {
				int x=I();
				g.get(x).add(i);
			}
			dfs(1,0);
			for(int i=1;i<=n;i++) 
                if(tf[i]&&!df[i]) vv.add((long)(s2[i]-a[i]));
			Collections.sort(vv);
			m=0;
			for(long x:vv) {
				if(!mp.containsKey(x)) {
					mp.put(x, ++m);//离散化
				}
			}
			tr.maxn=m;
			dfs2(1);
			pw.println(Math.max(ans, ans2));
		}

		private void dfs2(int i) {
			if(tf[i]&&!df[i]) {
				tr.modify(mp.get(s2[i]-a[i]), 1);
			}
			for(int x:g.get(i)) {
				long sum = s2[x]+a[x];//子树权值和
				int r = find(sum);//找到小于等于该节点权值的值的离散化索引
				if(r!=-1) {
					ans2 = Math.max(ans2, ans-cnt[x]+tr.qu(r));
				}
				dfs2(x);
			}
			if(tf[i]&&!df[i]) {
				tr.modify(mp.get(s2[i]-a[i]), -1);
			}
		}
		
		private int find(long sum) {
			int l=1,r=vv.size();
			int p=-1;
			while(l<=r) {
				int mid=(l+r)/2;
				if(vv.get(mid-1)<=sum) {
					p=mid-1;
					l=mid+1;
				}
				else r=mid-1;
			}
			return p>=0?mp.get(vv.get(p)):-1;
		}

		private long dfs(int i, long sum) {
			if(sum>=a[i]) tf[i]=true;
			long res=0;
			for(int x:g.get(i)) {
				res+=dfs(x,sum+a[i]);
				cnt[i] += cnt[x];
			}
			if(res<=a[i]) df[i]=true;
			df[i]=df[i]&&tf[i];
			s2[i] = res;
			if(df[i]) {
				ans++;
				cnt[i]++;
			}
			return res+a[i];
		}
	}
}

class BIT {
	int maxn=200005;
	int []t = new int [maxn];
	
	int lowbit(int x) {
		return x&-x;
	}
	
	int qu(int x) {
		int ans = 0;
		for(int i=x;i>0;i-=lowbit(i)) {
			ans += t[i];
		}
		return ans;
	}
	
	void modify(int x,int v) {
		for(int i=x;i<=maxn;i+=lowbit(i)) {
			t[i] += v;
		}
	}
	
}

F

思维。

表示当前所有值在 内的数的数量。遍历每个前缀 ，将当前数 更新至 ，然后求新的逆序对数量，为之前所有比它大的数的数量，可 转移。

之后循环将数组开头的数移到末尾，动态更新逆序对数量。先减去比它小的数的数量，再加上比它大的数的数量。

复杂度： ( 为卡， 设置较大，确实比较吓人

import java.util.*;
import java.io.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[]args) throws IOException{
		int n=sc.nextInt();
        int []a = new int [n+5];
		int sum[] = new int [n+5];
        long ans=0;
		for(int i=1;i<=n;i++) a[i]=sc.nextInt();
		for(int i=1;i<=n;i++) {
			ans += sum[n]-sum[a[i]];
			long res=ans,w=ans;
			for(int j=a[i];j<=n;j++) sum[j]++;
			for(int j=1;j<i;j++) {
				res = res - sum[a[j]-1] + i-sum[a[j]];
				w = Math.min(res, w);
			}
			System.out.print(w+" ");
		}
	}
}