头像

不高兴的兽奶

$ \color{RoyalBlue}{Always\ continue;\ Never\ break;}$




离线:4小时前


最近来访(1358)
用户头像
StarLi9ht
用户头像
greg666
用户头像
lpq1234
用户头像
易思人
用户头像
小红花
用户头像
德布罗意の猫
用户头像
李_04
用户头像
Chaleur
用户头像
yxc的小迷妹
用户头像
mmmmm
用户头像
未央刷题号
用户头像
いちじょうはるひこ
用户头像
别虐了
用户头像
AKStream
用户头像
Acwer
用户头像
唐の月
用户头像
空-白
用户头像
Kitebin
用户头像
violet_garden
用户头像
SmiLeeeee

新鲜事 原文

江爷爷要开心啊!



$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 12, M = 1 << 12, INF = 0x3f3f3f3f;

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

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

    memset(d,0x3f,sizeof d);
    for(int i=0;i<n;i++) d[i][i]=0;

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        a--,b--;
        d[a][b]=d[b][a]=min(d[a][b],c);
    }

    for(int i=1;i<1<<n;i++)
        for(int j=0;j<n;j++)
            if(i>>j&1)
                for(int k=0;k<n;k++)
                    if(d[j][k]!=INF)
                        g[i]|=1<<k;

    memset(f,0x3f,sizeof f);
    for(int i=0;i<n;i++) f[1<<i][0]=0;

    for(int i=1;i<1<<n;i++)
        for(int j=i-1;j;j=(j-1)&i)
            if((g[j]&i)==i)
            {
                int remain=i^j;
                int cost=0;
                for(int k=0;k<n;k++)
                    if(remain>>k&1)
                    {
                        int t=INF;
                        for(int u=0;u<n;u++)
                            if(j>>u&1)
                                t=min(t,d[k][u]);
                        cost+=t;
                    }

                for(int k=1;k<n;k++) f[i][k]=min(f[i][k],f[j][k-1]+cost*k);
            }

    int res=INF;
    for(int i=0;i<n;i++) res=min(res,f[(1<<n)-1][i]);

    cout<<res<<endl;

    return 0;
}



$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

完整代码

#include<bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<double,double> PDD;

const int N = 18, M = 1 << 18;
const double eps=1e-8;

int n,m;
PDD q[N];
int path[N][N];
int f[M];

int cmp(double x,double y)
{
    if(fabs(x-y)<eps) return 0;
    if(x<y) return -1;
    return 1;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;

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

        memset(path,0,sizeof path);

        for(int i=0;i<n;i++)
        {
            path[i][i]=1<<i;
            for(int j=0;j<n;j++)
            {
                double x1=q[i].x,y1=q[i].y;
                double x2=q[j].x,y2=q[j].y;
                if(!cmp(x1,x2)) continue;
                double a=(y1/x1-y2/x2)/(x1-x2);
                double b=y1/x1-a*x1;

                if(cmp(a,0)>=0) continue;
                int state=0;
                for(int k=0;k<n;k++)
                {
                    double x=q[k].x,y=q[k].y;
                    if(!cmp(a*x*x+b*x,y)) state+=1<<k;
                }
                path[i][j]=state;
            }
        }

        memset(f,0x3f,sizeof f);
        f[0]=0;
        for(int i=0;i+1<1<<n;i++)
        {
            int x=0;
            for(int j=0;j<n;j++)
                if(!(i>>j&1))
                {
                    x=j;
                    break;
                }

            for(int j=0;j<n;j++) f[i|path[x][j]]=min(f[i|path[x][j]],f[i]+1);
        }

        cout<<f[(1<<n)-1]<<endl;
    }

    return 0;
}



$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n;
int a[N];
int l[N][N],r[N][N];

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];

        for(int len=1;len<=n;len++)
            for(int i=1;i+len-1<=n;i++)
            {
                int j=i+len-1;
                if(len==1) l[i][j]=r[i][j]=a[i];
                else
                {
                    int L=l[i][j-1],R=r[i][j-1],X=a[j];
                    if(R==X) l[i][j]=0;
                    else if(X<L&&X<R||X>L&&X>R) l[i][j]=X;
                    else if(L>R) l[i][j]=X-1;
                    else l[i][j]=X+1;

                    L=l[i+1][j],R=r[i+1][j],X=a[i];
                    if(L==X) r[i][j]=0;
                    else if(X<L&&X<R||X>L&&X>R) r[i][j]=X;
                    else if(R>L) r[i][j]=X-1;
                    else r[i][j]=X+1;
                }
            }

        if(n==1) puts("1");
        else cout<<(l[2][n]!=a[1])<<endl;
    }

    return 0;
}



$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 20, P = 1e9 + 7;

struct F
{
    int s0,s1,s2;
}f[N][10][7][7];

int power7[N],power9[N];

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

