zzqwtc

未归档

题解(3)

/ 注册

全部文章 / 未归档（共54篇）

迭代加深-双向DFS-IDAstar

迭代加深避免搜索过深但答案在较浅的位置这种情况的发生 AcWing170. 加成序列满足如下条件的序列X（序列中元素被标号为1、2、3…m）被称为“加成序列”： 1、 X [ 1 ] = 1 X[1]=1 X[1]=1 2、 X [ m ] = n X[m]=n X[m]=n 3、...

2021-01-25

0 540

单源最短路的建图方式

最短路算法及其时间复杂度单源最短路 D i j k s t r a Dijkstra Dijkstra O ( n 2 ) O(n^2) O(n2) 堆优化版的 D i j k s t r a Dijkstra Dijkstra O ( m l o g n ) O(mlogn) O(m...

2021-01-25

0 430

单源最短路的综合应用

Acwing 1135 新年好重庆城里有 n 个车站，m 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。佳佳的家在车...

2021-01-25

0 508

Codeforces Round #689 Div. 2 （A-E）

A. String Generation 题意构造一个只包含’a’ ‘b’ 'c’的字符串此字符串中最大回文子串的长度不超过k 思路 'abcabcabc…'这样输出可以保证最大的回文子串的长度为1 代码 #include<bits/stdc++.h> using na...

2021-01-25

0 491

并查集原理

功能 ①：合并两个集合 void merge(int a, int b) { f[Find(a)] = Find(b); } ②：查询某个元素的祖宗节点 int Find(int x) { return x == f[x] ? x : f[x] = Find(f[x])...

2021-01-25

0 430

AcWing1250. 格子游戏

AcWing1250. 格子游戏 Alice和Bob玩了一个古老的游戏：首先画一个 n×n 的点阵（下图 n=3）。接着，他们两个轮流在相邻的点之间画上红边和蓝边：直到围成一个封闭的圈（面积不必为 1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！他...

2021-01-25

0 388

AcWing1252. 搭配购买（并查集+01背包）

AcWing1252. 搭配购买思路先分组再做01背包 Joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有 n 朵云，云朵被编号为 1,2,…,n，并且每朵云都有一个价值。但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。但是Joe...

2021-01-25

0 541

AcWing237. 程序自动分析

AcWing237. 程序自动分析思路先把相等的合并再判断不相等是否与已知条件矛盾在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设 x 1 , x 2 , x 3 x_{1},x_{2},x_{3} x1,x2,x3...

2021-01-25

0 434

AcWing238. 银河英雄传说

AcWing238. 银河英雄传说有一个划分为N列的星际战场，各列依次编号为1,2,…,N。有N艘战舰，也依次编号为1,2,…,N,其中第i号战舰处于第i列。有T条指令，每条指令格式为以下两种之一： 1、M i j，表示让第i号战舰所在列的全部战舰保持原有顺序，接在第j号战舰所在列的尾...

2021-01-25

0 491

AcWing239. 奇偶游戏

AcWing239. 奇偶游戏思路 s i = a 1 + a 2 + ⋯ + a i s_{i} = a_{1} + a_{2} +\dots +a_{i} si=a1+a2+⋯+ai 前i个数中1的个数 s [ l − r ] s[l-r] s[l−r]中有奇数个1 ...

2021-01-25

0 447