CSP-S模擬37（全真 1）

！CSP-S 全真模擬 1

流程：

$8:00 \to 8:20$：瀏覽題目，了解大致難度。

$8:20 \to 9:20$：發現 T3 很水，過 T3 大樣例。

$9:20 \to 11:00$：找 T1 規律，發現 T1 性質，過 T1 大樣例。

$11:00 \to 11:45$：拼包。

$11:45 \to 11:50$：檢查文件。

$11:50 \to 12:00$：萬 ys。 $\color{white}{\text{原計劃打快}}$

不足：沒拼 T2。

A. 回文 (string)：

noi 大綱【區間 dp】【多維 dp】

比較非常規的一道題。

設 $dp[i][j][p][q]$ 表示串 $a$ 選區間 $[i,j]$，串 $b$ 選區間 $[p,q]$ 時，是否可以構成回文。

將 a 串和 b 串的端點字符分別設為 '!''@''#''$' 防止出鍋。

考慮使用主動轉移的區間 dp 以減少分討。

初始化單個字符為回文，其余直接主動轉移。

就是 $dp[i][i][j][j-1]=1,dp[i][i-1][j][j]=1$。

假設現在枚舉到 $dp[i][j][p][q]$。

四種情況：（dp 左側為艾弗森括號，若為真時執行后續 dp 賦值操作）

\[([i>1][j<len_a][a[i-1]=a[j+1]])dp[i-1][j+1][p][q]=1 \]

\[([p>1][q<len_b][b[p-1]=b[q+1]])dp[i][j][p-1][q+1]=1 \]

\[([i>1][q<len_b][a[i-1]=b[q+1]])dp[i-1][j][p][q+1]=1 \]

\[([p>1][j<len_a][a[j+1]=b[p-1]])dp[i][j+1][p-1][q]=1 \]

最后答案為 $$\max((j-i+1+q-p+1)[dp[i][j][p][q]=1])$$。

注意初始化時應初始化 $[0 ~ len+1]$。否則有一組 Hack：

in:

1
bbabdcdd
a

out:

壞了 Hacker 殺瘋了！！！場上代碼幾乎無一幸免！

我的死因是轉移時右界應到 $len+1$ 而不是 $len$。

Code：

#include<bits/stdc++.h>
using namespace std;
 
