10.12 新一波高能胡策题 贪心+状压DP+分块+魔性DP

2023-12-11 15:40

本文主要是介绍10.12 新一波高能胡策题 贪心+状压DP+分块+魔性DP,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  • 出题人
  • Problem 1 零花钱
    • 题目来源
    • 题目描述
    • 题解
    • 代码
  • Problem 2 Oh My King
    • 题目来源
    • 题目描述
    • 题解
    • 代码
  • Problem 3 函数求和
    • 题目来源
    • 题目描述
  • Problem 4 防 AK 好题
    • 题目来源
    • 题目描述

出题人

(排名为字典序)
Chairman http://blog.csdn.net/qq_36693514
LXT http://blog.csdn.net/loi_lxtt
qrc 不用csdn的大佬
wyh 不用csdn的大佬

这里写图片描述

Problem 1 零花钱

题目来源:

http://www.tyvj.cn/p/1032
https://www.luogu.org/problem/show?pid=2376#sub
https://www.luogu.org/problem/show?pid=2619#sub

题目描述

快 NOIP 了, 国王决定开始每个星期给公主一点零花钱。
国王有一些硬币,一共有 N 种不同的面额。 国王想用给定的硬币的集合,每个星期至少给它某个零花钱的数目 C。请帮国王计算公主最多能支付多少个星期的零花钱。
每一个较小面额的硬币的面额, 都能被 比它面额更大的硬币的面额给整除

输入描述
第 1 行:两个有空格隔开的整数: N 和 C;
第 2 到第 N+1 行:每一行有两个整数表示一个面额的硬币:硬币面额 V
(1 <= V <= 100,000,000)拥有的该面额的硬币数 B (1 <= B <= 1,000,000)。

输出描述
一个单独的整数,表示最多能给支付多少个星期至少为 C 的零用钱。

样例输入
3 6
10 1
1 100
5 120

样例输出
111

数据范围及提示
题目保证给出的面额不重复;
对于 100% 的数据:
1<=N<=20 1<=C<=100000000 1<=Bi<=1000000 1<=Vi<=100000000

题解:

贪心
至少给C元,很显然的是,如果某个硬币的金额大于C,那么直接给,ans+
为了满足更多星期,我们优先使用大的面额且使花的冤枉钱最少;
按照面额大小排序,对于当前面额,在小于等于C的情况下,能放多少就放多少。
某时刻等于C则退出,进行下一次操作。
for循环结束后,如果仍然不能等于C,也就是说,如果要满足,必须大于C,那么为了花费的冤枉钱最少,我们找一个最小值加上。

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,c,ans,x,y,tot,minn,tmp;
struct wkw{int v,m;
}a[800];
bool cmp(wkw a,wkw b){return a.v>b.v;
}
int main(){//freopen("money.in","r",stdin);
//  freopen("money.out","w",stdout);scanf("%d%d",&n,&c);for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);if(x>=c) {ans+=y;continue;}a[++tot].v=x,a[tot].m=y;}sort(a+1,a+tot+1,cmp);while(1){tmp=c;for(int i=1;i<=tot;i++){if(a[i].m==0) continue;int maxx=min(a[i].m,tmp/a[i].v);a[i].m-=maxx;tmp-=(maxx*a[i].v);if(a[i].m) minn=i;if(tmp==0){ans++;break;}}if(tmp>0){tmp-=a[minn].v;a[minn].m--;if(tmp<=0) ans++;}if(tmp==c) break;}printf("%d",ans);return 0;
}

Problem 2 Oh! My King!

题目来源

http://www.lydsy.com/JudgeOnline/problem.php?id=1087

题目描述

很久很久以前,巨龙未曾出现, 国王风流倜傥京城酒吧鸡王南梦华【雾】 很无聊,他看过叛逆的鲁路修之后感觉国际象棋很好玩, 因此他准备搞一波国际象棋玩耍赛。由于他是国王, 他决定将棋子全换成国王来玩, 并且还是由于 EX 级皇帝特权, 所以他的国王棋子多的一笔,因此他决定在 N×N 的棋盘里面放 K个国王,使他们互不攻击。 又由于他是个乖巧的国王, 是要遵守游戏规则的, 最后他想求共有多少种摆放方案。
游戏规则: 国王能攻击到它上下左右,以及左上、 左下、 右上、 右下八
个方向上附近的各一个格子,共 8 个格子, 要保证国王互不攻击, 如果
没有方案数则输出 0。
国王鸡王南梦华听说你很厉害,决定丢你棋子钦定你干活 23333

输入描述
一行,输入 N 和 K, 意义见上文

输出描述
方案数

样例输入
3 2

样例输出
16

数据范围及提示
对于特殊的 10%的数据, n=1;
对于另 30% 的数据, 1<=n<=3, 1<=k<=n;
对于 100% 的数据,满足 1<= n<=9, 1<= k<=n*n;

题解:

讲了以后就会发现是一道很水的状压DP23333;
和炮兵阵地一样,以行为枚举单位,
预处理出每一行的状态和上下行状态是否合法(对角线上用左移右移即可);
设dp[i][j][pos]为第i行,放了j个国王,状态为pos的方案数
又上一行转移而来
答案是dp[n][k][pos] pos枚举的和(因为最后一行随便什么状态都可以)

