丽江北京网站建设,来个手机能看的网站2021,珠海自适应网站建设,北京知名企业100强文章目录前言考场题目解析T1T2T3总结代码T1T2T3前言
50pts 30020 rnk19 … 把1000ms看成10s我也真是个人才。 T3自然溢出50带模数T成20有点离谱。 但倒没有因为WA失分。 就是菜罢了
考场
这次时间管理还是比较合理的。 乍看三题觉得T1似乎是个伞兵题 这离线下来可持久化数组…
文章目录前言考场题目解析T1T2T3总结代码T1T2T3前言
50pts 30020 rnk19 … 把1000ms看成10s我也真是个人才。 T3自然溢出50带模数T成20有点离谱。 但倒没有因为WA失分。 就是菜罢了
考场
这次时间管理还是比较合理的。 乍看三题觉得T1似乎是个伞兵题 这离线下来可持久化数组二分一下不随便做 … 能有甚么奇怪的原因你就是不想让我得分。
T2乍一看又感觉可做了。 然后发现需要求权值的平方和。 先暴力枚举情况上轮廓线的话 n3n3n3 都感觉要T… 直接弃疗本次满分200分。
T3想到了类似题解的那个定义。 然后这个问法肯定往SA上想啊。 但是它变来变去似乎直接求SA会出大问题。 然后就不会勒。 补题的时候这个问题也没有解决qwq 我会哈希 服了 1040004000 1.5s跑不过去。
但是还是不是特别想写暴力。 还是对T1比较有想法。 瞅T1瞅到九点想法越来越少 然后就去敲 T3 暴力乐。 很好写半个小时写完了。 30min 50pts远超lb预期 怕锅还上了个双哈希。 不过那个题只要不自然溢出单双哈希都是会T的。 爱咋咋地吧。
此时还有2.5h 我就剩个暴力巨好写的T1了。 瞬间悠闲起来。 既然暴力好写这题其实还是应该先打个暴力虽然这次没吃亏但对拍还是写了个暴力不如提前写了。 一开始觉得可能是平衡树但越想越觉得平衡树不可做。 开始lxl化想是否可以根号分治之类的神奇科技。 一开始按照常规根号分治思路肯定要想修改集合大于根号如何小于根号如何。 发现修改集合大于根号根本没法如何。 然后灵光一闪觉得可以利用神奇的均摊对修改分块忽略掉一些很垃圾的修改。 仔细想想还是挺可行的。 想想实现似乎是 O(mf(B)logmmBmlogm)O(mf(B)\log m\dfrac{m}{B}m\log m)O(mf(B)logmBmmlogm) 每次贡献复杂度都会是观察者的变化量至少减少 1B\frac{1}{B}B1 上取整f(B)f(B)f(B) 就是这个贡献次数。 打表发现卡成最差也就是 8B−9B8B-9B8B−9B 左右。而且除非对着我的算法和块长卡否则根本卡不满。
在一看时间 10秒那不过了大伏笔
然后就愉快的开始敲。 后来由于感觉这个做法不是正解且出数据的人恐怕并不会想着卡把 BBB 调成了 300300300 左右复杂度往前倾斜一点让后面稳定的重构复杂度低一些。
算是被 std::set 玩明白了来回debug其实就一直在这件事上。 出考场 啊焯
题目解析
T1
每次把变化量平均分成 k 份有一份超了就重构这样复杂度是 O(mlog1.5t)O(m\log_{1.5}t)O(mlog1.5t) 的。 你说它难吧看题解一点不难你说它不难还就是想不到。 还是类似于利用 set 忽略修改复杂度均摊的思路但这个均摊靠谱多了。
T2
技巧题。 《变形》f2(x)f(x)∗f(x)f^2(x)f(x)*f(x)f2(x)f(x)∗f(x) 把问题转化为在同一种填数方案下关键任务两种连边方案的方案数。 然后直接插头dp即可。 补题发现这种轻插头dp其实挺好写的
T3
蜜汁题目 正准备敲“现在也没明白”然后突然就想明白了并且去补完了本题 其实本题真是离正解很近了唯一的障碍是我学了SA 关键是要灵活。 本题由于特殊元素在不同的后缀中值不一样用SA常规的倍增加基排是不可行的因为基排的原理是基于值域的。 就给你两个后缀让你比较字典序怎么做 哈希加二分啊 我暑假的时候还用这个做法切过一个题现在反而不会了悲 所以我们可以使用基于比较的快速排序写一个复杂度 log\loglog 的cmp揉进去。 加上 std::sort 的 log\loglog 预处理总复杂度 nlog2nn\log^2nnlog2n。 有了SA后面就简单了直接二分找到SA数组里的左右端点中间的后缀均为答案。 注意一些超出结尾的细节。
总结
还是比较惨的一次考试 最近就没有不惨过 但是T1,3对题目的直觉与大方向都是对的。 题目虽然整体偏难但也不是没有切题的机会尤其T3 明天加油吧awa
代码
T1
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N2e6100;
const int M2e4100;int n,m,tot;struct node{ll w;int id;bool operator (const node oth)const{if(w!oth.w)return woth.w;else return idoth.id;}bool operator (const node oth)const{if(w!oth.w)return woth.w;else return idoth.id;}bool operator (const node oth)const{return woth.widoth.id;}
};multisetnodes[N];
ll val[N],sum[N];
int p[N][5],k[N];
ll giv[N][5];
int lst;
int mem[N],num,ans[N];
void solve(int now,int op){ll lftsum[now];for(int i1;ik[now];i) lft-val[p[now][i]];if(op){for(int i1;ik[now];i){if(s[p[now][i]].find((node){giv[now][i],now})s[p[now][i]].end()){debug(!\n);exit(0);}s[p[now][i]].erase(s[p[now][i]].find((node){giv[now][i],now}));}}if(lft0){ans[lst]now;}else{int wlft/k[now];for(int i1;ik[now];i){int addw;lft-add;giv[now][i]val[p[now][i]]add;s[p[now][i]].insert((node){giv[now][i],now});}}return;
}int tag[N];
signed main(){//#ifndef ONLINE_JUDGEfreopen(obs.in,r,stdin);freopen(obs.out,w,stdout);//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);//#endifnread();mread();for(int clo1;clom;clo){int opread();if(op1){int nowtot,tread()^lst;k[now]read();assert(k[now]3);for(int i1;ik[now];i){p[now][i]read()^lst;sum[now]val[p[now][i]];}sum[now]t;solve(now,0);}else{int xread()^lst,vread()^lst;lst0;num0;val[x]v;for(node o:s[x]){if(o.wval[x]) break;if(tag[o.id]!clo) mem[num]o.id;//assert(tag[o.id]!clo);tag[o.id]clo;}for(int i1;inum;i){solve(mem[i],1);}sort(ans1,ans1lst);printf(%d ,lst);sort(ans1,ans1lst);for(int i1;ilst;i) printf(%d ,ans[i]);puts();}//lst0;}return 0;
}
/*
5 10
1 9 3 3 4 5
2 4 1
1 4 2 1 4
1 4 3 1 2 3
2 2 4
2 1 4
1 6 2 1 5
2 1 2
1 4 1 3
1 2 2 3 5
*/
T2
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N2e6100;
const int M2e4100;
const int mod998244353;int n,m,tot;
int mp[75][8],mi[10];
ll f[2][150][150];
int num[3],st[3][10];void init(){ mi[0]1;for(int i1;i8;i){mi[i]mi[i-1]1;//printf(i%d mi%d\n,i,mi[i]);}num[0]1;num[1]2;num[2]1;st[0][1]0;st[1][1]1;st[1][2]2;st[2][1]3;
}void work(){nread();mread();int Smi[m1]-1;for(int i1;in;i){for(int j1;jm;j) scanf(%d,mp[i][j]);}memset(f,0,sizeof(f));int now1,nxt0;f[nxt][0][0]1;for(int i1;in;i){for(int j1;jm;j){swap(now,nxt);memset(f[nxt],0,sizeof(f[nxt]));for(int p0;pmi[m1];p){for(int q0;qmi[m1];q){if(!f[now][p][q]) continue;int n1((pmi[j-1])?1:0)((pmi[j])?1:0);int n2((qmi[j-1])?1:0)((qmi[j])?1:0);//printf( p%d q%d n1%d%d n2%d%d\n,p,q,//(pmi[j]),(pmi[j1]),((qmi[j])?1:0),((qmi[j1])?1:0));//printf( ?? %d%d%d\n,p,mi[j],pmi[j]);for(int k0;k4;k){if(mp[i][j]!-1mp[i][j]!k) continue;int ak-n1,bk-n2;//printf( k%d a%d b%d\n,k,a,b);if(a0||b0) continue;for(int s1;snum[a];s){int np(p(S^(mi[j-1]|mi[j])))|(st[a][s](j-1));for(int t1;tnum[b];t){int nq(q(S^(mi[j-1]|mi[j])))|(st[b][t](j-1));if(jm){if((npmi[m])||(nqmi[m])) continue;np(np1)S;nq(nq1)S;}(f[nxt][np][nq]f[now][p][q])%mod;}}}}}//for(int p0;pmi[m1];p){// for(int q0;qmi[m1];q){// if(f[nxt][p][q]){// printf((%d %d) p%d q%d f%lld\n,i,j,p,q,f[nxt][p][q]);// }// }//}//puts();}}printf(%lld\n,f[nxt][0][0]);
}signed main(){freopen(grid.in,r,stdin);freopen(grid.out,w,stdout);init();int Tread();while(T--) work();return 0;
}
/*
1
1 2
1 1
*/
T3
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N2e6100;
const int M2e4100;int n,m,tot;ull h[N],Mi[N],key100003;
int s[N],ss[N],nxt[N][10],pre[10];
void init_Hash(){Mi[0]1;for(int i1;in;i) Mi[i]Mi[i-1]*key;for(int i1;in;i) h[i]h[i-1]*key(s[i]1);return;
}
inline ull Hash(int l,int r){return h[r]-h[l-1]*Mi[r-l1];
}
int a[12],b[12],na,nb;
inline int Lcp(int x,int y){int st0,edn-max(x,y)1;while(sted){int mid(sted1)1;if(Hash(x,xmid-1)Hash(y,ymid-1)) stmid;else edmid-1;}return st;
}
inline int lcp(int x,int y){na0;nb0;for(int i0;i9;i){if(nxt[x][i]) a[na]nxt[x][i];if(nxt[y][i]) b[nb]nxt[y][i];}a[na]n1;b[nb]n1;sort(a1,a1na);sort(b1,b1nb);int res(0),pax-1,pby-1;for(int i1;;i){//printf(res%d a%d b%d (%d %d) (%d %d)\n,res,a[i],b[i],pa1,a[i]-1,pb1,b[i]-1);if(max(a[i],b[i])n1||Hash(pa1,a[i]-1)!Hash(pb1,b[i]-1)){//printf( dif Lcp%d\n,Lcp(pa1,pb1));return resLcp(pa1,pb1);}else{//printf( ok\n);resa[i]-pa;paa[i];pbb[i];}}
}
bool cmp(int x,int y){int olcp(x,y);//printf(cmp: (%d %d) o%d %d %d\n,x,y,o,s[xo],s[yo]);if(xon||yon) return xy;int uxo-s[xo]x?s[xo]:-1,vyo-s[yo]y?s[yo]:-1;//if(uv){// printf((%d %d) o%d u%d v%d\n,x,y,o,u,v);//}assert(u!v);return uv;
}
int sa[N],rk[N],height[N];
int mn[N][20],lg[N],mi[20];
void SA(){for(int i1;in;i) sa[i]i;sort(sa1,sa1n,cmp);for(int i1;in;i) rk[sa[i]]i;for(int i2;in;i) height[i]lcp(sa[i-1],sa[i]);
}
void init_ST(){lg[0]-1;for(int i1;in;i) lg[i]lg[i1]1;mi[0]1;for(int i1;ilg[n];i) mi[i]mi[i-1]1;for(int i1;in;i) mn[i][0]height[i];for(int k1;klg[n];k){for(int i1;imi[k]-1n;i) mn[i][k]min(mn[i][k-1],mn[imi[k-1]][k-1]);}return;
}
inline int Min(int l,int r){int klg[r-l1];return min(mn[l][k],mn[r-mi[k]1][k]);
}
inline int Suf(int x,int len){int stx,edn;while(sted){int mid(sted1)1;//printf( (%d %d) mid%d %d%d?\n,st,ed,mid,Min(x,mid),);if(Min(x1,mid)len) stmid;else edmid-1;}return st;
}
inline int Pre(int x,int len){if(height[x]len) return x;int st2,edx;while(sted){int mid(sted)1;if(Min(mid,x)len) edmid;else stmid1;}return st-1;
}signed main(){ freopen(similar.in,r,stdin);freopen(similar.out,w,stdout);nread();mread();for(int i1;in;i){scanf(%1d,ss[i]);int xss[i];s[i]i-pre[x];for(int jpre[x]1;ji;j) nxt[j][x]i;pre[x]i;}s[n1]-1;init_Hash();//for(int i1;in;i) printf(%d,s[i]);//puts();//for(int i1;in;i){// for(int ji1;jn;j) printf((%d %d) lcp%d %d%d?:%d\n,i,j,lcp(i,j),i,j,cmp(i,j));//}//printf(%d\n,cmp(6,7));exit(0);SA();//for(int i1;in;i){//printf(i%d sa%d h%d ,i,sa[i],height[i]);//for(int jsa[i];jn;j) printf(%d,j-s[j]sa[i]?s[j]:0);//puts();//}init_ST();int lst(0);for(int i1;im;i){int lread()^lst,rread()^lst,lenr-l1;int posrk[l];lstSuf(pos,len)-Pre(pos,len)1;//printf( (%d %d) pos%d (%d %d)\n,l,r,pos,Pre(pos,len),Suf(pos,len));printf(%d\n,lst);//lst0;}return 0;
}
/*
1
1 2
1 1
*/
