CSP-S模擬37
T1：回文（string）
思路：
由于本題的數(shù)據(jù)范圍較小，所以可能有多種 \(dp\) 狀態(tài)，這里只呈現(xiàn)其中可能較典的兩種外加一種暴搜最優(yōu)解。
DP1：
我們設 \(f_{i,j,x,y}\) 表示使用 \(a\) 串的 \(i\) ~ \(j\) 和 \(b\) 串的 \(x\) ~ \(y\) 能否拼成一個回文串。
首先考慮原始狀態(tài)是什么樣的。顯然原始狀態(tài)有三種大情況： \(a，b\) 中的單個字符，\(a,b\) 中相鄰的兩個相同的字符以及 \(a,b\) 串中相同的字符。這些顯然都是初始能構成回文串的字符。
然后再考慮轉移。顯然有四種轉移方式：\(a\) 串自己左右擴展， \(b\) 串自己左右擴展， \(a\) 串左端與 \(b\) 串右端匹配， \(a\) 串右端與 \(b\) 串左端匹配。
最后我們枚舉每個串截取的長度，然后枚舉起點，計算出終點。若 \(f_{i,j,x,y}\) 為 \(1\) ，則 \(ans=max(ans,lena+lenb)\)。
\(O(Tn^4)\) 的時間復雜度。跑得還是比較快的。
代碼：
$code$
#include<iostream>
#include<cstring>
using namespace std;
int T,n,m,ans,f[55][55][55][55];
string a,b;
int main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
ios::sync_with_stdio(false);
cin>>T;
while(T--){
ans=1;
memset(f,0,sizeof(f));
cin>>a>>b;
a=' '+a;b=' '+b;
n=a.size()-1;m=b.size()-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m+1;j++)
f[i][i][j][j-1]=1;
for(int j=1;j<=m;j++)
for(int i=1;i<=n+1;i++)
f[i][i-1][j][j]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i]==b[j])
f[i][i][j][j]=1;
for(int i=1;i<n;i++){
if(a[i]==a[i+1]){
for(int j=1;j<=m+1;j++){
ans=2;
f[i][i+1][j][j-1]=1;
}
}
}
for(int j=1;j<m;j++){
if(b[j]==b[j+1]){
for(int i=1;i<=n+1;i++){
ans=2;
f[i][i-1][j][j+1]=1;
}
}
}
for(int lena=0;lena<=n;lena++){
for(int i=1;i<=n-lena+1;i++){
int j=i+lena-1;
for(int lenb=0;lenb<=m;lenb++){
for(int x=1;x<=m-lenb+1;x++){
int y=x+lenb-1;
if(f[i][j][x][y]){
ans=max(ans,lena+lenb);
if(i>1&&j<n&&a[i-1]==a[j+1]) f[i-1][j+1][x][y]=1;
if(x>1&&y<m&&b[x-1]==b[y+1]) f[i][j][x-1][y+1]=1;
if(i>1&&y<m&&a[i-1]==b[y+1]) f[i-1][j][x][y+1]=1;
if(x>1&&j<n&&a[j+1]==b[x-1]) f[i][j+1][x-1][y]=1;
}
}
}
}
}
cout<<ans<<'\n';
}
return 0;
}//題解方法 （較快）
DP2：
我們設 \(f_{i,j,x,y}\) 表示使用 \(a\) 串的 \(i\) ~ \(j\) 和 \(b\) 串的 \(x\) ~ \(y\) 能拼成回文串的最長長度。
還是先考慮初始狀態(tài)，顯然跟上面的是一樣的，不過上述的狀態(tài)一初始值為 \(1\) ，狀態(tài)二、三的初始值為 \(2\) （因為存的是長度嘛）
然后轉移就是正常的轉移啦~~
最后取 \(max\) 就好啦~~
時間復雜度也是 \(O(Tn^4)\) 的，不過跑起來不如上面那個快。
$code$
#include<iostream>
#include<cstring>
using namespace std;
int T,m,n,ans,f[55][55][55][55];
string a,b;
int main(){
// freopen("string.in","r",stdin);
// freopen("string.out","w",stdout);
ios::sync_with_stdio(false);
cin>>T;
while(T--){
memset(f,0,sizeof(f));
cin>>a>>b;
a=' '+a;b=' '+b;
n=a.size()-1;m=b.size()-1;
for(int lena=0;lena<=n;lena++){
for(int i=1;i<=n-lena+1;i++){
int j=i+lena-1;
for(int lenb=0;lenb<=m;lenb++){
for(int x=1;x<=m-lenb+1;x++){
int y=x+lenb-1;
if(lena+lenb==1) f[i][j][x][y]=1;
if(lena+lenb==2){
if(!lena&&b[x]==b[y]) f[i][j][x][y]=2;
else if(!lenb&&a[i]==a[j]) f[i][j][x][y]=2;
else if(lena&&lenb&&a[i]==b[x]) f[i][j][x][y]=2;
}
if(lena+lenb!=f[i][j][x][y]) continue;
if(i>1&&j<n&&a[i-1]==a[j+1]) f[i-1][j+1][x][y]=max(f[i-1][j+1][x][y],f[i][j][x][y]+2);
if(x>1&&y<m&&b[x-1]==b[y+1]) f[i][j][x-1][y+1]=max(f[i][j][x-1][y+1],f[i][j][x][y]+2);
if(i>1&&y<m&&a[i-1]==b[y+1]) f[i-1][j][x][y+1]=max(f[i-1][j][x][y+1],f[i][j][x][y]+2);
if(x>1&&j<n&&b[x-1]==a[j+1]) f[i][j+1][x-1][y]=max(f[i][j+1][x-1][y],f[i][j][x][y]+2);
}
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=i-1;j<=n;j++){
for(int x=1;x<=m;x++){
for(int y=x-1;y<=m;y++){
ans=max(ans,f[i][j][x][y]);
}
}
}
}
cout<<ans<<'\n';
}
return 0;
}//分討（較慢）
暴搜：
聽說或許可以構造數(shù)據(jù) \(hack\) 掉？
但目前看來的確是最優(yōu)解無疑了。
我們分別枚舉 \(a,b\) 串的回文中心（記得特判一下回文串長度為偶數(shù)的情況呀），然后跟上面的 \(dp\) 轉移相似，分別向左右暴搜就行了。
復雜度為 \(O(能過)\)（其實是我不會算??）
update： 據(jù)本人說這個代碼的時間復雜度是假的，所以請謹慎使用哦~~
代碼：
$code$
#include<iostream>
using namespace std;
int T,m,n,ans;
string a,b;
inline void dfs(int la,int ra,int lb,int rb,int len){
ans=max(ans,len);
if(la>=1&&ra<=n&&a[la]==a[ra]) dfs(la-1,ra+1,lb,rb,len+2);
if(la>=1&&rb<=m&&a[la]==b[rb]) dfs(la-1,ra,lb,rb+1,len+2);
if(lb>=1&&ra<=n&&b[lb]==a[ra]) dfs(la,ra+1,lb-1,rb,len+2);
if(lb>=1&&rb<=m&&b[lb]==b[rb]) dfs(la,ra,lb-1,rb+1,len+2);
}
int main(){
// freopen("string.in","r",stdin);
// freopen("string.out","w",stdout);
ios::sync_with_stdio(false);
cin>>T;
while(T--){
ans=0;
cin>>a>>b;
a=' '+a;b=' '+b;
n=a.size()-1;m=b.size()-1;
for(int i=1;i<=n+1;i++){
for(int j=1;j<=m+1;j++){
dfs(i-1,i,j-1,j,0);
if(i!=n+1) dfs(i-1,i+1,j-1,j,1);
if(j!=m+1) dfs(i-1,i,j-1,j+1,1);//回文長度為偶數(shù)
}
}
cout<<ans<<'\n';
}
return 0;
}//暴搜（最快）
T2：數(shù)排列（perm）
思路：
嘿，有個 \(O(n^3)\) 的做法沒聽，當時光顧著笑（一些不明事物）了。這里只提供 \(O(n^2)\) 的做法。
我們設 \(f_{i,j}\) 表示數(shù)字 \(i\) 放到 \(j\) 的位置上的合法方案數(shù)，直接枚舉 \(i-1\) 的位置，然后再前/后綴和優(yōu)化一下撒~~
代碼：
$code$
#include<iostream>
using namespace std;
const int N=2025,mod=1e9+7;
int n,s[N],f[N][N],ans;
int main(){
freopen("perm.in","r",stdin);
freopen("perm.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n;
f[0][1]=1;
for(int i=1;i<n;i++) cin>>s[i];
for(int i=1;i<n;i++){
if(s[i]==1) for(int j=2;j<=i+1;j++) f[i][j]=(f[i][j-1]+f[i-1][j-1])%mod;//i放到j位置的方案數(shù)等價于i-1放到所有j-1及以前位置的方案數(shù)加和
else for(int j=i;j>=1;j--) f[i][j]=(f[i][j+1]+f[i-1][j])%mod;
}
for(int i=1;i<=n;i++) ans=(ans+f[n-1][i])%mod;
cout<<ans<<'\n';
return 0;
}//O(n^2)
T3：樹上的背包（knapsack）
思路：
這里提供根號分治和折半搜索兩種思路。
折半搜索：
對于每一次查詢，我們把該節(jié)點及其祖先節(jié)點單獨記錄下來，這樣就轉化為了一個簡單問題：在一堆物品里選代價不超過 \(L\) 且價值最大的物品。不過千萬不要被題目的背包限制住思維，考慮折半搜索。
我們先來淺淺算一下時間復雜度。每個節(jié)點的深度為 \(log~ _n\) （顯然這是一顆二叉樹），所以折半搜的時間復雜度為 \(2^{ \frac{log_n}{2}}\)，轉化一下其實就是 \(\sqrt n\)。再算上多測那就是 \(O(q \sqrt n)\) 。顯然可過，不過跑得不大快，而且碼量相對較大就是了。（相比于根號分治來說）
代碼：
$code$
#include<iostream>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int N=1e5+5;
int n,Q,x,L,cnt,tot1,tot2,ans,v[N],w[N],vl[N],wei[N];
struct flower{
int val,weight;
bool operator<(const flower &css)const{
if(weight!=css.weight) return weight<css.weight;
else return val<css.val;
}
}a[N],s1[N],s2[N];
inline void dfs1(int pos,int weight,int val){
if(weight>L) return ;
if(pos==cnt/2+1){
s1[++tot1]={val,weight};
return ;
}
dfs1(pos+1,weight,val);
dfs1(pos+1,weight+a[pos].weight,val+a[pos].val);
}
inline void dfs2(int pos,int weight,int val){
if(weight>L) return ;
if(pos==cnt+1){
s2[++tot2]={val,weight};
return ;
}
dfs2(pos+1,weight,val);
dfs2(pos+1,weight+a[pos].weight,val+a[pos].val);
}
signed main(){
freopen("knapsack.in","r",stdin);
freopen("knapsack.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
cin>>Q;
while(Q--){
tot1=tot2=ans=cnt=0;
cin>>x>>L;
a[++cnt]={0,0};
while(x){
a[++cnt]=(flower){v[x],w[x]};
x/=2;
}
dfs1(1,0,0);
dfs2(cnt/2+1,0,0);
sort(s1+1,s1+tot1+1);
sort(s2+1,s2+tot2+1);
for(int i=1;i<=tot2;i++) s2[i].val=max(s2[i].val,s2[i-1].val);
for(int i=1,j=tot2;i<=tot1;i++){
while(j&&s2[j].weight+s1[i].weight>L) j--;
if(s1[i].weight+s2[j].weight<=L) ans=max(ans,s1[i].val+s2[j].val);
}
cout<<ans<<'\n';
}
return 0;
}//折半搜 （慢）
/*
3
1 2
2 3
3 4
3
1 1
2 5
3 5
15
123 119
129 120
132 112
126 109
118 103
115 109
102 100
130 120
105 105
132 115
104 102
107 107
127 116
121 104
121 115
8
8 234
9 244
10 226
11 227
12 240
13 237
14 206
15 227
*/
根號分治：
嗨，一種優(yōu)雅的暴力，我覺得沒啥難理解的地方，就不展開啦~~
代碼：
$code$
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+5,maxn=511;
int n,x,l,Q,dp[520][N];
struct flower{
int v,w;
}a[N];
inline int work(int x,int l){
if(l<0) return -1e9;
if(x<=maxn) return dp[x][l];
return max(work(x>>1,l),work(x>>1,l-a[x].w)+a[x].v);
}
int main(){
// freopen("knapsack.in","r",stdin);
// freopen("knapsack.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].v>>a[i].w;
for(int i=1;i<=min(maxn,n);i++){
if(i>>1) memcpy(dp[i],dp[i>>1],sizeof(dp[i]));
for(int j=N-5;j>=a[i].w;j--){
dp[i][j]=max(dp[i][j],dp[i][j-a[i].w]+a[i].v);
}
}
cin>>Q;
while(Q--){
cin>>x>>l;
cout<<work(x,l)<<'\n';
}
return 0;
}
后言：
感謝gyh提醒。
祝阿聯(lián)節(jié)日快樂呀~~
