HPU积分赛 （Day34）

分数

Description:
Anxdada有一个长度为n的非负整数序列a1, a2, ..., an.
他想知道能否将这个序列划分成奇数个子序列,其中每个子序列的第一个数字是奇数,最后一个数字也是奇数,而且这个子序列的长度也是奇数

子序列就是原序列的一个连续的片段. 例如,{3, 4, 5}和{1}都是{1, 2, 3, 4, 5, 6}的子序列,但是{1, 2, 4}和{7}并不是{1, 2, 3, 4, 5, 6}的子序列

Input
第一行包含一个正整数n(1 ≤ n ≤ 100) — 原序列的长度.
第二行包含n个非负整数a1, a2, ..., an (0 ≤ ai ≤ 100) — 这个序列的元素.

Output
如果原序列可以按要求进行划分就输出"Yes",否则输出"No".

Simple Input 1
3
1 3 5
Simple Output 1
Yes
Simple Input 2
5
1 0 1 5 1
Simple Output 2
Yes
Simple Input 3
3
4 3 1
Simple Output 3
No
Simple Input 4
4
3 9 9 3
Simple Output 4
No
Note
在第一个样例中,把原序列划分为1个子序列: {1, 3, 5}满足题目的要求.
在第二个样例中,把原序列划分为3个子序列: {1, 0, 1}, {5}, {1}.
在第三个样例中,其中一个子序列一定以4开头,但是4是偶数,因此不符合题意.
在第四个样例中,把原序列划分为2个部分:{3, 9, 9},{3},但是2是偶数不满足题意.
Problem solving:
这道题的意思就是给你一个序列，问你能不能把它分成满足以下条件的几部分

1. 分出来的这一部分的长为奇数。
2. 分出来的这一部分的首尾的数都是奇数。
3. 总共分出来的部分数是奇数。

首先如果这个序列的长度是一个偶数，那么他就不可能同时满足1跟3，因为奇数乘奇数还是奇数。
然后我们只需要再判断一下这个序列的首项和尾项是不是奇数。因为如果这两个有一个是偶数，那就不可能会满足题目中的要求。反之一定可以。
Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int main()
{
    int n,a[maxn],flag=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    if(n%2==0)    flag=1;
    if(a[1]%2==0||a[n]%2==0)    flag=1;
    cout<<(flag==1?"No":"Yes")<<endl;
}

搜索漂亮的整数

Description:
小红现在有两个列表的数字.

如果一个十进制数至少有一个数字来自列表一且至少有一个数字来自列表二，那么将这个数字叫做小红数，请你找出最小的正小红数

Input
第一行包括两个整数 n 和 m (1 ≤ n, m ≤ 9) — 分别代表第一个和第二个列表的长度。

第二行包含 n 个不同的数字 a1, a2, ..., an (1 ≤ ai ≤ 9) 代表列表一中的元素。

第三行包含 m 个不同的数字 b1, b2, ..., bm (1 ≤ bi ≤ 9) 代表列表二中的元素

Output
输出最小正小红数.

Example
Input
2 3
4 2
5 7 6
Output
25
Input
8 8
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
Output
1
Problem solving:
这道题的意思就是给你两组序列，让你从找到一个数，这个数的每一位都是这两组序列中的某一个数。问你这个数最小是多少。
考虑两种情况

1. 两个序列中有相等的数字出现，那么最小的数就是同时出现的数字里面的最小的那个。
2. 没有相等的，就拿出来两个序列中的最小的数i,j，让它们两个之间较大的做个位，较小的做十位。即ans=max(i,j)+min(i,j)*10。

Code:

#include<bits/stdc++.h>
using namespace std;
int a[12],b[12];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)    cin>>a[i];
    for(int i=0;i<m;i++)    cin>>b[i];
    sort(a,a+n);
    sort(b,b+m);
    int ans=-1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(a[i]==b[j])
            {
                ans=a[i];
                break;
            }
        }
        if(ans!=-1)    break;
    }
    if(ans==-1)
    {
        ans=min(a[0],b[0])*10+max(a[0],b[0]);
    }
    cout<<ans<<endl;
}

hzy 和zsl 的生存挑战

Description:
zsl 和hzy 来到了臭臭城堡，打算挑战臭臭城堡的大魔王hyz，大魔王hyz设置了这样的一个挑战：

1. zsl 和hzy两个人各自来到一间密室，期间两人无法以任何形式交流
2. 大魔王hyz会随机在两个人的脑海里各发送一个数字，0或者是1
3. zsl 和 hzy 需要猜对这俩个数字才算通关，但是大魔王hyz觉得人生不能过于无敌，因此降低难度，只要两个人中有一个人答对就算是通关

