「ZYB和售貨機·ZYB玩字元串·午餐·計數」 on 9.14
我在時光斑駁深處，聆聽到花開的聲音。
前言
這套題好像是随便拼接起來的，來自三套不同的題，最後一道還是學長出的（nb
場上為數不多的幾次死磕一道題正解，大概有三個小時吧（慚愧，前兩個小時看錯題了，一直以為是外向樹，幸虧後面發現部分結論仍然适用。。
然後碼完之後錯誤不算太多就是沒寫對拍（然後我就 30pts 了。。。
考完之後寫了一個對拍整了幾組資料就過了（也許是題庫資料水吧，WindZR已經把我給 Hack 了。。。但是懶地改了。
果然打出來沒有對拍的正解就是個廢物。。
T1 ZYB和售貨機
解題思路
看到這個題的第一眼就發現是一個 n 個點 n 條邊的圖，一開始是以為 \(f_i\) 互不相同隻需要找到環就好了，然後我的考試時間就少了一個小時。
後來又看了一邊題，以為是個外向樹，大概和 Tarjan 有關系，然後我的考試時間就又少了一個小時。
這個題顯然是一個由多個内向樹構成的森林，我們隻需要對于每一棵樹進行處理就好了。
不難發現其實在所有物品都有剩餘也就是不為零的時候我們是可以随便購買的，是以将所有可購買的點都用最大的利潤也就是最小如價買到隻剩下一個。
然後對于每一棵樹，限制他的隻是環裡的點，分情況讨論，這個點的最小入價是否來自于環裡，但凡有一個不是我們就可以直接斷開這個點的連接配接，這樣就可以把所有的點都以最優的方式購買了。
對于在環内并且最小入價的點也在環内的點我們先按不在環内的最小值計入答案最後再把所有受限制的點選擇删去貢獻最小的就好了。
我的代碼實作就比較惡心了（也就 170 行，是以下面也會放一下 fengwu 的 30 行超短代碼。。
code
170行的。。。
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e5+10,INF=1e18;
struct Node
{
int id,to,c,d,a;
vector<int> fro;
}s[N];
int n,ans,cnt,top,id[N],sta[N];
bool flag,vis[N];
pair<int,int> jl;
vector<int> v[N],vec;
queue<int> q;
void dfs(int x)
{
if(flag) return;
sta[++top]=x;id[x]=top;
for(int i=0;i<s[x].fro.size();i++)
{
int to=s[x].fro[i];
if(id[to])
{
flag=true;
jl.first=id[to];
jl.second=id[x];
return ;
}
dfs(to);
}
top--;
}
signed main()
{
freopen("goods.in","r",stdin); freopen("goods.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
{
s[i].to=read(); s[i].c=read();
s[i].d=read(); s[i].a=read();
s[i].id=i;
}
for(int i=1;i<=n;i++) s[s[i].to].fro.push_back(i);
for(int i=1;i<=n;i++)
{
int minn=INF;
for(int j=0;j<s[i].fro.size();j++)
minn=min(minn,s[s[i].fro[j]].c);
if(minn>s[i].d) continue;
ans+=(s[i].d-minn)*(s[i].a-1); s[i].a=1;
}
for(int i=1;i<=n;i++)
{
if(vis[i]||!s[i].fro.size()) continue;
q.push(i);cnt++;
while(!q.empty())
{
int x=q.front();q.pop();
if(vis[x]) continue;
vis[x]=true;v[cnt].push_back(x);
for(int j=0;j<s[x].fro.size();j++)
q.push(s[x].fro[j]);
}
}
memset(vis,false,sizeof(vis));
for(int i=1;i<=cnt;i++)
{ top=0; flag=false;
int pos=0;
while(pos<v[i].size())
{
if(!s[v[i][pos]].fro.size()) pos++;
else break;
}
dfs(v[i][pos]);
if(jl.first==jl.second)
{
for(int j=0;j<v[i].size();j++)
{
int minn=INF,x=v[i][j];
for(int k=0;k<s[x].fro.size();k++)
minn=min(minn,s[s[x].fro[k]].c);
if(minn>s[x].d) continue;
ans+=s[x].d-minn; s[x].a=0;
}
continue;
}
vector<int>().swap(vec);
bool jud=false;
for(int j=jl.first;j<=jl.second;j++) vis[sta[j]]=true;
for(int j=jl.first;j<=jl.second;j++)
{
int minn=INF,pos=0,x=sta[j];
for(int k=0;k<s[x].fro.size();k++)
if(minn>s[s[x].fro[k]].c) minn=s[s[x].fro[k]].c,pos=s[x].fro[k];
if(minn>s[x].d)
{
if(vis[pos]) break;
continue;
}
if(vis[pos]){jud=true;break;}
}
if(!jud)
{
for(int j=0;j<v[i].size();j++)
{
int minn=INF,x=v[i][j];
for(int k=0;k<s[x].fro.size();k++)
minn=min(minn,s[s[x].fro[k]].c);
if(minn>=s[x].d) continue;
ans+=s[x].d-minn; s[x].a=0;
}
continue;
}
for(int j=jl.first;j<=jl.second;j++)
{
int minn=INF,sec=INF,pos2=0,pos=0,x=sta[j];
for(int k=0;k<s[x].fro.size();k++)
if(minn>=s[s[x].fro[k]].c)
{
if(minn==s[s[x].fro[k]].c&&vis[s[s[x].fro[k]].c]) pos=s[s[x].fro[k]].c;
minn=s[s[x].fro[k]].c;
pos=s[x].fro[k];
}
for(int k=0;k<s[x].fro.size();k++)
if(pos!=s[x].fro[k]&&vis[s[x].fro[k]])
{
vec.push_back(-INF);
goto V;
}
if(minn>=s[x].d){if(vis[pos])vec.push_back(-INF);continue;}
if(!vis[pos]){ans+=s[x].d-minn;continue;}
for(int k=0;k<s[x].fro.size();k++)
if(sec>s[s[x].fro[k]].c&&s[x].fro[k]!=pos)
sec=s[s[x].fro[k]].c,pos2=s[x].fro[k];
if(sec==INF||sec>=s[x].d)
{
vec.push_back(s[x].d-minn);
continue;
}
vec.push_back(sec-minn);
ans+=s[x].d-sec; s[x].a=0;
V:;
}
sort(vec.begin(),vec.end());
for(int j=1;j<vec.size();j++)
if(vec[j]>0)
ans+=vec[j];
for(int j=0;j<v[i].size();j++)
{
int minn=INF,x=v[i][j];
for(int k=0;k<s[x].fro.size();k++)
if(!vis[s[x].fro[k]])
minn=min(minn,s[s[x].fro[k]].c);
if(minn>=s[x].d) continue;
ans+=(s[x].d-minn)*s[x].a; s[x].a=0;
}
}
printf("%lld",ans);
return 0;
}
30行的極緻體驗
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register int
const int N=1e6+5;
const int inf=1e9;
int n,f[N],c[N],d[N],a[N],v[N];
int mx[N],nx[N],mn,bel[N],cnt;
ll ans;
void dfs(int x){
if(bel[x]==cnt){ans-=mn;return ;}
if(bel[x])return ;
bel[x]=cnt;
if(!mx[x])return ;
ans+=1ll*v[mx[x]]*a[x];
mn=min(mn,v[mx[x]]-v[nx[x]]);
if(mx[x]!=x)dfs(mx[x]);
}
signed main(){
freopen("goods.in","r",stdin);freopen("goods.out","w",stdout);
scanf("%d",&n);
for(re i=1;i<=n;i++)scanf("%d%d%d%d",&f[i],&c[i],&d[i],&a[i]);
for(re i=1;i<=n;i++){
v[i]=d[f[i]]-c[i];
if(v[i]>=v[mx[f[i]]])nx[f[i]]=mx[f[i]],mx[f[i]]=i;
else if(v[i]>=v[nx[f[i]]])nx[f[i]]=i;
}
for(re i=1;i<=n;i++)if(!bel[i])mn=inf,++cnt,dfs(i);
printf("%lld",ans);
}
T2 ZYB玩字元串
官方題解寫的特别明白就是兩個 DP 柿子。
主要解釋一下暴力為什麼不對，在我們暴力掃的時候如果同時有兩個可以消去的一個可能是對于正确答案不可以消去的，也就是他是由一段字尾加上一段字首的組成方式，由于某些玄學因素看似合法了。。
給出對于這份代碼的兩組Hack資料（如果這個做法是正确的話他正着掃和反着掃得分是一樣的，但是在 OJ 上卻是 30 和 50）
ddaddadad
輸出應該是
dad
但是反着掃的結果是
ddaddadad
cdcdcdccc
cdc
但是正着掃的結果是
cdcdcdccc
下面也會給出一組造随機資料的程式，其實就是随一個字元串然後向裡面随機插入就好了。
正解 DP 方程的正确性的前提是要保證所掃到的字串的長度要是整個串長度的因數，\(f_{i,j}\) 表示區間 \([i,j]\) 能否合法或者能否消光。
轉移方程就是下面的兩個（盡管有關于代碼的不能用 Latex，但是代碼快真的好醜）
\[f_{i,j}|=f_{i,j}\&[a_j=p_{(j-i)\bmod len +1}]
\]
\[f_{i,j}|=f_{i,j-k\times len}\&f_{j-k\times len+1,j},k\times len\in[1,j-i]
注意這裡的 p 就是我們掃到的字元串下标從 1 開始，顯然轉移應該從小的區間到大的區間，是以區間 DP 就可以了。
最後有幾個小優化：s 的每種字元是不是 p 中對應的整數倍，p 的開頭和結尾一定是 S 的開頭或者結尾，記錄一下 p 是否已經被計算過。
然後我們的時間就 \(3000ms\rightarrow500ms\rightarrow50ms\)
正解
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=300;
int T,n,all[26],tot[26],f[N][N];
char s[N],ch[N];
unordered_map<string,bool> mp;
void solve()
{
scanf("%s",s+1); n=strlen(s+1); memset(all,0,sizeof(all)); mp.clear();
for(int i=1;i<=n;i++) all[s[i]-'a']++;
for(int len=1;len<=n;len++)
if(n%len==0)
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1; memset(tot,0,sizeof(tot));
if(s[l]!=s[1]||s[r]!=s[n]) continue; string c;
for(int i=l;i<=r;i++) ch[i-l+1]=s[i],c.push_back(s[i]);
if(mp.find(c)!=mp.end()) continue; mp.insert(make_pair(c,true));
for(int i=1;i<=len;i++) tot[ch[i]-'a']++;
for(int i=0;i<26;i++) if(tot[i])if(all[i]%tot[i]) goto V;
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++) f[i][i]=(s[i]==ch[1]);
for(int ll=2;ll<=n;ll++)
for(int i=1;i+ll-1<=n;i++)
{
int j=i+ll-1;
f[i][j]|=f[i][j-1]&(s[j]==ch[(j-i)%len+1]);
for(int k=1;j-k*len>=i&&!f[i][j];k++)
f[i][j]|=f[i][j-k*len]&f[j-k*len+1][j];
}
if(f[1][n])
{
for(int i=1;i<=len;i++) printf("%c",ch[i]);
printf("\n");
return ;
}V:;
}
}
signed main()
{
freopen("string.in","r",stdin); freopen("string.out","w",stdout);
T=read(); while(T--) solve();
return 0;
}
資料生成器
#include <bits/stdc++.h>
using namespace std;
int main() {
srand((int)time(0));
int T = 10, sum = 0;cout<<T<<endl;
while (T--) {
int m =3;
string p = "";
int k = rand() % 26 + 1;
while (m--) p = p + (char)('a' + rand() % k);
int num = 3;
string s = "";
while (num--) {
int k = rand() % (s.length() + 1);
s = s.substr(0, k) + p + s.substr(k);
}
cout << s << endl;
//fprintf(stderr, "%d\n", s.length());
sum += s.length();
}
//fprintf(stderr, "%d\n", sum);
}
T3 午餐
很玄學的一道最短路題。
第一邊是通過無法學會的人為起點通過 不用進行的聚餐 進行轉移 \(h_i\) 表示隻考慮 -1 的情況下最早的學會時間。
對于一條邊也就是一次聚餐時間為 \(L,R\)，我們要從 x 到 to 轉移方程就是：
\[h_{to}=L+1,h_x>R且h_{to}<L+1
再跑一次最短路從 1 開始，求出最終的答案然後這次跑的就是 用進行的聚餐
設 \(lim=\max\{L,h_{to},ans_x\}\)，則 \(ans_{to}=lim,lim\le R且 ans_{to}>lim\)
最後輸出的時候判斷是否相沖突就好了，注意如果一個點最終不能學會那麼他一定不可能和 1 連邊。
如果一條邊連接配接的有最終不能學會的，那麼時間最好就是 \(L\) 如果這場聚餐無所謂其實可以是 \([L,R]\) 中的任何一個數，但是由于題庫的 SPJ 有點小問題是以隻可以是 L 。
如果有必要舉行那麼答案就是 \(\max\{L,ans_x,ans_y\}\)
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=2e6+10,INF=0x3f3f3f3f3f3f3f3f;
int n,m,s[N],ans[N],h[N];
int tot=1,head[N],nxt[N<<1],ver[N<<1],val[N<<1],var[N<<1];
bool vis[N];
struct Queue{int l,r,num[N];void push(int x){num[++r]=x;}void pop(){l++;}int front(){return num[l];}bool empty(){return l>r;}}q;
void add_edge(int x,int y,int l,int r){ver[++tot]=y;nxt[tot]=head[x];val[tot]=l;var[tot]=r;head[x]=tot;}
signed main()
{
freopen("lunch.in","r",stdin); freopen("lunch.out","w",stdout);
srand(time(0)); n=read(); m=read(); memset(ans,0x3f,sizeof(ans));
for(int i=1,x,y,l,r;i<=m;i++) x=read(),y=read(),l=read(),r=read(),add_edge(x,y,l,r),add_edge(y,x,l,r);
for(int i=1;i<=n;i++) s[i]=read();
for(int i=1;i<=n;i++) if(s[i]==-1) h[i]=INF,q.push(i),vis[i]=true;
while(!q.empty())
{
int x=q.front();q.pop();vis[x]=false;
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i],l=val[i],r=var[i];
if(h[x]<=r||h[to]>=l+1) continue;
h[to]=l+1; if(!vis[to]) q.push(to),vis[to]=true;
}
}
q.push(1);ans[1]=0;vis[1]=true;
while(!q.empty())
{
int x=q.front();q.pop();vis[x]=false;
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i],l=val[i],r=var[i];
int lim=max(l,max(h[to],ans[x]));
if(lim>r||ans[to]<=lim) continue;
ans[to]=lim; if(!vis[to]) q.push(to),vis[to]=true;
}
}
for(int i=1;i<=n;i++)if(s[i]==1&&ans[i]>=INF){printf("Impossible");return 0;}
for(int i=head[1];i;i=nxt[i])if(s[ver[i]]==-1){printf("Impossible");return 0;}
for(int i=1;i<=m;i++)
{
int l=val[i<<1],r=var[i<<1],x=ver[i<<1],y=ver[i<<1|1];
if(ans[x]==-1||ans[y]==-1){printf("%lld\n",l);continue;}
printf("%lld\n",max(ans[x],ans[y])>r?l:max(l,max(ans[x],ans[y])));
}
return 0;
}
T4 計數
rvalue 學長不僅題目出的好而且官方題解寫的也非常 nb，于是我們直接。。。（這個題的轉移是有類似于區間性質的是以我選擇了記憶化搜尋的寫法）
首先我們可以根據前序周遊的定義分析出一棵符合前序周遊限制的樹的一些性質:
- 這棵樹的編号滿足小根堆性質
- 這棵樹的某個子樹編号連續,為 \([root,root+size-1]\)
- 這棵樹左子樹中的結點編号都小于右子樹
- 這棵樹任意一個有左子節點的節點的左子節點編号必定為該節點編号 +1
然後我們來看中序周遊限制. 首先我們強制 \(a<b\) , 然後将限制轉化為“強制 a 在 b 前”或“強制 a 在 b 後”.
因為\(a<b\), 再加上上面的性質, 是以 a 和 b 隻有兩種位置關系:
- a 是 b 的祖先
- a 在 LCA 的左子樹且 b 在LCA 的右子樹.
我們來分析一下兩種限制條件:
-
限制1: 強制 a 在 b 後:
這種情況下 a 一定是 b 的祖先, 因為如果他們的位置關系是第二種的話,a 在中序周遊中一定在 b 之前. 是以 b 一定在 a 的左子樹中
-
限制2: 強制 a 在 b 前:
這種情況下兩種位置關系都有可能, 如果是位置關系 1 則 b 在 a 的右子樹, 如果是位置關系 2 則 b 不在該子樹中. 這種限制和 b 不在 a 的左子樹中等價
因為子樹中結點編号連續, 是以上述限制條件都可以轉化為對 的左子樹大小的限制.
對于第一種限制, 則根據性質 2 和 4, 左子樹大小不小于 \(b-a\) 是該限制被滿足的充要條件. 對于第二種限制, 左子樹大小小于 \(b-a\) 是該限制被滿足的充要條件.
是以我們隻需要将每個節點的左子樹大小限制預處理出來即可. 方式就是對于每個 a 都計算出限制 1的 b 的最大值和限制2 的 b 的最小值. 定義狀态 \(f_{i,j}\) 表示根節點為 i 子樹大小為 j 的合法方案數量, 枚舉左子樹配置設定到的子樹大小轉移即可. 也即
\[\displaystyle f_{i,j}=\sum_{k=low_i}^{hig_i}f_{i+1,k}\times f_{i+k+1,j-k-1}
k 就是可行的左子樹大小
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=3e3+10,M=3e3+10,mod=1e9+7,INF=1e18;
int n,m,T,f[N][M],low[N],hig[N];
struct Node
{
int x,y;
}s[M];
int dfs(int x,int siz)
{
if(~f[x][siz]) return f[x][siz];
if(siz==0||x==n) return f[x][siz]=1;
int rec=0,fro=low[x],to=min(siz-1,hig[x]);
for(int i=fro;i<=to;i++) rec=(rec+dfs(x+1,i)*dfs(x+i+1,siz-i-1))%mod;
return f[x][siz]=rec;
}
void solve()
{
n=read(); m=read();
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++) low[i]=0,hig[i]=n-i+1;
for(int i=1;i<=m;i++) s[i].x=read(),s[i].y=read();
for(int i=1;i<=m;i++)
if(s[i].x<s[i].y) hig[s[i].x]=min(hig[s[i].x],s[i].y-s[i].x-1);
else low[s[i].y]=max(low[s[i].y],s[i].x-s[i].y);
printf("%lld\n",dfs(1,n));
}
signed main()
{
freopen("count.in","r",stdin); freopen("count.out","w",stdout);
T=read(); while(T--) solve();
return 0;
}