头像

wyc1996

哈尔滨工业大学




离线:7小时前


活动打卡代码 AcWing 1432. 棋盘挑战

wyc1996
7小时前
#include<iostream>
#include<cstring>
#include<vector>

using namespace std;
const int N=15,M=2*N;
int col[N],dg[N*2],udg[N*2];
char g[N][N];
int n;
int ans;

void dfs(int u)
{
    if(u==n){
        ans++;
        if(ans<=3){
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    if(g[i][j]=='Q')
                        printf("%d ",j+1);
            puts("");
        }
    }
    for(int i=0;i<n;i++){
        if(!col[i] && !dg[u+i] && !udg[n-u+i]){
            col[i]=dg[u+i]=udg[n-u+i]=true;
            g[u][i]='Q';
            dfs(u+1);
            g[u][i]='*';
            col[i]=dg[u+i]=udg[n-u+i]=false;
        }
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            g[i][j]='*';

    dfs(0);        
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 218. 扑克牌

wyc1996
8小时前
#include<iostream>
#include<cstring>

using namespace std;
const int N=14;
const double INF=1e20;
double f[N][N][N][N][5][5];
int A,B,C,D;

double dp(int a,int b,int c,int d,int x,int y)
{
    double &v=f[a][b][c][d][x][y];
    if(v>=0)return v;
    int as=a+(x==0)+(y==0);
    int bs=b+(x==1)+(y==1);
    int cs=c+(x==2)+(y==2);
    int ds=d+(x==3)+(y==3);
    if(as>=A && bs>=B && cs>=C && ds>=D)return v=0;
    int sum=a+b+c+d+(x!=4)+(y!=4);
    sum=54-sum;
    if(sum<=0)return v=INF;

    v=1;
    if(a<13)v+=(13.0-a)/sum*dp(a+1,b,c,d,x,y);
    if(b<13)v+=(13.0-b)/sum*dp(a,b+1,c,d,x,y);
    if(c<13)v+=(13.0-c)/sum*dp(a,b,c+1,d,x,y);
    if(d<13)v+=(13.0-d)/sum*dp(a,b,c,d+1,x,y);
    if(x==4){
        double t=INF;
        for(int i=0;i<4;i++)
            t=min(t,1.0/sum*dp(a,b,c,d,i,y));
        v+=t;
    }
    if(y==4){
        double t=INF;
        for(int i=0;i<4;i++)
            t=min(t,1.0/sum*dp(a,b,c,d,x,i));
        v+=t;
    }
    return v;
}

int main()
{
    cin>>A>>B>>C>>D;
    memset(f,-1,sizeof f);
    double t=dp(0,0,0,0,4,4);
    if(t>INF/2)t=-1;
    printf("%.3lf\n",t);
    return 0;
}


活动打卡代码 AcWing 217. 绿豆蛙的归宿

wyc1996
12小时前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=100010,M=200010;
int h[N],e[M],ne[M],w[M],idx;
double f[N];
int dout[N];
int n,m;

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

double dp(int u)
{
    if(f[u]>=0)return f[u];
    f[u]=0;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        f[u]+=(w[i]+dp(j))/dout[u];
    }
    return f[u];
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        dout[a]++;
    }
    memset(f,-1,sizeof f);
    printf("%.2lf\n",dp(1));
    return 0;
}


活动打卡代码 AcWing 1305. GT考试

wyc1996
14小时前
#include<iostream>
#include<cstring>

using namespace std;
const int N=25;
int n,m,mod;
char str[N];
int ne[N];
int a[N][N];

void mul(int c[][N],int a[][N],int b[][N])
{
    static int t[N][N];
    memset(t,0,sizeof t);

    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
            for(int k=0;k<m;k++)
                t[i][j]=(t[i][j]+a[i][k]*b[k][j])%mod;
    memcpy(c,t,sizeof t);
}

int qmi(int k)
{
    int f0[N][N]={1};
    while(k){
        if(k&1)mul(f0,f0,a);
        mul(a,a,a);
        k>>=1;
    }
    int res=0;
    for(int i=0;i<m;i++)res=(res+f0[0][i])%mod;
    return res;
}

int main()
{
    cin>>n>>m>>mod;
    cin>>str+1;

    for(int i=2,j=0;i<=m;i++){
        while(j && str[j+1]!=str[i])j=ne[j];
        if(str[j+1]==str[i])j++;
        ne[i]=j;
    }

    for(int j=0;j<m;j++){
        for(int c='0';c<='9';c++){
            int k=j;
            while(k && str[k+1]!=c)k=ne[k];
            if(str[k+1]==c)k++;
            if(k<m)a[j][k]++;
        }    
    }
    cout<<qmi(n)<<endl;
    return 0;
}



wyc1996
21小时前
#include<iostream>
#include<cstring>

using namespace std;
typedef long long LL;
const int N=4;
int n,m;

void mul(int c[],int a[],int b[][N])
{
    int temp[N]={0};
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            temp[i]=(temp[i]+(LL)a[j]*b[j][i])%m;
    memcpy(c,temp,sizeof temp);
}

void mul(int c[][N],int a[][N],int b[][N])
{
    int temp[N][N]={0};
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
                temp[i][j]=(temp[i][j]+(LL)a[i][k]*b[k][j])%m;
    memcpy(c,temp,sizeof temp);
}

