! 某些代码为提交区的转载
A 互质对数位和 - 容斥原理
import java.util.*;
public class Main {
/*
求 sum{ sum{ F(j) | j=1->i } | i=1->n }
其中F(j)表示j的数位和
*/
/**
贡献法, 计算i的贡献, 即F[i] * 数量
数量 = i后面与i互质的数的个数 = (n-i) - i后面不与i互质的数个数
<p>
i后面不与i互质的数个数 可以 枚举i的质因子集
假设枚举出的质因子集相乘为mul, 则 i~n上有 (n-i) / mul 个mul的倍数, 即有 (n-i) / mul 个数与i不互质
但是枚举出来的是有重叠的, 需要使用容斥原理, 奇数个因子则计入"不互质", 偶数个因子则从"不互质"中减去
*/
public static void main(String[] args) {
long n = new Scanner(System.in).nextLong();
init(n);// 预处理
//对于每一个i, 找[i+1,n]里有多少个个数和它互质
long ans = 1;// f(1)
for (int i = 1; i < n; i++) {
int m = p[i].size();// i的因数个数
long cnt = 0; // 与i不互质的数的个数
for (int j = 1; j < (1 << m); j++) {// 枚举因数集
long mul = 1; //当前枚举状态的所有质因数的乘积
for (int k = 0; k < m; k++) {
if ((j & (1 << k)) != 0) mul *= p[i].get(k);
}
long now = (n - i) / mul; //mul的倍数个数
int t = (Integer.bitCount(j) % 2 == 1) ? 1 : -1; //容斥,奇加偶减
cnt += t * now;
}
ans += f[i] * (n - i - cnt);
}
System.out.println(ans);
}
static int N = 100010;
static long[] f = new long[N]; //数位和
static List<Integer> prime = new ArrayList<>(); //素数
static List<Integer>[] p = new List[N]; // p[i]:i的质因子
static int F(int x) {
int sum = 0;
while (x != 0) {
sum += x % 10;
x /= 10;
}
return sum;
}
static void init(long n) {
// 数位和
for (int i = 1; i <= n; i++) f[i] = F(i);
Arrays.setAll(p, i -> new ArrayList<>());
//素数筛
boolean[] isCom = new boolean[N];
for (int i = 2; i < N; i++) {
if (!isCom[i]) prime.add(i);
for (int j = 0; j < prime.size(); j++) {
int v = prime.get(j);
if (i * v >= N) break;
isCom[i * v] = true;
if (i % v == 0) break;
}
}
//质因子筛
for (int i = 2; i <= n; i++) {
int x = i;
for (int j = 0; j < prime.size(); j++) {
int v = prime.get(j);
if (v * v > x) break;
if (x % v == 0) {
p[i].add(v);
while (x % v == 0) x /= v;
}
}
if (x != 1) p[i].add(x);
}
}
}
B 分苹果 - 签到
t = int(input())
for _ in range(t):
n,m=map(int,input().split())
if (n < m*(m+1)//2):
print("impossible")
else:
print("possible")
C 区间选择 - 贪心
题意: 给定n个区间[L,R],从中选择k个区间I[1],I[2]...I[k], 交集长为x, 最大化min(k,x)
交集: 如果∀i∈[1,k]都有a∈I[i],则a∈区间交集
排序贪心:
按L升序, 假设当前要选择第i条线段 [ L , R ] (下图中 红色线段)
前面已选择的线段 左端点<L, 存储在队列中按右端点进行排序 (下图中 黑色线段为已选择的)
此时重叠区间为[L,min{r}] (下图中 红-深绿区间)
要最大化min(k,x), 如果此时 x < k, 可以选择抛弃一些线段, 优先抛弃的是已选择的线段中r最小的, 这样min{ r }可以向右不断增大
直到k<=x时停止抛出线段, 则选择第i条线段的最大化结果为k
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
I();
int m = I();
int[][] list = new int[m][2];
for (int i = 0; i < m; i++) list[i] = new int[]{I(), I()};
Arrays.sort(list, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);//线段按照左端点优先从小到大排序,右端点从小到大排序
Queue<Integer> queue = new PriorityQueue<>();//选择的线段, 按右端点从小到大排序
int ans = 0;
for (int i = 0; i < m; i++) {
queue.offer(list[i][1]);//选择第i条线段
while (!queue.isEmpty()) {
int cnt = queue.peek() - list[i][0] + 1; // [L,R]: L为当前枚举的线段左端点, R为选择的线段的右端点最小值
if (queue.size() <= cnt) break; // tol=q.size, 保证tol是小值
// 如果tol>cnt, 说明选择了一些贡献很小的线段
// L是固定/递增的, 选择的线段按R排序, R小的不再选择,应该抛出, 否则随着L递增,cnt会越来越小
queue.poll();
}
ans = Math.max(ans, queue.size());
}
System.out.println(ans);
}
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in), 65535));
static int I() throws IOException {
st.nextToken();
return (int) st.nval;
}
}
D 子数数位和 - 后缀自动机
// Java魅力时刻: 这代码改Java,测试样例n=3跑了1秒多, 全TLE了
#include <iostream>
#include <vector>
using namespace std;
const int N = 2000010;
const int mod = 1e9 + 7;
struct SAM {
struct Node {
int fa, len;
int ch[10];
} node[N];
int q[N];
int tr[N][26], idx = 1;
int tot = 1;
int pos[N];
int ch[N], fa[N];
void insert() {
string s;
cin >> s;
int p = 1;
for (int i = 0; s[i]; i++) {
int u = s[i] - '0';
if (tr[p][u] == 0) {
tr[p][u] = ++idx;
fa[idx] = p;
ch[idx] = u;
}
p = tr[p][u];
}
}
int extend(int c, int last) {
int p = last, np = ++tot;
node[np].len = node[p].len + 1;
for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
if (!p) node[np].fa = 1;
else {
int q = node[p].ch[c];
if (node[q].len == node[p].len + 1) node[np].fa = q;
else {
int nq = ++tot;
node[nq] = node[q], node[nq].len = node[p].len + 1;
node[q].fa = node[np].fa = nq;
for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
}
}
return np;
}
void build() {
int tt = -1, hh = 0;
for (int i = 0; i < 10; i++)
if (tr[1][i]) q[++tt] = tr[1][i];
pos[1] = 1;
while (hh <= tt) {
int t = q[hh++];
pos[t] = extend(ch[t], pos[fa[t]]);
for (int i = 0; i < 10; i++)
if (tr[t][i]) q[++tt] = tr[t][i];
}
}
int f[N], g[N];
int din[N];
int solve() {
int res = 0;
for (int i = 1; i <= tot; i++) {
for (int j = 0; j < 10; j++) {
din[node[i].ch[j]]++;
}
}
g[1] = 1;
int tt = -1, hh = 0;
q[++tt] = 1;
while (hh <= tt) {
int t = q[hh++];
(res += f[t]) %= mod;
for (int j = 0; j < 10; j++) {
int v = node[t].ch[j];
if (!v) continue;
(g[v] += g[t]) %= mod;
(f[v] += 10ll * f[t] % mod + 1ll * g[t] * j % mod) %= mod;
if (!--din[v]) q[++tt] = v;
}
}
return res;
}
} sam;
int main() {
int n;
cin >> n;
while (n--) sam.insert();
sam.build();
cout << sam.solve();
return 0;
}
E 颜色序列 - 前缀异或
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashMap;
public class Main {
/*
长度为n的数组, c[i]表示第i个位置的颜色, 求有多少个子数组满足以下条件:
子数组内各颜色的出现次数为偶数
c[i]<=20
*/
/**
[l,r]满足要求
<=> [l,r]的异或和 = 0
<=> [1,r]的异或和 ^ [1,l-1]的异或和 = 0
<=> [1,r]的异或和 = [1,l-1]的异或和
所以求前缀异或和数组, 然后用哈希表滚动记录异或和, 每滑到一个位置, 直接取哈希表中的计数即可
*/
public static void main(String[] args) throws Exception {
int n = I();
int[] c = new int[n + 1];
for (int i = 1; i <= n; i++) {
c[i] = I();
}
int[] preFix = new int[n + 1];
for (int i = 1; i <= n; i++) {
preFix[i] = preFix[i - 1] ^ (1 << c[i]);
}
HashMap<Integer, Integer> preCnt = new HashMap<>();
preCnt.put(0, 1);
long ans = 0;
for (int i = 1; i <= n; i++) {
int cnt = preCnt.getOrDefault(preFix[i], 0);
ans += cnt;
preCnt.put(preFix[i], cnt + 1);
}
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;
}
}
F 魔术数字 - dfs
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
static BigInteger[] cost = new BigInteger[10];
static BigInteger[] B = new BigInteger[11];
static {
for (int i = 0; i < B.length; i++) {
B[i] = BigInteger.valueOf(i);
}
int[] l = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
for (int i = 0; i <= 9; i++) {
cost[i] = B[l[i]];
}
}
static BigInteger ans = BigInteger.valueOf(-1);
static BigInteger n;
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
n = new BigInteger(sc.next());
for (int first = 1; first <= 9; first++) {//枚举首位
dfs(1, B[first], cost[first]);
}
System.out.println(ans);
}
/**
第i位数, 当前为num, 使用了consume个火柴
*/
static void dfs(int i, BigInteger num, BigInteger consume) {
int compareTo = consume.compareTo(n);
if (compareTo == 0) {
ans = ans.max(num);
return;
}
if (compareTo > 0) return;
// 枚举下一位
for (int d = 0; d <= 9; d++) {
BigInteger newNum = num.multiply(B[10]).add(B[d]);
if (newNum.mod(BigInteger.valueOf(i + 1)).equals(B[0])) {
dfs(i + 1, newNum, consume.add(cost[d]));
}
}
}
}
G 子集选择 - 组合数学
n个元素, m个位置
对于任意一个元素来说, 它都有m个位置可选(题目说m个子集是有序的), 也可以选择不放, 所以一共m+1个选择
所以输出 (m+1)^n % MOD 即可
MOD = 998244353
n,m=map(int,input().split()) # n个元素, m个位置
print(pow(m + 1, n, MOD)) # 每个数都有m个位置可以选择, 并且也可以选择不放, 所以一共m+1个选择
H 序列操作 - 线段树维护区间最小值
package 算法.进阶数据结构算法.树.线段树;
import java.io.*;
public class ICPC_序列 {
/*
给定长度为n的数组a
操作1: x,y, 将a[x]修改为y
操作2: x, 查询包含a[x]的子数组个数, 子数组需满足a[x]为子数组最小值
*/
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;
}
/**
线段树 维护区间最小值
操作1: 单点修改
操作2: 查询[1,x]中第一个比x小的数位置,查询[x,n]中第一个比x小的数位置
*/
public static void main(String[] args) throws IOException {
int n = I(), q = I();
int[] a = new int[n + 1];
for (int i = 1; i <= n; i++) a[i] = I();
Tree tree = new Tree(n, a);//线段树区间最小值
for (int i = 0; i < q; i++) {
int type = I();
if (type == 1) {
int x = I(), y = I();
tree.update(1, 1, n, x, y);
a[x] = y;
} else {
int x = I();
int left = tree.queryLeft(x);
int right = tree.queryRight(x);
pw.println((x - left + 1L) * (right - x + 1L));
}
}
pw.flush();
pw.close();
}
static class Tree {
int[] tree = new int[100010 << 2];
int n;
int[] a;
public Tree(int n, int[] a) {
this.a = a;
this.n = n;
build(1, 1, n);
}
void build(int rt, int l, int r) {
if (l == r) {
tree[rt] = a[l];
return;
}
int mid = (l + r) >>> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
tree[rt] = Math.min(tree[rt << 1], tree[rt << 1 | 1]);
}
/**
单点修改
*/
void update(int rt, int l, int r, int x, int y) {
if (l == r) {
tree[rt] = y;
return;
}
int mid = (l + r) >>> 1;
if (x <= mid) {
update(rt << 1, l, mid, x, y);
} else {
update(rt << 1 | 1, mid + 1, r, x, y);
}
tree[rt] = Math.min(tree[rt << 1], tree[rt << 1 | 1]);
}
/**
区间最小值查询
*/
int query(int rt, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return tree[rt];
}
int mid = (l + r) >>> 1;
int ans = (int) (1e9 + 10);
if (L <= mid) ans = Math.min(ans, query(rt << 1, l, mid, L, R));
if (R > mid) ans = Math.min(ans, query(rt << 1 | 1, mid + 1, r, L, R));
return ans;
}
public int queryLeft(int x) {
int l = 0, r = x;//r:大于等于x
while (l + 1 != r) {
int mid = (l + r) >>> 1;
if (query(1, 1, n, mid, x) >= a[x]) r = mid;
else l = mid;
}
return r;
}
public int queryRight(int x) {
int l = x, r = n + 1;//l:大于等于x
while (l + 1 != r) {
int mid = (l + r) >> 1;
if (query(1, 1, n, x, mid) >= a[x]) l = mid;
else r = mid;
}
return l;
}
}
}
I 对角线排列 - 算
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong(), x = sc.nextLong(), y = sc.nextLong();
long line = x + y; // 在第几个对角线上
if (line < n) { // 上半区
long cnt = line * (line + 1) / 2; // 左上区的个数
System.out.println(cnt + x); // x: 这条线上方的个数
} else { // 下半区
long cnt = (2 * n - line - 2) * (2 * n - line - 1) / 2; // 右下区的个数
long last = n * n - 1;// 最后一个数
System.out.println(last - cnt - (n - x - 1)); // n - x - 1: 这条线下方的个数
}
}
}
J 剪纸博弈 - sg函数
import java.util.Arrays;
import java.util.BitSet;
import java.util.Scanner;
public class Main {
/*
n*m的纸, 每次可选择一条水平或竖直的先进行裁剪
如果见出的两边纸有1*1的,则输了
给出n,m,Alice先手,问谁会赢
*/
public static void main(String[] args) {
for (int[] s : sg) Arrays.fill(s, -1);
sg[1][2] = sg[2][1] = sg[3][1] = sg[1][3] = 0;
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int n = sc.nextInt(), m = sc.nextInt();
dfs(n, m);
System.out.println(sg[n][m] != 0 ? "Alice" : "Bob");
}
}
static int[][] sg = new int[200][200];
/**
(n,m)的情况下,先手能不能赢
*/
static void dfs(int n, int m) {
if (sg[n][m] != -1) return;
BitSet set = new BitSet();
for (int i = 1; i < n; i++) {
if (m == 1 && (i == 1 || i == n - 1)) continue;
dfs(i, m);
dfs(n - i, m);
set.set(sg[i][m] ^ sg[n - i][m]);// 如果一边输, 在另一边先后手反转, 所以结果不同则为赢
}
for (int i = 1; i < m; i++) {
if (n == 1 && (i == 1 || i == m - 1)) continue;
dfs(n, i);
dfs(n, m - i);
set.set(sg[n][i] ^ sg[n][m - i]);
}
sg[n][m] = set.nextClearBit(0);// mex
}
}
K 背包旅行 - 最短路径 + 二分
import java.io.*;
import java.util.*;
public class Main {
/*
n个城市, m个双向边, 边权为1
q个询问, 从x到y, 最大预算为B
如果背有k个包袱, 从 x->a1->a2->...->y 一共经过t条边, 花费为 k+k^2+k^3+...+k^t
*/
public static void main(String[] args) throws IOException {
int n = I(), m = I();
int[][] graph = new int[n + 1][n + 1];
int inf = 0x3f3f3f3f;
for (int[] g : graph) Arrays.fill(g, inf);
for (int i = 0; i < m; i++) {
int u = I(), v = I();
graph[u][v] = graph[v][u] = 1;
}
// Floyd求最短路
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (graph[i][k] != inf && graph[k][j] != inf) {
graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
}
//处理询问
int q = I();
for (int i = 0; i < q; i++) {
int x = I(), y = I(), B = I();
int t = graph[x][y];// 背1个, 需要t的预算
long ans = cal(t, B);
pw.println(ans);
}
pw.flush();
pw.close();
}
static long cal(int t, int B) {
if (B < t) return 0;
if (B == t) return 1;
if (t == 1) return B;
// k(k^t-1)/(k-1) <= B
int left = 1, right = B + 1;//left:√, right:×
while (left + 1 != right) {
int k = (left + right) >>> 1;
if (sum(k, t) > B) {
right = k;
} else {
left = k;
}
}
return left;
}
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 long sum(int k, int t) {
// k + k^2 + k^3 + ... + k^t
// = k(k^t-1)/(k-1)
return (long) (k * (Math.pow(k, t) - 1) / (k - 1));
}
}
L N皇后 - 状压dp
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
n = I();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) map[i][j] = I();
}
for (int i = 0; i < (1 << n); i++) { //i: 表示一行的可选状态
int cnt = Integer.bitCount(i); // 有多少个1
rp[cnt]++; // rp[x]: 有x个1的状态个数
status[cnt][rp[cnt]] = i; // s[x][k] = i 表示有x个1的第k个状态为i
}
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// 尝试在(i,j)上放
if (map[i][j] == 1) continue; //不可选
for (int k = 1; k <= rp[i - 1]; k++) {
int pre = status[i - 1][k]; //前面i-1行时的状态
if (((pre >> (j - 1)) & 1) != 0) continue; // j这一列有了
int cur = pre | (1 << (j - 1)); // pre + 第j位 -> cur
dp[i][cur] = (dp[i][cur] + dp[i - 1][pre]) % MOD;
}
}
}
long ans = dp[n][(1 << n) - 1];
// n个皇后可以调换顺序, A(n,n)=n!
for (int i = 1; i <= n; i++) ans = ans * i % MOD;
System.out.println(ans);
}
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in), 65535));
static int I() throws IOException {
st.nextToken();
return (int) st.nval;
}
static int MOD = 1000000007;
static int N = 21, M = (1 << 20) + 1;
static int n;
static int[][] map = new int[N][N];// 图, 0为空位
static int[] rp = new int[N];// rp[x]: 有x个1的状态个数
static int[][] status = new int[N][M];// s[x][k] = i 表示有x个1的第k个状态为i
static int[][] dp = new int[N][M]; // 前n行 m个状态 里有多少个合法情况, dp[i][cur] = sum{ dp[i - 1][pre] }
}
M 动物园 - 签到
s1=input()
s2=input()
print(s1+s2)
京公网安备 11010502036488号