【洛谷4424】[HNOI_AHOI]寻宝游戏(我也不知道括号里该写啥)
题目洛谷 4424分析感觉思路比较神仙。对于按位与和按位或两种运算,显然每一位是独立的,可以分开考虑。对于某一位,「与 \(0\)」会将这一位变成 \(0\...
洛谷刷题-【入门2】分支结构
目录 1.苹果和虫子 题目描述 输入格式 输出格式 输入输出样例 2.数的性质 题目描述 输入格式 输出格式 输入输出样例 3.闰年判断 题目描述 输入格式 输出格式 输入输出样例 4.apples 题目描述 输入格式 输出格式 输入输出样例 5.洛谷团队系统 题目描述 输入格式 输出格式 输入输出...
洛谷 P1041 错解
P1041 传染病控制题目背景近来,一种新的传染病肆虐全球。蓬莱国也发现了零星感染者,为防止该病在蓬莱国大范围流行,该国政府决定不惜一切代价控制传染病的蔓延。不幸的是,由于人们尚未完全认识这种传染病,难以准确判别病毒携带者,更没有研制出疫苗以保护易感人群。于是,蓬莱国的疾病控制中心决定采取切断传播途...
[bzoj4443] [loj#2006] [洛谷P4251] [Scoi2015]小凸玩矩阵
Description小凸和小方是好朋友,小方给小凸一个 \(N \times M\)( \(N \leq M\) )的矩阵 \(A\) ,要求小秃从其中选出 \(N\) 个数,其中任意两个数字不能在同一行或同一列,现小凸想知道选出来的 \(N\) 个数中第 \(K\) 大的数字的最小值是多少。In...
洛谷 [P1118] IOI1994 数字三角形
简单dfs我们注意到,题目中的运算方式与杨辉三角极其相似,所以说本题实际上是一道加权的杨辉三角,搜索系数#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>...
洛谷P2886 [USACO07NOV]牛继电器Cow Relays
题意很简单,给一张图,把基本的求起点到终点最短路改成求经过k条边的最短路。求最短路常用的算法是dijkstra,SPFA,还有floyd。考虑floyd的过程:c[i][j]=min(c[i][j],a[i][k]+b[k][j]);自然而然联想到矩阵乘法,每次加入一个点就相当于多加一条边,那么加k...
洛谷 P2886 [USACO07NOV]牛继电器Cow Relays
题面解题思路 ##floyd+矩阵快速幂,跟GhostCai爷打赌用不用离散化,最后完败。。GhostCai真是tql ! 有个巧妙的方法就是将节点重新编号,因为与节点无关。代码#include<bits/stdc++.h>using namespace std;const int MA...
洛谷 P2491消防 解题报告
P2491 消防题目描述某个国家有n个城市,这n个城市中任意两个都连通且有唯一一条路径,每条连通两个城市的道路的长度为zi(zi<=1000)。这个国家的人对火焰有超越宇宙的热情,所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍(大量的消防经费开销)可是却又无可奈何(总统竞选的国...
AC日记——独木桥 洛谷 p1007
题目背景战争已经进入到紧要时间。你是运输小队长,正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激,于是命令你的士兵们到前方的一座独木桥上欣赏风景,而你留在桥下欣赏士兵们。士兵们十分愤怒,因为这座独木桥十分狭窄,只能容纳一个人通过。假如有两个人相向而行在桥上相遇,那么他们两个人...
洛谷P2243 电路维修
题目地址转化为图论问题对于每个交叉点(X,Y)抽象成节点。与它相邻的四个点中,可以直接连线的边权为0,否则边权为1。用死了的SPFA解决图论问题。#include <cstring>#include <cstdio>#define GC getchar()#define Cl...
洛谷mNOIP模拟赛Day2-将军令
题目背景pdf题面和大样例链接:http://pan.baidu.com/s/1cawM7c 密码:xgxv 历史/落在/赢家/之手 至少/我们/拥有/传说 谁说/败者/无法/不朽 拳头/只能/让人/低头 念头/却能/让人/抬头 抬头/去看/去爱/去追 你心中的梦 题目描述又想起了四月。如果不是...
POJ1471 Tree/洛谷P4178 Tree
TreeP4178 Tree点分治板子。点分治就是直接找树的重心进行暴力计算,每次树的深度不会超过子树深度的\(\frac{1}{2}\),计算完就消除影响,找下一个重心。所以伪代码:void solve(int u){ calc(u); used[u]=true; for(int...
洛谷P3810 陌上花开 CDQ分治(三维偏序)
好,这是一道三维偏序的模板题当然没那么简单.....首先谴责洛谷一下:可怜的陌上花开的题面被无情的消灭了:这么好听的名字#(滑稽)那么我们看了题面后就发现:这就是一个三维偏序。只不过ans不加在一起,而是加在每朵花内部。很裸的一道CDQ分治,CDQ一维,sort一维,TreeArray一维,然后就爆...
[洛谷P4178] Tree (点分治模板)
题目略了吧,就是一棵树上有多少个点对之间的距离 \(\leq k\)\(n \leq 40000\)算法##首先有一个 \(O(n^2)\) 的做法,枚举每一个点为起点,\(dfs\) 一遍可知其它点到这个点的距离,统计一下即可。但是这样太慢了。于是考虑“分治”这种神奇的做法。第一步,选一个点做根节...
洛谷 4178 Tree——点分治
题目:https://www.luogu.org/problemnew/show/P4178点分治。如果把每次的 dis 和 K-dis 都离散化,用树状数组找,是O(n*logn*logn),会T7个点。#include<iostream>#include<cstdio>#...
2018.07.20 洛谷P4178 Tree(点分治)
传送门 又一道点分治。 直接维护子树内到根的所有路径长度,然后排序+双指针统计答案。 代码如下:#include<bits/stdc++.h>#define N 40005using namespace std;inline int read(){ int ans=0; ch...
洛谷P1993 小 K 的农场
题目描述小 K 在 Minecraft 里面建立很多很多的农场,总共 n 个,以至于他自己都忘记了每个农场中种植作物的具体数量了,他只记得一些含糊的信息(共 m 个),以下列三种形式描述:农场 a 比农场 b 至少多种植了 c 个单位的作物。农场 a 比农场 b 至多多种植了 c 个单位的作物。农场...
洛谷P1993 小K的农场 [差分约束系统]
题目传送门小K的农场题目描述小K在MC里面建立很多很多的农场,总共n个,以至于他自己都忘记了每个农场中种植作物的具体数量了,他只记得一些含糊的信息(共m个),以下列三种形式描述:农场a比农场b至少多种植了c个单位的作物,农场a比农场b至多多种植了c个单位的作物,农场a与农场b种植的作物数一样多。但是...
洛谷 P3989 [SHOI2013]阶乘字符串 解题报告
P3989 [SHOI2013]阶乘字符串题目描述给定一个由前\(n(\le 26)\)个小写字母组成的串\(S(|S|\le 450)\)。串\(S\)是阶乘字符串当且仅当前 \(n\) 个小写字母的全排列(共\(n!\)种)都作为的子序列(可以不连续)出现。请判断出给定的串是否是阶乘字符串。当\...
2018.10.29 洛谷P4129 [SHOI2006]仙人掌(仙人掌+高精度)
传送门显然求出每一个环的大小。Ans=∏i(siz[i]+1)Ans=\prod_i(siz[i]+1)Ans=∏i(siz[i]+1)注意用高精度存答案。代码:#include<bits/stdc++.h>using namespace std;inline int read(){ ...