头像

欧拉AC




离线:2小时前


活动打卡代码 AcWing 1369. 牛之关系谱

欧拉AC
1个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N=210,M=110,mod=9901;

int n,m;
int f[N][M];

int main()
{
    cin>>n>>m;

    for(int i=1;i<=m;i++) f[1][i]=1;

    for(int i=2;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=1;k<=i-2;k++)
                (f[i][j]+=f[k][j-1]*f[i-k-1][j-1])%=mod;

    cout<<(f[n][m]-f[n][m-1]+mod)%mod<<endl;

    return 0;


}


活动打卡代码 AcWing 1368. 最长前缀

欧拉AC
1个月前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>

using namespace std;

typedef unsigned long long ULL;

const int N=2e5+10,P=131;

string str;
bool f[N];

int main()
{
    unordered_set<ULL> hash;
    while(cin>>str,str!=".")
    {
        ULL h=0;
        for(int i=str.size()-1;i>=0;i--)
            h=h*P+str[i];
        hash.insert(h);
    }

    str.clear();

    f[0]=true;
    int res=0;

    string line;
    while(cin>>line) str+=line;

    for(int i=1;i<=str.size();i++)
    {
        ULL h=0;
        for(int j=i;j>i-10 && j>=0;j--)
        {
            h=h*P+str[j-1];
            if(hash.count(h) && f[j-1])
            {
                f[i]=true;
                break;
            }
        }
        if(f[i]) res=i;
    }

    cout<<res<<endl;




    return 0;
}


活动打卡代码 AcWing 1352. 虫洞

欧拉AC
1个月前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=14;

#define x first
#define y second

int n;
int to1[N],to2[N];
bool st[N],used[N][2],cur[N][2];
int ans;

struct Node
{
    int x,y;
    bool operator< (const Node& W)const
    {
        if(y!=W.y) return y<W.y;
        return x<W.x;
    }
}q[N];

bool dfs_c(int a,int b)
{
    if(cur[a][b]) return true;
    if(used[a][b]) return false;

    cur[a][b]=used[a][b]=true;
    bool res=false;

    if(!b)
    {
        if(dfs_c(to2[a],1)) res=true;
    }
    else
    {
        if(to1[a]!=-1 && dfs_c(to1[a],0)) res=true;
    }

    cur[a][b]=false;

    return res;
}

bool check()
{
    memset(used,0,sizeof used);
    memset(cur,0,sizeof cur);

    for(int i=0;i<n;i++)    
        for(int j=0;j<2;j++)
            if(!used[i][j])
                if(dfs_c(i,j))
                    return true;

    return false;
}


void dfs(int u)
{
    if(u==n/2) 
    {
        if(check()) ans++;
        return;
    }

    for(int i=0;i<n;i++)    
        if(!st[i])
        {
            for(int j=i+1;j<n;j++)
                if(!st[j])
                {
                   st[i]=st[j]=true;
                   to2[i]=j,to2[j]=i;
                   dfs(u+1);
                   to2[i]=to2[j]=-1;
                   st[i]=st[j]=false;
                }
                break;
        }

}


int main()
{
    cin>>n;

    memset(to1,-1,sizeof to1);
    memset(to2,-1,sizeof to2);

    for(int i=0;i<n;i++) cin>>q[i].x>>q[i].y;

    sort(q,q+n);

    for(int i=1;i<n;i++)
        if(q[i].y==q[i-1].y)
            to1[i-1]=i;


    dfs(0);

    cout<<ans<<endl;

}


活动打卡代码 AcWing 1085. 不要62

欧拉AC
1个月前
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N=15;

int f[N][10];

void init()
{
    for(int i=0;i<=9;i++)
        if(i!=4)
            f[1][i]=1;

    for(int i=2;i<N;i++)
        for(int j=0;j<=9;j++)
            if(j!=4)
            {
                for(int k=0;k<=9;k++)
                {
                    if(k==4 || j==6 && k==2) continue;
                    f[i][j]+=f[i-1][k];
                }
            }

}


int dp(int n)
{
    if(n==0) return 1;

    vector<int> nums;
    while(n) nums.push_back(n%10),n/=10;

    int res=0;
    int last=0;

    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        for(int j=0;j<x;j++)
        {
            if(j==4 || last==6 && j==2) continue;
            res+=f[i+1][j];
        }

        if(x==4 || last==6 && x==2) break;

        last=x;

        if(i==0) res++;

    }

    return res;
}