现在大魔王hyz 给出的数字可能的情况有 00， 01， 10， 11 四种，请按上述枚举的顺序，计算所有情况下zsl 和hzy 通关的几率。（假设zsl 和 hzy 两个人都足够机智，能够选择出最优决策）
Input
(空)
Output
输出四个答案，每个答案后面跟随一个换行符并且保留两位小数位，分别对应00，01，10，11的情况下，zsl和hzy通关的几率
Sample Input
(空)
Sample Output
1.00
0.00
0.50
0.55 (输出仅做格式参考,不保证正确性)
Problem solving:
这道题没啥意思。
hzy和zsl都很聪明，所以只要他们一个人说0一个人说1就一定可以出去。直接输出4个1就行。
Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    puts("1.00");
    puts("1.00");
    puts("1.00");
    puts("1.00");
    return 0;
}

共享单车

Description:
学长自从上次被打了一顿之后,就想着讨好实验室的人。
于是他决定带着实验室的人出去玩。实验室一共有k个人,出去玩需要骑自行车。
一共有m家共享单车公司提供自行车,第i家共享单车公司提供的自行车信息用li,ri,ci,pi表示。
其中:
li,ri表示这家公司从接下来的第li天到ri天,提供共享单车.
ci表示这家公司在这些天每天提供的单车数目.
pi表示租用每辆车需要的单价.
现在学长想在接下来连续的n天,每天都带着实验室的k个人出去玩,要求出行时候每个人都尽可能能坐到单车,即每天都要租k辆车,当然如果某一天所有公司全部加起来都没有提供k辆车,那么就将所有车都租下,让剩下的一些人走路,否则如果够k辆就一定要租k辆.
请你输出学长最少需要花多少钱.
Input
输入的第一行为3个整数n,k,m(1<=n,k<=10^6,1<=m<=2*10^5).
接下来m行,每行4个整数li,ri,ci,pi(1<=li<=ri<=n,1<=ci,pi<=10^6).
Output
输出只有一行,表示学长最少需要花费的钱.
Examples
Input
5 7 3
1 4 5 3
1 3 5 2
2 5 10 1
Output
44
Input
7 13 5
2 3 10 7
3 5 10 10
1 2 10 6
4 5 10 9
3 4 10 8
Output
462
Problem solving:
暂无
Code:

最小值最大值

Description:
给出一个有n个整数的数组 a1, a2, ..., an 和一个整数k。你被要求把这个数组分成k 个非空的子段。 然后从每个k 个子段拿出最小值，再从这些最小值中拿出最大值。求这个最大值最大能为多少？

Input
第一行输入两个整数 n 和 k (1 ≤ k ≤ n ≤  1e5) — 数组a 的大小和要求分成子段的数目

第二行包含 n 整数 a1,  a2,  ...,  an ( - 1e9  ≤  ai ≤  1e9).

Output
输出答案——在你分离的每个子段中最小值中的最大值k

Example
Input
5 2
1 2 3 4 5
Output
5
Input
5 1
-4 -5 -3 -2 -1
Output
-5
Problem solving:
这道题很有意思。
他就是给你一组数，这组数有m个，问你分成m份的话，每一份的最小值中的最大值是多少。

看到了最小的最大我一开始以为是2分。但是check函数一直写不出来。再仔细一想发现这不就是个规律题吗。
分三种情况

1. 分成1份，此时的答案就是这组数中的最小值。
2. 分成2份，此时的答案就是这组数的开头跟结尾的最大值。这个不太好理解。因为分成两份，每一份都要取一个最小值，所以我们把两边的两个数单独分成一组来考虑，此时就已经是最优解了。这一点不太好解释（因为我当时是病急乱投医这样写的，现在发现还是挺有道理的——因为我们要求的是最小的最大，可以自己举几个例子，你就会发现这个的巧妙）
3. 除了前两种，此时的答案就是这组数中的最大值。因为当你可以分3份开始，你就可以把这组数中的最大值单独一个数分成一组，其他任意分。这时每组数的最小的最大值就是整组数中的最大值了。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6;
const ll inf =1e9+10;
ll a[maxn];
int main()
{
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
    }
    if(m==2)    cout<<max(a[0],a[n-1])<<endl;
    else
    {
        sort(a,a+n);
        if(m==1)    cout<<a[0]<<endl;
        else    cout<<a[n-1]<<endl;
    }
    return 0;
}

Ring

