原博客链接

A 清楚姐姐的糖葫芦

签到。

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[]args) throws IOException{
		char[]s = sc.next().toCharArray();
		long ans=0;
		for(char x:s) {
			if(x=='o') ans++;
		}
		System.out.println(ans);
	}
}

B 清楚姐姐买竹鼠

分类讨论。

import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[]args) throws IOException{
		long a=sc.nextLong(),b=sc.nextLong(),x=sc.nextLong(),ans=0;
		if(a*3<=b) {
			System.out.println(a*x);return;
		}
		ans += x/3*b;
		x -= x/3*3;
		System.out.println(ans + Math.min(a*x, b));
	}
}

C 竹鼠饲养物语

模拟。
开一个桶逐级往上，维护当前等级 的竹鼠数量。 ​

import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[]args) {
        int n = sc.nextInt(),m = sc.nextInt();
        int []a = new int [n+2];
        for(int i=1;i<=n;i++){
            int x = sc.nextInt();
            if(x>n) continue;
            a[x]++;
        }
        long ans=0;
        int tot = n;
        for(int i=1;tot>0;i++){
            int x = Math.min(a[i],tot);
            ans += x;
            tot = x;
        }
        System.out.println(ans);
    }
}

D 清楚姐姐跳格子

bfs。
由于 只有 ，暴力遍历 ~ 内是否是当前位置数的因数即可。复杂度： ​

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

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[]args) throws IOException{
		long []a = new long[1002];
		boolean []f = new boolean[1002];
		int []dp = new int [1002];
		int n = sc.nextInt();
		int inf = (int)1e9;
		for(int i=1;i<=n;i++) a[i] = sc.nextLong();
		Arrays.fill(dp, inf);
		dp[1] = 0;
		Queue<Integer> q = new LinkedList<>();
		q.add(1);
		while(!q.isEmpty()) {
			int x = q.poll();
			for(int i=1;i<=n;i++) {
				if(a[x]%i == 0) {
					if(x+i<=n && dp[x+i] > dp[x] + 1) {
						dp[x+i] = dp[x] + 1;
						q.add(x+i);
					}
					if(x-i>1 && dp[x-i] > dp[x] + 1) {
						dp[x-i] = dp[x] + 1;
						q.add(x-i);
					}
				}
			}
		}
		System.out.println(dp[n]);
	}
}

E 清楚姐姐的布告规划

背包板子题。注意更新条件。
复杂度： ​

import java.util.*;
public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[]args) throws IOException{
        int t = sc.nextInt();
        while(t-->0){
            int n = sc.nextInt();
            int inf = (int)1e9;
            int []dp = new int [n+3];
            Arrays.fill(dp, inf);
            for(int i=1;i<=n;i++) {
                int x = sc.nextInt();
                for(int j=n;j-x>0;j--) {
                    if(dp[j-x]!=inf && j>=i && j-x<i) dp[j] = Math.min(dp[j], dp[j-x]+1);
                }
                if(x>=i) dp[x] = Math.min(dp[x], 1);
            }
            System.out.println(dp[n]!=inf?dp[n]:-1);   
        }
    }
}

F 竹鼠，宝藏与故事

园方树。详细内容见 Oi-wiki

考虑构造园方树。其中点双的定义是：图中任意两不同点之间都有至少两条点不重复的路径。这意味着你从一个点双的任意 点进入，再从这个点双的任意 点出去，都能拿到该点双内所有的宝藏。

在构造园方树时，方点（即点双）的价值为点双内所有点的价值之和。最后进行一次 ，必定是圆点、方点交替遍历，所以遍历到方点时，由于方点的价值包含了前一个圆点的价值，需减去。

复杂度：

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

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int n,m,maxn=2000005,inf = 0x3f3f3f3f;
	static long ans=0,mod=(int)1e9+7,INF=(long)2e18;
	public static void main(String[]args) throws IOException{
		new Task().main();
	}

	static class Task{
		void main()throws IOException{
			int t=1;
			while(t-->0) {
				solve();
			}
		}
		
		int []dfn = new int [maxn];
		int []low = new int [maxn];
		int []st = new int [maxn];
		int len = 0;
		int cnt = 0, tot = 0;
		long []a = new long[maxn];
		int []x = {0,0,1,-1},y = {1,-1,0,0};
		int start = 0,end = 0;
		boolean []vis = new boolean[maxn];
		int []hd = new int [maxn<<1];
		int []nxt = new int [maxn<<1];
		int []to = new int [maxn<<1];
		int siz = 0;
		
      
		void solve() throws IOException{
			n = sc.nextInt();m = sc.nextInt();
			end = (n-1)*1002 + m-1;
			tot = n*1002 + m;
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					a[i*1002 + j] = sc.nextInt();
				}
			}
			tarjan(0);
			ans=0;
			dfs(0,a[0],0);
			System.out.println(ans);
		}

      
		private void dfs(int u, long sum, int f) {
			// TODO Auto-generated method stub
			if(vis[end]) return;
			vis[u] = true;
			if(u == end) {
				ans = sum;return;
			}
			for(int i = hd[u];i>0;i=nxt[i]) {
				int x = to[i];
				if(vis[x]) continue;
				if(f==0) {
					dfs(x,sum+a[x]-a[u],1);
				}
				else {
					dfs(x,sum,0);
				}
			}
		}

      
		private void tarjan(int u) {
			// TODO Auto-generated method stub
			low[u] = dfn[u] = ++cnt;
			st[++len] = u;
			int x1 = u/1002,y1 = u%1002;
			for(int i=0;i<4;i++) {
				int x2 = x1 + x[i];
				int y2 = y1 + y[i];
				int v = x2*1002 + y2;
				if(x2<0 || x2>=n || y2<0 || y2>=m || a[v] == -1) continue;
				if(dfn[v] == 0) {
					tarjan(v);
					low[u] = Math.min(low[u], low[v]);
					if(low[v] == dfn[u]) {
						++tot;
						for(int x=0;x != v;len--) {
							x = st[len];
							a[tot] += a[x];
							add(tot,x);
						}
						a[tot] += a[u];
						add(tot,u);
					}
				}
				else low[u] = Math.min(low[u], dfn[v]);
			}
		}

		private void add(int x, int y) {
			// TODO Auto-generated method stub
			nxt[++siz] = hd[x]; hd[x] = siz; to[siz] = y;
			nxt[++siz] = hd[y]; hd[y] = siz; to[siz] = x;
		}

	}
}