没开long long没去文件输入输出流在bzoj上wa了几次。

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
bool mmp[600][600];
int sta[600],cnt[600];
long long n,k,maxx,tot;
long long  dp[15][100][600];
int find(int x){int ans=0;while(x){if(x&1) ans++;x>>=1;}return ans;
}
void init(){int g=(1<<n);while(g){g--;if(g<<1&g) continue;sta[++tot]=g;cnt[tot]=find(g);}for(int i=1;i<=tot;i++){for(int j=1;j<=tot;j++){mmp[i][j]=mmp[j][i]=((sta[i]&sta[j])|(sta[i]>>1&sta[j])|(sta[i]<<1&sta[j]));}}
}
int main(){scanf("%lld%lld",&n,&k);init();for(int i=1;i<=tot;i++) dp[1][cnt[i]][i]=1;for(int i=2;i<=n;i++){for(int pos=1;pos<=tot;pos++){for(int j=cnt[pos];j<=k;j++){for(int p=1;p<=tot;p++){if(mmp[p][pos]) continue;dp[i][j][pos]+=dp[i-1][j-cnt[pos]][p];}}}}for(int i=1;i<=tot;i++) maxx+=dp[n][k][i];printf("%lld",maxx);return 0;
}

Problem 3 函数求和

题目来源

据说是原创题

题目描述

有一个含有 n 个数字的序列 A, 元素标号 1 到 n。
同时你有 n 个函数,标号为 1 到 n。
第 i 个函数函数值为序列中下标为 Li 到 Ri 的元素和。
现在你需要维护以下两种操作
1 x y : 将序列中下标为 x 的元素修改为 y
2 s t : 询问标号为 s 到 t 的函数值的和

输入描述
第一行一个正整数 n,表示序列和函数的个数。
接下来一行 n 个整数表示序列 A。
接下来 n 行,每行两个整数 Li, Ri,表示第 i 个函数
接下来一行一个整数 q,表示询问次数
下面 q 行,每行一个询问,格式如题面描述

输出描述
对于每个询问 2, 输出对应答案

样例输入
5
1 2 3 4 5
1 3
2 5
4 5
3 5
1 2
4
2 1 4
1 3 7
2 1 4
2 3 5

样例输出
41
53
28

数据范围及提示
对于 20%的数据, n<=100&&q<=100
对于另外 30%数据, Ri–Li<=10,所有 x 各不相同
对于 100%的数据, 1 <=n<=1e5,1<=Li<=Ri<=n, 1<=x<=n,
1<=s<=t<=n,1<=Ai,y<=1e9,1<=q<=1e5;

Problem 4 防 AK 好题

题目来源

bzoj 1017

题目描述

在你的世界中,每个人都有一个能力值, 并且初始为 0
通过金币购买装备,可以提高这一属性,并且不同装备增加的属性值不

装备分基础装备和高级装备,基础装备可以直接购买,高级装备需要基础装备合成。 合成高级装备只需要基础装备,不需要附加条件。
一件高级装备可能需要多件不同的基础装备合成,比如 A 的合成可能需要 2 * a && 3 * b && 1 * c。合成高级装备的同时,基础装备消失。
每件基础装备都有一个购买限制以为着你不能无限的购买和合成。
现在你有 m 个金币,你想知道用这些金币最大可以获得多少能力值。

输入描述
第一行两个数字 n, m 分别表示装备种类和金币数
接下来 n 行,按照装备 1 到 n 排序,每行描述一件装备。每行第一个数
字表示这件装备的力量值,接下来一个字符 A || B 表示高级装备||基础
装备。如果是基础装备,接下来两个整数表示单价和数量限制,如果是
高级装备后面一个数字 c 表示这件高级装备需要 c 种低级装备,后面的
2 c 个数分别表示这 c 件装备的种类和需求量。

输出描述
一行一个数字表示能达到的最大能力值

样例输入
10 59
5 A 3 6 1 9 2 10 1
1 B 5 3
1 B 4 3
1 B 2 3
8 A 3 2 1 3 1 7 1
1 B 5 3
5 B 3 3
15 A 3 1 1 5 1 4 1
1 B 3 5
1 B 4 3

样例输出
33

数据范围及提示
对于 100%的数据, N (1 <= n <= 51) m (0 <= m <= 2,000)
对于第 9 测试点时限为 11s, 十个点总时限为 30s

这篇关于10.12 新一波高能胡策题 贪心+状压DP+分块+魔性DP的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/481204

相关文章

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

uva 10154 DP 叠乌龟

题意: 给你几只乌龟,每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析: 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠,状态转移方程: dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]

uva 10118 dP

题意: 给4列篮子,每次从某一列开始无放回拿蜡烛放入篮子里,并且篮子最多只能放5支蜡烛,数字代表蜡烛的颜色。 当拿出当前颜色的蜡烛在篮子里存在时,猪脚可以把蜡烛带回家。 问最多拿多少只蜡烛。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cs

uva 10069 DP + 大数加法

代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>#include <cl

uva 10029 HASH + DP

题意: 给一个字典,里面有好多单词。单词可以由增加、删除、变换,变成另一个单词,问能变换的最长单词长度。 解析: HASH+dp 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s