SOL

SOL

关注
发信
关注(28)粉丝(399)

NCPC 2016：简单题解

A .Artwork

pro：给定N*M的白色格子，然后Q次黑棒，输出每次加黑棒后白色连通块的数量。(N,M<1e3, Q<1e4)

sol：倒着离线做，并查集即可。

（在线做法：https://www.cnblogs.com/asdfsag/p/10485607.html

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn = 1e6 + ;

int a[][], fa[maxn], ID[][];

struct node

{

    int x1, y1, x2, y2;

    node(){}

    node(int x1, int y1, int x2, int y2):x1(x1), y1(y1), x2(x2), y2(y2){}

}c[maxn];

int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}

int dir[][] = {,,,,-,,,-};

stack<int>s;

int main()

{

    int n, m, q, tot = , x1, y1, x2, y2;

    scanf("%d%d%d", &n, &m, &q);

    for(int i = ; i <= n; i++)for(int j = ; j <= m; j++){ID[i][j] = ++tot; fa[tot] = tot;}

    for(int i = ; i <= q; i++)

    {

        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

        c[i] = node(x1, y1, x2, y2);

        for(int x = x1; x <= x2; x++)for(int y = y1; y <= y2; y++)a[x][y]++;

    }

    int white = , cnt = ;

    for(int i = ; i <= n; i++)for(int j = ; j <= m; j++)if(!a[i][j])

    {

        white++;

        for(int k = ; k < ; k++)

        {

            int x = i + dir[k][], y = j + dir[k][];

            if(x >=  && x <= n && y >=  && y <= m && !a[x][y])

            {

                int u = ID[i][j], v = ID[x][y];

                u = Find(u);v = Find(v);

                if(u != v)fa[u] = v, cnt++;

            }

        }

    }

    s.push(white - cnt);

    for(int i = q; i >= ; i--)

    {

        for(int x = c[i].x1; x <= c[i].x2; x++)

            for(int y = c[i].y1; y <= c[i].y2; y++)

        {

            a[x][y]--;

            if(!a[x][y])

            {

                white++;

                for(int k = ; k < ; k++)

                {

                    int xx = x + dir[k][], yy = y + dir[k][];

                    if(xx >=  && xx <= n && yy >=  && yy <= m && !a[xx][yy])

                    {

                        int u = ID[x][y], v = ID[xx][yy];

                        u = Find(u);v = Find(v);

                        if(u != v)fa[u] = v, cnt++;

                    }

                }

            }

        }

        s.push(white - cnt);

    }

    while(!s.empty()){cout<<s.top()<<endl;s.pop();}

    return ;

}

C .Card Hand Sorting

pro：给定N张扑克牌，保证来自一副牌，有四种花色。现在让你重排，同种花色放一起，内部递增或者递减。 重排的方式是抽出一张牌，插入到某位置。

sol：四种花色，枚举花色的排列，再枚举每种花色内是递增还是递减。  对于每种方案，ans=N-LIS。

（写个结构体还是蛮方便的。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

map<char, int>level_num, level_color;

struct node

{

    char num, color;

    node(){}

    node(char num, char color):num(num), color(color){}

    bool operator <(const node& now)const

    {

        if(level_color[color] == level_color[now.color])//花色相同

        {

            //奇数递增，偶数递减

            if(level_color[color] & )return level_num[num] < level_num[now.num];

            else return level_num[num] > level_num[now.num];

        }

        return level_color[color] < level_color[now.color];

    }

    bool operator == (const node& now)const{return num == now.num && color == now.color;}

}a[], b[];

int dp[][], n;

int solve()

{

    memset(dp, , sizeof(dp));

    for(int i = ; i <= n; i++)

    {

        for(int j = ; j <= n; j++)

        {

            dp[i][j] = max(dp[i - ][j], dp[i][j - ]);

            if(a[i] == b[j])dp[i][j] = max(dp[i][j], dp[i - ][j - ] + );

        }

    }

    return n - dp[n][n];

}

char s[] = "shdc";

int c[];

int main()

{

    int tot = ;

    for(char i = ''; i <= ''; i++)level_num[i] = ++tot;

    level_num['T'] = ++tot;level_num['J'] = ++tot;level_num['Q'] = ++tot;

    level_num['K'] = ++tot;level_num['A'] = ++tot;

    cin >> n;

    for(int i = ; i <= n; i++){cin >> a[i].num >> a[i].color;b[i] = a[i];}

    for(int i = ; i <= ; i++)c[i] = i;

    int ans = n;

    do

    {

        for(int i = ; i <= ; i++)level_color[s[i - ]] = c[i];

        for(int i = ; i < ( << ); i++)

        {

            for(int j = ; j < ; j++)

            {

                level_color[s[j]] *= ;

                if(i & ( << j))level_color[s[j]]++;

            }

            sort(b + , b +  + n);

            ans = min(ans, solve());

        }

    }while(next_permutation(c + , c + ));

    cout<<ans<<endl;

    return ;

}

