又是拉胯的一天
/** * 第二题 * 给定n头奶牛，有 m 个条件，满足这 m 个条件的奶牛是优质奶牛。 * 然后就是给定 m 个条件，对于每个条件给 k 个区间，在闭区间内是满足条件的奶牛 * 然后就是问有多少个奶牛是优质的，并输出奶牛的序列号。 * * 大概思路就是对于每个条件，做一个差分，得出每个奶牛满足条件的个数，达到m个就是优质的了 * 这里用了差分区间做法，和输入流加速，避免超时。 * 然后在差分时还要去除重复的区间，否则就会把一个条件当做两个条件。 * * 如果不懂差分的做法，搜索差分区间 * 只需要将区间的第一位加上区间的加数，区间的最后一位减去区间的加数，就能做到对区间的更改。 * * 拉胯。。。结束前十分钟才找到，第三题也没时间找bug了。。。 */ import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.StreamTokenizer; import java.util.Arrays; import java.util.Scanner; public class Main { static StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { int T = nextInt(); Node ns[] = new Node[1005]; int arr[] = new int[1005]; while (T-- > 0) { int n = nextInt(); int m = nextInt(); for (int i = 0; i < m; i++) { int t = nextInt(); for (int j = 0; j < t; j++) { ns[j] = new Node(nextInt(),nextInt()); } Arrays.sort(ns, 0, t); int last = 0; for (int j = 0; j < t; j++) { Node nd = ns[j]; if (nd.l > last) { arr[nd.l]++; arr[nd.r + 1]--; last = nd.r; } else { if (last < nd.r) { arr[last]++; arr[nd.r + 1]--; last = nd.r; } } } } for (int i = 1; i < n; i++) { arr[i] = arr[i] + arr[i - 1]; } StringBuffer s = new StringBuffer(); int cont = 0; for (int i = 0; i < n+1; i++) { if (arr[i] >= m) { s.append(i + " "); cont++; } arr[i] = 0; } System.out.println(cont); System.out.println(s.toString().substring(0, s.length()-1)); } } static double next() throws IOException { st.nextToken(); return st.nval; } static int nextInt() throws IOException { st.nextToken(); return (int) st.nval; } } class Node implements Comparable<Node> { int l; int r; public Node(int l, int r) { this.l = l; this.r = r; } @Override public int compareTo(Node o) { return this.l - o.l == 0 ? o.r - this.r : this.l - o.l; } } /** * 第三题 * 这题名叫走楼梯，和普通见过走楼梯不同的是，不能与前两次走的楼梯个数相同。。。（大概是强迫症患者） * 一共有n个楼梯，每次可以走1-m个楼梯，m<7 * 问走的方法数模于1e9+7 * * 仍然是dp的做法，就是扩展到了三维，对于这个三维，表示dp[当前位置][前一次走的楼梯][前前一次走的楼梯] * 就是遍历前一次的所有做法，找到三次都不一样的走法加起来。 * dp[i + j][j][k] += dp[i][k][l]; * 本次走j 前一次走k，在前一次走l * 这样将 n位置的所有前两次走法加起来就是答案 * * 本题又是拉胯的一题。。结束十分钟找到bug */ import java.util.Scanner; public class Main2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); long dp[][][] = new long[n + 8][8][8]; long mod = 1000000007; for (int k = 1; k <= m; k++) { dp[k][k][0] = 1; } for (int i = 0; i < n; i++) { for (int j = 1; j <= m; j++) { for (int k = 1; k <= m; k++) for (int l = 0; l <= m; l++) { if(l!=j&&l!=k&&j!=k) { dp[i + j][j][k] += dp[i][k][l]; } } } } long ans = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { ans += dp[n][i][j]; } } System.out.println(ans % mod); } }