2025年天梯赛第1场选拔赛

目录

A:徐老师的积木山峰

 B:徐老师的最长上升子序列

 C:徐老师的机器命令

 D:徐老师的地下堡

E:徐老师的新鲜羊腿

 F:徐老师的黄金矿工

 G:徐老师的成绩统计

 H:春节糖果

 I:幸运函数

 J:好坏钥匙

---

A:徐老师的积木山峰

徐老师有 n 块积木排成一排，从左往右数编号依次为 1∼n，第 i 块积木的高度为 ai

徐老师认为如果某个积木块比左右两边相邻的两块积木块都高（即 ai−1<ai>ai+1 那么它就可以被看做是一个 **积木山峰**

现在徐老师想知道，在这 n 块积木中，有多少个 **积木山峰**

输入

输入第一行一个正整数 n，表示积木块的数量

输入第二行包含 n 个正整数，依次表示积木块的高度
对于 100% 的数据保证，1≤n,ai≤105

输出

一个整数，表示共有几块积木山峰

样例输入 Copy

7
2 1 3 1 1 1 3

样例输出 Copy

1

提示

样例解释1

只有第三个积木满足积木山峰的条件

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <deque>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<long double,long double> PDD;
const int N = 1e5+5;
const int M = 2023;
const int inf = 0x3fffffff;
const int P = 13331;
void solve(){int n;cin>>n;vector<int> a(n);for(int i=0;i<n;i++){cin>>a[i];} int s=0;for(int i=1;i<n-1;i++){if(a[i]>a[i-1]&&a[i]>a[i+1]){s++;}}cout<<s<<"\n";
}
int main(){ios::sync_with_stdio(0);cin.tie(0);//int T;cin>>T;for(int i=1;i<=T;i++)solve();return 0;
}

 B:徐老师的最长上升子序列

徐老师现在有一个长度为 n 的数组，然后他会将这个数组复制 n 次拼接在一起

比如初始数组是 [1,3,2,2]，拼接 4 次后是 [1,3,2,2,1,3,2,2,1,3,2,2,1,3,2,2]

现在徐老师想知道，拼接完以后的数组里的 **严格最长上升子序列** 长度为多少？

P.S.1 子序列指原数组中一段不需要连续的序列，即任意挑选几个数字，保持相对顺序组成的新序列称为子序列

P.S.2 严格上升子序列是指在这个数组中选出一个子序列，这个子序列中的数字依次递增

例如上述例子中可以选出的严格上升子序列有 [1],[2],[3],[1,2],[2,3],[1,2,3] 

其中最长的严格上升子序列长度为 3

输入

输入第一行包含一个正整数 n，表示数组的长度

输入第二行包含 n 个正整数，依次表示数组内的每个数字
对于 50% 的数据保证，1≤n≤50

对于 100% 的数据保证，1≤n≤50000

特别的对于所有数据保证， 1≤ai≤n

输出

一个整数，表示复制拼接后的数组的最长严格上升子序列的长度。

样例输入 Copy

4
1 3 2 2

样例输出 Copy

3

提示

样例解释1

下面用括号表示选择的数字，以下是其中一组长度为 3 的方案

[(1),3,(2),2,1,(3),2,2,1,3,2,2,1,3,2,2]

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <deque>
#include <bitset>
#include <unordered_set> 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
const int N = 1e6+10;
const int M = 1e9+7;
const int inf = 0x3fffffff;
const int P = 13331;
void solve(){int n;cin>>n;unordered_set<int> st;for(int i=0;i<n;i++){int x;cin>>x;st.insert(x);} cout<<st.size()<<"\n";
}
int main(){ios::sync_with_stdio(0);cin.tie(0);//int T;cin>>T;for(int i=1;i<=T;i++)solve();return 0;
}

 C:徐老师的机器命令

最近黄老师到徐老师家做客，但是没想到机器人的控制器居然被徐老师放在了沙发上

于是黄老师一屁股坐在了控制器上，在黄老师做完客离开家里以后

