文章目錄

• 前言
• $\text{A?Comparing?Two?Long?Integers}$
• • $\text{Description}$
  • $\text{Solution}$
  • $\text{Code}$
• $\text{B?Dinner?with?Emma}$
• • $\text{Descripion}$
  • $\text{Solution}$
  • $\text{Code}$
• $\text{C?The?Labyrinth}$
• • $\text{Descripion}$
  • $\text{Solution}$
  • $\text{Code}$
• $\text{D?Longest?k-Good?Segment}$
• • $\text{Descripion}$
  • $\text{Solution}$
  • $\text{Code}$
• $\text{E?Sum?of?Remainders}$
• • $\text{Descripion}$
  • $\text{Solution}$
  • $\text{Code}$
• $\text{F?Expensive?Strings}$
• • $\text{Descripion}$
  • $\text{Solution}$
  • • updata on 2022.1.1
  • $\text{Code}$

前言

比較簡單的一場比賽。
ABC是水題。
D簡單雙指針。
E整除分塊板子題。
F廣義SAM板子，但是由于我太蒻不會，所以只能拿SA硬做qwq

$\text{A?Comparing?Two?Long?Integers}$

$\text{Description}$

比較兩個不超過 $1000000$ 位的正整數的大小。正整數可能有前導零。前面那個比后面那個大輸出 >，比后面那個小輸出 <，兩個一樣大輸出 =。

$\text{Solution}$

python爪把
讀進來后去掉前導零再判斷即可。

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }const int N=1e6+100; const int M=505;char a[N],b[N]; int n,m,q,tim;signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifscanf(" %s %s",a+1,b+1);n=strlen(a+1);m=strlen(b+1);int pa=1,pb=1;while(pa<=n&&a[pa]=='0') pa++;while(pb<=m&&b[pb]=='0') pb++;if(n-pa+1!=m-pb+1){if(n-pa+1<m-pb+1) putchar('<');else putchar('>');return 0;}while(pa<=n){if(a[pa]!=b[pb]){if(a[pa]<b[pb]) putchar('<');else putchar('>');return 0;}++pa;++pb;}putchar('=');return 0; } /**/

$\text{B?Dinner?with?Emma}$

$\text{Descripion}$

杰克決定邀請艾瑪出去吃飯。杰克是個謙虛的學生，他不想去昂貴的餐館。可艾瑪是個品味很高的女孩，她更喜歡高端的餐館。

Munhatan由 $n$ 條街道和 $m$ 條巷子組成。在每一條街道和小巷的交叉口都有一家餐館。街道用 $1$ 到 $n$ 的整數來編號，巷子用從 $1$ 到 $m$ 的整數來編號。在第 $i$ 街和第 $j$ 巷交叉口的餐館里吃飯的費用是 $C_{i,j}$。

杰克和艾瑪決定按以下方式選擇餐館。先是艾瑪選了在哪條街上吃飯，然后杰克選了巷子。艾瑪和杰克做出了最佳的選擇：艾瑪想最大限度地提高晚餐的成本，杰克想把它降到最低。而艾瑪知道杰克的想法。告訴這對戀人晚餐最終的費用。
$n,m\le 100$

$\text{Solution}$

tag：min-max 容斥。
找到每一行最小值的最大值即可。

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }const int N=1e6+100; const int M=505;int n,m; int a[105][105];signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifn=read();m=read();int ans=0;for(int i=1;i<=n;i++){int mn(2e9);for(int j=1;j<=m;j++) a[i][j]=read(),mn=min(mn,a[i][j]);ans=max(ans,mn);}printf("%d\n",ans);return 0; } /**/

$\text{C?The?Labyrinth}$

$\text{Descripion}$

給你一張圖，* 表示墻，.表示空地，問每個 * 周圍的聯通快中 . 的數量和模 $10$ 的結果，屬于同一個聯通快的只計算一次。
$n,m\le 1000$

$\text{Solution}$