Description:
邓布利多教授正在帮助哈利摧毁魂器。当他怀疑一个魂器出现在那里时，他去了冈特沙克。他看到Marvolo Gaunt的戒指，并将其确定为魂器。虽然他摧毁了它，但仍然受到诅咒的影响。斯内普教授正在帮助邓布利多解除诅咒。为此，他想给Dumbledore提供他制作的药水x滴。

x的值被计算为给定p，q，r和阵列a1，a2，......的p·ai + q·aj + r·ak的最大值，使得1≤i≤j≤k≤n。帮助Snape找到x的值。请注意x的值可能是负数。

Input
第一行输入包含4个整数n，p，q，r（ - 1e9≤p，q，r≤1e9, 1≤n≤1e5）。

下一行输入包含n个空格分隔的整数a1，a2，... an（ - 1e9≤ai≤1e9）。

Output
输出p≤ai+ q·aj + r·ak的最大值，只要1≤i≤j≤k≤n即可得到。

Examples
Input
5 1 2 3
1 2 3 4 5
Output
30
Input
5 1 2 -3
-1 -2 -3 -4 -5
Output
12
Note
In the first sample case, we can take i = j = k = 5, thus making the answer as 1·5 + 2·5 + 3·5 = 30.

In second sample case, selecting i = j = 1 and k = 5 gives the answer 12.
Problem solving:
暂无
Code:

赛题分析

Description:
著名出题人小Q每次比赛后都会写一份《赛题分析》，包含比赛概况、每题的参考算法以及一些统计数值。

对于一道题来说，小Q会统计最短的验题人代码长度(Shortest judge solution)以及赛内参赛队伍最短的AC代码长度(Shortest team solution)。

统计验题人代码长度比较容易，因为验题人最多也不会超过20个。但是统计选手代码长度就不容易了，因为大赛区动辄三四百支队伍。

请写一个程序，帮助小Q统计最短代码长度。
Input
第一行包含一个正整数T(1≤T≤13)，表示赛题数量。

每道题第一行包含两个整数n,m(2≤n≤20,0≤m≤500)，分别表示验题人数量以及AC了该题的队伍数量。

第二行包含n个正整数a1,a2,...,an(50≤ai≤65536)，依次表示每个验题人的代码字节数。

第三行包含m个正整数b1,b2,...,bn(50≤bi≤65536)，依次表示每支AC队伍的代码字节数。若m=0则该行为空行。
Output
对于第i(1≤i≤T)道题，输出三行，第一行输出Problem x:，其中x=i+1000。

第二行输出Shortest judge solution: y bytes.，其中y表示最短的验题人代码字节数。

第三行输出Shortest team solution: z bytes.，其中z表示最短的选手代码字节数，若不存在请输出N/A。

注意：间隔都是一个空格。
Sample Input
2
3 2
3627 1460 5288
2365 2671
2 0
5510 7682
Sample Output
Problem 1001:
Shortest judge solution: 1460 bytes.
Shortest team solution: 2365 bytes.
Problem 1002:
Shortest judge solution: 5510 bytes.
Shortest team solution: N/A bytes.
Problem solving:
没啥好说的，sort就完事了。
我还PE了好几次。。。

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 505;
int a[maxn],b[maxn];
int main()
{
    int t,n,m;
    cin>>t;
    for(int l=1;l<=t;l++)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)    cin>>a[i];
        for(int i=0;i<m;i++)    cin>>b[i];
        sort(a,a+n),sort(b,b+m);
        printf("Problem %d:\n",l+1000);
        printf("Shortest judge solution: %d bytes.\n",a[0]);
        if(m)
        printf("Shortest team solution: %d bytes.\n",b[0]);
        else
        printf("Shortest team solution: N/A bytes.\n");
    }
}

差异的可分割性

Description:
现在有n个整数，在这n个数中找出k个数，保证这k个数中任意两个数差的绝对值可以被m整除。
Input
第一行输入三个整数n，k，m(2<=k<=n<=100000,1<=m<=100000)。
第二行包含n个整数a1，a2，...，  an（0 <= ai <= 10^9 )。
Output
如果不存在这样的k个数，输出"No"；
否则输出"Yes"后，在下一行输出这k个数,数与数之间用空格隔开。 (存在多种情况，输出任意一种)。
Example
Input
3 2 3
1 8 4
Output
Yes
1 4
Input
3 3 3
1 8 4
Output
No
Input
4 3 5
2 7 7 7
Output
Yes
2 7 7
Problem solving:
这道题也挺有意思的。输入的n代表有n个数，k，m就是问你在n个数中能不能找到k个数，使这k个数任意两个的差都可以被m整除。如果可以的话还要输出一种情况。

这道题我一开始是一点思路没有，暴力tle了几发之后想到了用取模来写。因为如果两个数的差对能被一个数m整除。那么这两个数对m的模一定是相等的。

