NOIP2024 GD 迷惑行为大赏
照例，一些统计，使用 vsc。
共有 .cpp，这次没有 pascal 选手。
//.*freopen 在 182 文件出现 382 次，其中 GD-0228\traverse\traverse.cpp 贡献了 72 个，GD-0911 的每道题都贡献了 12 个。
(traverse|assign|edit|query)[1-10].in 共在 33 文件中有 44 结果。但是匹配上了 int query1(int l,int r){}。
AFO 共在 42 文件中出现 66 次。
std::vector 在 38 文件中出现 65 次。其中 21 次是我的。
CCF 共在 14 文件中出现 23 次。
orz 共在 11 文件中出现 38 次。
sto 在 21 文件中出现 88 次。居然比 orz 还多吗。
原来有
struct lstore {
int u, v, id;
}ls[100010];int depth[N],ancestor[N][LOG];
void dfs(int node,int parent){
depth[node]=depth[parent]+1;
ancestor[node][0]=parent;
for(int i=1;i<LOG;i++){
ancestor[node][i]=ancestor[ancestor[parent][i-1]][i-1];
}
for(int v:edge[node]){
if(parent!=v)dfs(v,node);
}
}三份代码贡献了一半的 sto，以 ancestor，stoid，stop 等形态出现。
luogu 在 27 文件中出现 27 次。
AK 在 13 文件中出现 22 次。
qwq 在 46 文件中出现 204 次。好多都是变量名。次数刚好跟 CSP 一致（
pts 在 15 文件中出现 24 次。
- 检查人
/*
期望得分:0pts
算法:
思路:
题目名称编辑字符串遗失的赋值树的遍历树上查询
题目类型传统型传统型传统型传统型
目录edit assign traverse query
可执行文件名edit assign traverse query
输入文件名edit.in assign.in traverse.in query.in
输出文件名edit.out assign.out traverse.out query.out
每个测试点时限1.0 秒1.0 秒1.0 秒2.0 秒
内存限制512 MiB 512 MiB 512 MiB 1024 MiB
测试点数目20 20 25 25
测试点是否等分是是是是
检查:long long? 1e9 bool? //freopen("neuvillette.in","r",stdin)????
*/- 你好呀
//freopen("你好呀！","w",stdin);
//feropen("别看了我不会，拜拜~","r",stdout);
//打暴力好麻烦啊）*@#……（*&@￥
//不想打了 - 空白人
#include<bits/stdc++.h>
using namespace std;
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
} - 还是空白人
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
fclose(stdin);
fclose(stdout);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll getInt() {
ll s = 0, f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
if (c == '-') f = -1;
for (; isdigit(c); c = getchar())
s = s * 10 + c - '0';
return s * f;
}
int main() {
// freopen("traverse.in", "r", stdin);
// freopen("traverse.out", "w", stdout);
fclose(stdin);
fclose(stdout);
return 0;
}- 有进无出人
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+100,mod=1e9+7;
bool f[N];
int a[3],b[3],c[3],_vx;
bool flag,del=1;
int T,n,m,v,x,d;
inline int in(){
//
return a*f;
}inline void out(int a){
//
}
void init(){
//
}
signed main(){
freopen("assign.in","r",stdin);
// freopen("assign.out","w",stdout);
cin>>T;
while(T--){
n=in();m=in();v=in();
//
}
return 0;
}- qaq
//Author:Dream_Flynn(luogu uid=578398)
#include<bits/stdc++.h>
using namespace std;
int n,ans;
string s1,s2,t1,t2;
namespace PlanBF{
struct Pr{
//int x,y;
string x,y;
};
//bool mp[2000005];
map<string,bool> mp;
queue<Pr> q;
inline void check(string str1,string str2){
int res=0;
for(int i=1;i<=n;i++){
if(str1[i]==str2[i]){
res++;
}
}
ans=max(res,ans);
}
void main(){
//
}
}
namespace PlanA{
void main(){
int ans=0;
for(int i=1;i<=n;i++){
if(s2[i]==s1[i]){
ans++;
}
}
cout<<ans<<'\n';
}
}
namespace PlanB{
const int N=1e5+5;
int s1cnt1=0,s1cnt0=0,s2cnt1=0,s2cnt0=0;
void main(){
//
}
}
namespace PlanC{
int ss1[100005][2],ss2[100005][2];
void main(int s1pos,int s2pos){
if(s1pos<s2pos){
swap(s1pos,s2pos);
swap(s1,s2);
swap(t1,t2);
}
ans=0;
ss1[0][0]=ss1[0][1]=ss2[0][0]=ss2[0][1]=0;
for(int i=1;i<=n;i++){
ss1[i][0]=ss1[i-1][0];
ss1[i][1]=ss1[i-1][1];
ss2[i][0]=ss2[i-1][0];
ss2[i][1]=ss2[i-1][1];
ss1[i][s1[i]-'0']++;
ss2[i][s2[i]-'0']++;
}
int L=s1pos,R=s2pos;
int s1l0cnt=ss1[R][0],s1r0cnt=ss1[n][0]-ss1[R-1][0];
int s2l0cnt=ss2[L][0],s2r0cnt=ss2[n][0]-ss2[L-1][0];
int s1l1cnt=ss1[R][1],s1r1cnt=ss1[n][1]-ss1[R-1][1];
int s2l1cnt=ss2[L][1],s2r1cnt=ss2[n][1]-ss2[L-1][1];
ans+=min(s1l0cnt,s2l0cnt)+min(s1l1cnt,s2l1cnt);
int s1m0cnt=s1l0cnt-min(s1l0cnt,s2l0cnt);
int s1m1cnt=s1l1cnt-min(s1l1cnt,s2l1cnt);
ans+=min(s1r0cnt,s2r0cnt)+min(s1r1cnt,s2r1cnt);
int s2m0cnt=s2r0cnt-min(s1r0cnt,s2r0cnt);
int s2m1cnt=s2r1cnt-min(s1r1cnt,s2r1cnt);
ans+=min(s1m0cnt,s2m0cnt)+min(s1m1cnt,s2m1cnt);
cout<<ans<<'\n';
//xie le 30 hang,mei guo yang li,xin tai beng le
}
}
void Dream_Flynn_T1(){
//
if(s1_all_same){
PlanA::main();
return;
}
/*if(s1_0cnt==1&&s2_0cnt==1){
PlanC::main(s1_0pos,s2_0pos);
return;
}*/
PlanA::main();
}
int main(){
freopen("edit.in","r",stdin);
//freopen("edit2.in","r",stdin);//freopen()//feropen()itn
freopen("edit.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--){
Dream_Flynn_T1();
}
return 0;
}
//wo xian zai hen mi huo,t1 dao di zeng me xie?
//hao nan,tai cai le,bu hui,qaq我现在很迷惑，T1 到底怎么写？
好难，太菜了，不会，qaq
（翻译）
- 你文操呢
#include <cstdio>
const int N = 100050, M = 1e9 + 7;
int C, T, n, m, i, j, k, ans;
void work2(){
scanf("%d%d", &n, &m);
for(i=1; i<n; i++) scanf("%*d%*d");
for(i=1; i<=m; i++) scanf("%*d");
for(ans=m, i=1; i<n; i++){
ans = (1ll*ans*i) % M;
}
printf("%d\n", ans);
}
int main(){
// freopen("traverse10.in", "r", stdin);
scanf("%d%d", &C, &T);
if(19 <= C && C <= 21){
while(T--) work2();
}
return 0;
}- 没被骗到，但是你好
//freopen("query.in","r",stdin);捕鼠笼
//freopen("query.out","w",stdout);
//40+35+0+10=85(1st past)
//20+25+0+0=45(2nd past)
//60+60+0+10=130(total)
//LG 755789 QwQ
//The sky blue archive!- 祝好
/*
//freopen Edit
//freopen dino
while(1); surf
孩子们 这里依然是Coverain（洛谷同名）
可能你们不熟悉我 但或许你们可能看过我发的一篇文章——《抽象代码落榜的看过来》
这一次的Noip就是我证明自己的研究的机会！如果你们能看到这段文字的话 那么应该是没落榜了罢 （大喜）
t1就花了我2h 先不打注释了 我要干t2了孩子们
haha man!what can i say ?Coverain out! t2看不懂一点孩子们！
t1! 你让我付出那么多的心血！你一定要AC啊！！！！
测评机！不要小瞧我与t1的羁绊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！
（\ /) ________
( 益 ) (edit.cpp)
| | /AC @---------
abaaba话说第二题输出0能骗到分吗。。。。。。。。。。
要不我还是检验一下t1吧
哇塞t1宝宝连1e3的数据都算对了 要不试试1e5的数据呢
宝宝你卡住了。。。 让我给你写个.in文件润滑一下
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊宝宝做对了啊啊啊啊啊！！！！！
宝宝要不要挑战一下极限呢？我要把整个edit2.in狠♂狠♂的塞进你的输入里面了
宝宝你怎么4,5,6，10的输出都错了？看来我得狠狠的调教你了！
赞美万机之神 赞美帝皇
话说机魂大悦的话 没有代码也能跑AC吗。。。
我这种3k时代的古人类写出来的代码 在未来会不会当作是考古依据呢？
废了 改不动了 预计50pts
不行 感觉万机之神和帝皇不管用啊
俺寻思这代码应该跑得动 Waaaaaaaaaaaaaaaaagh！
最后两分钟 AFO咯
*/- YOIMIYA
#include<bits/stdc++.h>
using namespace std;
vector<int> a[100086];
int main(){
//froepen('w', "query1.ans", "stdin");
//return
//froopen
//YOIMIYA
freopen("query.in", "r", stdin);
freopen("query.out", "w", stdout);
int n, q;
scanf("%d", &n);
int u, v;
for(int i = 1; i <= n; i++){
scanf("%d%d", &u, &v);
}
scanf("%d", &q);
while(q--){
printf("1\n");
}
return 0;
}
/* rp++
__ __ _______ __ ___ ___ __ __ __ ____
| | / / / ___ / / / / | / | / / | | / / / |
| | / / / / / / / / / /| | / /| | / / | | / / / /| |
| |/ / / / / / / / / / | | / / | | / / | |/ / / / | |
\ ' / / / / / / / / / | | / / | | / / \ ' / / /__| |
\ / / / / / / / / / | | / / | | / / \ / / _____ |
/ / / / / / / / / / | |/ / | | / / / / / / | |
/ / / /__/ / / / / / | / | | / / / / / / | |
/_/ /______/ /_/ /_/ |__/ |_|/_/ /_/ /_/ |_|
*/- 祝好
/*
挂分了，挂分了
真的 AFO 了
Goodbye, world!
*/#include<iostream>
using namespace std;
int main()
{
freopen("traverse.in","r",stdin);
freopen("traverse.out","w",stdout);
int c,T;scanf("%d %d",&c,&T);
srand(20070522);//纪念我摆烂的oi生涯，NOIP后AFO了
while(T--)
{
int n,k;
scanf("%d %d",&n,&k);
printf("%d\n",rand()%(n-k)+k);
}
}#include<bits/stdc++.h>
using namespace std;
int n,u,v,q,l,r,k;
int main(){
freopen("query.in","r",stdin);
freopen("query.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
cin>>u>>v;
}
cin>>q;
for(int i=1;i<=q;i++){
cin>>l>>r>>k;
cout<<(l+r+k)/3;
}
}
//AFO,再见了oi
//期望分数 60+40+0+0
//今年感觉比去年难好多，不开心 :-(
//也该回去搞文化课了，要是大学有机会再搞吧 /*
1
16
1111000000000000
1110000000011111
1111111111011111
1111110111111111
AFO on 2024.11.30
luogu uid157820
*/#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("query.in","r",stdin);
freopen("query.out","w",stdout);
cout<<"AFO";
return 0;
}/*
压缩包：Forget#2501
PDf：memory@2107
T1调不动 看来只有 100
fropen("","",in);
fropen("","",in);
GD-0335
I'm xiaoshui(yes), i'm a 蒟蒻。
Because I will AFO,i will write an articlue about this ,wait for you to look.
Can you celebrate me. Or you can play with me.
I hope thar I can forget OI before,but now sometimes I am happy to learn OI.
I enctoured many friends by OI.
It's memoriable for me toyour years.
Gooodbye OI.See you next life.
我英语不太好，将就看看
题外话 冬日绘版支持一下小帅计划
luogu:544383 tzjahinie
O:228942055
崩铁：115821736
零：19635543(?)
*/#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("query.in","r",stdin);
freopen("query.out","w",stdout);
cout << 3;
}
/*
我是0349，这是我的考号
我要开始写游记了
转眼三年初中的竞赛时光已经一去不复返了
上次在s组想着打完那次比赛，就不参加noip了
后来想了下，还有些没写的事情，不留遗憾，就再写一篇吧
每个人都得照顾到，那就一个个来写吧
致可爱活泼（被人称绿茶）的W同学：
记得当初你刚接触信竞，你说你没学过，但是看起来这很有意思
那时候时不时就举办一些小比赛，什么"喜闻乐见"，"信息队小白菜"印象中都出现过在比赛名字里
只可惜过了好久，我记不清楚了
当时你掌握的特别快，比赛里基本都是前三
有时你不会的题也会来问我
不过我真的很烦你的for循环从0开始哈哈哈
我打代码喜欢在符号两边加空格，会觉得大方整洁一点
你也很烦我这点说超级丑哈哈哈哈
可惜你后来挺早就退出啦
祝愿你能天天开心！
致爱踢球喜欢电音的C同学：
当时你是我们之中学的最多的一个人
记得最早的时候，对你印象最深的就是你打字好快哈哈
不过现在我也能打这么快啦
要数我们之中最遗憾的人只能是你了
你真的非常热爱信息，完全地投入进去了
可惜得到的结果总是不如意
当时下午一放学你就带我们去踢球来着
虽然可能踢不过另外那个竞赛班但是真的很开心
还会在宿舍里拿着你电脑一起打游戏
玩的最多的感觉就是坦克动荡了哈哈哈哈
虽然现在不在一个学校里了
但是祝你在这条路上一路顺风！
致胖胖的家里有两只猫的X同学：
刚进信息队的时候还觉得你普普通通的
后来不知道哪个假期
你打比赛开始天天拿第一
真的很厉害
我记得我妈还说，你每天无论再忙都会坚持做一道题
还让我也跟你学
不过我很懒的哈哈哈
当时说，比赛第一地请大家吃外卖
虽然你点的奶茶肯德基都不到你零头（
但是真的很难忘
你现在也去了另一个学校啦
祝你前程似锦！（还有祝你家猫健健康康哈哈哈哈）
致眼睛很大的F同学
你眼睛真的很大
你也真的很自信幽默（唐）
不过你比我厉害，当时J组你1=了我还没有（orz）
不过你也很早就退了
但是你现在跟我一个学校，所以你的篇幅压缩一下嘻嘻
祝你喜欢的女生也喜欢你（
致被夸赞信息队最帅的M同学：
你也还跟我一个学校，压缩压缩！
时间真的不够了还有好多人呢
现在是12：26，我还有30多分钟
当时刚接触的时候你也掌握的很快
貌似就跟W同学争第一
印象最深的是你报名J组忘记交钱了（
然后你就退了（
祝你打羽毛球赢过F同学（
致成绩很好下课总是去问老师问题的C同学：
你和W同学是很好的朋友
当时你们总是坐在一起
虽然貌似你信息没什么成绩只是来体验了一下
但是你whk真的很强（orz）
真的不知道为什么你总是能找到很好的问题问老师（
祝你问题越来越多（
致脸很圆喜欢摸脖子的X同学：
你真的很喜欢摸脖子 （
印象最深的是
我们一大群人围着你手机看偶像剧（
虽然剧情很史
但是一起看还是很欢乐的
你也很会踢球，虽然比不上C同学
不知道说什么跟你交流不太多嘻嘻（
祝你少看点偶像剧（
致胖胖的转学去了广西的Z同学：
虽然跟你不熟，你也很早就退了
但是怎么时不时就能看到你抄题解的代码被放到solution里哈哈哈哈
不知道你现在在哪里上学
当时你突然回来我们学校
我还差点没认出来你
不过你微胖的身材很特别（
祝你在另一个城市升官发财（
致很喜欢当主持人的Y同学：
你长得很高
你很喜欢当主持人
你很有领导风范
每次集体活动都能看到你很会领导（
班长什么的都是你当
你好早就退了信息队
还不知道你退出的原因呢
祝你以后当领导嘻嘻
致腿很长的Y同学：
你腿真的好长
你跳的也真的好远
当时你跳远拿了一金一银（orz）
你也很会踢球，但是也不如C同学（C同学暗爽）
当时你貌似和C同学在一个机构上信息？
说的算法我都听不懂（
噢还有你爸爸真的很热情
总是会拉着我们来合影哈哈哈
祝你跳的越来越远，你爸爸越来越热情
致特别爱看小说的L同学：
每次见到你你都抱着一本电子书
不过也真的很烦你的码风
你总是喜欢压行真的很丑（
我都调侃你是"城墙"形代码
你后来到初三就去搞whk了
听说你作文很厉害
一定是看小说看的
祝你能看到更好看的小说
还剩下10分钟
我回想了很久应该没漏人
要是漏了哪个人来找我我v你10r抵罪真的对不起啊啊啊啊啊！
今天太阳很温柔
今天坐在角落很适合写文章
今天不能睡到自然醒不太爽
今天大概是最后一天碰OI
今天虽然没过完，但是很开心
今天我1点半才能吃到饭，饿
今天是2024年，11月，30日
我会记住这一天
也会记住你们每一个人
我今天是0349
我要AFO了
-----送给我的OI生涯
*/ #include <bits/stdc++.h>
#define FF ;
using namespace std;
const int N=1e5+10;
string s1,s2,t1,t2;
//C8，afo了
int len,ans,c[N][6],qr1[N],qr2[N];//纯浪费空间
int lowbit(int x){
return x&(-x);
}
void add(int mk,int x,int val){
while(x<=len) c[x][mk]+=val,x+=lowbit(x);
}
int query(int mk,int x){
int res=0;
while(x) res+=c[x][mk],x-=lowbit(x);
return res;
}
struct node{
int tot1,tot0;
}f1[N],f2[N];
int totu1=1,totu2=1,num1[N],num2[N],c8[N],c9[N];
int main(){
freopen("edit.in","r",stdin);
freopen("edit.out","w",stdout);
// ios::sync_with_stdio(false);
// cin.tie(NULL);cout.tie(NULL);//没人觉得这两行压在一起很工整吗
int T;//多测 记得清空 虽然我也不知道我还能有什么清空的
cin>>T;
while(T--){
cin>>len;
cin>>s1>>s2>>t1>>t2;
bool ok1=1;
memset(c,0,sizeof(c));
s1=" "+s1,s2=" "+s2,t1=" "+t1,t2=" "+t2;
string pbf1="#",pbf2="#";
ans=0;
for(int i=2;i<=len;i++){
if(s1[i]!=s1[i-1])ok1=0;
}
// if(ok1){
ans=0;
for(int i=1;i<=len;i++){
if(s1[i]==s2[i]) ans++;
}
cout<<ans<<endl;
continue;
// }
//放弃了。
int pre1=1,pre2=1;
for(int i=1;i<=len;i++){
pbf1=pbf1+"#",pbf2=pbf2+"#";
add(0,i,s1[i]-'0');
add(1,i,s2[i]-'0');
if(i==1){
add(2,i,1);
}
else if(t1[i]=='0'){
add(2,i,i-pre1);
pre1=i;
}
else add(2,i,0);
if(i==1){
add(3,i,1);
}
else if(t2[i]=='0'){
add(3,i,i-pre2);
pre2=i;
}
else add(3,i,0);
if(t1[i]=='0') totu1++;
if(t2[i]=='0') totu2++;
if(s1[i]=='0') f1[totu1].tot0++;
else f1[totu1].tot1++;
if(s2[i]=='0') f2[totu2].tot0++;
else f2[totu2].tot1++;
num1[i]=totu1,num2[i]=totu2;
}
qr1[len+1]=len,qr2[len+1]=len;
for(int i=len;i>=1;i--){
if(t1[i]=='1') qr1[i]=qr1[i+1];
else qr1[i]=i;
if(t2[i]=='1') qr2[i]=qr2[i+1];
else qr2[i]=i;
}
pbf1=pbf1+"#";pbf2=pbf1;
// for(int i=1;i<=len;i++) cout<<query(3,i)<<endl;
for(int i=1;i<=len;i++){
FF
int tl1=query(2,i),tl2=query(3,i),tr1=qr1[i],tr2=qr2[i];FF
int cnt1=query(0,tr1)-query(0,tl1-1);FF
int cnt2=query(1,tr2)-query(1,tl2-1);FF
// cout<<"cnt1:"<<tr1<<" "<<tl1<<" "<<cnt1<<endl;
// cout<<"cnt2:"<<tr2<<" "<<tl2<<" "<<cnt2<<endl;
if(tl1==tr1 && tl2==tr2){//说明这个点两边都不让动
pbf1[tl1]=s1[tl1],pbf2[tl2]=s2[tl2];
}
else if(tl1==tr1){//s1不能动,看看s2的区间里有没有和它一样的
cnt2=query(1,tr2-1)-query(1,tl2);
// cout<<i<<" "<<cnt1<<" "<<cnt2<<" "<<tr2-tl2+1<<endl;
if(cnt1==1){
if(cnt2>0){
// cout<<"1i="<<i<<endl;
pbf1[tl1]=s1[tl1],pbf2[tl1]=s1[tl1];FF
if(pbf2[tl1]=='0' && s2[tl1]=='1'){
cout<<__LINE__<<endl;
f2[num2[tl1]].tot0++,f2[num2[tl1]].tot1--;
f2[num2[tl1]-1].tot0--,f2[num2[tl1]-1].tot1++;
}
if(pbf2[tl1]=='1' && s2[tl1]=='0'){
f2[num2[tl1]].tot0--,f2[num2[tl1]].tot1++;
f2[num2[tl1]-1].tot0++,f2[num2[tl1]-1].tot1--;
}
}
else pbf1[tl1]=s1[tl1],pbf2[tl1]=s2[tl1];
}
else{FF
if(cnt2<tr2-tl2+1){
// cout<<"2i="<<i<<endl;
pbf1[tl1]=s1[tl1],pbf2[tl1]=s1[tl1];
if(pbf2[tl1]=='0' && s2[tl1]=='1'){
// cout<<__LINE__<<endl;
f2[num2[tl1]].tot0++,f2[num2[tl1]].tot1--;
f2[num2[tl1]-1].tot0--,f2[num2[tl1]-1].tot1++;
}
if(pbf2[tl1]=='1' && s2[tl1]=='0'){
f2[num2[tl1]].tot0--,f2[num2[tl1]].tot1++;
f2[num2[tl1]-1].tot0++,f2[num2[tl1]-1].tot1--;
}
}
else pbf1[tl1]=s1[tl1],pbf2[tl1]=s2[tl1];
}
//把s2的l修改到这个点
add(3,i,i-tl2);
add(3,tr2,tl2-i);
// cout<<"case1,"<<pbf1<<" "<<pbf2<<endl;
}
else if(tl2==tr2){//s1不能动,看看s2的区间里有没有和它一样的
cnt1=query(0,tr1-1)-query(0,tl1);
// cout<<i<<" "<<cnt1<<" "<<cnt2<<" "<<tr1-tl1+1<<" "<<tr1-1<<" "<<tl1+1<<endl; FF
if(cnt2==1){
if(cnt1>0){
// cout<<"3i="<<i<<endl;
pbf2[tl2]=s2[tl2],pbf1[tl2]=s2[tl2];
// cout<<"tl2="<<tl2<<" "<<pbf1[tl2]<<endl;
if(pbf1[tl2]=='0' && s1[tl2]=='1'){
// cout<<__LINE__<<endl;
f1[num1[tl2]].tot0++,f1[num1[tl2]].tot1--;
f1[num1[tl2]-1].tot0--,f1[num1[tl2]-1].tot1++;
}
if(pbf1[tl2]=='1' && s1[tl2]=='0'){
// cout<<__LINE__<<endl;
f1[num1[tl2]].tot0--,f1[num1[tl2]].tot1++;
f1[num1[tl2]-1].tot0++,f1[num1[tl2]-1].tot1--;
}
}
else pbf2[tl2]=s2[tl2],pbf1[tl2]=s1[tl2];
}
else{
if(cnt1<tr1-tl1+1){
// cout<<"4i="<<i<<endl;
pbf2[tl2]=s2[tl2],pbf1[tl2]=s2[tl2];
if(pbf1[tl2]=='0' && s1[tl2]=='1'){
f1[num1[tl2]].tot0++,f1[num1[tl2]].tot1--;
f1[num1[tl2]-1].tot0--,f1[num1[tl2]-1].tot1++;
}
if(pbf1[tl2]=='1' && s1[tl2]=='0'){
f1[num1[tl2]].tot0--,f1[num1[tl2]].tot1++;
f1[num1[tl2]-1].tot0++,f1[num1[tl2]-1].tot1--;
}
}
else pbf2[tl2]=s2[tl2],pbf1[tl2]=s1[tl2];
}
//把s2的l修改到这个点
add(2,i,i-tl1);
add(2,tr1,tl1-i);
// cout<<"case2,"<<pbf1<<" "<<pbf2<<endl;
}
}
ans=0;
for(int i=1;i<=len;i++){
if(pbf1[i]!='#'){
if(pbf1[i]==pbf2[i]) ans++;
cout<<i<<" "<<ans<<endl;
continue;
}
int tmp1=f1[num1[i]].tot0,tmp2=f1[num1[i]].tot1;
int tmp3=f2[num2[i]].tot0,tmp4=f2[num2[i]].tot1;
if(tmp1&&tmp3){
ans++;
f1[num1[i]].tot0--;f2[num2[i]].tot0--;
}
else if(tmp2&&tmp4){
ans++;
f1[num1[i]].tot1--;f2[num2[i]].tot1--;
}
cout<<ans<<endl;
}
cout<<ans<<endl;
}
return 0;
}
/*
我就知道会考点字符串，c8
反正这里把固定的字符当边界然后每一段里面的字符都是可以任意移动的吧
这个是个贪心还是dp，我觉得可以贪心
不管了321上暴力
老天啊我真的想要NOIP1=和NGOI1=
咦我是不是可以预处理一个前缀和（是不是单点修改区间查询啊？
新建一个cpp测试一下我的树状数组是否正确(ok)。
考点dev的格式化怎么是好的
线性处理出来 每个点的左边界和右边界(ok)
我想的是，每次遇到当前字符不能动的就尽量满足它，如果两边都不能动就认命
经过这样的处理可以让两边不能动的区域变成一样的
然后一样长的能动的区域ans+=min(能动的1，能动的0)
这题怎么有点像我看kpop舞台拉郎：这里有1，这里有0，好了我要让他们配对
我要哭出来了怎么这么困难，你们是不是都会了
@poembelief @Jasmine_Xu
求你们了救救我吧
AFO了真AFO了疑似成为全市最菜女选手
*///Away from OI
// by McIron233//若两个数都不确定，方案 v*v
//若第一个数确定，第二个数不确定，方案数v*v ,但是有v个方案会使下个数进入确定状态
//若第一个数不确定，第二个数确定 方案数v*v
//若两个数都确定 方案数 (v-1)*v + 1
//2 2 2 2 的方案数为27
//x x x x 的方案数为64
//2 x x 2 的方案数为60，分析
//实际上分成了
//x x 2
//x x 2
//1 x 2
//2 x 2
//分析1 x 2的方案数
//分成了
//x 2
//x 2
//1 2
//2 2
//2*v*v + 2*((v-1)*v + 1)
//重新分析2 x x 2
// 2*v*v*v*v + 2*(2*v*v + 2*((v-1)*v + 1))
//带入v=2 ，得60
//11:20了
//看看2 x x x 2
//x x x 2
//x x x 2
//1 x x 2
//2 x x 2
//易得这个和数字本身是什么没关系，和数字是否确定有关系
//对于形如2 x x ... x 2 (n个x)的数列，设计如下函数
//f(n) =
//2*v^2^n + 2f(n-1) n>=1
//(v-1)*v + 1 n==0
//全对！多么富有基米精神！ 但还是不如农神
//11:26 开始敲
//19和20不能用记忆化，有点头疼
//用区间优化，他要是用2 x x... x 2 (10^9个x）来卡人就有点刻晴了
//会超时，难受，再看看
//算了，就这样吧，AFO了 #include <iostream>
#include <cstdio>
#include <vector>
#define pb push_back
using namespace std;
const int N=105;
int Takanashi_Hoshino, AFO, n, k, ans, u, v, rt, l[N], r[N], cnt;
bool vis[N], flag;
vector<int> e[N];/*
AFO
it = journey
it can be painful awesome of good
if it's painful, then it's awesome
if it's awesome, then it's good
how many solution can the journey be?:)
*/// this is the last code before AFO... maybe #include<bits/stdc++.h>
using namespace std;
int c,T;
void sol(){
printf("%d\n",T);
}
int main(){
freopen("traverse.in","r",stdin);
freopen("traverse.out","w",stdout);
scanf("%d %d",&c,&T);
while(T--) sol();
return 0;
}
/*
12:51 AFO
炸了 能拿多少分全靠狗运
算了 大家并没有那么脆弱
最后 祝学长、队友、学弟们拿到好成绩吧！
再见
*/ //最后一次打信息竞赛，死于死磕第一题，看来只能走文化了，AFO
//“还在争，还在争，争个不停的”....下次再也不争了（当然没有下次了）
//Luogu:_None
//有兴趣就交个朋友吧——致看公示代码的朋友 // SPDX-License-Identifier: Unlicense
// Author: Bingwu Zhang <[email protected]>
/**
* 9:49了
* 高二老登AFO前的最后一次参赛
* T1不会做，哎，TLE
* https://xtexx.eu.org
* The Last Dance
* 12:51了
* Goodbye, AFOed
* 感谢两年来支持我的各位老师和同学
* Sat, 30 Nov 2024 12:53:52 +0800 @ 中山纪中
*/#include<bits/stdc++.h>
using namespace std;
signed main(){
// FurinaHateComma luogu 763542
// write at lst 3 min
// in order to remember cjk
// id = Citilaly_qwq
// he AFOed
}//可能要退役了，退役快乐。
//might afo sometimes later
//wish to happy in the after days
//NOIP T2 放容斥 dp？
//炸了啊。准备退役了。
//T1 没调出来。T2 没写完。
//T1 最后 15min 调出来了。但是 T2 真的寄了。
//也许真的是能力问题吧。
//Luogu uid 514700。
//再见。
// 来自收集人：不知道为什么第一行与其它几行编码不同int mian()
//freopen("query.out","r",stdin);
I am a Grade 9 student.
After this NOIP,I will AFO.
I know I can not get a good grade in the NOIP.
Maybe 100 points,or less than it.
I can not stop me from AFO.
If there are someone looking it,I can be little warm.
Luogu ID:mywzj_mo
*//*
8:38 T1 可以切 100pts?
8:58 A打完
10:03 厕所回来找到B的hack了(其实没找到)
11:24 打完T2的暴力回来写T1
11:27
只剩下一个半小时了，我能做什么呢？
B死活调不出来
11:58
如果有人看到这个那就帮忙发出来吧谢谢
最后一小时了，能写点什么呢？
可能真的要暂时AFO了，从去年搞OI搞到现在，有什么进步呢？
从CSPS二等奖到CSPS二等奖，从NOIP2023 90pts到NOIP2024 20pts
whk已经退步了200年级排名了
搞OI+WHK已经把我人搞垮不知道多少次了。
教练说，以我的水平，在考场睡4个小时，
写半个小时的题目都能三等奖，
但是结果T1 性质B都调不出来。
12:56
看起来交卷的时间就要到了呢。
我这个OIer，也该准备谢幕了。
话虽说的这么轻松，但面对退役，果然还是有些不舍啊。
再见，信息学竞赛，
希望你喜欢这三年来属于你的戏份。
---wwwidk1234(luogu uid=728483)
*/- 琵琶行人
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("assign.in", "r", stdin);
freopen("assign.out", "w", stdout);
cin >> T;
for(int i = 1; i <= T; i++){
cout << 0;
}
/*
60pts+0pts+0pts+36pts=寄
AFO，启动！
自言本是jhy，家在致明楼中住。
十三学得数论成，名属创美第一部
证毕每教陈海服，洗发每被蒋楠妒
五大竞赛争缠头，一证答案不知数
电脑键盘敲到碎，代码bug修到哭
今年信竞复明年，高中时光等闲度
代码爆零信心死，暮去朝来大脑故
屏幕题目思路稀，老大摆烂作了土
竞赛重利轻别离，前月浮梁学文化
学完文化期中考，排名八百不敢看
夜深忽梦少年事，梦啼妆泪红阑干
我打竞赛已叹息，又闻此语重唧唧
同是天涯信竞人，相逢何必曾相识
我从去年辞南屏，谪居卧病一中里
一中地辟无游戏，终岁不闻音乐声
其间旦暮闻何物，超雄宿管罗凤秀
春江花朝秋月夜，往往长坐机房中
岂无同学乱唱歌？呕哑嘲哳难为听
今夜闻君信竞语，如听仙乐耳暂明
莫辞更坐打一曲，为君翻作《信竞行》
感我此言良久立，却坐促键键转急
凄凄不似向前声，满座重闻皆掩泣
座中泣下谁最多？泰国司马青衫湿
*/
}- 游记人
// contest record(lyy plz dont roast me)
//
// 8:30 6(^) & 7(&) on my keyboard are swapped wtf
// i cant write ifs well now
// "&&" -> smiley face
// 10:18 IT HAPPENS ALL THE TIME
// THOSE SMILEY FACES
// 10:38 how do i use freopen
// 10:54 hey we gettin 3/10 on sample 2
// gg guys we're so doomed
// 11:11 gave up , solve A & B and im leavin
// 12:29 just finished t4 A O(n^2) solution , from which 0 pts expected
//
// i am if realm big god hand dragon hand
// if if if if if .jpg
//
// btw probably AFO after this , for gotten caught in 4K playin MK48 in training. yay- 我喜欢这个【数据删除】NOIP
if(n<=10){
for(int i=0;i<(1<<n);i++) abl1[i]=ck1(i),abl2[i]=ck2(i);
for(int i=0;i<(1<<n);i++) for(int j=0;j<(1<<n);j++) if(abl1[i] && abl2[j]) ans=max(ans,n-pc(i^j));
}else if(flag1){
for(int i=1;i<=n;i++) ans+=(s1[i]==s2[i]);
}else if(flag2){
assert(m1==m2);
for(int i=1,l,r,tp;i<=m1;i++){
l=q1[i].l,r=q1[i].r,tp=a1[l]-'0';
if(tp){
ans+=min(q1[i].sum,q2[i].sum)+min((r-l+1)-q1[i].sum,(r-l+1)-q2[i].sum);
}else{
for(int j=l;j<=r;j++) ans+=(s1[j]==s2[j]);
}
}
}else{
puts("I love this shujushanchu wisdom T1 problem maker.");
puts("Which shujushanchu shujushanchu human makes this shujushanchu T1?");
puts("shujushanchu NOIP");
puts("AFO!!!");
}
printf("%d\n",ans);- rp++++++++
/*
10:57 maybe 15 pts(but quite hard), see next timu first
12:11 don't know how to write, bailan
12:14 suijihua, qidong
12:16 find it can't AC any yangli XD
*/
/*
maybe 125~133 pts, at most 2=
if so i'm pleased, but i'm still too vegetable
rp++
rp++
rp++
rp++
rp++
rp++
rp++
rp++
rp++
rp++
rp++
don't AFO
don't AFO
don't AFO
// 省略大量删除
rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++rp++
suijihua don't fail me now
suijihua wo ai ni
suijihua wo ai ni
suijihua wo ai ni
suijihua wo ai ni
// 省略大量相同
ohhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
follooooooooooow me!
me:dzd is love!
you:dzd is love!!
me:dzd is power!
you:dzd is power!!
*/- 感谢
// start at 9:38
// finish at 10:22
// expected point : 100
/*
现在是 10:24，停下来稍微写点东西。
大概赢了。当 T2 70 分暴力跑过大样例时，狂喜席卷我全身。
现在估分 200，只要 T1 不挂，后面随便写点暴力，女生全国前十大概拿下了吧。
这场怎么那么难啊。不会是绿紫紫紫吧。KDOI 模拟的还真好 /hsh
Qingyu 的博客中曾说，要珍惜自己通过刻苦训练获得的赛场上的时间。但当我真的做到了，还是忍不住要停下来感谢一下帮助过我的人。
谢谢 xht 哥哥，给了我鼓励和训练的方向，让我感受到了被支持。
谢谢 -95 老师，我本以为退役前要一个人走下去了。
谢谢同学们，学弟们，教练们。和你们讨论总是愉快的。
祝你们好运。
272。会赢吗。
*/- orz 人
int sto_explore_orz(int a,int b)
{
int ans=1;
while(b)
{
if(b&1)
{
ans=1ll*ans*a%p;
}
a=1ll*a*a%p;
b>>=1;
}
return ans;
}int poworz(int q,int w){
if(w==0)return 1;
if(w==1)return q;
if(w==2)return q*q%orz;
return poworz(poworz(q,w/2),2)*poworz(q,w%2)%orz;
}- find zuofa wrong again
//10:00 pass xingzhiA
//10:15 find zuofa wrong
//10:19 many WAs
//10:26 find zuofa wrong again
//10:33 WA on #5
//10:36 pass big sample O(mlogn)*t=O(tmlogn) (logn from quickpow)
//sto cyq,the maths master,rating higher than tourist,will solve it easily (if he is still awake) orz//0110111100
//1111111100
//9:03 pass big sample O(n)*t=O(tn)
//sto faker wcy,will know how to do it and program it in less than 10min (if his brain work normally) orz//11:20 O(nlognlogn+qnlogn)=O(qnlogn) or nlognlogn+q(\sum r-k-l)logn might 20~64pts expect 32pts
//xingzhiA:O(qnlogn)->O(xuanxue) (16pts+[0,16]pts)
//xingzhiB: qnlogn->qlogn O(nlognlogn+qnlogn)->O(nlognlogn+qlogn) (12pts)
//sto AKer wsy will gain 100pts here (if he do not fake) orz
//wsy is shine,thanks wsy- 你是奶龙
#include<bits/stdc++.h>
using namespace std;
int mian(){
freopen("query.in","r",stdin);
freopen("query.in","r",stdin);
freopen("query.out","r",stdout);
freopen("query.out","w",stdin);
//我故意的
//我要流萤
return 114514;
}
//rp++
//这题懒得骗了
//预祝 @jiangzenyu NOIP2024 rp++
//我要流萤
//“飞萤扑火，直至一切，燃烧殆尽！”
//“我将，点燃星海！”
//“为战而生，为生而战！”
//我好神经
//自此，一锤定音；尘埃，依然落定。
//sto%%%kkksc03%%%orz
//我要上魔怔榜
//小恐龙真好玩(
//不行，还得再疯一点
//第五人格，启动!
//我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙， 我是奶龙，我好唐。
//已经1.3k了，我好无聊。
//看到这的人都去玩《饿殍：明末千里行》!立刻!马上!
//考试结束了，我真是唐完了。 - BIT 爱好者
/*
9
101111111
100111000
110111011
011111111
我是树状数组厨！！！
luogu: LDR___ 780377
树状数组是我的！！！
树状数组是我的！！！
树状数组是我的！！！
给我上迷惑性行为大赏吧
本来想写个单log树状数组RMQ的，但是没时间了。。。
*/ - 你也是奶龙
/*
9:52:43 开题。
我真的纯乃龙。虽然思考了半天 D 暴力，但是 C 的 40 分暴力我怎么写了快 2h
我就是奶龙，我就是奶龙，这下真的只能退役了
我宣布，luogu uid 61158 就是奶龙！！！！！！！！！！！！！！！
啊考前一天立下 flag 如果纸盒和 tder 考的比比我高要请他们吃外卖来着
啊啊啊我的钱包……
写 D 暴力了
最后一次 noip 只能以 100 + 100 + 40 + 32 收尾了吗
好不甘心，好难受，心态有点崩溃。
不管，最后一小时写完 D 暴力就行。
这么顺利的前两个提被 C 暴力毁了。
//freoepn 上述是奶龙内容
12:53:49 结束了，最后一次 noip。
之后不确定能不能去 WC。APIO 肯定会去打。
不过我是高二老灯了，这也没办法了吧。
包拿不到两倍对线内的。复课文化课了。之后可能晚上去机房或者只有周末再学学了。省选会去考，不过希望不大。
subetewo owari.
AzusidNya. 2024/11/30
12:26
我回来了。因为 D 32 分暴力 20 分钟写完了。
再看看还有没有能打的部分分。
现在能做的有什么？
k = 1，链，菊花。
共有 40 分。
所以我想要什么？
k = 2。看看能不能转化上把。
最后还有 15 分钟的时候跑虚拟机。
应该是，在一些情况的时候答案和 k = 1 一样
否则不同。
这里的一些情况是什么啊
我找不到条件了。以我的实力应该不足以在 20 分钟内再拿下这题多少分了。
现在要干什么？看看 D 把。
*/- luogu 游记合集
//[l,r] for every "free"block
//freopen()
//froepen()
//edit2
//bits\stdc++.h
//mian
//slvoe
//x1,y1,x2,y2,next,node
//enjoy my blog ，luoguid：560807，木棉絮123
//qq:2260065019，是福瑞/furry，欢迎扩列（
/*
感觉有点麻烦，四道题看下来没有一道一眼题。
压缩包密码是 Forget#2501，PDF密码是 memory@2107，被扎心了。
### T1
值域为0和1，感觉是个性质。
可以用前缀优化。
完了不会，直接二十分跑路
高二已经没有复活币了，这次也拿不到一等了。
没事反正一直都是拿二等这下变成二流傻瓜了（doge）
三道题调半天调不出来，不知道能混多少分。
反正t3二十分和t1六十分肯定有。t2的容斥写出来了但是过不了，预计20分。
按自己挂分的本领铁定只有40分了。
有点难受，也释然了，毕竟自己天天摆烂。
已经不是很想搞oi了。
还是退役好。
这次1=分数线至少120分。而且t1应该不难。
没关系，其实都一样的。
你说你不想在这里，我也不想在这里。
但……
难度猜测：绿蓝紫蓝
*/ //Author:Dream_Flynn(luogu uid=578398)// 打的最差的一次 一个题都没切 下个赛季再见 qaq
// luogu uid : 752017 name : buowen123
/*
时间过得真快, 转眼间 NOIP 就到来了
考完后停课就结束了 就要回去学 whk 了
希望今年一等线能低一点吧
T2 应该是会的，我的思路大概没有假
就是最暴力的 dp[i][0/1][0/1] 表示前 i 个标记
i 处于一条“真链”/“不定链”上，且这条链搭在/没打在 i 处
链表示传递关系 x[i]=a -> x[i+1]=b -> x[i+2]=c...，
而链是否真取决于一元关系 不过我没时间写了
代码实现能力还是太弱了啊
就这样吧 祝大家未来可期
*/ /*
Luogu uid: 818165
qiu guan zhu!!!!!
100 + 100 + 4 + 8 = 212
RRRRR PPPPP + +
R R P P + +
RRRRR PPPPP +++++++ +++++++
R R P + +
R R P + +#include<bits/stdc++.h>
using namespace std;
signed main(){
// FurinaHateComma luogu 763542
// write at lst 3 min
// in order to remember cjk
// id = Citilaly_qwq
// he AFOed
}int mian()
//freopen("query.out","r",stdin);
I am a Grade 9 student.
After this NOIP,I will AFO.
I know I can not get a good grade in the NOIP.
Maybe 100 points,or less than it.
I can not stop me from AFO.
If there are someone looking it,I can be little warm.
Luogu ID:mywzj_mo
*/- AK 人
#include<bits/stdc++.h>
using namespace std;
int c,T;
signed main()
{
freopen("traverse.in","r",stdin);
freopen("traverse.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cout<<"I AK NOIp2024."<<endl;
//My Luogu uid is 765763,I AK NOIp2024.
//If you GuanZhu me,you will AK NOIp2024,too.
return 0;
}- big yangli 人
//big yang li ban tian pao bu guo qu
//ran hou fa xian
//mei you qing kong
//duo ce bu qing kong,bao ling liang hang lei
//CCF I love you kkksc03 I love you
//NOIP2024 rp++
//my luogu id:745358- 加油！
/*
10:56 maybe can pian 25 pts, see next timu first
11:01 try baoli
11:26 done,25 pts get,now 125,try T4
*/
/*
i still continue to study OI because of MST(luogu 815497) encouraged me last year when i got low pts
but this year she can't come to NOIP
so MST, if you see this in daimamihuoxingwei, it's my courage to you, you can still go on
*/- 不可以奶龙
/*
9:17:11 开题
我不想成为乃龙！！！！！！！！！
好像是我擅长的组合数学提！
好耶！
这感觉就像无亚凹日向 15 爆 13 无 miss 或者 15 爆 14 时打出了 15 爆 15 一样。
9:41:30 写完啦！开条
9:48:25 怎么这么顺利，一遍把大衍历过完了。
这个也不会拍啊。
还有三小时，后面还有两个提，又是在我。
其实 200 一等已经稳了，但是这其实很危险
对线肯定还在高不可攀的地方，说不定现在人 Shui_dream 已经 AK 了（（（
呜呜 Shui_dream 大神/bx/bx/bx/ll/ll/ll
*/- 祝好
/*
void flower_for_my_last_competition(int the_last_year_of_NOIP){
again.I(am_feeling(desperate)){
however_a_power(push_me_ahead);
I.wish( (the_person.see_this_text? find_out_the_beauty_of_the_world:AK_IOI) );
I.wish( a_even_better_life_for_everyone_to_live );
I.wish( all_of_you , prevented_from(disaster_and_failure) );
I.wish( a_peaceful_world.where(has_no_war_and_enemy) );
however_this_cannot_be_seen_by_myself();
}
all_of_all(The_best_wishes);
return ;
}
By high school Senior2 student *mglf;
24/11/30 12:52:48;
*/- orzzzzzzz
/*
these problem is toooooooooooooooo difficult for me!!!!!!
help
father CCF give me 100 pts plzzzzzzzzzzzzzzzzzzzzzzz
TYS AK NOIP I think
my classmates AK NOIP I think
ZK AK NOIP I think
*/- (:з)∠)
#include <bits/stdc++.h>
using namespace std;
int qwq[114514];
int main() {
freopen("ccf.in", "r", stdin);
freopen("ccf.out", "w", stdout);
/*
while(1)
rp++;
*/
return 0;
}
/*肝不动了，不想写了，吐会槽先
朝为想，暮为念，而你为朝朝暮暮
爱是自由意志的沉沦
智者不坠爱河，除非怪盗基德
喜欢看魔术的人只不过是喜欢被骗的感觉罢了
真相只有一个！
这是奶龙，贝利亚和胖猫举办的吧 ……
_Error_and_Bug_到此一游^_^
考试祭：玩游戏被警告一次 qwq
都给我去玩第五人格！
我知道你们会看到， 因为我一直在视奸你们！(╬▔皿▔)╯
_(:з)∠)_
_(:з)∠)_
_(:з)∠)_
_(:з)∠)_
_(:з)∠)_
_(:з)∠)_
_(:з)∠)_
_(:з)∠)_
_(:з)∠)_
我承认我成分复杂，但我相信在座的各位比我更抽象q(≧▽≦q)
最后一次noip了，退役！！ - /jk
- 救救我，CCF 先生！
/*
I love Firefly.
I love Nahida.
CCF,helps me!
I shall ... set the seas ablaze.
*/- 考场不是给你写回忆录的地方，请尊重你通过漫长的训练换来的考试机会
/*
//freopen("query2.in","w","stdout");
//freopen("query.txt","r",stdin);
freopen("adit.in","r",stdin)
freopen("asign.in","r",stdin)
int mian()
return 1;
kkkcs03
lin_toto
#include<bits\stdc++.h>
int x1,y1;
int size;
cout<<rand()<<'\n';
__int64 n;
while(1){}
while(true){}
I love ccf
I love NOIp
考场不是给你写回忆录的地方，请尊重你通过漫长的训练换来的考试机会
10:25 通过前两题大样例
10:30 T3好难，放弃T3
10:42 T4好难，拿32pts跑路
11:10 写写停停地打完了2.4k的树剖+线段树，此时还有110min结束
目测：
T1黄
T2绿
T3不知道因为没想
T4性质B绿，性质A蓝，整体蓝或紫
那我232真能全国前20%吗？
感觉旁边几个人全都好强，对面的人也好强，感觉T3T4起码也打出了特殊性质
更不用说高中生了..
反正拿不了奖
*/- niop--
ture!!!!
kkk, xiaofentu, chen_zhe, noip++, niop--, cspjs+-;
I love ccf!
yuanshen, qidong
shutdown -s -t 0
system(.txt)
zip key: Forget#2501
pdf key: memeory@2107
$$$ccf$$$
}
}
*/- 表白 CCF 人
#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("query.in","r",stdin);
freopen("query.out","w",stdout);
printf("I love CCF");
} - 获得 8 pts 的好成绩!
/*
首先注意到一个性质
对于点集 V
如果往里面加新的点，那么 V 的 LCA 的深度是单调不增的
所以显然我们只需要 check 长度恰好为 K 的子区间
那么考虑最暴力的做法，O(N^2 log N) 的处理每个问询的答案，可以通过 n,Q<=500 的数据
获得 8 pts 的好成绩!
然后考虑性质 A
树的形态是一条链
我们先算每个节点的深度
然后做如下转化
有一个序列 d1~dn
它是 1~n 的排列，并且保证 d1=1
每次问一个区间 [l,r] ，问里面所有长度 >=K 的子区间 [l',r'] 的区间最小值中的最大值是多少
考虑二分答案
我们二分 v 然后判断能否找到一个长度 >=K 的子区间，使得这个子区间的最小值至少是 v
现在看来特殊性质 A 不是很好写的样子
考虑 n,Q<=5000 的情况
需要在 O(N log N) 左右回答每个问询
由于 lca 是可重复贡献的
考虑倍增优化
处理出 act[u][i] 表示 [u,u+2^i-1] 内的元素在树上的 lca 是哪个节点
这个东西可以在 O(N log^2 N) 的时间内预处理出来
然后对每个问询，我们枚举左端点 l ，快速计算长度为 K 的子区间的 lca 是哪个节点
我们可以在 O(N log^2 N) 的时间内得出答案
*/- 感谢相遇
/*
可是，少年，当你最后一次行云流水地写下线段树的时候，是否还记得，
当初懵懵懂懂的自己，曾经觉得这是一个多么难的知识？
五年的路说短不短，说长不长，有苦，有甜，有笑，有哭，有辛酸，有幸福，有泪水，有笑容
OI 见证着我从小学生蜕变为一名义忠仁，我又因为它最终选择离开这温暖的家。
可以说，OI 几乎贯穿了我整个青春，几乎影响了我生活的一切。
现在是 2024年11月30号 12:54，距离我告别 OI，仅剩 6 分钟。
最后还是想说，感谢 OI，感谢所有帮助过我的同学、老师，感谢一直支持我的父母。
感恩相遇，我们大学，有缘再见……
*//*
2024.11.30 星期六 晴
广东的冬天来得太过突然，但又太过宁静，在人们还没有反应过来之前就已将寒风吹送来了岭南
大地。
说是冬天，这片热情的土壤仍会在下午展现出它的力量：太阳才刚跨过头顶，身上的衣裳就得削
薄，再削薄。
周六的早晨带着几分萧条，目送我们早起赶往考场。也不知它有没看到，偌大的高三楼，在幸苦
了一个月的高三学子们享受宝贵的双休的时候，还有几道身影从睡梦中艰难的爬起。
是啊，都高三了。
高三有一种奇妙的魔力，能让学生的大脑放空，不再为许多得失计较，但又称不上是心心念念的
悠闲时光。我们不是机器，我们歌唱、我们奔跑、我们大笑，但也剩下歌唱、奔跑、大笑了。
还有什么放不下呢？
上楼的时候，听到几位学弟吐槽考场的楼梯，我也笑着吐槽了几句。
真好啊。
也不知道今年还有没有人做迷惑行为大赏，但我也就是写写，有没有人看到却是没什么所谓了。
不知道出了考场，天空中有没有挂起太阳？
再见了，OI。
愿后来者都能如愿，有心者终不负。
*/- 看不懂喵
/*
After Leaving OI
Kondo wa Nihongo de Kaku no o Kimeru.
Umakunai node, Nani o Machigaetara Moushiwakenai.
Tabun Boku wa Dare ka mo Suisokudekiru ka to Omou.
Gonen o Sugoshite, Yatto OI no Owari o Mukaeru.
Mata Oyoso Nijikan ga Nokotteru, demo CSP no Tsugou to wa Ooku Kotonaru.
Mondai Ichi mo Tokenakatta, Hontou no Shippai da.
Kurorekishi o Nokoshinai Tame ni, Konomama Giveupshite Ze-ro o Ete ni Naru Kamoshirenai.
Maa Ii, Jibun ni wa Kamawanai kara Kono Kanashii You na Kota wa mou Iwanai.
Jitsu wa Nani o Kakou to wa Kangaenakute, Soshite Omoidasu Koto ya Kakitai Koto o Kirokushiyou.
Kaita Koto wa Futatabi Iitakunai node, Ima no Atarashii Seikatsu no Kansou o Kouyuushiyou.
Kono Gakunen wa Hajimatta.
Boku wa Izen to Zenzen Ninai Kurasu ni Haitte, Shiru Hito mo Nakatta.
Tabun Hitori ka Futari ka Sono Mae ni Shitta no ka, Dare mo Shiranai to no Chigai wa Amari Nai, Ima made mo Hanashiau Koto ga Sukunai.
Nanka Kodoku dattadarou.
Sou Itta ga, Suujitsu o Sugoshite Ii Hito ni Atta. Gaikoutekide Omoshirosoude Boku ni Hanashi o Kaketa.
Shibaraku Hoka no Koto o Hanasou.
CSP no Toki ni Kaita Toori, Jibun wa Saiwai to Zutto Omotteru.
OI o Erande Ii Gakkou ni Benkyoushite Dake ja Nakute, Sore yori, Takusan no Jiyuu o Ataerareru no da.
Sono Jiyuu tte wa Iroiro na Koto o Fukumete,
Benkyou Igai no Jikan o Donnani Tsukau no ka,
Benkyou no Sutore-su no Sukunai Koto,
Busshitsuteki na Koto,
Soreto Mirai no Susumu Michi o Jiyuu ni Erabu Koto.
Sonowakede, Manzoku na Seikatsu o Itsumo Sugoshiteta.
Imamireba, Hitotsu no Koto wa Iyoiyo Kanseishisou da.
Sono Koto wa Zutto Dekinakatta na.
Towaie, Kono Kurasu ni Tennyuusite, Ato Ichi no Koto o Kanjita.
Jugyou no Naiyou wa Itsuyorimo Kantan ni Natta.
Boku o Shiru Hito ni Totte wa Motto Rikaiyasui to Omou kedo, Shiranai no mo Kamawanai.
Mirai no Susumu Michi o Erabu Jiyuu o Motsu ga, Jissaini Itsumademo Mirai ni Nani o Shiyou no wa Kimaranai.
Hima ga Areba, Ichiban Suki na Koto wa Chuugoku de "Moyu", Aruiwa "Bailan" da.
Jissaini wa Sou da.
Aruhito wa Boku ga Tokidoki Soushiteiru no o Mitomenai keredo, Sore wa Tashikani Boku no Itsumo Shiteiru Koto da.
Sorenishite, Izen no Kontesuto ni Mukau Kurasu o Hanareta Ato wa Ippai no Koto ya Katsudou o Shitte Naru.
Bukatsu You na Koto, Iroiro na Hoka no Kontesuto, Takusan no Purojekuto, Soreto Hoka no Shiranakatta Koto mo.
Kontesutosei ja Nakereba Koukou Seikatsu ga Sonna Azayaka ni Naru no wa Omowanakatta.
Demo Kontesuto no Seikatsu ga Kirai to Itta Tsumori ja Nakute, Tada Kotonaru Omoshirosa da.
Mou Tsukarete, Kakitakunai.
Soredewa, Saigouni,
OI,
Sayounara.
*/- RP++！
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("traverse.in","r",stdin);
// freopen("traverse.out","w",stdout);
CECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECECE
// The T1 is simple but its hardly to write code,i did it for 50min.
// The T2 is a good DP problem and not very hard,i did it for 60min.
// But T3 is a S* problem,I think the parson who make this problem is cute.
// (tips:S* is a suan fa,like A*)
// I can't write a baoli code for T3.
// Then I opened T4,its seemed like a data jiegou problem.
// The 32pts is easy,I write a segtree to do that.
// But the 100pts is very hard,and I'm too vegetable :(
// I tried to think the xingzhi A,I should answer the problem:
// Give you l,r,k,answer the minval-max,k-len qujian's minval(?).
// I think and think but can't do that.
// My OI is vegetable,My English is vegetable too! :(
// Like my CSP-S,my NOIp is bad.
// In the two matches,I finished T1 and T2 quickly.But I can't do T3 or T4.
// Why I'm vegetable like this???
// I'm not a beginner now,I learned OI 400+ days.
// I'm not Young now,I'm chu er.
// How I get Qianger?
// The Bigger dalao in my school is Exp10re,let's mod him!!!!
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// The Bigger dalao in my school grade 10 is lilong,Let's mod him!!!!
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// The Bigger dalao in my school grade 9 is cgj0128,Let's mod him!!!!
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// The Bigger dalao in my school grade 8 is _Accepted_100,Let's mod him!!!!
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// The Most vegetable Oier in my school garde 8 is ME,Let's Laugh him!!!!
//lol lol lol lol lol lol lol lol lol lol lol lol lol lol lol lol
// The Better data jiegou is segtree,because it's Exp10re's belief,Let's Learn it!!!!
//learn learn learn learn learn learn learn learn learn learn
// Wish everyone RP++!!!!
return 0;
}- 祝好
// T1: how to write code?
// T2: how to optimize the dp?
// T3: how?
// T4: how?
// 184. Nobody is worse than me.
// 1=? To far for me to reach.
// End of OI (maybe)
/*
+++++
+ +
+ +
+++++ +++++
+ OI +
+2022.09.08 +
+2024.11.30 +
+++++ +++++
+ +
i + + i
| +++++ |
*/