Codeforces Round #587 (Div. 3)

我不是女神ヾ 2023-06-01 15:54 28阅读 0赞

#  #

Codeforces Round \#587 (Div. 3)

[\\(E1.Numerical\\ Sequence\\ (easy\\ version)\\)][E1.Numerical_ Sequence_ _easy_ version]

这道题目比较简单因为根据等差数列求和公式 \\(n\*(n+1)/2\\) 这道题暴力枚举的时间复杂度不会超过 \\(\\Theta (10^5)\\)，所以我们先预处理出来 \\(10^5\\) 一共可以排多少位，然后每次暴力跳，只要当前的和加上这个数以及以前分解的小于等于 \\(k\\) 就一直往后跳，跳到最大小于 \\(k\\) 的，然后剩下的一段的末尾就是答案。

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+100; int q,num; int a[N*5],pre[N]; inline void work(int x) { if (!x) return ; work(x/10); a[++num]=x%10; return ; } int main() { for (int i=1;i<=(int)1e5;i++) { work(i); pre[i]=num; } scanf("%d",&q); while (q--) { ll k,sum=0; scanf("%lld",&k); for (int i=1;i<=(int)1e5;i++) if (sum+pre[i]<k) sum+=pre[i]; printf("%d\n",a[k-sum]); } return 0; }

反思：这道题目比较简单，比赛中却没有写出来，因为考试的时候只想怎样快速找到后面的那一段，没有想到通过预处理来暴力跳。

[\\(F. Wi-Fi\\)][F. Wi-Fi]

这道题目首先想出来的是贪心，结果发现贪心比较麻烦，发现可以 \\(DP\\) 所以就直接写了 \\(DP\\) 。设 \\(dp\[i\]\\) 为覆盖到 \\(i\\) 的最小花费。

然后如果 \\(a\[i\]\\) 为 \\(0\\) 就有

\\\[dp\[i\]=\\min(dp\[i-1\]+i,dp\[i\])\\\]

表示直接从前 \\(i-1\\) 个被覆盖的最小花费转移过来

如果 \\(a\[i\]\\) 为 \\(1\\) 就有

\\\[dp\[i\]=\\min(dp\[i-1\]+i,dp\[i\])\\\]

\\\[dp\[i\]=\\min(dp\[\\max(i-k,1)-1\]+i,dp\[i\])\\\]

表示从这个放置路由器可以覆盖范围的最前面的前一个转移过来

然后我们发现如果 \\(a\[i\]\\)是 \\(1\\) 的话 \\(\[\\max(i-k,1),\\min(i+k,n)\]\\) 其实也可以通过 \\(dp\[i\]\\) 转移过去。

但是直接这样做是 \\(\\Theta (n^2)\\) 的，然后我们发现操作可以通过线段树实现，时间复杂度降到 \\(\\Theta (n\\log\_2n)\\) 。

暴力转移

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=2e5+100; int n,k,cnt=1; char a[N]; int main() { scanf("%d%d",&n,&k); scanf("%s",a+1); for (int i=1;i<=n;i++) dp[i]=4e10+100; dp[0]=0; for (int i=1;i<=n;i++) { dp[i]=min(dp[i],dp[i-1]+i); if (a[i]=='1') { ll will=dp[max(1,i-k)-1]+i; dp[i]=min(dp[i],will); for (int j=max(1,i-k);j<=min(n,i+k);j++) dp[j]=min(dp[j],will); } } printf("%lld\n",dp[n]); return 0; }

线段树优化

[\\(Code\\)][Code]

反思：写的时候线段树写错了，所以就一直没有调出来，以后初始化标记的时候要在建树的每一个函数里。因为标记只能下传，不能上传。

转载于:https://www.cnblogs.com/last-diary/p/11567813.html

[E1.Numerical_ Sequence_ _easy_ version]: http://codeforces.com/contest/1216/problem/E1
[F. Wi-Fi]: http://codeforces.com/contest/1216/problem/F
[Code]: https://www.luogu.org/paste/1aivuiou