但是还需要输出情况，所以我用了两个数组来存，一个存原始的，一个用结构体来存，存进去它取模之后的结果以及取模之前的序号，其实现在一想也可以直接存上它原来的值。

然后就存进去之后排一下序，所以这时候如果相等的个数大于k的话，就说明可以，然后再用结构体里面存的数据输出就行了。
Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6;
int a[maxn];
struct node{
    int d,id;
}p[maxn];
bool cmp(node a,node b)
{
    return a.d<b.d;
}
int main()
{
    int n,k,m,flag=0;
    scanf("%d %d %d",&n,&k,&m);
    for(int i=0;i<n;i++)    scanf("%d",&a[i]);
    for(int i=0;i<n;i++)
    {
        p[i].d=a[i]%m;
        p[i].id=i;
    }
    sort(p,p+n,cmp);
    int mid=p[0].d,cnt=1;
    for(int i=1;i<n;i++)
    {
        if(p[i].d==mid)
        {
            cnt++;
        }
        else
        {
            mid=p[i].d;
            cnt=1;
        }
        if(cnt==k)
        {
            puts("Yes");
            for(int j=i;j>i-k;j--)
            {
                printf("%d ",a[p[j].id]);
            }
            return 0;
        }
    }
    puts("No");
    return 0;
}

扫雷

Description:
扫雷游戏是晨晨和小璐特别喜欢的智力游戏，她俩最近沉迷其中无法自拔。
该游戏的界面是一个矩阵，矩阵中有些格子中有一个地雷，其余格子中没有地雷。 游戏中，格子可能处于己知和未知的状态。如果一个己知的格子中没有地雷，那么该 格子上会写有一个一位数，表示与这个格子八连通相邻的格子中地雷总的数量。
现在，晨晨和小璐在一个3行N列（均从1开始用连续正整数编号）的矩阵中进 行游戏，在这个矩阵中，第2行的格子全部是己知的，并且其中均没有地雷；而另外 两行中是未知的，并且其中的地雷总数量也是未知的。
晨晨和小璐想知道，第1行和第3行有多少种合法的埋放地雷的方案。
Input
包含多组测试数据，第一行一个正整数T，表示数据组数。
每组数据由一行仅由数字组成的长度为N的非空字符串组成，表示矩阵有3行N 列，字符串的第i个数字字符表示矩阵中第2行第i个格子中的数字。
保证字符串长度N <= 10000，数据组数<= 100。
Output
每行仅一个数字，表示安放地雷的方案数mod100,000,007的结果。
Sample Input
2
22
000
Sample Output
6
1
Problem solving:
暂无
Code:

派对柠檬水

Description:
点完菜，他们发现好像觉得少了点什么？

想想马上就要回老家了某不愿透露姓名的林姓学长再次却陷入了沉思。。。。。。。。。

他默默的去前台打算点几瓶二锅头。

他发现菜单上有n 种不同毫升的酒. 第 i 种有2i - 1 毫升价格为ci 元.商店中每种类型的酒的数量可以被认为是无限的。.

他对于自己能喝多少还是有点B-Tree的，但是他认为喝酒一定要喝的尽兴，于是他打算买至少L 毫升，但是又要花最少的钱，现在他想知道他最少需要花多少钱

Input
第一行输入两个整数 n and L (1 ≤ n ≤ 30; 1 ≤ L ≤ 1e9) — 代表有n总酒和需要买的数量

第二行输入 n个整数s c1, c2, ..., cn (1 ≤ ci ≤ 1e9) —代表第i种酒需要的钱数

Output
输出一个整数，他买至少L 了毫升，所花的最少钱数

Example
Input
4 12
20 30 70 90
Output
150
Input
4 3
10000 1000 100 10
Output
10
Input
4 3
10 100 1000 10000
Output
30
Input
5 787787787
123456789 234567890 345678901 456789012 987654321
Output
44981600785557577
Note
在第一个例子中，你应该花90元购买一个8毫升的，花60元的购买两个2毫升的。总共你会得到12毫升只要150元。

在第二个例子中，即使你只需要3毫升，但是购买一个10元8毫升的便宜一些。

在第三个例子中，最好10元购买三个1毫升的。
Problem solving:
暂无
Code:

Count

