[知识总结] 【ACM】ACM宝典
作者:CC下载站 日期:2021-05-25 08:53:00 浏览:71 分类:编程开发
本文用于记录ACM比赛时常用的算法和模板
全排列
public class Main {
public static void main(String[] args) {
perm(new int[]{1,2,3},0,2);
}
public static void perm(int[] array,int start,int end) {
if(start==end) {
System.out.println(Arrays.toString(array));
} else {
for (int i = start; i <= end; i++) {
//1,2,3的全排列这块相当于将其中一个提了出来,下次递归从start+1开始
swap(array,start,i);
perm(array,start+1,end);
//这块是复原数组,为了保证下次另外的同级递归使用数组不会出错
//这块可以通过树来理解,每次回退一步操作,交换回去
swap(array,start,i);
}
}
}
public static void swap(int[] array,int i,int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
快速幂
public static long fastPow(long k,long e,long mod) {
long ans=1;
while(k>=1)
{
if ((k&1)>=1) {
ans*=e%mod;
}
e*=e%mod;
k>>=1;
}
return ans;
}
快速输入输出
//第一种
public class Main {
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String[] init = br.readLine().split(" ");
int n = Integer.valueOf(init[0]);
long m = Long.valueOf(init[1]);
long q = Long.valueOf(init[2]);
long[] x = new long[n+1];
String[] xs = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
x[i+1] = Long.valueOf(xs[i]);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < q; i++) {
String s2[]=br.readLine().split(" ");
int k = Integer.parseInt(s2[1]);
long length = p * x[k];
if ((length/m)%2 == 1) {
sb.append(m - (length%m));
}else {
sb.append(length%m);
}
sb.append('\n');
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
}
//第二种
public class FastScanner {
public static void main(String[] args) {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
try {
st.nextToken();
int n = (int) st.nval;
System.out.println(n);
} catch (IOException e) {
e.printStackTrace();
}
}
}
格式化输出
public class FormatDemo {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Hello World");
double x=-10000.0/3.0;
double y=5000.0/3.0;
System.out.println(x);
System.out.printf("%,10.2f\r\n",x);
System.out.printf("%-,10.2f\r\n",x);
System.out.printf("%+(,10.2f %2$.3f\r\n",x,y);
System.out.printf("%+(,10.2f %1$.3f %2$.3f %<f %<.3f\r\n",x,y);
}
}
并查集
public class DisjointSet {
public static int n = 6;
public static void main(String[] args) {
int[] parent = new int[n];
int[] rank = new int[n];
int[][] edges = {{0,1}, {1,2}, {1,3}, {3,4},{2,5}, {4,5}};
init(parent);
for (int i = 0; i < edges.length; i++) {
int x = edges[i][0];
int y = edges[i][1];
if (!union_vertices(x, y, parent, rank)) {
System.out.println("Cycle detected!");
return;
}
}
System.out.println("No cycles found.");
}
public static void init(int parent[]) {
for (int i = 0; i < n; i++) {
parent[i] = -1;
}
}
public static int find_root(int x, int[] parent) {
int x_root = x;
while (parent[x_root] != -1) {
x_root = parent[x_root];
}
return x_root;
}
public static boolean union_vertices(int x, int y, int[] parent, int[] rank) {
int x_root = find_root(x, parent);
int y_root = find_root(y, parent);
if (x_root == y_root) {
return false;
}
if (rank[x_root] > rank[y_root]) {
parent[y_root] = x_root;
}else if (rank[x_root] < rank[y_root]){
parent[x_root] = y_root;
}else {
parent[x_root] = y_root;
rank[y_root]++;
}
return true;
}
}
01背包模板
public class Knapsack {
public static void main(String[] args) {
int[][] plan = new int[6][21];
int[] w = {0,2,4,8,10,13};
int[] v = {0,3,5,9,12,15};
int v1,v2;
for(int id=1;id<6;id++) {
for(int C=1;C<21;C++) {
if(w[id]>C) plan[id][C]=plan[id-1][C];
else {
v1 = plan[id-1][C-w[id]]+v[id];
v2 = plan[id-1][C];
plan[id][C] = v1 >=v2 ?v1:v2;
}
}
}
//输出背包
for(int i=0;i<6;i++) {
for(int j=0;j<21;j++) {
if (j > 9 && i < 3) {
System.out.print(plan[i][j]+" ");
}else {
System.out.print(plan[i][j]+" ");
}
}
System.out.println();
}
}
}
区间调度dp模板
//根据时间做任务,选任务会占据一定的时间
public class S {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
State[] list = new State[n];
for(int i = 0; i < n; i++) {
//开始时间,得分,等待时间
list[i] = new State(sc.nextInt(), sc.nextInt(), sc.nextInt());
}
Arrays.sort(list);
int[] dp = new int[2000001]; //20000001分钟
int index = 0;
for (int i = 0; i < 2000000 ; i++) {
while (index < n && list[index].m == i) {
dp[i+list[index].w] = Math.max(dp[i+list[index].w], dp[i]+list[index].f);
index++;
}
dp[i+1] = Math.max(dp[i + 1], dp[i]);
}
System.out.println(dp[2000000]);
}
static class State implements Comparable<State> {
public int m,f,w;
public State(int a, int b, int c){
m=a;
f=b;
w=c;
}
@Override
public int compareTo(State s) {
return m - s.m;
}
}
}
二分
- 当
check(mid) == true
调整的是l
时:计算mid
的方式应该为mid = l + r + 1 >> 1
:
while (l < r) {
long mid = l + r + 1 >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
- 当
check(mid) == true
调整的是r
时:计算mid
的方式应该为mid = l + r >> 1
:
while (l < r) {
long mid = l + r >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
龟速乘法(处理直接加会爆longlong)
快速乘法,采用了倍增思想:
long mul(long a, long k) {
long ans = 0;
while (k > 0) {
if ((k & 1) == 1) ans += a;
k >>= 1;
a += a;
}
return ans;
}
快速幂
static long mpow(long a, long b) {
long res = 1;
while (b > 0) {
if ((b & 1) == 1) {
res *= a;
}
a *= a;
b >>= 1;
}
return res;
}
区间dp
for (int l = 1; l <= n; l++) {//枚举长度
for (int i = 1; i + l <= n + 1; i++) {//枚举起点,
int j = i + l - 1;
for (int k = i; k < j; k++) {//枚举分割点,更新小区间最优解
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + something);
}
}
}
Java快读,快输出
StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
sc.nextToken();
int t = (int)sc.nval;
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
out.println();
out.flush();
质数筛(埃及筛)
int N = (int) 1e7;
boolean[] isPrime = new boolean[N + 5];
Arrays.fill(isPrime, true);
isPrime[1] = false;
for (int i = 2; i <= N; i++) {
if (isPrime[i]) {
for (int j = 2; j * i <= N; j++) {
isPrime[i * j] = false;
}
}
}
阶乘因子个数(m!中含有多少k因子)
static long numberOfFactorials(long m, long k) {
long ret = 0;
while (m > 0) {
ret += m / k;
m /= k;
}
return ret;
}
快排
public static void quick_sort(int[] nums, int l, int r) {
if (l >= r) {
return;
}
int x = nums[l], i = l - 1, j = r + 1;
while (i < j) {
do i++; while (nums[i] < x);
do j--; while (nums[j] > x);
if (i < j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
quick_sort(nums, l, j);
quick_sort(nums, j + 1, r);
}
弗洛伊德算法--构造两点最短路径(全员)
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
狄克斯特拉算法
import java.util.Arrays;
import java.util.PriorityQueue;
public class 最短路径 {
static int[] d = new int[2100];
static boolean[] vis = new boolean[2100];
static PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> d[o1] - d[o2]);
static int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
static int lcm(int x, int y) {
return x * y / gcd(x, y);
}
static void dijkstra() {
Arrays.fill(d, Integer.MAX_VALUE);
d[1] = 0;
vis[1] = true;
for (int i = 2; i <= 22; i++) {
d[i] = lcm(1, i);
heap.add(i);
}
while (!heap.isEmpty()) {
int v = heap.poll();
if (vis[v]) continue;
vis[v] = true;
if (v == 2021) break;
for (int i = Math.max(1, v - 21); i <= Math.min(2021, v + 21); i++) {
if (!vis[i]) {
d[i] = Math.min(d[i], d[v] + lcm(v, i));
heap.add(i);
}
}
}
System.out.println(d[2021]);
}
public static void main(String[] args) {
dijkstra();
}
}
猜你还喜欢
- 03-29 [编程相关] Winform窗体圆角以及描边完美解决方案
- 03-29 [前端问题] has been blocked by CORS policy跨域问题解决
- 03-29 [编程相关] GitHub Actions 入门教程
- 03-29 [编程探讨] CSS Grid 网格布局教程
- 10-12 [编程相关] python实现文件夹所有文件编码从GBK转为UTF8
- 10-11 [编程算法] opencv之霍夫变换:圆
- 10-11 [编程算法] OpenCV Camshift算法+目标跟踪源码
- 10-11 [Python] python 创建 Telnet 客户端
- 10-11 [编程相关] Python 基于 Yolov8 + CPU 实现物体检测
- 03-15 [脚本工具] 使用go语言开发自动化脚本 - 一键定场、抢购、预约、捡漏
- 01-08 [编程技术] 秒杀面试官系列 - Redis zset底层是怎么实现的
- 01-05 [编程技术] 《Redis设计与实现》pdf
取消回复欢迎 你 发表评论:
- 精品推荐!
-
- 最新文章
- 热门文章
- 热评文章
[书籍] 【帛书版】合集
[老照片] 一万张珍贵历史老照片【jpg 40.4GB】
[素材] 2024新年春节烟花素材合集【PSD格式+PNG格式】
[美剧] 《生活大爆炸》S01-S12季合集 【1080P 蓝光原盘REMUX】 DTS-HD.MA.5.1 【外挂简英双语字幕】 742.8G
[电影] 茶馆(1982)蓝光原盘REMUX 内封简繁英.简中简繁四字幕【33.9G】本片根据老舍同名原著改编
[电视剧] 永夜星河(2024)【4K 2160P 杜比音效】国语中字【全32集完结】爱情,古装 又名 :黑莲花攻略手册
[影视合集] 《霍比特人》三部曲加长版合集 【4K 蓝光 HDR】 TrueHD.7.1 国语次世代+导评 【国配简繁英特效+导评中字五字幕】134G
[课程] 2024邓诚高三数学视频课【MP4 12.2GB】
[电视剧] 宿敌(2024)【完结】【4K / 臻彩视听 / 杜比音效】【廖凡/朱珠】【17.8G】
[影视合集] 【鹿鼎记 7个版本合集】【1984-2020】【4K、1080P、720P】【中文字幕】【278.5G】
[书籍] 彭子益医书合集 [PDF/DOC]
[游戏] 《黑神话悟空》免安装学习版【全dlc整合完整版】+Steam游戏解锁+游戏修改工具!
[动画] 2002《火影忍者》720集全【4K典藏版】+11部剧场版+OVA+漫画 内嵌简日字幕
[剧集] 《斯巴达克斯》1-4季合集 无删减版 1080P 内嵌简英特效字幕
[电影] 《变形金刚系列》七部合集 [4K HDR 蓝光] 国英双语音轨 [内封精品特效字幕]【典藏版】235G
[CG剧情] 《黑神话:悟空》158分钟CG完整剧情合集 4K120帧最高画质
[动画] 收藏版:1996-2024年名侦探柯南全系列1080P,含国配、日配双语版+26部剧场作品
[游戏] 黑神话悟空离线完整版+修改器
[电影] 《神奇动物在哪里三部合集》 4K REMUX原盘 [杜比视界] [国英双语音轨] 特效字幕 [171.1G]
[动画] 西游记 (1999) 动画版 4K 全52集 高清修复版 童年回忆
[电影] 《黄飞鸿》全系列合集
[Android] 开罗游戏 ▎像素风格的模拟经营的游戏厂商安卓游戏大合集
[游戏合集] 要战便战 v0.9.107 免安装绿色中文版
[电影] 【珍藏版】20世纪电影合集从1922年到1990年代,看看爷爷辈的电影是什么样合集约212G
[书籍] 彭子益医书合集 [PDF/DOC]
[系统]【黑果小兵】macOS Big Sur 11.0.1 20B50 正式版 with Clover 5126 黑苹果系统镜像下载
[美图] 【经典收藏美图集合】1500多张韩国美女高清图片让你的收藏夹更加丰富多彩
[瓜] 青岛【路虎女】插队、逆行、追尾、打人未删减【完整版视频】
[电视剧] 灵魂摆渡(1-3季合集)【未删减】【4K.无水印】【剧情/恐怖/惊悚】【豆瓣8.7】
[书籍资料] 《玉房秘诀》《玉房秘典》《古代房中术》
- 最新评论
-
电影很不错谢谢分享贪睡的猫 评论于:11-18 一部不错的经典科幻kelvin 评论于:11-13 找了好久的资源,终于在这里找到了。感谢本站的资源和分享。谢谢285552528 评论于:11-09 找了好久的资源bjzchzch12 评论于:11-07 谢谢分享感谢ppy2016 评论于:11-05 谢谢分享感谢ppy2016 评论于:11-05 有靳东!嘻嘻奥古斯都.凯撒 评论于:10-28 流星花园是F4处女作也是4人集体搭配的唯一一部!奥古斯都.凯撒 评论于:10-28 找了好久的资源,终于在这里找到了。感谢本站的资源和分享。谢谢AAAAA 评论于:10-26 找了好久的资源,终于在这里找到了。感谢本站的资源和分享。谢谢password63 评论于:10-26
- 热门tag