长乐培训Day1

t1 魔法照片

题目

【题目描述】

如果你看过《哈利·波特》，你就会知道魔法世界里的照片是很神奇的。也许是因为小魔法师佳佳长的太帅，很多人都找他要那种神奇的魔法照片，

而且还都要佳佳和他的mm的合照。那些照片可是非常珍贵的，他到底应该把照片给谁呢？

一共有n个人（以1—n编号）向佳佳要照片，而佳佳只能把照片给其中的k个人。佳佳按照与他们的关系好坏的程度给每个人赋予了一个初始权值w[i]。

然后将初始权值从大到小进行排序，每人就有了一个序号d[i]（取值同样是1—n）。按照这个序号对10取模的值将这些人分为10类。

也就是说定义每个人的类别序号c[i]的值为(d[i]-1) mod 10 +1，显然类别序号的取值为1—10。第i类的人将会额外得到e[i]的权值。

你需要做的就是求出加上额外权值以后，最终的权值最大的k个人，并输出他们的编号。在排序中，如果两人的w[i]相同，编号小的优先。

【输入格式】

第一行两个整数，分别是n和k。

第二行给出了10个正整数，分别是e[1]到e[10]。

第三行给出了n个正整数，第i个数表示编号为i的人的权值w[i]。

【输出格式】

输出仅一行为用空格隔开的k个整数，分别表示最终的w[i]从高到低的人的编号。

【数据规模】

对于50%的数据，n<=200；

对于100%的数据，n<=50 000，k<=2000，给出的所有正整数都不超过32767

解析

送分题。

先用结构体处理一下输入数据，再按初始权值从大到小排序，排完序后用序号d处理得到序号c，

再给每个人加上权值e，最后再按当前权值从大到小排列，依次输出前k个编号即可。

code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int read()    //快读 
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
struct rec{
    int num,w,d;
}ra[50001];
int n,k,e[11];
bool cmp(rec a,rec b)
{
    if(a.w==b.w) return a.num<b.num;
    return a.w>b.w;
}
int main()
{
    //freopen("mphone.in","r",stdin);
    //freopen("mphone.out","w",stdout);
    n=read(),k=read();
    for(int i=1;i<=10;i++) e[i]=read();
    for(int i=1;i<=n;i++)
    {
        ra[i].w=read();
        ra[i].num=i;
    }
    sort(ra+1,ra+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        ra[i].d=(i-1)%10+1;
        ra[i].w+=e[ra[i].d];
    }
    sort(ra+1,ra+n+1,cmp);
    for(int i=1;i<=k;i++) cout<<ra[i].num<<" ";
    return 0;
    //fclose(stdin);
    //fclose(stdout);
}

 

 

 

 

 

 

 

 

t2 个人所得税

题目

【题目描述】

某国个人所得税法规定，普通公民的主要应纳税收入项目及纳税金额如下：工资、薪金所得。按月计算征税，

以每月收入额减去费用800元后的余额作为该月应纳税所得额，税率如下表所示：

级数	月应纳税所得额	税率（%）
1	不超过500元的	5
2	超过500元~2000元的部分	10
3	超过2000元~5000元的部分	15
4	超过5000元~20000元的部分	20
5	超过20000元~40000元的部分	25
6	超过40000元~60000元的部分	30
7	超过60000元~80000元的部分	35
8	超过80000元~100000元的部分	40
9	超过100000元的部分	45

一次性劳动报酬所得。按次计算征税，每次不超过4000元的，减去费用800元；4000元以上的，减去20%的费用；余额为应纳税所得额。征税税率如下表所示：

级数	每次应纳税所得额	税率（%）
1	不超过20000元的部分	20
2	超过20000元~50000元的部分	30
3	超过50000元的部分	40

由上面可以看出，个人工资、薪金及一次性劳动报酬所得都是按照超额累进税率来征税的。超额累进税率将应纳税所得额按数额大小分成若干等级，

每一等级规定一个税率，税率依次提高，但每一纳税人的的应纳税所得额依照所属等级同时适用几个税率分别计算，将计算结果相加后的总额作为应纳税款。

例如，某人某月工资总额为3800元，减去800元后，应纳税所得额为3000元。其中1级500元，2级1500元，3级1000元，税率分别为5%、10%、15%，

应纳税总额为500*5%+1500*10%+1000*15%=325（元）。

