头像

Laleyendadelaeternid




离线:2019-11-18 00:44


最近来访(4)
用户头像
Tilbur
用户头像
Tkybk_dz
用户头像
朝霞
用户头像
不想罚座

活动打卡代码 AcWing 519. 跳石头

Laleyendadelaeternid
2019-11-13 13:29
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
const int N=50010;

int L,n,m;
int d[N];

bool check(int mid)
{
    int last=0,cnt=0;
    for(int i=1;i<=n;++i)
        if(d[i]-last<mid) cnt++;
        else last=d[i];
    return cnt<=m;
}

int main(void)
{
    scanf("%d%d%d",&L,&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",&d[i]);
    d[++n]=L;
    int l=1,r=1e9;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d\n",r);
    return 0;
}


活动打卡代码 AcWing 518. 斗地主

Laleyendadelaeternid
2019-11-12 23:45
#include<bits/stdc++.h>
using namespace std;
int T,n,card[16],ans;

inline int read()
{
    int x=0; char c=getchar();
    while(c>'9'||c<'0') c=getchar();
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x;
}

inline void init()
{
    memset(card,0,sizeof(card));
    ans=n;
    return ;
}

inline void dfs(int step,int point,int out) 
{
    if(step>=ans) return ; 
    if(out==n)  //出完所有的牌了 
    {
        ans=step;
        //cout<<step<<" "<<point<<" "<<out<<endl;
        return;
    }
    if(point==16) return;
    if(card[point]==0) dfs(step,point+1,out);
    if(card[14]&&card[15])      //炸弹 
    {
        card[14]--; card[15]--;
        dfs(step+1,point,out+2);
        card[14]++; card[15]++;
    }
    if(card[point]>=4)  
    {
        card[point]-=4;
        for(int i=1;i<=13;++i)  //四带二 
        {
            if(card[i])
            {
                card[i]--;
                for(int j=i;j<=15;++j)
                {
                    if(card[j])
                    {
                        card[j]--;
                        dfs(step+1,point,out+6);
                        card[j]++;
                    }
                }
                card[i]++;
            }
        }
        for(int i=1;i<=13;++i)
        {
            if(card[i]>=2)
            {
                card[i]-=2;
                for(int j=i;j<=13;++j)
                {
                    if(card[j]>=2)
                    {
                        card[j]-=2;
                        dfs(step+1,point,out+8);
                        card[j]+=2;
                    }
                }
                card[i]+=2;
            }
        }
        card[point]+=4;
    }
    if(card[point]>=3)
    {
        card[point]-=3;
        for(int i=point+1;i<=12;++i)    //三顺子 
        {
            if(card[i]<3) break;
            if(i-point+1>=2)
            {
                for(int j=point+1;j<=i;++j) card[j]-=3;
                dfs(step+1,point,out+(i-point+1)*3);
                for(int j=point+1;j<=i;++j) card[j]+=3;
            }
        }
        for(int i=1;i<=15;++i)
        {
            if(i==point) continue;
            if(card[i]>=1)              //三带一 
            {
                card[i]--;
                dfs(step+1,point,out+4);
                card[i]++;
            }
        }
        for(int i=1;i<=15;++i)
        {
            if(i==point) continue;
            if(card[i]>=2)              //三带二
            {
                card[i]-=2;
                dfs(step+1,point,out+5);
                card[i]+=2;
            }
        }
        dfs(step+1,point,out+3);        //三张牌 
        card[point]+=3;
    }
    if(card[point]>=2)
    {
        card[point]-=2;
        for(int i=point+1;i<=12;++i)    //双顺子 
        {
            if(card[i]<2) break;
            if(i-point+1>=3)
            {
                for(int j=point+1;j<=i;++j) card[j]-=2;
                dfs(step+1,point,out+(i-point+1)*2);
                for(int j=point+1;j<=i;++j) card[j]+=2;
            }
        }
        for(int i=1;i<=13;++i)  //对带四再带对
        {
            if(card[i]>=4)
            {
                card[i]-=4;
                for(int j=1;j<=13;++j)
                {
                    if(card[j]>=2&&j!=point)
                    {
                        card[j]-=2;
                        dfs(step+1,point,out+8);
                        card[j]+=2;
                    }
                }
                card[i]+=4;
            }
        }
        for(int i=1;i<=13;++i)  //二带三
        {
            if(card[i]>=3&&i!=point)
            {
                card[i]-=3;
                dfs(step+1,point,out+5);
                card[i]+=3;
            }
        }
        dfs(step+1,point,out+2);        //对子
        card[point]+=2;
    }
    if(card[point])
    {
        card[point]--;
        for(int i=point+1;i<=12;++i)    //单顺子 
        {
            if(!card[i]) break;
            if(i-point+1>=5)
            {
                for(int j=point+1;j<=i;++j) card[j]--;
                dfs(step+1,point,out+i-point+1);
                for(int j=point+1;j<=i;++j) card[j]++;
            }
        }
        for(int i=1;i<=13;++i)  //单带四再带单 
        {
            if(card[i]>=4)
            {
                card[i]-=4;
                for(int j=1;j<=15;++j)
                {
                    if(card[j])
                    {
                        card[j]--;
                        dfs(step+1,point,out+6);
                        card[j]++;
                    }
                }
                card[i]+=4;
            }
        }
        for(int i=1;i<=13;++i)  //一带三 
        {
            if(card[i]>=3&&i!=point)
            {
                card[i]-=3;
                dfs(step+1,point,out+4);
                card[i]+=3;
            }
        }
        dfs(step+1,point,out+1);        //单牌 
        card[point]++;
    }
    return ;
}

int main(void)
{
    //freopen("in.txt","r",stdin); 
    //freopen("out.txt","w",stdout);
    T=read(); n=read();
    while(T--)
    {
        init(); int a,b;
        for(int i=1;i<=n;++i)
        {
            a=read(); b=read();
            if(a==0){a=((b==1)?14:15);}
            else if(a==1) a=12;
            else if(a==2) a=13;
            else a-=2; card[a]++;
        }
        //for(int i=1;i<=15;++i) cout<<card[i]<<endl;
        dfs(0,1,0);
        printf("%d\n",ans);
    }
    return 0;
}


活动打卡代码 AcWing 517. 信息传递

Laleyendadelaeternid
2019-11-12 23:44
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 200010
using namespace std;
int fa[MAXN],deep[MAXN],n,ans=1e9;

inline int find(int x)
{
    if(fa[x]!=x)                       
    {
        int last=fa[x];               
        fa[x]=find(fa[x]);                 
        deep[x]+=deep[last];                 
    }
    return fa[x];
}

inline void check(int a,int b)
{
    int x=find(a),y=find(b); 
    if(x!=y) {fa[x]=y; deep[a]=deep[b]+1;}
    else ans=min(ans,deep[a]+deep[b]+1); 
    return;
}

int main(void)
{
    scanf("%d",&n); int x;
    for(int i=1;i<=n;++i) fa[i]=i; 
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&x);
        check(i,x); 
    }
    printf("%d\n",ans);
    return 0;
}


