本场赛时5题被B和H卡了一下后面的中档题没时间开。觉得是见的比较少前面的题难度不高但由于思考和用了比较复杂的方法浪费了不少时间。本场链接寒假训练营3B. Random考察点质数gcd之前没遇到过随机生成的题一直在想特例怎么办。赛时我用了筛法由于本题不是让用这个所以数据规模上不太匹配我一直没写.思路由于数据是随机的所以非常难遇到一直找不到两个都是不同质数的数直接n 2 n^2n2暴力就行这里贴上筛法的代码让本题变得有意义一些voidpre(){v[1]1;for(inti1;iN;i){if(!v[i])f.pb(i);for(intj0;jmin(N,(int)f.size())i*f[j]N;j){v[i*f[j]]1;if(i%f[j]0)break;}}}voidcheck(vectorinta){unordered_mapint,intmp;k0;for(inti0;in;i){intxa[i];for(intj0;jf.size();j){if(x%f[j]0){if(mp[f[j]]){k1;coutmp[f[j]] a[i]endl;return;}else{mp[f[j]]a[i];while(x%f[j]0f[j])x/f[j];}}if(x1)break;}}}voidsolve(){cinn;vectorinta(n);mapint,intp;for(inti:a)cini,p[i];for(auto[x,y]:p){if(x!1y1){coutx xendl;return;}}check(a);if(!k)cout-1endl;}J. Branch of Faith考察点二叉树计算思路法1二进制的每一位刚好就是二叉树每一层的数量可利用此特性进行模拟。​ 遇到的问题log2计算太大的数字如(1e18)的时候会导致精度丢失还是一点点左移保险法2将二叉树前x层之和存到vector里每次用lower_bound定位到当层并计算代码1// Problem: Branch of Faith// Contest: NowCoder// URL: https://ac.nowcoder.com/acm/contest/120563/J// Memory Limit: 512 MB// Time Limit: 2000 msintcal(intx){intlen0;while(x)x1LL,len;intp(1LLlen)-1;intq(1LLlen-1)-1;intresmin(p,n)-q;returnres;}voidsolve(){intq;cinnq;while(q--){intx;cinx;intanscal(x);coutansendl;}}代码2voidpre(){for(inti1;iINF;i*2)f.pb(i-1);}voidsolve(){cinn;intq;cinq;while(q--){intx;cinx;intculower_bound(all(f),x)-f.begin();//当层intnum1LLcu-1;//当层总数量intkn-f[cu-1];coutmin(num,k)endl;}}F. Energy Synergy Matrix考察点博弈思维思维需要注意的是小红和小小红不是同一个人小红的任务是在小小红所在的另一行在不让小紫放到此行的情况下尽量靠右小紫的任务是在小小红所在的这一行尽量靠左的放大概是这么个情况其中⚪代表小红菱形表示小紫先说结论a n s ( n − 1 ) n / 5 ans(n-1)n/5ans(n−1)n/5首先n-1是除了第一列以外向右走的步数n/5是上下变换的步数。通过观察不难发现小小红总是在菱形所在的前一列进行变换但是由于题目中说到达当列的任意位置都行所以这个推迟了一步每次就到了菱形这一列。而菱形列刚好是5的倍数。H. Tic Tac DREAMIN’考察点数学计算几何思路1用二分不断枚举x的位置check中用叉积计算面积来判断。需要注意的是叉积具有方向性如果A C → \overrightarrow{AC}AC在A B → \overrightarrow{AB}AB的左侧则A B → × A C → 0 \overrightarrow{AB}×\overrightarrow{AC}0AB×AC0。所以计算面积需要取绝对值面积公式为1 2 ⋅ ∣ A B → × A C → ∣ \frac{1}{2}·|\overrightarrow{AB}×\overrightarrow{AC}|21​⋅∣AB×AC∣思路2由于用叉积计算面积的时候x是唯一的未知数所以可以直接解出来需要注意的是正着计算叉积的时候直接取绝对值即可但是倒着推式子就要提前加上符号再推导代码1doublexa,ya,xb,yb;doubleg(doublex){return-(yb-ya)*x(yb-ya)*xa-(xb-xa)*ya;}voidsolve(){cinxayaxbyb;if(ybya){doubletfabs((xb-xa)*ya);if(fabs(t-4.0)1e-9)cout0.0\n;elsecoutno answer\n;return;}doubleA-(yb-ya);doubleB(yb-ya)*xa-(xb-xa)*ya;doublex0-B/A;doublelx0,r1e18;for(inti0;i200;i){doublemid(lr)/2;if(fabs(g(mid))4.0)lmid;elsermid;}coutfixedsetprecision(10)((lr)/2)\n;}signedmain(){ios::sync_with_stdio(false);cin.tie(0);solve();return0;}代码2voidsolve(){cinxayaxbyb;if(yayb){doublepfabs(ya)*fabs(xa-xb)/2;if(p2)cout0.00000endl;elsecoutno answerendl;return;}axb*ya-xa*yb;byb-ya;doublex(-4-a)/b;coutfixedsetprecision(15)xendl;}C. Inverted World考察点思维思路首先可以明确最终的结果是01010101···或者是10101010···我们分别假设最终变成这些串通过计算后取操作数比较小的那个设原始串是100011001001以第二种串10101010···为例标号123456789101112目标串101010101010原串100011001001子串不必连续找的第一个操作字串就是本来就刚好吻合的剩下的标号3671112目标串10110原串01001剩下的就一点点“缝合”如果有可以接上的就接上接不上就另起一列。在这个例子中我们可以选择3,6,11,12为一个操作字串01017是另一个intcal(string p){vectorintv;for(inti0;is.size();i)if(s[i]!p[i])v.pb(s[i]-0);if(v.size()0)return0;intval1,numv[0];intcnt00,cnt10;//此时需要的数if(v[0]1)cnt0;elsecnt1;for(inti1;iv.size();i){if(v[i]){cnt0;if(cnt1)cnt1--;elseval;}else{cnt1;if(cnt0)cnt0--;elseval;}}returnval;}voidsolve(){cinns;string s1,s2;charx0;for(inti0;in;i){s1x;// 01x^1;s2x;// 10}intk1cal(s1);intk2cal(s2);coutmin(k1,k2)endl;}A. 宙天考察点简单语法思路利用s q r t sqrtsqrt下取整的性质k s q r t ( x ) ksqrt(x)ksqrt(x)直接判断k ( k 1 ) k(k1)k(k1)与x xx是否相等即可G. スピカの天秤考察点简单模拟思路分类讨论对每种情况进行模拟等到了下一种状态就输出本次补题主要有这几点B题随机二字背后的深意J题学会多利用二进制的性质F题比较有意思的思维博弈和找规律H题对叉积的进一步理解C题对题目的不断拆解和转化