GCPC 2022 题解

2023/6/12 C++ 算法竞赛 题解 GCPC

存一下代码

A. Alternative Architecture

就是算一下斜边一定下的直角三角形个数，需要注意的是斜边并不是 和 ，而是 和 ，复杂度要求不高，暴搜即可

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    ll a,b;
    cin>>a>>b;
    if(a>b)
        swap(a,b);
    a-=1,b-=1;
    ll cnt=0;
    for(ll i=1;i<a;i++)
    {
        if(b*i%a!=0)
            continue;
        ll s=sqrt(a*a-i*i);
        if(s*s+i*i==a*a)
        {
            if(s*b%a==0)
                cnt++;
        }
    }
    if(a==b)
        cout<<cnt+1<<'\n';
    else
        cout<<cnt*2+2<<'\n';
    return 0;
}

C. Chaotic Construction

只需查看两个方向上是否有障碍物即可，直接查询复杂度会爆，用树状数组优化

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) ((x) & (-(x)))
const int N=2e5+5;
int n;
int tree[N];
void update(int x,int d)
{
    while(x<=n)
    {
        tree[x]+=d;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    int q;
    cin>>n>>q;
    memset(tree,0,sizeof(tree));
    for(int i=1;i<=q;i++)
    {
        char op;
        int a;
        cin>>op>>a;
        if(op=='-')
            update(a,1);
        else if(op=='+')
            update(a,-1);
        else if(op=='?')
        {
            int b;
            cin>>b;
            if(a>b)
                swap(a,b);
            if((sum(a)==0&&(sum(n)-sum(b-1)==0))||sum(b)-sum(a-1)==0)
                cout<<"possible"<<'\n';
            else
                cout<<"impossible"<<'\n';
        }
    }
    return 0;
}

E. Enjoyable Entree

, ,

用特征方程可以直接解出来 的通式:

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    ll n;
    scanf("%ld",&n);
    long double ans2=4.0/3*pow(-0.5,n)+2.0/3;
    printf("%Lf %Lf\n",(1-ans2)*100,ans2*100);
    return 0;
}

I. Improving IT

如果将 当做从第 个月买入CPU开始经历 个月之后将CPU卖掉所需成本，那么这个题就是求 这些点组成的图中从 到 的最短路径

记忆化搜索即可，复杂度为 符合要求

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e6;
int n,m;
int arc[N];
ll dp[N];
int num(int x,int y)
{
    return x*(m+2)+y;
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    memset(arc,-1,sizeof(arc));
    for(int i=1;i<=n;i++)
    {
        int c;
        cin>>c;
        for(int j=1;j<=min(m,n+1-i);j++)
        {
            int cj;
            cin>>cj;
            arc[num(i,j)]=c-cj;
        }
    }
    for(int i=1;i<=n+1;i++)
        dp[i]=LONG_LONG_MAX;
    dp[0]=dp[1]=0;
    for(int i=1;i<=n+1;i++)
    {
        for(int j=max(1,i-m);j<i;j++)
        {
            dp[i]=min(dp[i],dp[j]+arc[num(j,i-j)]);
        }
    }
    cout<<dp[n+1]<<'\n';
    return 0;
}

K. K.O. Kids

一个模拟

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    int i=0;
    int cnt=0;
    int op=0;
    while(i<s.length())
    {
        if(op==0)
        {
            if(s[i]=='L')
                i++;
            else
            {
                i++;
                cnt++;
                op=(op+1)%2;
            }
        }
        else
        {
            if(s[i]=='R')
                i++;
            else
            {
                i++;
                cnt++;
                op=(op+1)%2;
            }
        }
        op=(op+1)%2;
    }
    cout<<max(0,k-cnt)<<'\n';
    return 0;
}

L. Lots of Land

可以看出有解的话每一块的面积 。

并且 时一定有解。

如果 是素数，那么显然可以；如果 不是素数，那么可以选择 与 的最小的公约数作为矩形的短边，然后用仿射变换将短边变回1，重复这个过程，可知 不为素数时与 为素数时结果一样。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
char ch[N][N];
int main() {
    ios::sync_with_stdio(false);
    int l,w,n;
    cin>>l>>w>>n;
    if(l*w%n!=0)
        cout<<"impossible"<<'\n';
    else
    {
        int s=l*w/n;
        int x=1,y=1;
        for(int i=1;i<=s;i++)
        {
            if(s%i!=0)
                continue;
            if(l%i==0&&w%(s/i)==0)
            {
                x=i,y=s/i;
                break;
            }
        }
        char c='A';
        //cout<<x<<' '<<y<<'\n';
        for(int i=0;i<l;i++)
        {
            for(int j=0;j<w;j++)
            {
                ch[i][j]=c+j/y;
            }
            if((i+1)%x==0)
                c+=w/y;
        }
        for(int i=0;i<l;i++)
        {
            for(int j=0;j<w;j++)
                cout<<ch[i][j];
            cout<<'\n';
        }
    }
    return 0;
}
img_show