活动打卡代码 AcWing 516. 神奇的幻方

Laleyendadelaeternid
2019-11-12 10:24
#include<cstdio>
#include<iostream>
using namespace std;
const int N = 40;
int n,ans[N][N];

int main(void)
{
    scanf("%d",&n);
    ans[1][n/2+1]=1;
    int lx=1,ly=n/2+1;
    for(int i=2;i<=n*n;++i)
    {
        if(lx==1&&ly!=n) lx=n,ly=ly+1;
        else if(lx!=1&&ly==n) lx=lx-1,ly=1;
        else if(lx==1&&ly==n) lx=lx+1,ly=n;
        else
        {
            if(!ans[lx-1][ly+1]) lx=lx-1,ly=ly+1;
            else lx=lx+1,ly=ly;
        }
        ans[lx][ly]=i;
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
            printf("%d ",ans[i][j]);
        printf("\n");
    }
    return 0;
}


活动打卡代码 AcWing 515. 解方程

Laleyendadelaeternid
2019-11-12 09:23
#include<bits/stdc++.h>
#define MAXN 105
#define MAXM 1000010
using namespace std;
typedef long long ll;
const int mod=1000000009;
int n,m,A[MAXN],ans[MAXM],sum,cnt;
bool flag=1;

inline int read()
{
    int x=0,f=1; char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x*1ll*10+c-'0')%mod;
        c=getchar();
    }
    return x*f;
}

inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return ;
}

inline bool check(int x)
{
    int res=A[n];
    for(int i=n-1;i>=0;--i) 
        res=(res*1ll*x+A[i])%mod;
    return !res;
}

int main(void)
{
    //freopen("in.txt","r",stdin);
    n=read(); m=read();
    for(int i=0;i<=n;++i) A[i]=read();
    for(int i=1;i<=m;++i)
        if(check(i))
        { 
            sum++; ans[++cnt]=i;
        }
    write(sum); printf("\n");
    for(int i=1;i<=cnt;++i)
    {
        write(ans[i]);
        printf("\n");
    }
    return 0;
}


活动打卡代码 AcWing 514. 寻找道路

Laleyendadelaeternid
2019-11-12 09:11
#include<bits/stdc++.h>
#define rint register int
#define MAXN 100010
#define MAXM 200020
using namespace std;
int head[MAXN],dis[MAXN],cnt,start,endd,chead[MAXN],ccnt,n,m;
bool vis1[MAXN],vis2[MAXN],book[MAXN];
const int inf=1000000; 

struct Edge 
{
    int v,w,next; 
}edge[MAXM],cedge[MAXM];

struct NODE 
{
    int u,d;
    bool operator <(const NODE& rhs) const {
        return d>rhs.d;
    }
};

inline int read()
{
    register char c=getchar(); rint x=0; short f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}

inline void add(int u,int v) 
{
    edge[++cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
    return ;
}

inline void cadd(int u,int v) 
{
    cedge[++ccnt].v=v;
    cedge[ccnt].next=chead[u];
    chead[u]=ccnt;
    return ;
}

inline void dfs1(int x)
{
    vis1[x]=true;
    for(int i=chead[x];i;i=cedge[i].next)
    {
        int v=cedge[i].v;
        if(vis1[v]) continue;
        dfs1(v);
    }
    return ;
}

inline void dfs2(int x)
{
    vis2[x]=true;
    for(int i=head[x];i;i=edge[i].next)
    {
        int v=edge[i].v;
        if(!vis1[v]) book[x]=true;
        if(vis2[v]) continue;
        dfs2(v);
    }
    return ;
}

inline void Dijkstra() 
{
    fill(dis+1,dis+n+1,inf);
    dis[start]=0;
    priority_queue<NODE> Q;
    Q.push((NODE){start,0});
    while(!Q.empty()) 
    {
        NODE fr=Q.top(); Q.pop();
        int u=fr.u,d=fr.d;
        if(d!=dis[u]) continue;
        for(rint i=head[u];i;i=edge[i].next) 
        {
            int v=edge[i].v,w=1;
            if(book[v]) continue;
            if(dis[u]+w<dis[v]) 
            {
                dis[v]=dis[u]+w;
                Q.push((NODE){v,dis[v]});
            }
        }
    }
    return ;
}

int main(void)
{
    //freopen("in.txt","r",stdin);
    n=read(); m=read();
    int a,b;
    for(int i=1;i<=m;++i)
    {
        a=read(); b=read();
        add(a,b);   cadd(b,a);
    }
    start=read(); endd=read();
    dfs1(endd); dfs2(start);
    Dijkstra();
    if(dis[endd]==inf) printf("-1");
    else printf("%d",dis[endd]);
    return 0;
}



Laleyendadelaeternid
2019-11-12 09:09
#include<iostream>
#include<cstdio>
using namespace std;
int n,d,sum[180][180],ans,cnt;

int main(void)
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&d,&n); int x,y,z;
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        sum[x+21][y+21]=z;
    }
    for(int i=1;i<=169;++i)
      for(int j=1;j<=169;++j)
        sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];           
    for(int i=21;i<=149;++i)
        for(int j=21;j<=149;++j)
        {
            int res=sum[i+d][j+d]-sum[i-d-1][j+d]-sum[i+d][j-d-1]+sum[i-d-1][j-d-1];
            if(res>ans){ ans=res; cnt=1;}
            else if(res==ans) cnt++;
        }   
    printf("%d %d\n",cnt,ans);
    return 0;
}


