搜索结果
查询Tags标签： maxn，共有 417条记录-
【C++】ZZ2193-城市之路 解题精讲
【Horn Coding Studio】CPP编程专栏（狄克斯特拉-算法） 题目 题目描述 罗老师被邀请参加一个舞会，是在城市n，而罗老师当前所处的城市为1,附近还有很多城市2~n-1，有些城市之间没有直接相连的路，有些城市之间有直接相连的路，这些路都是双向的，当然也可能有多条。 现在…
2022/6/5 1:20:27 人评论 次浏览 -
NHOI2022总结
NHOI2022总结 全过程： T1：看到“质约数”时有点懵，但转念一想：“可能跟公约数有点相似”，便随便打了个代码交上去 T2：貌似是暴力枚举，打的代码感觉会爆，但是一时想不出优化方案，先交了 T3（原）：这题跟以前某道贪心题好像啊，不过做到一半突然换题，有点破防 T4…
2022/6/4 23:22:50 人评论 次浏览 -
5.30 NOI 模拟
$5.30\ NOI $模拟 高三大哥最后一次模拟考了,祝他们好运 \(T1\)装箱游戏 显然可以将四种字母之间的空缺当做状态枚举 那么这道题就很显然了 #include<bits/stdc++.h> #define MAXN 305 using namespace std; int n; double f[4][MAXN][MAXN][MAXN],a,b,c,d; bool fl…
2022/5/30 23:19:59 人评论 次浏览 -
C++-小熊的果篮（CSP-J 2021 T4） 解题思路
【Horn Studio】编程专栏：小熊的果篮（CSP-J 2021 T4）解题思路 题目题目描述 小熊的水果店里摆放着一排 nn 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 1,2,…,n1,2,…,n 编号。连续排在一起的同一种水果称为一个"块"。小熊要把这一排水果挑到…
2022/5/29 1:21:02 人评论 次浏览 -
理想的正方形
理想的正方形 二维倍增 SCUACM2022集训前训练-动态规划 - Virtual Judge (vjudge.net) 设 \(maxn[i][j][k]\) 为以 \((i,j)\) 为左上角，边长为 \(2^k\) 的正方形内元素的最大值 #include <iostream> #include <cstring> #include <algorithm> #include…
2022/5/28 23:24:09 人评论 次浏览 -
1268：【例9.12】完全背包问题
1268：【例9.12】完全背包问题 【题目描述】设有nn种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为MM，今从nn种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于MM，而价值的和为最大。【输入】第一行：…
2022/5/25 23:23:54 人评论 次浏览 -
BZOJ-2724 蒲公英
蒲公英 求区间众数 分块 用的蓝书法二做的：预处理每个区间的最大众数，然后二分检查更新答案，同时更新边角的答案，记得分块的数量的是 \(\sqrt{m * log_{2}n}\) 这个代码过不了 acwing 的：https://www.acwing.com/problem/content/251/ #include <iostream> #in…
2022/5/23 23:22:53 人评论 次浏览 -
图论：Ford 算法 求最短路径
Ford 算法 求最短路径先构建邻接表数组和初始化邻接关系int v1[maxn],v2[maxn],w[maxn];//记录起点终点和权值for(int i=1;i<=m;++i){cin>>u>>v>>val;v1[i]=u;v2[i]=v;w[i]=val;}构建一维数组d，记录距离出发点的距离，d[出发点]初始化为0，自己和自…
2022/5/10 17:00:31 人评论 次浏览 -
传递闭包
传递闭包模板#include<iostream> #define maxn 10007 using namespace std; int a[maxn], dis[107][107], n, m; int main(void) {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n;…
2022/5/2 23:42:43 人评论 次浏览 -
差分约束
差分约束模板典型的 $x_u - x_v <= y$ 形式 #include<iostream> #include<cstring> #include<queue> #define maxn 50007 using namespace std; struct edge {int to, val, nxt; }g[maxn]; int n, m, cnt, dis[maxn], hd[maxn], sum[maxn]; bool vis…
2022/5/1 6:14:52 人评论 次浏览 -
2021CCPC女生赛
这篇题解题目的顺序是按照我认为的难度顺序来的。 K.音乐游戏把每一行的字符串读进来之后，直接去计算这个字符串中有多少个\("-"\)字符就可以了 int n; std::cin >> n; i64 ans = 0; rep(i,0,n + 1) { // for (int i = 0; i < n + 1; i ++ ) 读到n + …
2022/4/30 23:22:00 人评论 次浏览 -
分层图模板题
感谢所有AC 分层图形式 传送门 思路建立分层图，即复制 $k + 1$ 张图，层与层之间建立零权边。对源点进行 $dijstra$ ，得出源点到分层图上任意一点的最短路。由于最优方案并非要把所有次数用完，所以最后需要取终点的所有可能的最小值。需要注意空间大小，如果数据过大无…
2022/4/30 6:14:56 人评论 次浏览 -
[ICPC2022Macau]Cyclic Buffer【线段树】【动态规划】
分析：首先可以设计一个简单的dp。设dp[i][j]表示前i个数已经被选，且当前buffer的左端点在j这个位置的最小代价。注意到这个dp的有用点是很少的(有用点的意思是dp[i][j]不是由dp[i][j-1]或者dp[i][j+1]转移而来的)，而且所有的有用点集中在buffer覆盖在第i个数所在的位置…
2022/4/29 6:13:16 人评论 次浏览 -
[2022天梯赛] 教科书般的亵渎 【记忆化搜索】【剪枝】
题目描述： $n$张牌每个牌有权值$a_i$，要求选择$k$次，每次让牌的权值减一，使得牌的权值形成从$1$开始的连续整数(不含$0$). $n,k,ai \leq 50$ 分析： 先考虑朴素dp，先将$a_i$排序，$dp[i][S][j]$表示前$i$个数，把$S$这些位填上了，还剩$j$次行动机会的方案数。有 $$d…
2022/4/26 6:13:11 人评论 次浏览 -
卡牌
题意： 现在有 \(m\) 轮游戏，第 \(i\) 轮游戏会给出 \(c_i\) 个质数，小 A 需要选择任意多张卡牌，使得这些卡牌上面的正整数的乘积能被该轮游戏给出的每个质数整除。 问有多少种卡牌的选法。 暴力容斥 考虑 \(s_i \leq 30\) 时的做法。 目标：使每个质数被整除的方案数，…
2022/4/24 23:15:02 人评论 次浏览
