來自FallDream的博客，未經允許，請勿轉載

---

奇怪的O(n)大賽，三道題數據都是幾百萬，真嚇人。

-------------------------------------------------

A.交易♂

一個坐標軸上有n個商人，分別在坐標x1.x2..xn(保證遞增且都是正整數)，你和商人在同一位置的時候你可以和他交易，他在t秒后會丟下一個貨物，你和貨物在同一位置的時候可以拿走那個貨物。移動一個單位花費時間1，撿起貨物和交易不消耗時間，你一開始在0號點求拿走所有商人的貨物并且走到點m(m>x)的最小時間。

n<=3000000 x,m,t<=10^9

題解：顯然最優解是我們走很多段，每一段中，我們都是在走過去的時候先交易一下，然后往回走，再往前走，拿走所有貨物。

用f[i]表示拿到前i個貨物并且到達第i個點的最小時間，n^2dp很好列出:$$f[i]=max(f[j]+s[i]-s[j]+max(2*s[i]-2*s[j+1],t)$$

考慮優化，但是這個max怎么辦呢？我們可以把它拆成兩部分，一部分等待時間都是t，只需要求一個最小的坐標更新答案，另一部分我們記一下f[j]-s[j]-2*s[j+1]的最小值就行了，復雜度O(n)

我比較傻還上了一個單調隊列

#include<iostream> #include<cstdio> #define MN 3000000 #define INF 10000000000000000LL #define ll long long #define getchar() (*S++) using namespace std; char B[1<<26],*S=B; inline int read() {int x = 0; char ch = getchar();while(ch < '0' || ch > '9') ch = getchar();while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x; }int n,q[MN+5],top,tail; ll m,t,f[MN+5],mn=INF,s[MN+5];inline ll get1(int x,int y) {while(top>=tail&&q[tail]<y) tail++;if(top<tail)return INF;return f[q[tail]]+t+s[x]-s[q[tail]]; }inline void ins(int x) {while(top>=tail&&f[x]-s[x]<f[q[top]]-s[q[top]]) --top;q[++top]=x; }int main() {freopen("trade.in","r",stdin);freopen("trade.out","w",stdout);fread(B,1,1<<26,stdin);n=read();m=read();t=read();for(int i=1;i<=n;i++)s[i]=read();for(int i=1,j=0;i<=n;i++) {while(j<i&&2*s[i]-2*s[j+1]>=t)mn=min(mn,f[j]-2*s[j+1]-s[j]),++j;ll res1,res2;res1=j<i?get1(i,j):INF;res2=j?mn+3*s[i]:INF;f[i]=min(res1,res2);ins(i);}printf("%lld\n",f[n]+m-s[n]);return 0; }

B.字符串

給定兩個長度都是n的字符串，你要通過一種變換使得第一個字符串變成第二個字符串，求最小變換次數。
所謂的變換是指，對于一個區間[l,r]，從前往后，每個字符都可以變成上一個變成的字符，或者不變。

如果無法完成，輸出-1?? n<=3000000

題解：考慮貪心。我們定義一個k，初始k=n,然后從后往前對于第二個字符串中的第i位，從第一個字符串的第k位之前找一個和它相同的字符，從那個字符更新它肯定最優。

那么我們用f[i]表示第i個字符在多久之前被占用，也就是有多少個操作覆蓋了它。那么每次k前移，f[i]都會+1，而每個$k\leqslant j<i$的j都要用它來更新下一個，也就是說f[j]=max(f[j],f[j+1])+1.

很顯然f[j]一定不會比f[j+1]大,所以f[j]=f[j+1]+1,也就是整個數組的前半部分被我們后移了一位，然后+1? 最后答案就是f的最大值.

考慮實現，后移直接用一個變量統計，+1操作通過差分實現，時間復雜度都是O(n)

#include<iostream> #include<cstdio> #define MN 3000000 using namespace std; inline int read() {int x = 0;; char ch = getchar();while(ch < '0' || ch > '9') ch = getchar();while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x; }int n; int x[MN+5],now=0,move=0,ans=0; char s[MN+5],s2[MN+5];int main() {freopen("string.in","r",stdin);freopen("string.out","w",stdout);n=read();scanf("%s",s+1);scanf("%s",s2+1);for(register int i=n,k=n;i;i--){if(k>i&&s2[i]!=s[i]) k=i;now+=x[i+move],x[i+move]=0;if(k<=i&&s2[i]!=s[k]){while(k&&s[k]!=s2[i]) --k;if(!k) return 0*puts("-1");move++,x[k+move-1]-=1,++now;ans=max(ans,now); }}printf("%d\n",ans);return 0; }

C.矩陣
有一個n*n的矩陣，其中有m個黑塊。如果有兩個塊(x,y)(y,z)都是黑塊，那么你可以把(z,x)涂黑。求你最多能涂黑多少塊。n,m<=1000000

題解：很容易想到轉化成圖論模型，黑塊(x,y)表示第x個點向第y個點連邊。那么考慮暴力染色，將i能到的所有點染色成(col[i]+1)%3

如果存在一種合法的染色方案，且顏色012都有出現，那么此時所有點0向所有點1都有連邊，1->2,2->0同理

這個很容易證明，假設你有一個圖，所有0->1,1->2,2->0都有連邊，那么你隨意加入一個點，假設是一個0->1,那么因為所有2都向0連邊，所以新加的點向所有2都有連邊，那么又因為2到所有0都有連邊，所以所有0到他都有連邊，所以新圖同樣滿足這個結論。而012都出現的圖可以看作一個簡單的0->1->2->0三個點組成的環，你把其他所有點塞進去，一定還是滿足的。

如果存在一種合法的染色方案，且顏色012沒有全部出現，那么此時肯定沒有新增的邊，這個很好理解。

如果沒有合法的染色方案呢？這時候所有點向所有其他點,包括自己，肯定都有邊。這個結論同樣可以證明，當然也可以 打表/畫圖 觀察發現。

嚴格證明我不會，但是你可以隨意選出一個長度不是3的倍數的環，你會發現邊都是滿的。

大概就是這樣，每個聯通塊跑一跑就沒了，復雜度O(n+m)吧。

#include<iostream> #include<cstdio> #define ll long long using namespace std; inline int read() {int x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; }struct edge{int to,next,kind;}e[2000005]; int head[1000005],cnt=0,n,num,m,sum,col[1000005],cou[5]; ll ans=0; bool mark[1000005],flag; inline void ins(int f,int t){e[++cnt]=(edge){t,head[f]};head[f]=cnt;}void dfs(int x) {mark[x]=1;num++;cou[col[x]]++;for(int i=head[x];i;i=e[i].next,++sum)if(!mark[e[i].to]) col[e[i].to]=(col[x]+((i&1)?1:-1)+3)%3,dfs(e[i].to);else if(col[e[i].to]!=(col[x]+((i&1)?1:-1)+3)%3) flag=false; }void solve(int i) {cou[0]=cou[1]=cou[2]=0;flag=true;num=0;sum=0;dfs(i);sum/=2;if(flag) {if(cou[0]&&cou[1]&&cou[2]) ans+=1LL*cou[0]*cou[1]+1LL*cou[2]*cou[0]+1LL*cou[1]*cou[2]-sum; }elseans+=1LL*num*num-sum; }int main() {freopen("matrix.in","r",stdin);freopen("matrix.out","w",stdout);n=read();m=read();for(register int i=1;i<=m;i++){int u=read(),v=read();ins(u,v);ins(v,u);}for(register int i=1;i<=n;i++)if(!mark[i]&&head[i])solve(i);printf("%lld\n",ans+m);return 0; }

?

轉載于:https://www.cnblogs.com/FallDream/p/liankao49.html

總結

以上是生活随笔為你收集整理的[4.9福建四校联考]的全部內容，希望文章能夠幫你解決所遇到的問題。

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