徐老师发现机器人被输入了一连串的指令！

但是幸好的是，机器人收到的指令中只有两种指令：**充电(C)** 和 **移动(M)**

这让徐老师相当心疼，因为机器人进行移动是会导致磨损的！

而徐老师当然可以擦除机器人现在收到的指令序列，但是擦除指令也会对机器人造成损伤！

机器人现在的指令序列可以用一个仅包含 C 和 M 的字符串表示

由于随机擦除指令会极大的影响机器人的 CPU 使用寿命，所以徐老师只会从指令序列的开头或者结尾擦除指令，不会擦除中间的指令

即如果指令序列为 CCMMCC，徐老师可以擦除开头的指令变成 CMMCC,MMCC,MCC… 可以擦除结尾的指令变成 CCMMC,CCMM,CCM,CC…，也可以两段都擦除一部分变成 CMMC,MM,M…，当然也可以不擦除任何命令

这样可以让徐老师擦除指令时对机器人的损伤达到最小，但是不可避免的损伤依旧存在两种：
1. 擦除指令时，每擦除一个 C 指令会对机器人造成 1 点 CPU 损伤
2. 剩余的指令集中，每存在一个 M 指令会对机器人造成 1 点物理损伤

徐老师只会关心两种损伤中比较大的损伤是多少

现在徐老师想知道，对于一个指令序列，怎么擦除指令可以使得机器人最终受到的损伤最小？

输入

第一行包含一个整数 T 表示有多组测试数据

对于每组测试数据包含一行仅由大写字母 C,M 组成的字符串，其中 C 代表充电指令，M 代表移动指令

| 数据点编号 | 字符串长度 len | 其他 |  
| :----: | :----: | :----: | :----: |
| 1∼3 | 1≤len≤100 | 无 |
| 4∼5 | 1≤len≤20000 | 每个指令序列中不超过 10 个 C |
| 6∼7 | 1≤len≤20000 | 每个指令序列中不超过 10 个 M |
| 8∼10 | 1≤len≤20000 | 无 |

对于 100% 的数据保证，1≤T≤10

输出

对于每组测试数据，输出一行包含一个整数表示最小的损伤

样例输入 Copy

5
CMCCCMCCM
CMMCMMCMMCMMC
MMMMCCCCCC
MMMMM
CCCC

样例输出 Copy

1
3
0
0
0

提示

样例解释1

第一组测试数据：CMCCCMCCM→(CM)CCCMCC(M)
移除的 C 有 1 个，剩余的 M有 1 个，损伤为 max(1,1)=1

第二组测试数据：CMMCMMCMMCMMC→(CMMCMM)CMMC(MMC)
移除的 C 有 3 个，剩余的 M有 2 个，损伤为 max(3,2)=3

第三组测试数据：MMMMCCCCCC−>(MMMM)CCCCCC
移除的 C 有 0 个，剩余的 M 有 0 个，损伤为 max(0,0)=0

第四组测试数据：MMMMM−>(MMMMM)
移除的 C 有 0 个，剩余的 M 有 0 个，损伤为 max(0,0)=0

第五组测试数据：CCCC−>CCCC
移除的 C 有 0 个，剩余的 M 有 0 个，损伤为 max(0,0)=0

以上对于每组测试数据均只提供一种可能方案，方案可能不止一种

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <deque>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
const int N = 3e3+10;
const int inf = 0x3fffffff;
const int P = 13331;
const int MOD = 7777777;
int n;
bool check(int m,vector<int> a,vector<int> b){int s=a[n]-m;for(int i=0;i<n;i++){int s1=a[i+1]-s;if(s1<0){continue;}auto it=upper_bound(a.begin(),a.end(),s1);int k=(it-a.begin())-1;if(k<0){continue;}int kk=min(k,i);int s2=b[i+1]-m;if(b[kk]>=s2){return true;}}return false;
}
void solve(){string s;cin>>s;n=s.size();vector<int> a1(n+1,0),a2(n+1,0);for(int i=0;i<n;i++){if(s[i]=='C'){a1[i+1]=a1[i]+1;a2[i+1]=a2[i];}else{a2[i+1]=a2[i]+1;a1[i+1]=a1[i];}}if(a1[n]==0||a2[n]==0){cout<<0<<"\n";return;}int l=0,r=max(a1[n],a2[n]);int ans=r;while(l<=r){int mid=(l+r)/2;if(check(mid,a1,a2)){ans=mid;r=mid-1;}else{l=mid+1;}}cout<<ans<<"\n";
}
int main(){ios::sync_with_stdio(0);cin.tie(0);int T;cin>>T;for(int i=1;i<=T;i++)solve();return 0;
}

 D:徐老师的地下堡(我不会思密达)