int main()
{
    int l,r;

    init();

    while(cin>>l>>r,l||r)
    {
        cout<<dp(r)-dp(l-1)<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 1084. 数字游戏 II

欧拉AC
1个月前
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N=15;

int f[N][10][100];
int P;

int mod(int x,int y)
{
    return (x%y+y)%y;
}

void init()
{
    for(int i=0;i<=9;i++) f[1][i][i%P]++;

    for(int i=2;i<N;i++)
        for(int j=0;j<=9;j++)
            for(int k=0;k<P;k++)
                for(int x=0;x<=9;x++)
                    f[i][j][k]+=f[i-1][x][mod(k-j,P)];   
}

int dp(int n)
{
    if(n==0) return 1;

    vector<int> nums;
    while(n) nums.push_back(n%10),n/=10;

    int res=0;
    int last=0;

    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        for(int j=0;j<x;j++)
            res+=f[i+1][j][mod(-last,P)];

        last+=x;

        if(i==0 && last%P==0) res++;

    }


    return res;
}

int main()
{
    int l,r;
    while(cin>>l>>r>>P)
    {
        memset(f,0,sizeof f);
        init();
        cout<<dp(r)-dp(l-1)<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 1083. Windy数

欧拉AC
1个月前
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int N=12;

int f[N][10];

void init()
{
    for(int i=0;i<=9;i++) f[1][i]=1;

    for(int i=2;i<=N;i++)
        for(int j=0;j<=9;j++)
            for(int k=0;k<=9;k++)
                if(abs(j-k)>=2) f[i][j]+=f[i-1][k];
}

int get(int n)
{
    if(n==0) return 0;

    vector<int> nums;
    while(n) nums.push_back(n%10),n/=10;

    int res=0;
    int last=-2;


    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        if(x)
        {
            for(int j=i==nums.size()-1;j<x;j++)
                if(abs(j-last)>=2) res+=f[i+1][j];
        }

        if(abs(x-last)<2) break;
        last=x;

        if(i==0) res++;
    }

    for(int i=1;i<nums.size();i++) 
        for(int j=1;j<=9;j++)
            res+=f[i][j];

    return res;
}

int main()
{
    int l,r;
    cin>>l>>r;

    init();

    cout<<get(r)-get(l-1)<<endl;

    return 0;
}


活动打卡代码 AcWing 1082. 数字游戏

欧拉AC
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=15;

int f[N][N];


void init()
{
    for(int i=0;i<=9;i++) f[1][i]=1;

    for(int i=2;i<=N;i++)   
        for(int j=0;j<=9;j++)
            for(int k=j;k<=9;k++)
                f[i][j]+=f[i-1][k];

}


int get(int n)
{
    if(n==0) return 1;

    vector<int> nums;
    while(n) nums.push_back(n%10),n/=10;

    int res=0;
    int last=0;

    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        if(x<last) break;

        for(int j=last;j<x;j++)
            res+=f[i+1][j];

        last=x;

        if(i==0) res++;
    }

    return res;
}


int main()
{
    int l,r;

    init();

    while(cin>>l>>r)
    {
        cout<<get(r)-get(l-1)<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 734. 能量石

欧拉AC
1个月前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=10010;

int f[N];

struct Stone
{
    int s,e,l;
    bool operator< (const Stone &W)const
    {
        return s*W.l<W.s*l;
    }
}stone[N];

int main()
{
    int T,cnt=1;
    cin>>T;
    while(T--)
    {
        int n,m=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>stone[i].s>>stone[i].e>>stone[i].l;
            m+=stone[i].s;
        }

        sort(stone+1,stone+n+1);

        memset(f,-0x3f,sizeof f);
        f[0]=0;

        for(int i=1;i<=n;i++)
        {
            int s=stone[i].s,e=stone[i].e,l=stone[i].l;
            for(int j=m;j>=s;j--)
            {
                f[j]=max(f[j],f[j-s]+e-(j-s)*l);
            }
        }

        int res=0;
        for(int i=1;i<=m;i++) res=max(res,f[i]);
        printf("Case #%d: %d\n",cnt++,res);

    }

    return 0;
}



欧拉AC
1个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N=110;

int h[N],e[N],ne[N],idx;
int f[N][N];
int n,m;
int v[N],w[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int son=e[i];
        dfs(son);

        for(int j=m-v[u];j>=0;j--)
            for(int k=0;k<=j;k++)
                f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);
    }

    for(int i=m;i>=v[u];i--) f[u][i]=f[u][i-v[u]]+w[u];

    for(int i=0;i<v[u];i++) f[u][i]=0;

}

int main()
{
    memset(h,-1,sizeof h);

    cin>>n>>m;

    int root;
    for(int i=1;i<=n;i++)
    {
        int p;
        cin>>v[i]>>w[i]>>p;
        if(p==-1) root=i;
        else add(p,i);
    }

    dfs(root);

    cout<<f[root][m]<<endl;

    return 0;

}



活动打卡代码 AcWing 275. 传纸条

欧拉AC
1个月前
#include <iostream>

using namespace std;

const int N=55;

int n,m;
int w[N][N];
int f[N+N][N][N];

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)  
            cin>>w[i][j];

    for(int k=2;k<=n+m;k++)
        for(int i1=1;i1<=n;i1++)    
            for(int i2=1;i2<=n;i2++)
            {
                int j1=k-i1,j2=k-i2;

                if(i1!=i2 || k==n+m)
                {
                    if(j1>0 && j1<=m && j2>0 && j2<=m)
                    {
                        int t=w[i1][j1]+w[i2][j2];
                        int &x=f[k][i1][i2];

                        x=max(x,f[k-1][i1][i2]+t);
                        x=max(x,f[k-1][i1-1][i2]+t);
                        x=max(x,f[k-1][i1][i2-1]+t);
                        x=max(x,f[k-1][i1-1][i2-1]+t);
                    }
                }
            }

    cout<<f[n+m][n][n];

    return 0;
}