Day29

Day29

今天学长的积分赛
好好学习!!!

分数

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”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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是偶数不满足题意.

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;

int a[110];
int main()
{
int t;
scanf("%d",&t);
for(int i = 1; i <= t; i ++) scanf("%d",&a[i]);
if(t % 2 == 0) puts("NO");
else
{
if((a[1] & 1) && (a[t] & 1)) puts("YES");
else puts("NO");
}
return 0;
}

搜索漂亮的整数

Description:
小红现在有两个列表的数字.
如果一个十进制数至少有一个数字来自列表一且至少有一个数字来自列表二,那么将这个数字叫做小红数,请你找出最小的正小红数
Input
第一行包括两个整数 n 和 m (1 ≤ n, m ≤ 9) — 分别代表第一个和第二个列表的长度。
第二行包含 n 个不同的数字 a1, a2, …, an (1 ≤ ai ≤ 9) 代表列表一中的元素。
第三行包含 m 个不同的数字 b1, b2, …, bm (1 ≤ bi ≤ 9) 代表列表二中的元素

Output
输出最小正小红数.

1
2
3
4
5
6
7
8
9
10
11
12
13
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

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
const int maxx = 20;
int a[maxx], b[maxx];
int main()
{
ios::sync_with_stdio(false);
int n, m;
int minn, maxn;
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 = 0;
int flag = 0;
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
if(a[i] == b[j])
{
ans = a[i];
flag = 1;
break;
}
}
if(flag) break;
}
if(flag) cout << ans << '\n';
else
{
minn = min(a[0], b[0]);
maxn = max(a[0], b[0]);
cout << minn * 10 + maxn << '\n';
}
return 0;
}

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通关的几率

1
2
3
4
5
6
7
Sample Input
(空)
Sample Output
1.00
0.00
0.50
0.55 (输出仅做格式参考,不保证正确性)

评价

该题及其SB,不得不吐槽一下
code:

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;


