A 牛牛排队
题目大意:
牛牛希望排队通过一扇门。牛牛离门 x 米,他每走一米需要 y 分钟。由于门口有保安查健康码,牛牛需要耗费 a 分钟掏出手机,b 分钟打开健康码,c 分钟扫码过门。
他想知道,对于不同的 x,y,a,b,cx,y,a,b,cx,y,a,b,c,他需要几分钟才能通过这扇门。
一边行走,一边掏手机或者打开健康码。
题解:
签到,给自己整服了,看错题罚了三次
代码:
#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--){ long long x,y,a,b,c; cin>>x>>y>>a>>b>>c; long long k; k = max(x * y, a + b); printf("%lld\n", k + c); } }
B 斗地主
题目大意:
牛牛一个人在打牌(他失去了牛妹),他有 m 种类型的牌,每种牌的分值是
a1,a2…a_{m}
。第 0 回合时牛牛的分值为 0。每回合他都会打出一张牌,然后新的分值就是上一回合得分值加上这张牌的分值再对 k 取模 。
牛牛喜欢一个数字,当且仅当数字中含有 7 或者含有 9。请你告诉他 n 轮后他分值会是他所"喜欢"的方案数。
我们认为两种方案不同,当且仅当存在某一个回合牛牛打出的牌不同。
由于答案可能非常大,你只需要输出其对于
10^{9}+7
取模的结果。数据范围:
$$1≤n≤100,1≤m,k≤50,0≤a_{m}<k$$
题解:
最开始写了一个DFS,hhhhhhhhh.....
其实一看就超时,就算m = 2
,当n = 100
的时候也有2^{100}
种情况= =,更何况这里m最大是50
后面问了一下是dp,才写出的dp,但是又是没交上去,考完后几分钟就ac了(早知道我就不吃面了,中间感觉凉了就去泡面了回来发现好像还能写hhhhhhh)....佛...
其实就是每一轮只依赖于上一轮的结果,然后只要按轮数去推就好了,然后就是MOD的分配律,加法和乘法都适用。直接计算下一轮中数MOD k的情况就好了。
代码:
#include<bits/stdc++.h> using namespace std; const int MOD = 1e9 + 7; long long n, m, k; long long nums[300]; long long ls[] = {7, 17, 27, 37, 47, 9, 19, 29, 39, 49}; long long f[300][300]; int main() { cin >> n >> m >> k; for (long long i = 1; i <= m; i++) { scanf("%lld", &nums[i]); } memset(f, 0, sizeof(f)); f[0][0] = 1; for (long long i = 1; i <= n; i++) { for (long long j = 0; j < k; j++) { for (long long o = 1; o <= m; o++) { f[i][(nums[o] + j) % k] = (f[i][(nums[o] + j) % k] + f[i - 1][j]) % MOD; } } } long long ans = 0; for (int i = 0; i < k; i++) { if (i % 10 == 7 || i % 10 == 9) { ans = ( ans + f[n][i] ) % MOD; } } printf("%lld", ans); return 0; }
总结
这把打得太差了,有点玉玉。希望今天的CF和At能好点吧= =
C题听wljss大佬说是换根dp,嗯又是我没听过的。
等学会了再来补C的题解