题目背景 小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章. 题目描述 这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换.对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译:如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译. 假设内存中有MMM个单元,每单元能存放一个单词和译义.每当软件将一个新单词存入内存前,如果当前内存中已存入

题目背景 小明过生日的时候,爸爸送给他一副乌龟棋当作礼物. 题目描述 乌龟棋的棋盘是一行N个格子,每个格子上一个分数(非负整数).棋盘第1格是唯一的起点,第N格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点. 乌龟棋中M张爬行卡片,分成4种不同的类型(M张卡片中不一定包含所有4种类型的卡片,见样例),每种类型的卡片上分别标有1.2.3.4四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数.游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌龟棋子前

[题解] 很容易想到这是一个DP,f[i][j][k][l]表示4种卡片分别用了多少张,那么转移方程就是f[i][j][k][l]=Max(f[i-1][j][k][l],f[i][j-1][k][l],f[i][j][k-1][l],f[i][j][k][l-1])+a[i+j*2+k*3+l*4+1]. #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #defin

传送门 ## T1 区间修改+单点查询.差分树状数组. #include<iostream> #include<cstdio> #include<cstring> using namespace std; ; inline int rd(){ ,f=;char ch=getchar(); :;ch=getchar();} )+(x<<)+ch-';ch=getchar();} return f?x:-x; } void out(int x){ if(!x)

传送门 ## $T1$ 一道结论题,设原来A队能力最大的是x,那么A队的选择方案就是$2^{x-1}$,B队的选择方案就是$(2^{n-x}-1)$种,因为不能不选.其中$1\leq x\leq n$,那么根据乘法原理,最后的答案就是 $\sum\limits^{n-1}_{x=1}2^{x-1}*(2^{n-x}-1)$,化简可得 $ans=n*2^{n-1}-(2^{n}-1)$,然后一个快速幂就行了. #include<iostream> #include<cstdio> #

传送门 解题思路 一道裸的dp. 用dp[i][j][k][kk]表示用i个1步,j个2步,k个3步,kk个4步所获得的最大价值,然后状态转移方程就要分情况讨论了(详见代码) 然后就是一开始统计一下几步的卡片共有几张存在num里. 这道题的范围小,所以可以大胆的用思维数组QAQ!!! AC代码 #include<iostream> using namespace std; ; ]; ][][][]; int main() { cin>>n>>m; ;i<=n-;i

传送门 解题思路 很显然,为了让最大值最小,肯定就是从大到小枚举,让他们分在两个监狱中,第一个不符合的就是答案. 怎样判断是否在一个监狱中呢? 很显然,就是用种类并查集. 种类并查集的讲解——团伙(很像的一个题) 很裸的一个种类并查集. 当然,也可以用二分+二分图染色来解决. AC代码 #include<iostream> #include<algorithm> #include<cstdio> using namespace std; ; ; *maxn]; stru

目录 \(NOIP2010\)提高组真题部分整理 \(T1\)机器翻译: 题目背景: 题目描述: 输入输出格式: 输入输出样例: 说明: 题解: 代码: \(T2\)乌龟棋 题目背景: 题目描述: 输入输出格式: 输入输出样例: 说明: 题解: \(T4\)引水入城: 题目描述: 输入输出格式: 输入输出样例: 说明: 题解: 代码: \(NOIP2010\)提高组真题部分整理 \(T1\)机器翻译: 洛谷\(P1540\) 题目背景: ​ 小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来