徐老师最近回归了一个著名老牌游戏——《魔兽世界》

在新版本中有一个单人副本模式《地下堡》，这可真是太利好徐老师这样的单人玩家了

于是徐老师在家里从早刷到晚，刷的昏天暗地，天旋地转

在梦里，徐老师依旧在刷地下堡，但是他梦到了一个神奇的地下堡副本，这个副本是一条直线，一共有 n+1 个房间排成一排编号分别为 0∼n，徐老师必须从 0 号房间进入，从 n 号房间结束副本

有些房间内存在 **火焰喷射器**，这个火焰喷射器会使得连续一段房间以及房间之间的走廊中都覆盖着火焰，徐老师一旦碰到火焰就会受到致命伤害导致游戏失败

有些房间内存在 **护盾发生器**，当拥有一个护盾发生器时，徐老师可以进入到有火焰的地方而不受伤害

当然，一个房间可能既被火焰覆盖，又有护盾发生器，甚至有好几个护盾发生器

也就是说，每次进入一个房间时，徐老师会 **依次** 进行以下行动或判定
1. 如果房间内有护盾发生器，徐老师可以选择拿起其中的某个护盾发生器
2. 如果该房间被火焰覆盖，则系统会判定徐老师身上是否有护盾发生器，若没有则游戏失败
3. 如果徐老师身上已经带有护盾发生器，徐老师可以选择放下身上的护盾发生器

而护盾发生器的重量可能不同，徐老师如果拿着一个重量为 p 的护盾发生器从当前房间 **移动到下一个房间**，需要花费 p 点体力

当然，徐老师身上可以同时携带多个护盾发生器，也可以在某个房间内放下多个护盾发生器

现在徐老师想知道，自己最少花费多少体力可以通关这个梦中副本？

P.S. 如果只是拿起放下护盾发生器，不会消耗体力

输入

输入第一行包含三个整数，n,m,k，分别表示有 n+1 个房间，m 个火焰喷射器和 k 个护盾发生器

接下来 m 行每行包含两个整数 l,r 表示第 i 个火焰喷射器覆盖编号为 l∼r 的房间以及房间之间的走廊（包含编号为 l 和 r 的房间内）

接下来 k 行每行包含两个整数 x,p 表示第 i 个护盾发生器在编号为 x 的房间内，重量为 p

对于 30% 的数据满足：1≤n,m,k,p≤10

对于 100% 的数据满足：1≤n,m,k,p≤2000

对于所有数据保证：
1. m≤n/2,1≤l<r≤n,0≤x≤n
2. 保证火焰喷射器的覆盖范围不会出现重叠或交叉，且给定的 l,r 不会重复
3. 火焰喷射器和护盾发生器的分布保证徐老师存在至少一种方案能够通关副本

输出

输出一行包含一个整数，表示徐老师最小花费的体力

样例输入 Copy

3 2 3
1 2
2 3
0 3
1 2
3 1

样例输出 Copy

4

提示

样例解释1

不拿 0 号房间的护盾发生器，到 1 号房间拿起重量为 2 的护盾发生器，一直走到 3 号房间通关游戏，共计花费体力 2∗2=4


样例解释2

在 1 号房间拿起重量为 2 的护盾发生器，到 7 号房间经过火焰判定后丢下身上的护盾发生器，此时花费体力 6∗2=12