bfs 一遍求出每個連通塊的大小，求出每個點四周的大小之和即可。
可以利用 set 方便去重。

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }const int N=1050;int n,m; int a[N][N],bel[N][N],siz[N*N],tot,vis[N][N]; int dx[5]={0,0,-1,0,1},dy[5]={0,-1,0,1,0}; inline bool exi(int x,int y){return x>=1&&x<=n&&y>=1&&y<=m;} void bfs(int x,int y,int f){vis[x][y]=1;bel[x][y]=f;siz[f]++;for(int i=1;i<=4;i++){int xx=x+dx[i],yy=y+dy[i];if(vis[xx][yy]||a[xx][yy]||!exi(xx,yy)) continue;bfs(xx,yy,f);}return; } set<int>s;signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifn=read();m=read();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char c;scanf(" %c",&c);a[i][j]=(c=='*');}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]||vis[i][j]) continue;++tot;bfs(i,j,tot);}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(!a[i][j]){putchar('.');continue;}for(int k=1;k<=4;k++){int x=i+dx[k],y=j+dy[k];if(a[x][y]||!exi(x,y)) continue;s.insert(bel[x][y]);}int ans(1);for(int x:s) ans+=siz[x];printf("%d",ans%10);s.clear();}putchar('\n');}return 0; } /**/

$\text{D?Longest?k-Good?Segment}$

$\text{Descripion}$

給定一個包含 $n$ 個整數的序列$a$，$0\le a_i\le 10^6$ ，詢問不重復數字個數 $\le k$ 的最長區間的左右端點。如果有多解輸出任意一組。
$n\le 5\times 10^5$

$\text{Solution}$

開一個桶維護各種數字的數量維護當前區間不重復數字個數，雙指針取區間最大值即可。

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }const int N=1e6+100;int n,m; int a[N],bac[N],now,ans,L,R;signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifn=read();m=read();for(int i=1;i<=n;i++) a[i]=read();int l=1,r=0;while(r<n){now+=(++bac[a[++r]]==1);while(now>m) now-=(--bac[a[l++]]==0);if(r-l+1>ans){ans=r-l+1;L=l;R=r;}}printf("%d %d\n",L,R);return 0; } /**/

$\text{E?Sum?of?Remainders}$

$\text{Descripion}$

計算以下式子的和：$n\mathrm{m}\mathrm{o}\mathrm{d}1+n\mathrm{m}\mathrm{o}\mathrm{d}2+n\mathrm{m}\mathrm{o}\mathrm{d}3+?+n\mathrm{m}\mathrm{o}\mathrm{d}m$。由于結果可能很大，你需要輸出其對 $10^9+7$ 取模的結果。
$n,m\le 10^{1}3$

$\text{Solution}$

