头像

ৡ心梦ﻬ




离线:1天前


活动打卡代码 AcWing 1322. 取石子游戏

ৡ心梦ﻬ
1个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1010;
ll n;
ll a[N];
ll l[N][N],r[N][N];
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(ll i=1;i<=n;i++)cin>>a[i]; 
        for(ll len=1;len<=n;len++)
        {
            for(ll i=1;i+len-1<=n;i++)
            {
                ll j=i+len-1;
                if(len==1)l[i][j]=r[i][j]=a[i];
                else 
                {
                    ll 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)cout<<"1"<<endl;
        else printf("%d\n", l[2][n] != a[1]);
    }
 } 
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 1321. 取石子

ৡ心梦ﻬ
1个月前
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
const ll N=55,M=50050;
ll f[N][M];
ll dp(ll a,ll b)
{
    ll &v=f[a][b];
    if(v!=-1)return v;
    // 简单情况
    if(!a)return v=b%2;
    // 一般情况
    // 上一次取完后 b中只有1堆 且只有1个石子 b=1+1-1=1 这堆并入a中
    if(b==1)return (a+1,0);
    // 有a 从a中取1个
    if(a&&!dp(a-1,b))return v=1;
    // 有b 从b中取1个 or 合并b中2个
    if(b&&!dp(a,b-1))return v=1;
    // 合并a中2个
    if(a>=2&&!dp(a-2,b+(b?3:2)))return v=1;
    // 合并a中1个b中1个
    if(a&&b&&!dp(a-1,b+1))return v=1;
    return v=0;
 } 
 int main()
 {
    memset(f,-1,sizeof(f));
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll a=0,b=0;
        for(ll i=0;i<n;i++)
        {
            ll x;
            cin>>x;
            if(x==1)a++;
            // b==0时 加1堆+加x石子=0 + 1+x-1=x
            // b!=0时 加1堆+加x石子=原来的+x+1
            else b += b ? x + 1 : x;
         }
         if (dp(a, b)) puts("YES");
        else puts("NO");
     }
 }
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 1319. 移棋子游戏