现在需要你编一程序，根据该国某公司的所有职员一年内的各项收入信息（收入项目、收入时间、收入金额）计算该公司所有职员这一年应交纳的个人所得税总额。

【输入格式】

输入文件的第一行为一个正整数m，表示该公司的职员总数（职员编号依次为1,2,…,m）。接下来的各行每行表示一年内某一个职员的一项收入信息。具体格式如下：

工资、薪金收入信息：pay 职员编号 收入时间 收入金额

一次性劳务报酬收入信息：income 职员编号 收入时间 收入金额

其中，收入时间格式为：mm/dd，mm表示月份，dd表示日期；收入金额是一个正整数（单位：元），并假设每人每项收入金额小于100万元。

输入文件以字符“#”表示结束。输入文件中同一行相邻两项之间用一个或多个空格隔开。

【输出格式】

输出文件只有一个正数p，保留两位小数。p表示该公司所有职员一年内应交纳的个人所得税总额（单位：元）

【数据规模】

m<=50000;1<=mm<=12;1<=dd<=31

解析

水题，直接模拟即可。

开一个w1[i][j]数组表示i号职员在第j月总共领了多少工资，注意月工资是按月结算，必须合在一起算，分开就错了；

一次性工资直接计算就可以了。要注意税率及应纳税所得额之间的运算，不要弄错了。

非常坑爹的是，'/'是整除，用月工资小于等于500元的举例，不能写“w*5/100”这种形式（我因为这样少了90分qaq），而是要写“w*0.05”这种形式。