int main()
{
printf("1.00\n1.00\n1.00\n1.00\n");

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
输出只有一行,表示学长最少需要花费的钱.

题意

有很多个活动,每个活动有持续天数,每个活动会在每天提供C个CPU每个CPU价格为P,问需要工作N天,每天需要K个CPU的最少花费。

解题思路

首先价格越低的活动,肯定是要选的。因此我们对于每一天记录有哪些新活动 加入,哪些活动结束。然后维护一个线段树,线段树的下标是价格。即价格为i的活动,一共能提供多少个CPU,然后加入和删除活动就相当于update(C,+-P,1,MAXC,1)。 然后我们顺便维护一下价格*数量的和。然后利用线段树天然的二分性,快速求出前缀数量和为K的价格和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <memory.h>
#include <bitset>
#include <map>
#include <deque>
#include <math.h>
#include <stdio.h>
using namespace std;
typedef long long int ll;
const int MAXN = 1000005;

ll num[MAXN<<2];
ll sum[MAXN<<2];
int N;
void pushup(int rt){
num[rt]=num[rt<<1]+num[rt<<1|1];
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void update(int P,int C,int l,int r,int rt){
if(l==r){
num[rt]+=C;
sum[rt]+=1ll*P*C;
return;
}

int m=(l+r)/2;

if(P<=m)
update(P,C,l,m,rt<<1);
else
update(P,C,m+1,r,rt<<1|1);
pushup(rt);
}

ll query(int K,int l,int r,int rt){

if(l==r){
//不到K个
if(l==MAXN){
return 0;
}
if(K>0)
{
return 1ll*K*l;
}
else
return 0;
}
int m=(l+r)/2;
if(num[rt<<1]>=K){
return query(K,l,m,rt<<1);
}
else{
return sum[rt<<1]+query(K-num[rt<<1],m+1,r,rt<<1|1);
}
}

vector<pair<int,int> > C[MAXN];//第i天加入的活动
vector<pair<int,int> > O[MAXN];//第i天结束的活动

int main()
{
int K,M;
scanf("%d%d%d",&N,&K,&M);

int l,r,c,p;
for(int i=0;i<M;i++){
scanf("%d%d%d%d",&l,&r,&c,&p);
C[l].push_back(make_pair(p,c));//加入的活动
O[r].push_back(make_pair(p,c));//退出的活动
}

ll ans=0;
for(int i=1;i<=N;i++){
//新活动加入
for(int j=0;j<C[i].size();j++)
update(C[i][j].first,C[i][j].second,1,MAXN,1);
ans+=query(K,1,MAXN,1);
//活动结束
for(int j=0;j<O[i].size();j++)
update(O[i][j].first,-O[i][j].second,1,MAXN,1);
}
cout<<ans<<endl;

return 0;
}

最小值最大值

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
Example
Input
5 2
1 2 3 4 5
Output
5
Input
5 1
-4 -5 -3 -2 -1
Output
-5

PS:对2也要特判一下
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100001];
int main()
{
int n, k;
scanf("%d %d",&n, &k);
for(int i = 1; i <= n; i ++) scanf("%lld",&a[i]);
if(k == 2) cout << max(a[1], a[n]) << '\n';
else
{
sort(a + 1, a + n + 1);
if(k == 1) cout << a[1] << '\n';
else cout << a[n] << '\n';
}

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即可得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.

题解

找到a[i]p+a[j]q+a[k]*r的最大值,i<=j<=k;
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//每次更新
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
long long n,a1,a2,a3,a=-8e18,b=-8e18,c=-8e18;
cin>>n>>a1>>a2>>a3; int x;
for(int i=0;i<n;i++)
{
cin>>x;
a=max(a,a1*x);
b=max(b,a+a2*x);
c=max(c,b+a3*x);
}
cout<<c<<endl;
}

//前后缀维护
#include<bits/stdc++.h>
using namespace std;

const int N = 100005;
int a[N];
long long L[N],R[N];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
long long p,q,r;
cin >> n >> p >> q >> r;
for(int i = 1;i <= n;i++)
cin >> a[i];
L[1] = a[1]*p;R[n] = a[n]*r;

for(int i = 2;i <= n;i++)
L[i] = max(L[i-1],a[i]*p);
for(int i = n-1;i >= 1;i--)
R[i] = max(R[i+1],a[i]*r);
long long maxn = -(1ll<<63);
for(int i = 1;i <= n;i++)
maxn = max(maxn , L[i]+a[i]*q+R[i]);
cout << maxn << "\n";
return 0;
}

赛题分析

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。
注意:间隔都是一个空格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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.

排序题

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int a[30], b[600];
int main()
{
int t;
int n, m;
scanf("%d",&t);
int k = 1001;
while(t --)
{
scanf("%d %d",&n, &m);

for(int i = 0; i < n; i ++) scanf("%d",&a[i]);
for(int i = 0; i < m; i ++) scanf("%d",&b[i]);
sort(a, a + n);
sort(b, b + m);
printf("Problem %d:\n",k ++);
printf("Shortest judge solution: %d bytes.\n",a[0]);
if(m != 0)
printf("Shortest team solution: %d bytes.\n",b[0]);
else
printf("Shortest team solution: N/A bytes.\n");
}
return 0;
}

差异的可分割性

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个数,数与数之间用空格隔开。 (存在多种情况,输出任意一种)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

题解

用数组记录每个数对m取模余数相等的有多少个
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
int nu[maxn];
int cnt[maxn];
int main() {
ios::sync_with_stdio(false);
int n,k,m,i;
cin>>n>>k>>m;
for(i=1;i<=n;++i) {
cin>>nu[i];
}
int ans=-1;
for(i=1;i<=n;++i) {
int u=nu[i]%m;
++cnt[u];
if(cnt[u]==k) {
ans=u;
break;
}
}
if(ans==-1) cout<<"No"<<endl;
else {
cout<<"Yes"<<endl;
for(int i=1;i<=n;++i) {
if(nu[i]%m==ans) {
--k;
cout<<nu[i]<<" ";
}
if(k==0) break;
}
}
return 0;
}

扫雷

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

1
2
3
4
5
6
7
Sample Input
2
22
000
Sample Output
6
1

题解

