2022/8/13

活动地址：CSDN21天学习挑战赛

E-Slash_牛客小白月赛54 (nowcoder.com) dp

        dp[i][j][k]表示在i,j这个位置匹配到了s串的第k位所能包含的s的最大个数，那么转移方程也可以求出来 在a[i][j]==s[k]的情况下,dp[i][j][k]=max(dp[i-1][j][k-1],dp[i][j-1][k-1]);

假设abcdabc,  s=abc,为了方便转移设dp[1][9][0]=2,dp[1][9][3]=1,所以遍历完串之后要有dp[i][j][0]=dp[i][j][len](len为s的长度),同时0也表示开始匹配新s串，所以其实0可以在任何情况下被转移到，不需要非得是len才可以，所以需要再遍历一遍k进行更新，这样可以做到不漏掉每一个状态

E_哔哩哔哩_bilibili

#include 
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=1e9+7;
double eps=1e-8;
ll n,m,dp[105][105][105];
char s[105],a[105][105];
int main(){
    scanf("%lld%lld%s",&n,&m,s+1);
    ll len=strlen(s+1);
    for(int i=0;i<=n;i++)
    for(int j=0;j<=m;j++)
    for(int k=0;k<=len;k++) dp[i][j][k]=-1e8;
    dp[0][1][0]=0;
    for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        for(int k=1;k<=len;k++){
            if(a[i][j]==s[k]) dp[i][j][k]=max(dp[i-1][j][k-1],dp[i][j-1][k-1]);
        }
        dp[i][j][0]=dp[i][j][len]+1;
        
        for(int k=0;k<=len;k++) dp[i][j][0]=max({dp[i][j][0],dp[i-1][j][k],dp[i][j-1][k]});
        //cout<
    }
    ll ans=0;
    for(int i=0;i<=len;i++) ans=max(ans,dp[n][m][i]);
    printf("%lld\n", ans);
    system("pause");
    return 0;
}

F-Traveling_牛客小白月赛54 (nowcoder.com) 构造

自己一定是做不出这题来的，，，可以看出d[1]一定是和d[n]相同的，并且m不能大于完全图所需要的边数，因为题目不能是重边；这样可以先把1和n连上，然后对于d[i]-d[1]为偶数的点可以直接连1，权值为(d[i]-d[1])/2,对于奇数的点，找到权值最小的点，将权值对半分分别连到1和n，之后剩余的奇数点按照偶数点的连接方式连接到这个最小奇数点就行了，当有奇数点且d[1]<=0的话是不能构造出来的，所以要特判一下，如果不对半分的话对于这个构造方式来说可能会出来别的路径比d[i]小，所以要对半分

F_哔哩哔哩_bilibili

#include 
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=1e9+7;
double eps=1e-8;
ll n,m,d[300005];
vector>odd,ev;
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&d[i]);
    if(d[1]!=d[n]||m>n*(n-1LL)/2LL||m-1){
        printf("No\n");system("pause");return 0;
    }
    for(int i=2;i
        if(d[i]-d[1]<0){printf("No\n");system("pause");return 0;}
        if((d[i]-d[1])&1){
            if(d[1]<=0){printf("No\n");system("pause");return 0;}
            odd.push_back({d[i],i});
        }
        else ev.push_back({(d[i]-d[1])/2,i});
    }
    ll need=odd.size()+ev.size()+1+(odd.size()>0);
    if(need>m){printf("No\n");system("pause");return 0;}
    set>s;
    printf("Yes\n");
    printf("%lld %lld %lld\n",1,n,d[1]);
    s.insert({1,n});
    for(int i=0;isize();i++){
        printf("%lld %lld %lld\n",1,ev[i].second,ev[i].first);
        s.insert({1,ev[i].second});
    }
    sort(odd.begin(),odd.end());
    ll id,len;
    for(int i=0;isize();i++){
        if(i==0){
            id=odd[i].second;
            len=odd[i].first;
            printf("%lld %lld %lld\n",1,odd[i].second,len/2);
            printf("%lld %lld %lld\n",odd[i].second,n,len-len/2);
            s.insert({1,odd[i].second});
            s.insert({odd[i].second,n});
            continue;
        }
        
        if(id
            printf("%lld %lld %lld\n",id,odd[i].second,(odd[i].first-len)/2);
            s.insert({id,odd[i].second});
        }
        else{
            printf("%lld %lld %lld\n",odd[i].second,id,(odd[i].first-len)/2);
            s.insert({odd[i].second,id});
        }
    }
    m=m-s.size();
    ll inf=1e9;
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++){
        if(m<=0){system("pause");return 0;}
        if(s.count({i,j})) continue;
        printf("%lld %lld %lld\n",i,j,inf);
        s.insert({i,j});m--;
    }
    system("pause");
    return 0;
}

P2453 [SDOI2006]最短距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) dp

想复杂了，其实就是6种情况分别写出对应的转移方程就可以，但是这个题也不像是状压dp啊，只是一个普通的dp而已，设dp[i][j]为初始串到i，目标串到j所需要的最小代价，然后每种方式都写出转移方程就可以，可能就是需要写6个方程比较繁琐罢了，这题没自己做出来纯属是自己懒惰了

题解 P2453 【[SDOI2006]最短距离】 - LingFengGold 的博客 - 洛谷博客

#include 
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=1e9+7;
double eps=1e-8;
char s[205],t[205];
ll n,m,cost[6],dp[205][205];
int main(){
    scanf("%s%s",s+1,t+1);
    n=strlen(s+1);m=strlen(t+1);
    for(int i=1;i<=5;i++) scanf("%lld",&cost[i]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) dp[i][j]=1e18;
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
        dp[i][0]=cost[1]*i;
    for(int j=1;j<=m;j++)
        dp[0][j]=cost[4]*j;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        if(s[i]==t[j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]+cost[3]);
        dp[i][j]=min(dp[i][j],dp[i-1][j]+cost[1]);
        dp[i][j]=min(dp[i][j],dp[i-1][j-1]+cost[2]);
        dp[i][j]=min(dp[i][j],dp[i][j-1]+cost[4]);
        if(s[i-1]==t[j]&&s[i]==t[j-1]&&i>=2&&j>=2)
            dp[i][j]=min(dp[i][j],dp[i-2][j-2]+cost[5]);
        if(j==m&&imin(dp[n][m],dp[i][m]+cost[1]*(n-i)-1);
    }
    printf("%lld\n",dp[n][m]);
    system("pause");
    return 0;
}

P2591 [ZJOI2009]函数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

看了提示后才发现第一层和最后一层都是有办法将段数变为2，根据相同的思想发现第二层和倒数第二层最小值也是一样，第三层第四层类似，又发现第二层最小可以是4，所以倒数第2层也是4，这样就可以看出规律来了

#include 
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=1e9+7;
double eps=1e-8;
ll n,k;
int main(){
    scanf("%lld%lld",&n,&k);
    if(n==1) printf("1\n");
    else{
        if(k>n/2) k=n-k+1;
        printf("%lld\n",k*2LL);
    }
    system("pause");
    return 0;
}