1001:Public Bike Management
题目大意：自行车数量管理，有一问题站点，解决问题求路径最短，并且让图中每一个站点的自行车数量都为c/2，outbikes最小，inbikes最小；
1 | #include <iostream> |
1002:All Roads Lead to Rome
和前面一题一样的思路，图的DFS确定所有可以到目的地的路线，按照一定规则选取最优路径，并存储；
1 | #include <iostream> |
1003：Highest Price in Supply Chain
刚开始没有理解题意，题意是分别输入以0-N-1为下标的父母结点的下标；
解题思路：按照输入建树，求层数；
使用一个向量数组存放当前结点的子节点：vector
注意树的DFS不需要vis标记访问，因为从根节点到达某一结点有且只有一条路径；
1 | #include <iostream> |
1004:Acute Stroke
三维的BFS，用DFS时间复杂度过大；
1 | #include <iostream> |
1005:The Largest Generation
家谱树问题，求结点最多的一层的结点数与层数；思路：使用vector数组保存每个结点的孩子，构建成家谱树，然后使用BFS计算每层结点数，过程中维护家谱树每一层的level，使用一个数组记录各层结点数；
1 | #include <iostream> |
1006:Cars on Campus
题目意思是给出一组车进出记录，给定时刻，算出状态还未in的车的数量，并且求出一天中停留时间最长的车牌号与时间；
题目不难，在理解题意上花了一点时间，主要是pat惯用的需要建立一个专用的数据结构node存储记录；
数据量较大，容易超时，刚开始用char type[4]来存储记录的状态，因此每次都需要调用strcmp函数对字符串进行比较，后改为bool字段，直接在输入时判断为in(true)/out(false)，没有超时；
1 | #include <iostream> |
1007:Consecutive Factors
题目大意：求一个数的最长的连续因数串；
思路：从1到sqrt(n)的范围内循环，计算从当前i开始能够被n整除的最长子串，保存比较长度，最后得出最长；
1 | #include <iostream> |
1008:Deduplication on a Linked List
题目大意：将链表式数组中绝对值重复的值取出来，放入一个新的数组中，需要输入当前地址，值，以及下一个地址值；
我的思路：
- 使用特定数据结构存储add,value,next,初始化按照链表顺序排好序；
- 从表头结点开始遍历，判断下一个结点的值是否出现过，flag[10001]表示是否出现过标记；
- 出现过则需要改变当前结点的next值，同时把重复结点赋予新数组，改变新数组的前一个结点的next值；
超时了！主要时间复杂度在排序O(n^2)!
不超时思路： - 空间换取时间，直接在当前地址存储value/next,inList[add].value=v;inList[add].next=n;
- 从起始地址开始，判断当前value是否访问过，removeList[] 与 outList[]存放最终结果各个结点的地址；
- 遍历输出List[i],inList[List [i]].value,List[i+1];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
int num,first;
/*
struct node
{
int add,value,next;
bool sign;
}List[100001],removeList[100001];
int flag[10001];
int s_index;
void InitNode()
{
int nnum=1;
List[0]=removeList[s_index];
int n=removeList[s_index].next;
while(n!=-1){
for(int j=0;j<num;j++){
if(removeList[j].add==n){
List[nnum++]=removeList[j];
n=removeList[j].next;
break;
}
}
}
}
int main()
{
int removenum=0;
cin>>first>>num;
memset(flag,0,sizeof(flag));
for(int i=0;i<num;i++){
cin>>removeList[i].add>>removeList[i].value>>removeList[i].next;
if(removeList[i].add==first)s_index=i;
}
InitNode();
flag[abs(List[0].value)]=1;
for(int i=0;i<num-1;i++){
int v=abs(List[i+1].value);
//发生重复
if(flag[v]!=0){
//从链表中去除结点
List[i].next=List[i+1].next;
//加入到remove链表中
if(removenum==0)removeList[removenum++]=List[i+1];
else {
removeList[removenum-1].next=List[i+1].add;
removeList[removenum++]=List[i+1];
}
List[i+1].sign=true;
}
else flag[v]=1;
}
int t=0,f=0;
for(int i=0;i<num;i++){
if(!List[i].sign){
if(t==num-removenum-1){
printf("%05d %d %d\n",List[i].add,List[i].value,-1);break;
}
printf("%05d %d %05d\n",List[i].add,List[i].value,List[i].next);
t++;
}
}
for(int i=0;i<removenum;i++){
if(i==removenum-1)
printf("%05d %d %d\n",removeList[i].add,removeList[i].value,-1);
else printf("%05d %d %05d\n",removeList[i].add,removeList[i].value,removeList[i].next);
}
return 0;
}*/
#define MAX 100001
struct node
{
int value,next;
}inList[MAX];
int outList[MAX],removeList[MAX];
bool flag[10001]={0};
int s_index=0;
int main()
{
scanf("%d%d",&first,&num);
int add;
for(int i=0;i<num;i++){
cin>>add;
scanf("%d%d",&inList[add].value,&inList[add].next);
if(add==first)s_index=add;
}
int temp=s_index;
int p=0,q=0;
int rfirst=0;
while(temp!=-1){
int v=abs(inList[temp].value);
//发生冲突
if(flag[v]){
if(q==0)rfirst=inList[temp].value;
removeList[q++]=temp;
}
else {
outList[p++]=temp;
flag[v]=1;
}
temp=inList[temp].next;
}
//输出
for(int i=0;i<p;i++){
if(i!=p-1){
//printf("%05d %d %05d\n",outList[i].value,outList[i+1].value);
printf("%05d %d %05d\n",outList[i],inList[outList[i]].value,outList[i+1]);
}
else printf("%05d %d %d\n",outList[i],inList[outList[i]].value,-1);
}
for(int i=0;i<q;i++){
if(i!=q-1){
printf("%05d %d %05d\n",removeList[i],inList[removeList[i]].value,removeList[i+1]);
}
else printf("%05d %d %d\n",removeList[i],inList[removeList[i]].value,-1);
}
}1009:Insertion or Heap Sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112#include <iostream>
#include <math.h>
using namespace std;
int num[101];
int num2[101];
int res[101];
int Heap_Size=0;
bool flag=false;
bool isSame(int arr[],int len)
{
for(int i=0;i<len;i++){
if(arr[i]!=res[i])return false;
}
return true;
}
void out_put(int arr[],int len)
{
for(int i=0;i<len;i++){
if(i!=0)cout<<" ";
cout<<arr[i];
}
}
//插入排序
bool Insert_Sort(int arr[],int len)
{
for(int i=1;i<len;i++){
int temp=arr[i];
int j;
for(j=i-1;j>=0;j--){
if(arr[j]>temp){
arr[j+1]=arr[j];
}
else {
break;
}
}
arr[j+1]=temp;
if(flag){
out_put(arr,len);
return true;
}
if(isSame(arr,len)){
cout<<"Insertion Sort"<<endl;
flag=true;
}
}
return false;
}
void Max_Heap(int arr[],int i)
{
int l=2*(i+1)-1;
int r=2*(i+1);
int largeset=i;
if(arr[l]>arr[i]&&l<Heap_Size){
largeset=l;
}
if(arr[r]>arr[largeset]&&r<Heap_Size){
largeset=r;
}
if(largeset!=i){
swap(arr[largeset],arr[i]);
Max_Heap(arr,largeset);
}
}
//建最大堆
void Build_Max_Heap(int arr[],int len)
{
//从第一个非叶子结点开始
for(int i=len/2-1;i>=0;i--)
{
Max_Heap(arr,i);
}
}
bool Heap_Sort(int arr[],int len)
{
Heap_Size=len;
Build_Max_Heap(arr,len);
for(int i=0;i<len-1;i++){
if(flag){
out_put(arr,len);
return true;
}
if(isSame(arr,len)){
cout<<"Heap Sort"<<endl;
flag=true;
}
swap(arr[Heap_Size-1],arr[0]);
Heap_Size--;
Build_Max_Heap(arr,Heap_Size);
}
return false;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>num[i];
num2[i]=num[i];
}
for(int i=0;i<n;i++){
cin>>res[i];
}
if(!Insert_Sort(num,n))
Heap_Sort(num2,n);
return 0;
}1010:Build A Binary Search Tree
根据输入构造二叉树，利用二叉搜索树的排序特点，将key[]从小到大排序后，就是BST的中序遍历的顺序，因此可以为BST直接赋值，再用queue层次遍历，实际上就是树的BFS；
刚开始还想要按照传统方法输入建树，也太蠢了吧！1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct treeNode
{
int left;
int right;
int value;
}Tree[101];
int key[101];
int index=0;
//中序遍历
void mid(int t)
{
if(t==-1)return;
mid(Tree[t].left);
Tree[t].value=key[index++];
mid(Tree[t].right);
}
//层次遍历
void BFS()
{
bool flag=false;
queue<treeNode>q;
q.push(Tree[0]);
while(!q.empty())
{
treeNode n=q.front();
q.pop();
if(flag)cout<<" ";
flag=true;
cout<<n.value;
if(n.left!=-1)q.push(Tree[n.left]);
if(n.right!=-1)q.push(Tree[n.right]);
}
}
int main()
{
int num;
cin>>num;
for(int i=0;i<num;i++){
cin>>Tree[i].left>>Tree[i].right;
}
for(int i=0;i<num;i++){
cin>>key[i];
}
sort(key,key+num);
//for(int i=0;i<num;i++)cout<<key[i]<<" ";
mid(0);
BFS();
return 0;
}1011:Forwards on Weibo
太感动了，思路都是自己想出来的！
挺切合实际的， - 用vector二维数组保存微博关注者；
- 使用queue保存每一level转发者；注意保存的是自己设定的node，其中包括level，保证转发层次在一定范围内；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
vector<vector <int> > User;
int flag[1001];//标记是否转发过
int N=0;//user数<=1000
int level=0;//follow层数<=6
int qnum=0;//查询次数
struct node
{
int index;
int Lev;
node(int _index, int _lev){
index=_index;
Lev=_lev;
}
};
int main()
{
cin>>N>>level;
int num;//关注人数
int follow;//关注人的下标值
User.resize(N+1);
//输入,记录关注者
for(int i=1;i<=N;i++){
cin>>num;
for(int j=0;j<num;j++){
cin>>follow;
User[follow].push_back(i);
}
}
/* cout<<"------------------------------"<<endl;
for(int i=1;i<=N;i++){
for(int j=0;j<User[i].size();j++){
cout<<User[i][j]<<" ";
}
cout<<endl;
}*/
cin>>qnum;
int k;
int sum=0;
for(int i=0;i<qnum;i++){
cin>>k;
queue<node> q;
memset(flag,0,sizeof(flag));
sum=0;
flag[k]=1;
q.push(node(k,0));
while(!q.empty()){
node temp=q.front();
q.pop();
//cout<<temp.index<<" "<<temp.Lev<<endl;
int now_level=temp.Lev;
if(now_level>=level)break;
for(int j=0;j<User[temp.index].size();j++){
if(!flag[User[temp.index][j]]){
sum+=1;
q.push(node(User[temp.index][j],now_level+1));
flag[User[temp.index][j]]=1;
}
}
}
cout<<sum<<endl;
// cout<<"------------------------------"<<endl;
}
return 0;
}1012:Kuchiguse
char str[101][256]字符数组的输入：scanf(“%s”,&str[i]) / string str[101]字符串输入：cin>>str[i],以空格为分割字符串；
简单题，求N个字符串的最长公共后缀，思路：以第一个字符串为基准，遍历另外N-1个字符串，判断从后往前的同样位置字符是否相等；1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
string str[101];
int main()
{
int num;
cin>>num;
getchar();
for(int i=0;i<num;i++){
getline(cin,str[i]);
}
bool flag=false;
int res=0;
for(int i=0;i<str[0].length();i++){
char temp=str[0][str[0].length()-i-1];
for(int j=1;j<num;j++){
char x=str[j][str[j].length()-i-1];
if(x!=temp){
res=i;
flag=true;
break;
}
}
if(flag)break;
}
if(res==0&&flag)//bugcout<<"nai"<<endl;
else if(res==0){
for(int i=0;i<str[0].length();i++)cout<<str[0][i];
}
else
for(int i=str[0].length()-res;i<str[0].length();i++)cout<<str[0][i];
/* for(int i=0;i<num;i++){
cout<<str[i]<<endl;
}*/
return 0;
}1013:Hashing
Hash+平方探测法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
bool isPrime(int x)
{
if(x==1)return false;
if(x==2)return true;
int temp=sqrt(x);
for(int i=2;i<=temp;i++){
if(x%i==0)return false;
}
return true;
}
//找到比x大的最近一个质数
int Find_Prime(int x)
{
while(1){
if(isPrime(x))return x;
x++;
}
}
int main()
{
int MSize,N;
bool flag[10001];
int input[10001];
bool ff=false,fff=false;
memset(flag,0,sizeof(flag));
cin>>MSize>>N;
int table_size;
//if(MSize==1)table_size=2;
table_size=Find_Prime(MSize);
int num;
for(int i=0;i<N;i++){
cin>>input[i];
}
for(int i=0;i<N;i++){
int num=input[i];
int a=num%table_size;
if(ff)cout<<" ";
if(!flag[a]){
cout<<a;
flag[a]=1;
fff=true;
}
//平方探测法
else {
for(int x=1;x<table_size;x++){//bug
int t=(x*x+a)%table_size;
if(!flag[t]){
cout<<t;
fff=true;
flag[t]=1;
break;
}
}
}
if(!fff)cout<<"-";
ff=true;
fff=false;
}
return 0;
}1014:Total Sales of Supply Chain
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61#include <iostream>
#include <vector>
#include <stdio.h>
#include <math.h>
using namespace std;
double sum=0;
vector<vector<int> > tree;
int N;//结点总数
double P,r;//根结点的原始值，rate
int flag[100001];//标记子节点的产品值
void DFS(int index,int level)
{
//说明为叶子结点
//可结合产品数量计算金额
if(tree[index].size()==0){
//这儿存在bug，一个超时，一个错误
//改用pow函数即可
/*double t=r;
for(int k=0;k<level-1;k++){
t=r*t;
}*/
sum+=pow(r,level)*P*flag[index];
return;
}
for(int i=0;i<tree[index].size();i++){
DFS(tree[index][i],level+1);
}
}
int main()
{
scanf("%d %lf %lf",&N,&P,&r);
r=(double)1+r/100;
tree.resize(N);
int childnum;
//输入
for(int i=0;i<N;i++){
scanf("%d",&childnum);
if(childnum!=0){
int child;
//记录各个结点的子节点
for(int j=0;j<childnum;j++){
cin>>child;
tree[i].push_back(child);
}
}
else {
int products;
scanf("%d",&products);
flag[i]=products;
}
}
//DFS求出遍历所有路径
DFS(0,0);
printf("%.1lf",sum);
return 0;
}1015Graduate Admission
优先队列,pop(),push(),top(),没法遍历；
- 自定义优先级
struct cmp{
operator bool(int x,int y){return x>y;}
}
priority_queue<int,vector,cmp> - 结构体声明方式
struct node{
int x,y;
friend bool operator < (node a, node b)
{
return a.x > b.x; //结构体中，x小的优先级高
}
}
priority_queueq; 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int nums,schools,chs;//毕业人数<=40000，
//院校数<=100，
//志愿数<=5
vector<int>quotas;//院校招生限额
struct node
{
int index;
int GE;
int GT;
vector<int>choices;
}Students[40001];
vector<node>SchoolsStu[101];//院校招生学生
bool cmp(node a,node b)
{
//两个double！！！
double x=(double)(a.GE+a.GT)/2;
double y=(double)(b.GE+b.GT)/2;
if(x!=y)return x>y;
else return a.GE>b.GE;
}
bool cmp2(node a,node b)
{
return a.index<b.index;
}
bool isEqual(node a,node b)
{
//两个double！！！
double x=(double)(a.GE+a.GT)/2;
double y=(double)(b.GE+b.GT)/2;
if(x==y&&a.GE==b.GE)return true;
return false;
}
int main()
{
//输入
cin>>nums>>schools>>chs;
int quo;
for(int i=0;i<schools;i++){
cin>>quo;
quotas.push_back(quo);
}
for(int i=0;i<nums;i++){
Students[i].index=i;
Students[i].choices.resize(chs);
cin>>Students[i].GE>>Students[i].GT;
int temp;
for(int j=0;j<chs;j++){
cin>>temp;
Students[i].choices[j]=temp;
}
}
//计算
sort(Students,Students+nums,cmp);
for(int i=0;i<nums;i++){
for(int j=0;j<chs;j++){
int tempc=Students[i].choices[j];
if(quotas[tempc]>SchoolsStu[tempc].size()){
SchoolsStu[tempc].push_back(Students[i]);
break;
}
else {
//无需用循环！
//用循环复杂度极高，实际上只要对比新加入的最菜的那个学生即可
if(isEqual(SchoolsStu[tempc].back(),Students[i])){
SchoolsStu[tempc].push_back(Students[i]);
break;
}
}
}
}
//输出
/*cout<<"============================="<<endl;
for(int i=0;i<nums;i++){
cout<<Students[i].GE<<" "<<Students[i].GT<<" ";
for(int j=0;j<Students[i].choices.size();j++){
int xx=Students[i].choices[j];
cout<<xx<<" ";
}
cout<<endl;
}
cout<<"============================="<<endl;*/
for(int i=0;i<schools;i++){
//vector的排序方式
sort(SchoolsStu[i].begin(),SchoolsStu[i].end(),cmp2);
for(int j=0;j<SchoolsStu[i].size();j++){
if(j!=0)cout<<" ";
cout<<SchoolsStu[i][j].index;
}
cout<<endl;
}
return 0;
}
1021
一开始题目看错，用空间换取时间，出现段错误，因为数组越界；
使用了
1 | #include <iostream> |