7-10 链表去重 (25分)
题意：给出一组链表，删除数据重复的链表，输出去重后的链表和删除的链表。
题解：用结构体定义链表(包含链表的数据和下一个链表的地址)，然后把输入的数据存到链表中，然后定义一个标记数组用来判断是否重复，把删除的链表存到a2数组，重复的链表存到a1数组，保存a2，a1
的长度，注意格式的输出。
#include<bits/stdc++.h> using namespace std; struct node{ int data; int next; }l[100000]; int vis[100000],a1[100000],a2[100000];//vis数组判断是否重复,a1去重完的链表,a2删除完的链表 int main(){ ios::sync_with_stdio(false); int add,n; int ad,da,ne; cin>>add>>n; for(int i=0;i<n;i++){ cin>>ad>>da>>ne;//ad是地址 da是数据 ne是下个地址 l[ad].data=da; l[ad].next=ne; } int count1=0,count2=0; for(int i=add;i!=-1;i=l[i].next){//由它们的地址来找出数据是否相等 if(vis[abs(l[i].data)]==0){ vis[abs(l[i].data)]=1; a1[count1]=i; count1++; } else{ a2[count2]=i; count2++; } } for(int i=0;i<count1;i++){//输出去重链表 cout<<setw(5)<<setfill('0')<<a1[i]<<" "<<l[a1[i]].data<<" "; if(i!=count1-1){ cout<<setw(5)<<setfill('0')<<a1[i+1]<<endl; } else{ cout<<-1<<endl; } } for(int i=0;i<count2;i++){//输出删除的链表 cout<<setw(5)<<setfill('0')<<a2[i]<<" "<<l[a2[i]].data<<" "; if(i!=count2-1){ cout<<setw(5)<<setfill('0')<<a2[i+1]<<endl; } else{ cout<<-1<<endl; } } }
7-12 月饼 (25分)
题意：给出n个种类的月饼的价格和库存，判断卖出m个月饼最大的收益。
题解：贪心，根据每个不同种类的月饼的平均售价进行排序，然后从售价大的到小的进行判断，当m=0时结束循环即可。注意精度问题（比赛的时候差了3分一直看不出来- -）
#include<bits/stdc++.h> using namespace std; struct yb{ double sj; double xql; double pjsj; }; bool cmp(yb p,yb q){ return p.pjsj>q.pjsj; } int main(){ int n,d; cin>>n>>d; yb a[n+10]; for(int i=0;i<n;i++){ cin>>a[i].xql; } for(int i=0;i<n;i++){ cin>>a[i].sj; a[i].pjsj=double(a[i].sj*1.0/a[i].xql); } sort(a,a+n,cmp); double sum=0; // for(int i=0;i<n;i++){ // cout<<a[i].pjsj<<endl; // } for(int i=0;i<n;i++){ if(a[i].xql<=d){ // sum+=a[i].xql*a[i].pjsj; sum+=a[i].sj; d-=a[i].xql; } else{ sum+=a[i].pjsj*d; break; } if(d<=0){ break; } } printf("%.2lf ",sum); }
7-5 6翻了 (15分)
题意：把这个字符串中6进行转换，如果6超过3个改成9，如果6超过9个改成27。
题解：就是记录每个6的个数存到数组中，然后进行遍历，如果遇到6判断这个6的字符串有多少个6然后进行输出6还是9还是27即可。
#include<bits/stdc++.h> using namespace std; int main(){ string p; getline(cin,p); int g[10001]; int count; int count1=0; for(int i=0;i<p.size();i++){ if(p[i]=='6'){ count=0; for(int j=i;p[j]=='6';j++){ count++; } //cout<<count<<endl; g[count1]=count; count1++; i+=count; } } int count2=0; for(int i=0;i<p.size();i++){ if(p[i]=='6'){ if(g[count2]<=3){ for(int j=0;j<g[count2];j++){ cout<<'6'; } i+=g[count2]; if(i<p.size()){ cout<<" "; } count2++; } else if(g[count2]>3&&g[count2]<=9){ cout<<'9'; i+=g[count2]; if(i<p.size()){ cout<<" "; } count2++; } else if(g[count2]>9){ cout<<"27"; i+=g[count2]; if(i<p.size()){ cout<<" "; } count2++; } } else{ cout<<p[i]; } } cout<<endl; }
7-11 部落 (25分)
题意:
输入每个部落的人数和序号，输出总人数和几个不交融的部落，再根据输入判断这2个人的部落是否有交集。
题解：根据并差集
#include<stdio.h>
#include<iostream>
#include<cstring>
#define maxn 100000
int f[maxn];
using namespace std;
void init() //初始化函数因为没有告知人数所以就到maxn(作用:根都为自己)
{
for(int i=1;i<=maxn;i++){
f[i]=i;
}
}
int getf(int a) //找爹函数(找根)
{
if(f[a]==a) //找到根(爹是自己~ ~),退出
return a;
else{
f[a]=getf(f[a]);//递归调用，找该树的根(祖先)
return f[a];
}
}
void merge(int v,int u) //找两个树的关系，如果祖先不一样(即没有关系，就合并，这里采用偏左原则)
{
int t1,t2;
t1=getf(v);
t2=getf(u);
if(t1!=t2){
f[t2]=t1; //让t1为t2的爹
}
}
int main()
{
int n1,party[maxn],map[maxn];
int m,n=0,su=0,n2;
int i,a,b;
int sum=0;
cin>>m;
init();
memset(map,-1,sizeof(maxn)); //把map的值都设为-1，函数头文件#include<csting>,格式:memset(地址，需要设置成的值，sizeof);
while(m--)
{
cin>>n1;
n=n+n1;
for(i=1;i<=n1;i++){
cin>>party[i];
map[party[i]]=1; //输入时会用重复的，用标记数组map，进行标记，把输入树对应的值改为1
if(i-1)
merge(party[i-1],party[i]);
}
}
for(i=0;i<=n;i++){ //n没实际含义，只是圈定了一个范围，毕竟maxn太大
if(map[i]==1){
sum++;
}
}
for(i=1;i<=sum;i++){
if(f[i]==i){
su++;
}
}
cin>>n2;
cout<<sum<<" "<<su<<endl;
while(n2--){
cin>>a>>b;
if(getf(a)==getf(b))
cout<<"Y"<<endl;
else
cout<<"N"<<endl;
}
return 0;
}