Codeforces Round #462 (Div. 2)

B題……我固執的認為1e18是18位數，導致被hack，花了20分鐘才檢查出這個錯誤，很僵硬

Codeforces 934C

題意

給定一個由\(1\)和\(2\)組成的數列，并且可以將區間\([l,r]\)內的數翻轉一次，求這種情況下數列的\(LIS\)

數列長度\(n \le 2000\)

解題思路

如果不翻轉的話，可以枚舉從1變成2的位置，通過預處理\(1\)和\(2\)數量的前綴和，那么這個決策點的\(LIS=one[i]+two[n]-two[i]\)。

再考慮翻轉，可以算出翻轉區間內的決策點的\(LIS\)為
\[ one[l-1]+two[i-1]-two[l-1]+one[r]-one[i-1]+two[n]-two[r] \]
兩兩配對有：
\[ (one[l-1]-two[l-1])-(one[i-1]-two[i-1])+(one[r]-two[r])+two[n] \]

進而固定\(l\)，增加\(r\)時，維護\((one[i-1]-two[i-1])\)的最小值，可得當前區間決策的最大值

復雜度\(O(n^2)\)

#include <bits/stdc++.h> using namespace std; const int maxn=2018; int n; int a[maxn],one[maxn],two[maxn],dev[maxn]; int main(int argc, char const *argv[]) {scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&a[i]);for (int i=1;i<=n;i++){if(a[i]==1){one[i]=one[i-1]+1;two[i]=two[i-1];}else{one[i]=one[i-1];two[i]=two[i-1]+1;}}for (int i=0;i<=n;i++)dev[i]=one[i]-two[i];int ans=0;for (int i=0;i<=n;i++){int minv=dev[i];for (int j=i;j<=n;j++){ans=max(dev[i]+dev[j]-minv+two[n],ans);minv=min(dev[j],minv);}}printf("%d\n",ans);}

Codeforces 934D

題意

對于給定的\(1 \le p \le 10^{18}\)，\(2 \le k \le 2000\)，構造多項式\(f(x)=q(x)(x+k)+p\)，其中\(f(x)\)的所有系數都\(0 \le a_i \le k\)

解題思路

設\(f(x)=\sum\limits_{i=0}^ze8trgl8bvbqa_i \cdot x^i\)，\(q(x)=\sum\limits_{i=0}^{d-1}b_i \cdot x^i\)

通過多項式長除法，易得\(p=a_0-k \cdot a_1+ \cdots +(-1)^d \cdot k^d\cdot a_d\)

在\(-k\)進制下，系數\(a\)是唯一的

對等式兩端同時模\(k\)取整數 ，可得\(a_0\)，減去\(a_0\)除以\(-k\)進入新一輪迭代

AC代碼

#include <bits/stdc++.h> using namespace std; int ans[200]; int cnt=0; int main(int argc, char const *argv[]) {long long p,k;scanf("%I64d%I64d",&p,&k);while(p!=0){ans[++cnt]=(p%k+k)%k;p-=(p%k+k)%k;p/=(-k);}printf("%d\n",cnt);for (int i=1;i<=cnt;i++)printf("%d ",ans[i]);printf("\n");return 0; }

轉載于:https://www.cnblogs.com/falseangel/p/8449641.html

總結

以上是生活随笔為你收集整理的Codeforces Round #462 (Div. 2)题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。