社区讨论

一放到这上面就都变为0了?

P1026[NOIP 2001 提高组] 统计单词个数参与者 8已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mi6h105k
此快照首次捕获于
2025/11/20 04:44
4 个月前
此快照最后确认于
2025/11/20 04:44
4 个月前
查看原帖
为什么本地机上测试都是对的(下了数据),一放到这上面就都变为0了?
我没有用string啊?急急急!望大佬解答,谢谢。
CPP
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 250
using namespace std;
struct key{char s[2001],lon;}b[2001];
char a[5000];
int f[3000][3000];
int comp(key a,key b)
{
    if(a.s[1]<b.s[1])return 1;
    if(a.s[1]==b.s[1] && a.lon<b.lon)return 1;
    if(a.s[1]>b.s[1])return 0;
    if(a.s[1]==b.s[1] && a.lon>b.lon)return 0;
}
int delete1(int N,int sum)
{
    int q,w,l1,l2,i,j,I,t; 
    for(q=1;q<=N;q++)
    {
        if(b[q].s[1]==b[q+1].s[1])
        {
            for(w=q+1;w<=N;w++)if(b[w+1].s[1]!=b[q].s[1])break;  //找到相同的长度 
            l1=q;l2=w;q=w;                //限定处理边界
            for(i=l1;i<=l2;i++)
            {
                for(j=i+1;j<=l2;j++)
                {
                    I=1;
                    if(b[j].lon=='|')continue; 
                    for(t=1;t<=b[i].lon && t<=b[j].lon;t++)
                    {
                        if(b[i].s[t]!=b[j].s[t]){I=0;break;}    //有差异,不为包含 
                    }
                    if(I==1){b[j].s[1]='|';sum--;}   //'|':127   //为包含关系(全部一样)删去长的(已经由长到短排序) 
                }
            } 
        }
    }
    return sum;
}
int check(int ch,int mo,int n,int sum)
{
    int q,w,I,e,r;
    for(q=ch;q<=mo;q++)               //枚举位置 
    {
        for(w=1;w<=n;w++)                //枚举第几个单词 
        {
            if(a[q]==b[w].s[1])
            {
                I=1;
                for(e=2,r=q+1;e<=b[w].lon;e++,r++)       //比较 
                {
                    if(b[w].s[e]!=a[r]){I=0;break;}
                    if(r>mo){I=0;break;}         //超出边界 
                }
                if(I==1)sum++;
            }
        }
    }
    return sum; 
}
int main()
{
    //freopen("A.in","r",stdin);
    int H,k,i,j,t,len,N;char ch;
    scanf("%d%d\n",&H,&k);
    for(i=1;i<=H;i++)
    {
        for(j=1;j<=20;j++)scanf("%c",&a[j+(i-1)*20]);//=getchar();        //拼接 
        scanf("\n");
    }
    len=H*20;                //总长度
    scanf("%d\n",&N);
    for(i=1;i<=N;i++)
    {
        j=0;
        while(666)
        {
            scanf("%c",&ch);//ch=getchar();
            if(ch=='\n' || ch==' ' || ch=='\0' || ch<0)break;      //读入单词 
            j++; b[i].s[j]=ch;
        }
        b[i].lon=j;
    }
    int R=N;
    sort(b+1,b+N+1,comp);           //第一次排序 (未删减)
    N=delete1(N,N);                     //删除包含关系中较长的 
    sort(b+1,b+R+1,comp);           //第二次排序(已删减)  //此时N已经未实际长度 
    //DP: 
    for(i=1;i<=len;i++)f[i][1]=check(1,i,N,0);       //预处理得只分一组的情况  //!!!!!!!!!!!!!!!!!!!!
    for(i=2;i<=len;i++)             //枚举长度 (i==2<------>j==2)
    {
        for(j=2;j<=min(i,k);j++)              //从第二组分起 
        {
            for(t=j-1;t<=i-1;t++)                //分j-1组至少要有j-1个字母
            {
                f[i][j]=max(f[t][j-1]+check(t+1,i,N,0),f[i][j]);
            } 
        }
    }
    printf("%d",f[len][k]);
    return 0;
}

回复

7 条回复,欢迎继续交流。

正在加载回复...