void init()
{
    for(int i=0;i<=9;i++)
    {
        if(i==7) continue;
        auto &v=f[1][i][i%7][i%7];
        v.s0++,v.s1+=i,v.s2+=i*i;
    }

    LL power=10;
    for(int i=2;i<N;i++,power*=10)
        for(int j=0;j<=9;j++)
        {
            if(j==7) continue;
            for(int a=0;a<7;a++)
                for(int b=0;b<7;b++)
                    for(int k=0;k<=9;k++)
                    {
                        if(k==7) continue;
                        auto &v1=f[i][j][a][b],&v2=f[i-1][k][mod(a-j*power,7)][mod(b-j,7)];
                        v1.s0=mod(v1.s0+v2.s0,P);
                        v1.s1=mod(v1.s1+v2.s1+j*(power%P)%P*v2.s0,P);
                        v1.s2=mod(v1.s2+j*j*(power%P)%P*(power%P)%P*v2.s0+v2.s2+2*j*power%P*v2.s1,P);
                    }
        }

    power7[0]=power9[0]=1;
    for(int i=1;i<N;i++) 
    {
        power7[i]=power7[i-1]*10%7;
        power9[i]=power9[i-1]*10ll%P;
    }
}

F get(int i,int j,int a,int b)
{
    int s0=0,s1=0,s2=0;
    for(int x=0;x<7;x++)
        for(int y=0;y<7;y++)
            if(x!=a&&y!=b)
            {
                auto v=f[i][j][x][y];
                s0=(s0+v.s0)%P;
                s1=(s1+v.s1)%P;
                s2=(s2+v.s2)%P;
            }

    return {s0,s1,s2};
}

int dp(LL n)
{
    if(!n) return 0;

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

    int res=0;
    LL last_a=0,last_b=0;
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        for(int j=0;j<x;j++)
        {
            if(j==7) continue;
            int a=mod(-last_a*power7[i+1],7);
            int b=mod(-last_b,7);
            auto v=get(i+1,j,a,b);
            res=mod(res+(last_a%P)*(last_a%P)%P*power9[i+1]%P*power9[i+1]%P*v.s0%P+v.s2+2*last_a%P*power9[i+1]%P*v.s1,P);
        }

        if(x==7) break;
        last_a=last_a*10+x;
        last_b+=x;

        if(!i&&last_a%7&&last_b%7) res=(res+backup_n*backup_n)%P;
    }

    return res;
}

int main()
{
    init();

    int T;
    cin>>T;
    while(T--)
    {
        LL l,r;
        cin>>l>>r;
        cout<<mod(dp(r)-dp(l-1),P)<<endl;
    }

    return 0;
}



$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n,m;
int tr[N][4],dar[N],idx;
int q[N],ne[N];
char str[N];
int f[N][N];

int get(char c)
{
    if(c=='A') return 0;
    else if(c=='G') return 1;
    else if(c=='C') return 2;
    else return 3;
}

void insert()
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int t=get(str[i]);
        if(!tr[p][t]) tr[p][t]=++idx;
        p=tr[p][t];
    }
    dar[p]=1;
}

void build()
{
    int hh=0,tt=-1;
    for(int i=0;i<4;i++)
        if(tr[0][i])
            q[++tt]=tr[0][i];

    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=0;i<4;i++)
        {
            int p=tr[t][i];
            if(!p) tr[t][i]=tr[ne[t]][i];
            else 
            {
                ne[p]=tr[ne[t]][i];
                q[++tt]=p;
                dar[p]|=dar[ne[p]];
            }
        }
    }
}

int main()
{
    int T=1;
    while(cin>>n,n)
    {
        //多组数据初始化
        memset(ne,0,sizeof ne);
        memset(tr,0,sizeof tr);
        memset(dar,0,sizeof dar);
        idx=0;

        for(int i=0;i<n;i++)
        {
            cin>>str;
            insert(); //插入字符串
        }

        build(); //AC自动机

        cin>>str+1;
        m=strlen(str+1);

        memset(f,0x3f,sizeof f);
        f[0][0]=0;
        for(int i=0;i<m;i++) //枚举主串
            for(int j=0;j<=idx;j++) //枚举AC自动机
                for(int k=0;k<4;k++) //枚举字符
                {
                    int t=get(str[i+1])!=k;
                    int p=tr[j][k];
                    if(!dar[p]) f[i+1][p]=min(f[i+1][p],f[i][j]+t);
                }

        int res=0x3f3f3f3f;
        for(int i=0;i<=idx;i++) res=min(res,f[m][i]);

        if(res==0x3f3f3f3f) res=-1;
        printf("Case %d: %d\n",T++,res);
    }

    return 0;
}



$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路:

$依次填入1,2,3,…,2n,需满足任何时候奇数项个数\ge 偶数项个数,则\ res=C_{2n}^{n}-C_{2n}^{n-1}$

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2000010;

int n,p;
int primes[N],cnt;
bool st[N];

void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int get(int n,int p)
{
    int res=0;
    while(n) res+=n/p,n/=p;
    return res;
}