然后移动到 8 号房间，由于身上没有护盾发生器不花费体力

进入 8 号房间时拿起 8 号房间内重量为 1 的护盾发生器，此时能够通过火焰判定，游戏不会失败

移动到 10 号房间通关副本，此时花费体力 2∗1=2

共计花费体力 12+2=14

E:徐老师的新鲜羊腿

徐老师很喜欢吃羊腿，而他经常去的这家店的羊腿定价规则是这样的

羊腿刚烤好的上架的时候，售价是 x 元，如果上架 n 小时还没卖出去，那么老板就会把这个羊腿下架

在刚上架的 10 小时内，每经过一小时羊腿的售价会减少 1 元
在第 11∼20 小时，每经过一小时羊腿的售价会减少 2 元
在第 21∼30 小时，每经过一小时羊腿的售价会减少 3 元

也就是说，对于所有小于 n 的正整数 t 来说，在经过 t 小时后，羊腿的售价会减少 ⌈t10⌉ 元。（⌈v⌉ 的意思是不小于 v 的最小整数）。在经过第 n 小时后，羊腿就会下架不允许再购买

举例来说，当 x=1000,n=30，若羊腿上架时就立刻买下（也就是经过 0 个小时），需要花 1000 元。
而在第 5 个小时买下，售价会减少 5，变为 995 元。

而在第 11 个小时买下，售价会减少 10+2 元，此时售价为 988 元。

现在徐老师想买一只羊腿，可是他囊中羞涩，只有 y 元钱，请问徐老师最早可以在一个羊腿上架后的第几个小时买到羊腿？

输入

输入只有一行，包含 3 个整数值 x,n,y，含义如题。

并保证在过程中羊腿售价也总是正整数。

对于 20% 的数据，n=1。

对于 60% 的数据，1≤n≤10。

对于 100% 的数据，1≤n≤1000，且 x,y≤106，。

输出

输出只有一个整数，代表徐老师最早在羊腿上架后的第几个小时能买到羊腿。

如果徐老师无论如何都买不起羊腿，请输出`IMPOSSIBLE`。

样例输入 Copy

1000 100 989

样例输出 Copy

11

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <deque>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<long double,long double> PDD;
const int N = 1e5+5;
const int M = 2023;
const int inf = 0x3fffffff;
const int P = 13331;
void solve(){int x,n,y;cin>>x>>n>>y;if(x<=y){cout<<"0\n";return;}int z=1;for(int i=1;i<=n;i++){x-=z;if(x<=y){cout<<i<<"\n";return;}if(i%10==0){z++;}}cout<<"IMPOSSIBLE\n";
}
int main(){ios::sync_with_stdio(0);cin.tie(0);//int T;cin>>T;for(int i=1;i<=T;i++)solve();return 0;
}

 F:徐老师的黄金矿工

徐老师最近让机器人学习如何挖矿，希望有朝一日可以带着机器人去挖黄金！

这天徐老师为了考察机器人的挖矿水平，设计了一套简单的挖矿模型

这个模型是这样的，机器人会站在某个位置，向下进行挖掘

但是机器人不像人工，需要逐步往下深挖的，机器人的挖矿方式是这样的：机器人会提前给矿钩一个足够大的动力 x，然后矿钩会一路向下到达距离地面深度为 x 米的位置然后停止

如果此时矿钩附近有黄金，则会自动开采黄金并通过传输带传回地面

现在徐老师在这块地底设计了一些 **黄金区**，每个 **黄金区** 用一个区间 [l,r] 描述，表示如果矿钩在 l∼r 米停止可以开采到黄金

由于徐老师设计了很多的黄金区，导致自己也不记得到底什么位置可以开采到黄金了

于是徐老师将模型信息输入到机器人的系统中，决定直接询问机器人第 x 米能否开采到黄金

而你的任务则和机器人一样，以此来让徐老师判断机器人的答案是否正确

输入

