2020

A. ⽃⽜

给定五个 0~9 范围内的整数 a1, a2, a3, a4, a5。
如果能从五个整数中选出三个并且这三个整数的和为10 的倍数（包括 0），
那么这五个整数的权值即为剩下两个没被选出来的整数的和对 10 取余的结果，显然如果有多个三元组满⾜和是 10 的倍数，剩下两个数之和对 10 取余的结果都是相同的；
如果选不出这样三个整数，则这五个整数的权值为 -1。
现在给定 T 组数据，每组数据包含五个 0~9 范围内的整数，分别求这 T 组数据中五个整数的权值。

• 【输⼊格式】
  第⼀⾏⼀个整数 T (1<=T<=1000)，表⽰数据组数。
  接下来 T ⾏，每⾏ 5 个 0~9 的整数，表⽰⼀组数据。
  【输出格式】
  输出 T ⾏，每⾏⼀个整数，表⽰每组数据中五个整数的权值。

【样例输⼊】
4
1 0 0 1 0
1 0 0 8 6
3 4 5 6 7
4 5 6 7 8
【样例输出】
2
-1
-1
0

**#include<iostream>

using namespace std;
int a[4],sum2,sum3,sum5,power;

void dfs(int x,int y)
{
    sum2=a[x]+a[y];
    sum3=sum5-sum2;

    if(!(sum3%10) ) 
    {
        power=sum2%10;
        return;
    }
    else 
    {
        if(y==4) 
        {
            if(x!=3)

            {
                dfs(x+1,x+2);
            }
            else
            {
                power=-1;
                return;
            }
        }
        else
        {
            dfs(x,y+1);
        }
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4];
        sum5=a[0]+a[1]+a[2]+a[3]+a[4];
        dfs(0,1);  
        cout<<power<<endl;
    }
    return 0;
}

B. 打地⿏
给定 n 个整数 a1, a2, …, an 和⼀个 d，你需要选出若⼲个整数，使得将这些整数从⼩到⼤排好序之
后，任意两个相邻的数之差都不⼩于给定的 d，问最多能选多少个数出来。

【输⼊格式】
第⼀⾏两个整数 n,d (1<=n<=10^5, 0<=d<=10^9)，分别表⽰整数个数和相邻整数差的下界。
第⼆⾏ n 个整数 a1, a2, …, an (1<=ai<=10^9, 1<=i<=n)，表⽰给定的 n 个整数。
【输出格式】
仅⼀⾏⼀个整数，表⽰答案。
【样例输⼊】
6 2
1 4 2 8 5 7
【样例输出】
3

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N=1e5+10;

int n,d;//整数个数和相邻整数差的下界
int p[N];
unordered_map<int ,int>  note;

int pre(int i)
{

    int res=i-1;
    while(p[i]-p[res]<d&&res>=0) res--;
    if(res<0) return 0;
    return p[res];
}
int main()
{
    cin>>n>>d;
    for(int i=0;i<n;i++)  cin>>p[i];

    sort(p,p+n);

    note[0]=0;
    note[p[0]]=1;

   ** for(int i=1;i<n;i++)
    {
        if(p[i]-p[i-1]>=d) 
           note[p[i]]=1+note[p[i-1]];
        else 
           note[p[i]]=max(1+note[pre(i)],note[p[i-1]]);
    }**
    cout<<note[p[n-1]]<<endl;
    return 0;
}
//关键就是写出状态转义方程

C. 排队打饭
下课了，有 n 位同学陆续赶到⻝堂进⾏排队打饭，其中第 i 位同学的到达时间为 ai，打饭耗时为 ti，
等待时间上限为 bi，即如果其在第 ai+bi 秒的时刻仍然没有轮到他开始打饭，那么他将离开打饭队列
另寻吃饭的地⽅。问每位同学的开始打饭时间，或者指出其提前离开了队伍（如果这样则输出 -1）。
【输⼊格式】
第⼀⾏⼀个整数 n (1<=n<=10^5)，表⽰来打饭的同学数量。
接下来 n ⾏，每⾏三个整数 ai,ti,bi (1<=ai,ti,bi<=10^9, 1<=i<=n)，分别表⽰每位同学的到达时间、打
饭耗时、等待时间上限。
保证 a1<a2<…<an
【输出格式】
⼀⾏ n 个整数，表⽰每位同学的开始打饭时间或者 -1（如果该同学提前离开了队伍）。
【样例输⼊】
4
1 3 3
2 2 2
3 9 1
4 3 2
【样例输出】
C. 排队打饭
1 4 -1 6

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n;
struct student
{
    int arrive_time;
    int lasting_time;
    int limit_time;
    bool operator<(const student &t) const
    {
        return arrive_time<t.arrive_time;
    }
};
vector<student>  students;
priority_queue<int,vector<int>,greater<int>>  que ;