Description:
Farmer John有n头奶牛.
某天奶牛想要数一数有多少头奶牛,以一种特殊的方式:
第一头奶牛为1号,第二头奶牛为2号,第三头奶牛之后,假如当前奶牛是第n头,那么他的编号就是2倍的第n-2头奶牛的编号加上第n-1头奶牛的编号再加上自己当前的n的三次方为自己的编号.
现在Farmer John想知道,第n头奶牛的编号是多少,估计答案会很大,你只要输出答案对于123456789取模.
Input
第一行输入一个T,表示有T组样例
接下来T行,每行有一个正整数n,表示有n头奶牛 (n>=3)
其中，T=1e4,n<=1e18
Output
共T行,每行一个正整数表示所求的答案
Sample Input
5
3
6
9
12
15
Sample Output
31
700
7486
64651
527023
Problem solving:
这个题就是给了你一个递推式
f(n)=f(n-1)+2*f(n-2)+n*n*n
然后告诉你f(1)=1,f(2)=2。让你求第n项的值，n的范围比较大，所以得用到矩阵快速幂，构建出来常熟矩阵和系数矩阵就行了（这是之前学矩快的时候的一道原题

难点就是构建n的三次方那里。
构建的矩阵看代码注释吧（还有别忘了给用到的矩阵先初始化为0）

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 123456789;
struct node{
    ll a[10][10];
};
node mul(node a,node b)
{
    node ans;
    memset(ans.a,0,sizeof(ans.a));
    for(ll i=0;i<6;i++)
    {
        for(ll j=0;j<6;j++)
        {
            for(ll k=0;k<6;k++)
            {
                ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
            }
        }
    }
    return ans;
}
node poww(node a,ll b)
{
    node mid;
    memset(mid.a,0,sizeof(mid.a));
    for(ll i=0;i<6;i++)    mid.a[i][i]=1;
    while(b)
    {
        if(b&1)    mid=mul(mid,a);
        a=mul(a,a);
        b/=2;
    }
    return mid;
}
int main()
{
    ll n,t;
    cin>>n;
    node s,mid;
    memset(s.a,0,sizeof(s.a));
    memset(mid.a,0,sizeof(mid.a));
    s.a[0][0]=31;s.a[1][0]=2;s.a[2][0]=27;s.a[3][0]=9;s.a[4][0]=3;s.a[5][0]=1;//s是系数矩阵
    mid.a[0][0]=1;mid.a[0][1]=2;mid.a[0][2]=1;mid.a[0][3]=3;mid.a[0][4]=3;mid.a[0][5]=1;
    mid.a[1][0]=1;//mid是常数矩阵
    mid.a[2][2]=1;mid.a[2][3]=3;mid.a[2][4]=3;mid.a[2][5]=1;
    mid.a[3][3]=1;mid.a[3][4]=2;mid.a[3][5]=1;
    mid.a[4][4]=1;mid.a[4][5]=1;mid.a[5][5]=1;
    while(n--)
    {
        cin>>t;
        if(t==1)    puts("1");
        else if(t==2) puts("2");
        else if(t==3)    puts("31");
        else
        {
            node ans=poww(mid,t-3);
            ans=mul(ans,s);
            cout<<ans.a[0][0]<<endl;
        }
    }
}

诊断

Description:
Hao得了重感冒。他将要去看 n 名医生来找出确切的诊断。每个医生都需要之前医生的所有的诊断信息，所以Hao需要按照规定的顺序访问医生（比如Hao应该先访问 1号医生,2号医生, 然后是3号医生，等等）。 Hao将从上一位医生那里获取关于他的健康信息。

医生有一个奇怪的工作表。第i名医生从si天起工作之后会每隔di 天再工作.所以医生在si, si + di, si + 2di, ....这段时间是处以上班状态

Hao一天只能访问一名医生，Hao访问完所有医生之后所花费的最短时间是多少？

Input
First line contains an integer n — number of doctors (1 ≤ n ≤ 1000).

Next n lines contain two numbers si and di (1 ≤ si, di ≤ 1000).

Output
Output a single integer — the minimum day at which Borya can visit the last doctor.

Example
Input
3
2 2
1 2
2 2
Output
4
Input
2
10 1
6 5
Output
11
Note
In the first sample case, Borya can visit all doctors on days 2, 3 and 4.

In the second sample case, Borya can visit all doctors on days 10 and 11.
Problem solving:
这道题就是给你每个医生开始上班的日期以及上班的周期。问你多久之后你能看完所有医生。每天只能看一个医生，并且你看医生的顺序是固定的，跟输入的顺序一样。

一个while模拟一下就行了。每次没到上班的日期就往上加。
注意：一天只能看一个医生。

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int s[maxn],d[maxn];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>s[i]>>d[i];
    int ans=s[0];
    for(int i=1;i<n;i++)
    {
        int mid=s[i];
        while(s[i]<=ans)
        {
            s[i]+=d[i];
        }
        ans=s[i];
    }
    cout<<ans<<endl;
}