NOIP2010提高组题解 T1:机器翻译 题目大意:顺序输入n个数,有一个队列容量为m,遇到未出现元素入队,求入队次数. AC做法:直接开1000的队列模拟过程. T2:乌龟棋 题目大意:有长度为n的棋盘,每个格子对应一个分数,1,2,3,4的卡片共m张,给出四种卡片各自的数量,求改变出牌顺序能获得的最大分数. 思路:开了一个四维的f[i][j][k][l]来表示每张牌有了几张时的最大分数: F[i][j][k][l]=max(f[i-1][j][k][l],f[i][j-1][k][l],f

洛谷P4363 一双木棋 chess 省选最水的一道题了. 且看我数个月AC一道题...... 具体是这样的:我们发现这个下了棋的地方一定形成一个锯齿形,那么怎么状态压缩呢? 维护轮廓线! 从左下角出发,向上为1,向右为0即可. 然后我们就开心的DP…等等这按照什么顺序DP啊!!好,那么我们退而求次,记忆化搜索!然后就没有然后了… 需要注意的地方: 记得判断max还是min 二进制位运算一如既往的烦人 DFS起点和终点的处理 求最大差值,转化为加A减B即可 那么我们调了一年后终于A了!! #in

题目背景 小明过生日的时候,爸爸送给他一副乌龟棋当作礼物. 题目描述 乌龟棋的棋盘是一行N个格子,每个格子上一个分数(非负整数).棋盘第1格是唯一的起点,第N格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点. 乌龟棋中M张爬行卡片,分成4种不同的类型(M张卡片中不一定包含所有4种类型的卡片,见样例),每种类型的卡片上分别标有1.2.3.4四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数.游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌龟棋子前

刚才做并查集想到了这道以前做的题,干脆一并放上来 题目描述 S 城现有两座监狱,一共关押着N 名罪犯,编号分别为1~N.他们之间的关系自然也极不和谐.很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突.我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多.如果两名怨气值为c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为c 的冲突事件. 每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到

P1514 引水入城 题目描述 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠.该国的行政区划十分特殊,刚好构成一个N 行M 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度. 为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施.水利设施有两种,分别为蓄水厂和输水站.蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中. 因此,只有与湖泊毗邻的第1 行的城市可以建造蓄水厂.而输水站的功能则是通过输水管线利用高度落差,将湖水从高处向

(洛谷P1525) 题目描述 S 城现有两座监狱,一共关押着N 名罪犯,编号分别为1~N.他们之间的关系自然也极不和谐.很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突.我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多.如果两名怨气值为c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为c 的冲突事件. 每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到S 城Z 市长那里.公务繁忙的

将Noip2010重新做了一遍,第一遍做下来居然只有290分,比当年浙江的一等线低了20分,因为各种坏习惯丢掉了许多分数,Noip时需要特别注意! T1:机器翻译 第一题直接暴力,内存足够所以不用循环队列,5分钟AC: #include <cstdio> int stack[10000],now; int main(){ int m,n; scanf("%d%d",&m,&n); int head=m; for(int i=0;i<m;i++)stac

这道这么简单的题目还写了这么久.. 将每个会发生冲突的两人的怒气进行排序,然后从怒气大到小,将两个人放到不同监狱中.假如两人都已经被放置且在同一监狱,这就是答案. ---------------------------------------------------------------------------------------- #include<cstdio> #include<cstring> #include<iostream> #include<

OJ题号:洛谷1525 思路:贪心. 先将所有的人按怨气值从大到小排一下,然后依次尝试将双方分入两个不同的监狱,如果失败(即已分入相同的监狱),则输出这个怨气值. #include<cstdio> #include<algorithm> #include<functional> struct Edge { int u,v,w; bool operator >(const Edge &x) const { return this->w>x.w;

题目:洛谷P1514.Vijos P1777.codevs1066. 题目大意:有一个$n×m$的矩阵,每个点都有一个高度,可以在第一行的任意点建立蓄水厂.现在要把水输到最后一行的所有点上,规定水只能流到高度比当前点小的点上.先让你判断能否输到所有点上,如能,输出最少建多少个蓄水厂:如不能,输出最多能输到几个点上. 解题思路:首先把第一行所有点塞进队列里,跑BFS,找出所有能到的点,然后判断能否输到最后一行所有点上.如果不能,输出最后一行能被输到的点的总数.如果能的话,我们依次把第一行每个点能输

题目描述 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠.该国的行政区划十分特殊,刚好构成一个N 行M 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度. 为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施.水利设施有两种,分别为蓄水厂和输水站.蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中. 因此,只有与湖泊毗邻的第1 行的城市可以建造蓄水厂.而输水站的功能则是通过输水管线利用高度落差,将湖水从高处向低处输送.故一座城市能

题目背景 小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章. 题目描述 这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换.对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译:如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译. 假设内存中有M个单元,每单元能存放一个单词和译义.每当软件将一个新单词存入内存前,如果当前内存中已存入的单

题目描述 S 城现有两座监狱,一共关押着N 名罪犯,编号分别为1~N.他们之间的关系自然也极不和谐.很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突.我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多.如果两名怨气值为c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为c 的冲突事件. 每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到S 城Z 市长那里.公务繁忙的Z 市长只会去看列表