Xunyoyo

[NOIP2006 普及组] 开心的金明题目描述金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过$N$元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的$N$元。于是，他把每件物品规定了一个重要度，分为$5$等：用整数$1-5$表示，第$5$等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过$N$元（可以等于$N$元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第$j$件物品的价格为$v[j]$，重要度为$w[j]$，共选中了$k$件物品，编号依次为$j_1,j_2,…,j_k$，则所求的总和为： $v[j_1] \times w[j_1]+v[j_2] \times w[j_2]+ …+v[j_k] \times w[j_k]$。 请你帮助金明设计一个满足要求的购物单。 输入格式第一行，为$2$个正整数，用一个空格隔开：$n,m$（其中$N(<30000)$表示总钱数，$m(<25) ...

独木桥题目背景战争已经进入到紧要时间。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。士兵们十分愤怒，因为这座独木桥十分狭窄，只能容纳 $1$ 个人通过。假如有 $2$ 个人相向而行在桥上相遇，那么他们 $2$ 个人将无法绕过对方，只能有 $1$ 个人回头下桥，让另一个人先通过。但是，可以有多个人同时呆在同一个位置。 题目描述突然，你收到从指挥部发来的信息，敌军的轰炸机正朝着你所在的独木桥飞来！为了安全，你的部队必须撤下独木桥。独木桥的长度为 $L$，士兵们只能呆在坐标为整数的地方。所有士兵的速度都为 $1$，但一个士兵某一时刻来到了坐标为 $0$ 或 $L+1$ 的位置，他就离开了独木桥。 每个士兵都有一个初始面对的方向，他们会以匀速朝着这个方向行走，中途不会自己改变方向。但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。转身不需要任何的时间。 由于先前的愤怒，你已不能控制你的士兵。甚至，你连每个士兵初始面对的方向都不知道。因此，你想要知道你的 ...

[USACO2.1]三值的排序 Sorting a Three-Valued Sequence题目描述排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种 $1,2,3$。我们用交换的方法把他排成升序的。 写一个程序计算出，给定的一个 $1,2,3$ 组成的数字序列，排成升序所需的最少交换次数 输入格式第一行一个正整数 $n$，表示奖牌个数。接下来 $n$ 行，每行一个 $[1,3]$ 内的整数，表示奖牌。 输出格式输出一行一个整数，表示排成升序所需的最少交换次数。 样例 #1样例输入 #1123456789109221333231 样例输出 #114 提示【数据范围】对于 $100\%$ 的数据，$1\le n \le 1000$。 题解题目解析统计1,2,3的个数，那么排好序的一定是分为三个区间，那么当某数位置错误时，有以下几种情况： 1、一个数字1跑到了区间2，同时区间2中的一个数字2跑到了区间1 2、一个数字1跑到了区间3，同时区间3中的一个数字3跑到了区间1 3、一个数字2跑到 ...

[NC235624] 牛可乐和最长公共子序列1234题号：NC235624时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld 题目描述牛可乐得到了两个字符串 $s$ 和 $t$ ,牛可乐想请聪明的你帮他计算出来，两个字符串的最长公共子序列长度是多少。 最长公共子序列的定义是，子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。 输入描述:输入包含多组数据，请读至文件末尾。 每行包含两个字符串 $s,t$，两个字符串用一个空格字符间隔，单个字符串长度不超过 $5000$。 数据保证所有数据的字符串 $s$ 长度之和与字符串 $t$ 长度之和均不超过 $5000$。 输出描述:对于每组数据，输出一个整数，代表最长公共子序列的长度。 输入1abccde bcee 输出13 说明1最长公共子序列长度为 bce，长度为 3。 题解题目解析这个题目我使用的是朴素的最长公共子序列求解方法,其时间复杂度是 $O(n^2)$ ,具体过程还是使用动态规划完成. 其状态转移方程为: ...

[NOIP2001 普及组] 装箱问题题目描述有一个箱子容量为 $V$，同时有 $n$ 个物品，每个物品有一个体积。 现在从 $n$ 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。 输入格式第一行共一个整数 $V$，表示箱子容量。 第二行共一个整数 $n$，表示物品总数。 接下来 $n$ 行，每行有一个正整数，表示第 $i$ 个物品的体积。 输出格式 共一行一个整数，表示箱子最小剩余空间。 样例 #1样例输入 #1123456782468312797 样例输出 #110 提示对于 $100\%$ 数据，满足 $0<n \le 30$，$1 \le V \le 20000$。 【题目来源】 NOIP 2001 普及组第四题 题解题目解析一个简化的01背包问题,今天刚学的背包问题,作为例题所作.这个问题如果按照一个一个列的话可能到$2^{30}$个可能,事实上我们仅需考虑其前面最多可能组成的可能性. 举一个例子: 123456789101112背包大小为10,其中有5个物品,其重量为:1 2 3 4 5.我们分开情况讨论:- 1:0,1当仅有一个 ...