输入第一行一个正整数 n，表示黄金区的数量

接下来的 n 行，每行包含两个整数 li,ri 表示这个黄金区的区间

接着输入一个正整数 q 表示询问次数

接下来的 q 行，每行包含一个整数 x 表示这次询问深度 x 米是否能开采到黄金
|  数据点编号   | n,q | l,r | 
|  :----:  | :----:  | :----:  | 
| 1∼3 | 1≤n,q≤103 | 1≤l≤r≤104 | 
| 4∼6 | 1≤n,q≤105 | 1≤l≤r≤106 | 
| 7∼8 | 1≤n,q≤105 | 1≤l≤r≤109 | 
| 9∼10 | 1≤n,q≤105 | 1≤l≤r≤109 | 

特别的：对于第 7∼8 组数据，保证 n 个区间正好可以合并成一个连续的区间

对于所有数据保证：可能存在黄金区的端点是相交的，但是保证黄金区的区间不会重叠，且 x 一定再 int 范围内

输出

对于每次询问，若能开采到黄金则输出 `Gold!`，若不能开采到黄金则输出 `Sad!` （其中符号均为英文符号）

样例输入 Copy

3
1 3
9 9
5 7
10
1
2
3
4
5
6
7
8
9
10

样例输出 Copy

Gold!
Gold!
Gold!
Sad!
Gold!
Gold!
Gold!
Sad!
Gold!
Sad!

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <deque>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<long double,long double> PDD;
const int N = 1e5+5;
const int M = 2023;
const int inf = 0x3fffffff;
const int P = 13331;
struct S{int l,r;
}a[N];
bool cmp(S x,S y){if(x.l==y.l){return x.r<y.r;}return x.l<y.l;
}
void solve(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i].l>>a[i].r; }sort(a+1,a+1+n,cmp);int q;cin>>q;while(q--){int x;cin>>x;bool f=false;int ll=0,rr=n+1;while(ll<=rr){int m=ll+rr>>1;if(x>=a[m].l&&x<=a[m].r){cout<<"Gold!\n";f=true;break;  } else if(x<a[m].l){rr=m-1;}else{ll=m+1;} }if(!f){cout<<"Sad!\n";}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);//int T;cin>>T;for(int i=1;i<=T;i++)solve();return 0;
}

 G:徐老师的成绩统计

众所周知，最近为了准备复赛，大家都在紧锣密鼓的打模拟赛练习

而今天徐老师准备搞一场在线 OI 赛制的比赛

比赛的规则其实就是在线 IOI 赛制，一共四道题

任何一位同学随时都可以给任何一道题提交代码，而在后台评测机会直接评测出成绩，但是这个成绩只有管理员徐老师能看到，比赛选手是无法看到自己这次提交的成绩的

而一位同学可以反复提交代码到同一道题，但是最终系统只会保留最后一次提交的成绩

也就是说就某同学第一次提交一道题是 100 分，第二次提交这道题是 80 分，第三次提交这道题是 90 分，系统只会保留最后一次提交 90 分

而现在徐老师想在比赛过程中给同学们一些紧迫感，于是他会不定时的通知现在的第一名是哪位同学

现在徐老师为了防止出错，他希望把每次同学的提交结果告诉你，你来帮他统计得分

输入

输入第一行包含两个整数 n,m 表示一共有 n 位同学参赛，一共有 m 次事件（事件只有两种：某同学提交代码和徐老师询问第一名同学是谁）

接下来一行包含 n 个由空格隔开的字符串 ai，分别表示参赛的每位同学姓名

接下来 m 行，每行包含一个事件，首先会输入一个整数 op 表示事件类型

- op=1 表示这是一次同学提交记录，接着输入信息为 `<name> <id> <score>`，其中 `<name>` 是一个字符串表示此次提交代码的同学姓名，`<id>` 为一个 1∼4 的整数表示此次该同学提交的题目序号, `<score>` 为一个 0∼100 的整数表示此次提交的得分
- op=2 表示这是一次询问，此时后续没有其他输入，表示徐老师询问此时成绩排第一的同学姓名

