vijos专题

vijos P1680距离

https://vijos.org/p/1680#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;char s1[2222],s2[2222];int dp[2222][2222];int min(int a,int b,int c){b=b<c?b:c;re

vijos 1028 最长上升序列。

vijos 1028 换一个角度看问题。这道题其实就是一个上升序列。如：a,aa,aaa,aaaa.一个另类的上升序列。然后弱弱的试了是二分查找。很理想。不过却是个错误的思路。朴素的上升序列求法代码： #include <iostream>#include <string.h>#include <algorithm>using namespace std;char

vijos 1193 dp

每一行的状态由之前两行决定，dp[i][t][k]表示第i行状态为k，下一行状态为t时的种数，然后dp一遍即可。代码： #include <iostream>#include <cstring>#include <cstdio>using namespace std;int a[10010];int dp[10010][2][2]; //1下一行还需要一个1,0下一行不需要1in

Vijos:P1001谁拿了最多奖学金

描述某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同： 1) 院士奖学金，每人8000元，期末平均成绩高于80分（>80），并且在本学期内发表1篇或1篇以上论文的学生均可获得； 2) 五四奖学金，每人4000元，期末平均成绩高于85分（>85），并且班级评议成绩高于80分（>80）的学生均可获得； 3) 成绩优秀奖，每人2000元，期末平均成绩高于

vijos 1100（树状dp）

点击打开链接描述设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数若某个子树

Vijos P1848 记数问题【进制】

描述试计算在区间 1 到 n 的所有整数中,数字 x(0 ≤ x ≤ 9)共出现了多少次?例如,在 1 到 11 中,即在 1、2、3、4、5、6、7、8、9、10、11 中,数字 1 出现了 4 次。格式输入格式输入共 1 行,包含 2 个整数 n、x,之间用一个空格隔开。输出格式输出共 1 行,包含一个整数,表示 x 出现的次数。样例1 样例输入1 11 1

Vijos P1849 表达式求值【有限状态自动机】

描述给定一个只包含加法和乘法的算术表达式,请你编程计算表达式的值。格式输入格式输入仅有一行,为需要你计算的表达式,表达式中只包含数字、加法运算符“+”和乘法运算符“*”,且没有括号,所有参与运算的数字均为 0 到 2 ^ 31 -1 之间的整数。输入数据保证这一行只有 0~ 9、+、*这 12 种字符。输出格式输出只有一行,包含一个整数,表示这个表达式的值。注意:当

Vijos P1756 数字反转【进制】

背景 noip2011 NO.1 描述给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。格式输入格式输入共1 行，一个整数N。输出格式输出共1 行，一个整数，表示反转后的新数。样例1 样例输入1 123 样例输出1 321 样例2

Vijos P1449 字符串还原【密码】

背景小K是一位蔚蓝教主的崇拜者(Orz教主er)，有一天，他收到了一封匿名信，信告诉了小K由于他表现出色，得到了一次当面Orz教主的机会，但是要当面Orz教主可不那么容易，不是每个人都有资格Orz教主的。所以要破解下面一段密文才可以得到相关的信息，信中有提供加密的规则，但是小K觉得这个问题看似复杂，所以想请你帮忙。描述一个长度为n的由小写字母组成的字符串s1 s2 ⋯ sn按如

vijos 1243 生产产品单调性优化动态规划

描述 Description 在经过一段时间的经营后，dd_engi的OI商店不满足于从别的供货商那里购买产品放上货架，而要开始自己生产产品了！产品的生产需要M个步骤，每一个步骤都可以在N台机器中的任何一台完成，但生产的步骤必须严格按顺序执行。由于这N台机器的性能不同，它们完成每一个步骤的所需时间也不同。机器i完成第j个步骤的时间为T[i,j]。把半成品从一台机器上搬到另一台机器上也需要一定的时

Vijos 小白逛公园线段树加DP

描述小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择**连续**的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。

Vijos P1725随机数生成器

暴力三个点的longlong 真是丧心! 以后要检查是不是相乘爆ll #include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;long long ans[3];long long tmp[3][3];long long f[3][3];long

Vijos P1531 食物链

没看懂偏移向量和拆点用的带权并查集水过去的注意先判断是否大于n 可能有 1 n+1 n+1 #include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int MAXN = 50000+10;int fa[MAXN],fv[M

Vijos P1297 生日蛋糕 NOI1999

居然又是搜索题本来以为是贪心后来发现搜索加剪枝轻松过剪枝大法好!!!!!!!!!!!!! 注意题目中的 pi是常数派我开始以为是单位啥的.. #include <iostream>using namespace std;int n,m;int min_s=1000000000;int SS[25],VV[25];void dfs(int s,int

SSL 1026 VIJOS 1126 洛谷 1034 CODEVS 1101 矩形覆盖#区间dp#

