学长出的题都很精华,自己都没法ak
G. 股市风云
小明的父亲是New Internet Technology And China Maker 公司的总裁,大大大的土豪,每次都会给小明用不完的零花钱。为了小明的成长,他决定让小明用自己的零花钱去股市磨练一下。
他给小明限定了一个特定的股票和n天时间,小明只能买这一只股票,并且他磨练的时间一共只有n天。
而且,因为小明的耐心有限,他最多会买入这只股票两次,并且每次只会持有一股。
现在给你这n天内这只股票的单价,问你小明在n天内能获得的最大利润是多少。
Input
第一行给出一个T,表示有T组案例。对于每组案例,第一行给出一个n,表示小明磨练的时间。接下来一行给出n个数,第i个数pi表示第i天股票的价格。
(1<=n<=1e6,0
#include
#include
#include
#include
#include
#include
H. 按位与运算&&&&&
按位与运算的规则。
参加运算的两个数据,按二进制位进行“与”运算。
运算规则:0&0=0; 0&1=0; 1&0=0; 1&1=1;
即:两位同时为“1”,结果才为“1”,否则为0
例如:3&5 即 0000 0011 & 0000 0101 = 0000 0001 因此,3&5的值得1。
另,负数按补码形式参加按位与运算。
“与运算”的特殊用途:
(1)清零。如果想将一个单元清零,即使其全部二进制位为0,只要与一个各位都为零的数值相与,结果为零。
(2)取一个数中指定位
方法:找一个数,对应X要取的位,该数的对应位为1,其余位为零,此数与X进行“与运算”可以得到X中的指定位。
例:设X=10101110,
取X的低4位,用 X & 0000 1111 = 0000 1110 即可得到;
Input
第一行给出一个T,表示有T组案例。对于每组案例,在一行中给你两个数m,n(0<=m<=n<=2^31)。
Output
对于每组案例,求在区间[m,n]所有数按位与的结果,输出一行表示答案。
Sample Input
2
9 10
1 10
Sample Output
8
0
Hint
对于第二个案例 1&2&3&4&5&6&7&8&9&10=0
考验,对二进制的认识,及位移运算符的运用
建议先暴力求解出前一千个数的二进制码;
其实求的就是高位的最大公共部分
#include
#include
#include
#include
#include
#include
F. 休赛季的引援#2
众多周知,勇士又拿了nba的总冠军,作为詹姆斯球迷的袁大牛,当然不能接受这样的现实,于是在多年后他买下了骑士队,不过这只骑士队现在一个球员也没有,现在袁大牛要去自由市场引援,你帮他看看他的球队能否击败勇士(战斗力高于勇士).
首先,nba是有工资帽的,你签约自由球员的时候,你球队的工资总额是不能超过这个工资帽的,你要做的就是在工资帽内招到总战斗力最大的一些球员.其次,签约球员没有人数要求,几个人都行.
不过,你nba你每年都可以得到一个特例,特例能干什么用呢,说起来比较复杂,总之在休赛季,你可以无视工资帽的情况下签约一个工资50及以内的人,比如你当前总工资为800,工资帽为800,因为没有空间去再签一个球员,比如A(工资30,战斗力50),这时候你就可以用你的特例把他签下了.
Input
第一行给出一个整数n(0<=n<=1000),表示工资帽.
第二行给出一个整数m(0<=m<=1000),表示勇士战斗力.
第三行给出一个整数t(1<=t<=100),表示自由球员的数量.
【NIT 股市风云 按位与运算&&&&& F. 休赛季的引援#2】接下来t行,每行两个整数,球员需求的工资v(1<=v<=1000),球员的价值val(1<=val<=1000).
Output
输出你能得到的最高战斗力,并告袁大牛是否能击败勇士,详见输出.
Sample Input
1000
1000
5
100 200
500 105
200 300
300 200
300 200
1000
1000
5
500 105
200 300
500 400
300 200
30 100
1000
1000
5
500 105
200 500
500 400
300 200
30 100
Sample Output
900 no
1000 no
1200 yes
01背包变形,这个效率不高,
每个小于50的都有做特例的机会,先把每个小于50的取出来对剩余的暴力dp,再加上这个小于50的,求解最大值;
#include
#include
#include
#include
using namespace std;
int main()
{
int n, m, t;
while (~scanf("%d%d%d", &n, &m, &t))
{
int v[1111] = { 0 }, val[1111] = { 0 };
for (int i = 1;
i <= t;
i++)
scanf("%d%d", v+i, val+i);
int dp[1111] = { 0 };
int mm = -999;
for (int k = 1;
k <= t;
k++)
{
int pos = 0;
if (v[k] <= 50)
pos = k;
memset(dp,0, sizeof(dp));
for (int i = 1;
i <= t;
i++)
{
if (i == pos)
continue;
for (int j = n;
j >= v[i];
j--)
dp[j] = max(dp[j], dp[j - v[i]] + val[i]);
}
mm = max(mm, dp[n] + val[pos]);
}
printf("%d ", mm);
if (mm > m)
puts("yes");
else
puts("no");
}
return 0;
}
E. 休赛季的引援#1众多周知,勇士又拿了nba的总冠军,作为詹姆斯球迷的袁大牛,当然不能接受这样的现实,于是在多年后他买下了骑士队,不过这只骑士队现在一个球员也没有,现在袁大牛要去自由市场引援,你帮他看看他的球队能否击败勇士(战斗力高于勇士).首先,nba是有工资帽的,你签约自由球员的时候,你球队的工资总额是不能超过这个工资帽的,你要做的就是在工资帽内招到总战斗力最大的一些球员.其次,签约球员没有人数要求,几个人都行.Input
输入数据有多组.第一行给出一个整数n(0<=n<=1000),表示工资帽.第二行给出一个整数m(0<=m<=1000),表示勇士战斗力.第三行给出一个整数t(1<=t<=100),表示自由球员的数量.接下来t行,每行两个整数,球员需求的工资v(1<=v<=1000),球员的价值val(1<=val<=1000).
Output
输出你能得到的最高战斗力,并告袁大牛是否能击败勇士,详见输出.
Sample Input
1000
1000
5
100 200
500 105
200 300
300 200
300 200
1000
1000
5
500 105
200 300
500 400
300 200
30 100
1000
1000
5
500 105
200 500
500 400
300 200
30 100
Sample Output
900 no
900 no
1100 yes
无脑01背包,签到题
#include
#include
#include
#include
#include
#include
#include
#include