式子可以寫成：
$$\sum _{i=1}^{m}n??\frac{n}{i}?\times i$$
直接上整除分塊即可。

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }const int N=1e6+100; const int mod=1e9+7;ll n,m,ans; ll ksm(ll x,ll k){ll res(1);while(k){if(k&1) res=res*x%mod;x=x*x%mod;k>>=1;}return res; }inline ll calc(ll l,ll r){return ((l+r)%mod)*((r-l+1)%mod)%mod*500000004%mod;} signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifn=read();m=read();ans=(m%mod)*(n%mod)%mod;for(ll l=1,r;l<=min(n,m);l=r+1){r=min(m,n/(n/l));ll o=n/l%mod;ans=(ans+mod-o*calc(l,r)%mod)%mod;//printf("(%lld %lld) o=%lld\n",l,r,o);}printf("%lld\n",ans);return 0; } /**/

$\text{F?Expensive?Strings}$

$\text{Descripion}$

給你$n$個字符串。每個字符串的成本都是$c_i$。
定義字符串的函數，其中$f(s)={\sum }_{i=1}^n{c}_i?p_{s,i}?|s|$，$p_{s,i}$是$s$在$t_i$中出現的次數，$|s|$是字符串$s$的長度。求所有字符串函數$f(s)$的最大值。

注意字符串$s$不一定是$t$中的某個字符串。

$\text{Solution}$

據說用廣義 SAM 的話就是板子了。
但是我并不會qwq。
考慮使用 SA。

先把所有串連起來，中間夾一些泥巴。
后綴排序后先求出 $\mathrm{height}$。
每個后綴的價值定義為其所屬串的價值，并求出價值的前綴和。
然后如果選擇區間 $[l,r]$ 的所有字符串，那么選擇的價值就是：
$$(\underset{i=l+1}{\overset{r}{\min }}{\mathrm{height}}_i)\times su{m}_r?su{m}_{l?1}$$
因為貪心的考慮一定使這個串最長。
那么我們懸線法求出每個 $height$ 作為最小值的有效區間，掃一遍取最大值即可。
但這樣是無法考慮這個串只出現一遍的情況的，這個串一定就是某個串本身，map 暴力判一下即可。

updata on 2022.1.1

感謝 @望月Asta 提供的hack，上面的算法會在下面這個數據出錯：

2 od iod 2 -1 ans:2

原因是之前 map 判整串判的過于草率了，正確的做法應該是記錄每個串開頭的位置 $pl$，然后看看 $heigh{t}_{pl}$ 和 $heigh{t}_{pl+1}$ 是否都小于該串長度。

但是我代碼不想改了，哈哈。

$\text{Code}$

# include <bits/stdc++.h> # include <bits/extc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }const int N=1e6+100; const int mod=1e9+7;int n,m,tot; int sa[N],rk[N],id[N],oldrk[N],bel[N],len[N],p,cnt[1234567],a[N],l[N],r[N]; ll h[N],c[N]; void calc(){for(int k=0,i=1;i<=n;i++){if(k) --k;while(a[i+k]==a[sa[rk[i]-1]+k]) ++k;h[rk[i]]=k;}return; } bool jd[N]; ll ans,sum[N]; string s[N]; map<string,int>mp;signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifm=read();for(int i=1;i<=m;i++){cin>>s[i];n=s[i].size();for(int j=0;j<n;j++) a[++tot]=s[i][j]-'a'+1,bel[tot]=i;a[++tot]=i+26;bel[tot]=i;jd[tot]=1;len[i]=n;mp[s[i]]++;}for(int i=1;i<=m;i++) c[i]=read();//ans=max(ans,c[i]*len[i]);for(int i=1;i<=m;i++) if(mp[s[i]]==1) ans=max(ans,c[i]*len[i]);n=tot;m+=26;for(int i=1;i<=n;i++) ++cnt[rk[i]=a[i]];for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];for(int i=n;i>=1;i--) sa[cnt[rk[i]]--]=i;for(int w=1;;w<<=1){p=0;for(int i=n;i>n-w;i--) id[++p]=i;for(int i=1;i<=n;i++){if(sa[i]>w) id[++p]=sa[i]-w;}memset(cnt,0,sizeof(cnt));memcpy(oldrk,rk,sizeof(rk));//for(int i=1;i<=n;i++) printf("%d ",id[i]);//putchar('\n');for(int i=n;i>=1;i--) ++cnt[rk[id[i]]];for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];for(int i=n;i>=1;i--) sa[cnt[rk[id[i]]]--]=id[i];p=0;for(int i=1;i<=n;i++){if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w]) rk[sa[i]]=p;else rk[sa[i]]=++p;}m=p;//for(int i=1;i<=n;i++) printf("%d ",sa[i]);//putchar('\n');if(m==n) break;}calc();for(int i=1;i<=n;i++) sum[i]=sum[i-1]+c[bel[sa[i]]]; for(int i=1;i<=n;i++){l[i]=i;//printf("i=%d\n",i);while(l[i]>1&&h[l[i]-1]>=h[i]) l[i]=l[l[i]-1];}for(int i=n;i>=1;i--){r[i]=i;while(r[i]<n&&h[r[i]+1]>=h[i]) r[i]=r[r[i]+1];}//for(int i=1;i<=n;i++){//printf("i=%d pl=%d h=%lld l=%d r=%d sum=%lld tmp=%lld\n",// i,sa[i],h[i],l[i],r[i],sum[i],h[i]*(sum[r[i]]-sum[max(0,l[i]-2)]));//}for(int i=2;i<=n;i++){ ans=max(ans,h[i]*(sum[r[i]]-sum[max(0,l[i]-2)]));}printf("%lld\n",ans);return 0; } /* 5 bbbab bbaab bbbaa bbabb babba 3 -9 8 -3 9 */

總結

以上是生活随笔為你收集整理的CodeForces616:Educational Round 5的全部內容，希望文章能夠幫你解決所遇到的問題。

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