这一题,你会发现确定了第一列的摆放方案,后面所有的都就确定了。。所以我们就枚举第一列的方案数,一共就有0,1,2三种,注意我们操作的是每一列,所以注意不能超过2个。。然后,模拟姿势就是,因为这个是身边的八个格子,枚举当前列的时候,我们要把它当成八个格子三列中的最后一列,以中间列为标准,设dp为枚举状态每一列已经放的个数,num为题目告诉的雷数,那么枚举每一列的时候,都要看前一列(八个格子三列中的中间列),用num[i-1]-dp[i-2]-dp[i-1],即减去中间列左面放的,自己这一列放的,就是右边放的了,这样就满足了num[i]的数量。。姿势很重要。。然后就是计数了,如果当前放了0个或者两个,i列跟i-1列的方案数是一样的,如果是1的话,那i列就是i-1列的两倍了。。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 5;
const int Mod = 1e8 + 7;
int num[maxn], dp[maxn];
char str[maxn];
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
memset(dp, 0, sizeof(dp));
scanf("%s", str);
int n = strlen(str);
for(int i = 0; i < n; i++)
num[i+1] = str[i] - '0';
ll ans = 1, res = 0;
for(int i = 0; i <= num[1]; i++)
{
ans = 1;
if(i > 2) break; //控制条件
dp[1] = i;
int j;
for(j = 2; j <= n; j++)
{
int k = num[j-1] - dp[j-1] - dp[j-2];
if(k > 2 || k < 0) break; //控制条件,这些都容易漏
dp[j] = k;
}
if(j <= n) continue;
if(dp[n-1] + dp[n] != num[n]) continue; //这里一定要有,区域赛的题好几题都是策略完了,然后要判定一下。。按照这个策略,看看最后两列是不是相同
for(int i = 1; i <= n; i++)
{
if(dp[i] == 1)
ans = (ans * 2) % Mod;
}
res = (res + ans) % Mod;
}
printf("%lld\n", res);
}
return 0;
}

派对柠檬水

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

想想马上就要回老家了某不愿透露姓名的林姓学长再次却陷入了沉思。。。。。。。。。
他默默的去前台打算点几瓶二锅头。
他发现菜单上有n 种不同毫升的酒. 第 i 种有2i - 1 毫升价格为ci 元.商店中每种类型的酒的数量可以被认为是无限的。.
他对于自己能喝多少还是有点B-Tree的,但是他认为喝酒一定要喝的尽兴,于是他打算买至少L 毫升,但是又要花最少的钱,现在他想知道他最少需要花多少钱

Input
第一行输入两个整数 n and L (1 ≤ n ≤ 30; 1 ≤ L ≤ 109) — 代表有n总酒和需要买的数量
第二行输入 n个整数s c1, c2, …, cn (1 ≤ ci ≤ 109) —代表第i种酒需要的钱数
Output
输出一个整数,他买至少L 了毫升,所花的最少钱数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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毫升,但是购买一个108毫升的便宜一些。

在第三个例子中,最好10元购买三个1毫升的。

题目大意

有 n 种柠檬汁,第 i 种每瓶的容量为 2^(i-1) 升,价格为 Ci,问至少买 L 升柠檬汁最少花多少钱?

题解

一看题,第一感觉是 DP,但是由于购买数可以超过 L 升,并且 L 太大了,所以不能用 DP解决。我们采取贪心的策略:优先买单价更低的。这样会出现一个问题,剩余量如果不够一瓶,我们是买一瓶单价最低的呢?还是从单价更高的中拼一下呢?因为买一瓶单价最低的话会产生一点浪费。所以我们就可以按照这个思路用 DFS做。
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;

LL n,mn;

struct node
{
LL cost,lit; //每瓶的价格和容量
double v; //单价 /升
} a[33];

LL cmp(node a,node b)
{
return a.v<b.v;
}

