当前位置：首页 > news >正文

CF每日5题（1300-1500）

news 2025/5/18 6:46:27

1500好难刷不动了T_T

2069C 贪心找规律 1500

只有123三个数，组合只有 $1 2...2 3$ 。
1和3之间k个2，贡献 $2^k-1$ 个答案

所有1和3两两组合 O(n2) 超时
关注每一个1的贡献

我们掏一个样例：1 2 3 2 1 3 2 2 3。对于每个 1，我们把它对于答案的贡献写出来。
第一个1 后面有3个3 $2^1+2^2+2^4-1-1-1$
第二个1 后面有2个3 $2^0+2^2-1-1$

思路就是从后往前判断，遇到3就-1，遇到2就 $\times 2$ ，遇到1就ans+=结算。 O(n)
注意取模后防止为负数，(ans+MOD)%MOD

const int MOD=998244353;
void solve(){int n;cin>>n;vector<int>a(n+1);int t=0,cnt=0,ans=0;forr(i,1,n){cin>>a[i];}reforr(i,1,n){if(a[i]==1)ans=(ans+(t-cnt)+MOD)%MOD;if(a[i]==2)t=(t<<1)%MOD;if(a[i]==3)t++,cnt++;}cout<<ans<<endl;
}

2067C 找规律 1500

$99..9(x个9)=10^x-1$

n 的末尾加上至多 9 个 9 便一定可以得到 7
我对这里的理解是，对个位是6这样的数，不管高位是什么，加上9*9=81的个位1，最后个位一定是7

枚举可能的答案k:0~9，先做-1再+10^x，防止低位-1需要借位的情况
找前面+10^x的过程（代码中用ans计数）
- 先考虑最高位前面的0，需要+7才得到7
- 之后比较每一位到7需要+1的个数，取最小的
- 需要ans<k，因为前面+10^x和后面+1的个数要匹配

为什么个位(l-1)也要判断和7的距离？
eg: 6

void solve(){int n;cin>>n;forr(k,0,9){int ans=7;//对于最高的0为 需要7个+1 到7string s=to_string(n-k);int l=s.size();forr(i,0,l-1){if(s[i]>='0'&&s[i]<='7')ans=min(ans,(int)('7'-s[i]));}if(ans<=k){cout<<k<<endl;break;}}
}

2065C2 贪心 1300

水题

注意到，若 $b_j-a_i\geq a_{i-1}$ 即 $a_{i-1}+a_i\leq b_j$ ，二分查找满足这样的 $b_j$
尽量把前面的数往小压，取a[i]=min(b[x]-a[i],a[i])
遇到a[i-1]>a[i]，取大的a[i]，max(b[x]-a[i],a[i])，如果取大的还不行，就出NO

void solve(){int n,m;cin>>n>>m;vector<int>a(n+1),b(m);int fg=1;forr(i,1,n){cin>>a[i];if(i>=2&&a[i]<a[i-1])fg=0;}forr(i,1,m)cin>>b[i-1];if(fg)return cout<<"YES"<<endl,void();sort(b.begin(),b.end());if(b[0]-a[1]<a[1])a[1]=b[0]-a[1];forr(i,2,n){int x=lower_bound(b.begin(),b.end(),a[i]+a[i-1])-b.begin();if(x<m&&(b[x]-a[i]>=a[i-1]))a[i]=min(b[x]-a[i],a[i]);// cout<<x<<endl;if(a[i-1]>a[i]){if(x<m)a[i]=max(b[x]-a[i],a[i]);if(a[i]<a[i-1]||x==m)return cout<<"NO"<<endl,void();}// cout<<b[x]<<endl;}// forr(i,1,n)cout<<a[i]<<' ';cout<<"YES"<<endl;
}

2027C dfs 1500

$a_i=n-i+1a$ 可化为 $a_i-n+i-1=0$ ，对长度有 $i - 1$ 的贡献
下一轮 $a_j-(n+i-1)+j-1=0$ ，化为 $a_j-n+j-1=i-1$ ，从上一轮转移过来
考虑dp， $dp[(a_k-n+k-1)]=增加的长度$ ，自底向上递推上来
数据量大，记忆化搜索

const int N=3e5+10;
map<int,vector<int>>g;
map<int,int>dp;
int n;
int dfs(int now){if(dp[now])return dp[now];int ans=now;for(auto i:g[now]){ans=max(ans,dfs(now+i));}return dp[now]=ans;
}
void solve(){cin>>n;dp.clear();g.clear();forr(i,1,n){int ai;cin>>ai;if(i!=1&&ai>=n-i+1){g[ai-(n-i+1)].push_back(i-1);}}cout<<dfs(0)+n<<endl;
}

2033D 前缀和 1300

$\sum\limits_{i=l}^{r} a_i=pre_r-pre_{l-1}=0 \rightarrow pre_r=pre_{l-1}$

void solve(){int n;cin>>n;vector<int>a(n+1);forr(i,1,n){cin>>a[i];}vector<int>pre(n+1,0);map<int,int>cnt;//记录相同前缀和cnt[0]++;int ans=0;forr(i,1,n){pre[i]=a[i]+pre[i-1];// cout<<pre[i]<<' ';if(cnt[pre[i]]){ans++;cnt.clear();cnt[pre[i]]++;//上一个前缀和记录进去}else cnt[pre[i]]++;}// cout<<endl;cout<<ans<<endl;
}