这场就比较难了。。。不过出题人说这场比赛是A组偏上的难度。。
因为和实验室比赛冲突，于是边写博客边补这个的题。话说这场题目名字取得花里胡哨的- -….
前言
D - 抽刀断水水更流，举杯销愁愁更愁 10’
-
题意:
给定一个22个数的质数集合，可以从中挑出任意多个(0-12个)不同的数出来构成一个新数，问0-1694中有多少个数是无法构成的。 -
思路:
每个数只有挑或者不挑，dfs一遍，挑12个数出来，把和标记一下即可。
int vis[] = {3, 5, 7, 11, 13, 19, 23, 29, 31, 37, 41, 53, 59, 61, 67, 71, 97, 101, 127, 197, 211, 431};
int s[1700];
void dfs(int i, int sum, int step)
{
if (step > 12)
return;
s[sum] = 1;
for (int j = i + 1; j < 22; j++)
dfs(j, sum + vis[j], step + 1);
}
int main()
{
for (int i = 0; i < 22; i++)
{
s[vis[i]] = 1;
dfs(i, vis[i], 1);
}
int ans = 0;
for (int i = 1; i < 1695; i++)
{
if (!s[i])
{
ans++;
}
}
cout<<ans;
return 0;
}
F - 等差等比有联系 公差公比求通项 15’
-
题意:
已知一个等比数列的某三项分别是a,b,c, 且已知第一项是a，求等比数列的第N项最大是多少。 -
思路:
- 可知公比最大只能为min(c/b,b/a)
- for循环枚举可能的公比，求出能取的最大值（当c/b,b/a都能整除i时即为可取）
- 用快速幂优化时间复杂度。
const long long mod = 1e9;
long long a, b, c, N;
long long qpow(long long a, long long b)
{
long long res = 1ll;
while (b > 0)
{
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
bool sieve(long long a, long long b)
{
while (a % b == 0)
{
a /= b;
}
return a == 1;
}
int main()
{
cin >> a >> b >> c >> N;
long long b1 = b / a, b2 = c / b, q = 1;
for (long long i = min(b1, b2); i >= 2; i--)
{
if (sieve(b1, i) && sieve(b2, i))
{
q = i;
break;
}
}
cout << a * qpow(q, N - 1) % mod << '\n';
return 0;
}
G - 进退得失全看透，名利当作粪土丢 15’
- 题意:
第一行输入n，以及每瓶饮料需要的a材料的数量和b材料的数量，接下来n组数据，每组数据ci,p ai,pbi，表示每天需要制作的饮料的数量和两种材料的价格，问在允许囤积材料的情况下且满足n天需求的最小花费。 - 思路:
贪心，如果当前库存量够当天使用，则直接使用库存的，如果不够，则在前i天中找最便宜的一天提前购买存货即可。但是补题的时候依然WA两发。。坑点挺多的，不过主要是代码写的狗屎。。。。
struct node
{
int k;
int x, y;
} s[1005];
int main()
{
int n, a, b, xx, yy;
cin >> n >> a >> b;
int nowx = 9999, nowy = 9999;
for (int i = 0; i < n; i++)
{
cin >> s[i].k >> xx >> yy;
nowx = min(nowx, xx);
nowy = min(nowy, yy);
s[i].x = nowx;
s[i].y = nowy;
}
int ans = 0, xulmp, nowlmp = 0;
for (int i = 0; i < n; i++)
{
ans += s[i].k * s[i].x * a;
xulmp = s[i].k * b - nowlmp;
if (xulmp <= 0)
{
nowlmp -= s[i].k * b;
continue;
}
nowlmp = 0;
if (xulmp % 80 == 0)
{
ans += s[i].y * (xulmp / 80);
}
else
{
int tt = 80 - (xulmp % 80);
nowlmp += tt;
ans += s[i].y * (xulmp / 80 + 1);
}
}
cout << ans << endl;
return 0;
}