D .Daydreaming Stockbroker

pro：开始你有100元，给出N天的股价单价，你每天可以选择用当时的价格交易。限制持有股份不超过100000， 问最后有多少钱。N<365;

sol：枚举之前哪天买即可。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

ll a[maxn],dp[maxn],ans=;

int main()

{

    int N;

    scanf("%d",&N);

    rep(i,,N) scanf("%lld",&a[i]);

    dp[]=dp[]=;

    rep(i,,N){

        rep(j,,i-){

           ll t=min(dp[j]/a[j],100000LL);

           dp[i]=max(t*a[i]+dp[j]-t*a[j],dp[i]);

        }

        ans=max(ans,dp[i]);

        dp[i+]=max(dp[i+],dp[i]);

    }

    printf("%lld\n",ans);

    return ;

}

E .Exponial

pro：给定N，M。求。N^((N-1)^(N-2)...)%M；(N,M<1e9)

sol：显然欧拉降幂。 注意幂>mod时才能降幂，4以内的小于1e9，所以特判。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

int n,m;

int phi(int x){

    int ans=x;

    for(int i=;i*i<=x;i++)

        if(x%i==){

            ans/=i;ans*=i-;

            while(x%i==) x/=i;

    }

    //cout<<x<<" "<<ans<<" "<<endl;;

    if(x>) ans/=x,ans*=x-;

    return ans;

}

int ksm(int x,int y,int p){

    int ans=;

    for(;y;y>>=){

        if(y&)ans=(ll)ans*x%p;

        x=(ll)x*x%p;

    }

    return ans;

}

int dfs(int x,int y){

    if(y==) return ;

    if(x==) return ;

    if(x==) return ksm(x,,y);

    if(x==) return ksm(x,,y);

    if(x==) return ksm(x,,y);

    if(x==) return x%y;

    int ph=phi(y);

    return ksm(x,dfs(x-,ph)+ph,y);

}

int main(){

    scanf("%d%d",&n,&m);

    printf("%d",dfs(n,m));

    return ;

}

G .Game Rank

排位模拟题。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

int n,lev=,st,wins;

char s[];

int main(){

    scanf("%s",s+);

    n=strlen(s+);

    for(int i=;i<=n;i++){

        if(s[i]=='W'){

            if(lev>=&&wins>=)st+=,wins++;

            else st++,wins++;

            while(lev>&&st>)lev--,st-=;

            while(lev>&&st>)lev--,st-=;

            while(lev>&&st>)lev--,st-=;

            while(st>)lev--,st-=;

        }

        else{

            wins=;

            if(lev<=)st--;

            if(st<){

                lev++;

                if(lev>)lev=,st=;

                else if(lev>)st=;

                else if(lev>)st=;

                else st=;

            }

        }

        if(lev<=)return *puts("Legend");

    }

    printf("%d",lev);

    return ;

}

H .Highest Tower

pro：BZOJ4886

小Q正在玩一个叠塔的游戏，游戏的目标是叠出尽可能高的塔。在游戏中，一共有n张矩形卡片，其中第i张卡片的
长度为a_i，宽度为b_i。小Q需要把所有卡片按一定顺序叠成一座塔，要求对于任意一个矩形，它的长度要严格大
于它上边的任意一个矩形的长度。塔的高度为所有矩形的宽度之和。在游戏中，小Q可以将卡片翻转90度来使用，
而且必须用上全部n张卡片。请写一个程序，帮助计算小Q能叠出最高的塔的高度。

sol：定向问题。 不难证明最后是一棵或者多棵树或者环套树。 证明https://blog.csdn.net/V5ZSQ/article/details/79337446?utm_source=blogxgwz8

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

map<int,int>mp;

int ind[maxn],tot,mx[maxn],fa[maxn],tag[maxn],val[maxn]; ll ans;

int find(int x){

    if(x==fa[x]) return x;

    return fa[x]=find(fa[x]);

}

int u[maxn],v[maxn];

int main()

