CSP-S 2024 福建奇葩代码大赏
CSP-S 2024 福建奇葩代码大赏
0. 成就
最长空格子串由 FJ-S00638\detect\detect.cpp 达成（长度为 12243）
最多 Tab 由 FJ-S01483\arena\arena.cpp 达成（4012 个）
preopen 由 FJ-S00950 / FJ-S01058 / FJ-S01710 达成
"r",stdout 由 FJ-S00187 / FJ-S00682 / FJ-S00721 / FJ-S01058 / FJ-S01078 / FJ-S01386 / FJ-S01467 / FJ-S01614 / FJ-S01779 达成（共 9 人）
"w",stdin 由 FJ-S00111 / FJ-S00533 / FJ-S00682 / FJ-S00932 / FJ-S00974 / FJ-S01164 / FJ-S01339 / FJ-S01499 / FJ-S01512 / FJ-S01727（共 10 人）
0 bit 文件夹由 FJ-S00015 / FJ-S00017 / FJ-S00033 / FJ-S00076 / FJ-S00086 / FJ-S00347 / FJ-S00557 / FJ-S00562 / FJ-S00570 / FJ-S00573 / FJ-S00593 / FJ-S00596 / FJ-S00608 / FJ-S00613 / FJ-S00734 达成（共 15 人）
最小非空文件夹由 FJ-S00365 达成（8 kb）（4 个空cpp文件）
最大单文件由 FJ-S00332\detect\detect.cpp 达成（长度为 501762）（输出最大样例）
最大数组由 FJ-S01506\detect\detect.cpp 达成 int r[1000000005],tong[1000000005];
1. 游记人
FJ-S00201/detect/detect.cpp
/*
我感觉我好幸运啊，
去年初三考到了一元二次方程，今年刚刚高一考到了加速度
这是我熟悉的领域，笑.jpg
虽然一元二次方程炸了就是...
怎么感觉这个也要炸？？？
还好还好，调了半天
c,还是错.........
话说我这份吐槽不会被发到FJ代码吐槽上吧》
可能原本不会，加上这句话就会了(
错的是ccf！不是我的二分！！！
对，我的二分一直没错，有问题的是我的眼睛！！！
.ra侦察 1d100=100/25,大失败导致的
*/FJ-S00038\arena\arena.cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
return 0;
}/*
18：19，我坐在考场上还有最后的十分钟。其实对去年的s组印象没有很深刻，就记得打到很晚，和llxy去上育龙，在街边吃的面条。那个时候我还是个初三生。
那个时候的我一定不会想到会是我今天这个样子吧。印象更深的是，初二的s组。那次是在一中考的。一中的机房不是很好，空调嗡嗡作响
晚上很黑，机房的FRC很不稳定，我等到很晚才走。我记得那一次周周还在。
今天T1感觉写假了，但是大样例都过了，不知道会不会挂分。T4本来还有12pts没有打的，但是我看不懂输入输出，加上码量确实也不少，我也就放弃了。
我决定给T4一点地位，至少我四个文件夹都要有东西吧。这是我第一次考试没有摸鱼，扎扎实实的打完了整场比赛。*/ FJ-S01307\color\color.cpp
/*
15:12 right deskmate is sleeping! /jk
I think he AKed CSP-S only spend 42min /bx
15:27 left deskmate is sleeping! /jk
I think he AKed CSP-S only spend 57min /bx
I want to sleep too. qwq.
but FLC is really vegetable so she can't relax.
san zhuang ying yu /cf
bu yong chinese's reason is DevC++ == shit
xuan ran hui hu /kk
5
3
1 2 1
4
1 2 3 4
8
3 5 2 5 1 2 1 4
15
5 3 7 2 4 13 11 6 5 5 3 5 12 8 13
15
1 12 11 11 7 11 15 6 4 6 3 15 7 5 2
1
100
17 18 18 19 17 19 20 20 18 19 18 19 18 19 19 19 18 17 19 17 40 40 40 37 40 39 39 39 38 39 38 40 37 40 38 40 38 39 39 40 59 60 58 60
59 58 59 58 60 57 58 60 57 60 57 60 58 60 57 60 80 80 79 80 78 77 80 79 79 80 79 79 79 77 80 77 77 80 80 78 100 100 98 97 97 99 98
99 100 99 100 98 98 99 98 98 100 100 97 98
good guo, jb lai de, CCF wo chihaole.
but this is a new yangli.
P yong mei you. idk solve.
16:07 yangli #1 ACed!
16:17 Dead #2.
16:23 go to WC and meet tobie's friend (forget name(xiu kui)) and get idea! I can AC it!
16:56 Dead again.
17:19 (ノ｀Д)ノ
no // 51 hang
yes // 114 hang
/jk
*/2. F**k CCF 人
FJ-S00110\arena\arena.cpp // CCF 怎么又涨价 我 你
FJ-S00201\arena\arena.cpp
/*
ccfwcnm
bydcff
i f**k ccf
*/FJ-S00208\duel\duel.cpp
/*
Fuck you ccf
ccf your mother is BOOM!!!!!!
*/FJ-S00356\arena\arena.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
freopen("arena.in","r",stdin);
freopen("arena.out","w",stdout);
cout<<"FUCK CCF!!! CCF SB!!! Died mom's CCF";
return 0;
}FJ-S00735\color\color.cpp
int CCF(){
// 略
}
} // namespace Fuck
int main(){
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
Fuck::CCF();
return 0;
}FJ-S00735\detect\detect.cpp
int CCF(){
// 略
}
} // namespace Fuck
int main(){
freopen("detect.in","r",stdin);
freopen("detect.out","w",stdout);
Fuck::CCF();
return 0;
}FJ-S00735\duel\duel.cpp
int CCF(){
// 略
}
} // namespace Fuck
int main(){
freopen("duel.in","r",stdin);
freopen("duel.out","w",stdout);
Fuck::CCF();
return 0;
}FJ-S01031\color\color.cpp// can i **** ***? so ccf ____ ___.
2.5. Don't like CCF 人
FJ-S01031\duel\duel.cpp // i don't like ccf
3. Love CCF 人
FJ-S00125\color\color.cpp //泥嚎，亲爱的CCF,我也不知道我为什么会在S组的考场上，你记住了奥，我是真的穷，麻烦宁高抬贵手多给点分罢
FJ-S00208\color\color.cpp
/*
CCF I LOVE YOU CAN YOU GIVE ME 1 POINT?
:( 已老实，求放过 FJ-S00445\arena\arena.cpp
#include<bits/stdc++.h>
using namespace std;
int main() {
freopen("arena.in","r",stdin);
freopen("arena.out","w",stdout);
//CCF...Orz...
return 0;
}FJ-S00445\color\color.cpp
/*
CSP-S 2024 RP++!
This Code By Zhang Yimin.
I will Get Second Prize?
I Want to Get Second Prize!!!
I Hope This Code Will Get 20 pts.
(My English is not well QwQ)
CCF <--- OIer's God--CCF!
_____
| |___Orz_Orz_Orz___
*/FJ-S00445\duel\duel.cpp
/*
CSP-S 2024 RP++!
This Code By Zhang Yimin.
I will Get Second Prize?
I Want to Get Second Prize!!!
I Hope This Code Will Be AC.
(My English is not well QwQ)
CCF <--- OIer's God--CCF!
_____
| |___Orz_Orz_Orz___
面对现实，成为现实。
*/FJ-S01711\arena\arena.cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
freopen("arena.in","r",stdin);
freopen("arena.out","w",stdout);
printf("I LOVE CCF!\n");
return 0;
}4. 周杰伦
FJ-S00500\color\color.cpp
/*久未放晴的天空
依旧留着你的笑容
哭过
却无法掩埋歉疚
风筝在阴天搁浅
想念还在等待救援
我拉着线
复习你给的温柔
曝晒在一旁的寂寞
笑我给不起承诺
怎么会怎么会
你竟原谅了我
我只能永远读着对白
读着我给你的伤害
我原谅不了我
就请你当作我已不在
我睁开双眼看着空白
忘记你给我的期待
读完了依赖
我很快就离开
*/FJ-S00500\arena\arena.cpp
int main()
{
freopen("arena.in","r",stdin);
freopen("arena.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",aa+i);
for(int i=1;i<=m;i++) scanf("%d",c+i);
for(int i=1;i<log2(n);i++) scanf("%d",&d);
cout<<1<<endl;
fclose(stdin);
fclose(stdout);
return 0;
//f**k you CcF
}
/*乌云在我们心里留下一块阴影
我聆听沉寂已久的心情
清晰透明
就像美丽的风景
总在回忆里才看得清
被伤透的心能不能够继续爱我
我用力牵起没温度的双手
过往温柔
已经被时间上锁
只剩挥散不去的难过
（在山腰间飘逸的红雨
随着北风凋零
我轻轻摇曳风铃
想唤醒被遗弃的爱情
雪花已铺满了地
深怕窗外枫叶已结成冰）
缓缓飘落的枫叶像思念
我点燃烛火温暖岁末的秋天
极光掠夺天边
北风掠过想你的容颜
我把爱烧成了落叶
却换不回熟悉的那张脸
缓缓飘落的枫叶像思念
为何挽回要赶在冬天来之前
爱你穿越时间
两行来自秋末的眼泪
让爱渗透了地面
我要的只是你在我身边
*/5. 被 AK 人
FJ-S00679\arena\arena.cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("arena.in","r",stdin);
freopen("arena.out","w",stdout);
cout<<"CSP-S RP++"<<endl;
cout<<"CCF NOI 114514"<<endl;
cout<<"CSP-S AK ME!"<<endl;
return 0;
}FJ-S00679\detect\detect.cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("detect.in","r",stdin);
freopen("detect.out","w",stdout);
cout<<"CSP-J RP++"<<endl;
cout<<"CCF NOI 114514"<<endl;
cout<<"I AK CSP-J!"<<endl;
return 0;
}6. AFO 人
FJ-S00735\arena\arena.cpp
#include<bits/stdc++.h>
using namespace std;
// 祝机房各位同仁全员进队！
// 祝CCF蒸蒸日上！
// CCF求求你不要再收那么多钱了
int main(){
freopen("arena.in","r",stdin);
freopen("arena.out","w",stdout);
unsigned seed=chrono::system_clock::now().time_since_epoch().count();
mt19937_64 rnd(seed);
int n, m;
cin>>n>>m;
if(n==5){ cout << "5\n19\n7\n1"; }
else if(n==500) { cout << "126395"; }
else if(n==498) { cout << "1698571"; }
else if(n==5000) { cout << "132523761347"; }
else if(n==99998) { cout << "329154437110732\n894132907628644"; }
else{
int tmp;
for(int i=1;i<=n;i++) scanf("%d", &tmp);
for(int i=1;i<=m;i++) scanf("%d", &tmp);
scanf("%d",&tmp);
for(int i=1;i<=tmp;i++){
printf("%lu\n", rnd());
}
}
return 0;
}
// 那么，就这么结束了吧
// AFOed on 2024.10.26
// 也许我早就习惯了放手
// Goodbye, OI.FJ-S01153\color\color.cpp
这把再爆炸就可以准备退役了
防止成为最后一次导致没整过活，玩一下
//freopen("AFO.in", "r", stdin);
感谢cxy考前帮忙调整心态，现在根本不慌（假的）
希望不要挂分
最近真的输太多次了
去年也是60滚蛋
给CCF送了2000了，但愿有回报
*/FJ-S01221\arena\arena.cpp
//难说
//这真的是给我做的？
//AYIAYI
//SEEEE
//再见FJ-S01312\arena\arena.cpp
#include <bits/stdc++.h>
// wls & dls bless me!!!
//#define int long long, remember to change to signed main()
// don't use rep when the range is ll
#define rep(x, y, z) for(int x = (y);x <= (int)(z);x++)
#define per(x, y, z) for(int x = (y);x >= (int)(z);x--)
#define fvec(x, y) for(auto x : y)
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define pb push_back
typedef long long ll;
using namespace std;
void gmax(auto &x, auto y){
x = max(x, y);
}
void gmin(auto &x, auto y){
x = min(x, y);
}
const int inf = 0x3f3f3f3f, mod = 998244353;
void add(auto &x, auto y){
if((x += y % mod) >= mod) x -= mod;
}
/*
一名即将AFO的OIer的告白。
100+(60~100)+50+(0~10)=210~260.
今年题难度下降了，分数线绝对会上来，可我的成绩呢。
私以为大众分也至少会是210呢。
县一中特招条件就是CSP-S 1=，但既然题这么水的话，再加上挂分的可能性，也毫无希望了。
T2的卡常毁了我的OI梦。还是建议不要放多测，或者T<=5就足够。
OI带给了我太多美好的回忆，无论当初是好或不好，可到现在都弥足珍贵。
可现在我却需离OI而去了。
CSP-J的AK本是良兆，可到了下午我却以失败告终。
AFOed on 2024.10.26
Allen_123 Luogu uid=710031
如果S能1=我还会回来的。
*/
int n;
int main(){
freopen("arena.in", "r", stdin);
freopen("arena.out", "w", stdout);
scanf("%d", &n);
rep(i, 0, 25){
if(n <= (1 << i)){
ll ans = 0;
rep(j, 1, (1 << i)){
ans ^= (1ll * j * j);
}
printf("%lld\n", ans);
break;
}
}
// Goodbye, OI.
// I'll miss you.
return 0;
}FJ-S00956\color\color.cpp
}/*luogu 340940 yizcdl2357
NOI2024 喜提低分银后转了数竞，回来 OI 后状态 一蹶不振，故决定退役。
因此这次 CSP 是裸考，考得也不尽人意，100+100+50+68，考试结束前 5min 发现 T3 是简单题，记之。*/ 7. 不会物理人
FJ-S01167\detect\detect.cpp
//均加速运动是什么鬼啊 看不懂 不管了 骗分哈
//妈呀 T2相当于还要在考场学物理知识... CCF疯了吧 FJ-S00110\detect\detect.cpp
if (a[i] < 0)
{
cout << "我算你 的加速度";
return 0;
}8. 善人
FJ-S01312\detect\detect.cpp
// wow 竟然会了第二题
// CCF善
// 不是怎么还卡常啊啊啊 9. 科比
FJ-S01336\arena\arena.cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ioimprove(); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FILE(x); freopen(x".in","r",stdin);freopen(x".out","w",stdout);
signed main()
{
FILE("arena");
ioimprove();
cout<<"Man, What can I say? Manba out! CCF is a ***! SDF is the strongest school forever in the earth!!!\n";
cout<<"7142txwd1524txws";
return 0;
}10. Love 老师人
FJ-S00073\detect\detect.cpp
cout<<f;//然后不知道了QAQ
//求2等awa
//老师球球了，我会谢谢您的 11. 刻晴的狗
FJ-S01280\arena\arena.cpp
//You're right but Genshin is invented by Hihuyo in Shanghai.
//Keqing is really beautiful!!
//sto QWQ_SenLin orz
//T4 is too difficult for me to get any scores.
//It's truly a bad thing.
//But Keqing is really pretty!!
#include <iostream>
#include <cstdio>
using namespace std;
int T;
int main () {
freopen("arena.in","r",stdin);
freopen("arena.out","w",stdout);
//freopen("arena.in","r",stdin);
//freopen("arena.out","w",stdout);
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
//
// freopen("duel.in","r",stdin);
// freopen("duel.out","w",stdout);
//
// freopen("detect.in","r",stdin);
// freopen("detect.out","w",stdout);
//I can't finish T4 and T3.
//sto QWQ_SenLin orz
scanf("%d",&T);
if (T == 99998) puts("329154437110732\n894132907628644");
if (T == 5000) puts("132523761347");
if (T == 498) puts("1698571");
if (T == 500) puts("126395");
return 0;
} 12. 速通人
FJ-S00028\duel\duel.cpp
/*
16min做出来的t1我去！！！
*/ 13. 三体人（思维暴露在外）
FJ-S00091\detect\detect.cpp
每辆车被超速的位置是一段前缀/后缀
我们有n个区间，要求数m个点在多少个不同的区间中
直接扫描线
T1做完
T2：
你有k个区间，m个点，求最少的点使得所有区间内至少包含一个点
按照r排序，直接贪心即可
想了挺久，这辈子有了
问题在于找到距离右端点最小的检查点
双指针
T2略多几个点，怎么回事
我比答案更优？
感觉有很多分 FJ-S00140\arena\arena.cpp
void build(int l,int r,int now,int dep){//一开始大家没有现象编号，只有抽象编号
if(l==r){
tr[now].bh=l,tr[now].lun=dep;tr[now].xb=0;//如果只是记录数据本身的话，就不用管了
tr[now].free=1,tr[now].cb=l;tr[now].dir=2;
return;
}
build(l,mid,ls,dep-1);build(mid+1,r,rs,dep-1);
tr[now].lun=dep,tr[now].cb=tr[ls].cb+tr[rs].cb;
tr[now].free=1;tr[now].xb=0;
}
void upd(int l,int r,int now,int p){//插入a[p]=v
if(l==r){
tr[now].cb=0,tr[now].xb=l;//assert(tr[now].lun==0);
tr[now].free=0;return;
}if(p<=mid) upd(l,mid,ls,p);if(p>mid) upd(mid+1,r,rs,p);
if(tr[ls].free*tr[rs].free==1) tr[now].free=1;
else if(tr[ls].free==0&&tr[rs].free==0) tr[now].free=0;
else tr[now].free=2;
if(tr[now].dir==0){
//现象编号只能有一个（至少现在如此），抽象编号有无数个
//如果小的是擂主且小的只有现象：
//如果现象赢，则右边抽象编号被删除，只保留左边的现象编号
//如果现象输，右边同时继承现象编号和抽象编号
//如果有现象有抽象，那么右边一定是抽象：
//如果现象输，就意味着要么是抽象赢，要么是右边抽象赢，总之现象活不下去了
//如果现象赢呢？那么左边的抽象还能赢回来，同时记录所有编号
//你要注意一点啊！我们只需要到那个地方去看看就够了。
//别忘了，胜负只和擂主有关
if(tr[now].free==1) tr[now].cb=tr[ls].cb+tr[rs].cb;
if(tr[now].free==0){
tr[now].cb=0;
if(a[tr[ls].xb]>=tr[now].lun) tr[now].xb=tr[ls].xb;
else tr[now].xb=tr[rs].xb;
}
if(tr[now].free!=2) return;//维护完毕，cbxb都维护了
if(tr[ls].free==0){//落于现象
if(a[tr[ls].xb]>=tr[now].lun) tr[now].xb=tr[ls].xb,tr[now].cb=0,tr[now].free=0;
else tr[now].xb=tr[rs].xb,tr[now].cb=tr[rs].cb;
return;
}
//tr[ls].free=2
//就是有的啊！
if(a[tr[ls].xb]>=tr[now].lun) tr[now].cb=0,tr[now].xb=tr[ls].xb,tr[now].free=0;//ls的抽象（说不定）可以先润了
//然后把烂摊子给现在的cb
else tr[now].cb=tr[ls].cb+tr[rs].cb,tr[now].xb=0;//tr[rs].xb; //否则的话肯定没了
}
}
void mian(){
ans=0;//cerr<<r<<"?";
int g=1,p=1;while(g<=n){
upd(1,r,1,g);//cerr<<tr[1].free<<'\n';
while(g==q[p].first) res[q[p].second]=tr[1].xb+tr[1].cb,p++;
g++;
}fs(xx,1,m,1) ans^=(res[xx]*xx);cout<<ans<<"\n";
}
int pr[11],z[19][N],vis[11],cur;
void dfs(int now){
if(now>r){
// cout<<r<<'$'<<k<<'\n';
fs(i,1,r,1) z[0][i-1]=i;
fs(id,1,k,1){int ch=1;fs(i,0,(1<<(k-id+1))-1,2){
if(d[id][ch]=='0'&&pr[z[id-1][i]]>=id) z[id][i/2]=z[id-1][i];
else if(d[id][ch]=='0')z[id][i/2]=z[id-1][i+1];
if(d[id][ch]=='1'&&pr[z[id-1][i+1]]>=id) z[id][i/2]=z[id-1][i+1];
else if(d[id][ch]=='1')z[id][i/2]=z[id-1][i];
ch++;
}}
// if(k==1) cout<<z[k][0]<<'@'<<vis[z[k][0]]<<'\n';
if(!vis[z[k][0]]) vis[z[k][0]]=1,cur+=z[k][0];
return;
}
fs(i,0,k,1) pr[now]=i,dfs(now+1);
}
void mian0(){
ans=0;//fs(i,1,r,1) pr[i]=i;
fs(xx,1,m,1){
k=__lg(q[xx].first);if((1<<k)<q[xx].first) k++;r=(1<<k);
// cout<<k<<'?'<<r<<'?'<<q[xx].first<<'\n';
fs(i,1,r,1) vis[i]=0;cur=0;
fs(i,1,q[xx].first,1) pr[i]=a[i];
dfs(q[xx].first+1);//if(xx==2) cout<<cur<<"??\n";
res[q[xx].second]=cur;
}
// fs(xx,1,m,1) cout<<res[xx]<<"?";
fs(xx,1,m,1) ans^=(res[xx]*xx);cout<<ans<<"\n";
}
//没错，或者说，这个就是我想要的意思
//因为不可能扩张
void mian1(){
k=__lg(n);r=(1<<__lg(n));
fs(i,1,r,1) z[0][i-1]=i;
fs(id,1,k,1){int ch=1;fs(i,0,(1<<(k-id+1))-1,2){
if(d[id][ch]=='0'&&a[z[id-1][i]]>=id) z[id][i/2]=z[id-1][i];
else if(d[id][ch]=='0')z[id][i/2]=z[id-1][i+1];
if(d[id][ch]=='1'&&a[z[id-1][i+1]]>=id) z[id][i/2]=z[id-1][i+1];
else if(d[id][ch]=='1')z[id][i/2]=z[id-1][i];
ch++;
}}
fs(xx,1,m,1) res[q[xx].second]=z[__lg(q[xx].first)][0];
fs(xx,1,m,1) ans^=(res[xx]*xx);cout<<ans<<"\n";
}
inline bool scm(int x){return bool((1<<__lg(x))==x);}
//bool _ed;
signed main(){
freopen("arena.in","r",stdin);
freopen("arena.out","w",stdout);
// cerr<<(&_ed-&_st)/1048576.0;return 0;
n=read(),m=read();fs(i,1,n,1) b[i]=read();fs(i,1,m,1) q[i]={read(),i},flg1&=scm(q[i].first);
sort(q+1,q+m+1);k=__lg(n);if((1<<k)<n) k++;r=(1<<k);
fs(i,1,k,1) scanf("%s",d[i]+1);
//凹正解吧，我觉得正解直接合并就好了，还有1h40min
//就算没凹出来，250也在可接受的范围内了
//需要注意的是今年比去年还水？唉管他呢
//假设数给我凹进去了，那又怎样？
build(1,r,1,k);int now=1;
ft(i,k,1,-1) fs(j,1,(1<<(k-i)),1) tr[now++].dir=d[i][j]-'0',flg2&=(d[i][j]=='0');
//需要build吗？不需要吧，
//现在的问题在于说你跑一次还需要这么多？合并上来的复杂度是……
//每个节点需要维护什么？编号，现象世界的编号和，抽象世界的编号和，我是否自由，指向的方向，对应的轮数。
//也就是说，我们客观上是需要build的
t=read();while(t--){
fs(i,0,3,1) x[i]=read();
fs(i,1,n,1) a[i]=b[i]^x[i%4];
if(n<=8&&m<=8) mian0();
else if(flg1) mian1();//,cerr<<'?';
else mian();
}
return 0;
}FJ-S00140\color\color.cpp
void mian(){
n=read();fs(i,1,n,1) a[i]=read();int res=0;
fs(i,0,n,1) fs(j,0,n,1) f[i][j]=0;f[0][0]=1;//fij：最后一个蓝在i，最后一个红在j的答案
fs(i,1,n,1){
//假设i是蓝，i-1是蓝
fs(j,0,i-2,1) f[i][j]=max(f[i][j],f[i-1][j]+(a[i]==a[i-1])*a[i]);
//假设i是蓝，i-1是红
fs(j,0,i-2,1) f[i][i-1]=max(f[i][i-1],f[j][i-1]+(a[i]==a[j])*a[i]);
//i是红，i-1是红
fs(j,0,i-2,1) f[j][i]=max(f[j][i],f[j][i-1]+(a[i]==a[i-1])*a[i]);
//i是红，i-1是蓝
fs(j,0,i-2,1) f[i-1][i]=max(f[i-1][i],f[i-1][j]+(a[i]==a[j])*a[i]);
}fs(i,0,n-1,1) res=max(res,max(f[i][n],f[n][i]));cout<<res<<'\n';
}
signed main(){
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
int t=read();while(t--) mian();
return 0;
}
//如果大家都不管，理论上谁都能赢？
//没错，理论上谁都能赢
//所以……？
//不不不，我们现在要解决几个问题
//第一，对于纯空洞该怎么办，大家都填0上位，或者大家都填inf下位，就这么办
//如果有人是擂主，那么就看他行不行；否则大家就都有可能赢
//第二？ FJ-S00140\detect\detect.cpp
void mian(){
n=read(),m=read(),l=read(),k=1.0*read();cnt=0;//tid++;
fs(i,1,n,1) d[i]=1.0*read(),v[i]=1.0*read(),a[i]=1.0*read();//,(tid==20)&&(assert(a[i]<0),1);
fs(i,1,m,1) pos[i]=1.0*read();pos[m+1]=1e9;
// if(tid==11){
// cerr<<l<<' '<<k<<'\n';
// fs(i,1,n,1) cerr<<d[i]<<' '<<v[i]<<' '<<a[i]<<'\n';
// fs(i,1,m,1) cerr<<pos[i]<<' ';cerr<<'\n';
// }
fs(i,1,n,1){
if(a[i]==0.0) if(v[i]>k){
int fir=lower_bound(pos+1,pos+m+1,d[i])-pos;
if(fir==m+1) continue;
p[++cnt]={fir,m};
}
if(a[i]<0.0){
if(v[i]>k){
int fir=lower_bound(pos+1,pos+m+1,d[i])-pos;//第几个测速器是我上路时碰到的
if(fir==m+1) continue;
db s=pos[fir]-d[i];if(v[i]*v[i]+2.0*a[i]*s<0.0) continue;//已下班
db sd=sqrt(v[i]*v[i]+2.0*a[i]*s);
if(sd<=k) continue;//肯定是越早时测到的速度越大
db zd=min(1.0*l,(k*k-v[i]*v[i])/(2.0*a[i])+d[i]);//k<vi，前面一定是负数
// if(zd==(k*k-v[i]*v[i])/(2.0*a[i])+d[i]&&fabs(1.0*int(zd)-zd)<1e-9) zd-=1.0;
int sec=lower_bound(pos+1,pos+m+1,zd)-pos-1;//最后一个能拍到他的
if(zd!=(k*k-v[i]*v[i])/(2.0*a[i])+d[i]&&pos[m]==1.0*l) sec=m;
//最后一个小于zd的？
//还要在起点特判v=k!
//啥意思，如果到了那一刻的速度已经等于k了就润
// if(sec==m+1) continue;
//对啊，那时隐性的问题果然爆出来了
sec=min(sec,m);sec=max(sec,fir);
// if(tid==11&&i==3) cerr<<fir<<','<<sec<<'\n';
p[++cnt]={fir,sec};
// if(tid==11)cerr<<i<<' '<<cnt<<' '<<fir<<' '<<sec<<','<<zd<<'\n';
}
}
if(a[i]>0.0){
db qd=1.0*l;if(v[i]>k) qd=min(qd,d[i]);
//else if(fabs(v[i]-k)<1e-9) qd=min(qd,d[i]+1.0);//开局时没法查到
else qd=min(qd,d[i]+(k*k-v[i]*v[i])/(2.0*a[i]));//这个是我的起点标记，但是……？
// assert(v[i]!=k);
if(k-sqrt(v[i]*v[i]+2.0*a[i]*(1.0*l-d[i]))>1e-9) continue;
//如果开到底了还没好，就无须管理
// cerr<<fixed<<setprecision(8)<<qd<<','<<sqz(qd)<<':';
// db vqd=sqrt(v[i]*v[i]+2.0*a[i]*(qd-d[i]));cerr<<vqd<<','<<k<<','<<v[i]<<':';
// if(fabs(vqd-k)>1e-9) assert(vqd==v[i]&&v[i]>k);
int fir=lower_bound(pos+1,pos+m+1,qd)-pos;//第几个测速器是我上路时碰到的
// if(v[i]>k) assert(sqz(qd)==d[i]);
//多统计了？
// cerr<<fir<<','<<pos[fir]<<','<<sqrt(v[i]*v[i]+2.0*a[i]*(pos[fir]-d[i]))<<'\n';
if(sqrt(v[i]*v[i]+2.0*a[i]*(pos[fir]-d[i]))<=k) fir++;
if(fir>m) continue;
//continue;
p[++cnt]={fir,m};
}
}cout<<cnt<<' ';
sort(p+1,p+cnt+1,[](qj x,qj y){return x.r!=y.r?x.r<y.r:x.l<y.l;});int res=0,cur=-1;
fs(i,1,cnt,1) if(cur<p[i].l) res++,cur=p[i].r;//完了
cout<<m-res<<'\n';//变多了？
}
signed main(){
freopen("detect.in","r",stdin);
freopen("detect.out","w",stdout);
int t=read();while(t--) mian();
return 0;
}
//感觉t3难度更低，先看t3
//一个显然的dp是每次划分一段？一定是一段红
//50p！f[i][j]表示最后i红j蓝的答案，很好写
//想想正解吧，我觉得答案和ai有关?
//先开t2
//你这个可以直接判定出来
//算出他需要额位置FJ-S01076\detect\detect.cpp
/*
可以用n^2算法算出来第一问。
可以得到每个车会踩到几个测速仪，每个测速仪对应哪些车。
第二问：考虑贪心，猜的车越多的测速仪越首先保留，当然这不太对。比如123456车，c1-123,c2-2345,c3-456,显然保留c1和c3.
那怎么办呢。
车的犯罪是区间。保证每一个区间至少有一个点。我再猜一个贪心。从左往右，每当一个区间快要结束时，找一个能用的探测器把它爆了。这个探测器最好能检测尽可能多的车。
用线段树实现。加油，哈哈哈。
1
10 10 99858 982
39033 1000 -2
26456 999 -1
25617 37 -242
28141 1000 -1
27960 995 -6
1452 988 -58
44970 993 -322
16069 998 -1
26508 999 -1
44686 993 -1
1460 14938 17798 29360 42181 44971 55154 55534 74909 99858
*/- 题解人
FJ-S00133\detect\detect.cpp
/*
题解：
首先，我们需要为每一辆车鉴定它是否会被检测到超速，顺带求出每个超速仪分别查出了哪些车辆
至此，我们能解决第一个输出结果：多少辆车超速了
接着，我们需要让超速仪尽量少——利用搜索算法
所以，我们需要找出一系列超速仪，使得这些超速仪刚好能查出所有超速车辆且数量最小
设：dfs(x, s, n)：当前搜索到第x个测速仪，已经动用了n台超速仪，s为已经能查出的车辆集合
当s.size()=超速车辆数时，即为一种方案，多种方案的n进行比较，以此找到最优方案，输出最小的n
能不能优化？
用动态规划算法：dp[x]：只用x台超速仪，能查出的最多的车辆集合
易见dp[1]=一台超速仪能查到的最多的车辆的集合（即最强超速仪所查到的车辆集）
因此我们需要寻找最小的x，使得dp[x]=所有超速的车辆（即能查出所有车的最优方案）
dp[x] = setmax{任意一台超速仪所查出的车辆集 并 dp[x-1]} ，其中setmax{s}表示所有可能的s中，最长的s
其实“任何一台超速仪”并不是指所有的超速仪，而是指还没有被加入的超速仪。
一些技术细节：
检查车辆是否超速：当车辆行驶到s时，v是否大于限速
因为2as=v[t]^2-v[0]^2
所以vt^2=2as+v0^2
不要开根！开根会产生精度问题！只比较vt^2和限制速度^2也能知道是否超速！
需要警惕：车辆不能倒车，因此速度是大于等于0的
需要警惕：s=L-d
需要警惕：如果是加速，那么一旦有第一台超速仪查到，后续的超速仪肯定也能查到
需要警惕：如果是减速，那么一旦有第一台超速仪没查到超速，后续的超速肯定也查不到
*/FJ-S00133\duel\duel.cpp
/*
题解：
由于怪兽不可能同归于尽
因此最少也要剩下一头怪兽
我们可以把怪兽排序，并且从小怪兽开始，让实力最相近（但是小怪兽大）的怪兽攻击小怪兽
不妨将r排序为s
让s[1]攻击s[0]，s[2]攻击s[1]——这是最理想的情况
当然也存在s[1]=s[2]的情况，这种情况下：
要么s[1]和s[2]苟且偷生，要么后续存在两个相等的s[i]，可以分别把s[1],s[2]攻击掉
（也有可能只把s[1]攻击掉）
以上是怪兽会剩余出来的原理，我们来研究怎样实现
建立一个列表m，将输入的r排序并存入m（m中的每一个元素都附带有一个标记，用于表示该怪兽是否已经攻击过）
建立一个变量o，初始值为0。
只要o小于|m|，做以下事：
让i=o+1...|m|，遍历m[i]，如果：
有m[o]<m[i]，那么把m[o]删去，o不变
否则：
o加等于一
当o=|m|时，输出|m|，并退出程序
我们来实践一下（以样例二为例）
将r排序为m，得到m={136,136,136,136,136,136,136,136,2417,2417}
o=1, 发现m[1]<m[9]，且m[9]没攻击过人，删去m[1]，m[9]被标记为已发动攻击
o=1, 发现只有m[1]<m[10]，且m[10]没攻击过人，删去m[1]
一共删去了两个，剩余8个
怎么优化？
改装m：让m由<n,f>组成，其中r是攻击力，n是相同攻击力的怪兽个数，f是这群怪兽还有多少只没发动过攻击
要求m：不存在两个元素<n1,f1>和<n2,f2>，n1=n2
排序m：按照n从小到大排序
因此让m[1].n减去m[2].n、m[3].n。。。直到m[1].n=0为止（或直到m的所有元素的f都为0）
注意：在减去被攻击元素的n时，记得减去攻击元素的f
注意：如果m的所有元素都为0，可以直接开始清算
在全部执行完后，可以开始清点所有的n的和
时间复杂度为O(n^2)
*/- RP+=INF 人
FJ-S00164\arena\arena.cpp //必须给我蒙对！ 加纳！ RP+=INF BX
FJ-S00164\color\color.cpp //俺也不知道对不对，收卷前推的式子，我用俞高航十年阳寿蒙个5分！ RP+=INF BX
FJ-S00164\duel\duel.cpp //害 感觉会被常数卡，幸运女神给予我力量！！！ 暴力哥哥救救我吧！！！！ rp+=INF BX
- 为了使字节数便于辨认人
FJ-S00182\color\color.cpp
//#1-#4 20pts
//为了使字节数便于辨认，我加了这句话。
//为了使字节数便于辨认，我加了这句话。
//为了使字节数便于辨认，我加了这句话。
//为了使字节数便于辨认，我加了这句话。。 - 不会 dp 人
FJ-S00201\color\color.cpp
//暴力打好，20'
//我猜正解是dp，但是我做不出来
//如果不是当我没说(
//反正我只会写dfs... - 我重生了
FJ-S00791\*（4 题都写了）
//你说得对, 但是只有写了这句话的才是 FJ-S00791 的代码
//你说得对, 但是去年我是 FJ-S00579
//你说得对, 但是上午我是 FJ-J01085 - 艺术生
FJ-S00830\color\color.cpp
/* * ,
_/^\_
< >
* /.-.\ *
* `/&\` *
,@.*;@,
/_o.I %_\ *
* (`'--:o(_@;
/`;--.,__ `') *
;@`o % O,*`'`&\
* (`'--)_@ ;o %'()\ *
/`;--._`'--._O'@;
/&*,()~o`;-.,_ `""`)
* /`,@ ;+& () o*;-';\
(`""--.,_0o*`;-'&()\
/-.,_ ``''-...-'`) *
* /@%;o`:;'--,._ _.]'\
;*,&();@%&^;~`"'`o;@(); *
/()Emily & ().o@Robin%OCF\
`"="==""==,,,.,="=="==="`
__.----.(\-''#####---...___...-----._
'` \)_`"""""`
.--' ')
o( )_-\
`"""` `
*/FJ-S01608
/*
__________________
/ /|
/ / |
/_________________/ |
| | |
| | |
| Pink Rabbit | |
| | |
| | |
____________| | |______________
/ | _|_____|_ | / /|
/ | | | |/ / |
/______________| _____ |______________/ |
| |_____| | |
| |_____| | |
| _____/______ | |
| / \ | /
| / | \ | /
|______________ _/ _|_ \_ ______________|/
| __|__ | |
| | |
| Pink Rabbit | |
| | | |
| V | |
| Brown Rabbit | |
| _________ | |
| | | | |
| | \ / | | |
| | =O= | | |
| | o-o | | |
| |_________| | |
| | |
| (2015-2024) | |
| | |
_________|_________________|__|______
/ (_) \
/ STO STO STO s|s OTZ OTZ OTZ \
/ STO STO STO Z Z OTZ OTZ OTZ \
/ STO STO STO %%% OTZ OTZ OTZ \
/_____________________________________________\
|_____________________________________________|
*/- ZYQ's lover
FJ-S01014\arena\arena.cpp
// 不会，根本没看时间
/*
不想看题，总司令。
至少让我混个 2= 罢 /ll。
I love ZYQ.
*/FJ-S01014\color\color.cpp
// 17:17 - 没看
/*
dp 罢这是，但我 dp 学得很烂，转移方程不会写啊，打了个爆搜，/kk
I love ZYQ.
*/21. 食 noi 人
FJ-S01146\arena\arena.cpp //noi太棒了吧我的天比shi还好吃lalalallalalalalla
22. 祥林嫂
FJ-S01309\detect\detect.cpp //我真傻，真的
23. 心态好人
FJ-S01312\color\color.cpp
// To myself:
// 给我冷静下来，不要急眼，不然更没法1=
// 机子肯定比本机跑的快，不必担心T2了，就算不是后面多拿点分也能200
// 你这题拿个35/50pts下题拿个12pts不就把前面落下的40pts补回来了？心态保持好24. 凸人
FJ-S00373\arena\arena.cpp //printf("凸-_-%d %d\n",k,plu);
25. Viviana's lover
FJ-S01590\arena\arena.cpp
//300pts
//may be it`s my final result
//there`s no time for me to finish T4
//even if I did it before
//meaningful,I want a origin for the 5 years` hard work
//just......A "cout<<1;"
//and the reason why I work for OI until while(1)
//By the way,I Love Viviana forever
//Luogu id:qzyz_cyc26. 留名人
FJ-S00503\duel\duel.cpp //luogu Tis yuangong
27. 基建人
FJ-S01447\duel\duel.cpp（这里显示不是很正常）
/*
—————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
—————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
*/28. (首)
FJ-S01281\color\color.cpp /*1145141919810114514191981011451419198101145141919810114514191981011451419198101145141919810(首)a*/
29. AKIOI 人
FJ-S00094\color\color.cpp if (n>2000) puts("IAKIOI");
FJ-S00131\detect\detect.cpp puts("iakioi");
30. 你 AKIOI 人
FJ-S00304\arena\arena.cpp
//%%%UAKIOI%%%
//sto orz
//2024 CSP-S rp++
//31. WZT AKIOI 人
FJ-S00918\color\color.cpp printf("WZTAKIOI\n");
32. Python 人
FJ-S00704\duel\duel.cpp
#imculde<imcos>
use name;
int I[100000],N
def m(int a[]){
for(i)=
}
int main{
cin<<n;
for(int i=0,i<=n,i++){
cin<<I[i];
}
return 0;
}
33. %%% 人
FJ-S01608\arena\arena.cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("arena.in","r",stdin);
freopen("arena.out","w",stdout);
cout<<"%%%%%czh%%%%%\n";
cout<<"%%%%%Cey%%%%%\n";
cout<<"%%%%%cyz%%%%%\n";
cout<<"%%%%%C R%%%%%\n";
cout<<"%%%%%dje%%%%%\n";
cout<<"%%%%%wjh%%%%%\n";
cout<<"%%%%%P C%%%%%\n";
cout<<"%%%%%lzx%%%%%\n";
cout<<"%%%%%xhg%%%%%\n";
cout<<"%%%%%ctb%%%%%\n";
cout<<"%%%%%lwl%%%%%\n";
cout<<"%%%%%lrc%%%%%\n";
cout<<"%%%%%hzh%%%%%\n";
cout<<"%%%%%lsx%%%%%\n";
cout<<"%%%%%ljf%%%%%\n";
cout<<"%%%%%ljk%%%%%\n";
cout<<"%%%%%wwt%%%%%\n";
return 0;
}34. 义和团成员
FJ-01418\arena\arena.cpp & color\color.cpp
cout<<"在光绪二十六年，神助拳义和团\n";
cout<<"扶清灭洋\n";
cout<<"把洋人都赶出北京\n";
cout<<"非是邪，非白莲\n";
cout<<"请来各洞路神仙\n"; -1. 未分类
FJ-S00276\arena\arena.cpp
/*(300 && 300)
rp++ != rip++;
这首歌写在十年前的某个凌晨四点， 工作室，你一个人的时间
我会开始养生希望你还能
*/FJ-S01076\arena\arena.cpp
/*
听着周围选手一篇敲击键盘的声音，我陷入沉思。
如果这只是一场旅行，那很浪漫吧。
键盘声如雨声，淅淅沥沥，而后点点滴滴。
加缪和西西弗斯
西西弗只有他和他的石头
如果人生只有机房
*/ FJ-S01787\arena\arena.cpp
/*
写不出来，摆了QWQ，希望这次不要挂分，
让我好好上一次250qwq，虽然这个分数较去年没有一点进步，
今年第一题为什么像入门题，还是数据太水了，我怎么全过了
*/FJ-S00629\arena\arena.cpp
#include <bits/stdc++.h>
using namespace std;
#define maxN
#define yangzc99 AKIOI
int main()
{
fstream fin("arena.in",ios_base::in);
fstream fout("arena.out",ios_base::out);
int t;
fin >> t;
if(t == 5)
fout << "5\n19\n7\n1";
else if(t > 100)
fout << "你说得对，但是原神是一款由米哈游自主研发的全新RPG开放世界游戏，在这里，玩家将扮演一名称为“旅行者”的角色，开启在提瓦特大陆的旅行，同时揭开血亲失散的秘密......";
else
fout << "为什么不是样例？RNM,退钱！";
fin.close();
fout.close();
return 0;
}