复兴提高班第二十二课 综合练习（二）
2025-10-31 12:45:39
发布于：上海
3阅读
0回复
0点赞
T1【综合练习(一)】水果
#include<bits/stdc++.h>
using namespace std;
int t,m;
struct fir {
string name; //水果的名字
string lcat; //产地
int num;
} a[109];
bool cmp(fir x,fir y) {
if(x.lcat != y.lcat)
return x.lcat < y.lcat;
else
return x.name < y.name;
}
int main() {
cin >> t;
while(t--) {
cin >> m;
for(int i = 1; i <= m; i++)
cin >> a[i].name >> a[i].lcat >> a[i].num; //水果名字 产地 数量
sort(a + 1,a + 1 + m,cmp);
string lf = a[1].name , lc = a[1].lcat; //lf:水果名字 lc：产地 lfn:水果数量
int lfn = a[1].num;
cout<<lc<<endl;
for(int i = 2; i <= m; i++) {
if(a[i].lcat != lc) { //产地是否相同
cout << " |----" << lf << "(" << lfn << ")" << endl;
lc = a[i].lcat;
lf = a[i].name;
lfn = a[i].num;
cout << lc << endl;
} else if(a[i].name != lf) { //产地相同，水果不同
cout << " |----" << lf << "(" << lfn << ")" << endl;
lf = a[i].name;
lfn = a[i].num;
} else //产地相同 水果相同 数量累加
lfn += a[i].num;
}
cout << " |----" << lf << "(" << lfn << ")" << endl;
if(t)
cout << endl; //控制格式
}
return 0;
}
T2【综合练习(一)】Hero
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
struct hero {
int dps;
int hp;
double ave;
} a[22];
int n , ans;
bool cmp(hero x,hero y) {
return x.ave > y.ave;
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i].dps >> a[i].hp;
a[i].ave = a[i].dps * 1.0 / a[i].hp; //攻击力和血量的比值
ans += a[i].dps; //总攻击值
}
sort(a + 1,a + 1 + n,cmp); //排序
int sum = 0; //损失的hp累加
for(int i = 1; i <= n; i++) {
int k = a[i].hp;
while(k > 0) { //消灭这个敌人 ,hp减为0
k--;
sum += ans;
}
ans -= a[i].dps; //消灭了这个人，这个人的攻击力减去
}
cout << sum;
return 0;
}
T3【综合练习(一)】瓷砖
#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[55][55];
int sum;
int to[4][2] = {-1,0,0,1,1,0,0,-1}; //四个方向
void dfs(int x,int y) {
for(int i = 0; i < 4; i++) {
int tx = x + to[i][0];
int ty = y + to[i][1];
if(tx >= 0 && tx < n && ty >= 0 && ty < m && a[tx][ty] == '.') {
sum++;
a[tx][ty] = '#';
dfs(tx,ty);
}
}
}
int main() {
cin >> n >> m;
for(int i = 0; i < n; i++) //输入地图
cin >> a[i];
int bx,by;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(a[i][j] == '@') { //. # @ 黑色的瓷砖、红色的瓷砖、小林的初始位置
bx = i; //起点
by = j;
}
}
}
sum = 1; //记录答案
a[bx][by] = '#';
dfs(bx,by);
cout << sum;
return 0;
}
T4【综合练习(一)】数的划分
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int n,k,res;
int a[10];
void dfs(int step) {
if(n == 0) //n全部被瓜分完
return;
if(step == k) { //分了规定的k份
if(n >= a[step-1]) {
res++;
return;
}
}
for(int i = a[step - 1]; i <= n / (k - step + 1); i++) { //下限 上限
a[step] = i;
n -= i;
dfs(step + 1);
n += i;
}
}
int main() {
cin >> n >> k;
a[0] = 1;//a[0]相当于比较的作用，保证每一份不为空
dfs(1);
cout << res;
return 0;
}
T5【综合练习(一)】Cow Travelling S
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;
int to[4][2]= {-1,0,0,1,1,0,0,-1};
int n,m,t;
char mp[N][N]; //.为草地 *为障碍
int a[N][N];
int bx,by,ex,ey;
int res;
int dp[N][N][20];
int dfs(int x,int y,int step)
{
if(step>t) //剪枝1
return 0;
if(step+fabs(x-ex)+fabs(y-ey)>t) //剪枝2，走到(x,y),已经走了T秒，若(x,y)到目标点(ex,ey)的最短距离花费的总时间>t,则直接返回
return 0;
if(dp[x][y][step])
return dp[x][y][step];
if(x==ex&&y==ey&&step==t) //奶牛总是在移动，结束条件是刚好走了t秒 ,可以重复走
return 1;
int sum=0;
for(int i=0; i<4; i++)
{
int tx=x+to[i][0];
int ty=y+to[i][1];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]==1)
sum+=dfs(tx,ty,step+1);
}
dp[x][y][step]=sum;
return sum;
}
int main()
{
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
cin>>n>>m>>t; //地图n*m t秒 (R1,C1)-->(R2,C2)
for(int i=0; i<n; i++)
cin>>mp[i];
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(mp[i][j]=='*')
a[i+1][j+1]=0;
else
a[i+1][j+1]=1; //1能走、0不能走
}
}
cin>>bx>>by>>ex>>ey;
cout<<dfs(bx,by,0);
return 0;
}
T6【综合练习(一)】PM2.5
#include<bits/stdc++.h>
using namespace std;
int t,n;
struct PM
{
int a1,a2;
int xf; //差值
int id;
} a[110];
bool cmp(PM x,PM y)
{
if(x.xf!=y.xf)
return x.xf > y.xf;
else
{
if(x.a2!=y.a2)
return x.a2 < y.a2;
else
return x.id < y.id;
}
}
int main()
{
cin>>n;
for(int i=0; i<n; i++)
{
cin>>a[i].a1>>a[i].a2;
a[i].xf=a[i].a1-a[i].a2;
a[i].id=i;
}
sort(a,a+n,cmp);
for(int i=0; i<n; i++)
cout<<a[i].id<<" ";
cout<<endl;
return 0;
}
T7【综合练习(一)】狗哥玩木棒
#include<bits/stdc++.h>
using namespace std;
int t,m;
bool vis[29];
int a[29],sum;
bool cmp(int x,int y)
{
return x>y;
}
bool dfs(int num,int len,int rest) //剩余的小木棒的数量 长度 剩余要拼接的
{
if(num==0 && rest==0)
return true;
if(rest==0)
rest=len;
for(int i=1;i<=m;i++)
{
if(vis[i])
continue;
if(a[i]>rest)
continue;
vis[i]=true;
if(dfs(num-1,len,rest-a[i]))
return true;
vis[i]=false;
if(a[i]==rest || len==rest) //剪枝3
break;
while(a[i]==a[i+1]) //剪枝2
i++;
}
return false;
}
int main()
{
cin>>t;
while(t--)
{
sum=0;
memset(vis,0,sizeof(vis));
cin>>m; //m根木棒
for(int i=1; i<=m; i++) {
cin>>a[i];
sum+=a[i]; //总长度
}
sum/=4; //正方形的边长
sort(a+1,a+1+m,cmp);//剪枝1
int flag=dfs(m,sum,sum);
if(flag)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
return 0;
}
有帮助，赞一个