进阶实验6-3.4 拯救007(升级版)题目解法题目
在老电影“007之生死关头”(Live and Let Die)中有一个情节,007被毒贩抓到一个鳄鱼池中心的小岛上,他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄…
原题链接:CCF-CSP 201803-5 二次求和
#include <bits/stdc.h>
using namespace std;
const int N2010;
const int Q1000000007;long long tree[N];
long long mp[N];
vector<long long> adj[N];
set<vector<int>> path;void dfs1(int f…
原题链接:CCF-CSP 201812-4 数据中心 纯纯的kruscal
#include <bits/stdc.h>
using namespace std;
int n,m,root;
const int N5e410;
const int M1e510;struct edge
{int u,v,w;
}e[M];
bool cmp(edge a,edge b)
{return a.w<b.w;
}
int f[N];
int find…
原题链接:Leetcode 2285. 道路的最大总重要性 class Solution {
public:long long maximumImportance(int n, vector<vector<int>>& roads) {long long res0;vector<long long> degree(n);for(auto x:roads){degree[x[0]];degree[x[1]];}sort…
头文件
#include<bits/stdc.h>
#define intn long long
#define ls(k) (k)<<1
#define inf 2147483647
#define re register
#define rs(k) (k)<<1|1
#define _0for(i, a) for(int i 0; i < (a); i)
#define _1for(i, a) for(int i 1; i <(a); i)
#…
树状数组和差分树状数组 快速求前缀和修改某个数 241. 楼兰图腾 - AcWing题库
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N 200010;int n;
int a[N];
int tr[N];
int g[N], l[N…
这次考的是 A t C o d e r AtCoder AtCoder的题 发挥不是很好 用洛谷当题面了 还能方便点
A
直接七天一求和就行
#include<bits/stdc.h>
#define reg register
using namespace std;
inline void read(int &x){int s0,w1;char chgetchar();while(ch<0||ch>9…
Einstein学画画
题目描述
Einstein 学起了画画。
此人比较懒~~,他希望用最少的笔画画出一张画……
给定一个无向图,包含 n n n 个顶点(编号 1 ∼ n 1 \sim n 1∼n), m m m 条边,求最少用多少笔可以画…
Prufer序列
起源于对 C a y l e y Cayley Cayley定理的证明,但是其功能远不止于此 现在考虑将一棵n个节点的树与一个长度为n-2的prufer序列构造对应关系 T r e e − > P r u f e r : Tree->Prufer: Tree−>Prufer: ①从树上选择编号最小的叶子节点&#x…
文章目录 贪心:A. Sasha and Array Coloring结论:B. Long Long性质:C. Sum in Binary Treedfs求叶子数量:D. Apple Tree二分与前缀和:E. Tracking Segments 贪心:A. Sasha and Array Coloring
Problem - A…
输入两个分数,例如3/41/2,输出3/41/25/4。 运行程序时,如下图所示: 输入样例1:
1/61/2输出样例2:
1/61/22/3 #include<stdio.h>
int gcd(int a,int b) //求最大公约数(Greatest Common Divisor&…
一、图的定义
图是通过一组边相互连接的顶点的集合。 In this graph,
V { A , B , C , D , E }
E { AB , AC , BD , CD , DE } 二、图的类型 2.1 Finite Graph
A graph consisting of finite number of vertices and edges is called as a finite graph. Null Graph
Tri…
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。
输入格式 第一行两个整数,N&a…
Winter Training Div.1 #1 C题
D. Fix a Tree
A tree is an undirected connected graph without cycles. 一棵树是一个无向无环的连通图。 Let’s consider a rooted undirected tree with nnvertices, numbered 1" role="presentation" style="posit…
做图论的社区检测,需要画图显示,用igraph可以进行可视化。 igraph有几个布局,分别如下:
layout_with_dh : The Davidson-Harel layout algorithm
Place vertices of a graph on the plane, according to the simulat…
08-图8 How Long Does It Take
分数 25 作者 陈越 单位 浙江大学
Given the relations of all the activities of a project, you are supposed to find the earliest completion time of the project.
Input Specification:
Each input file contains one test case. Each…
高精度乘低精度
高精度乘低精度模板
// C A * b, A > 0, b > 0
vector<int> mul(vector<int> &A, int b){vector<int> C;int t0;for(int i0;i<A.size()||t;i){if(i<A.size()) tA[i]*b;C.push_back(t%10);t/10;}while(C.size()>1&&…
模拟栈
题目链接 栈的数组模拟非常简单,不详细描述 设置一个指针指向栈顶第一个元素即可 STL中stack实现已经更新在STL_Stack #include<iostream>
#include<string>using namespace std;const int N1e51;
int m;
string s;
int stack[N];
int p;//指针…
Portal.
LCA。
询问树上两条路径是否有交点。
画图发现无非两种情况: 发现一条路径的起点和终点的 LCA 经过另一条路径,是两路径相交的充要条件。
考虑如何判断这个 LCA 在不在路径上。若 d ( s , LCA ) d ( LCA , t ) d ( s , t ) d(s,\text{LCA…
2022gdcpc
和学弟vp了一下这场,本来抓的数学选手咕咕了,只有2个人,打下来的感觉就是套路题和码量太大了,太久没写码量题导致 I I I调太久了,最后G没写完,K也没冲出来,感觉数学大爹在的话这K应该…
如图,在 △ A B C \triangle ABC △ABC 中, A C > 5 , A B > A C AC>5,AB>AC AC>5,AB>AC,点 E E E 是 A B AB AB 上一点,链接 C E CE CE,将 △ B C E \triangle BCE △BCE 沿 C E CE CE 折叠&…
Floyd算法主要内容 一、基本思路1、算法原理2、基本思路3、注意 二、Java、C语言模板实现三、例题题解 一、基本思路
1、算法原理 遍历每条边,通过比较进行路径更新——暴力 解决多源最短路问题,求解 i 点到 j 点的最短距离 f [ i, j, k] 表示从 i 走…
分数 30
全屏浏览题目
切换布局
作者 CHEN, Yue
单位 浙江大学
A travelers map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest…
图的引入与术语
两种图
1. 有向图(Digraph):Each edge of arc has an associated direction.
2. 无向图(non-directed graph):Every edge or arc is two-way. 简单图是一种特殊的无向图。无向图没有自环…
4.A A. 不是简单路径的话,有环,去环路径会更短 B. 适合的 弗洛伊德算法才不适合 C. 本来就是 D 2X2矩阵拓展到3X3矩阵 再扩大 若是子集 即加入新顶点后,最短路径都没有变,错
5.B 本题用弗洛伊德更合适 但这道题只需全部代入求最…
题目链接
迷路
题目描述
windy 在有向图中迷路了。
该有向图有 n n n 个节点,节点从 1 1 1 至 n n n 编号,windy 从节点 1 1 1 出发,他必须恰好在 t t t 时刻到达节点 n n n。
现在给出该有向图,你能告诉 windy 总共有…
P3366 【模板】最小生成树
一道模板题,prim算法就可以过,krustal算法也是可以的嗷 prim算法
#include <bits/stdc.h>
using namespace std;
const int N 5010;
const int INF 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
in…
文章目录一、A - Hall of Fame二、B - MKnezs ConstructiveForces Task三、C - Least Prefix Sum四、D - Boris and His Amazing Haircut一、A - Hall of Fame 思路: 对于一个点(X,Y)来说,答案最多就是4,也就是(X 1,Y),(X - 1,Y),(X,Y 1),(X,Y - 1),但是对于边界上面的点,也就…
74. 搜索二维矩阵 - 力扣(LeetCode)
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int n matrix.size(), m matrix[0].size();int x 0, y m - 1;while(true){if(x > n || y < 0) r…
本题要求对两个整数a和b,输出其中较大的数。
函数接口定义: int max( int a, int b ); 其中a和b是用户传入的参数,函数返回的是两者中较大的数。
裁判测试程序样例:
#include <stdio.h>int max( int a, int b );int main…
最长公共子序列
代码(附分析过程)
import java.util.Scanner;public class one {// DP求解最长公共子序列public static int LcsLength(char[] x, char[] y, int[][] vis) {int m x.length - 1;int n y.length - 1;int[][] c new int[m 1][n 1]; …
题目
POJ2955.Brackets We give the following inductive definition of a “regular brackets” sequence:
the empty sequence is a regular brackets sequence, if sss is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and if aaa and…
LINK
不得不说 双指针用法nb
题目 输入输出样例
输入 6 3 1 5 2 1 7 3 1 3 8 输出 3
思路:
建议看尺取法
代码:
#include<bits/stdc.h>
using namespace std;
typedef long long ll;
//#define int long long
const int mod1e97;
const int…
原题链接:CSP 202109-5 箱根山岳险天下 代码来自我亲爱的室友
#include <bits/stdc.h>
using namespace std;
#define ll long long
const int MAX3e510;
int m,p,t;
int a0;
int ty[MAX];
int x[MAX],y[MAX];
ll qiang[MAX];//每个队员的强度
vector<int…
原题链接:CSP 202112-5 极差路径
#include <bits/stdc.h>
using namespace std;
#define ll long long
const int MAX5e510;
const int INF1e9;int n,k1,k2;
vector<int> g[MAX];
int vis[MAX];
int p[MAX];
int num1;
set<pair<int,int> >…
原题链接CSP 201903-5 317号子任务
1.下面是30分的暴力代码,仅仅使用常规的未优化的Dijkstra算法做的。
#include <bits/stdc.h>
using namespace std;
#define ll long long
const int MAX10010;
const int INF1e8;int n,m,k;
int f[MAX];
struct node
{i…
Graph algorithms
Definitions
graph: a set of objects that are connected to each other through links G (V,E) directed graph(有向图) digraph undirected graph(无向图) indegree of a vertix path simple path: does not contain the same vertex more than on…
AcWing 每日一题 2022/5/6【2012. 一排奶牛】
农夫约翰的 N 头奶牛排成一排。
每头奶牛都用一个整数品种 ID 标识,队列中第 i 头奶牛的 ID 为 Bi。
约翰认为如果有一大段连续的奶牛都具有相同的品种 ID,他的奶牛就会更加的引人注目。
为了创造这样的…
public class BreadthFirstPaths {private boolean[] marked;// 保存被标记的顶点private int[] edgeTo;// 保存起点到与之连通的顶点之间的最短路径private final int s;// 起点public BreadthFirstPaths(Graph G, int s) {marked new boolean[G.V()];edgeTo new int[G.V()]…
题意
给出一个图,图中的边表示从点u到点v路径上的噪音。给出q个查询,问从u到v所经路径上的最小噪音
思路
在使用floyd计算点对之间的路径时, D u , v k m i n { D u , v k − 1 , m a x { D u , k k − 1 , D k , v k − 1 } } D_{u, v}^…
选择 D 0作为本地宿主机,127作为内部回送,不予分配 A B C C 存储在浏览器 D A B B D 网络延迟是指从报文开始进入网络到它离开网络之间的时间 编程
红与黑
红与黑__牛客网 #include <iostream>
#include <stdexcept>
#include <string…
写个目录图的存储图的遍历深度优先搜索(DFS)法遍历图[PAT A1034] 1034 Head of a Gang(30)广度优先搜索(BFS)法遍历图[PAT A1076] Forwards on Weibo(30)最短路径Dijkstra算法——解决单源最短路径问题最短距离最短路径最短路径不…
题目来源:PAT (Advanced Level) Practice
Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well. Hence a social network is formed with followers relations. When a user …
P2607 [ZJOI2008] 骑士
[P2607 ZJOI2008] 骑士 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 文章目录 P2607 [ZJOI2008] 骑士题目大意思路code 题目大意
给你一个 n n n 个点, n n n 条边的基环树森林。
你可以从中选择若干个点,满足两两之间不存…
L1-014 简单题 (5 分)
这次真的没骗你 —— 这道超级简单的题目没有任何输入。
你只需要在一行中输出事实:This is a simple problem.就可以了。
输入样例:
无输出样例:
This is a simple problem.#include<iostream>
#include<…
Problem - 1525 (nefu.edu.cn)
Problem:1525
Time Limit:1000ms
Memory Limit:131072K
Description
给定一个包含 n 个节点和 m 条边的图,每条边有一个权值。
你的任务是回答 k 个询问,每个询问包含两个正整数 s 和 t 表示起点和终点,…
一、问题简介
最近公共祖先简称 LCA(Lowest Common Ancestor)。两个节点的最近公共祖先,就是这两个点的公共祖先里面,离根最远的那个。为了方便,我们记某点集 S { v 1 , v 2 , … , v n } S\{v_1,v_2,\ldots,v_n\} S…
Problem - E2 - Codeforces
问题描述:给两个字符串和一个k。如果下标i,j满足|i - j| k or |i - j| k 1,则可以swap(s[i], s[j]),s为两个字符串之一。
思路:如果<i,z> <z,j>可行,那么<i…
Linova and Kingdom—CF1336A 参考文章
思路 1 1 1 号节点为根节点。很容易想到,工业城市在树的下边,旅游城市在树的上边。具体来说,如果节点 u u u 是工业城市,那么它的子树的所有节点一定都是工业城市;如果节点 u…
[图论与代数结构 701] 强连通分量
题目描述
给定一张 n n n 个点 m m m 条边的有向图,求出其所有的强连通分量。
注意,本题可能存在重边和自环。
输入格式
第一行两个正整数 n n n , m m m ,表示图的点数和边数。
接下来…
CF837G Functions On The Segments
Functions On The Segments - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 文章目录 CF837G Functions On The Segments题目大意思路code 题目大意
你有 n n n 个函数,第 i i i 个函数 f i f_i fi 为: f i ( x…
基础
前置知识
强连通:对于有向图中两点 i i i, j j j,若存在 i i i 到 j j j 和 j j j 到 i i i 的路径,则称 i i i, j j j 强连通。强连通:对于有向图中两点 i i i, j j j࿰…
[蓝桥杯 2022 省 A] 推导部分和
题目描述
对于一个长度为 N N N 的整数数列 A 1 , A 2 , ⋯ A N A_{1}, A_{2}, \cdots A_{N} A1,A2,⋯AN,小蓝想知道下标 l l l 到 r r r 的部分和 ∑ i l r A i A l A l 1 ⋯ A r \sum\limits_{il}^{r}A_iA_{l}A…
【模板】差分约束
题目描述
给出一组包含 m m m 个不等式,有 n n n 个未知数的形如: { x c 1 − x c 1 ′ ≤ y 1 x c 2 − x c 2 ′ ≤ y 2 ⋯ x c m − x c m ′ ≤ y m \begin{cases} x_{c_1}-x_{c_1}\leq y_1 \\x_{c_2}-x_{c_2} \leq y_2 \\ \cd…
文章目录K.Search For MafuyuC.Optimal Strategy补题链接:https://pintia.cn/market/item/1459833348620926976
K.Search For Mafuyu
K Search For Mafuyu (300分) Mafuyu has hidden in Sekai, and Kanade is searching for her.
In Sekai, there is nothing bu…
http://cplusoj.com/d/senior/p/SS231114D
重新梳理一下题目
我们先建图 x → y x\to y x→y,然后对点分类:原串出现点,原串未出现点。
假如我们对一个原串出现点进行了操作,那么它剩余所有出边我们立刻去操作必然没有影响。所…
思路:对于有很多询问的题,一般都是先初始化。我们求出每个点到其他点的最短路径以及相同路径下最大的价值和即可。
代码:
#include <bits/stdc.h>
#define pb push_back
#define a first
#define b second
using namespace std;
type…
模板记录 #include<bits/stdc.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define x first
#define y second
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> …
[HNOI2005] 狡猾的商人
题目描述
刁姹接到一个任务,为税务部门调查一位商人的账本,看看账本是不是伪造的。账本上记录了 n n n 个月以来的收入情况,其中第 i i i 个月的收入额为 a i a_i ai, i 1 , 2 , … , n − 1 , n i…
C : 追星 文章目录 C : 追星DescriptionInputOutputSampleInputOutput 解题思路AC代码: Description
城市总共有N座。yintama是右京女神的狂热粉,当他得知右京女神将要在城市N举办演唱会的时候,马上开始准备动身前往城市N。原本他可以直接乘…
快速幂求逆元 核心思想: 逆元: 逆元 ap-2 mod p #include<iostream>#include<algorithm>using namespace std;typedef long long LL;LL pmi(int a,int b,int c){LL res 1;while(b){if(b & 1) res res * a %c;b >> 1;a (LL)…
题目描述 Farmer John has decided to assemble a panoramic photo of a lineup of his N cows (1 < N < 200,000), which, as always, are conveniently numbered from 1..N. Accordingly, he snapped M (1 < M < 100,000) photos, each covering a contiguous ra…
树和无向图都可以看成有向图(无向图在添加边的时候添加双向的) 下面是模版,实际使用要根据情况改:
#include <iostream>
#include <cstring>
using namespace std;const int N 10010, M N * 2;int n;
int h[N], e[…
Time Limit: 1000MSMemory Limit: 65536KTotal Submissions: 30932Accepted: 20284
Description
In the Fibonacci integer sequence, F0 0, F1 1, and Fn Fn − 1 Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:
0, 1, 1, 2, 3,…
前言:嗯,这个题上午有的思路,敲了一中午代码,改了一下午最后超时? 题:D. Boris and His Amazing Haircut 题意:一个理发师可以把一段数组给建成一个高度,他现在每个高度的剪子都有若干个。给一个原始数组和…
文/Emma Z1950年,图灵发表了具有里程碑意义的论文《计算机器与智能》(Computing Machinery and Intelligence),提出了一个关于机器人的著名判断原则——图灵测试,也被称为图灵判断,它指出如果第三者无法辨别…
诸神缄默不语-个人CSDN博文目录 文章目录 1. 对称归一化 D − 1 2 A D − 1 2 D^{-\frac{1}{2}}AD^{-\frac{1}{2}} D−21AD−212. D − 1 A D^{-1}A D−1A 1. 对称归一化 D − 1 2 A D − 1 2 D^{-\frac{1}{2}}AD^{-\frac{1}{2}} D−21AD−21
代码参考自R-former&…
题意:https://www.luogu.com.cn/problem/AT_abc283_e
思路:非常经典的dp,设为前i行第i行是否反转和第i1行是否反转。
/*keep on going and never give up*/
#include<cstdio>
#include<iostream>
#include<queue>
#inclu…
【题目描述】
n 位同学站成一排,音乐老师要请其中的 n−k 位同学出列,使得剩下的 k 位同学排成合唱队形。
合唱队形是指这样的一种队形:设 kk 位同学从左到右依次编号为 1,2, … ,k,他们的身高分别为,, … ,,则…
AtCoder Beginner Contest 292 A - E前言Q1 A - CAPS LOCKQ2 Yellow and Red CardQ3 Four VariablesQ4 D - Unicyclic ComponentsQ5 E - Transitivity前言
本来晚上在打Acwing周赛,最后一题Trie想不出来咋写,看群里有人说ABC要开始了,想着没…
分数 25
全屏浏览题目
作者 CHEN, Yue
单位 浙江大学
Suppose that all the keys in a binary tree are distinct positive integers. Given the preorder and inorder traversal sequences, you are supposed to output the first number of the postorder traversal sequ…
分数 30
全屏浏览题目
切换布局
作者 CHEN, Yue
单位 浙江大学
Given a non-empty tree with root R, and with weight Wi assigned to each tree node Ti. The weight of a path from R to L is defined to be the sum of the weights of all the nodes along the pa…
题目描述 知名美食家小 A 被邀请至 ATM 大酒店,为其品评菜肴。ATM 酒店为小 A 准备了 nn 道菜肴,酒店按照为菜肴预估的质量从高到低给予 11 到 nn 的顺序编号,预估质量最高的菜肴编号为 11。
由于菜肴之间口味搭配的问题,某些菜肴…
分数 25
全屏浏览题目
作者 CHEN, Yue
单位 浙江大学
A family hierarchy is usually presented by a pedigree tree where all the nodes on the same level belong to the same generation. Your task is to find the generation with the largest population.
Input Sp…
今年比去年难好多
A. 日期统计
直接8个for,然后剪枝一下(只取2023)开头的,跑起来还是很快的,自己电脑100ms,机房1s左右 我算的答案是235,不一定对qwq
#include <bits/stdc.h>
using namespace st…
算法基础简介 - OI Wiki (oi-wiki.org) 文章目录1. 数据结构介绍1.1 什么是数据结构1.2 数据结构分类2. 链表、栈、队列:略3. 哈希表:略4. 树4.1 二叉树4.2 B 树与 B 树4.3 哈夫曼(霍夫曼)树:Huffman Tree4.4 线段树&a…
题意:
给定一个 n n n 点 m m m 条边的无向连通图,其中 1 ≤ m ≤ n 2 1\leq m\leq n2 1≤m≤n2。 m m m 条边中有一些条边被染成红色,剩下的边被染成蓝色。只考虑红色边,有 c 1 c_1 c1 个连通分量。只考虑蓝色边…
[POJ - 1015]Jury Compromise(01背包问题) 一、问题二、分析1、状态表示2、状态转移3、方案输出 三、代码 一、问题 二、分析
这道题可以转化为一个01背包问题,问题描述可以改为,每个物品具有两个属性 a a a和 b b b,…
(1条消息) POJ 3050 Hopscotch(深搜)_3050hopscotch_皮皮皮皮皮皮皮卡乒的博客-CSDN博客 #include <iostream> #include<cstring> #include<set> using namespace std; int a[5][5]; int i; set<int> s; int dis[4][2]{0,1,0,-1…
小 A A A地盘上的所有人被从 1 1 1 到 n n n 编号,每个人都有自己传话的对象,第 i i i 个人对第 a i a_i ai个人传话。 有一天,小 A A A在宫殿的顶部大声喊着 O w f Owf Owf,于是一个有趣的游戏在小 A A A的地盘上开始了。 …
题目:
The "BerCorp" company has got n employees. These employees can use m approved official languages for the formal correspondence. The languages are numbered with integers from 1 to m. For each employee we have the list of language…
本题要求实现一个判断整数是否为完全平方数的简单函数。
函数接口定义:
int IsSquare( int n );
其中n是用户传入的参数,在长整型范围内。如果n是完全平方数,则函数IsSquare必须返回1,否则返回0。
裁判测试程序样例࿱…
题目来源:PAT (Advanced Level) Practice
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length…
数据结构 图形化What you will learn? 您将学到什么? In this article we are going to study how graph is being represented? 在本文中,我们将研究图形如何表示 ? Following is an undirected graph, 以下是无向图, We ca…
public class DepthFirstPaths {private boolean marked[];// 用于存放被标记过的顶点private int edgeTo[];// 数组内的元素表示某顶点,其索引表示某顶点的相邻顶点。private final int s;// 起点private int count;// 已遍历顶点的数量public DepthFirstPaths(Gra…
本题要求的是最短转换序列的长度,看到最短首先想到的就是广度优先搜索。想到广度优先搜索自然而然的就能想到图,但是本题并没有直截了当的给出图的模型,因此需要按照题意把它抽象成图的模型。
class Solution:def ladderLength(self, beginW…
题目来源:PAT (Advanced Level) Practice
A travelers map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between…
题目来源:PAT (Advanced Level) Practice
A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible. However it must guarantee that all the houses a…
原题链接:CSP 201909-5 城市规划 暴力前20分
#include <bits/stdc.h>
using namespace std;
#define ll long long
const int INF1e8;
int big[2020];struct node
{int v;int w;node(int _v,int _w){v_v;w_w;}
};vector<node> g[2010];
int vis[2010];…
2022.2.13 练习 PAT 甲 1030 Travel Plan (原题链接)
题解一:
#include <bits/stdc.h>
using namespace std;
const int MAX_NUM510;
const int INF0x3fffffff;
int n,m,s,D;int d[MAX_NUM];//起点到各点的最短路径长度
int visit[MA…
#include<cstdio>
#include<map>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int inf 0x3f3f3f3f;
int n, m, graph[66][66], vis[66], dis[66];//dis表示当前顶点i离生成树最近距离
int sum 0;
voi…
#include<cstdio>
#include<map>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int inf 0x3f3f3f3f;
int n, m;
int graph[66][66],vis[66],dis[66];
void dijkstra(int s)//s表示源点
{memset(vis, 0,…
在图论中,拓扑排序是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足下面两个条件:
每个顶点出现且只出现一次。若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在…
1.tokitsukaze and Connection 题目大意:字符串中的相同字符是不是全部在一起 思路:对于每一个字符,判断是否出现过,出现过则判断它的上一个字母与现在的是否相同,相同则连续,否则不连续;没出现…
5347. 使网格图至少有一条有效路径的最小代价 BFS中每个点只入列一次,但有时,我们可能需要bfs中允许一个点入列多次才能解决问题,这种方法就是SPFA。 class Solution {public int minCost(int[][] grid) {int m grid.length, n grid[0].len…
Link 思维,贪心,拓扑排序 2400
题意
有nnn种菜,每种菜都有wiw_iwi碟,你有mmm个朋友,每个朋友都有两种喜欢的菜,你按照某个排序让朋友一个一个来吃菜,如果现在桌上有这个朋友喜欢的菜&#x…
Link 挺有意思的一道题,思路其实蛮清晰也比较容易理解,然而实现的时候写了半天
代码
const int maxn 1e6 10;
const int maxm 1e6 10;
struct Edge {int to, dis, next;
}edge[maxm];
int n, m;
int head[maxn], dis[maxn], cnt 1;
bool vis[maxn…
题目链接:Dijkstra求最短路 I
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N 510;int n, m;
int g[N][N];
int dist[N];
bool st[N];int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1…
题目链接:Floyd求最短路 #include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N 210, INF 1e9;int n, m, Q;int d[N][N];void floyd()
{for(int k 1; k < n; k)for(int i 1; i < n; i)for(int …
数据结构–拓扑排序
AOV⽹ A O V ⽹ \color{red}AOV⽹ AOV⽹(Activity On Vertex NetWork,⽤顶点表示活动的⽹): ⽤ D A G 图 \color{red}DAG图 DAG图(有向⽆环图)表示⼀个⼯程。顶点表示活动,有向边 < V i , V j …
题目链接:树的重心
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N 100010, M N * 2;int n;
int h[N], e[M], ne[M], idx;
int ans N;
bool st[N];void add(int a, int b)
{e[idx] b, ne[id…
C 最小步数模型通常用于寻找两个点之间的最短路径或最少步数。以下是一个基本的 C 最小步数模型的示例代码:
#include<bits/stdc.h>
using namespace std;
const int N 1e5 5;
vector<int> G[N];
int d[N];
bool vis[N];void bfs(int s) {queue<i…
20分,六重循环看不懂
计算机软件能力认证考试系统
#include<bits/stdc.h>
using namespace std;
int NK[6][10];
int line[6][6][10][10];
int main()
{int N,M,K;cin>>N>>M>>K;for(int i0;i<N;i){for(int j0;j<K;j){cin>>NK…
LGV引理
在一个有向无环图G中,出发点 A { a 1 , a 2 , . . . a n } A\{a_1,a_2,...a_n\} A{a1,a2,...an},目标点 B { b 1 , b 2 , . . b n } B\{b_1,b_2,..b_n\} B{b1,b2,..bn}。有向边 e e e的权值为 w e w_e we, e ( u , …
1、题目
问题描述
过年小蓝想要回家串门。
蓝桥村可以抽象为 n n n 个节点, n − 1 n-1 n−1 条边的一棵树,每条边有边权长度 w i w_i wi。
小蓝可以选择任意一个点作为起点,然后选择一条路径,可以访问每个节点至少一次。…
Alice \text{Alice} Alice 和 Bob \text{Bob} Bob 又开始玩游戏了,他们已经把石子堆得比山还高了,现在他们要玩一种更新奇的游戏,这种游戏的规则如下:
给定一颗 n n n 个节点的树, Alice \text{Alice} Alice 和 Bo…
A - On and Off (atcoder.jp) (1)题意 高桥每天在S点钟打开他房间的灯,并在T点钟关灯,指示灯亮起时,日期可能会发生改变,判断是否在X点过后30分时亮着。 (2)思路 直接模拟即可。 &am…
Problem - 431C - Codeforces 解析: #include<bits/stdc.h>
using namespace std;
#define int long long
const int mod1e97,N110;
int n,k,d,dp[N][2];
signed main(){scanf("%lld%lld%lld",&n,&k,&d);dp[0][0]1;for(int i1;i<n;…
Problem - 1336A - Codeforces
Linova and Kingdom - 洛谷 解析: 开始认为分情况讨论 k 小于等于叶子结点和大于叶子结点的情况,然后选择深度最深的叶子结点和子孙数量最小的结点,但是发现如果把某一个非叶子结点选取,那么其子孙…
AtCoder Beginner Contest 324
F Beautiful Path
需要一点思维的转化,一时竟然没想到。
题意
给定大小为 n n n 的有向图, m m m 条边,每条边有 b i , c i b_i,c_i bi,ci 两个属性,需要找到一条从 1 ∼ n 1\sim n 1∼n…
P3177 [HAOI2015] 树上染色
[P3177 HAOI2015] 树上染色 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 文章目录 P3177 [HAOI2015] 树上染色题目大意思路code 题目大意
有一棵 n n n 个点的树,你可以在上面把 k k k 个点染成黑色,收益为黑点两两之间…
Problem - F - Codeforces
题目大意:有一棵n个点的树,其中有k个标记点,令点i到所有标记点的最远距离为fi,问所有点中fi的最小值是多少
1<k<n<2e5
思路:我们首先考虑取得最小值的点在哪,我们假设…
回忆旅途的过往 文章目录 回忆旅途的过往题大意思路code 题大意
有 n n n 个砝码,每个砝码都有初始重量 a i a_i ai 。 Q Q Q 次操作,每次操作有以下两种 1 , l , r , x 1,l,r,x 1,l,r,x:表示把 l l…
澪有个 n n n 个点 m m m 条边的无向图,每条边都有蓝白两种颜色中的一种,保证蓝色的边形成了这个图的一个生成树。
她希望给这些边赋上边权,保证边权是 1 ∼ m 1 \sim m 1∼m 的排列,使得蓝色的边是最小生成树。
希望这些边权…
URL:https://atcoder.jp/contests/abc321 目录
E
Problem/题意
Thought/思路
Code/代码 E
Problem/题意
有一颗 N 个节点的完全二叉树,现在给出节点 X,一个整数 K,问举例节点 X 的长度为 K 的点有多少个?
Thoug…
gcd就是a、b的最大公约数 #include<iostream>
using namespace std;int exgcd(int a, int b, int &x, int &y)//返回gcd(a,b) 并求出解(引用带回)
{if(b0){x 1, y 0;return a;}int x1,y1,gcd;//这里不用看a和b谁大,因为递归还是会反过来比较&#x…
题目
前缀和 题解 前缀和模板 太简单了就多加了点东西:对比cin cout和scanf printf的耗时对比 代码
#include <iostream>
using namespace std;
const int N 100010;
int n, m;
int a[N], s[N];
int main(){scanf("%d%d", &n, &m);//原数组 for (in…
文章目录 题目描述输入格式输出格式样例样例输入样例输出 数据范围与提示完整代码 题目描述
给出一个 N N N 个顶点 M M M 条边的无向无权图,顶点编号为 1 ∼ N 1\sim N 1∼N。问从顶点 1 1 1 开始,到其他每个点的最短路有几条。
输入格式
第一行…
2023NOIP A层联测27 A.kotori 文章目录 2023NOIP A层联测27 A.kotori题目大意思路code 题目大意
琴里的飞船中有 n n n 个人,其中有 n − 1 n - 1 n−1 个通道,所以飞船的内部是一个树形结构。每个人从 1 − n 1-n 1−n 编号,编号越小代表…
解析: 对于英雄跑一边二分图匹配,记录res1 再跑一边二分图匹配,记录res2 答案即为res1min(k,res2)
#include<bits/stdc.h>
using namespace std;
int n,m,k;
int g[510][510],match[510],st[510];
b…
【模板】差分约束
题目描述
给出一组包含 m m m 个不等式,有 n n n 个未知数的形如: { x c 1 − x c 1 ′ ≤ y 1 x c 2 − x c 2 ′ ≤ y 2 ⋯ x c m − x c m ′ ≤ y m \begin{cases} x_{c_1}-x_{c_1}\leq y_1 \\x_{c_2}-x_{c_2} \leq y_2 \\ \cd…
琴里的飞船中有 n n n 个人,其中有 n − 1 n - 1 n−1 个通道,所以飞船的内部是一个树形结构。每个人从 1 ∼ n 1\sim n 1∼n 编号,编号越小代表这个人的投票经验最丰富。
每个人有一个投票装置,初始都没有启动。现在琴里希望…
最优贸易
题目描述 C C C 国有 n n n 个大城市和 m m m 条道路,每条道路连接这 n n n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m m m 条道路中有一部分为单向通行的道路,一部分为双向通行的道路,双向通行的…
题目
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 impossible。
数据保证不存在负权回路。
输入格式
第一行包含整…
题目
给定 n 个区间 [ai,bi] 和 n 个整数 ci。
你需要构造一个整数集合 Z,使得 ∀i∈[1,n],Z 中满足 ai≤x≤bi 的整数 x 不少于 ci 个。
求这样的整数集合 Z 最少包含多少个数。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含三个…
Portal.
拓扑排序的定义为,若存在边 u → v u\rightarrow v u→v,则 u u u 的拓扑序小于 v v v。拓扑排序是针对 DAG(有向无环图)而言的。
拓扑排序的流程如下:
记录每个点的度数,把度数为 0 0 0 的…
CSDN 有字数限制,因此笔记分别发布,目前:
【笔记1】概念与计算、树及其算法【笔记2】容量网络模型 4.1 容量网络模型
4.1.1 容量网络
容量网络:如果一个加权有向网络 D D D 满足如下三个条件:①存在唯一一个入度为…
文章目录 A - abB - A^AC - Number PlaceD - Good Tuple ProblemE - Maximize RatingF - Apples A - ab
#include <bits/stdc.h>using namespace std;
const int N 2e5 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int…
要求实现一个递归函数,高效求ab(1≤a,b≤62,ab<263)。
函数接口定义: long long int pow(int a, int b);
其中a 、b 是用户传入的参数。
裁判测试程序样例: #include<iostream>
using namespace std;
long long int pow(int a,…
🌈个人主页: Aileen_0v0 🔥热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 💫个人格言:"没有罗马,那就自己创造罗马~" 目录
Shell method
Setting up the Integral
例题
Example 1:
Example 2:
Example 3: Computing…
1 文本格式 #include <bits/stdc.h> using namespace std; const int maxn 1e4 5; const int maxk 5005;
int n, k; int id[maxn][5]; char s[maxn][5][5], ans[maxk]; bool vis[maxn];
struct Edge { int v, nxt; } e[maxn * 100];
int head[maxn], tot 1;
vo…
给你一个无根树,问你以哪个节点为根节点的时候得到所有点的深度之和最大 《贴一张 知乎大佬的一个解释》 #include<bits/stdc.h>
using namespace std;
const int N 2e610;
using ll long long;
ll dep[N],sz[N];
ll ans[N];
vector<int>g[N];
int n;…
题目描述 输入格式 输出格式
输出一行包含一个整数表示答案。
输入输出样例 解题思路
最短路二分
AC代码
#include<bits/stdc.h>
using namespace std;
long long temp,n, Q;
long long f[105][105],min_f[105][105],cut[105],dis[105][105];//cut为减少多少&#x…
https://www.luogu.com.cn/problem/P3163
考虑一条无向边 ( u , v ) (u,v) (u,v) 可走 w w w 次。
我们直接这样子转换 因此直接跑即可 但此题中如果我们直接源点练出去,汇点连出入,可能会算错: 如果都能流对应的流量,那么我…
筛法求欧拉函数 核心思想 :线性筛法 筛的过程中顺便求欧拉函数 第一种情况 (i % prime[j] 0) 第二种情况 (i % prime[j] ! 0) #include<iostream>#include<algorithm>using namespace std;typedef long long LL;const int N 1000010;int prime[N],cnt…
Educational Codeforces Round 158 (Rated for Div. 2) 文章目录 Educational Codeforces Round 158 (Rated for Div. 2)ABCD A
枚举模拟
#include <bits/stdc.h>using namespace std;const int N 2e5 10;
int a[N];void solve()
{int n , x;cin >> n >>…
题目描述
给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环,边权可能为负数。
求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G(V,E),其中 V 表示图中点的集合ÿ…
题目背景 题目限制 题目描述
给定一个 n 个点,m 条有向边的带非负权图,请你计算从 s 出发,到每个点的距离。
数据保证你能从 s 出发到任意点。
输入格式
第一行为三个正整数n,m,s。 第二行起 m 行,每行三个非负整数 ui,vi…
#include<bits/stdc.h>
using namespace std;
using ll long long;bool vis[110];//用来判断该符号是否合法,为1代表合法
//左边和右边的括号都要配对,所以要记录一下各自的位置,所以干脆就将左括号的下标推入栈中int main(){stack<int> stk;string s;…
状态转移问题,一个状态的改变还会牵涉到此状态之前的状态时,很难利用简单的动态规划解决,可以考虑利用BFS队列优化,把更新过的状态存进队列中,队列空时停止 例题:2024牛客寒假集训2D-Tokitsukaze and Slash…
DFS
排列数字 #include<iostream>
using namespace std;
const int N 10;
int a[N], b[N];
int n;void dfs(int u){if(u > n){for(int i 1; i < n; i)cout<<a[i]<<" ";cout<<endl;return;}for(int i 1; i < n; i){if(!b[i]){b[…
ST表
可以求区间最大、最小、gcd、lcm,符合 f(a, a) a都可以 求区间最值,一个区间划分成两段 f[i][j]: 从i开始,长度为2^j的区间最值
#include<iostream>
#include<cmath>
using namespace std;
const int N 1e6 10;
int n,…
拆地毯 这个就是套用最小生成树的模板,只不过要将sort函数改成从大到小进行排序。然后这个退出条件是只要大于k就退出。 代码如下
#include<iostream>
#include<cmath>
#include<algorithm>
#define N 1009000
using namespace std;
int n,m,k…
1-DFS
排列数字
N10
path[0]*N
state[False]*N
def dfs(u):if un:for i in range(n):print(path[i],end )print()for i in range(n):if state[i]False:path[u]i1 state[i]Truedfs(u1)#恢复现场path[u]0state[i]False
nint(input())
dfs(0)采用位运算太优雅了,细细…
1 拓扑排序
对有向图的节点排序,使得对于每一条有向边 U-->V U都出现在V之前
*有环无法拓扑排序
indegree[], nxs[];//前者表示节点 i 的入度,后者表示节点 i 指向的节点
queue []
for i in range(n):if indege[i] 0: queue.add(i)// 入度为0的节…
快速幂 核心思想:logk的复杂度求出ak mod p 将k拆成若干个2的n之和 (二进制) #include<iostream>#include<algorithm>using namespace std;typedef long long LL;LL qmi(int a,int k,int p){LL res 1 % p;while(k) //k转为二进制 还有正数 就进行…
Gopher II(二分图匹配-匈牙利算法) Description The gopher family, having averted the canine threat, must face a new predator. The are n gophers and m gopher holes, each at distinct (x,y) coordinates. A hawk arrives and if a gopher does not reach a…
经颅磁刺激(Transcranial magnetic stimulation, TMS)是一种非侵入性的神经调控工具,目前被用作多种精神和神经疾病的治疗手段。尽管它被广泛使用,但我们对TMS的急性和慢性疗程影响各种神经和血管系统的方式还没有完全了解。本文总…
题目1448:Legal or Not时间限制:1 秒 内存限制:128 兆 特殊判题:否 提交:1071 解决:485 题目描述:ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmoniou…
朴素版dijkstra
主要用于对稠密图的处理,即:m>n2 对于稠密图,用邻接矩阵进行存储
Dijkstra求最短路 I
#include <bits/stdc.h>
using namespace std;
const int N 510;
int n, m;
int g[N][N]; //用邻接矩阵存储图
int dist[N];…
文章目录A.Hero Named MagnusI. PTSDG. Occupy the CitiesE. Buy and DeleteD.Assumption is All You Need补题链接:https://codeforces.com/gym/103409
A.Hero Named Magnus
A Hero Named Magnus Input file: standard input Output file: standard output Time …
1013 Battle Over Cities
dfs确定连通块数量
const int N 1e6 10, M 2 * N, INF 0x3f3f3f3f;
int n, m, k, h[N], e[M], ne[M], idx 0;
bool visited[N];
void add(int a, int b)
{e[idx] b, ne[idx] h[a], h[a] idx;
}void dfs(int u, int x)
{visited[u] true;for…
能被整除的数 核心思想: 容斥原理 总面积 1-23-4…. 总集合元素中个数 1-23-4…. #include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N 20;typedef long long LL;int p[N];int main(){int n,m;cin&…
一.题目 二.思路
1.暴力
训练的时候,初看这道题,这不就打个暴力吗? 2.暴力代码
#include<bits/stdc.h>
#define int long long
using namespace std;
int n,m,fa,x,y,vis[1000001],ans;
vector<int> vec[1000001];
void dfs(i…
活动 - AcWing
给定一个包含 n 个点 m 条边的有向图,每条边都有一个流量下界和流量上界。
给定源点 S 和汇点 T,求源点到汇点的最大流。
输入格式
第一行包含四个整数 n,m,S,T。
接下来 m 行,每行包含四个整数 a,b,c,d 表示点 a 和 b 之…
1.邻接表 static class Edge {int next;int value;public Edge(int next, int value) {this.next next;this.value value;}}static HashMap<Integer, LinkedList<Edge>> graph new HashMap<>();public static void addEgde(int from, int to, int value) …
题目链接
Prim算法实现
class Solution {
public:int minCostConnectPoints(vector<vector<int>> &points) {int ans 0;int n points.size();// 定义并初始化邻接矩阵vector<vector<int> > graph(n, vector<int>(n));for (int i 0; i &…
class Solution {
public://是课程表207题的升级版,不同是结果需要输出顺序数组//不同的地方作了标注,思路不懂的建议先翻看第207题的注释vector<vector<int>> vecVecInt;vector<int> visited;bool flag true;vector<int> ans;…
4.A A. 不是简单路径的话,有环,去环路径会更短 B. 适合的 弗洛伊德算法才不适合 C. 本来就是 D 2X2矩阵拓展到3X3矩阵 再扩大 若是子集 即加入新顶点后,最短路径都没有变,错
5.B 本题用弗洛伊德更合适 但这道题只需全部代入求最…
回溯算法其实就是深搜,只不过这里的深搜是侧重于在图上搜索,回溯大多是在树上搜索。
797.所有可能的路径 完成 代码
模板题
class Solution {List<List<Integer>> res new ArrayList<>();List<Integer> path new ArrayList…
文章目录 题目描述输入格式输出格式样例样例输入样例输出 完整代码 题目描述
Bessie 计划调查 N N N( 2 ≤ N ≤ 2 000 2 \leq N \leq 2\,000 2≤N≤2000)个农场的干草情况,它从 1 1 1 号农场出发。农场之间总共有 M M M( 1 ≤…
题目 在郊区有 N 座通信基站,P 条 双向 电缆,第 i 条电缆连接基站 Ai 和 Bi。 特别地,1 号基站是通信公司的总站,N 号基站位于一座农场中。 现在,农场主希望对通信线路进行升级,其中升级第 i 条电缆需要花费…
目录
基于属性网络的混合阶异常检测
1 Introduction
2 Ralated Work
3 Notations and Problem Formulation
4 The Proposed Model
4.1 Motif and Motif-Augmented Attributed Network Construction
4.2 Hybrid-Order Attributed Network Encoder
4.3 Hybrid-Order Attr…
Layout题目信息输入输出测试样例提示来源解答方法一Bellman_Ford方法二SPFA想法题目信息
Like everyone else, cows like to stand close to their friends when queuing for feed. FJ hasN (2 < N < 1000)cows numbered 1...N standing along a straight line waiting …
求图的最小生成树的Prim、Kruscal算法,其实都是由最小生成树的性质推来的,掌握了该性质,便能较容易地推导出这两种算法。 最小生成树的性质
无向图G的顶点集为 V V V,设 U U U为 V V V的真子集, u ∈ U u\in U u∈U&a…
[蓝桥杯 2016 国 AC] 路径之谜
题目描述
小明冒充 X X X 星球的骑士,进入了一个奇怪的城堡。
城堡里边什么都没有,只有方形石头铺成的地面。
假设城堡地面是 n n n\times n nn 个方格。如图所示。 按习俗,骑士要从西北角走到东南角。 …
网络流
设源点为 s s s,汇点为 t t t,每条边 e e e 的流量上限为 c ( e ) c(e) c(e),流量为 f ( e ) f(e) f(e)。割 指对于某一顶点集合 P ⊂ V P \subset V P⊂V,从 P P P 出发指向 P P P 外部的那些原图中的边的集合&a…
一、问题引出
[NOIP2002 普及组] 选数
题目描述
已知 n n n 个整数 x 1 , x 2 , ⋯ , x n x_1,x_2,\cdots,x_n x1,x2,⋯,xn,以及 1 1 1 个整数 k k k( k < n k<n k<n)。从 n n n 个整数中任选 k k k 个整数相加&…
#include <bits/stdc.h>
using namespace std;
int n, m;
int r[100010];
int l[100010];
int vis[100010];
int idx;void init() {r[0] 1;l[1] 0;r[1] -1;//先把第一个同学安排进入队列,左手连着0节点,右手连 -1 表示空idx 2;
}void add(int …
最短网络
题目http://ybt.ssoier.cn:8088/problem_show.php?pid1350
#include<bits/stdc.h>
using namespace std;
const int N110;
int w[N][N];
bool st[N];
int dist[N];
int n,res0;
void prim()
{memset(dist,0x3f,sizeof dist);dist[1]0;//初始化第一个点到自己…
[NOIP2018 提高组] 铺设道路
题目背景
NOIP2018 提高组 D1T1
题目描述
春春是一名道路工程师,负责铺设一条长度为 n n n 的道路。
铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n n n 块首尾相连的区域,一开始,第 i i i …
文章目录B A Funny Bipartite Graph 状压DPE Bobs ProblemG Eating PlanK Tree 树上启发式合并L Who is the Champion 签到题目集地址
ICPC2019南昌B A Funny Bipartite Graph 状压DP
题目地址B A Funny Bipartite Graph 题目大意:一个二分图,左右各有n个点&#x…
约数
869. 试除法求约数
给定 n 个正整数 ai,对于每个整数 ai,请你按照从小到大的顺序输出它的所有约数。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个整数 ai。
输出格式
输出共 n 行,其中第 i 行输出第 i 个整…
Eppstein的算法是David Eppstein于1998年提出的一种高效且易于实现的k条最短路径寻找方法。它的时间复杂度为O(m n log n k),其中m是边的数量,n是节点的数量,k是要寻找的路径数。相较于其他方法,它具有较好的性能和实用性。 Epp…
inputs a date (e.g. July 4, 2008) and outputs the day of the week-根据输入日期判断星期几://inputs a date (e.g. July 4, 2008) and outputs the day of the week
#include<iostream>
#include<string>
using namespace std;bool leapyear;void g…
Traditional Method for ML in Graphs
lecture2主要介绍的是传统的图机器学习方法,从三个维度进行阐述:Node level, Link level, Graph level。想要应用机器学习模型,首先需要从图中提取出能够充分表示这张图信息的特征,而本节le…
Graph接口
public interface Graph<V, E> {int edgesSize();int verticesSize();void addVertex(V v);void addEdge(V from, V to);void addEdge(V from, V to, E weight);void removeEdge(V from, V to);void removeVertex(V v);// interface vertexVisitor<V>…
Problem - H - Codeforces
题意: 思路:
手玩一下样例就能发现简单结论:
v 离它所在的树枝的根的距离 < m 离这个根的距离时是 YES
否则就是NO
实现就很简单,先去树上找环,然后找出这个根,分别给a 和…
今日份题目:
给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序)
graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节…
有一个邮递员要送东西,邮局在节点 1 1 1。他总共要送 n − 1 n−1 n−1样东西,其目的地分别是节点 2 2 2到节点 n n n。所有的道路都是单行的,共有 m m m条道路。邮递员每次只能带一样东西,运送每件物品过后必须返回邮局。求送完东…
Leetcode 3017. Count the Number of Houses at a Certain Distance II 1. 解题思路2. 代码实现 题目链接:3017. Count the Number of Houses at a Certain Distance II
1. 解题思路
这一题其实思路上还是比较简单的,显然任何一个图都可以拆分为以下三…
解析: 并查集,求每个集合的最小费用。 每次合并集合的时候,根节点保存当前集合最小的费用。
#include<bits/stdc.h>
using namespace std;
#define int long long
const int N1e55;
int n,m,a[N],p[N],cnt[N];
int find(int x){retur…
题目链接:有边数限制的最短路 #include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N 510, M 10010;int n, m, k;
int dist[N], backup[N];// 存放边的信息
struct Edge
{int a, b, w;
}edges[M];void …
图的存储
B3643 图的存储 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:mp[n][n]用来存邻接矩阵,二维vector用来存每个点连的点
完整代码:
#include <bits/stdc.h>
#define int long long
const int N 1e5 10;
int n, m;
…
C F 786 B − L e g a c y \mathrm{CF786B - Legacy} CF786B−Legacy D e s c r i p t i o n \mathrm{Description} Description
给定 1 1 1 张 n n n 个点的有向图,初始没有边,接下来有 q q q 次操作,形式如下:
1 u v w 表示…
答案:
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
class Solution {public List<Integer> distanceK(TreeNode root, TreeNode tar…
当时只做出来4个题,被两个学弟的队伍压了一题,可能是因为两个中等题都偏向构造和猜结论这种,我们队伍不太擅长,需要加强这方面的训练。
C Cheeeeen the Cute Cat(图论)
说实话不看题解,还是很…
P8794 [蓝桥杯 2022 国 A] 环境治理 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <iostream>
using namespace std;
#define ll long long
const int N150;
const int inf0x7fffffff;
int n,q;
int d[N][N],l[N][N];
int t[N][N];
void floyd()
{for(int k0…
图的存储
B3643 图的存储 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:mp[n][n]用来存邻接矩阵,二维vector用来存每个点连的点
完整代码:
#include <bits/stdc.h>
#define int long long
const int N 1e5 10;
int n, m;
…
Problem - E - Codeforces
题目大意:有一棵n个点的树,初始状态下所有点都是白色的,每次操作可以选择一个点u和一个距离dis,使得距离点u所有长度为dis的点变为黑色,问最少需要多少次操作能使所有点变成黑色,…
网址如下:
Play on Words - UVA 10129 - Virtual Judge (vjudge.net)
(第三方网站) 一道关于有向欧拉回路的题,其中字母为节点,单词为道路
满足存在欧拉回路的条件有两个:
1,最多有两个奇点…
题目:http://acm.hdu.edu.cn/showproblem.php?pid3549 Flow Problem
Time Limit: 5000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 11114 Accepted Submission(s): 5271
Problem Description
Network flow…
文章目录G.The WitchwoodF.Kobolds and CatacombsK.Scholomance AcademyD.Journey to UnGoro补题链接:https://ac.nowcoder.com/acm/contest/18713 https://codeforces.com/gym/103202
G.The Witchwood
G. The Witchwood time limit per test2 seconds memory lim…
C 23 实用工具(二)绑定工具 Adaptors for Functions
std::bind、std::bind_front、std::bind_back和std::function这四个函数非常适合一起使用。
其中,std::bind、std::bind_front和std::bind_back可以让您即时创建新的函数对象,…
1.两重二for循环维护次大值 这里我就直接用map维护了,多了个logn复杂度还是可以的,下面是AC代码:
#include<bits/stdc.h>
using namespace std;
int n,a[1010];
map<int,int> mp;
int main(){cin>>n;int sum0;map<int,…
第三题:T3工作安排
标签:结构体排序、贪心算法 题意:有 n n n份任务。完成第 i i i份任务需要 t i t_i ti的时间,在这份任务没有完成之前,每一个单位时间会收到 f i f_i fi单位的罚款。求以什么顺序安排这些任务&…
一、约数
1. 试除法求约数
最朴素的办法是遍历1 ~ n(不是从2开始),如果能被n整除,就输出。但是,类比质数的求法,约数都是成对出现的,因此只需要遍历到根号n即可。for(int i = 1; i <= x / i; ++i),但是需要注意的是,如果这个数是个平方数,则存在正好卡在 x / i …
排队接水
题目描述
有 n n n 个人在一个水龙头前排队接水,假如每个人接水的时间为 T i T_i Ti,请编程找出这 n n n 个人排队的一种顺序,使得 n n n 个人的平均等待时间最小。
输入格式
第一行为一个整数 n n n。
第二行 n n n 个…
Problem - D - Codeforces 给定一个由 n 个顶点和 m 条边组成的无向连通加权图。将从顶点 1 到顶点 i 的最短路径长度表示为 di。
你必须删除一些图中的边,使得最多只保留 k 条边。如果在删除边后,仍然存在从 1 到 i 的路径,其长度为 di&…
给定三个整数数组
A [A1, A2, … AN],
B [B1, B2, … BN],
C [C1, C2, … CN],
请你统计有多少个三元组(i, j, k) 满足:
1 < i, j, k < N Ai < Bj < Ck
输入格式
第一行包含一个整数N。
第二行包含N个整数A1, A2, … AN。
第三行…
2023.4.1:更新抽象
又是鸽了三千万年... -------------------------------------------------------------------- 题目描述 Bessie and her friends are playing hoofball in the annual Superbull championship, and Farmer John is in charge of making the tou…
Problem - E - Codeforces 有人给Ivan一个奇怪的生日礼物,这是一只刺猬 - 一个连通的无向图,其中一个顶点的度至少为3(我们称其为中心),而所有其他顶点的度数均为1。Ivan认为刺猬太无聊了,决定自己制造k-多…
文章目录一、A - Ian Visits Mary二、B - Grid Reconstruction三、C - Ian and Array Sorting四、D - Sum Graph一、A - Ian Visits Mary 思路: 思维题,仔细观察发现.要想他们中间没有数字,那我们就第一步先走到(1,b - 1),然后再从(1,b - 1)走到(a,b) 代码:
#include<bit…
深搜其实用的就是栈,虽然不是手写的栈,但是递归函数就是在调用系统的栈。
dfs基础篇
(1)排列数字
#include<cstdio>
int N;
int path[15], vis[15];
void dfs(int u) {if (u N) {for (int i 0; i < N; i) printf(&q…
传送门:CF
本场因为C题赛时被题意绕晕了,导致狠狠的掉分(准确的来说是题意没有想错但是自己的脑子被绕晕了)
A题:A. LuoTianyi and the Palindrome String
考虑暴力进行循环,找到所有所有不同的字符对(不妨记为 [ l , r ] [l,r] [l,r]).那么对于这个字符区间来说,显然中间的…
Marking
题目描述 输入输出 #include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{return b0?a:gcd(b,a%b);
}
int main()
{ll t;cin>>t;ll n,d,k;while(t--){cin>>n>>d>>k;k--;if(g…
1. Kruskal算法
const int maxn1e6;
int n,m;//点数,边数
int u[maxn],v[maxn],w[maxn];//第i条边的两个端点序号和权值
int r[maxn];//排序后第i小的边的序号
int cmp(const int i,const int j){ return w[i]<w[j]; }//间接比较函数
int find(int x){//并查集…
分数 25
全屏浏览题目
切换布局
作者 CHEN, Yue
单位 浙江大学
Given a tree, you are supposed to tell if it is a complete binary tree.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N …
分数 30
全屏浏览题目
作者 CHEN, Yue
单位 浙江大学
One way that the police finds the head of a gang is to check peoples phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the …
图论
2-SAT加边
1. x and y false说明两者不能同时选(x,true)->(y,false),(y,true)->(x,false)
2. x or y true说明两者不能同时不选(x,false)->(y,true),(y,false)->(x,true)
3. x xor y true说明两者不能一样(x,true)->(y,false),(y,true)->(x,false)…
分数 25
全屏浏览题目
作者 CHEN, Yue
单位 浙江大学
The "Hamilton cycle problem" is to find a simple cycle that contains every vertex in a graph. Such a cycle is called a "Hamiltonian cycle".
In this problem, you are supposed to tell…
教学地址:
普里姆算法
算法核心:
(T集合包含生成树中的结点,V集合包含所有结点) 在连接T内顶点与V-T内顶点的边中选取权值最小的边(pu,u),将其作为MST(最小生成树)的边,并添加u至T中! 代码实现:
#include <bits/stdc.h>#define ll long long
using namespace std;con…
石子合并(弱化版)
题目描述
https://www.luogu.com.cn/problem/P1775
设有 N ( N ≤ 300 ) N(N \le 300) N(N≤300) 堆石子排成一排,其编号为 1 , 2 , 3 , ⋯ , N 1,2,3,\cdots,N 1,2,3,⋯,N。每堆石子有一定的质量 m i ( m i ≤ 1000 …
强连通分量(SCC, Strongly Connected Component) 强连通分量的概念强连通分量的应用强连通分量的算法——Tarjan算法 强连通分量的概念
在有向图中,任意两个顶点 v i v_i vi 和 v j v_j vj 互相可达(也即存在路径 v i → v…
参考:https://www.luogu.com.cn/problem/P8671 参考:https://zhuanlan.zhihu.com/p/121159246 参考:https://blog.csdn.net/doge__/article/details/82429348
#include <bits/stdc.h>
using namespace std;
int n,k,s;
int main(){cin>>n>>k;for(int i2;i&…
A - First Player
AC代码:
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N110;
struct node{string name;int age;
}q[N];
int main()
{int n;cin>>n;for(int i1;i<n;i) cin>>q[i…
7-12 关于堆的判断
分数 25 全屏浏览题目 切换布局
作者 陈越
单位 浙江大学
将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种:
x is the root:x是根结点;x and y are siblings&…
0. 0. 0.写在前面
最短路算法一般在算法竞赛中有四种比较常见, F l o y d Floyd Floyd算法, B e l l m a n − F o r d Bellman-Ford Bellman−Ford算法, D i j k s t r a Dijkstra Dijkstra算法, S P F A SPFA SPFA算法。 F l …
一、拓扑排序
1.简介
拓扑排序的英文名是 Topological sorting。拓扑排序要解决的问题是给一个图的所有节点排序,目标是将所有节点排序,使得排在前面的节点不能依赖于排在后面的节点。
在一个 D A G DAG DAG(有向无环图)中&…
1004 Counting Leaves
分数 30 全屏浏览题目 切换布局
作者 CHEN, Yue
单位 浙江大学
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
Input Specification:
Each input file contains one…
K r u s k a l Kruskal Kruskal 算法 K r u s k a l Kruskal Kruskal 算法是一种求解最小生成树的贪心算法。它的基本思想是从图中的边集中依次选取边,使得选出的边不会构成回路,并且满足边权和最小。
具体实现过程如下: 将原图中的所有边按…
题目来源:PAT (Advanced Level) Practice
It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to …
目录
MGraph类
构造函数
深度优先遍历
广度优先遍历 MGraph类
const int N 10;
int visit[N]; // 顶点是否被访问
template<typename DataType>
class MGraph//无向图
{
public:MGraph(DataType a[], int n, int e);~MGraph(){}void DF(int x); //深度优先遍历void…
普里姆算法最小生成树What to Learn? 学什么? How to construct minimum spanning tree using Prims Minimum Spanning Tree algorithm and its C implementation? 如何使用Prim的最小生成树算法及其C 实现构造最小生成树? Minimum Spanning Tree is…
题目描述 给出 n 个点的一棵树,多次询问两点之间的最短距离。
注意:边是双向的。
输入格式 第一行为两个整数 n 和 m。n 表示点数,m 表示询问次数;
下来 n-1 行,每行三个整数 x ,y, k,表示点 x 和点 y 之…
SPFA模板啦~
直接上ACcode: #include<bits/stdc.h>
using namespace std;
//#define int long long
#define inf 2147483647
const int N15e310,M2*N;
int dis[N],head[N],cnt;
bool vis[N];
int n,m;
struct E {int to,w,next;
} e[M];
queue<int>q;
void add(in…
无向图中的顶点用数组的索引表示,该索引中的元素用bag表示,而这些元素指的是索引对应的顶点所连接的顶点。
public class Graph {private final int V;// 顶点个数private int E;// 边的数目private Bag<Integer> adj[];// 邻接表//初始化邻接表p…
文章目录B Chessboard 上下界最小费用最大流C cities 区间dpH Hard Calculation 简单题I Mr. Main and Windmills 计算几何J Parallel Sort 思维模拟第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(昆明)我们只做了H题,水题。。…
力扣-图论 深度优先搜索 剑指 Offer II 111. 计算除法 我的题解: **思路:*字符串a / b 2.0 , b / c 3.0 可以求: b / c 3.0, c / b 1.0 / 3.0, 因此我们可以将a / b描述为从a到b的一条边,这样就抽象画出一张图,我们将所有的点与权值加入图中…
文章目录题236.pat甲级练习-1072 Gas Station (30 分)一、题目二、题解题236.pat甲级练习-1072 Gas Station (30 分) 一、题目 二、题解 本题要求得到一个最好位置的加油站,该加油站到houses的距离中的最短距离需要在所有加油站这方面中是最大的,即求最大…
import numpy as np
def distl(matrix,starPoint):M 1E100dist[M]*len(matrix)#用于存放距离findPonit[]#用于存放已经找到的点unFindPoint[i for i in range(len(matrix))]#用于存放没有找到的点Finallpath[[]]*len(matrix)#用于存放路径dist[starPoint]0findPonit.append(st…
Link
思路
感觉方法很妙的一道题,用类似kruskal的方法,每次合并两个联通块x, y时,假设这条边长度为 www,若要构成完全图,则我们需要额外添加SxSy−1S_xS_y-1SxSy−1条边,其中SiS_iSi表示第 iii 个连…
link
G.小沙的身法
由于给出的是一个树,所以两点间简单路径唯一。考虑极端情况,给出的n个点构成一条链,可以用前缀和求解,所以容易想到用lca通过类似方法计算。
const int maxn 1e6 10;
int n, m;
int vis2[maxn];
int a[max…
树的重心
给定一颗树,树中包含 n n n 个结点(编号 1 ∼ n 1∼n 1∼n)和 n − 1 n−1 n−1条无向边。请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。 重心定义: 重心是指树中的一…
AcWing 每日一题 2022/5/9【3371. 舒适的奶牛】
Farmer John 的草地可以被看作是一个由正方形方格组成的巨大的二维方阵(想象一个巨大的棋盘)。
初始时,草地上是空的。
Farmer John 将会逐一地将 N 头奶牛加入到草地上。
第 i 头奶牛将会…
Choose the best route
One day , Kiki wants to visit one of her friends. As she is liable to carsickness , she wants to arrive at her friend’s home as soon as possible . Now give you a map of the city’s traffic route, and the stations which are near Kiki…
数据结构–BFS求最短路 BFS求⽆权图的单源最短路径
注:⽆权图可以视为⼀种特殊的带权图,只是每条边的权值都为1 以 2 为 b e g i n 位置 以2为begin位置 以2为begin位置 代码实现
//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u…
原题链接:活动 - AcWing
给定一个 nn 个点 mm 条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你求出 11 号点到 nn 号点的最短距离,如果无法从 11 号点走到 nn 号点,则输出 impossible。
数据保证不存在…
2023牛客第七场补题报告C F L M
C-Beautiful Sequence_2023牛客暑期多校训练营7 (nowcoder.com)
思路
观察到数组一定是递增的,所以从最高位往下考虑每位的1最多只有一个,然后按位枚举贪心即可。
代码
#include <bits/stdc.h>
using namespac…
明天比赛了,让我这个临时抱佛脚的选手写个图论题,练练手。
1.Dijkstra
#include<bits/stdc.h>
#define x first
#define y secondusing namespace std;
typedef pair<int,int> PII;
const int MAX 2100;
const int INF 0x3f3f3f3f;vecto…
Floyd求最短路
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,边权可能为负数。
再给定 k 个询问,每个询问包含两个整数 x 和 y,表示查询从点 x 到点 y 的最短距离,如果路径不存在,则输出 impo…
个人学习记录,代码难免不尽人意。 It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to repair a…
【题目来源】http://oj.ecustacm.cn/problem.php?id1850http://oj.ecustacm.cn/viewnews.php?id1023【题目描述】 给定 n 个小球,编号为 1-n,给定 m 个篮子,编号为 1-m。 每个球只允许放入样例给定的编号为 Ai 或者 Bi 的两个篮子中的 1 个…
数据结构–最短路径 Dijkstra算法 Dijkstra算法 计算 b e g i n 点到各个点的最短路 \color{red}计算\ begin\ 点到各个点的最短路 计算 begin 点到各个点的最短路 如果是无向图,可以先把无向图转化成有向图 我们需要2个数组 final[] (标记各顶点是否已…
实验任务
(1) 掌握Kruskal最小生成树算法; (2) 掌握Prim最小生成树算法。
实验内容
(1) 随机生成一个无向网 G ( V, E ),V { A, B, C, D, E, F },| E | 11,边的权值取值范围为 [ 1, 40 ]; (2) 使用Prim算法求出图…
来源:“范式杯”2023牛客暑期多校训练营10 —— L Grayscale Confusion 题意:给定 n 个三元组 ( r i , g i , b i ) 。构造一个长度为 n 的数组 w, 使得 ①w1 w 2 ②对于任意 i, j ,若 r i > r j , g i > g …
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>using namespace std;const int N 100010, M 2*N;int h[N], e[M], ne[M], idx;bool st[N];// dfs只搜索一遍// 有向图邻接表存储
void add(int a, int b){e[idx] b;ne[…
Problem - E - Codeforces
题意: 思路:
st 到 ed存在多条路径
注意到在同一个边双连通分量中,如果存在一条边的边权是1,那么这个边双连通分量中所有点对的路径中都存在一条边的边权是1,因此我们考虑缩点,…
虚树
在给定的树上问题中,树的大小过大,导致总时间复杂度 O ( n q ) O(nq) O(nq)不能被接受,但是有很多点在查询的过程中根本用不到,所以对于每一个查询,建立一个小的查询树,在这个小树上求解问题。这个小…
点此查看所有题目集 At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the records of signing ins and outs, you are supposed to find the ones who have…
C. Infected Tree
Problem - C - Codeforces
问题描述:一个二叉树,根节点被感染了,可以通过删除一个节点使这个树分成两个部分,从而使分离开的子树无法被感染,求这样操作,有最多多少个节点是未被感染的&a…
#include <bits/stdc.h>
using namespace std;
using VI vector<int>;
int n,m;
int close[110];
int open[110];
int dp[1 << 12];
int vis[1 << 12];
//n个灯 m 个 按钮
// n < 10
//dp[0] 0;
//按下一个按钮 , 先把状态 | 开…
判断一个非负序列是否为某简单图的度序列有两种方法 import numpy as np
import networkx as nx
import matplotlib.pyplot as pltdef hh_algorithm(graph_list):"""Havel-Hakimi algorithm:param graph_list: 非负序列:return: 是否可图True or False"&qu…
LeetCode 130- 被围绕的区域
题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
题目描述:给你一个 m x n 的矩阵 board ,由若干字符 X 和 O ,找到所有被 X 围绕的区域,并将这些区域…
A - QQ solver (atcoder.jp)直接按题意模拟即可。
B - Caesar Cipher (atcoder.jp)按题意模拟即可
C - Graph Isomorphism (atcoder.jp)按题意模拟即可
D - Weak Takahashi (atcoder.jp) 一个非常套路的网格dp
E - Rook Path (atcoder.jp) (1)题意 有…
有点难😅
发现 x , y x,y x,y在一个强连通块内,这样一定有环🤔
发现可以找到强连通块内所有环长度的 gcd \gcd gcd,这样从 x x x到 y y y的所有路径的长度都模这个数同余,又因为 K K K非常大,所以我们…
[NOIP2002 普及组] 产生数
题目描述
给出一个整数 n n n 和 k k k 个变换规则。
规则:
一位数可变换成另一个一位数。规则的右部不能为零。
例如: n 234 , k 2 n234,k2 n234,k2。有以下两个规则: 2 ⟶ 5 2\longrightarrow 5 2⟶5。 …
【模板】拓扑排序 / 家谱树 - 洛谷
终于凭着仅存的记忆写出来了,虽然是板子题
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;const int N 1010;
int e[N], ne[N], h[N], idx;
int n, ind[N];
queue<int&g…
Problem - D - Codeforces
题目大意:有一个长度为n的数组a,每次操作可以选取一个长度为k的所有数互不相同的数组b,令a[bi]b[i%k1],问能否将一个全为零的数组通过任意次操作得到a
1<k<n<1e5
思路:通过上述操…
文章目录 一维差分二维差分 一维差分
#include
using namespace std; const int N 1e5 10; int s[N], a[N];
void insert(int l, int r, int x){ a[l] x; a[r 1] - x; }
int main(){ int n, m; cin >> n >> m;
for (int i 1; i < n; i ){cin >>…
F. We Were Both Children 题意:n只青蛙初始在0处,每只青蛙都有一个a[i]表示青蛙每次能跳a[i],我们可以在1~n的位置处放置一个陷阱,每只青蛙经过陷阱后会掉进陷阱,求最多能捕获多少只青蛙。 思路:我们观察a[i]的范围很…
题目描述 D D D 市有 n n n 个公交车站和 m m m 条公交线路,公交车站的编号为从 1 1 1到 n n n 。每条公交线路会经过某些车站,如果两条公交线路有公共的公交车站,那么它们可以在公共车站相互换乘。比如线路 ( 1 , 2 , 3 , 9…
引
对老师布置的题目稍微记录一下吧 也算对树形 D P DP DP 的巩固
T1 Ostap and Tree
题目传送门 由于有 距离 k 距离k 距离k 的限制,设计二维 d p dp dp
设计状态: f i , j : i 的子树内,离 i 最近的染色点与 i 距离为 j 且若 j <…
定长路径计数 给一个 n n n 阶有向图,每条边的边权均为 1 1 1,然后给一个整数 k k k,你的任务是对于所有点对 ( u , v ) (u,v) (u,v) 求出从 u u u 到 v v v 长度为 k k k 的路径的数量 乘法原理 P4159 [SCOI2009] 迷路 拆点建边 P2151…
代码:
class Solution {int[][] dirs {{-1,0},{1,0},{0,1},{0,-1}};public int maxAreaOfIsland(int[][] grid) {int max 0;for(int i0;i<grid.length;i){for(int j0;j<grid[0].length;j){if(grid[i][j]1){int[] start {i,j};int area getArea(start,0,g…
[TJOI2007] 线段 - 洛谷 #include<bits/stdc.h>
using namespace std;
const int N2e410;
int n;
int f[N][2],a[N][2];
int dis(int a,int b)
{return abs(a-b);
}
int main()
{scanf("%d",&n);for(int i1;i<n;i)scanf("%d %d",&a[i][0]…
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、力扣62. 不同路径二、力扣63. 不同路径 II 前言 一、力扣62. 不同路径
class Solution {public int uniquePaths(int m, int n) {int[][] dp new int[m][…
题目描述
给定一个 n n n 个点的基环树,现在对基环树上的点染色,使得每个点都有且仅有一个与他相连的点(不包括它自身)被染色,求最少的染色点数,或者返回无解。 n n n 个点, n n n条边的连通无…
给定一张 n n n 个顶点 m m m 条边的无向图,顶点的编号在 1 ∼ n 1 \sim n 1∼n 内,第 i i i 条无向边连接着顶点 x i x_i xi 与 y i y_i yi。
我们称顶点 v 0 , v 1 , ⋯ , v k − 1 v_0,v_1,\cdots, v_{k-1} v0,v1,⋯,vk−1 构成了一…
Problem A: Here Comes Santa Claus
给一个数列,要求分成若干组,要求每组至少2个数,使得所有组中位数的最大值与最小值之差尽量大,求这个值。
#include<bits/stdc.h>
using namespace std;
#define For(i,n) for(int i1;…
生成树:删去一些边,使图变成树。 对于 n n n 个点的图,生成树有 n − 1 n-1 n−1 条边。 最小生成树:所有生成树中边权最小的。 对于一个图,不存在最大/最小生成树的条件是并查集里面没有 n n n 个点,…
2.概念与计算
2.1 图的定义
图(graph) G G G 是一个有序的三元组,记作 G < V ( G ) , E ( G ) , ψ ( G ) > G<V(G),E(G),\psi (G)> G<V(G),E(G),ψ(G)>。 V ( G ) V(G) V(G) 是顶点集。 E ( G ) E(G) E(G) 是边集。 ψ ( G ) \psi (G) ψ(G…
题目
给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环,边权可能为负数。
求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G(V,E),其中 V 表示图中点的集合,E…
URL:https://codeforces.com/contest/1890
目录
A
Problem/题意
Thought/思路
Code/代码
B
Problem/题意
Thought/思路
Code/代码
C
Problem/题意
Thought/思路
Code/代码
D
Problem/题意
Thought/思路
Code/代码 A
Problem/题意
给出一个数组 A…
次小生成树有严格次小生成树和非严格次小生成树之分。常见的是严格次小生成树。
严格次小生成树的定义如下: 如果最小生成树选择的边集是 E M E_M EM,严格次小生成树选择的边集是 E S E_S ES,那么需要满足:( v a l u e ( e…
通信线路 思路:我们考虑需要升级的那条电缆的花费,若其花费为 w ,那么从 1 到 n 的路径上,至多存在 k 条路径的价值大于 w ,这具有一定的单调性,当花费 w 越大,我们路径上价值大于 w 的花费会越…
文章目录 示例代码 示例 最短路径: A -> C -> D -> F -> E -> G 长度 16 代码
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graphviz.h…
NOIP2023模拟4联测25 B. 多边形 文章目录 NOIP2023模拟4联测25 B. 多边形题目大意思路code 题目大意
给你一个正 n n n 边形,每个点有三种颜色,红、蓝、绿。现在你想要连接 n − 3 n - 3 n−3 条对角线,使得这些对角线把整个图形分成了 n…
“六度空间”理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如图1所示…
题目分析:
这道题还是比较裸的一道书上差分的题目了 对于每一对标记点(x,y) 他们之间的路径就是 x − > L C A ( x , y ) − > y x->LCA(x,y)->y x−>LCA(x,y)−>y 这条路径上的每一条边都要经过。
那么对于一条边,什么时候砍掉这条…
字符串哈希 核心思想:用p(131或者13331)进制数储存字符串每一位数的hash值 L—R的哈希值 h[R]-h[L-1]*PR-L1 哈希值很大—>modQ(264)变小 用unsigned long long 存 (出界) #include<iostream>using namespace std;typedef unsigned long long ULL;co…
六、图与网络分析
最大流问题
最大流问题的数学规划模型为: max v f 12 f 13 { f 12 f 13 − f 57 − f 67 0 f 13 f 23 f 34 f 35 . . . 0 ≤ f i j ≤ c i j \max vf_{12}f_{13}\\ \begin{cases} f_{12}f_{13}-f_{57}-f_{67}0 \\ f_{13}f_{23}f_{34}f…
如果一个无向图存在一笔画,则一笔画的路径叫做欧拉路,如果最后又回到起点,那这个路径叫做欧拉回路。
#include<bits/stdc.h>
using namespace std;
#define N 510
int g[N][N],d[N],c[N],n,m,reckon,oddity_point,lt;
void dfs(int i)…
文章目录 1. P a g e R a n k PageRank PageRank算法背景2. P a g e R a n k PageRank PageRank算法基础2.1. P a g e R a n k PageRank PageRank问题描述2.2.有向图模型2.3.随机游走模型 3. P a g e R a n k PageRank PageRank算法定义3.1. P a g e R a n k PageRank PageRank…
文章目录 EK求最大流题目描述输入格式输出格式数据范围 算法步骤算法时间复杂度 O ( n m 2 ) O(nm^2) O(nm2) AC CodeDinic/ISAP求最大流题目描述输入格式输出格式数据范围 算法步骤算法时间复杂度 O ( n 2 m ) O(n^2m) O(n2m) AC CodeDinic/ISAP求最小割EK求费用流题目描述输…
A 统计一下每个字母的出现次数然后输出即可
#include <bits/stdc.h>
#define rep(i,a,b) for(register int i (a); i < (b); i)
#define fep(i,a,b) for(register int i (a); i > (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair&l…
文章目录 流网路残留网络增广路径割最大流最小割定理最大流Edmonds-Karp 算法算法步骤程序代码时间复杂度 流网路
流网络: G ( V , E ) G (V, E) G(V,E) 有向图,不考虑反向边s:源点t:汇点 c ( u , v ) c(u, v) c(u,v)ÿ…
最小生成树
p算法是往树里加点,k算法是往树里加边
prim
#include<iostream>
#include<queue>
using namespace std;
#define re register
#define il inline
il int read() {re int x 0, f 1; char c getchar();while (c < 0 || c>9) { if …
C/C++等级考试(1~8级)全部真题・点这里 第1题:道路
N个以 1 … N 标号的城市通过单向的道路相连:。每条道路包含两个参数:道路的长度和需要为该路付的通行费(以金币的数目来表示) Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后,Bob和她…
P2149 Elaxia的路线 D e s c r i p t i o n \mathrm{Description} Description
给定 n n n 个点, m m m 条边的无向图,求 2 2 2 个点对间最短路的最长公共路径 S o l u t i o n \mathrm{Solution} Solution
最短路有可能不唯一,所以公共路…
P5304 旅行者 D e s c r i p t i o n \mathrm{Description} Description
给定一个 n n n 个点, m m m 条边的有向图,求解 k k k 个点两两间最短路长度的最小值。 S o l u t i o n \mathrm{Solution} Solution
对于 k k k 个点,可以考虑二…
文章目录 A - Amusement Arcade题意:题解:代码: B - Brexiting and Brentering题意:题解:代码: I - Montys Hall题意:题解:代码: A - Amusement Arcade
题意:…
Leetcode204. 计数质数
题目
给定整数 n ,返回 所有小于非负整数 n 的质数的数量 。
代码
class Solution:def countPrimes(self, n: int) -> int:if n < 2:return 0prime_arr [1 for _ in range(n)]prime_arr[0], prime_arr[1] 0, 0ls list()for i in…
题目描述
这是上海计算机学会竞赛 P 243 P243 P243:5G通讯( 2020 2020 2020年 9 9 9月月赛 乙组 T 2 T2 T2)标签:二分查找题意:给定 n n n个点,第 i i i个点的坐标为 x i x_i xi。给定限制 d d d&#…
题目 把 i i i 和 i n in in 看作一个点,对所有 a i a_i ai 和 b i b_i bi 连边,得到的图称为 G G G,则 G G G 的割边 ( a i , b i ) (a_i,b_i) (ai,bi) 在原图中 ( a i , b i n ) (a_i,b_in) (ai,bin) 或 ( a i n ,…
4979. 合适的环 - AcWing题库 给定一个 n 个点 m 条边的无向图。 图中不含重边和自环。 请你在图中选出一个由三个点组成的环。 设图中一共有 x 条边满足:不在选择的环内,且与选择的环内某个点相连。 我们希望通过合理选环,使得 x 的值尽可能…
砝码承重
【问题描述】 你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W1,W2,...,WN。请你计算一共可以称出多少种不同的正整数重量?注意砝码可以放在天平两边。【输入格式】 输入的第一行包含一个整数 N。第二行包含 N 个整数:W1,W2,W3,.…
原题链接:E. AND-MEX Walk 题目大意: 给出一张 n n n 个点 m m m 条边的无向图,边带有边权。
我们定义一条路径的价值为:
假设我们经过了 k k k 个点(点和边都可重复经过),且按顺序经过的边…
(总分100,考试时间90分钟) 一、选择题 1. 设有以下语句: charx3,y6,z; zx^y<<2; 则z的二进制值是( )。 A. 00010100 B. 00011011 C. 00011100 D. 00011000 …
P2371 墨墨的等式 D e s c r i p t i o n \mathrm{Description} Description
求解有多少个 b ∈ [ l , r ] b\in [l,r] b∈[l,r] 满足 ∑ i 1 n a i x i b \sum\limits_{i1}^n a_ix_ib i1∑naixib 存在非负整数解( x i x_i xi 为变量, a a …
C F 715 B − C o m p l e t e T h e G r a p h \mathrm{CF715B - Complete\ The\ Graph} CF715B−Complete The Graph D e s c r i p t i o n \mathrm{Description} Description
给定一张 n n n 个点, m m m 条边的无向图,点的编号为 0 ∼ n − 1 0\…
1、B站视频链接:D01 拓扑排序_哔哩哔哩_bilibili #include <bits/stdc.h>
using namespace std;
const int N100010;
int n,m,a,b;
vector<int> e[N],tp;
int din[N];
bool topsort(){queue<int> q;for(int i1;i<n;i){if(din[i]0)q.push(i);}…
原题链接:E. Matrix Problem 题目大意: 给出一个 n n n 行 m m m 列的 0 / 1 0/1 0/1 矩阵,再给出一些限制条件:一个长为 n n n 的数组 a a a,和一个长为 m m m 的数组 b b b 。
其中 a i a_{i} ai 表示第 …
P1135
#include<iostream> #include<algorithm> #include<cstring>
using namespace std;
const int N 10010;
int n, A, B; int evlt[N]; int res 1e9; bool st[N]; //存每层楼走没走过
//当前在x楼, 当前按了cnt次按钮 void dfs(int x, int cnt) …
活动 - AcWing
给定一个包含 n 个点 m 条边的有向图,并给定每条边的容量,边的容量非负。
图中可能存在重边和自环。求从点 S 到点 T 的最小割。
输入格式
第一行包含四个整数 n,m,S,T。
接下来 m 行,每行三个整数 u,v,c,表示…
力扣第381场周赛 文章目录 力扣第381场周赛输入单词需要的最少按键次数 I按距离统计房屋对数目 I输入单词需要的最少按键次数 II按距离统计房屋对数目 II 输入单词需要的最少按键次数 I
贪心模拟
class Solution {
public:int minimumPushes(string word) {int n word.size(…
文章目录 题目大意1.输入格式2.输出格式3.数据范围与约定 思路维护每一行区间维护每一列区间维护区间最大值code↓ 完结撒花( ̄▽ ̄) / 题目大意
给定 n , m , r , s n,m,r,s n,m,r,s 和一个 n m n\times m nm 的整数矩阵 A A A,求它每个 …
我这里主要写代码,定义等参考图论基础和表示 | 菜鸟教程
一、邻接矩阵代码实现
public class AdjacencyMatrix {private int n;//节点数private int m;//边数private boolean directed;//是否为有向图private int[][] data;//图数据// 构造一个没有边的邻接矩阵pu…
Going Home
Here 解题思路
模板 二分图最优匹配,前提是有完美匹配(即存在一一配对)左右集合分别有顶标,当时,为有效边,即选中初始对于左集合每个点,选择其连边中最优的,然后对于每…
Title: 贝叶斯树增量式更新的细嚼慢咽 —— Notes for “The Bayes Tree: An Algorithmic Foundation for Probabilistic Robot Mapping” 文章目录 I. 前言II. 贝叶斯树的构建关系III. 贝叶斯树增量式更新的基础IV. 贝叶斯树增量式更新的算法V. 贝叶斯树增量式更新的实例VI. 总…
1.深度优先搜索
深度优先搜索(DFS,Depth First Search)是一种用于遍历或搜索树或图的算法。它将当前状态按照一定的规则顺序,先拓展一步得到一个新状态,再对这个新状态递归拓展下去。如果无法拓展,则退回…
文章目录 邻接矩阵洛谷3643 图的存储 邻接矩阵
邻接矩阵相比于上一篇博客邻接表的讲解要简单得多
数据结构,如果将二维数组 g g g 定义为全局变量,那默认初始化应该为 0 0 0 ,如果题目中存在自环,可以做特判, m e …
Welsh, D.J.A. and Powell, M.B. (1967) An Upper Bound for the Chromatic Number of a Graph and Its Application to Timetabling Problems. 《The Computer Journal》, 10, 85-86. 《The Computer Journal》 1 图着色算法概述
1967年,Welsh和Powell算法引入了…
DFS 模板 #include<bits/stdc.h>
using namespace std;
const int N20;
int dp[N][N];
int a[N],len;
int n,m;//pos 代表当前位置 limit是当前位置是否有这个枚举范围限制int dfs(int pos,int pre,int limit){if(!pos)return 1;if(!limit&&~dp[pos][pre])return…
P3379 【模板】最近公共祖先(LCA) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc.h>
#include<cstdio>
using namespace std;
const int N5e5100;
const int inf0x3f3f3f;
int n,m,s;
vector<int>g[N];
int dep[…
/* 指数型枚举(每个数有选和不选两种情况) #include<bits/stdc.h> using namespace std; const int N20; int n; int st[N];//记录每个数的状态,0还没有考虑,1表示选这个数,2表示不选这个数 void dfs(int x){/…
P8605 [蓝桥杯 2013 国 AC] 网络寻路
思路来源于https://www.luogu.com.cn/article/iat8irsf
#include <iostream>
using namespace std;
int n,m;
int q[10010];
int v[100010],u[100010];
long long res;int main()
{cin>>n>>m;for(int i0;i<m;i){cin…
算法:
简单的一个dfs就能过 ac:
#include "iostream"
#include "algorithm"
#include "cstring"
#include "queue"
using std::cin;
using std::cout;
using std::endl;
#define N 110
char a[N][N];
int abook[N][N];
i…
作者 DS课程组
单位 浙江大学
给定一个顺序存储的线性表,请设计一个函数删除所有值大于min而且小于max的元素。删除后表中剩余元素保持顺序存储,并且相对位置不能改变。
函数接口定义:
int Delete( int A[], int L, int minA, int maxA )…
D. Rudolf and the Ball Game
set模拟
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const int N2e510;
set<int>s1,s2;
int main()
{int t…
4.全球变暖 - 蓝桥云课 (lanqiao.cn)
#include <bits/stdc.h>
using namespace std;
#define int long long
const int N1e36;
char a[N][N];
int n;
int xx[]{0,1,-1,0};//右 下 上 左
int yy[]{1,0,0,-1};
int scc0;//涂色器
int clsm[N*N];//用于存储每个颜色是否还有…
B. Two Out of Three
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output You are given an array a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an. You need to find an array b 1 ,…
树的直径——树形 D P 、两次 B F S \Huge{树的直径——树形DP、两次BFS} 树的直径——树形DP、两次BFS 文章目录 树形DP两次BFS 不再详细解释代码,只记录完整模板。 树形DP
可以计算负权边。
时间复杂度: O ( n ) O(n) O(n)。
设 D [ x ] D[x] D[x]表…
抽象数据结构类型
Graphic操作接口
操作接口功能描述操作接口功能描述e()获取图的总边数n()顶点的总数exits(v,u)判断v,u两个顶点是否存在边insert(v) 在顶点集 V 中插入新顶点 v remove(v,u)删除从v 到u的 关联边 remove(v) 将顶点 v 从顶点集中删除 type(v,u)边所属的类型(…
题目链接
NOIP2014提高组D1T2:联合权值
题目描述
无向连通图 G G G 有 n n n 个点, n − 1 n-1 n−1 条边。点从 1 1 1 到 n n n 依次编号,编号为 i i i 的点的权值为 W i W_i Wi,每条边的长度均为 1 1 1。图上两点 ( u , v ) (…