1104 数学
题目大意： 已知一个正数序列， 求出它所有连续子序列元素之和。
思路： 经分析，第i个数，出现i*(n-i+1)次 。安排！
#include<iomanip>
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
double sum = 0;
for(int i=1;i<=n;i++){
double x;
cin>>x;
sum += x*i*(n-i+1);
}
cout.setf(ios::fixed);
cout<<fixed<<setprecision(2)<<sum<<endl;
return 0;
}
1105 逻辑题
题目大意： 经典矩阵填充问题。
- 将N个数按规则以不递增的顺序填充到矩阵中
- 第一个字符填充在左上角，然后按照顺时针 （ a clockwise spiral）的方式填充 。
- 矩阵m行n列，找到m和n，使得m*n == N ，且m>=n, 且m-n是最小值
思路： 将序列排序之后，按照圈数挨个排就好了。
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
bool cmp(int a, int b){
return a>=b;
}
int main(){
int N;
cin>>N;
vector<int> v(N);
for(int i=0;i<N;i++){
cin>>v[i];
}
sort(v.begin(), v.end(), cmp);
int n, m;
for(m = ceil(sqrt(N)); m<=N; m++){
if(N%m == 0){
n = N/m;
break;
}
}
//cout<<m<<" "<<n;
vector< vector<int> > ans(m);
for(int i=0;i<m;i++){
ans[i].resize(n);
}
int count = 0;
int quan = 0;
while(count<N){
for(int j = quan;j<n-quan && count<N;j++){
ans[quan][j] = v[count++];
}
for(int i = quan+1;i<m-quan && count<N;i++){
ans[i][n-quan-1] = v[count++];
}
for(int j = n-quan-2;j>=quan && count<N;j--){
ans[m-quan-1][j] = v[count++];
}
for(int i = m-quan-2;i>quan && count<N;i--){
ans[i][quan] = v[count++];
}
quan++;
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(j!=0){
cout<<" ";
}
cout<<ans[i][j];
}
cout<<endl;
}
return 0;
}
1106 DFS
题目大意： 一个网络有零售商，经销商和供应商。每个人都将商品从供应商交到顾客手中。从一个 源供应商 开始， 每个人从一个供应商那里以P价格买入商品，以（1+r%）*P的价格卖出。只有零售商面对顾客销售。假设每个在供应链上的人（除了 源供应商 外）只有一个供应商。 给你这个供应链，求出顾客能得到的最低价格.
思路： 转化成求有向图中经过结点最少的路径。
#include<iostream>
#include<vector>
#include<iomanip>
using namespace std;
int n; //节点数，源节点编号为0， <=10^5
double p, r; //源供应商提供的价格，升价比率
vector< vector<int> > v;
int num = 0;
double minprice = 9999999;
void dfs(int index, double price){
if(v[index].size()==0){//说明是零售商
if(price < minprice){
minprice = price;
num = 1;
}else if(price == minprice){
num++;
}
}
//cout<<price<<endl;
for(int i=0;i<v[index].size();i++){
dfs(v[index][i], price*(1+r));
}
return;
}
int main(){
cin>>n>>p>>r;
r = r*0.01;
v.resize(n);
for(int i=0;i<n;i++){
int k;
cin>>k;
for(int j=0;j<k;j++){
int x;
cin>>x;
v[i].push_back(x);
}
}
dfs(0, p);
cout.setf(ios::fixed);
cout<<fixed<<setprecision(4)<<minprice<<" "<<num<<endl;
return 0;
}
1107 并查集
题目大意： 给每个人的爱好，将具有相同爱好的人合成一个集合。输出集合个数与每个集合的元素数量。
思路： 这题显然是并查集，但是做着做着突然发现，我将爱好当作元素构建并查集之后，他让我统计人的个数而不是爱好的个数。于是开了个一维数组ren，来存储每个人的第一个爱好。然后遍历ren数组，查找他那个爱好属于的集合，集合元素数量+1即可。还需要注意的一点是，爱好的编号不连续！因此可以用map<int, int>来构建并查集，也可以用一个一维数组+set代替。
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
int n; //<=1000
int table[1005];
int find(int x){
if(table[x] == -1) return x;
return table[x] = find(table[x]);
}
bool cmp(int a, int b){
return a >= b;
}
int main(){
cin>>n;
fill(table,table+1005, -1);
set<int> hobby; //爱好数不重复
int ren[1005];
for(int i=1;i<=n;i++){
int k,st,en;
scanf("%d:",&k);
cin>>st;
ren[i] = st;
hobby.insert(st);
for(int j=1;j<k;j++){
cin>>en;
hobby.insert(en);
if(find(st) != find(en)){
table[find(st)] = find(en);
}
st = en;
}
}
int count = 0;
set<int>::iterator iter;
for(iter = hobby.begin(); iter != hobby.end(); iter++){
if(table[*iter] == -1){
count++;
}
}
map<int, int> num; //用于统计每从的人数
for(int i=1;i<=n;i++){
num[find(ren[i])]++;
}
vector<int> ans;
map<int ,int>::iterator it;
for(it = num.begin(); it!=num.end();it++){
ans.push_back(it->second);
}
sort(ans.begin(), ans.end(), cmp);
cout<<count<<endl;
for(int i=0;i<ans.size();i++){
if(i!=0){
cout<<" ";
}
cout<<ans[i];
}
return 0;
}
