今天做了一下Infinity37大学姐早期作品qwq

感觉很可以哇……数据出的很棒,成功卡出了我程序中的微小的错误。


Task1 Due

题目大意

求N个字符串对模式串的LCS.

$N \le 10, length \le 1000.$

直接暴力$O(n^2)$求LCS就好了。
题目要求输出LCS最长的一个字符串编号,如果相同就输出靠后的那个,但是我写的时候没注意于是写错= =

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1010
int n,f[N][N],len[15],ans[15],res=1;
char a[N],b[15][N];
int main()
{
    freopen("due.in","r",stdin);
    freopen("due.out","w",stdout);
    scanf("%s%d",a+1,&n);
    len[0]=strlen(a+1);
    for(int i=1;i<=n;++i) scanf("%s",b[i]+1),len[i]=strlen(b[i]+1);
    for(int i=1;i<=n;++i)
    {
        memset(f,0,sizeof f);
        for(int j=1;j<=len[0];++j)
            for(int k=1;k<=len[i];++k)
            {
                if(a[j]==b[i][k]) f[j][k]=f[j-1][k-1]+1;
                else f[j][k]=max(f[j-1][k],f[j][k-1]);
            }
        ans[i]=f[len[0]][len[i]];
    }
    for(int i=1;i<=n;++i)
        if(ans[i]>=ans[res])
            res=i;
    printf("%d\n",res);
}

Task2 Maps

题目大意

给你一个最小生成树,求它的最小生成完全图。

$N \lt 20000, K_i \lt maxint$

这题我似乎做过qwq

考虑还原Kruskal的行为:一条一条边向图里加,之后根据加入的是最小的这一特性还原其他边。

之后我就想出来一个方法:考虑加入每个点。加进去之后直接暴力向已经在里面的点连长度为现在边长+1的边,之后就可以啦。

之后20分滚粗= =

简单想了一下,发现不太对。
考虑这样一个图:1-2,3-4已经连边,2-3有边还没添加。此时我已经确保整个图是完全图了,所以如果2-3的边很大很大,此时我得到的是更优解。所以只能每时刻确保每个联通块是完全图,之后就可以确保整个图是最小生成完全图= =

#include <cstdio>
#include <algorithm>
using namespace std;
#define N 20010
int n,fa[N],sz[N];
long long ans;
bool use[N];
struct edge{long long u,v,w;}e[N];
bool cmp(edge tx,edge ty){return tx.w<ty.w;}
int unifind(int tx){return fa[tx]==tx?tx:fa[tx]=unifind(fa[tx]);}
int main()
{
    freopen("maps.in","r",stdin);
    freopen("maps.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) fa[i]=i,sz[i]=1;
    for(int i=1;i<n;++i) scanf("%lld%lld%lld",&e[i].u,&e[i].v,&e[i].w),ans+=e[i].w;
    sort(e+1,e+n,cmp);
    for(int i=1;i<n;++i)
    {
        int tx=unifind(e[i].u),ty=unifind(e[i].v);
        if(tx!=ty)
        {
            fa[tx]=ty;
            ans+=(1ll*sz[tx]*sz[ty]-1)*(e[i].w+1);
            sz[ty]+=sz[tx];
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Task3 buy

题目大意(保留题面#滑稽):

大学姐去日本买N个偶像团体的周边。如果想购买其中一个团体i的周边需要付$X_i$元才能开始买。买一个周边可以获得$P_i$收益但是要付出$L_i$费用。求总费用不超过W的最大收益。

$w \le 20000,n \le 25,m_i \le 8,x_i \le 1000,l_j \le 1000,p_j \le 1000$

这题一看就是分组背包qwq每组有1个依赖,之后对每组单独进行讨论,然后进行合并……合并……
朴素合并?
合并的时间复杂度是$O(20000^2)$,已经无法接受了。

所以因为从来没写过我就GG了。

明明知道咋写……每次清空一个G数组进行单独的背包,之后进行合并。$G_j$表示花费$j+X_i$的最大收益。之后问题就来了——初始值是啥?

如果是0,那么意思就是我只能选择一组,GG。之后就是初始值究竟咋写清真。实际上应该是$G_i = F_i$,之后更新的时候需要用原值+费用+新费用来进行更新。

用一个图来理解一下。

Explain-infinity-01.PNG

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 30
#define M 20010
int n,w,x[N],m[N],l[N][M],p[N][M],f[M],g[M],ans;
int main()
{
    freopen("buy.in","r",stdin);
    freopen("buy.out","w",stdout);
    scanf("%d%d",&n,&w);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",x+i,m+i);
        for(int j=1;j<=m[i];++j) scanf("%d%d",&l[i][j],&p[i][j]);
    }
    for(int i=1;i<=n;++i)
    {
        memset(g,0,sizeof g);
        for(int j=w;~j;j--)
                g[j]=f[j];
        for(int j=1;j<=m[i];++j)
            for(int k=w;~k;k--)
                if(k>=l[i][j])
                    g[k]=max(g[k],g[k-l[i][j]]+p[i][j]);
        for(int j=w;~j;j--)
            if(j>=x[i])
                f[j]=max(f[j],g[j-x[i]]);
    }
    for(int i=w;~i;i--) if(f[i]>=f[ans]) ans=i;
    printf("%d %d\n",f[ans],w-ans);
    return 0;
}