int main()
{
    cin>>n>>m;
    int f1[N]={1,1,1,0};
    int a[N][N]={
        {0,1,0,0},
        {1,1,1,0},
        {0,0,1,1},
        {0,0,0,1}
    };
    int k=n-1;
    while(k){
        if(k&1)mul(f1,f1,a);
        mul(a,a,a);
        k>>=1;
    }
    cout<<(((LL)n*f1[2]-f1[3])%m+m)%m<<endl;
    return 0;
}



wyc1996
21小时前
#include<iostream>
#include<cstring>

using namespace std;
typedef long long LL;
const int N=3;
int n,m;

void mul(int c[],int a[],int b[][N])
{
    int temp[N]={0};
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            temp[i]=(temp[i]+(LL)a[j]*b[j][i])%m;
    memcpy(c,temp,sizeof temp);
}

void mul(int c[][N],int a[][N],int b[][N])
{
    int temp[N][N]={0};
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
                temp[i][j]=(temp[i][j]+(LL)a[i][k]*b[k][j])%m;
    memcpy(c,temp,sizeof temp);
}

int main()
{
    cin>>n>>m;
    int f1[N]={1,1,1};
    int a[N][N]={
        {0,1,0},
        {1,1,1},
        {0,0,1}
    };
    n--;
    while(n){
        if(n&1)mul(f1,f1,a);
        mul(a,a,a);
        n>>=1;
    }
    cout<<f1[2]<<endl;
    return 0;
}


活动打卡代码 AcWing 754. 平方矩阵 II

wyc1996
22小时前
#include<iostream>

using namespace std;
const int N=110;
int g[N][N];

int main()
{
    int n;
    while(cin>>n,n){
        for(int i=0;i<n;i++)
            for(int j=i;j<n;j++){
                if(j==i)g[i][j]=1;
                else g[i][j]=g[j][i]=g[i][j-1]+1;
            }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                printf("%d ",g[i][j]);
            puts("");
        }
        puts("");
    }
    return 0;
}


活动打卡代码 AcWing 1341. 十三号星期五

wyc1996
1天前
#include<iostream>

using namespace std;
int s[12]={31,28,31,30,31,30,31,31,30,31,30,31};
int ans[7];

bool check(int year)
{
    return (year%4==0 && year%100 || year%400==0);    
}

int main()
{
    int n;
    cin>>n;
    int t=0;
    for(int i=1900;i<1900+n;i++){
        for(int j=1;j<=12;j++){
            int x=t+13;
            ans[x%7]++;
            t+=s[j-1];
            if(j==2 && check(i))t+=1;
        }
    }
    for(int i=6,j=0;j<7;i++,j++)printf("%d ",ans[i%7]);
    return 0;
}


活动打卡代码 AcWing 1298. 曹冲养猪

wyc1996
1天前
#include<cstring>
#include<iostream>

using namespace std;
typedef long long LL;
const int N=10;
int n;
int A[N],B[N];

void exgcd(LL a,LL b,LL& x,LL& y)
{
    if(!b)x=1,y=0;
    else {
        exgcd(b,a%b,y,x);
        y-=a/b*x;
    }
}

int main()
{
    scanf("%d",&n);
    LL M=1;
    for(int i=0;i<n;i++){
        scanf("%d%d",&A[i],&B[i]);
        M*=A[i];
    }
    LL res=0;
    for(int i=0;i<n;i++){
        LL Mi=M/A[i];
        LL ti,x;
        exgcd(Mi,A[i],ti,x);
        res+=B[i]*Mi*ti;
    }
    cout<<(res%M+M)%M<<endl;
    return 0;
}


活动打卡代码 AcWing 202. 最幸运的数字

wyc1996
1天前
#include<iostream>
#include<cstring>

using namespace std;
typedef long long LL;

LL qmul(LL a,LL k,LL b)
{
    LL res=0;
    while(k){
        if(k&1)res=(res+a)%b;
        a=(a+a)%b;
        k>>=1;
    }
    return res;
}

LL qmi(LL a,LL k,LL b)
{
    LL res=1;
    while(k){
        if(k&1)res=qmul(res,a,b);
        a=qmul(a,a,b);
        k>>=1;
    }
    return res;
}

LL get_phi(LL c)
{
    LL res=c;
    for(LL i=2;i<=c/i;i++)
        if(c%i==0){
            while(c%i==0)c/=i;
            res=res/i*(i-1);
        }
    if(c>1)res=res/c*(c-1);
    return res;
}

int main()
{
    int T=1;
    LL L;
    while(cin>>L,L){
        int d=1;
        while(L%(d*2)==0 && d*2<=8)d*=2;
        LL c=9*L/d;
        LL phi=get_phi(c);
        LL res=1e18;
        if(c%2==0 || c%5==0)res=0;
        else {
            for(LL d=1;d*d<=phi;d++)
                if(phi%d==0){
                    if(qmi(10,d,c)==1)res=min(res,d);
                    if(qmi(10,phi/d,c)==1)res=min(res,phi/d);
                }
        }
        printf("Case %d: %d\n",T++,res);
    }
    return 0;
}