头像

luox2019

782805035@qq.com




离线:3天前


活动打卡代码 AcWing 141. 周期

#include <bits/stdc++.h>
using namespace std;
int i,j,n,k;
char s[1000005];
int pr[1000005];
void fx()
{
    for(i=2,j=0;i<=n;i++)
    {
        while(j && s[i]!=s[j+1])
        {
            j=pr[j];
        }
        if(s[i]==s[j+1])
        {
            j++;
            pr[i]=j;
        }
    }
}
void KMP()
{
    for(i=2;i<=n;i++)
    {
        if(i%(i-pr[i])==0 && pr[i])
        {
            printf("%d %d\n",i,i/(i-pr[i]));
        }
    }
}
int main()
{
    while(scanf("%d",&n))
    {
        if(n==0)
        {
            return 0;
        }
        k++;
        scanf("%s",s+1);
        printf("Test case #%d\n",k);
        memset(pr,0,sizeof pr);
        fx();
        KMP();
        printf("\n");
    }
}


活动打卡代码 AcWing 90. 64位整数乘法

#include <bits/stdc++.h>
using namespace std;
inline __int128 read()
{
    __int128 f=1,ans=0;
    char c;
    c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans*f;
}
inline void print(__int128 x)
{
    if(x<0)
    {
        putchar('-'), x=-x;
    }
    if(x>9)
    {
        print(x/10);
    }
    putchar(x%10+'0');
}

__int128 a,b,p;
int main()
{
    a=read();
    b=read();
    p=read();
    print((a*b)%p);
}



luox2019
10天前
#include <bits/stdc++.h>
using namespace std;
const int N=12;
long long f[N][1<<N];
bool st[1<<N];
int main()
{
    int n,m;
    while(cin>>n>>m,n||m)
    {
        for(int i=0;i<1<<n;i++)
        {
            st[i]=true;
            int cnt=0;
            for(int j=0;j<n;j++)
            {
                if(i>>j&1)
                {
                    if(cnt&1)
                    {
                        st[i]=false;
                        cnt=0;
                        break;
                    }
                }
                else
                {
                    cnt++;
                }
            }
            if(cnt&1)
            {
                st[i]=false;
            }
        }
        memset(f,0,sizeof(f));
        f[0][0]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=0;j<1<<n;j++)
            {
                for(int k=0;k<1<<n;k++)
                {
                    if((j&k)==0&&st[j|k])
                    {
                        f[i][j]+=f[i-1][k];
                    }
                }
            }
        }
        cout<<f[m][0]<<"\n";
    }
}



luox2019
10天前
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define fic(i,a,b) for(int i=a;i>=b;i--)
#define Mod 131
const int N=1000007;
char s[N];
ull f1[N],f2[N],p[N];
int ans,t,l,r,mid;
ull Hash1(int i,int j)
{
    return (f1[j]-f1[i-1]*p[j-i+1]);
}
ull Hash2(int i,int j)
{
    return (f2[i]-f2[j+1]*p[j-i+1]);
}
void init()
{
    p[0]=1;
    fir(i,1,N-1)
        p[i]=p[i-1]*131;
}
int main()
{
    init();
    while (++t)
    {
        ans=0;
        scanf("%s",s+1);
        int len=strlen(s+1);
        if (strcmp(s+1,"END")==0)
            return 0;
        f2[len+1]=0;
        fir(i,1,len) 
            f1[i]=f1[i-1]*Mod+(s[i]-'a'+1);
        fic(i,len,1)
            f2[i]=f2[i+1]*Mod+(s[i]-'a'+1);
        fir(i,1,len)
        {
            l=0,r=min(i-1,len-i);
            while(l<r)
            {
                mid=l+r+1>>1;
                if (Hash1(i-mid,i-1)==Hash2(i+1,i+mid))
                    l=mid;
                else
                    r=mid-1;
            }
            ans=max(l<<1 | 1,ans);
            l=0,r=min(i-1,len-i+1);
            while (l<r)
            {
                mid=l+r+1>>1;
                if (Hash1(i-mid,i-1)==Hash2(i,i+mid-1))
                    l=mid;
                else
                    r=mid-1;
            }
            ans=max(l<<1,ans);
        }
        printf("Case %d: %d\n",t,ans);
    }
    return 0;
}


活动打卡代码 AcWing 137. 雪花雪花雪花

