2022年成都工业学院新生程序设计竞赛题解

A.你好，程序猿

这道题都不会？小黑子无疑了！！

#include<iostream>
using namespace std;

int main()
{
 cout<<"⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣦⣤⣄⣄"<<endl;
 cout<<"⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⢿⣿⣿⣷⡀"<<endl;
 cout<<"⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⡁⣠⣿⣿⣿⣿⣦"<<endl;
 cout<<"⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⣿⠿⠃⠘⠛⠙⣿⣿⣿"<<endl;
 cout<<"⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠃⠀⠶⠆⠀⠀⠸⠏⠁"<<endl;
 cout<<"⠀⠀⠀⠀⠀⠀⠀⠀⢸⣤⣤⠐⠋⠉⠀⢀⣿⡆"<<endl;
 cout<<"⠀⠀⠀⠀⠀⣆⠀⠀⢿⣿⣿⣷⣀⣤⣴⣿⡾⡇"<<endl;
 cout<<"⠀⠀⠀⠀⣼⣿⣿⣿⣦⣿⣿⣿⣿⣿⣿⡟⣾⣿"<<endl;
 cout<<"⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⠻⠿⠱⢻⣿⣿⣄"<<endl;
 cout<<"⠀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⢞⣋⣠⡿⠁⣠⣦"<<endl;
 cout<<"⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣿⣠⣿⣿⣿⣧"<<endl;
 cout<<"⣿⣿⣿⣿⣿⡿⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿"<<endl;
    return 0;
}

B.租用游艇

dijkstra

#include<iostream>
using namespace std;

const int N = 210;
int r[N][N]; 
int dist[N];  //1到i点的距离 

int main()
{
	int n;
	cin>>n;
	for(int i=1; i<=n; i++) 
		for(int j=i+1; j<=n; j++)
			cin>>r[i][j];
	
	for(int i=1; i<=n; i++) dist[i] = r[1][i];
	for(int i=1; i<=n; i++)
		for(int j=1; j<i; j++)
			dist[i] = min(dist[i], dist[j]+r[j][i]); 
	cout<<dist[n]<<endl;
	return 0;
}

C.只因你太美

字符串处理（会的都是真ikun)

#include<iostream>
using namespace std;

int main()
{
    bool have = false;
    string s, res = "";
    cin>>s;
    int n = s.length();
    int i;
    for(i=0; i<n; i++)
    {
        if(i+1<n && s[i]=='j' && s[i+1]=='i') 
        {
            res += "zhiyin"; 
            i++;
            have = true;
        }
        else res += s[i];
    }
    if(!have) cout<<"zhiyinnitaimei"<<endl;
    else cout<<res<<endl;
    return 0;
}

D.切分披萨

区间DP+高精度

#include<iostream>
#include<cstring>
using namespace std;

typedef long long LL;
const int N = 55, M = 35;  
int w[N];
int f[N][N][M];

void add(int a[], int b[])
{
    int c[M]; 
    memset(c, 0, sizeof c);
    int t = 0;
    for(int i=0; i<M; i++)
    {
        t += a[i]+b[i];
        c[i] = t%10;
        t /= 10;
    }
    memcpy(a, c, sizeof c); 
}
void mul(int a[], int b)
{
    static int c[M];
    memset(c, 0, sizeof c);
    LL t = 0;  
    for(int i=0; i<M; i++)
    {
        t += (LL) a[i]*b;
        c[i] = t%10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);
}
int cmp(int a[], int b[])
{
    for(int i=M-1; i>0; i--)  
        if(a[i] > b[i]) return 1;
        else if(a[i] < b[i]) return -1;
    return 0;
}
void print(int a[])
{
    int k = M-1;
    while(k && a[k]==0) k--;  //去掉高位0
    while(k >= 0) cout<<a[k--];
    puts("");
}
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) cin>>w[i];
    
    int temp[M]; 
    for(int len=3; len<=n; len++)  
    {
        for(int l=1; l+len-1<=n; l++)
        {
            int r = l+len-1;
            f[l][r][M-1] = 1;  //f[l][r] = 1后面接M-1个0
            for(int k=l+1; k<r; k++)  
            {
                memset(temp, 0, sizeof temp);
                temp[0] = w[l];  
                mul(temp, w[k]);
                mul(temp, w[r]);
                add(temp, f[l][k]);
                add(temp, f[k][r]);
                if(cmp(f[l][r], temp) > 0) memcpy(f[l][r], temp, sizeof temp);
            }
        }
    }
    print(f[1][n]);  
    return 0;
}

E.快乐水