void dfs(LL dep,LL res,LL ans)
{ //参数:当前位置,剩余量,当前花费
int f=0;
if(ans>=mn) return; //如果当前花费比最小值大则退出
if(dep==n||res<=0)
{ //如果搜索完毕或者已经购买完,则更新最小值并退出
if(ans<mn) mn=ans;
return;
}
LL x=res/a[dep].lit; //当前种柠檬汁可以买多少瓶
if(res%a[dep].lit!=0)
{ //如果剩余不够一瓶,则多买一瓶
x++;
f=1;
}
ans+=x*a[dep].cost; //先多买一瓶当前种的
res-=x*a[dep].lit;
dfs(dep+1,res,ans);
if(f==1)
{ //如果多买了,则在回溯时还原
ans-=a[dep].cost;
res+=a[dep].lit;
dfs(dep+1,res,ans);
}
}

int main()
{
LL i,l;
while(~scanf("%lld%lld",&n,&l))
{
for(i=0;i<n;i++)
{
scanf("%lld",&a[i].cost);
a[i].lit=1<<i;
a[i].v=(double)a[i].cost/a[i].lit;
}
sort(a,a+n,cmp); //按单价升序排序
mn=0x7fffffffffffffff;
dfs(0,l,0);
printf("%lld\n",mn);
}
return 0;
}

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=10^4,n<=10^18
Output
共T行,每行一个正整数表示所求的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
Sample Input
5
3
6
9
12
15
Sample Output
31
700
7486
64651
527023

数据范围这么大,直接矩阵快速幂解决
题意
f[n] = 2*f[n-2] + f[n-1] + n^3,n<=1e18,求f[n] 。

题解
在计算 f[n+1] 的时候, 要变为 ,所以构造的矩阵中需要有这几项,然后因为引入了 ,所以 要变为 ,因为 项、项、常数项都已经存在,所以不需要引入新的项,其余各项均可通过这几项计算出。
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX = 1e6 + 20;
const int mod = 123456789;

ll n;

typedef struct {
ll m[10][10];
}Matrix;

Matrix Mul(Matrix a, Matrix b)
{
Matrix c;
memset(c.m, 0, sizeof(c.m));
for (int i = 0; i < 6; i++)
{
for (int j = 0; j < 6; j++)
{
for (int k = 0; k < 6; k++)
{
c.m[i][j] += ((a.m[i][k] * b.m[k][j]) % mod + mod) % mod;
c.m[i][j] %= mod;
}
}
}
return c;
}

Matrix fastm(Matrix a, ll num)
{
Matrix res;
memset(res.m, 0, sizeof(res.m));
for (int i = 0; i < 6; i++)
res.m[i][i] = 1;
while (num)
{
if (num & 1)
res = Mul(res, a);
num >>= 1;
a = Mul(a, a);
}
return res;
}

int main()
{
int T;
scanf("%d", &T);
Matrix a;
memset(a.m, 0, sizeof(a.m));
a.m[0][0] = 1, a.m[0][1] = 1;
a.m[1][0] = 2;
a.m[2][0] = 1, a.m[2][2] = 1;
a.m[3][2] = 1, a.m[3][3] = 1;
a.m[4][2] = 1, a.m[4][3] = 2, a.m[4][4] = 1;
a.m[5][2] = 1, a.m[5][3] = 3, a.m[5][4] = 3, a.m[5][5] = 1;
ll st[10];
st[0] = 2, st[1] = 1, st[2] = 27, st[3] = 27, st[4] = 9, st[5] = 1;
while (T--)
{
scanf("%lld", &n);
n -= 2;
Matrix b = fastm(a, n);
ll ans = 0;
for (int i = 0; i < 6; i++) {
ans = (ans + b.m[i][0] * st[i] % mod) % mod;
}
printf("%lld\n", ans);
}
return 0;
}

诊断

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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.

题目大意说的是找到最晚的一天,那就一只加呗,直到最后一天
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;

struct node{
int x, y;
}e[1001];
int main()
{
int t;
while(~scanf("%d",&t))
{
for(int i = 1; i <= t; i ++)
scanf("%d %d",&e[i].x, &e[i].y);
int ans = e[1].x;
for(int i = 2; i <= t;)
{
if(e[i].x > ans)
{
ans = e[i].x;
i ++;
}
else
{
while(e[i].x <= ans)
{
e[i].x += e[i].y;
}
}
}
printf("%d\n",ans);
}


return 0;
}

---------------- The End ----------------
0%