int main()
{
    cin>>n;
    while(n--)
    {
        int arrive_time,lasting_time,limit_time;
        cin>>arrive_time>>lasting_time>>limit_time;
        //lasting_time=min(lasting_time,limit_time);
        students.push_back({arrive_time,lasting_time,limit_time});
    }

    sort(students.begin(),students.end());
    que.push(1);
    for(auto &student:students)
    {
        auto arrive_time=student.arrive_time;
        auto lasting_time=student.lasting_time;
        auto limit_time=student.limit_time;
        int w=que.top();//小根堆存的是 结束时间点
        if(arrive_time+limit_time<w)   
        {
            cout<<-1<<endl;
            continue;
        }
        que.pop();
        cout<<w<<endl;

        que.push(w+lasting_time);
    }
    return 0;
}

D.⼆叉搜索树
【输出格式】
⼀⾏ n 个整数，其中第 i 个整数 ai 表⽰元素 i 对应节点的⽗亲节点的元素。特别地，根节点的⽗亲节
点元素视为 0。
【样例输⼊】
5
2 3 5 1 4
【样例输出】
2 0 2 5 3
【样例解释】
最后建出来的⼆叉搜索树如下：
2
/ \
1 3
\
5
/
4
1 的⽗亲为 2，2 为根结点，所以⽗亲为 0，3 的⽗亲为 2，4 的⽗亲为 5，5 的⽗亲为 3。
【时空限制】
5000ms，256MB

#include<iostream>
using namespace std;
const int N=1e5+10;
int l[N],r[N],fa[N];
int n;
int root;
void insert(int i,int root)
{
    if(i<root)  
    {
        if(!l[root])
        {
        l[root]=i;
        fa[i]=root;
        return ;
        }
        else
        {
            insert(i,l[root]);
        }
    }
    else if(i>root)
    {
        if(!r[root])
        {
        r[root]=i;
        fa[i]=root;
        return ;
        }
        else 
        {
            insert(i,r[root]);
        }
    }
}
int main()
{
    cin>>n;
    cin>>root;
    fa[root]=0;
    for(int i=1;i<n;i++)
    {
        int t;
        cin>>t;
        insert(t,root);
    }

    for(int i=1;i<=n;i++)
      cout<<fa[i]<<' ';
      cout<<endl;

    return 0;
}

2019.
输入一个 yyyymmdd 格式的时间，如 20190318，计算与 20190205 相差的天数，
取绝对值，所有输入在 19000101 和 21000101 之间。
样例输
入：20190208
输出：3
给定一个数组及其大小，数组元素在[-10^6，10^6]，元素个数最多 10^6 个。
输出最大的连续子序列和，题目保证最后结果为正数。

给定二叉树的节点总数 n，输出二叉树形态总数，n<= 1000
样例输入：3
输出：5

#include<iostream>
using namespace std;
const int N=1e5+10;
int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31,};
int s[13];

int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=13;i++)  
       s[i]=s[i-1]+m[i];
    int year=t/10000;
    int month=(t%10000)/100;
    int day=t%100;

   int res=0;
    if(year>=2019)
    {
        res+=(year-2019)*365;
        for(int i=2019;i<year;i++)
            if(i%100&&i%4==0||i%400==0)
               res+=1;

        res+=(day+s[month-1]);
        if(year%100&&year%4==0||year%400==0)
        {
            if(month>2)  res+=1;
        }

            cout<<res-s[1]-5<<endl;
    }
     else
    {
        res+=(2019-year)*365;
        for(int i=year;i<2019;i++)
           if(i%100&&i%4==0||i%400==0)  res+=1;

        res+=s[1]+5;
        res-=(s[month-1]+day);
        if(year%100&&year%4==0||year%400==0)
          if(month>2)  res-=1;

        cout<<res<<endl;
    }
    return 0;
}