夏令营7.18总结

Day7 模考

时间分配

$8:30\sim8:40$做T1，AC

$8:40\sim8:50$做T2，AC

$8:50\sim9:30$做T3，AC

$9:30\sim10:00$尝试T3，样例不对

$10:00\sim10:20$尝试T4，过不了

$10:20\sim10:30$T4骗分，30tps

题目

T1

比较简单。

定义$a_i$代表袋子里又$i$个标号为$a$的球。

同时额外累计一个ans，代表当前袋子里球的数量

读入每组数据，如果是

• 放入：将下述操作完成后$a_i$加一。
  • 操作：
  • $a_i=0$：将ans加一
  • 否则ans不变
• 取出：完成下述操作后$a_i$减一。
  • 操作：
  • $a_i=0$：将ans减一
  • 否则ans不变
• 统计：直接输出ans

核心代码：

int n;
cin>>n;
if(n==1){
    int x;
    cin>>x;
    if(a[x]==0) ans++;
    a[x]++;
}
else if(n==2){
    int x;
    cin>>x;
    a[x]--;
    if(a[x]==0) ans--;
}
else{
    cout<<ans<<endl;
}

T2

强烈怀疑是放错题目了

这题就是一个简单的判断模三。但是，当你准备把一段简单的模三代码交上去时，你会发现什么结果都没有因为时OI赛制。但是实际上只有十分，因为你没开long long不对是因为你没看题面。

题面里明明白白地写了：$\Huge接下来每个整数的长度小于等于1000.$

那么，接下来的就很简单了。

用string是最简单的，当然你用字符数组我也不拦着你。

简单的核心代码：

string a;
cin>>a;
int add=0;
for(int i=0;i<a.size();i++){
    add+=a[i]-'0';
}
if(add%3==0){
    cout<<"Yes"<<endl;
}
else cout<<"No"<<endl;

T3

这道题目相对来说还是比较简单的。

这里的重点不放在做法上，在一种在考试时很实用的小妙招：

一种简单的vector去重方法：

sort(a.begin(),a.end());//排序
//unique把重复元素放到最后，并返回最后一个非重复元素的下一个的下标
a.erase(unique(a.begin(),a.end()),a.end());//erase擦除第一个重复元素到最后一个元素

注意：判断下标，所以要加一句，否则会RE：

if(c.empty()) return;

注意特殊情况，否则容易爆零。

//情况1
lower_bound();
end() n+1;//lower_bound()找不到可能返回end+1的下标，容易越界
auto it=lower_bound();//可能这个指针为空
ans=max(ans,*it);//这里可能会越界

//情况2
//减之前判断下标位置
if(it!=a.begin()) it--;

还有一个vector的使用小技巧：

reserve()//可以给vector预留空间

T4

为了最大化嵌套后的结果，我们需要：

优先选择增长潜力大的函数：即每次嵌套后能带来更大增幅的函数。

$dp$优化：通过$dp$逐步构建最优解，避免暴力枚举所有可能的组合。

对每个函数计算一个关键值$K=\frac{B_i}{A_i−1}$，用于衡量函数的增长潜力。

如果$A_i=1$则$k$设为无穷大，确保这些函数优先被选中。

按照$k$从大到小排序，确保增长潜力大的函数优先被考虑。

动态规划计算最大值：

初始化动态规划数组$dp$，其中$dp[j]$表示选择$j$个函数时的最大可能值。

初始时$dp[0]=1$，因为嵌套的初始输入是$1$

对于每个函数，从$K$到$1$反向更新$dp[j]$：

计算选择当前函数后的新值：$neww=A_i\times dp[j−1]+B_i$。

如果新值比当前$dp[j]$大，则更新$dp[j]$。

T5

骗分骗30

还没搞定QwQ。