淘宝网电脑版登录入口官网网页,网站用户体验优化方案,网站建设与管理自考试题及答案,网站加图标problem
【题目描述】 你在 NOIP 2018 的赛场上遇到了「货币系统」一题。你没有写出这题#xff0c;导致网友的国度简化货币系统的任务失败了。网友的国度的货币系统现在十分混乱。
网友的国度现今有两套货币系统「忘忧」和「网游」。为了方便使用#xff0c;它们有一个共用…problem
【题目描述】 你在 NOIP 2018 的赛场上遇到了「货币系统」一题。你没有写出这题导致网友的国度简化货币系统的任务失败了。网友的国度的货币系统现在十分混乱。
网友的国度现今有两套货币系统「忘忧」和「网游」。为了方便使用它们有一个共用的货币单位「」而且二者都可以凑出价值任意整数的货币。
你现在希望用人民币来兑换一些网友的国度的货币。你需要兑换多次每次恰好兑换 1 。
忘忧和网游的汇率互相独立而且会动态改变。具体而言
第一次兑换忘忧1 花费 a 元由于网友的国度持有的忘忧变少了因此其价格 上涨每兑换 1 下一的价格涨价 b 元 形式化地第 i 次兑换忘忧的价格是一 b(i −1) a 元。第一次兑换网游1 花费 c 元由于网友的国度持有的网游变少了因此其价格上涨每兑换 1 下一的价格涨价 d 元形式化地第 i 次兑换网游的价格是一 d(i −1) c 元。
为了能够随机应变你希望提前知道给出的 q 种 a, b, c, d 下用 x 元钱分别最多能兑换多少。
每次询问相互独立
【输入格式】
第一行一个正整数 q表示有 q 个询问。
接下来 q 行每行 5 个正整数 a, b, c, d, x分别表示忘忧、网游的汇率变化方式和你所拥有的钱。
【输出格式】
输出共 qqq 行分别表示每次询问中你最多能兑换到多少。
1≤a,b,c,d,x≤10181≤q≤1051 ≤a, b, c, d, x ≤10^{18}1 ≤q ≤10^51≤a,b,c,d,x≤10181≤q≤105
solution
看到这种两个函数都是单增的且最后总限制为 xxx。
我就想到了 CSP-S 2021 T1当时我就是采取的三分骗到了不错的分数。
这道题看起来似乎与二分/三分很有关联。
但是这两个函数不能拼成一个单调或有峰值的函数能够直接做。
很妙的是直接二分花费最大值 midmidmid。
让两种物品的单个兑换最大花费不超过 midmidmid。
先计算出每种物品最多能买多少个最大的那个花费不超过 midmidmid然后可以等差数列 O(1)O(1)O(1) 计算出。 具体而言假设最多能买 iii 个即 b(i−1)a≤midb(i-1)a\le midb(i−1)a≤mid。 花费则为 ∑k1ib(k−1)a∑k1ibk(a−b)∗i(bb∗i)i2i∗(a−b)\sum_{k1}^ib(k-1)a\sum_{k1}^ibk(a-b)*i\frac{(bb*i)i}{2}i*(a-b)∑k1ib(k−1)a∑k1ibk(a−b)∗i2(bb∗i)ii∗(a−b)。 再把两种物品的花费求和与 xxx 限制比较。
当然可能会剩下一点 rrr也许还可以再买两种物品中的一个特判一下。
最开始求最大花费不超过 midmidmid 的物品个数也请注意写法。——来自伞兵博主。
code
#include bits/stdc.h
using namespace std;
#define int __int128
int q, x, a, b, c, d, ans;void read( int x ) {x 0; char s getchar();while( s 0 or s 9 ) s getchar();while( 0 s and s 9 ) x ( x 1 ) ( x 3 ) ( s - 0 ), s getchar();
}void print( int x ) {if( x 9 ) print( x / 10 );putchar( x % 10 0 );
}bool check( int v ) {int i max( (int)0, ( v - a ) / b 1 );int j max( (int)0, ( v - c ) / d 1 );if( i and b * ( i - 1 ) a v ) i --;if( j and d * ( j - 1 ) c v ) j --;int cost ( i 1 ) * b * i / 2 i * ( a - b ) ( j 1 ) * d * j / 2 j * ( c - d );if( cost x ) return 0;int r x - cost, tot i j;if( r b * i a ) r - b * i a, tot , i ;if( r d * j c ) r - d * j c, tot , j ;ans max( ans, tot );return 1;
}signed main() {freopen( money.in, r, stdin );freopen( money.out, w, stdout );read( q );while( q -- ) {read( a ), read( b ), read( c ), read( d ), read( x );int l 0, r x; ans 0;while( l r ) {int mid ( l r ) / 2;if( check( mid ) ) l mid 1;else r mid - 1;}print( ans );puts();}return 0;
}
