又是拉胯的一天
/** * 第二题 * 给定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);
}
}
京公网安备 11010502036488号