PAT-甲级-1088-to-1091

1088 Rational Arithmetic

四则运算模拟题，代码太丑了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
struct node{    
    ll x,y;
    int f;
}a,b; 
ll gcd(ll a,ll b){
    return !b?a:gcd(b,a%b);
}
void show(ll x,ll y,int op){
    if(!y){
        printf("Inf");return;
    }
    if(op==-1) printf("(-");
    if(x%y==0){
        printf("%lld",x/y);
    }
    else {
        if(x/y) printf("%lld ",x/y);
        printf("%lld/%lld",x-x/y*y,y);
    }
    if(op==-1) printf(")");
}
void hj(ll &x,ll &y){
    ll g=gcd(x,y);
    x/=g,y/=g;
}
void Print(char op){
    show(a.x,a.y,a.f);printf(" %c ",op);show(b.x,b.y,b.f);printf(" = ");
}
int main(){
    scanf("%lld/%lld %lld/%lld",&a.x,&a.y,&b.x,&b.y);
    if(a.x<0) a.f=-1,a.x=-a.x;
    else a.f=1;
    if(b.x<0) b.f=-1,b.x=-b.x;
    else b.f=1;
    hj(a.x,a.y);hj(b.x,b.y);
    Print('+');
    ll lcm=a.y/gcd(a.y,b.y)*b.y;
    node z;
    z.x=a.f*lcm/a.y*a.x+b.f*lcm/b.y*b.x;
    if(z.x<0) z.f=-1,z.x=-z.x;
    else z.f=1;
    z.y=lcm;hj(z.x,z.y);
    show(z.x,z.y,z.f);printf("\n");
    Print('-');
    z.x=a.f*lcm/a.y*a.x-b.f*lcm/b.y*b.x;
    if(z.x<0) z.f=-1,z.x=-z.x;
    else z.f=1;
    z.y=lcm;hj(z.x,z.y);
    show(z.x,z.y,z.f);printf("\n");
    Print('*');
    z.x=a.f*a.x*b.x*b.f;
    z.y=a.y*b.y;
    if(z.x<0) z.f=-1,z.x=-z.x;
    else z.f=1;hj(z.x,z.y);
    show(z.x,z.y,z.f);printf("\n");
    Print('/');
    z.x=a.f*a.x*b.y;
    z.y=a.y*b.x*b.f;
    if((z.x<0&&z.y>0)||(z.x>0&&z.y<0)){
        z.x=abs(z.x),z.y=abs(z.y);
        z.f=-1;
    } 
    else z.f=1;hj(z.x,z.y);
    show(z.x,z.y,z.f);printf("\n");
    return 0;
}

1089 Insert or Merge

插入排序，每次排好第$i$个位置，后面位置保持原序。

归并排序，分区间合并，类似倍增。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
int a[N],b[N],n; 
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    int p=1,p1;
    while(p<n&&b[p]<=b[p+1]) p++;
    p1=++p;
    while(p<=n&&a[p]==b[p]) p++;
    if(p==n+1){
        puts("Insertion Sort");
        sort(b+1,b+p1+1);printf("%d",b[1]);
        for(int i=2;i<=n;i++)
            printf(" %d",b[i]);
    }
    else {
        puts("Merge Sort");
        int f=1,x=1;
        while(f){
            f=0;
            for(int i=1;i<=n;i++)
                if(a[i]!=b[i]) {
                    f=1;break;
                }
            x<<=1;
            for(int i=1;i<=n/x;i++)
                sort(a+(i-1)*x+1,a+i*x+1);
            sort(a+(n/x)*x+1,a+n+1);
        }
        printf("%d",a[1]);
        for(int i=2;i<=n;i++) printf(" %d",a[i]);
    }
    return 0;
}

1090 Highest Price in Supply Chain

$bfs,dfs$求深度的题，随便搞都行。

1091 Acute Stroke

求所有连通块大小，$bfs,dfs$都可，但本题因为递归深度较大，貌似一般机器最大递归深度是$1000$，因为因为一维的深度大于$1000$了，所以跑$dfs$会导致最后两个点段错误，所以老老实实跑$bfs$就好了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1305,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int m,n,l,t;
int a[N][130][65],vis[N][130][65],cnt,ans;
int d[6][3]={1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};
struct node{
    int x,y,z;
}u;
void bfs(int x,int y,int z){
    u={x,y,z};
    queue<node>q;
    q.push(u);vis[x][y][z]=1;
    while(!q.empty()){
        u=q.front();q.pop();
        cnt++;
        for(int i=0;i<6;i++){
            int nx=u.x+d[i][0],ny=u.y+d[i][1],nz=u.z+d[i][2];
            if(nx>=1&&nx<=m&&ny>=1&&ny<=n&&nz>=1&&nz<=l&&!vis[nx][ny][nz]&&a[nx][ny][nz])
                vis[nx][ny][nz]=1,q.push({nx,ny,nz});
        }
    }
    ans+=(cnt>=t)*cnt;cnt=0;
}
int main(){
    scanf("%d%d%d%d",&m,&n,&l,&t);
    for(int k=1;k<=l;k++)
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                    scanf("%d",&a[i][j][k]);
    for(int k=1;k<=l;k++)
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                if(!vis[i][j][k]&&a[i][j][k])
                    bfs(i,j,k);
            printf("%d\n",ans);
    return 0;
}