int C(int a,int b)
{
    int res=1;
    for(int i=0;i<cnt;i++)
    {
        int prime=primes[i];
        int s=get(a,prime)-get(a-b,prime)-get(b,prime);
        while(s--) res=(LL)res*prime%p;
    }
    return res;
}

int main()
{
    init(N-1);

    cin>>n>>p;

    cout<<(C(2*n,n)-C(2*n,n-1)+p)%p<<endl;

    return 0;
}



$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路:

$点\ (n,m)\ 关于直线\ y=x+1\ 对称的点是\ (m-1,n+1),答案=C_{n+m}^{n}-C_{n+m}^{n+1}$

$最后用高精度求解\ C_{n+m}^{n}-C_{n+m}^{n+1}$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 10010;

int n,m;
int primes[N],cnt;
bool st[N];
int a[N],b[N];

//线性筛质数
void init(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

//返回 x! 中质因子 p 的个数
int get(int x,int p)
{
    int res=0;
    while(x) 
    {
        res+=x/p;
        x/=p;
    }
    return res;
}

//高精度乘法
void mul(int r[],int &len,int p)
{
    int t=0;
    for(int i=0;i<len;i++)
    {
        t+=r[i]*p;
        r[i]=t%10;
        t/=10;
    }
    while(t)
    {
        r[len++]=t%10;
        t/=10;
    }
}

int C(int a,int b,int r[])
{
    int len=1;
    r[0]=1;
    for(int i=0;i<cnt;i++)
    {
        int p=primes[i];
        int s=get(a,p)-get(a-b,p)-get(b,p);
        while(s--) mul(r,len,p);
    }
    return len;
}

//高精度减法
void sub(int a[],int al,int b[],int bl)
{
    for(int i=0;i<al;i++)
    {
        a[i]-=b[i];
        if(a[i]<0) 
        {
            a[i]+=10;
            a[i+1]--;
        }
    }
}

int main()
{
    init(N-1);

    cin>>n>>m;

    int al=C(n+m,n,a);
    int bl=C(n+m,n+1,b);

    sub(a,al,b,bl);

    int k=al-1;
    while(!a[k]) k--;
    while(k>=0) cout<<a[k--];

    return 0;
}



$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路:

$L\le a_1\le a_2\le … \le a_k\le R$

$差分映射:x_1+x_2+…+x_k\le R-L,其中\ x_i\ge 0$

$令\ y_i=x_i+1,则\ y_1+y_2+…+y_k\le R-L+k,其中\ y_i>0$

$隔板法(最后一个板子后面的元素不要选):C_{R-L+k}^{k}$

$\begin{aligned}\sum\limits_{k=1}^NC_{R-L+k}^{k}& = \sum\limits_{k=1}^NC_{R-L+k}^{R-L} \\ & = C_{R-L+1}^{R-L}+C_{R-L+2}^{R-L}+…+C_{R-L+N}^{R-L}\\&=C_{R-L+1}^{R-L+1}+C_{R-L+1}^{R-L}+C_{R-L+2}^{R-L}+…+C_{R-L+N}^{R-L}-1\\&=C_{R-L+N+1}^{R-L+1}-1\end{aligned}$

$最后运用\ Lucas\ 定理求解\ C_{R-L+N+1}^{R-L+1}-1$

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int p = 1e6 + 3;

int qmi(int a,int b,int p)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(LL)res*a%p;
        a=(LL)a*a%p;
        b>>=1;
    }
    return res;
}

int C(int a,int b)
{
    if(a<b) return 0;

    int up=1,down=1;
    for(int i=a,j=1;j<=b;i--,j++)
    {
        up=(LL)up*i%p;
        down=(LL)down*j%p;
    }

    return (LL)up*qmi(down,p-2,p)%p;
}

int Lucas(int a,int b)
{
    if(a<p&&b<p) return C(a,b);
    return (LL)Lucas(a/p,b/p)*C(a%p,b%p)%p;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,l,r;
        cin>>n>>l>>r;
        cout<<(Lucas(r-l+n+1,r-l+1)+p-1)%p<<endl;
    }

    return 0;
}



$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路:

1. 首先 n ++,m ++,转换为格点数
2. 总方案:C(n * m, 3)
3. 横线:n * C(m, 3)
4. 竖线:m * C(n, 3)
5. 斜线:(gcd(i, j) - 1) * (n - i)(m - j) (i, j) = (纵坐标之差,横坐标之差)
6. 合法方案 = C(n * m, 3) - n * C(m, 3) - m * C(n, 3) - (gcd(i, j) - 1) * (n - i)(m - j)

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL C(int n)
{
    return (LL)n*(n-1)*(n-2)/6;
}

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

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

    LL res=C(n*m)-(LL)n*C(m)-(LL)m*C(n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            res-=2*(gcd(i,j)-1)*(n-i)*(m-j);

    cout<<res<<endl;

    return 0;
}