寒假刷题第15天

PTA甲级

1101 Quick Sort

求partition的位置，partition位置一定是排好的序列与原序列相等的位置，并且对应原数组的位置左右两边左边小右边大

#include<iostream>
#include<algorithm>
#include<vector>using namespace std;const int N = 1e5 + 10;
int n;
vector<int>v(N) , v1(N);int main()
{cin >> n;for(int i = 0;i < n;i ++)cin >> v[i];v1 = v;sort(v.begin() , v.begin() + n);vector<int>res;int m = -1;for(int i = 0;i < n;i ++){if(v1[i] == v[i] && v1[i] > m) res.push_back(v[i]);m = max(m , v1[i]);}cout << res.size() << endl;for(int i = 0;i < res.size();i ++){if(i) cout << " ";cout << res[i];}cout << endl;return 0;
}

1106 Lowest Price in Supply Chain

这题很像之前的一道题，这省事出一样的题目

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<cstring>using namespace std;const int N = 1e5 + 10;
int n;
double p , r;
vector<int>v[N];
int retail[N];
map<double , int>res;void dfs(int u , int dep)
{double now = pow(1 + 0.01 * r , dep) * p;if(retail[u] == u) res[now] ++;for(auto i : v[u])dfs(i , dep + 1);
}int main()
{memset(retail , -1 , sizeof retail);cin >> n >> p >> r;for(int i = 0;i < n;i ++){int k;cin >> k;if(!k) retail[i] = i;else {for(int j = 0;j < k;j ++){int x;cin >> x;v[i].push_back(x);}}}dfs(0 , 0);printf("%.4lf %d" , res.begin() -> first , res.begin() -> second);return 0;
}

1107 Social Clusters

是对人进行聚类

#include<iostream>
#include<vector>
#include<set>
#include<unordered_map>
#include<map>
#include<algorithm>
#include<cstring>using namespace std;const int N = 1010;
int n , p[N];
unordered_map<int , int>mp;
vector<int>res;
vector<int>hobby[N];int find(int x)
{if(p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{cin >> n;for(int i = 1;i <= n;i ++)p[i] = i;for(int i = 1;i <= n;i ++){int k;scanf("%d:" , &k);int last = -1;for(int j = 0;j < k;j ++){int x;cin >> x;hobby[x].push_back(i);}}for(int i = 1;i < N;i ++){for(int j = 1;j  < hobby[i].size();j ++){int pa = find(hobby[i][j]) , pb = find(hobby[i][j - 1]);if(pa != pb) p[pa] = pb;}}for(int i = 1;i <= n;i ++)mp[find(i)] ++;cout << mp.size() << endl;for(auto i : mp)res.push_back(i.second);sort(res.begin() , res.end());reverse(res.begin() , res.end());for(int i = 0;i < res.size();i ++){if(i) cout << " ";cout << res[i];}return 0;
}

1103 Integer Factorization

dfs，注意dfs不用循环就行，pow的计算拿到dfs外就行

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>using namespace std;const int N = 500;
int n , p , k;
vector<int>res;
int limit , sumfac;
int pows[N];void getpow()
{for(int i = 1;i <= limit;i ++)pows[i] = pow(i , p);
}void dfs(vector<int>&temp , int u , int total , int factotal)
{if(u <= 0) return ;if(total > n) return ;if(temp.size() > k) return ;if(total == n && temp.size() == k){if(!res.size()) res = temp , sumfac = factotal;else {if(sumfac < factotal){res = temp;sumfac = factotal;}else if(sumfac == factotal){if(res < temp) res = temp;}}return ;}// 不使用循环即可// for(int i = limit;i >= 1;i --)// {//     temp.push_back(i);//     dfs(temp , total + pows[i] , factotal + i);//     temp.pop_back();// }temp.push_back(u);dfs(temp , u , total + pows[u] , factotal + u);temp.pop_back();dfs(temp , u - 1 , total , factotal);
}int main()
{scanf("%d %d %d" ,&n ,&k ,&p);limit = pow(n , 1.0 / p);getpow();vector<int>temp;dfs(temp , limit , 0 , 0);if(res.size()){printf("%d = " , n);for(int i = 0;i < res.size();i ++){if(i) printf(" + ");printf("%d^%d" , res[i] , p);}}else puts("Impossible");return 0;
}