![打卡信奥刷题（3642）用C++实现信奥题 P12024 [USACO25OPEN] It‘s Mooin‘ Time III B](http://pic.xiahunao.cn/yaotu/打卡信奥刷题（3642）用C++实现信奥题 P12024 [USACO25OPEN] It‘s Mooin‘ Time III B)
P12024 [USACO25OPEN] It’s Mooin’ Time III B题目描述Elsie 正在试图向 Bessie 描述她最喜欢的 USACO 竞赛但 Bessie 很难理解为什么 Elsie 这么喜欢它。Elsie 说「现在是哞哞时间谁想哞哞拜托我只想参加 USACO」。Bessie 仍然不理解于是她将 Elsie 的描述转文字得到了一个长为NNN3≤N≤1053 \leq N \leq 10^53≤N≤105的字符串包含小写字母字符s1s2…sNs_1s_2 \ldots s_Ns1s2…sN。Elsie 认为一个包含三个字符的字符串ttt是一个哞叫如果t2t3t_2 t_3t2t3且t2≠t1t_2 \neq t_1t2t1。一个三元组(i,j,k)(i, j, k)(i,j,k)是合法的如果ijki j kijk且字符串sisjsks_i s_j s_ksisjsk组成一个哞叫。对于该三元组FJ 执行以下操作计算其值FJ 将字符串sss在索引jjj处弯曲 90 度该三元组的值是Δijk\Delta ijkΔijk的面积的两倍。换句话说该三元组的值等于(j−i)(k−j)(j-i)(k-j)(j−i)(k−j)。Bessie 向你进行QQQ1≤Q≤3⋅1041 \leq Q \leq 3 \cdot 10^41≤Q≤3⋅104个查询。在每个查询中她给你两个整数lll和rrr1≤l≤r≤N1 \leq l \leq r \leq N1≤l≤r≤Nr−l1≥3r-l1 \ge 3r−l1≥3并询问满足l≤il \leq il≤i和k≤rk \leq rk≤r的所有合法三元组(i,j,k)(i, j, k)(i,j,k)的最大值。如果不存在合法的三元组输出−1-1−1。注意这个问题涉及到的整数可能需要使用 64 位整数类型例如C/C 中的long long。输入格式输入的第一行包含两个整数NNN和QQQ。以下一行包含s1s2,…sNs_1 s_2, \ldots s_Ns1s2,…sN。以下QQQ行每行包含两个整数lll和rrr表示每个查询。输出格式对于每一个查询输出一行包含对于该查询的答案。输入输出样例 #1输入 #112 5 abcabbacabac 1 12 2 7 4 8 2 5 3 10输出 #128 6 1 -1 12说明/提示样例解释对于第一个查询(i,j,k)(i,j,k)(i,j,k)必须满足1≤ijk≤121 \le i j k \le 121≤ijk≤12。可以证明对于某个合法的(i,j,k)(i,j,k)(i,j,k)Δijk\Delta ijkΔijk的最大面积在i1i1i1j8j8j8以及k12k12k12时取到。注意s1s8s12s_1 s_8 s_{12}s1s8s12是字符串 “acc”根据前述定义是一个哞叫。Δijk\Delta ijkΔijk的直角边长为777和444从而它的面积的两倍将等于282828。对于第三个查询(i,j,k)(i,j,k)(i,j,k)必须满足4≤ijk≤84 \le i j k \le 84≤ijk≤8。可以证明对于某个合法的(i,j,k)(i,j,k)(i,j,k)Δijk\Delta ijkΔijk的最大面积在i4i4i4j5j5j5以及k6k6k6时取到。对于第四个查询不存在满足2≤ijk≤52 \le i j k \le 52≤ijk≤5的(i,j,k)(i,j,k)(i,j,k)使得sisjsks_i s_j s_ksisjsk是一个哞叫所以该查询的输出为−1-1−1。测试点性质测试点2∼32\sim32∼3N,Q≤50N,Q\le 50N,Q≤50。测试点4∼64\sim64∼6Q1Q1Q1唯一的询问满足l1l1l1且rNrNrN。测试点7∼117\sim 117∼11没有额外限制。C实现#includeiostream#includealgorithm#includevector#includestringusingnamespacestd;vectorintc[50];intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);intn,q,l,r;string s;cinnqs;for(inti0;in;i){c[s[i]-a].push_back(i);}inti,j,k;longlongans;while(q--){cinlr;l--;r--;ans-1;for(intc10;c126;c1){ilower_bound(c[c1].begin(),c[c1].end(),l)-c[c1].begin();if(ic[c1].size()||ir-1){continue;}for(intc30;c326;c3){if(c3c1||c[c3].size()2){continue;}kupper_bound(c[c3].begin(),c[c3].end(),r)-c[c3].begin()-1;if(k0||c[c3][k-1]c[c1][i]){continue;}jupper_bound(c[c3].begin(),c[c3].end(),(c[c3][k]c[c1][i])/2)-c[c3].begin();if(jk){ansmax(ans,(c[c3][k]-c[c3][j])*1LL*(c[c3][j]-c[c1][i]));}j--;if(j0c[c1][i]c[c3][j]){ansmax(ans,(c[c3][k]-c[c3][j])*1LL*(c[c3][j]-c[c1][i]));}}}coutans\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
P12024 [USACO25OPEN] It’s Mooin’ Time III B题目描述Elsie 正在试图向 Bessie 描述她最喜欢的 USACO 竞赛但 Bessie 很难理解为什么 Elsie 这么喜欢它。Elsie 说「现在是哞哞时间谁想哞哞拜托我只想参加 USACO」。Bessie 仍然不理解于是她将 Elsie 的描述转文字得到了一个长为NNN3≤N≤1053 \leq N \leq 10^53≤N≤105的字符串包含小写字母字符s1s2…sNs_1s_2 \ldots s_Ns1s2…sN。Elsie 认为一个包含三个字符的字符串ttt是一个哞叫如果t2t3t_2 t_3t2t3且t2≠t1t_2 \neq t_1t2t1。一个三元组(i,j,k)(i, j, k)(i,j,k)是合法的如果ijki j kijk且字符串sisjsks_i s_j s_ksisjsk组成一个哞叫。对于该三元组FJ 执行以下操作计算其值FJ 将字符串sss在索引jjj处弯曲 90 度该三元组的值是Δijk\Delta ijkΔijk的面积的两倍。换句话说该三元组的值等于(j−i)(k−j)(j-i)(k-j)(j−i)(k−j)。Bessie 向你进行QQQ1≤Q≤3⋅1041 \leq Q \leq 3 \cdot 10^41≤Q≤3⋅104个查询。在每个查询中她给你两个整数lll和rrr1≤l≤r≤N1 \leq l \leq r \leq N1≤l≤r≤Nr−l1≥3r-l1 \ge 3r−l1≥3并询问满足l≤il \leq il≤i和k≤rk \leq rk≤r的所有合法三元组(i,j,k)(i, j, k)(i,j,k)的最大值。如果不存在合法的三元组输出−1-1−1。注意这个问题涉及到的整数可能需要使用 64 位整数类型例如C/C 中的long long。输入格式输入的第一行包含两个整数NNN和QQQ。以下一行包含s1s2,…sNs_1 s_2, \ldots s_Ns1s2,…sN。以下QQQ行每行包含两个整数lll和rrr表示每个查询。输出格式对于每一个查询输出一行包含对于该查询的答案。输入输出样例 #1输入 #112 5 abcabbacabac 1 12 2 7 4 8 2 5 3 10输出 #128 6 1 -1 12说明/提示样例解释对于第一个查询(i,j,k)(i,j,k)(i,j,k)必须满足1≤ijk≤121 \le i j k \le 121≤ijk≤12。可以证明对于某个合法的(i,j,k)(i,j,k)(i,j,k)Δijk\Delta ijkΔijk的最大面积在i1i1i1j8j8j8以及k12k12k12时取到。注意s1s8s12s_1 s_8 s_{12}s1s8s12是字符串 “acc”根据前述定义是一个哞叫。Δijk\Delta ijkΔijk的直角边长为777和444从而它的面积的两倍将等于282828。对于第三个查询(i,j,k)(i,j,k)(i,j,k)必须满足4≤ijk≤84 \le i j k \le 84≤ijk≤8。可以证明对于某个合法的(i,j,k)(i,j,k)(i,j,k)Δijk\Delta ijkΔijk的最大面积在i4i4i4j5j5j5以及k6k6k6时取到。对于第四个查询不存在满足2≤ijk≤52 \le i j k \le 52≤ijk≤5的(i,j,k)(i,j,k)(i,j,k)使得sisjsks_i s_j s_ksisjsk是一个哞叫所以该查询的输出为−1-1−1。测试点性质测试点2∼32\sim32∼3N,Q≤50N,Q\le 50N,Q≤50。测试点4∼64\sim64∼6Q1Q1Q1唯一的询问满足l1l1l1且rNrNrN。测试点7∼117\sim 117∼11没有额外限制。C实现#includeiostream#includealgorithm#includevector#includestringusingnamespacestd;vectorintc[50];intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);intn,q,l,r;string s;cinnqs;for(inti0;in;i){c[s[i]-a].push_back(i);}inti,j,k;longlongans;while(q--){cinlr;l--;r--;ans-1;for(intc10;c126;c1){ilower_bound(c[c1].begin(),c[c1].end(),l)-c[c1].begin();if(ic[c1].size()||ir-1){continue;}for(intc30;c326;c3){if(c3c1||c[c3].size()2){continue;}kupper_bound(c[c3].begin(),c[c3].end(),r)-c[c3].begin()-1;if(k0||c[c3][k-1]c[c1][i]){continue;}jupper_bound(c[c3].begin(),c[c3].end(),(c[c3][k]c[c1][i])/2)-c[c3].begin();if(jk){ansmax(ans,(c[c3][k]-c[c3][j])*1LL*(c[c3][j]-c[c1][i]));}j--;if(j0c[c1][i]c[c3][j]){ansmax(ans,(c[c3][k]-c[c3][j])*1LL*(c[c3][j]-c[c1][i]));}}}coutans\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
