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;
}
全部评论
(0) 回帖