inline int read()
{
    int x=0,c=getchar(),f=0;
    for(;c<'0'||c>'9';f=c=='-',c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
    x=(x<<1)+(x<<3)+(c^48);
    return f?-x:x;
}
 
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
 
const int N=55;
char a[55],b[55];
bool dp[N][N][N][N];
 
void solve()
{
    memset(dp,0,sizeof(dp));
    scanf("%s%s",a+1,b+1);
    int la=strlen(a+1),lb=strlen(b+1);
    a[0]='!';
    b[0]='@';
    a[la+1]='#';
    b[lb+1]='$';
    a[la+2]='%';
    b[lb+2]='^';
    a[la+3]='&';
    b[lb+3]='*';
 
    int ans=1;
    for(int i=0;i<=la;i++)
    for(int j=1;j<=lb+1;j++)
    dp[i][i][j][j-1]=1;
 
    for(int i=0;i<=lb;i++)
    for(int j=1;j<=la+1;j++)
    dp[j][j-1][i][i]=1;
 
    for(int i=1;i<=la;i++)
    for(int j=1;j<=lb;j++)
    if(a[i]==b[j]) dp[i][i][j][j]=1;
 
    for(int i=0;i<=la;i++)
    if(a[i]==a[i+1])
    {
        for(int j=1;j<=lb+1;j++)
        dp[i][i+1][j][j-1]=1;
        ans=2;
    }
 
    for(int i=0;i<=lb;i++)
    if(b[i]==b[i+1])
    {
        for(int j=1;j<=la+1;j++)
        dp[j][j-1][i][i+1]=1;
        ans=2;
    }
 
    for(int lena=0;lena<=la+1;lena++)
    {
        for(int i=1;i<=la-lena+2;i++)
        {
            int j=i+lena-1;
 
            for(int lenb=0;lenb<=lb+1;lenb++)
            {
                for(int p=1;p<=lb-lenb+2;p++)
                {
                    int q=p+lenb-1;

                    // cout<<i<<" "<<j<<" "<<p<<" "<<q<<" dp="<<dp[i][j][p][q]<<"\n";

                    if(dp[i][j][p][q])
                    {

                        ans=max(ans,lena+lenb);
                        if(i>=1&&j<=la&&a[i-1]==a[j+1]) dp[i-1][j+1][p][q]=1;
                        if(p>=1&&q<=lb&&b[p-1]==b[q+1]) dp[i][j][p-1][q+1]=1;
                        if(i>=1&&q<=lb&&a[i-1]==b[q+1]) dp[i-1][j][p][q+1]=1;
                        if(p>=1&&j<=la&&b[p-1]==a[j+1]) dp[i][j+1][p-1][q]=1;
                    }
                }
            }
        }
    }

    // cout<<dp[5][4][2][3]<<"\n";
 
    cout<<ans<<"\n";
}
 
signed main()
{
    freopen("aa.in","r",stdin);
    freopen("aa.out","w",stdout);
 
    int T;
    cin>>T;
    while(T--) solve();
 
    return 0;
}

B. 數排列 (perm)：

Code：

#include<bits/stdc++.h>
#define int long long 
const int mod=1e9+7;
using namespace std;

inline int read()
{
    int x=0,c=getchar(),f=0;
    for(;c<'0'||c>'9';f=c=='-',c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
    x=(x<<1)+(x<<3)+(c^48);
    return f?-x:x;
}

inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

int n;
int a[1<<20];
int f[2005][2005];

signed main()
{
	freopen("perm.in","r",stdin);
	freopen("perm.out","w",stdout);
	n=read();

	if(n<=1) { cout<<1<<endl; return 0; }

	for(int i=1;i<n;i++) a[i]=read();

	f[0][1]=1;
    
	for(int i=1;i<n;i++)
    {
		if(a[i]==1)
        {
			for(int j=2;j<=i+1;j++)
            {
				f[i][j]=f[i][j-1]+f[i-1][j-1];
				f[i][j]%=mod;
			}
		}
        else
        {
			for(int j=i;j>=1;j--)
            {
				f[i][j]=f[i][j+1]+f[i-1][j];
				f[i][j]%=mod;
			}
		}
	}

	int ans=0;
	for(int j=1;j<=n;j++)
    {
		ans+=f[n-1][j];
		ans%=mod;
	}
    
	cout<<ans;
	return 0;
}

C. 樹上的背包 (knapsack)：

發現建樹操作建出來的每個點 $i$ 的樹高就是 $\log_2{i}\le 17$。

考慮直接暴力折半搜索。

設 $f(i)=(i+1)\times 2^i$ 為搜索 $i$ 個點并將結果排序之后的總時間復雜度。

復雜度 $O(n \times (f(8) + f(9)))$ 直接爆炸（排序復雜度占大頭）。

考慮優化。

可以先預處理一部分點的折半搜索的結果。

假設我們將深度為 $B$ 的點到根的搜索結果求出。

復雜度變為 $O(2^B times f(B) + n\times f(\max(B-1,17-B)) )$。實際取 $B=10$ 時最優。

Code：

#include<bits/stdc++.h>
#define int long long 
using namespace std;

inline int read()
{
    int x=0,c=getchar(),f=0;
    for(;c<'0'||c>'9';f=c=='-',c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
    x=(x<<1)+(x<<3)+(c^48);
    return f?-x:x;
}

inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const int N=1e5+5;
int n;
int fa[N];
int dep[N];
int id[N];
int v[N],w[N];
struct Node{
    int val,cost;
};
bool cmp(Node x,Node y) { return x.cost<y.cost||(x.cost==y.cost&&x.val>y.val); }
vector<Node> nw,nw2;
const int limit=10;
vector<Node> vec[(1<<limit)+limit];

void dfs1(int p,int val,int cost)
{

    if(!p) { nw.emplace_back(Node{val,cost}); return; }
    dfs1(fa[p],val,cost);
    dfs1(fa[p],val+v[p],cost+w[p]);
}

void dfs2(int p,int minn,int val,int cost)
{
    if(dep[p]<minn) { nw2.emplace_back(Node{val,cost}); return; }
    dfs2(fa[p],minn,val,cost);
    dfs2(fa[p],minn,val+v[p],cost+w[p]);
}

void solve(int p,int id)
{
    dfs1(p,0,0);
    sort(nw.begin(),nw.end(),cmp);
    swap(nw,vec[id]);
}

signed main()
{
    freopen("knapsack.in","r",stdin);
    freopen("knapsack.out","w",stdout);

    n=read();
    dep[1]=1;
    for(int i=2;i<=n;i++)
    {
        dep[i]=dep[i>>1]+1;
        fa[i]=(i>>1);
    }
    for(int i=1;i<=n;i++)
    {
        v[i]=read();
        w[i]=read();
    }
    int tot=0;
    // nw.reserve(1<<limit);
    for(int i=1;i<=n;i++)
    {
        if(dep[i]==limit)
        {
            id[i]=++tot;
            // v[id[i]].reserve(1<<limit);
            solve(i,id[i]);
            // cout<<"i="<<i<<" id="<<id[i]<<"\n";
            // for(Node a:vec[id[i]])
            // {
            //     cout<<"cost="<<a.cost<<" val="<<a.val<<"\n";
            // }
            // cout<<"\n";
        }
    }

    // return 0;

// return 0;
    int Q=read();
    while(Q--)
    {
        int u=read(),L=read();
        
        // nw.clear();
        // dfs1(u,0,0);
        // {
        //     int ans=0;
        //     for(const Node &i:nw)
        //     {
        //         if(i.cost<=L) ans=max(ans,i.val);
        //         // else break;
        //     }
        //     write(ans);
        //     putchar('\n');

        //     continue;    
        // }

        if(dep[u]==limit)
        {
            int ans=0;
            for(const Node &i:vec[id[u]])
            {
                if(i.cost<=L) ans=max(ans,i.val);
                // else break;
            }
            write(ans);
            putchar('\n');
            continue;
        }
        nw2.clear();
        nw.clear();
        int faa=u;
        if(dep[u]<limit)
        {
            for(int i=1;i<=((dep[u]-1)>>1);i++) faa=fa[u];
            dfs1(fa[faa],0,0);
            dfs2(u,dep[faa],0,0);
            sort(nw.begin(),nw.end(),cmp);
            sort(nw2.begin(),nw2.end(),cmp);
        }
        else
        {
            for(int i=limit+1;i<=dep[u];i++) faa=fa[faa];
            nw2.clear();
            dfs2(u,limit+1,0,0);
            sort(nw2.begin(),nw2.end(),cmp);
            swap(vec[id[faa]],nw);
        }
        int ans=0,ma1=0;
        int pos=0;
        int len=nw.size();
        for(int i=nw2.size()-1;i>=0;i--)
        {
            if(nw2[i].cost>L) continue;
            while(pos<len&&nw[pos].cost+nw2[i].cost<=L)
            {
                ma1=max(ma1,nw[pos].val);
                pos++;
            }
            ans=max(ans,ma1+nw2[i].val);
        }
        write(ans);
        putchar('\n');
        if(dep[u]>limit) swap(vec[id[faa]],nw);
    }
    // cout<<dep[n]<<"\n";

    return 0;
}

D. 開會 (meeting)：

Code：

posted @ 2025-10-24 07:42 Wy_x 閱讀(28) 評論(1) 收藏舉報

刷新頁面返回頂部

? つ ?_? ?つ Wy-x 的 blog ??

鳳凰臺上鳳凰游，鳳去臺空江自流。

CSP-S模擬37（全真 1）

！CSP-S 全真模擬 1

A. 回文 (string)：

Code：

B. 數排列 (perm)：

Code：

C. 樹上的背包 (knapsack)：

Code：

D. 開會 (meeting)：

Code：

公告