[知识总结] 【ACM】ACM宝典
作者:CC下载站 日期:2021-05-25 08:53:00 浏览:60 分类:编程开发
本文用于记录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
取消回复欢迎 你 发表评论:
- 精品推荐!
-
- 最新文章
- 热门文章
- 热评文章
[壁纸工具] 每日必应壁纸爬取
[文件转换] Unlock Music 音乐解锁---搬运工---使用过最好的音乐格式转换全能工具
[图床工具] 百家号变免费图床
[行业软件] 超市播音系统V9.9(思维构造)——定时播放功能免费
[数码资讯] 松下Lumix S9完整细节曝光
[电视剧] [庆余年 第二季] [更至9集] [WEB-MKV] [国语中字] [4K]
[游戏娱乐] 《漫野奇谭》v1.16.535中文版
[游戏娱乐] 《奥西里斯:新黎明》v1.5.67中文版
[游戏娱乐] 《倾覆之国:最后一战》v1.0.0中文版
[文件传输] 【Android/IOS/Win】互传 EasyShare 3.6.5 零流量、极速、多平台快捷传输工具
[资料] [大学期末救急课] 猴博士+高斯课堂+斐多课堂,全集视频合集
[云资源] 价值2万元的老男孩Python教程
[书库] 史上最全摄影书推荐(附700本PDF版打包下载)
[云资源] 花了一千多元买的私人健身教程
[下载工具] Internet Download Manager 6.42.7 (IDM)
[影视] 灌篮高手 WEB-DL版下载/Slam Dunk/スラムダンク/灌篮高手:THE FIRST/灌篮高手电影版 2022 The First Slam Dunk 61.35G
[安卓软件] 酷我音乐APP_v10.7.6.4 去广告破解豪华VIP版
[即时通讯] 微信PC版WeChat 3.9.9.43 多开防撤回绿色版
[安卓软件] Solid Explorer文件管理器APP 2.8.38 破解版
[浏览器] Google Chrome v123.0.6312.59便携增强版
[云资源] 价值2万元的老男孩Python教程
[影视] 灌篮高手 WEB-DL版下载/Slam Dunk/スラムダンク/灌篮高手:THE FIRST/灌篮高手电影版 2022 The First Slam Dunk 61.35G
[云资源] 花了一千多元买的私人健身教程
[书库] 史上最全摄影书推荐(附700本PDF版打包下载)
[动画] 北斗神拳(1984) [两季合集] [MKV]
[资料] 抗战阵亡将士资料+续编
[电视剧] 三体 (2024) 全8集 网飞版本 中文字幕 合集
[纪录片] 河西走廊【10集 国语 中文字幕 1080P 10.8G MP4】
[电影] 2024年喜剧片·热辣滚烫 [mp4]
[影视] 铁爪 WEB-DL版下载 2023 The Iron Claw 23.48G
- 最新评论
-
我想看看mw2ddyy 评论于:04-26 好东西阿zfy123123 评论于:04-18 谢谢楼主xiaoqi 评论于:04-12 勿在线解压,勿手机解压,请在电脑上用最新款压缩软件解压!推荐360压缩或者好压CC下载站 评论于:04-10 无法解压啊,客服能不能给个解压教程ravengrey 评论于:04-10 谢谢支持!!CC下载站 评论于:03-26 很棒的资源,感谢分享云体风身 评论于:03-26 感谢分享,好东西云体风身 评论于:03-26 谢谢支持!CC下载站 评论于:03-14 央视精品,感谢付出提供。qwer9009 评论于:03-14
- 热门tag