2025年10月17日参加的线上赛：
洛谷CCPC2024邀请赛山东站重现赛
洛谷入门赛#40
CodeForces round #1059 （Div.3）
首先是第一场 CCPC邀请赛山东重现
成绩：只过了I题（还是个水题）
感想：题目难度远超个人水平 任重道远
需要复盘的题目：A题：[# P14237[[P14237 打印机]] [CCPC 2024 Shandong I] 打印机](
写的暴力 结果当然是全TLE
问了问 Gemini 给出的思路是：二分答案 (Binary Search)
设最坏情况时间为t，如果t时间内任务完成，就尝试二分时间t，再次检测t时间内是否完成，如果能完成则继续二分，否则终止然后处理临界问题，最后得出答案。
赛后查看题解 确实是二分
暴露的问题：
没有想到二分，而是想成了贪心或者模拟（提交用的暴力模拟）
就算是写模拟也费了很多时间
二分不会写
“求打印 $k$ 份试题至少需要多少秒” 这种问法，通常暗示着二分答案
AC Code:
#include<bits/stdc++.h>
#include <climits>
using namespace std;
struct node;
bool judge();
void solve();
int n,k;//n最大100 k最大10亿
struct node{
unsigned long long ti,li,wi;
unsigned long long cycle;//时间周期 一次打印机从打印到冷却完毕的时间
}a[100];
int TT;
int main(){
cin>>TT;
while(TT-->0){
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i].ti>>a[i].li>>a[i].wi;
a[i].cycle = a[i].ti*a[i].li+a[i].wi;
}
solve();
}
return 0;
}
bool judge(unsigned long long t){
unsigned long long pnum =0;//检查时间t内是否够打印指标
for(int i=0;i<n;i++){
unsigned long long t1 = t/a[i].cycle;
t1*=a[i].li;
unsigned long long t2 = t%a[i].cycle;
t2/=a[i].ti;
pnum = pnum + t1 + min(t2,a[i].li);
if(pnum>=k){ //及时剪枝 否则pnum可能溢出数据范围 且会超时;
return 1;
}
}
return 0;
}
void solve(){
unsigned long long t =ULLONG_MAX,mid,l=0;//不开MAX会WA 就算开了MAX时间也是够的;
while(l<t){
mid = (l+t)/2;
if(judge(mid)){
t=mid;
}else{
l=mid+1;
}
}
cout<<t<<endl;
return;
}二分实现思路：
三个变量：左下标(l) 中间值(mid) 右下标(直接用t)
//如果是更复杂的问题 右下标可能要单独开
首先从t的最坏情况 测试能否完成指标
$$ mid = \frac{t}{2} $$
然后再对 mid 进行判断是否符合 同时t/=2
如果不能：此时答案一定在(mid,t)内
我们进行枚举即可 此时用到左下标
当然可以直接开个for循环（用下标更优雅一点
我们取
$$ mid=\frac{t+l}{2} $$
然后继续重复上述流程
终止条件：l = t 直接输出即可
洛谷入门赛#40
难绷之比赛结束快一周了连题都进不去
本次比赛一共八道题 当然div4的题目都不会很难 但本人这次卡到G题了 而且做题不够快，几乎每道题都会有错误提交 还是要练
因为现在题进不去 所以下面简述下题目：
两个长度为n的数组a,b 输入n和a,b
和一段字符串 输入大概长这样：
12
3 6 6 4 2 3 8 1 9 11 12 5
6 8 3 2 9 1 10 5 12 4 11 7
a[b[b[a[b[b[a[a[12]]]]]]]]
要求根据字符串 进行数组嵌套然后给出对应数组内的值
乍一看不是很难 卡题也没有卡在思路上
而是代码实现的时候炸了
先给AC Code：
#include<bits/stdc++.h>
using namespace std;
int a[10000],b[10000];
int solve(string s){
int aob;
if(s[0]=='a'){
aob = 1;
}
if(s[0]=='b'){
aob = 0;
}
if(s[0]<=57){
string num;
while(s[0]!=']'){
num += s[0];
s.erase(s.begin());
}
//cout<<num<<endl;
return stoi(num);
}
s.erase(s.begin());
s.erase(s.begin());
if(aob==1){
return a[solve(s)];
}else{
return b[solve(s)];
}
}
int main(){
int len;
cin>>len;
for(int i=0;i<len;i++){
cin>>a[i];
}
for(int i=0;i<len;i++){
cin>>b[i];
}
string s;
cin>>s;
cout<<solve(s);
return 0;
}思路是每次递归读取第一位
如果是字母就抹去前两个然后给下一层递归
一直到检测到数字 读取数字最后返回
至于为什么卡题
emm
读取数字的时候没有考虑数位
导致样例死活没过（草
赛后发现了一个很好用的东西：
stoi(string s);
to_string(int a);字符串和整形的互相转换
CodeForces Round #1059(Div.3)
本人第一次在cf上打比赛 div3的题目比div4难不少 不过也有一部分是因为英文题目（