模拟

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 110;
int a[N];

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n, m;
        cin>>n>>m;
        for(int i=0; i<n; i++) cin>>a[i];
        
        sort(a, a+n);
        int t = 0, cnt = 0;
        for(int i=0; i<n; i++)
        {
            if(m >= a[i] + t) 
            {
                m -= a[i] + t;
                t++;
                cnt++;
            }
            else break;
		}
        printf("%d %d\n", cnt, m);
	}
    return 0;
}

F.桃子合并

huffman编码，贪心

策略：每次合并两个最小的

#include<iostream>
#include<queue>
using namespace std;

const int N = 100010;
int a[N];

int main()
{
    int n;
    cin>>n;

    priority_queue<int, vector<int>, greater<int>> heap;  //小根堆
    while(n--)
    {
        int x;
        cin>>x;
        heap.push(x);
    }

    int res = 0;
    while (heap.size() > 1)  
    {
        int a = heap.top();  heap.pop();
        int b = heap.top();  heap.pop();
        res += a+b;
        heap.push(a+b);
    }
    cout<<res<<endl;
    return 0;
}

G.火柴棍数字

贪心

策略：若有有偶数根火柴，则全部摆成“1”，若为奇数根，摆一个“7”，其余全部摆成“1”

#include<iostream>
using namespace std;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        
        if(n-(n/2)*2) cout<<7;
        else cout<<1;
        for(int i=1; i<n/2; i++) cout<<1;
        cout<<endl;
    }
    return 0;
}

H.最小符号

思维题（硬做好像也可以）

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N = 200010;
int s[N];
 
int main()
{
	string str;
	cin>>str;
	
	int n = str.length();
	for(int i=0; i<n; i++) s[i] = str[i]-'0';
	int mi = n-1;
	for(int i=n-1; i>=0; i--)
	{
		if(s[i] < s[mi]) mi = i;
		else if(s[i] > s[mi]) s[i] = min(s[i]+1, 9);
	}
	sort(s, s+n);
	for(int i=0; i<n; i++) cout<<s[i];
	return 0;
}

I. 最大公约数

辗转相除法、暴力都能过

#include<iostream>
using namespace std;

int gcd(int a, int b)
{
    return b ? gcd(b, a%b) : a;
}
int main()
{
    int a, b;
    cin>>a>>b;
    cout<<gcd(a, b)<<endl;
    return 0;
}

J.简单题

枚举约数

#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;
int n,cnt,a[123456],num,minp[12345678],prime[12345678],p[20],t[20],x,f[12345678];
long long ans;
bool flag[12345678];
void solve1()
{
    long long ans=0;
    for (int i=1;i<=n;++i)
        for (int j=i+1;j<=n;++j)
            if (a[j]%a[i]==0)
                ++ans;
    printf("%lld\n",ans);
}
void dfs(int o,int s)
{
    if (o>num)
    {
        ans+=f[s];
        return;
    }
    int l=1;
    for (int i=0;i<=t[o];++i)
    {
        dfs(o+1,s*l);
        l=l*p[o];
    }
}
void pre()
{
    cnt=0;
    for (int i=2;i<=10000000;++i)   flag[i]=1;
    for (int i=2;i<=10000000;++i)
    {
        if (flag[i])
        {
            prime[++cnt]=i;
            minp[i]=i;
        }
        for (int j=1;j<=cnt;++j)
            if (i*prime[j]<=10000000)
            {
                minp[i*prime[j]]=prime[j];
                flag[i*prime[j]]=0;
                if (i%prime[j]==0)  break;
            }
            else break;
    }
}
void solve2()
{
    pre();
    for (int i=1;i<=n;++i)
    {
        num=0;
        x=a[i];
        while (x>1)
        {
            if (num && minp[x]==p[num]) t[num]++;
            else {t[++num]=1;p[num]=minp[x];}
            x/=minp[x];
        }
        dfs(1,1);
        f[a[i]]++;
    }
    printf("%lld\n",ans);
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
        scanf("%d",&a[i]); 
   solve2();
    return 0;
}

K.我的世界岩浆与水

模拟

#include<iostream>
using namespace std;

const int N = 1010;
int n, m, k;
int a[N][N];

void dao(int x, int y, int p, int len)
{
	int d = len-1>>1;
	for(int i=x-d; i<=x+d; i++)
	{
		for(int j=y-d; j<=y+d; j++)
		{
			if(i<1 || i>n || j<1 || j>m) continue;
			int dx = abs(i-x), dy = abs(j-y);
			if(dx+dy <= d) 
				a[i][j] = p;
		}
	}
}
int main()
{
	cin>>n>>m>>k;
	for(int i=0; i<k; i++)
	{
		int x, y, p, len;
		cin>>x>>y>>p>>len;
		dao(x, y, p, len);
	}
	
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
			printf("%d ", a[i][j]);
		printf("\n");
	}
	return 0;
}