NIT 股市风云 按位与运算&&&&& F. 休赛季的引援#2

学长出的题都很精华,自己都没法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 typedef long long ll; using namespace std; const int MM = (int)1e6 + 10; llnum[MM]; ll lef[MM], righ[MM]; int main() { int t,i,j; cin >> t; { while(t--) { int n; scanf("%d", &n); int le = 0; for (i = 0; i < n; i++) { scanf("%lld", &num[i]); if (num[le] > num[i]) le = i; lef[i] = le; } int re = n - 1; for (i = n - 1; i >= 0; i--) { if (num[i] > num[re]) re = i; righ[i] = re; } ll s1 = 0, s2 = 0; for (int i = 0; i < n; i++) { s1 = max(s1, num[i] - num[lef[i]]); s2 = max(s2, s1 + num[righ[i]] - num[i]); } printf("%lld\n", s2); } } return 0; }

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 typedef long long ll; using namespace std; intstu[(int)1e5 + 1]; int main() { ll t, n, m; while (cin >> t) { while (t--) { cin >> n >> m; int cnt = 0; int f = 0; while (n&&m) { if (n == m) { f = 1; cout << (n << cnt) << endl; break; } n >>= 1; m >>= 1; cnt++; } if (!f) puts("0"); } } return 0; }

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 #define MAXN 1000010 using namespace std; typedef long long ll; const int MOD = 10000; //tree array first blood int tarray[50005]; int n; int lowbit(int i) { return i&(-i); } void insert(int i, int k) { while (i <= n) { tarray[i] += k; i += lowbit(i); } } ll sum(int i) { ll s = 0; while (i > 0) { s += tarray[i]; i -= lowbit(i); } return s; } int dp[1111]; int main() { int w, m, t, v[1111], val[1111]; while (~scanf("%d%d%d", &n,&m,&t)) { memset(dp, 0, sizeof(dp)); for (int i = 1; i <= t; i++) scanf("%d%d", v + i, val + i); for (int i = 1; i <= t; i++) { for (int j = n; j >= v[i]; j--) dp[j] = max(dp[j], dp[j - v[i]] + val[i]); } if (dp[n] > m) { printf("%d yes\n", dp[n]); } else printf("%d no\n", dp[n]); } return 0; }

    推荐阅读