ৡ心梦ﻬ
1个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e4+10;
ll n,m,k;
ll h[N],e[N],ne[N],idx;
ll f[N];
void add(ll a,ll b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
ll sg(ll u)
{
    if(f[u]!=-1)return f[u];
    set<ll>S;
    for(ll i=h[u];~i;i=ne[i])
    {
        ll j=e[i];
        S.insert(sg(j));
    }
    for(ll i=0;;i++)
        if(S.count(i)==0)
        {
            f[u]=i;
            break;
        }
    return f[u];
}
int main()
{
    cin>>n>>m>>k;
    memset(h,-1,sizeof(h));
    for(ll i=0;i<m;i++)
    {
        ll a,b;
        cin>>a>>b;
        add(a,b);
    }
    memset(f,-1,sizeof(f));
    ll res=0;
    for(ll i=0;i<k;i++)
    {
        ll u;
        cin>>u;
        res^=sg(u);
    }
    if(res)cout<<"win"<<endl;
    else cout<<"lose"<<endl;
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

ৡ心梦ﻬ
1个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=14;
const double inf=1e20;
ll A,B,C,D;
double f[N][N][N][N][5][5];
double dp(ll a,ll b,ll c,ll d,ll x,ll y)
{
    double &v=f[a][b][c][d][x][y];
    if(v>=0)return v;
    ll as=a+(x==0)+(y==0);
    ll bs=b+(x==1)+(y==1);
    ll cs=c+(x==2)+(y==2);
    ll ds=d+(x==2)+(y==3);
    if(as>=A&&bs>=B&&cs>=C&&ds>=D)return 0;
    ll sum=a+b+c+d+(x!=4)+(y!=4);
    sum=54-sum;
    if(sum<=0)return 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(ll 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(ll 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("%.3f\n",t);
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

ৡ心梦ﻬ
1个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 100010, M = 200010;
ll n,m;
ll h[N],e[M],w[M],ne[M],idx;
int dout[N];
double f[N];  //f[i]存的为从i到n的期望 
void add(ll a,ll b,ll c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
 } 
double dp(ll u)
{
    if(f[u]>=0)return f[u];
    f[u]=0;
    for(ll i=h[u];~i;i=ne[i])
    {
        ll 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(ll i=0;i<m;i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        dout[a]++;
    }
    memset(f,-1,sizeof(f));
    printf("%.2lf\n", dp(1));
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 215. 破译密码

ৡ心梦ﻬ
1个月前
//这里填你的代码^^
#include<bits/stdc++.h>
#define LL ll
using namespace std;
typedef long long ll;
const ll N=50010;
ll primes[N],st[N],cnt;
ll mobius[N],sum[N];
void init(ll n)
{
    mobius[1]=1;
    for(ll i=2;i<=n;i++)
    {
        if(!st[i])
        {
            primes[cnt++]=i;
            mobius[i]=-1;       //一个 奇数个 
        }
        for(ll j=0;primes[j]<=n/i;j++)
        {
            ll t=primes[j]*i;
            st[t]=1;
            if(i%primes[j]==0)
            {
                mobius[t]=0;
                break;
            }
            mobius[t]=mobius[i]*-1;
        }
    }
    for(ll i=1;i<=n;i++)sum[i]=sum[i-1]+mobius[i];
}
int main()
{
    init(N-1);
    ll t;
    cin>>t;
    while(t--)
    {
        int a,b,d;
        scanf("%d%d%d", &a, &b, &d);
        a/=d,b/=d;
        int n=min(a,b);
        ll res=0;
        for(int l=1,r;l<=n;l=r+1)
        {
             r = min(n, min(a / (a / l), b / (b / l)));
            res += (sum[r] - sum[l - 1]) * (LL)(a / l) * (b / l);
        }
        printf("%lld\n", res);
    }
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 214. Devu和鲜花

ৡ心梦ﻬ
1个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=20,mod=1e9+7;
ll A[N];
ll down=1;
ll kum(ll a,ll k,ll mod)
{
    ll res=1;
    a%=mod;
    while(k)
    {
        if(k&1)res=res*a%mod;
        k>>=1;
        a=a*a%mod;
    }
    return res;
}
ll C(ll a,ll b)
{
    if(a<b)return 0;
    ll up=1;
    for(ll i=a;i>a-b;i--)up=i%mod*up%mod;
    return up*down%mod;
}
int main()
{
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<n;i++)cin>>A[i];
    for(ll j=1;j<=n-1;j++)down=j*down%mod;
    down=kum(down,mod-2,mod);
    ll res=0;
    for(ll i=0;i<1<<n;i++)
    {
        ll a=n+m-1,b=n-1;
        ll sign=1;
        for(ll j=0;j<n;j++)
            if(i>>j&1)
            {
                sign*=-1;
                a-=A[j]+1;
            }
        res=(res+C(a,b)*sign)%mod;
    } 
    cout<<(res+mod)%mod<<endl;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 208. 开关问题

ৡ心梦ﻬ
1个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=35;
ll n;
ll a[N][N];
ll gauss()
{
    ll r,c;
    for(r=1,c=1;c<=n;c++)
    {
        //找主元; 
        ll t=r;
        for(ll i=r+1;i<=n;i++)
            if(a[i][c])
                t=i;
        if(!a[t][c])continue;
        //交换;
        for(ll i=c;i<=n+1;i++)swap(a[t][i],a[r][i]);
        //消;
        for(ll i=r+1;i<=n;i++)
            for(ll j=n+1;j>=c;j--)
                a[i][j]^=a[i][c]&a[r][j];
        r++; 
    }
    ll res=1;
    if(r<n+1)
    {
        for(ll i=r;i<=n;i++)
        {
            if(a[i][n+1])return -1;
            res*=2;
        }
    }
    return res;
}
int main()
{
    ll t;
    cin>>t;
    while (t--)
    {
        memset(a,0,sizeof(a));
        cin>>n;
        for(ll i=1;i<=n;i++)cin>>a[i][n+1];
        for(ll i=1;i<=n;i++)
        {
            ll t;
            cin>>t;
            a[i][n+1]^=t;
            a[i][i]=1;
        }

        int x, y;
        while (scanf("%d%d", &x, &y), x || y) a[y][x] = 1;

        int t = gauss();
        if (t == -1) puts("Oh,it's impossible~!!");
        else printf("%d\n", t);
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



ৡ心梦ﻬ
1个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=15;
ll n;
double a[N][N],b[N][N];
void gauss()
{
    //转化成上三角矩阵
    for(ll r=1,c=1;c<=n;c++,r++)
    {
        //找主元
        ll t=r;
        for(ll i=r+1;i<=n;i++)
            if(fabs(b[i][c])>fabs(b[t][c])) 
                t=i;
        //交换
        for(ll i=c;i<=n+1;i++)swap(b[t][i],b[r][i]);
        //归一化
        for(ll i=n+1;i>=c;i--)b[r][i]/=b[r][c];
        //消
        for(ll i=r+1;i<=n;i++)
            for(ll j=n+1;j>=c;j--)
                b[i][j]-=b[i][c]*b[r][j];
     } 
     //转化成对角矩阵
     for(ll i=n;i>1;i--)
        for(ll j=i-1;j;j--)
         {
            b[j][n+1]-=b[i][n+1]*b[j][i];
            b[j][i]=0;
          } 
}
int main()
{
    cin>>n;
    for(ll i=0;i<n+1;i++)
        for(ll j=1;j<=n;j++)
            cin>>a[i][j];
    for(ll i=1;i<=n;i++)
        for(ll j=1;j<=n;j++)
        {
            b[i][j]+=2*(a[i][j]-a[0][j]);
            b[i][n+1]+=a[i][j]*a[i][j]-a[0][j]*a[0][j];
        }
    gauss();
    for (int i = 1; i <= n; i ++ ) printf("%.3lf ", b[i][n + 1]);
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 1316. 有趣的数列

ৡ心梦ﻬ
1个月前
//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N= 2000010;
ll n,p;
ll primes[N],st[N],cnt;
void init(ll n)
{
    for(ll i=2;i<=n;i++)
    {
        if(!st[i])primes[cnt++]=i;
        for(ll j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=1;
            if(i%primes[j]==0)break;
        }
    }
}
ll kum(ll a,ll k)
{
    a%=p;
    ll res=1;
    while(k)
    {
        if(k&1)res=res*a%p;
        k>>=1;
        a=a*a%p;
    }
    return res;
}
ll get(ll n,ll p)
{
    ll s=0;
    while(n)s+=n/p,n/=p;
    return s;
}
ll C(ll a,ll b)
{
    ll res=1;
    for(ll i=0;i<cnt;i++)
    {
        ll prime=primes[i];
        ll s=get(a,prime)-get(b,prime)-get(a-b,prime);
        res=res*kum(prime,s)%p;
    }
    return res;
}
int main()
{
    cin>>n>>p;
    init(n*2);
    cout<<(C(n*2,n)-C(n*2,n-1)+p)%p<<endl;

}

//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~