对于所有数据保证： 1≤n,m≤1000,1≤id≤4,0≤score≤100，所有同学的姓名只由小写字母组成，长度不超过 6，并且姓名不会出现重复


|  数据点编号 | 特殊性质 | 
|  :----:  | :----:  | 
| 1 |  n=1 | 
| 2∼3 | 所有同学的姓名长度为 1 |
| 4∼6 | 所有 op=1 的事件保证 id=1,score=100 |  
| 7∼10 | 无 |  

输出

对于每次徐老师的询问，输出成绩排第一的同学姓名，如果总分最高的同学有多位，则输出姓名字典序最小的那个名字

样例输入 Copy

3 12
xu huang shi
1 huang 1 100
1 xu 2 90
2
1 huang 2 90
1 xu 1 100
2
1 huang 2 100
2
1 shi 1 100
1 shi 2 100
1 shi 3 100
2

样例输出 Copy

huang
huang
huang
shi

提示

样例解释1

四次询问时三个人的得分分别为：

- `xu`：0+90+0+0，`huang`：100+0+0+0，`shi`：0+0+0+0
- `xu`：100+90+0+0，`huang`：100+90+0+0，`shi`：0+0+0+0
- `xu`：100+90+0+0，`huang`：100+100+0+0，`shi`：0+0+0+0
- `xu`：100+90+0+0，`huang`：100+100+0+0，`shi`：100+100+100+0

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <deque>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<long double,long double> PDD;
const int N = 1e3+5;
const int M = 2023;
const int inf = 0x3fffffff;
const int P = 13331;
struct S{string s;int a,b,c,d;
}a[N];
bool cmp(S x,S y){if(x.a+x.b+x.c+x.d!=y.a+y.b+y.c+y.d){return x.a+x.b+x.c+x.d>y.a+y.b+y.c+y.d;}return x.s<y.s;
}
void solve(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i].s;}while(m--){int op;cin>>op;if(op==1){string ss;cin>>ss;int id,sum;cin>>id>>sum;for(int i=1;i<=n;i++){if(ss==a[i].s){if(id==1){a[i].a=sum;}else if(id==2){a[i].b=sum;}else if(id==3){a[i].c=sum;}else{a[i].d=sum;}break;}}}else{sort(a+1,a+n+1,cmp);cout<<a[1].s<<"\n";}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);//int T;cin>>T;for(int i=1;i<=T;i++)solve();return 0;
}

 H:春节糖果

春节到了，王老师给同学们准备了春节糖果，让胡图图负责糖果的发放工作。
王老师准备的不同糖果美味度不同，为使得各位同学所获得的糖果美味度相对均衡，图图需要把购来的糖果根据美味度进行分组，但每组最多只能包括两份糖果，并且每组糖果的美味度之和不能超过一个给定的整数。
为了保证在尽量短的时间内发完所有糖果，图图希望分组的数目最少。 由于胡图图比较糊涂，所以请你帮图图写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入

单组输入，每组n+2行：
第1行包括一个整数w，为每组糖果美味度之和的上限。 （80 <= w <= 200）
第2行为一个整数n，表示购来的糖果的总件数。（1 <= n <= 30000）
第3~n+2行每行包含一个正整数pi (5 <= pi <= w)，表示所对应糖果的美味度。

输出

输出一个整数，即最少的分组数目。

样例输入 Copy

100
9
90
20
20
30
50
60
70
80
90

样例输出 Copy

6

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <deque>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
const int N = 1e5+10;
const int inf = 0x3fffffff;
const int P = 13331;
const int MOD = 1e9 + 7;
void solve(){int w,n;cin>>w>>n;vector<int> p(n);for(int i=0;i<n;i++){cin>>p[i]; }sort(p.begin(),p.end());int i=0,j=n-1;int s=0; while(i<=j){if(p[i]+p[j]<=w){s++;i++;j--;}else{s++;j--;}}cout<<s<<"\n";
}
int main(){ios::sync_with_stdio(0);cin.tie(0);//int T;cin>>T;for(int i=1;i<=T;i++)solve();return 0;
}

 I:幸运函数

