目录
1096 Consecutive Factors （20 分）（思维）
1098 Insertion or Heap Sort （25 分）（插入排序和堆排序）
1097 Deduplication on a Linked List （25 分）（链表模拟）
1099 Build A Binary Search Tree （30 分）（二叉搜索树的建立）
1096 Consecutive Factors （20 分）（思维）
【题意】正整数n，求一段连续整数序列，使n能被这段连续整数的乘积整除；如果有多种情况，输出最长的序列；若仍不唯一，输出第一个数最小的方案。
【分析】最大值必然不会超过sqrt(x)；那么进行遍历，记录连续序列的起始位置st及不断维护最大长度len。最后输出即可
【代码】
#include<bits/stdc++.h>
using namespace std;typedef long long ll;int main()
{ll n;scanf("%lld",&n);ll r=(ll)sqrt(n);ll st=0,len=0;for(ll i=2;i<=r;++i){ll sum=1,now=i;while(1){sum*=now;if(n%sum!=0)break;if(now-i+1>len)st=i,len=now-i+1;now++;}}if(len==0)printf("1\n%lld\n",n);else {printf("%lld\n",len);for(ll i=0;i<len;++i){printf("%lld",st+i);if(i<len-1) printf("*");}}
}1098 Insertion or Heap Sort （25 分）（插入排序和堆排序）
【分析】插入排序+堆排序（之后整理一下..）
堆排序：
//构造最大堆
void MaxHeapFixDown(int a[], int i, int n){int j = 2*i+1;int temp = a[i];while(j<n){if(j+1<n&&a[j]<a[j+1])++j;if(temp>a[j])break;else{a[i]=a[j];i=j;j=2*i+1;}}a[i]=temp;
}//堆排序
void HeapSort(int a[], int n){for(int i= n/2-1;i>=0;i--)MaxHeapFixDown(a,i,n);for(int i=n-1;i>=1;i--){swap(a[i],a[0]);MaxHeapFixDown(a,0,i);}
}【代码】
#include<bits/stdc++.h>
using namespace std;const int maxn=110;
int a[maxn],b[maxn];int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&a[i]);for(int i=1;i<=n;++i)scanf("%d",&b[i]);int cnt=1,f=1;while(b[cnt]<=b[cnt+1] && cnt<=n)cnt++;cnt++;for(int i=cnt;i<=n;++i)if(a[i]!=b[i]){f=0;break;}if(f){puts("Insertion Sort");int x=b[cnt],f=0;for(int i=1;i<=n;++i){if(i==cnt)i++;if(i!=1)printf(" ");if(b[i]>=x && !f)printf("%d %d",x,b[i]),f=1;else printf("%d",b[i]);}puts("");}else{puts("Heap Sort"); int i=1,j=i*2;int deep=n;while(deep>2 && b[deep]>=b[1])deep--;swap(b[1],b[deep]);deep--;while(j<=deep){if(j+1<=deep && b[j]<b[j+1])j++;if(b[i]>=b[j])break;swap(b[i],b[j]);i=j;j=i*2;//for(int p=1;p<=n;++p)cout<<b[p]<<",";puts("");}for(int i=1;i<=n;++i)(i==n)?printf("%d\n",b[i]):printf("%d ",b[i]);}
}1097 Deduplication on a Linked List （25 分）（链表模拟）
【题意】给定链表中每个节点的地址、值、下一个地址指向，删去绝对值相等的结点，并输出删除后的以及删除的链表
【分析】
将每个节点的地址作为下标会比较好操作一点。然后标记数组存入两个vector中；
不需要循环求出每个节点的nxt，输出的时候该节点的nxt即为下一个结点的ard
这道题其实思路理清楚了就好了吧，做的时候比较混乱
【代码】
#include<bits/stdc++.h>
using namespace std;const int maxn=1e5+10;
struct node{int adr;int key;int nxt;
}a[maxn];
vector<node>v2,v1;
int book[maxn];int main()
{int st,n;int num1,num2;scanf("%d%d",&st,&n);for(int i=0;i<n;++i){int x;scanf("%d",&x);scanf("%d%d",&a[x].key,&a[x].nxt);a[x].adr=x;}memset(book,0,sizeof(book));int cnt1=0,cnt2=0;for(int i=st;i!=-1;i=a[i].nxt){if(!book[abs(a[i].key)]){book[abs(a[i].key)]=1;v1.push_back(a[i]);}else v2.push_back(a[i]);}int l1=v1.size(),l2=v2.size();for(int i=0;i<l1;++i){if(i==l1-1)printf("%05d %d -1\n",v1[i].adr,v1[i].key);else printf("%05d %d %05d\n",v1[i].adr,v1[i].key,v1[i+1].adr);}for(int i=0;i<l2;++i){if(i==l2-1)printf("%05d %d -1\n",v2[i].adr,v2[i].key);else printf("%05d %d %05d\n",v2[i].adr,v2[i].key,v2[i+1].adr);}
}1099 Build A Binary Search Tree （30 分）（二叉搜索树的建立）
【题意】给出每个节点的左右子节点，并规定0始终是根节点；由此建立BST并将输入的序列建立成此形态的树
【分析】BST的中序遍历序列是递增序列，由此建树
【代码】
#include<bits/stdc++.h>
using namespace std;const int maxn=110;
struct node{int lchild,rchild;int val;
}tree[maxn];
int a[maxn];
int lv[maxn];
int cnt1,cnt2;void getLevel(node &nd)
{if(nd.val==-1)return;queue<node>q;q.push(nd);while(!q.empty()){node n1=q.front();q.pop();lv[cnt2++]=n1.val;if(n1.lchild!=-1)q.push(tree[n1.lchild]);if(n1.rchild!=-1)q.push(tree[n1.rchild]);}
}
void getIn(node &nd)
{if(nd.lchild!=-1)getIn(tree[nd.lchild]);nd.val=a[cnt1++];if(nd.rchild!=-1)getIn(tree[nd.rchild]);
}
int main()
{int n;scanf("%d",&n);for(int i=0;i<n;++i){scanf("%d%d",&tree[i].lchild,&tree[i].rchild);tree[i].val=i;}for(int i=0;i<n;++i)scanf("%d",&a[i]);sort(a,a+n); cnt1=cnt2=0;getIn(tree[0]);getLevel(tree[0]);for(int i=0;i<n;++i)(i==n-1)?printf("%d\n",lv[i]):printf("%d ",lv[i]);
}