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;
}