活动打卡代码 AcWing 512. 飞扬的小鸟

Laleyendadelaeternid
2019-11-12 08:44
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define MAXN 10010
#define MAXM 2010
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,p,up[MAXN],down[MAXN],ans,f[MAXN][MAXM],low[MAXN],high[MAXN];
bool book[MAXN];    //标记位置i有没有管道 
//f[i][j]表示到达(i,j)的最小点击次数 

int main(void)
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&p); int x,y,z;
    for(int i=1;i<=n;++i) scanf("%d%d",&up[i],&down[i]);
    for(int i=1;i<=n;++i){low[i]=1; high[i]=m;}
    for(int i=1;i<=p;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        book[x]=1; 
        low[x]=y+1; high[x]=z-1;
    }
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=m;++i) f[0][i]=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=up[i]+1;j<=m+up[i];++j)   
            f[i][j]=min(f[i-1][j-up[i]]+1,f[i][j-up[i]]+1);
        for(int j=m+1;j<=m+up[i];++j)   //超过m不会死,而是不会接着上升。 
            f[i][m]=min(f[i][m],f[i][j]);
        for(int j=1;j<=m-down[i];++j)
            f[i][j]=min(f[i][j],f[i-1][j+down[i]]);
        for(int j=1;j<low[i];++j) f[i][j]=inf;   //不能通过(INF) 
        for(int j=high[i]+1;j<=m;++j) f[i][j]=inf;   //不能通过(INF)
    }
    ans=0x3f3f3f3f;
    for(int i=1;i<=m;++i) ans=min(ans,f[n][i]);
    if(ans<inf)
    {
        puts("1");
        printf("%d\n",ans);
    }
    else
    {
        int i,j;
        for(i=n;i>=1;--i) //从后向前遍历 
        {
            for(j=1;j<=m;++j) 
                if(f[i][j]<inf) break; //如果能到达 
            if(j<=m) break;
        }
        ans=0;
        for(int j=1;j<=i;++j) 
            if(book[j]) ans++;
        puts("0");
        printf("%d\n",ans);
    }
    return 0;
}


活动打卡代码 AcWing 511. 联合权值

Laleyendadelaeternid
2019-11-12 08:04
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 200010 
using namespace std;
const int mod = 10007;
int n,val[MAXN],ans1,ans2;
int head[MAXN],to[MAXN<<1],nxt[MAXN<<1],cnt;

inline void add(int u,int v)
{
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
    return ;    
}

int main(void)
{
    //freopen("in.txt","r",stdin);
    scanf("%d",&n); int x,y;
    for(int i=1;i<=n-1;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    for(int i=1;i<=n;++i) scanf("%d",&val[i]);
    for(int i=1;i<=n;++i)
    {
        int max1=0,max2=0;  //最大的两个权值
        int t1=0,t2=0;      //t1代表和的平方,t2代表平方和
        for(int j=head[i];j;j=nxt[j])
        {
            int v=to[j];
            if(val[v]>max1) max2=max1,max1=val[v];
            else if(val[v]>max2) max2=val[v];
            t1=(t1+val[v])%10007;
            t2=(t2+val[v]*val[v])%10007;
        }
        t1=t1*t1%10007;
        ans2=(ans2+t1+10007-t2)%10007;
        if(ans1<max1*max2) ans1=max1*max2;
    }
    printf("%d %d\n",ans1,ans2);
    return 0;
}



Laleyendadelaeternid
2019-11-12 07:32
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 210;
int n,na,nb,a[N],b[N],cnta,cntb;
int vs[5][5] = {{0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0}};

int main(void)
{
    scanf("%d%d%d",&n,&na,&nb);
    for(int i=0;i<na;++i) scanf("%d",&a[i]);
    for(int i=0;i<nb;++i) scanf("%d",&b[i]);
    for(int i=0;i<n;++i)
    {
        cnta+=vs[a[i%na]][b[i%nb]]; 
        cntb+=vs[b[i%nb]][a[i%na]];
    }
    printf("%d %d\n",cnta,cntb);
    return 0;
}