听说日本题思维都很棒,去涨涨智商qwq
C - Half and Half
题解
枚举买多少个AB披萨也行
但是关于买x个AB披萨最后的总花费是个单峰函数,可以三分 这题有点像六省联考2017D1T1送分题期末考试代码
#include#include #include #include #define MAXN 100005#define PLI pair #define fi first#define se second#define mp make_pair//#define ivorysiusing namespace std;typedef long long int64;int64 A,B,C;int X,Y;int64 calc(int t) { return 2 * t * C + max(X - t,0) * A + max(Y - t,0) * B;}void Solve() { scanf("%lld%lld%lld%d%d",&A,&B,&C,&X,&Y); int L = 0,R = max(X,Y); while(1) { int k = (R - L) / 3; if(!k) break; if(calc(L + k) > calc(R - k)) L = L + k; else R = R - k; } int64 ans = X * A + Y * B; for(int i = L ; i <= R ; ++i) { ans = min(ans,calc(i)); } printf("%lld\n",ans);}int main() {#ifdef ivorysi freopen("f1.in","r",stdin);#endif Solve(); return 0;}
D - Static Sushi
题解
分类瞎讨论一下就好,顺时针走,逆时针走,顺时针走再去逆时针,逆时针走再去顺时针
代码
#include#include #include #include #define MAXN 100005#define PLI pair #define fi first#define se second#define mp make_pair//#define ivorysiusing namespace std;typedef long long int64;int N;int64 C,x[MAXN],v[MAXN],ans;int64 pre[MAXN],suf[MAXN],premax[MAXN],sufmax[MAXN];void Solve() { scanf("%d%lld",&N,&C); for(int i = 1 ; i <= N ; ++i) scanf("%lld%lld",&x[i],&v[i]); x[N + 1] = C; for(int i = 1 ; i <= N ; ++i) { pre[i] = pre[i - 1] + v[i] - (x[i] - x[i - 1]); premax[i] = max(pre[i],premax[i - 1]); } for(int i = N ; i >= 1 ; --i) { suf[i] = suf[i + 1] + v[i] - (x[i + 1] - x[i]); sufmax[i] = max(suf[i],sufmax[i + 1]); } ans = max(ans,max(sufmax[1],premax[N])); for(int i = 1 ; i <= N ; ++i) { ans = max(ans,pre[i] - x[i] + sufmax[i + 1]); } for(int i = N ; i >= 1 ; --i) { ans = max(ans,suf[i] - (C - x[i]) + premax[i - 1]); } printf("%lld\n",ans);}int main() {#ifdef ivorysi freopen("f1.in","r",stdin);#endif Solve(); return 0;}
E - Everything on It
题解
容斥,w(i)表示有i个配料出现小于2次
式子就是\(\sum_{i = 0}^{n}(-1)^{i}\binom{n}{i}w(i)\) 然后考虑求\(w(i)\) 再考虑一个\(w2(i,j)\)表示把i个数字分到j个碗里,可以有数字不分到碗里,用类似第二类斯特林数的递推方式可以求出来 然后方案数就是\(w(i) = \sum_{j = 0}^{i} w2(i,j)2^{(N - i)j}2^{2^{N - i}}\) 然后就能\(O(n^2)\)出解了代码
#include#include #include #include #define MAXN 100005#define PLI pair #define fi first#define se second#define mp make_pair//#define ivorysiusing namespace std;typedef long long int64;int N,M;int64 C[3005][3005],S[3005][3005],ans; int64 fpow(int64 x,int64 c,int64 MOD) { int64 res = 1,t = x; while(c) { if(c & 1) res = res * t % MOD; t = t * t % MOD; c >>= 1; } return res;}int64 ways(int x) { int64 res = 0; int64 tmp2 = fpow(2,fpow(2,N - x,M - 1),M); int64 t = fpow(2,N - x,M); int64 tmp1 = 1; for(int j = 0 ; j <= x ; ++j) { res += S[x][j] * tmp1 % M * tmp2 % M; tmp1 = tmp1 * t % M; res %= M; } return res;}void Solve() { scanf("%d%d",&N,&M); C[0][0] = 1; for(int i = 1 ; i <= N ; ++i) { C[i][0] = 1; for(int j = 1 ; j <= i ; ++j) { C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % M; } } S[0][0] = 1;S[1][1] = 1; for(int i = 1 ; i <= N ; ++i) { S[i][0] = 1; for(int j = 1 ; j <= i ; ++j) { S[i][j] = (S[i - 1][j - 1] + S[i - 1][j] * (j + 1)% M) % M; } } int t = 1; for(int i = 0 ; i <= N ; ++i) { (ans += t * C[N][i] % M * ways(i) % M) %= M; t = 1LL * t * (M - 1) % M; } printf("%lld\n",ans);}int main() {#ifdef ivorysi freopen("f1.in","r",stdin);#endif Solve(); return 0;}
F - Sweet Alchemy
题解
模型转化非常有趣,最后就变成了有n种物品,(一个点的花费是子树的m和,价值是子树大小),每个能选D个,1号节点可以选无穷个
但是……我最多也就能转一下模型,剩下的是非常奇怪的背包 物品种数50,物品个数,容积体积都是\(10^9\) 后来题解说是值域非常小(价值也只有50),考虑在值域上搞搞文章 我们把价值设成\(Y\),代价设成\(X\),按照\(Y_{i} / X_{i}\)从大到小排个序 贪心肯定是错的,但是我们考虑这么样的情况,如果有一对\(p,q\)且\(p <= q\),那么如果q选了50个,p有50个还没选,我们显然可以选\(Y_{q}\)个p物品,选\(Y_{p}\)个q物品,这样我们的获得的价值没变,但是花费的体积变少了 如果现在没有这样的情况了,最多也就是每种物品50个,做一个容量为50*50*50的背包就好,表示达到这样价值需要的最少的体积,然后剩余的体积用来贪心放单位价值最大的 为什么是对的呢,假如只有两种物品,都选了50个,A多了10个,B多了20个,假如这时候把B的20个全选了是最好的,然而按照上面的置换方式,如果A数量小于B的价值,那么我们就和选择了的50个中组合几个替换掉原先选的B物品,这样的话保证了贪心选的话,A物品剩下的部分若能选全能被选上代码
#include#include #include #include #include