函数F(x)满足以下条件：（其中x为非负整数）
(1) F(0)=1;
(2) 对于所有大于0的整数i，F(i) = F(j) + F(k)，其中j为(i/2)下取整的结果，k为(i/3)下取整的结果。
给出一个非负整数N，求F(N)。

输入

单组输入。
输入一个非负整数N。(1<=N<=10^18)

输出

输出一个整数表示F(N)的值。

样例输入 Copy

2

样例输出 Copy

3

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <deque>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
const int N = 3e3+10;
const int inf = 0x3fffffff;
const int P = 13331;
const int MOD = 7777777;
unordered_map<ll,ll> mp;
ll fun(ll i){if(i==0){return 1;}if(mp[i]){return mp[i];}ll s=fun(i/2)+fun(i/3);mp[i]=s;return s;
}
void solve(){ll n;cin>>n;cout<<fun(n)<<"\n";
}
int main(){ios::sync_with_stdio(0);cin.tie(0);//int T;cin>>T;for(int i=1;i<=T;i++)solve();return 0;
}

 J:好坏钥匙

Kimi有n个箱子，编号为1-n，第i个箱子中有ai枚金币。Kimi需要按照箱子编号从小到大的次序依次打开所有的箱子，每个箱子都需要一把钥匙。
现在有两种钥匙可以打开箱子：
(1) 一把好钥匙，需要花费k枚金币；
(2) 一把坏钥匙，不需要花费任何金币，但是会将每个未打开的箱子中的金币数减半，包括即将打开的那个箱子。例如，使用一把坏钥匙来打开第i个箱子，那么第i个到第n个箱子中的金币数量都会减半（即[ai/2]取下整数）。
Kimi一共需要使用n把钥匙，每个钥匙可以打开一个箱子。已知一把钥匙只能用于一个箱子，且不能重复使用。
初始时，Kimi没有金币，也没有钥匙。如果想要使用一把好钥匙打开箱子，就需要购买它，购买一把钥匙所需金币为k枚。
允许Kimi当前所拥有的金币数量为负数。例如，Kimi有一枚金币，可以买一把价值为k=3金币的钥匙，那么他当前拥有的金币数量为-2。
请你帮助Kimi计算，按照箱子编号从小到大依次打开所有箱子能获取的最大金币数。

输入

多组输入。
第1行表示测试样例的数量T（1<=T<=10^4）。
接下来每两行为一组，其中：
第1行包含两个整数n和k表示箱子数量和购买好钥匙所需的金币数，二者之间用一个英文空格隔开（1<=n<=10^5，0<=k<=10^9）。
第2行包含n个整数a1,a2,...,an分别表示编号为1-n的箱子中的金币数量，相邻两个整数之间用一个英文空格隔开(0<=ai<=10^9)。
所有测试用例中 n 的总和不超过10^5。

输出

针对每个测试样例输出一个整数表示结果。

样例输入 Copy

3
4 5
10 10 3 1
1 2
1
12 51
5 74 89 45 18 69 67 67 11 96 23 59

样例输出 Copy

11
0
60

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <deque>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
const int N = 3e3+10;
const int inf = 0x3fffffff;
const int P = 13331;
const int MOD = 7777777;
void solve(){ll n,k;cin>>n>>k;vector<ll> a(n+5,0),s(n+5,0);ll m=0;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];m=max(m,a[i]);}ll ans=0;for(int i=0;i<=n;i++){ll t=1;ll sum=s[i];for(int j=i+1;j<=n;j++){t*=2;if(t>m){break;}sum+=a[j]/t;}sum-=i*k;ans=max(ans,sum);}cout<<ans<<"\n";
}
int main(){ios::sync_with_stdio(0);cin.tie(0);int T;cin>>T;for(int i=1;i<=T;i++)solve();return 0;
}