uva

**记录** 10:46 2023-5-20 http://uva.onlinejudge.org/external/6/699.html reference:《算法竞赛入门经典第二版》例题6-10 二叉树的层次遍历，边读边写(这些题给我感觉是非常灵活)，对每个节点需要的数据就是在sum数组的位置 ......

~~怎么没有正常的后缀数组二分的题解啊~~ 给定 $n$ 个字符串，求出最长的，在多于 $\left\lfloor\frac{n}{2}\right\rfloor$ 个字符串中出现的子串，并按照字典序从小到大输出。 $n \leq 100$，$|S| \leq 1000$，~~根据套路~~可以将所有 ......

（提醒：原题面是 $m$ 行 $n$ 列，这里改成了 $n$ 行 $m$ 列） 首先很好想到设 $dp_{u,v}$ 为 $(u, v)$ 的期望步数 $dp_{u, v} = \begin{cases}\sum_{i=1}^4 dp_{u + du_i,v + dv_i}\times p_i& ( ......

给定 n，求有多少树满足：任意非叶子节点的儿子不少于 2 ， 叶子节点个数为 n ......

一家饭店，有一扇大小会变得门，变化范围为[0,k]。每过一单位时间你可以让门的大小+1，-1，或者不变。客人会在不同的时间来吃饭，但是如果门的大小和他们希望的值不一样，他们就不会进来并且直接消失。吃饭要花钱，现在问饭店最多能赚多少钱。 F[i ] [j ] =max( F[i-1][j] +v,F[ ......

有四个踩踏板，不同的踩踏方式消耗不同的力气 问最小花费的力气 F[ i ] [ a] [b ][ s] ， s 是上一次哪只角移动了( 0 ,1,2 ) https://www.luogu.com.cn/problem/UVA10618 #include<iostream> #include <cs ......

定义一个三元组(a,b,c)(a⩽b⩽c), 它的权值为 (a−b)^2, 给定 n(n⩽5000)n(n⩽5000) 个数，要求选出 k+8 个三元组，使得这k+8个三元组权值和最小。 输入数据是单调递增的。 #include <iostream> #include <algorithm> #in ......

有n个苹果，和一个数k，第i个苹果的重量是k+i(1<=i<=n). 已知其中只有一个苹果是甜的，所有比它重量轻的都是苦的，比它重的都是酸的。为了要找出甜的苹果，就要去一个一个地吃它，且吃了咬了苹果就必须把它吃完，不管苹果是苦的还是酸的。例如，先吃#1, 如果#1是甜的，花费1如果#2是甜的，那么选 ......

给定两种购买物品的方案：花费 c1元购买 n1 个物品，或者花费 c2c2​ 元购买 n2n2​ 个物品。 方案可以无限使用，询问购买 n个物品至少要多少元，若无法恰好购买到 n 个物品输出 failed #include <iostream> #include <algorithm> #inclu ......

题意：给定一些个d维的方块，给定两点，求穿过多少方块 转化为(0,0) 到 (a,b) 先考虑二维的 然后容斥原理 #include <iostream> #include <algorithm> #include <cstring> #include <cmath> using namespace ......

题意： 给两个串A，B。现在把B串分为若干个部分，对每一个部分进行操作将其变为一个A串，代价为每部分操作次数的最大值 求最小代价 #include <iostream> #include <algorithm> #include <cstring> using namespace std; cons ......

题目大意：给出n，一个无根的树，每条边上都有权值。 现在每个位置都有一个景点，一个人想在一年之内去cnt[ i ] 次景点，所以接下来给出m，表示说在m个位置上有这个人想去的地方，给出位置以及想去的次数（注意，每去一个景点都要返回自己的住处），namo这个人该住在哪里走的路程才最短。 换根dp #i ......

政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di(为正整数)，其中，0<i<m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学(设0<n≤m<500)。请根据给定的m、n以及所有相邻村 ......

每节课的长度为 L，有N个主题，讲每个主题的时间分别是 t1,t2,t3..., 每个主题必须在一节课讲完，不能分两节课。一节课可以将多个主题讲完每节课上完有不满意度。 在所需课程数量最少的前提下，求最小不满意度。 #include <iostream> #include <cstring> #in ......

定两个整数 L,R , 求闭区间 [L,R] 中相邻两个质数差值最小的数对与差值最大的数对。 当存在多个时，输出靠前的素数对。 筛 1e6 每个素数，在区间里标记倍数 #include<iostream> #include <algorithm> #include <cstring> using n ......

有n个影碟，标号为1~n，位置为0~n-1，每次取出一个影碟看完后，将其放在最前面（标号为0处）,问每个影碟取出前，其位置之前有多少个影碟 开2倍数组， "i放置前面" 这个操作 add(i,-1) ,add(newi,1) #include<iostream> #include<cstring> ......

一个步骤： 在[ a, b] 中标记 S 的倍数 #include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=1e5+20; const int ......

已知M 为T1,T2,T3 的LCM 输出满足 Ti-Tj<=25 的所有可能情况 #include<iostream> #include<cmath> #include<algorithm> #include<cstring> using namespace std; const int N= 1 ......

给定一个NxNxN的正方体，求出最多能选几个整数点。使得随意两点PQ不会使PQO共线。 F(k) #include<iostream> #include<cmath> #include<algorithm> using namespace std; const int N=5e5; #define ......

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=5e4; int b[N+2], pm[N+2],tot=0; void init(){ b[1]=1; for(int ......

给出n个点。问选出4个点作为定点，能够组成多少个平行与坐标轴的矩形。 点按照x排序 n^2挑选出 垂直x轴的线段，按照y1排序 #include<iostream> #include<cstring> #include<algorithm> #include<vector> using namesp ......

给你一个递增序列的第一位a1,最后一位an,求有多少个序列满足： 以a1为首，an为尾 1、B(1) = A(1) 2、后面每项满足 A[j]=B[j], A(j-1) < B(j) ≤ A(j), 且bj能整除A(j) - A(j-1)。 F[ i ] [ j ] 最后一位为j 的方案数 #inc ......

记录 23:27 2023-4-20 https://onlinejudge.org/external/1/122.pdf reference:《算法竞赛入门经典第二版》例题6-7 二叉树的层次遍历，这里是直接复制了作者的代码。(之前在我的数据结构学习里面手写过树、二叉树、AVL树(说是手写，其实也 ......

#include <iostream> #include <cstring> #include <queue> using namespace std; const int N=2e5+2; #define int long long int n,m,f1[50][2000] ,f2[50][200 ......

求 1∼n 的排列 A 中，满足前 m 个数中，刚好有 K 个数使得 A[ i ]=i 的 AA 的个数。 错位排列 #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; #define int long long int ......

给定空间里的 n 个点，其中没有三点共线。每两个点之间都用红色或黑色的线段连接。 求 3 条边同色的三角形个数。 n≤1000n≤1000。 同色的= 总数- 杂色的 杂色的直接乘法原理就行，但注意ij 和ji 一样 #include <iostream> #include <cstring> #i ......

写下区间[a,b]的所有数 ,问一共有多少个 0 #include <iostream> #include <cstring> #include <vector> using namespace std; #define int long long int n,f[40][40][2][2] ; v ......

定问在[A,B] 中，有多少个整数本身能被m整除，各个数位上数字之和也能被m整除？ #include <iostream> #include <cstring> #include <vector> using namespace std; vector<int> a; int m,f[40][105 ......

给出一棵树的 dfs 序，求可能的构成方案数。 A______A_______ f[l ][ r] =sum{ f[l+1][k-1] *f[k][j] } #include <iostream> #include <cstring> #include <sstream> using namespa ......

你有一个n×m的网格图，现在你要将K个人放在网格中，满足一下条件： 网格图的四个边都至少有一个人。 每个格子上不能有两个人。 每个人必须都有位置。 注意：四个角的人可以同时算作在两个边上 容斥原理 J=0 时就是 allAnswer #include <iostream> #include <cst ......