社区讨论

是不是位运算最慢呀,这两个代码思想一样,但是。。。

P2724[IOI 1998 / USACO3.1] 联系 Contact参与者 7已保存回复 14

讨论操作

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

当前回复
14 条
当前快照
1 份
快照标识符
@mi6hqsnr
此快照首次捕获于
2025/11/20 05:04
4 个月前
此快照最后确认于
2025/11/20 05:09
4 个月前
查看原帖
大神代码(膜拜无敌无敌无敌无敌大佬ylsoi):
CPP
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxm=200000+10;
int a,b,n,len,vis[20][5000],lenth,cnt,point;
struct node{
    int times;
    int lenths;
    int number;
}q[5000];
bool s[maxm];
bool cmp(node a,node b)
{
    if(a.times!=b.times)return a.times>b.times;
    if(a.lenths!=b.lenths)return a.lenths<b.lenths;
    return a.number<b.number;
}
void doit(int x,int size)
{
    if(size==0)return;
    doit(x/2,size-1);
    printf("%d",x%2);
}
int main()
{
    scanf("%d%d%d",&a,&b,&n);
    while(scanf("%c",&s[++len])!=EOF)
        if(s[len]=='\n' || s[len]=='\r')len--;
        else s[len]^='0';
    len--;
    for(int i=a;i<=b;i++){
        int tmp=0;
        for(int j=1;j<i;j++)
        tmp=tmp*2+s[j];
        for(int j=i;j<=len;j++){
            tmp=tmp*2+s[j];
            vis[i][tmp]++;
            tmp-=s[j-i+1]*(1<<(i-1));
        }
    }
    for(int i=a;i<=b;i++)
        for(int j=0;j<=4095;j++)
            if(vis[i][j]){
                cnt++;
                q[cnt].number=j;
                q[cnt].times=vis[i][j];
                q[cnt].lenths=i;
            }
    sort(q+1,q+cnt+1,cmp);
    for(int i=1;i<=cnt;i++){
        point++;
        int h=0;
        printf("%d\n",q[i].times);
        while(q[i].times==q[i+1].times){
            doit(q[i].number,q[i].lenths);
            printf(" ");
            i++;
            h++;
            if(h%6==0)
            cout<<endl;
        }
        doit(q[i].number,q[i].lenths);
        printf(" ");
        cout<<endl;
        if(point==n)break;
    }
    return 0;
}
我的代码:
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int c[200000+10];
int t,a,b,n,cnt;
bool f[13][1<<13];
struct node
{
    int x;
    int sum;
    int len;
}s[(1<<13)*13];
bool cmp(node u,node v)
{
    if(u.sum>v.sum)return 1;
    else if(u.sum==v.sum)
    {
        if(u.len<v.len)return 1;
        else if(u.len==v.len)
            return u.x<v.x;
        return 0;
    }
    return 0;
}
int p[30];
void print(int x,int len)
{
    int tt=0;
    while(x)
    {
        p[++tt]=x%2;
        x/=2;
    }
    for(register int i=1;i<=len-tt;++i)
    printf("0");
    for(register int i=tt;i>=1;--i)
    printf("%d",p[i]);
    printf(" ");
}
int main()
{
    char cc;
    scanf("%d%d%d",&a,&b,&n);
    while(scanf("%c",&cc)!=EOF)
        if(cc=='1'||cc=='0')c[++t]=cc-'0';
    for(register int len=a;len<=b&&len<=t;++len)
    {
        int ws=0,sum=0;
        for(register int i=1;i<=len;++i)
            sum=sum<<1|c[i],
            ws=ws<<1|1;
        if(!f[len][sum])
        {
            s[++cnt].x=sum;
            s[cnt].len=len;
            s[cnt].sum=0;
            f[len][sum]=1;
        }
        for(register int i=len+1;i<=t;++i)
        {
            sum=sum<<1|c[i];
            sum=sum&ws;
            if(!f[len][sum])
            {
                s[++cnt].x=sum;
                s[cnt].len=len;
                s[cnt].sum=0;
                f[len][sum]=1;
            }
        }
    }
    for(register int i=1;i<=cnt;++i)
    {
        int sum=0,ws=0;
        for(register int j=1;j<=s[i].len;++j)
        sum=sum<<1|c[j],
        ws=ws<<1|1;
        if(sum==s[i].x)s[i].sum++;
        for(register int j=s[i].len+1;j<=t;++j)
        {
            sum=sum<<1|c[j];
            sum=sum&ws;
            if(sum==s[i].x)
            s[i].sum++;
        }
    }
    sort(s+1,s+1+cnt,cmp);
    int i=1;
    while(n--)
    {
        int sum=s[i].sum,count=0;
        printf("%d\n",sum);
        while(s[i].sum==sum)
        {
            ++count;
            print(s[i].x,s[i].len);
            if(count%6==0)printf("\n");
            ++i;
        }
        if(count%6)printf("\n");
        if(i>cnt)break;
    }
    return 0;
}
我tle第五个点和第七个点,为什么呀,而且我的测试点普遍很慢

回复

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

正在加载回复...