A 01矩阵 - dp
题意: 给定一个 n * m 的01矩阵, 从(1,1)开始, 只能向右或向下, 问走到(n,m), 且路径上至少p个0,q个1的方案数有多少
根据题目我们很容易就可以定义出一个dp做法
dp[i][j][k1][k2]: 走到(i,j), 有k1个0,k2个1的方案数
(i,j)位置由(i-1,j)和(i,j-1)两个位置转移而来:
(1) map(i,j)==0
dp[i][j][k1][k2]=dp[i-1][j][k1-1][k2]+dp[i][j-1][k1-1][k2] // k1=p处需要特判
(2) map(i,j)==1
dp[i][j][k1][k2]=dp[i-1][j][k1][k2-1]+dp[i][j-1][k1][k2-1] // k2=q处需要特判
最后输出dp[n][m][p][q]即可
但是会超时且超内存,需要优化, n * m = 2.5e5, p * q = 1e10
因为矩阵里只有0和1, 两个点之间的路径长也是固定的, 那么只需要记录1的数量(或者0的数量)即可, 并且根据转移方程, 每个点只需要使用上一行和当前行的数据, 所以可以降下一个维度
所以定义:
dp[j][k]:走到(i,j), 1的数量为k的方案数, 其中i为枚举得到
数组大小[m + 1][n + m]
转移:
(1) map(i,j)==1
dp[j][k] = (dp[j - 1][k - 1] + dp[j][k - 1])
dp[j][0] = 0
(2) map(i,j)==0
dp[j][k] = (dp[j - 1][k] + dp[j][k])
最后统计合法情况, cnt(1) ≥ q, cnt(0)=n+m=1-cnt(1) ≥ p => cnt(1) ≤ n+m-1-p
即 sum{ dp[m][i] | q ≤ i ≤ n+m-1-p}
import java.io.*;
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);
static StreamTokenizer st = new StreamTokenizer(bf);
static int I() throws IOException {
st.nextToken();
return (int) st.nval;
}
static int MOD = 998244353;
static int[][] map = new int[501][501];
static int n, m;
public static void main(String[] args) throws Exception {
n = I();
m = I();
int p = I(), q = I();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
map[i][j] = I();
}
}
long[][] dp = new long[m + 1][n + m];
dp[1][map[1][1]] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == 1 && j == 1) continue;
if (map[i][j] == 1) {
for (int k = i + j - 1; k > 0; k--) {
dp[j][k] = (dp[j - 1][k - 1] + dp[j][k - 1]) % MOD;
}
dp[j][0] = 0;
} else {
for (int k = i + j - 1; k >= 0; k--) {
dp[j][k] = (dp[j - 1][k] + dp[j][k]) % MOD;
}
}
}
}
long ans = 0;
for (int i = q; i <= n + m - 1 - p; i++) {
ans = (dp[m][i] + ans) % MOD;
}
System.out.println(ans);
}
}
B 连分式
初始情况需要特判, 因为a<b时需要退出, b作为最后一个被加进去,a/b不添加, 但是初始a/b下取整为0,这个0是要的
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
int t = I();
while (t-- > 0) {
print(solve());
}
pw.flush();
}
private static void print(List<Integer> ans) {
pw.print(ans.size() - 1 + " ");
for (int i = 0; i < ans.size(); i++) {
pw.print(ans.get(i) + " ");
}
pw.println();
}
static List<Integer> solve() throws IOException {
int a = I(), b = I();
List<Integer> ans = new ArrayList<>();
ans.add(a / b);//先放一个(否则循环里停的时候还要考虑前面是不是0)
int c = a % b;
a = b;
b = c;
while (b != 0) {
if (a >= b) {// a/b = a//b + a%b / b = a//b + 1/(b / a%b)
ans.add(a / b);
c = a % b;
a = b;
b = c;
} else {// a < b
ans.add(b);
break;
}
}
return ans;
}
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 I() throws IOException {
st.nextToken();
return (int) st.nval;
}
}
F 汉诺塔(但4根柱子) - 打表?
(1) 选择A上面的x块, 借助C和D,移动到B
(2) 选择A上面的n-x-1块,借助D,移动到C
(3) 选择A的最后一块, 移动到D
(4) 将C上的n-x-1块,借助A,移动到B
(5) 将B上的x块,借助A和C,移动到D
定义: f(n)为四柱情况下的n块移动最少次数, g(n)为三柱情况下的n块移动最少次数
则有 f(n) = 2 * f(x) + 2 * g(n-x-1) + 1
对于三柱情况:
(1) 选择A上的n-1块, 借助C, 移动到B
(2) 将A的第n块, 移动到C
(3) 将B还是那个的n-1块, 借助A, 移动到C
g(n) = 2 * g(n-1) + 1
可得g的通项公式 g(n) = 2^n - 1
则f公式可化为 f(n) = 2 * f(x) + 2^(n-x) - 1 , 由于是最少操作次数, 需要取min
public static void main(String[] args) throws Exception {
int n = I();
long[] f = new long[n + 1];
for (int i = 1; i <= n; i++) {
long min = Long.MAX_VALUE;
for (int x = 0; x < i; x++) {
min = Math.min(min, 2 * f[x] + (1L << (i - x)) - 1);
}
f[i] = min;
}
System.out.println(Arrays.toString(f));
}
这是一个n^2的做法
打印出前面一些项:
0 1 3 5 9 13 17 25 33 41 49 65 ...
+1 +2 +2 +4 +4 +4 +8 +8 +8 +8 +16
可得规律: 从0开始, 加1,1次 、加2,2次 、加4,3次 、 加8,4次 、 加16,5次...
public static void main(String[] args) throws Exception {
int n = I();
long[] f = new long[n + 1];
long length = 1;//当前轮长度
long cnt = 0;//当前轮计数
long addFact = 1;//当前轮加多少
for (int i = 1; i <= n; i++) {
f[i] = f[i - 1] + addFact;
cnt++;
if (cnt == length) {//每计flag个进入下一轮
length++;
cnt = 0;
addFact *= 2;
}
}
System.out.println(Arrays.toString(f));
}
n有1e4, 加到那么大会爆掉, 需要用 BigInteger 或者 Python
import java.io.*;
import java.math.BigInteger;
public class Main {
static BigInteger[] ans = new BigInteger[10001];
static {
ans[1] = BigInteger.ONE;
int flag = 2, cnt = 0;
BigInteger B2 = BigInteger.valueOf(2);
BigInteger f = B2;
for (int i = 2; i <= 10000; i++) {
ans[i] = ans[i - 1].add(f);
cnt++;
if (cnt == flag) {
flag++;
cnt = 0;
f = f.multiply(B2);
}
}
}
public static void main(String[] args) throws Exception {
int t = I();
while (t-- > 0) {
pw.println(ans[I()]);
}
pw.flush();
}
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 I() throws IOException {
st.nextToken();
return (int) st.nval;
}
}
G 素因子 - 莫队
import java.io.*;
import java.util.*;
public class G素因子 {
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 I() throws IOException {
st.nextToken();
return (int) st.nval;
}
static int N = (int) 5e4;//数组长5e4
static List<Integer>[] factor = new List[N + 1];
static class Q {
int l, r, k;
public Q(int l, int r, int k) {
this.l = l;
this.r = r;
this.k = k;
}
}
static int[] a = new int[N + 1];
static Q[] questions = new Q[N + 1];
static {
Arrays.setAll(factor, k -> new ArrayList<>());
Arrays.setAll(questions, k -> new Q(0, 0, 0));
}
static int n;
public static void main(String[] args) throws Exception {
int t = I();
while (t-- > 0) solve();
pw.flush();
}
static void init() {
for (int i = 1; i <= n; i++) {
factor[i].clear();
for (int j = 2; j <= a[i] / j; j++) {
if (a[i] % j == 0) {
while (a[i] % j == 0) a[i] /= j;
factor[i].add(j);
}
}
if (a[i] != 1) factor[i].add(a[i]);
}
}
static void solve() throws Exception {
n = I();
int q = I();
int size = (int) Math.sqrt(n);
for (int i = 1; i <= n; i++) a[i] = I();
init();
for (int i = 0; i < q; i++) {
questions[i].l = I();
questions[i].r = I();
questions[i].k = i;
}
Arrays.sort(questions, 0, q, (a, b) -> {
if (a.l / size != b.l / size) return a.l - b.l;
return ((a.l / size) & 1) == 0 ? (a.r - b.r) : (b.r - a.r);
});
int L = 1, R = 0;
int[] ans = new int[q];
for (int i = 0; i < q; i++) {
while (L > questions[i].l) Add(--L);
while (R < questions[i].r) Add(++R);
while (L < questions[i].l) Sub(L++);
while (R > questions[i].r) Sub(R--);
ans[questions[i].k] = res;
}
for (int i = 0; i < q; i++) {
pw.println(ans[i]);
}
while (L <= R) Sub(L++);
}
static int res = 0;
static int[] cnt = new int[(int) 1e6 + 1];//a[i]=1e6
static int[] num = new int[(int) 1e6 + 1];
static void Add(int x) {
List<Integer> f = factor[x];
for (int i = 0; i < f.size(); i++) {
int p = f.get(i);
cnt[p]++;
num[cnt[p]]++;
if (num[cnt[p]] == 1) res++;// eg: cnt=1,2,2,3 -> 1,2,2,4
}
}
static void Sub(int x) {
List<Integer> f = factor[x];
for (int i = 0; i < f.size(); i++) {
int p = f.get(i);
num[cnt[p]]--;
if (num[cnt[p]] == 0) res--;// eg: cnt=1,2,2,3 -> 1,2,2
cnt[p]--;
}
}
}
H 炉石游戏 - 这也打表?
(1) 如果 n = 1:
A 第一次摸牌就死了
(2) 如果 k + 1 >= n:
A 摸牌, A扣1点, 打B, B扣k点血(可能死了), B摸牌, B扣1点, B(一定)死了
(3) 其他情况:
可以进行多个回合, 每一回合过后A和B的血量一定相等, .... 莫? B不是先死吗?....怎么我怎么手动模拟都是A先死
t = int(input())
for _ in range(t):
n, k = map(int, input().split())
if n == 1 or k + 1 < n:
print("freesin")
else:
print("pllj")
J LRU缓存 - 二分+数据结构实现
import java.io.*;
import java.util.*;
public class Main {
static class LRUCache {
//思路:双向链表
//在put和get时,把节点1插入到头部,淘汰时删除尾部节点
static class Node {
Node prev;
Node next;
int key;
int value;
public Node(Node prev, Node next, int key, int value) {
this.prev = prev;
this.next = next;
this.key = key;
this.value = value;
}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
public Node() {
}
}
static class DoubleLinkedList {
Node head;
Node tail;
public DoubleLinkedList() {
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
}
public void addFirst(Node node) {
Node first = head.next;
node.next = first;
node.prev = head;
first.prev = node;
head.next = node;
}
public void remove(Node node) {
Node p = node.prev;
Node n = node.next;
p.next = n;
n.prev = p;
}
public Node removeLast() {
Node delete = tail.prev;
remove(delete);
return delete;
}
}
Map<Integer, Node> map = new HashMap<>();
DoubleLinkedList list = new DoubleLinkedList();
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node node = map.get(key);
list.remove(node);
list.addFirst(node);
return node.value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {//更新
Node node = map.get(key);
node.value = value;
} else {//新增
Node node = new Node(key, value);
list.addFirst(node);
map.put(key, node);
if (map.size() > capacity) {
Node removed = list.removeLast();
map.remove(removed.key);
}
}
}
}
static int[] a;
static int n, k;
public static void main(String[] args) throws Exception {
n = I();
k = I();
a = new int[n];
HashSet<Integer> set = new HashSet<>();
int t = 0;
for (int i = 0; i < n; i++) {
a[i] = I();
if (!set.add(a[i])) t++;
}
if (t < k) {// 全部缓存也不够k
System.out.println("cbddl");
return;
}
int left = 0, right = n;
while (left + 1 != right) {
int mid = (left + right) >>> 1;
if (check(mid)) {
right = mid;
} else {
left = mid;
}
}
System.out.println(right);
}
static boolean check(int x) { // 模拟, 检查容量为x时是否有k次缓存命中
LRUCache cache = new LRUCache(x);
int cnt = 0;
for (int i = 0; i < n; i++) {
int t = cache.get(a[i]);
if (t == -1) {
cache.put(a[i], 1);
} else {
cnt++;
if (cnt == k) return true;
}
}
return false;
}
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);
static StreamTokenizer st = new StreamTokenizer(bf);
static int I() throws IOException {
st.nextToken();
return (int) st.nval;
}
}
K 塔 - 平方和公式
t =int(input())
for _ in range(t):
n,m=map(int,input().split())
print(m * n*(n+1)*(2*n+1)//6 )
L 下雨 - 区间并集
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
int n = I();
int[][] X = new int[n][2];
for (int i = 0; i < n; i++) {
int x1 = I(), y1 = I(), x2 = I(), y2 = I();
X[i] = new int[]{x1, x2};
}
Arrays.sort(X, (a, b) -> {// 对区间排序
if (a[0] != b[0]) return a[0] - b[0];
return a[1] - b[1];
});
long ans = 0;
long left = X[0][0], right = X[0][1];
for (int i = 1; i < n; i++) {
long L = X[i][0], R = X[i][1];
if (L > right) {// 两段区间分离
ans += right - left;
left = L;
}
right = Math.max(right, R);
}
ans += right - left;
System.out.println(ans);
}
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);
static StreamTokenizer st = new StreamTokenizer(bf);
static int I() throws IOException {
st.nextToken();
return (int) st.nval;
}
}
京公网安备 11010502036488号