09-21 今天考完了初赛，明显感觉数学门槛变高了一些，有高中数学知识才能保证看得懂题意，只是苦了小学和初中同学，看数据参加人数还涨了50%，权当拉低分数线了吧。用小图灵估分70。应该是稳过。
09-28 出分了，刚好70，稳过。竟然和小图灵估的一分不差。
10-25
复赛前一天晚上，停课的竞赛生们都回家休息了，只有我和肖总在空荡荡的机房里为这最后那点依稀的光芒而追逐，说这是理想，梦想，确实谈不上，但的确是我执着所追求的。停课或是不停，合流或是不合流，都只是追求我们所想要的罢了。
听着机房里交换机嗡嗡作响的声音，可能也听不了几次了，让他们都随着流水逝去吧，涓涓的流向远方吧，只留下我呆呆的驻足凝望。只有舍不得的，没有放不下的。
战吗？战啊！以最卑微的梦
致那黑夜中的呜咽与怒吼
谁说站在光里的才算英雄
现实乱捣鬼和理想作对
我输的毫无防备
亲手堆砌生活的墓碑
一边喊累一边破重围
真诚换虚伪真心换眼泪
多可悲
键盘在手下飞舞，字符组成运行集，希望不一定会降临，运行不一定有结果，但是每当一个程序被运行，每当一个 bug 被排除，我们就离突破黑暗的枷锁又近了一步。
明天不爆零便是实力展现。在此也预祝我的所有伙伴们取得理想成绩，祝福你们！
10-26
早上 8 点多钟才起床，主要还是心不净，在幻想。早上水了一会儿，复习了一下最短路，线性筛，最近公共祖先 Lca，模拟退火，结果一个没考到（T3 打了一个模拟退火，或者说是纯随机？）
吃完饭睡了 20 分钟就出发去成都外国语学校了，达到后发现其他人都先进去了，跟曾师打声招呼随入场。有钱的私立学校确实不同，到处都是励志的名言警句，逢门就有匾，还有一尊孔子像。
最后发现我比他们还先到，据说是他们有一位优秀的领路人？！大部分同学都在这一个考场，上机后发现电脑配置是 i3-6100 直接绷不住了，不是，比我笔记本还弱，这能跑虚拟机？用的 virtualBox，打开果然无法流畅使用，窗口分辨率无法自适应，遂放弃虚拟机。
2:30 准时开考，右边的一位同学上来就开始夸我大佬，说什么还没开始考试就把对拍打好了（也没用上）着实有点影响心态。
T1
确实足够简单，甚至怪物的进攻力和防御力是相同的，用桶装，排个序，从小到大加就可以了，击败前面所有的怪物，自己成为新增怪物。大概花了 30分钟。
赛时 AC 代码和注释：
#include<bits/stdc++.h>
using namespace std;
/*一定要稳住，不要急，特别是不要旁边的人影响
每只怪兽都只能用自己的攻击力攻击一次 ，
而且注意怪兽的攻击力和防御力相同，使这道题更简单了
按照惯性，第一题用桶，跑1e5结束了
*/
#define N 200000
int tong[N],n;
int main(){
freopen("duel.in","r",stdin);
freopen("duel.out","w",stdout);
scanf("%d",&n);
int maxn=0;
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
tong[x]++;
maxn=max(maxn,x);
}
int ans=0;
for(int i=1;i<=maxn;i++){
ans=max(0,ans-tong[i])+tong[i];
}
printf("%d",ans);
return 0;
}
T2
很庆幸把 T2 做出来了，需要用到高中物理的知识，对于超速的车的个数很好处理，对于每个车，我们只需要记录他的超速区间，然后判断这个区间里有没有测速点，我用的树状数据统计，后来发现 1e6 的数据大小直接用桶也可以。然后二分把超速区间的两个端点落到测速点上，因为在中间是没有意义的，随后按照右端点排序，每次看左端点是否被上一个右端点激活，如果没有，激活这个右端点。
其中关于超速区间的取整问题稍微有点坑，调了 2 个小时，终于锁定问题并解决。
赛时 AC 代码和注释：
#include<bits/stdc++.h>
using namespace std;
/*有意思，很有意思的加速度题目，跟实际联系起来了，虽然不难
但是出的有水平。
1 hour later 15:30 终于有思路了
首先，每个车都有一个超速区间，对于一辆车，我们只需要这个区间
是否被记录，直接对测速仪做前缀和，看是否有即可
对于最多关闭的测速仪，可以思考最少打开的测速仪
使用二位偏序，以每个区间右端点排序，看左端点是否被前一个激活
如果没有，则激活右端点
噫，我中了，回去再写题解*/
#define N 200000//注意道路长1e6，离散化
#define M 1000100
#define LL long long
int n,m,L,V,p[N];
int d[N],v[N],a[N],l[N],r[N];
int tree[M],car,car2,ans;
bool vis[N],flag;
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> >e;
int lowbit(int i){
return i & (-i);
}
void update(int i,int k){
while(i<=L){
tree[i]+=k;
i+=lowbit(i);
}
}
int query(int i){
int res=0;
while(i>0){
res+=tree[i];
i-=lowbit(i);
}
return res;
}
int dis(LL v1,LL v0,LL aa){
return (v1*v1-v0*v0)/(2*aa);//向上取整
}
signed main(){
freopen("detect.in","r",stdin);
freopen("detect.out","w",stdout);
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T--){
car2=car=ans=0;flag=0;
cin>>n>>m>>L>>V;
memset(tree,0,(L+10)*sizeof(int));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
cin>>d[i]>>v[i]>>a[i];
if(a[i]>0){
if(v[i]>V){
l[i]=d[i];r[i]=L;
}else{
l[i]=min(d[i]+dis(V,v[i],a[i]),L)+1;
r[i]=L;
}
}else if(a[i]<0){
if(v[i]>V){
l[i]=d[i];r[i]=d[i]+(V*V-v[i]*v[i])/(2*a[i]);
if((v[i]*v[i]-V*V)%(-2*a[i])==0) r[i]--;
r[i]=min(L,r[i]);
}else{
l[i]=r[i]=-1;
}
}else{
if(v[i]>V){
l[i]=d[i];r[i]=L;
}else{
l[i]=r[i]=-1;
}
}
}
for(int i=1;i<=m;i++){
cin>>p[i];
if(p[i]==0){
flag=1;
continue;
}
update(p[i],1);
}
for(int i=1;i<=n;i++){
// printf("||%d %d\n",l[i],r[i]);
if(query(r[i])-query(l[i]-1)>0){
car++;
vis[i]=1;
}
if(!l[i]&&flag){
car++;
vis[i]=1;
}
}
for(int i=1;i<=n;i++){
if(!vis[i]) continue;
int at=lower_bound(p+1,p+1+m,l[i])-p;
l[i]=at;
at=upper_bound(p+1,p+1+m,r[i])-p-1;
r[i]=at;
e.emplace(r[i],l[i]);
// printf("|%d %d\n",l[i],r[i]);
}
int last=0;
while(!e.empty()){
int le=e.top().second,ri=e.top().first;
e.pop();
// printf("|%d %d\n",le,ri);
if(le<=last) continue;
ans++;
last=ri;
}
cout<<car<<' '<<m-ans<<endl;
}
return 0;
}
T3
对于 \(n\le 15\) 时，暴力枚举，设 \(1\) 和 \(0\) 分别为蓝色和红色，然后从 \(1\) 枚举到 \(2^{n-1}\) 的二进制对应。
复杂度即为 \(2^{14}=16384\)
很可惜 \(2^{100}=1267650600228229401496703205376\)，只能过第一个数据范围，也就是前四个点，有20分。
剩下就是乱搞了，用的模拟退火的板子，但其实是纯随机，数据弱捞两分，但是其实早就料到 CCF 的数据强度是拉满的。看似是小于等于这个数据范围，其实都是顶满的。去年 T4 的暴力就是没料的小数据都爆 \(int\) 了。
赛时 20 分代码：
#include<bits/stdc++.h>
using namespace std;
/*暴力加模拟退火 GO*/
#define N 200000
int n,a[N],ans,T;
bool pos[N];
mt19937 rnd(random_device{}());
void baoli(){
for(int k=0;k<=(1<<(n-1));k++){//等于1为blue
int red=-1,blue=-1;
int res=0;
for(int i=0;i<n;i++){
if(k&(1<<i)){
if(blue>=0&&a[blue]==a[i]) res+=a[i];
blue=i;
}else{
if(red>=0&&a[red]==a[i]) res+=a[i];
red=i;
}
}
ans=max(ans,res);
}
}
int check(){
int red=-1,blue=-1;
int res=0;
for(int i=0;i<n;i++){
if(pos[i]){
if(blue>=0&&a[blue]==a[i]) res+=a[i];
blue=i;
}else{
if(red>=0&&a[red]==a[i]) res+=a[i];
red=i;
}
}
return res;
}
void stimulate_fire(){
double tem=1000,d=0.997;
memset(pos,0,(n+1)*sizeof(bool));
while(tem>1e-6){
tem*=d;
int rand=rnd()%n;
pos[rand]^=1;
ans=max(ans,check());
}
}
void stimulate(){
for(int i=1;i<=10;i++)
stimulate_fire();
}
int main(){
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
scanf("%d",&T);
while(T--){
ans=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
if(n<=15){
baoli();
}else{
stimulate();
}
printf("%d\n",ans);
}
return 0;
}
T4
确实没有时间看了，好像有 12 分的部分分。
最后还剩 1:21 的时候，看到前三道题都是提交了，变绿了，但是第四题是白色的，心想这可不行，故打了一行字。
赛时第四题代码：
//估分220，静待花开，再见CSP2024，美好的竞赛生涯，再见！！！
后事
由于今年 CCF 政策变化，所以只公布加密选手代码，故这下估不了分数了，不过做了的分数就是 220。
CCF：我们要做干净竞赛！
11-02
公布成绩了，100+100+20=220，但是看到小图灵估的四川省分数线是 260，这下凉了。
但曾师说分数线应该在 180-200 左右，应该还是有希望，看来小图灵的数据还是太水了。
11-08
完成这篇博客到这里的书写。
持续更行……
友情链接：https://blog.huasushis.cn/2024/10/31.html
标签：枷锁,int,res,else,2024,端点,ans,CSP,red From： https://www.cnblogs.com/alloverzyt/p/18535976