code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int read()    //快读 
{
    int sum=0,b=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') b=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        sum=(sum<<1)+(sum<<3)+ch-'0';
        ch=getchar();
    }
    return sum*b;
}
int m,n,w,w1[50001][13];
double ans;
string s,ss;
int main()
{
    //freopen("tax.in","r",stdin);
    //freopen("tax.out","w",stdout);
    memset(w1,0,sizeof(w1));
    m=read();
    cin>>s;
    while(s[0]!='#')
    {
        n=read();
        cin>>ss;
        int th=0;
        for(int i=0;i<s.size();i++)
        {
            if(ss[i]=='/') break;
            th=(th<<1)+(th<<3)+ss[i]-'0';
        }
        w=read();
        if(s[0]=='p') w1[n][th]+=w;
        else    //一次性 
        {
            double w2;
            if(w<=4000) w2=w-800;
            else w2=(double)(w*0.8);
            if(w2>0&&w2<=20000) ans+=w2*0.2;
            else if(w2>0)
            {
                ans+=4000;
                if(w2<=50000) ans+=(w2-20000)*0.3;
                else
                {
                    ans+=9000;
                    ans+=(w2-50000)*0.4;
                }
            }
        }
        cin>>s;
    }
    for(int i=1;i<=m;i++)    //每月 
        for(int j=1;j<=12;j++)
        {
            if(w1[i][j]!=0)
            {
                double w2=(double)(w1[i][j]-800);
                if(w2>0&&w2<=500) ans+=w2*0.05;
                else if(w2>0)
                {
                    ans+=25;
                    if(w2<=2000) ans+=(w2-500)*0.1;
                    else
                    {
                        ans+=150;
                        if(w2<=5000) ans+=(w2-2000)*0.15;
                        else
                        {
                            ans+=450;
                            if(w2<=20000) ans+=(w2-5000)*0.2;
                            else
                            {
                                ans+=3000;
                                if(w2<=40000) ans+=(w2-20000)*0.25;
                                else
                                {
                                    ans+=5000;
                                    if(w2<=60000) ans+=(w2-40000)*0.3;
                                    else
                                    {
                                        ans+=6000;
                                        if(w2<=80000) ans+=(w2-60000)*0.35;
                                        else
                                        {
                                            ans+=7000;
                                            if(w2<=100000) ans+=(w2-80000)*0.4;
                                            else
                                            {
                                                ans+=8000;
                                                ans+=(w2-100000)*0.45;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    printf("%.2lf",ans);
    return 0;
    //fclose(stdin);
    //fclose(stdout);
}

 

 

 

 

 

 

t3 最大子段和

题目

【题目描述】

给出一个首尾相连的循环序列，从中找出连续的一段，使得该段中的数和最大。

【输入格式】

第一行一个整数 n，表示有 n 个数。 第二行有 n 个整数，每个数的绝对值不超过 100000. 

【输出格式】

一个正整数，表示最大子段和。

【数据规模】

 1<=n<=100000

解析

这里说一个玄学算法（其实不然），因为序列是环状的，所以有最大连续子段和有两种情况：

1、前缀和：用f1数组与max1数组处理；

2、前缀和加后缀和：前缀同上，后缀用f2数组与max2数组处理。

开始的时候直接暴力求前缀和maxn1（第一种情况）；

然后求前缀和与后缀和，累加得到maxn2（第二种情况）。

最后输出max(maxn1,maxn2)即可。

code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int read()//快读 
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
const int n=100001;
int n,a[n];
long long temp,f1[n],f2[n],maxn1=-2147483647,maxn2=-2147483647,max1[n],max2[n];
int main()
{
    //freopen("maxsum.in","r",stdin);
    //freopen("maxsum.out","w",stdout);
    memset(max1,-0x7f7f7f7f,sizeof(max1));
    memset(max2,-0x7f7f7f7f,sizeof(max2));//极小值 
    n=read();
    for(int i=1;i<=n;i++)//前缀和 
    {
        a[i]=read();
        temp+=a[i];
        maxn1=max(maxn1,temp);
        if(temp<0) temp=0;
    }
    for(int i=1;i<=n;i++)//前缀和加后缀和 
    {
        f1[i]=f1[i-1]+a[i];
        max1[i]=max(max1[i-1],f1[i]);
    }
    for(int i=n;i>=1;i--)
    {
        f2[i]=f2[i+1]+a[i];
        max2[i]=max(max2[i+1],f2[i]);
    }
    for(int i=1;i<=n;i++) maxn2=max(maxn2,max1[i]+max2[i+1]);
    cout<<max(maxn1,maxn2);
    return 0;
    //fclose(stdin);
    //fclose(stdout);
}

 

 

 

 

 

 

 

t4 最小差值生成树

题目

【题目描述】

给定一个无向图，求它的一棵生成树，使得生成树中的最大边权与最小边权 的差最小，输出其最小差值。

【输入格式】

第一行两个整数 n，m,分别表示点数和边数。接下来m 行，第i+1行包含三个整数 xi,yi,di，

表示有一条边 连接 xi 和 yi，距离为 di。保证图是连通的，两个点之间最多只有一条边。

【输出格式】

包含一行，表示最小差值生成树的最大边与最小边的差值。 

【数据规模】

2<n<=200，m<=5000，0<xi<=n，0<yi<=n，0<di<=10^8

解析

这题和最小生成树原理相同，所以用kruskal是没有问题的，只需要把最小改成最小差值即可。

先把所有边按边权从小到大排序，再从所有边中任意选取一条边作为边权最小的边，

然后一条一条边往下循环，可以接上就接上，直到接完（即接的边数=n），最后比较最小差值就行了。

code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int read()//快读 
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
struct rec{
    int x,y;
    long long d;
}edge[5001];
int n,m,fa[201],temp,f1,f2;
long long minn=0x7f7f7f7f,maxn;
bool cmp(rec a,rec b)
{
    return a.d<b.d;
}
void clear()//修改回初始值 
{
    for(int i=1;i<=n;i++) fa[i]=i;
}
int get(int x)//找祖先 
{
    return fa[x]==x?x:fa[x]=get(fa[x]);
}
void kruskal()
{
    sort(edge+1,edge+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        maxn=edge[i].d;//把edge[i].d作为最小边权 
        temp=1;
        clear();
        fa[edge[i].x]=edge[i].y;
        for(int j=i+1;j<=m;j++)
        {
            f1=get(edge[j].x),f2=get(edge[j].y);
            if(f1!=f2)//祖先不同，连接 
            {
                fa[f1]=f2;
                temp++;
                maxn=max(maxn,edge[j].d);//最大边权 
            }
            if(temp==n-1) break;//接完了 
        }
        if(temp==n-1) minn=min(minn,maxn-edge[i].d);//计算最小差值 
    }
}
int main()
{
    //freopen("mdt.in","r",stdin);
    //freopen("mdt.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;i++) edge[i].x=read(),edge[i].y=read(),edge[i].d=read();
    kruskal();
    cout<<minn;
    return 0;
    //fclose(stdin);
    //fclose(stdout);
}