题目用 k 个矩形覆盖所有点，矩形的边平行于坐标轴。问题是当 n 个点坐标和 k 给出后，使得覆盖所有点的 k 个矩形的面积之和为最小。约定：覆盖一个点的矩形面积为 0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开（边线与顶点也都不能重合）。分析可以用dp，先离散。 f [ i ] [ j ] [ i 1 ] f[i][j][i1] f[i][j][i1]表示覆

#单调队列#洛谷 1090 SSL 1040 VIJOS 1097 CODEVS 1063 合并果子

题目及O（ n l o g 2 n nlog_2n nlog2n）做法分析其实我们也可以用O（n）来做，首先来个桶排。再用一个单调队列存下两个最小值，不断更新。代码 #include <cstdio>#include <cctype>using namespace std;short t[20001],l,r,min[2],n,head; int a[30001],

#离散# VIJOS 1237 CODEVS 2765 隐形的翅膀

题目选出两只最小的翅膀，使长度比接近黄金比例。分析我们可以把每一只翅膀都乘上黄金比例，然后快排找出最接近的。代码 #include <cstdio>#include <cctype>#include <algorithm>#define gs 0.6180339887498949using namespace std;double a[60001]; int n

#离散#SSL 1231 VIJOS 1238 容易的网络游戏

题目每台电脑最多只能有一人操作，一个人最多只能操作一台电脑；并且每款游戏最多只能在一台电脑上玩，每台电脑最多运行一个游戏。现在佳佳想知道，假如佳佳共有 M M M台电脑，且佳佳一共叫来了 P P P个同学，最多能得到多少单位的经验。分析离散。坑点答案开long long共有p+1个人（所以如果你不调整还是会炸掉）挑最小值分析 #include <cstdio>#i

vijos P1263 单挑女飞贼

单挑女飞贼实际上这是一道水题本弱菜由于看错题WA了好多次orzzzz…… 思路按照最普通的思路从林月如的位置进行宽搜每次取出头结点判断飞镖是否可以攻击到女飞贼没有用STL队列所以代码很丑还有就是数据很弱这样做居然可以秒掉…… 代码 #include <cstdio>#include <cstring>#include <iostream>using na

Vijos P1198 最佳课题选择

最佳课题选择这是一道多重背包问题仍记得当时写出来死命debug的过程然而最后发现没开long long导致只过两组只考虑给当前分配多少和给前面所有的东西分配多少就可以上代码 #include <cstdio>#include <cstring>#include <iostream>#define LL long longusing namespace std;c

VIJOS PID221 / 烦人的幻灯片

暴力出奇迹，学长诚不欺我。 PID221 / 烦人的幻灯片 2017-04-14 19:47:08 运行耗时：30 ms 运行内存：12292 KB 查看最后一次评测记录题目描述李教授于今天下午做一个非常重要的演讲。不幸的是他不是一个非常爱整洁的人，他把自己做演讲要用的幻灯片随便堆放在一起。因此，演讲之前他不得不去整理这些幻灯片。做为一个讲求效率的学者，他希望尽

Vijos——T1279 Leave-绿光

https://vijos.org/p/1279 背景期待这一份幸运，和一份冲劲，多么奇妙的际遇……。燕姿在演唱完绿光这首歌后，出给了姿迷一个考题。北欧有一个传说！人一生中能看见绿光！他就一生都可以得到幸福！描述燕姿唱完这首歌，天上降落了一道绿光，在地上形成了一个矩形的映射，矩形的长为a，宽为b。燕姿向姿迷出了一个考题，谁能够把这个矩形绿光阵分成若干个正整数的正方形，谁的正方形边长之和最

Vijos P1889 天真的因数分解

描述小岛: 什么叫做因数分解呢? doc : 就是将给定的正整数n, 分解为若干个素数连乘的形式. 小岛: 那比如说 n=12 呢? doc : 那么就是 12 = 2 X 2 X 3 呀. 小岛: 呜呜, 好难, 居然素数会重复出现, 如果分解后每一个素数都只出现一次, 我就会. wish: 这样来说, 小岛可以正确分解的数字不多呀. doc : 是呀是呀. wish: 现在问

vijos-1512 SuperBrother打鼹鼠(二维树状数组)

背景 SuperBrother在机房里闲着没事干(再对比一下他的NOIP,真是讽刺啊……),于是便无聊地开始玩“打鼹鼠”…… 描述在这个“打鼹鼠”的游戏中，鼹鼠会不时地从洞中钻出来，不过不会从洞口钻进去（鼹鼠真胆大……）。洞口都在一个大小为n(n<=1024)的正方形中。这个正方形在一个平面直角坐标系中，左下角为(0,0)，右上角为(n-1,n-1)。洞口所在的位置都是整点，就是横