[NC235948] 最大子串和123时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 131072K，其他语言262144K64bit IO Format: %lld 题目描述给你一个数组 $a$ ，包含 $n$ 个整数，你需要在其中选择连续的几个（至少一个）数，使得它们的和最大，求出最大的和。 输入描述:第一行输入一个正整数 $n(1\le n\le10^6)$ , 表示数组 $a$ 大小. 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n(-10^9\le n \le 10^9)$ , 表示数组 $a$ . 输出描述:示例1输入1261 -2 5 2 -3 5 输出19 说明1你可以选择区间[3,6]的子串，他们的和为5+2−3+5=9。 示例2输入128-3 2 -3 2 2 -1 3 -2 输出16 题解题目解析这个题目使用的方法是动态规划(dp),其时间复杂度是$O(n)$级别. 动态规划的状态转移方程为: dp[i]=\max(dp[i-1]+a[i],a[i])解释一下,$dp[i]$的意思为以$i$位置的数字为子串结尾的最大值,其状态转移 ...

[NC20650] 可爱の星空123时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 131072K，其他语言262144K64bit IO Format: %lld 题目描述 “当你看向她时，有细碎星辰落入你的眼睛，真好。”——小可爱 在一个繁星闪烁的夜晚，卿念和清宇一起躺在郊外的草地上，仰望星空。 星语心愿，他们，想把这片星空的星星，连成一棵漂亮的树，将这美好的景色记录下来。 现在，天上共有n颗星星，编号分别为1,2…..n，一开始任何两个点之间都没有边连接。 之后，他们两个想在在(u,v)之间连无向边，需要付出|u联通块大小-v联通块大小|的代价。 他们两个想用最少的代价来使这n个点联通，所以他们想知道最小代价是多少。 (多组数据 输入描述:123第一行一个正整数，表示数据组数T接下来T行每行一个正整数，表示询问的n 输出描述:1T行，每行一个数表示答案 输入1215 输出12 说明1231,2....5五个点，连边顺序为(1,2),(3,4),(1,5),(5,3),代价为0,0,1,1， ...

[NC22669] 舔狗舔到最后一无所有123时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld 题目描述作为队伍的核心，forever97很受另外两个队友的尊敬。Trote_w每天都要请forever97吃外卖，但很不幸的是宇宙中心forever97所在的学校周围只有3家forever97爱吃的外卖。如果Trote_w给forever97买了别家的外卖，forever97就会大喊“我不吃我不吃”。但是forever97又不喜欢连续三天吃一种外卖。如果Trote_w哪天忘了这件事并且三天给他买了同一家外卖，那么forever97就会把Trote_w的头摁进手机屏幕里。作为Trote_w的好朋友，你能告诉他连续请forever97吃n天饭，有多少不同的购买方法吗？ 输入描述:123多组样例第一行一个整数T(1<=T<=20)代表测试样例数接下来t行每行一个整数n，代表Trote_w要请forever97吃n天饭(1<=n<=100000) 输出描述:1输出T个整数代表方案数 ...

[NC22669] 栈和排序123时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 131072K，其他语言262144K64bit IO Format: %lld 题目描述 给你一个1->n的排列和一个栈，入栈顺序给定 你要在不打乱入栈顺序的情况下，对数组进行从大到小排序 当无法完全排序时，请输出字典序最大的出栈序列 输入描述:12第一行一个数n第二行n个数，表示入栈的顺序，用空格隔开，结尾无空格 输出描述:1输出一行n个数表示答案，用空格隔开，结尾无空格 示例1输入1252 1 5 3 4 输出15 4 3 1 2 说明12入栈；1入栈；5入栈；5出栈；3入栈；4入栈；4出栈；3出栈；1出栈；2出栈 题解12345678910111213141516171819202122232425262728293031#include <iostream>#include <stack>#include <algorithm>using namespace std;int p[1000010],maxn[1000010];sta ...

[蓝桥杯 2013 省 B] 带分数题目描述$100$ 可以表示为带分数的形式：$100 = 3 + \frac{69258}{714}$。 还可以表示为：$100 = 82 + \frac{3546}{197}$。 注意特征：带分数中，数字 $1$ ~ $9$ 分别出现且只出现一次（不包含 $0$）。 类似这样的带分数，$100$ 有 $11$ 种表示法。 输入格式从标准输入读入一个正整数 $N(N<10^6)$。 输出格式程序输出数字 $N$ 用数码 $1$ ~ $9$ 不重复不遗漏地组成带分数表示的全部种数。 注意：不要求输出每个表示，只统计有多少表示法！ 样例 #1样例输入 #11100 样例输出 #1111 样例 #2样例输入 #21105 样例输出 #216 提示时限 3 秒, 64M。蓝桥杯 2013 年第四届省赛 题解AC代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <iostr ...