除夕夜的比赛，除了高三高四那个除夕还在学习，这是第三次了吧，上大学之后的第一次。感觉年味越来越没有了，最有年味的一次是回我妈老家新华槎溪，大家坐在一起吃着东西聊着天，孩子一起玩耍放鞭炮，现在在城里面炮也不是很多，但是相比于其他地方还算可以的，出去散了个步，打了一下牛客的除夕比赛，再洗个澡打cf，唉，说多了。
这次比赛有个教训，就是类似于这句话The sum of k over all test cases does not exceed 2·10^5，计算时间复杂度的时候，往往能够枚举这个k，因为一共k有限，而不是每一个测试样例的k都是2e5
做题做的太慢了，想多了有的时候
A.Div 7
题意
给你一个数字$n(10\leq n\leq999)$，求改变$n$的位数最小次数的能整除$7$的数，如果有多就任意输出
思路
既然放在A题且数据不大，那么我们就可以枚举，样例给出了$n=377$然后输出的是$777$，我们还是不这样做，想到另外一种方法在$n$附近枚举找最近的满足条件的数。
那怎么样判断改变位数最小这个条件呢？因为数据太小，我就用的一个函数一位一位去判断...
其他方法：
思路： 能被7整除，方法有很多种，因为要求最小次数，那么我们特判能被7整除就输出0否则，暴力最后一位能被7整除即可，然后返回1，必定有答案。
所以只需要暴力枚举最后一位，x=n/10存前面两位..不需要左找右找
代码
inline int f(int x)
{
int y=n,cnt=0;
while (y)//这里要while n，我因为减x而wa了一发。。
{
if (x%10!=y%10) cnt++;
x/=10;y/=10;
}
return cnt;
}
inline void Case_Test()
{
cin>>n;
x=n;
if (x%7==0) {cout<<x<<endl;return;}
while (x>=0&&x%7!=0)
{
x--;
}
ans1=x;
x=n;
while (x<=999&&x%7!=0)
{
x++;
}
ans2=x;
if (f(ans1)<=f(ans2)) cout<<ans1<<endl;//判断一下，相等随便输出
else cout<<ans2<<endl;
}
B.Minority
题意
给出一个字符串$s$，求$s$的子串使得移除较小的那个最大的个数，比如00011111，0有$3$个1有$5$个，这样就是$3$
思路
不难，当时猜的结论，试了一试，直接从头判断到尾，贪心的思想直接cnt计数，然后边计边取max_ans
代码
inline void Case_Test()
{
cin>>s;
n=s.length();
ans=-1;
cnt0=cnt1=0;
for (int i=0;i<n;i++)
{
if (s[i]=='0') cnt0++;
else cnt1++;
if (cnt1>cnt0) ans=Max(ans,cnt0);
if (cnt0>cnt1) ans=Max(ans,cnt1);
}
cout<<ans<<endl;
}
C.Kill the Monster
题意
你需要去打败怪兽，每个人都有自己的血量$H$和攻击力$D$，是回合制，你先攻击，他扣你的攻击力值，然后他攻击你，你扣他的攻击力值。这时候你有金币$k$可以升级，花费一个金币可以使你的攻击力上升$w$或者血量增加$a$，问能否打败。
思路
我一直在推不等式，想推出一个关于一个未知数的式子，然后用判别式去判断，但是实在是太麻烦了，后面一看发现就是我之前说的那个，k是可以枚举的（我还想过二分。。）所以就枚举花x金币在血量上，花y金币在攻击力上，$[x,y]={[0,k],[1,k-1]...[k-1,1],[k,0]}$。
代码
inline int check(int x,int y)
{
int H=hc+x*a,D=dc+y*w;//升级
return ceil((double)hm/D)<=ceil((double)H/dm);
}
string s;
inline void Case_Test()
{
cin>>hc>>dc>>hm>>dm>>k>>w>>a;
for (int i=0;i<=k;i++)
if (check(i,k-i)) {cout<<"YES"<<endl;return;}//枚举
cout<<"NO"<<endl;
}
D. Make Them Equal
题意
给出长度为$n$的$b,c$两数组，和最多$k$次操作，每次消耗$1$次操作是你可以选择$i(1\leq i\leq n)$和$x(x>0)$让$a_i$增加$a_i=a_i+\lfloor \frac{a_i}{x} \rfloor$。如果$a_i=b_i$的话，就能得到$c_i$的奖励，求最大奖励是多少。
思路
一开始列了一个表，准备去找关系，但是发现数字并不大，$b_i$的最大值是$10^3$，所以直接循环递推过去，当时感觉应该是有规律的，直到最后选择暴力求的时候又花了好多时间，烦死了。
也可以打表..这里不重要，所以每次给出的数值我们都能得到花费，花费其实最大才12...所以给出的$k$最大是$10^6$用不完，我还在想时间复杂度呢，01背包时间复杂度是$O(nk)$，没优化前的。
所以这里就用01背包就可以了（我还想了优化，又花费了好久）
代码
inline void init()
{
int MAXN=1007;
mem(a,0x3f);
a[1]=0;
for (int x=1;x<=MAXN;x++)
for (int i=1;i<=x;i++)
if (a[x+x/i]>a[x]+1)
a[x+x/i]=a[x]+1;
}
int f[N];
inline void Case_Test()
{
cin>>n>>k;
mem(f,0);
for (int i=1;i<=n;i++)
{
cin>>x;
w[i]=a[x];
}
for (int i=1;i<=n;i++)
cin>>v[i];
m=Min(k,15*n);//1e6的数据肯定又剩下的，这里需要优化，不然两层循环上天
for(int i = 1; i <= n; i++)
for(int j = m; j >= w[i]; j--)
f[j] = max(f[j], f[j-w[i]]+v[i]);//01背包
cout<<f[m]<<endl;
}
祝大家虎年吉祥！万事如意！
2022/2/2/2:03
文章评论