{

    int N,x,y;

    scanf("%d",&N);

    rep(i,,N){

        scanf("%d%d",&u[i],&v[i]);

        x=u[i]; y=v[i];

        if(!mp[x]) mp[x]=++tot,val[tot]=mx[tot]=x;

        if(!mp[y]) mp[y]=++tot,val[tot]=mx[tot]=y;

        x=u[i]=mp[x]; y=v[i]=mp[y];

        ind[x]++; ind[y]++;

    }

    rep(i,,tot) fa[i]=i;

    rep(i,,tot){

        x=find(u[i]); y=find(v[i]);

        if(tag[x]&&tag[y]) continue;

        if(x==y) tag[y]=;

        else fa[x]=y,tag[y]|=tag[x],mx[y]=max(mx[x],mx[y]);

    }

    rep(i,,tot){

        ans+=1LL*(ind[i]-)*val[i];

        if(find(i)==i&&!tag[i]) ans+=mx[i];

    }

    printf("%lld\n",ans);

    return ;

}

J .Jumbled Compass

模拟。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=;i<=;i++){

        if((n+i)%==m)return *printf("%d",i);

        if((n-i+)%==m)return *printf("%d",-i);

    }

}

K .Keeping the Dogs Apart

题意: 给定两支猫的行走路线, 都是直线行走, 求他们都在走的最近距离.

思路: 模拟即可. 每次得到min{到转折点的时间},  然后得到结束位置, 至于这个过程的最近距离,我们可以假设一个不动,那么就是点到线段的距离. 继续模拟.

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

double x[maxn][],y[maxn][],ans;

const double inf=1e200;

const double pi=*atan(1.0);

struct point{

    double x,y;

    point(double a=,double b=):x(a),y(b){}

};

int dcmp(double x){ return fabs(x)<0.0000000000001?:(x<?-:);}

point operator +(point A,point B) { return point(A.x+B.x,A.y+B.y);}

point operator -(point A,point B) { return point(A.x-B.x,A.y-B.y);}

point operator *(point A,double p){ return point(A.x*p,A.y*p);}

point operator /(point A,double p){ return point(A.x/p,A.y/p);}

point rotate(point A,double rad){

    return point(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));

}

bool operator ==(const point& a,const point& b) {

     return dcmp(a.x-b.x)==&&dcmp(a.y-b.y)==;

}

double dot(point A,point B){ return A.x*B.x+A.y*B.y;}

double det(point A,point B){ return A.x*B.y-A.y*B.x;}

double dot(point O,point A,point B){ return dot(A-O,B-O);}

double det(point O,point A,point B){ return det(A-O,B-O);}

double length(point A){ return sqrt(dot(A,A));}

double angle(point A,point B){ return acos(dot(A,B)/length(A)/length(B));}

bool isPointOnSegment(point p,point a1,point a2)

{

    //点是否在线段上

    return dcmp(det(a1-p,a2-p)==&&dcmp(dot(a1-p,a2-p))<=);

}

double distoseg(point P,point A,point B)

{

    if(isPointOnSegment(P,A,B)) return 0.0;

    //点到线段距离

    if(A==B) return length(P-A);

    point v1=B-A,v2=P-A,v3=P-B;

    if(dcmp(dot(v1,v2))<) return length(v2);

    else if(dcmp(dot(v1,v3))>) return length(v3);

    return fabs(det(v1,v2)/length(v1));

}

double dist(double x1,double y1,double x2,double y2)

{

    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

}

void solve(int A,int B,double t)

{

    double dx[],dy[];

    double d1=dist(x[A][],y[A][],x[A+][],y[A+][]);

    double d2=dist(x[B][],y[B][],x[B+][],y[B+][]);

    dx[]=(x[A+][]-x[A][])/d1; dy[]=(y[A+][]-y[A][])/d1;

    dx[]=(x[B+][]-x[B][])/d2; dy[]=(y[B+][]-y[B][])/d2;

    double sx=x[A][],sy=y[A][],tx=x[A][]+(dx[]-dx[])*t,ty=y[A][]+(dy[]-dy[])*t;

    double res=distoseg(point(x[B][],y[B][]),point(sx,sy),point(tx,ty));

    ans=min(ans,res);

    x[A][]+=dx[]*t; y[A][]+=dy[]*t;

    x[B][]+=dx[]*t; y[B][]+=dy[]*t;

}

int main()

{

    int N,M;

    scanf("%d",&N);

    rep(i,,N) scanf("%lf%lf",&x[i][],&y[i][]);

    scanf("%d",&M);

    rep(i,,M) scanf("%lf%lf",&x[i][],&y[i][]);

    ans=;

    int A=,B=;

    while(A<N&&B<M){

        double da=dist(x[A][],y[A][],x[A+][],y[A+][]);

        double db=dist(x[B][],y[B][],x[B+][],y[B+][]);

        if(da<db){

            solve(A,B,da);

            A++;

        }

        else if(da==db){

            solve(A,B,da);

            A++; B++;

        }

        else {

            solve(A,B,db);

            B++;

        }

    }

    printf("%.8lf\n",ans);

    return ;

}
05-11 19:28
Powered by LMLPHP ©2024 SOL 0.052138