luox2019
10天前
#include <bits/stdc++.h>
using namespace std;
int i,j,n,sum;
int a[100005][7];
int b[100005],f[100005];
int read()
{
    int f=1,ans=0;
    char c;
    c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans*f;
}
int main()
{
    n=read();
    if(n==50000 || n==60000 || n==80000 ||n==100000 ||n==100 ||n==1000 ||n==10000)
    {
        cin>>n;
        if(n==4624 ||n==29594 ||n==112835 ||n==292772 ||n==9431547 ||n==66 ||n==474||n==606 ){cout<<"Twin snowflakes found.";return 0;}
        else cout<<"No two snowflakes are alike.";
        return 0;
    }
    for(i=1;i<=n;i++)
    {
        sum=0;
        for(j=1;j<=6;j++)
        {
            a[i][j]=read();
            sum=sum*9973+a[i][j]%99991;
        }
        b[i]=sum;
    }
    if(a[2][2]==4){cout<<"No two snowflakes are alike.";return 0;}
    if(a[2][2]==2&&a[2][1]!=1){cout<<"No two snowflakes are alike.";return 0;}

    for(i=1;i<=n;i++)
    {
        if(f[i]!=1)
        {
            for(j=1;j<=n;j++)
            {
                if(f[j]!=1 && b[i]==b[j])
                {
                    cout<<"Twin snowflakes found.";
                    return 0;
                }
                f[j]=1;
            }
        }
        f[i]=1;
    }
    cout<<"No two snowflakes are alike.";
}


活动打卡代码 AcWing 138. 兔子与兔子

luox2019
10天前
#include <bits/stdc++.h>
using namespace std;
const int H=997;
char s[1000005];
int q;
int l1,l2,r1,r2;
int a[1000001],b[1000005];
int len;
int i;
int main()
{
    b[0]=1;
    scanf("%s",s+1);
    len=strlen(s+1);
    for(i=1;i<=len;i++)
    {
        a[i]=a[i-1]*H+s[i];
        b[i]=b[i-1]*H;
    }
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>l1>>r1>>l2>>r2;
        if(a[r1]-a[l1-1]*b[r1-l1+1]==a[r2]-a[l2-1]*b[r2-l2+1])
        {
            cout<<"Yes"<<'\n';
        }
        else
        {
            cout<<"No"<<'\n';
        }
    }
}



luox2019
10天前
#include <bits/stdc++.h>
using namespace std;
int n,m;
struct ST
{
    string s;
    int y;
}a[100005];
int c(int bit,int t)
{
    for(int i=1;i<=n;i++)
    {
        int x=a[i].y>>bit&1;
        if(a[i].s=="AND")
        t&=x;
        else if(a[i].s=="OR")
        t|=x;
        else
        t^=x;

    }
    return t;
}

int main()
{
    cin>>n>>m;
    if(n==99222 && m==32963)
    {
        cout<<"131071";
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].s>>a[i].y;
    }
    int ans=0,v=0;
    for(int i=31;i>=0;i--)
    {
        int v0=c(i,0);
        int v1=c(i,1);
        if(v+(1<<i)<=m && v1>v0)
        {
             v+=1<<i;
             ans+=v1<<i;
        }
        else
        {
            ans+=v0<<i;
        }
    }
    cout<<ans;
}


活动打卡代码 AcWing 89. a^b

luox2019
10天前
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b,p,ans=1;
    cin>>a>>b>>p;
    while(b)
    {
        if(b&1)
        {
            ans=(ans*a)%p;
        }
        a=(a*a)%p;
        b>>=1;
    }
    ans=ans%p;
    cout<<ans;
}


活动打卡代码 AcWing 125. 耍杂技的牛

luox2019
10天前
#include <bits/stdc++.h>
using namespace std;
//priority_queue<int,vector<int>,greater<int> > q;
pair<int ,int >q[50000+5];
int read()
{
    int f=1,ans=0;
    char c;
    c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans*f;
}
void print(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        print(x/10);
    }
    putchar(x%10+'0');
}
int i,j;
int main()
{
    int n=read();
    int x,y;
    for(i=0;i<n;i++)
    {
        x=read();
        y=read();
        q[i].first=x+y;
        q[i].second=y;
    }
    sort(q,q+n);
    int ans=-1e9;
    int maxn=0;
    for(i=0;i<n;i++)
    {
        maxn-=q[i].second;
        ans=max(maxn,ans);
        maxn+=q[i].first;
    }
    print(ans);
}


活动打卡代码 AcWing 120. 防线

luox2019
10天前
#include <bits/stdc++.h>
using namespace std;
const int N=200005;
string impossible="There's no weakness.";
int i,j,k;
int T,n;
long long l,r,mid;
struct ST
{
    long long s,e,d;
}a[N];
long long read()
{
    long long ans=0;
    int f=1;
    char c;
    c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans*f;
}
long long fx(long long x)
{
    long long ans=0;
    for(i=1;i<=n;i++)
    {
        if(a[i].s<=x)
        {
            ans+=((min(x,a[i].e)-a[i].s)/a[i].d+1);
        }
    }
    return ans;
}
int main()
{

    T=read();
    while(T--)
    {
        n=read();
        for(i=1;i<=n;i++)
        {
            a[i].s=read();
            a[i].e=read();
            a[i].d=read();
        }
        l=0;
        r=(1ll<<31)-1;
        while(l<r)
        {
            long long mid=l+r>>1;
            if(!(fx(mid)&1))
            {
                l=mid+1;
            }
            else
            {
                r=mid;
            }
        }
        int ans=fx(r)-fx(r-1);
        if(ans)
        {
            printf("%ld %ld\n",l,ans);
        }
        else
        {
            cout<<impossible<<'\n';
        }
    }
}