绝世好b：XOI2003赛后题解 2024-04-25 17:04:35 0 0 比赛链接 由于码风的可读性较差，一些题目只提供思路，不提供代码 A 开幕雷击 没啥特别的，直接输出就行了。也没有什么奇怪的字符#include<cstdio>int main() {puts("Aeh Fin Fla Mea");return 0;} B 绝世好题 显然这道题没有资格被称为绝世好题，但它魔改自P4310 绝世好题，所以就叫这个名字了 原题要求 b i & b i − 1 ≠ 0 b_i\&b_{i-1}\ne 0 bi&bi−1=0 ，而本题要求 b i & ( b i − 1 ) ≠ 0 b_i\&(b_i-1)\ne 0 bi&(bi−1)=0 （希望比赛时没有人以为是我LaTeX下标炸了。。） 容易看出 i ≥ 2 i\ge 2 i≥2 时，选择 a a a 中所有符合条件的元素加入 b b b 即可 对于 b 1 b_1 b1 无限制，因此我们可以直接把 a 1 a_1 a1 作为 b 1 b_1 b1 。可以用贪心思想证明这不会导致答案更劣。 于是解法显然。#include<cstdio>#include<cctype>int read() { //快读int x=0; char ch=getchar();while (!isdigit(ch)) ch=getchar();while (isdigit(ch)) x=x*10+(ch^48),ch=getchar();return x;}int n,s,x;int main() {for (int T=read(); T; --T) {n=read(),read(),s=1;for (int i=1; i<n; ++i)((x=read())&(x-1))&&(++s); //符合条件，答案+1printf("%d\n",s);}return 0;} C 一键三连 虽然我没有写部分分的代码 但还是给个思路吧 首先你要知道 m m m 那么大范围其实没用，如果不低于 2 n k 2nk 2nk 那么就直接贪心选最大了。所以 m m m 真实范围只有 20000 20000 20000 。下假设 m < 2 n k m<2nk m<2nk 10pts：直接01背包 10pts+20pts：暴力枚举每个视频的所有观看情况，进行分组背包。时间复杂度 Θ ( n m 3 k ) \Theta(nm3^k) Θ(nm3k) 。 20pts：这部分分给的很迷惑。是为没有意识到 m m m 假范围的选手准备的，也不知道有没有人真的去写这档分 稍微思考一下会发现10+20的那个做法很蠢，把问题变复杂了。我们重新分析： 无论怎样，最优解肯定把所有视频都看了 k k k 遍（白嫖不消耗硬币，且不会降低快乐值）。 按 ( 0 , a i , j , 0 ) , ( 1 , a i , j , 1 ) , ( 2 , a i , j , 2 ) (0,a_{i,j,0}),(1,a_{i,j,1}),(2,a_{i,j,2}) (0,ai,j,0),(1,ai,j,1),(2,ai,j,2) 这样分组即可。复杂度 Θ ( n m k ) \Theta(nmk) Θ(nmk) 10+20是按照树形依赖背包的方式做的，但本质上 j j j 不同时不会形成依赖关系，直接分组就行了#include<cstdio>#define rep(i,l,r) for (int i=l; i<=r; ++i)typedef long long ll;int n,m,k,t,s,a[502][22][3]; ll v,f[10010];inline int max(int x,int y) { return (x>y?x:y); }int main() {scanf("%d%d%d",&n,&m,&k);rep(t,0,2) rep(i,1,n) rep(j,1,k) scanf("%d",&a[i][j][t]);//以下为特判rep(i,1,n) rep(j,1,k) {t=0; a[i][j][1]>a[i][j][t]&&(t=1);a[i][j][2]>a[i][j][t]&&(t=2);s+=t,v+=a[i][j][t];}if (m>=s) return printf("%lld\n",v),0;//以上为特判rep(i,1,n) rep(j,1,k) for (s=m; ~s; --s) {v=f[s]; //注意不能直接转移，t=0时会导致原数据被覆盖rep(t,0,2) s-t>=0&&(v=max(v,f[s-t]+a[i][j][t]));f[s]=v;}printf("%lld\n",f[m]);return 0;} D 天下第一 难点在于物理知识，如果你的物理知识储备达到洛谷人均水平（雾），这就是一道普通的思维题 根据题目里提到的方法，将所有木块看作一个系统，可以算出左一的木块与墙的摩擦力为 1 2 n G \dfrac 12nG 21nG 接着我们去掉系统中右一位置上的木块，把剩下的木块再看作一个系统。 这个系统依然是在摩擦力和重力的作用下平衡。 发现重力就是木块的总重力 ( n − 1 ) G (n-1)G (n−1)G ，两个摩擦力中一个是刚算出来的 1 2 n G \dfrac 12nG 21nG 那么另一个摩擦力（图右一、右二位置木块间的摩擦力）显然就是 ( n − 1 ) G − 1 2 n G = 1 2 n G − G (n-1)G-\dfrac 12nG=\dfrac 12nG-G (n−1)G−21nG=21nG−G 继续去掉右二位置上的木块，同理可得图右二、右三木块间的摩擦力是 1 2 n G − 2 G \dfrac 12nG-2G 21nG−2G，然后右三和右四木块间的摩擦力是 1 2 n G − 3 G \dfrac 12nG-3G 21nG−3G …… 根据这个规律解题即可。对于物理不好的选手，应当注意 n n n 为偶数时最中间位置的摩擦力算出来是0，这是没有问题的。 如果不理解，我们可以手算几组数据（以 G = 100 G=100 G=100 为例）： n = 3 n=3 n=3 时，输出 150 50 50 150 ~~~~~~~~~~~~150~~~50~~50~~~150 150 50 50 150 n = 4 n=4 n=4 时，输出 200 100 0 100 200 ~~~~~~~~~~200~100~~0~~100~200 200 100 0 100 200 n = 5 n=5 n=5 时，输出 250 150 50 50 150 250 ~~~~~~~250~150~~50~50~~150~250 250 150 50 50 150 250 n = 6 n=6 n=6 时，输出 300 200 100 0 100 200 300 ~~~300~200~100~~0~~100~200~300 300 200 100 0 100 200 300 通过这种方式看出规律，也能AC。 总之就是一个等差数列镜像反转了一下的样子 随便写写就行了 码风丑，不贴代码了 E 破事水题 提示其实给的很足了 事实上也有不少人在比赛时通过了此题 首先看提示，我们发现这个题答案要对1145141取模，输入 n n n 在 2 ∼ 1 e 9 2\sim 1e9 2∼1e9 的范围内，而且可能和质数有关 如果你看过骗分过样例这题，你就能很容易地猜到这些了 根据样例2可以大致猜到，这题和2的幂有关（ 2 16 = 65536 2^{16}=65536 216=65536） 再看数据最小的样例1，发现答案是 1145141 − 2 2 1145141-2^2 1145141−22 。猜测此题会存在某些特殊的输入，使得答案需要取相反数再膜 又发现最后三个样例刚好有两个输入是质数（切记10003不是质数），联系提示，可以猜到可能输入是质数时需要取相反数 于是我们按照这个思路写出程序：#include<cstdio>const int P=1145141; int n,t,f;int _power(int x,int y) {int ans=1;while (y) (y&1)&&(ans=1ll*ans*x%P),x=1ll*x*x%P,y>>=1;return ans;}int main() {scanf("%d",&n);for (int i=2; 1ll*i*i<=n; ++i)if (n%i==0) { f=1; break; }t=_power(2,n); f||(t=P-t); printf("%d\n",t);return 0;} 把所有样例带进去，发现全部正确。那么猜想很可能正确，大胆地交上去就行了（IOI赛制怕啥） 为了防止被D瞎出题，这题被打上了愚人节的TAG，并且降了分值。还是成为了比赛中不错的一部分的 F nCoV SARS-CoV-2 BFS+剪枝。 当然如果您有更好的解法，欢迎私信我洛谷账号来吊打我 std的思路其实就是朴素的BFS算法，也是非常暴力地通过枚举地方式扩展新的点。 但我们但凡会算时间复杂度，就明白裸BFS会T飞。 既然是搜索题，自然该考虑各种玄学剪枝了 题中采用的距离概念不是欧几里得距离，但下面我们把它看作欧几里得距离来讲解，这样会更方便（两者区别不大，实现的时候按照前者就行了） 我们把一个点可以直接影响到的点构成的集合叫做它的感染圆。显然感染圆的半径就是感染半径 r r r 。 首先是一个比较有用的剪枝优化： 如果扩展出的这个点（称为新点）的感染圆被扩展前的点（称为原点）的感染圆包含，那么不入队。 正确性显然，原点的感染一定比新点先一步进行。 实际实现就是判断 新 点 传 染 半 径 + 两 点 距 离 ≤ 原 点 传 染 半 径 新点传染半径+两点距离\le 原点传染半径 新点传染半径+两点距离≤原点传染半径 是否成立，成立则可以剪枝 这个优化具有优秀的效果。 但唯有所有半径全部相同时它无效。所以仍有一种极限数据对此免疫：半径全是9。 于是我们针对这种数据继续优化。 可以发现：如果一个点上下左右四个相邻点的感染圆合在一起，可以包含这个点的感染圆，那么也不用入队。 本质上和第一个剪枝很类似，证明也很类似。 不过上面提到了先一步进行这个条件。上面是直接由扩展顺序得出的，这里我们需要证明一下。 由于每个点的感染圆是个圆，没有办法感染到这个点而对它的相邻点一个也不碰。于是如果四个相邻点都被感染了，那么它们被感染的时刻不会比这个点更晚。 我们担心的无非是优化导致扩展被延迟，造成答案不准确。这样一来，要么四个点已经各自完成了它们的扩展，要么一些点的扩展和当前点同时进行。因此，不存在延迟问题。 实现也比较类似，写4个if就行了，不再赘述 #10作为最强的数据点，选择了半径全为9的方式，这时第二个剪枝会使实际用时大大缩短 #9采用了9和7交错分布的方式。这时，我们依然可以优化掉1/2的常数。事实上这个效果已经足够卡进时限了。 至于 T T T 的范围，其实是来吓唬人的…… 我们搜索的时候存一下上一个单位时间时被感染点的总数，如果和这一个单位时间结束后的相等，就说明这一轮没有新的感染发生，那么以后也不会变了，停止即可。 所以即使 n = 2000 n=2000 n=2000 ，也完全不必算到 T = 5000 T=5000 T=5000 那会儿 你的代码写法常数应当尽量小一些。下面放代码。#include<cstdio>#include<cctype> #include<cstring>const int N=2002; int n,T,x0,y0,l,r,s0=1,s1=1,R,tx,ty;struct node { int x,y; }Q[4000010]; //BFS队列struct ifmtn { int a,v,v2; }A[N][N]; //每个点的信息//a：感染半径 v：是否已被感染 v2：是否已被扩展inline int f(int x) { return (x<0?-x:x); } //绝对值inline int min(int x,int y) { return (x<y?x:y); }inline int read() { //没有必要使用fread快读int x=0; char ch=getchar(); while (!isdigit(ch)) ch=getchar();while (isdigit(ch)) x=x*10+(ch^48),ch=getchar();return x;}inline int check(int x,int y) { //剪枝二int r=A[x][y].a;ifmtn a1=A[x-1][y],a2=A[x+1][y],a3=A[x][y-1],a4=A[x][y+1];if ((a1.v&&a1.a>r)||(a2.v&&a2.a>r)) return 1;if ((a3.v&&a3.a>r)||(a3.v&&a3.a>r)) return 1;if (a1.v&&a1.a>=r-1&&a2.v&&a2.a>=r-1)return (a3.v&&a3.a>=r-1&&a4.v&&a4.a>=r-1);//这样写是为了代码美观，四个if直接判也是可以的return 0;}int main() {n=read();for (int i=1; i<=n; ++i)for (int j=1; j<=n; ++j) A[i][j].a=read();x0=read(),y0=read(),T=read(); A[x0][y0].v=1;for (Q[l=r=1]={x0,y0}; T; --T) { //模拟时间流逝for (int tr=r; l<=tr; ++l) { //完成这一个单位时间内的扩展tx=Q[l].x,ty=Q[l].y; ifmtn &A1=A[tx][ty];if (A1.v2) continue; A1.v2=1,R=A1.a;//如果已被扩展过，则无需再扩展int mn=min(R,tx-1),mx=min(R,n-tx);for (int i=-mn; i<=mx; ++i) { //枚举横坐标差值int mn2=min(R-f(i),ty-1),mx2=min(R-f(i),n-ty);for (int i2=f(i),i3=tx+i,j=-mn2; j<=mx2; ++j) {//枚举纵坐标差值ifmtn &A2=A[i3][ty+j]; //新点if (A2.v) continue; A2.v=1,++s1,A2.v2=1;if (check(i3,ty+j)) continue;//被感染过或符合剪枝二则无需入队//下面如不恢复v2，则符合剪枝一，无需再扩展，等效于被扩展过//因此选择提前设v2为1不会有错，而且方便一点点A2.a+i2+f(j)>=R&&(Q[++r]={i3,ty+j},A2.v2=0);//剪枝一，不成立则入队，并标记未被扩展}}}if (s1==s0) break; s0=s1; //无新的感染发生，直接停止}printf("%d\n",s1);return 0;} 预感这题会被喷。。坐等神仙来嘲讽 >_< G 出言不逊 可以说是本场比赛最大的败笔，反 复 出 锅 1：线性筛后直接判断 2,3,4,5：这个还要我讲做法的话请你自己反省一下吧（ 6：快速幂直接解决 7,8：逆元板子啦 9：预处理阶乘及其逆元，然后套公式算 10：在9的基础上使用卢卡斯定理 11：有点多，放在下面讲 12：预处理阶乘及其逆元，直接计算 13：费马小定理减小幂数（参考【模板】欧拉定理读入方法） 11的std是将完全平方展开，然后以 x x x 为主元整理，得到这个： ( l 2 + ( l + 1 ) 2 + ⋯ + r 2 ) + 2 ( l + ( l + 1 ) + ⋯ + r ) x + ( 1 + 1 + ⋯ + 1 ) x 2 (l^2+(l+1)^2+\cdots+r^2)+2(l+(l+1)+\cdots+r)x+(1+1+\cdots+1)x^2 (l2+(l+1)2+⋯+r2)+2(l+(l+1)+⋯+r)x+(1+1+⋯+1)x2 都有对应的公式可以处理，时间复杂度 Θ ( 1 ) \Theta(1) Θ(1) 。 也看到了有神仙直接预处理前缀平方和，然后好像也能 Θ ( 1 ) \Theta(1) Θ(1) 处理 顺便STO 0 o _ l o v e _ o 0 \sf 0\color{red}o\_love\_o0 0o_love_o0 倒序切题太强啦 UPD on 2020/3/28：对于12操作，使用逆元的做法局限性较大（甚至在本题条件下仍有可能出锅？？不管了反正弱鸡数据没反映出这一点），使用线段树/ST表处理区间求积更佳。 感谢 0 o _ l o v e _ o 0 \sf 0\color{red}o\_love\_o0 0o_love_o0 神仙发现并提出了这个问题qwq#include<cstdio>#include<cctype>#include<cstring>#define gc (prl==prr&&(prr=(prl=cr)+fread(cr,1,1<<21,stdin),prl==prr)?EOF:*prl++)typedef long long ll;char cr[1<<21],*prl=cr,*prr=cr;inline int read() {int x=0; char ch=gc;while (!isdigit(ch)) ch=gc;while (isdigit(ch)) x=x*10+(ch^48),ch=gc;return x;}inline int read2() {int x=0,f=0; char ch=gc;while (!isdigit(ch)) f|=(ch=='-'),ch=gc;while (isdigit(ch)) x=x*10+(ch^48),ch=gc;return (f?-x:x);}ll read3() {ll x=0; char ch=gc;while (!isdigit(ch)) ch=gc;while (isdigit(ch)) x=x*10+(ch^48),ch=gc;return x;}int read4(int p) {int x=0; char ch=gc;while (!isdigit(ch)) ch=gc;while (isdigit(ch)) (x=x*10+(ch^48))>=p&&(x%=p),ch=gc;return x;}char cw[1<<21]; int pw1=-1,pw2,num[20];inline void flush() { fwrite(cw,1,pw1+1,stdout),pw1=-1; }void write(ll x) {x<0&&(x=-x,cw[++pw1]='-'); (pw1>(1>>20))&&(flush(),0);do { num[++pw2]=x; }while (x/=10);do { cw[++pw1]=(num[pw2]^48); }while (--pw2);cw[++pw1]='\n';}inline void yes() { cw[++pw1]='Y',cw[++pw1]='e',cw[++pw1]='s',cw[++pw1]='\n'; }inline void no() { cw[++pw1]='N',cw[++pw1]='o',cw[++pw1]='\n'; }const int N=100010; int cnt,p1,p2,p3,pp,Q;int fac1[N],fac2[N],inv1[N],inv2[N],pri[N],v[1000010];void makep() {for (int i=2,n=1000000; i<=n; ++i) {v[i]||(pri[++cnt]=i);for (int j=1; j<=cnt&&1ll*pri[j]*i<=n; ++j) {v[pri[j]*i]=1;if (i%pri[j]==0) break;}}}ll gcd(ll x,ll y) { return (y?gcd(y,x%y):x); }inline int _power(int x,int y,int p) {int ans=1;while (y) (y&1)&&(ans=1ll*ans*x%p),x=1ll*x*x%p,y>>=1;return ans;}inline int C(int n,int m) {if (n<m) return 0;return 1ll*inv1[m]*inv1[n-m]%p1*fac1[n]%p1;}int lucas(ll n,ll m) {if (n==0) return 1;return 1ll*C(n%p1,m%p1)*lucas(n/p1,m/p1)%p1;}int main() {makep(); Q=read(),p1=read(),p2=read(),p3=read();fac1[0]=fac2[0]=1;for (int i=1; i<p1; ++i) fac1[i]=1ll*fac1[i-1]*i%p1;for (int i=1; i<p2; ++i) fac2[i]=1ll*fac2[i-1]*i%p2;inv1[p1-1]=_power(fac1[p1-1],p1-2,p1);inv2[p2-1]=_power(fac2[p2-1],p2-2,p2);for (int i=p1-1; i; --i) inv1[i-1]=1ll*inv1[i]*i%p1;for (int i=p2-1; i; --i) inv2[i-1]=1ll*inv2[i]*i%p2;for (int opt,x,y,p,l,r; Q; --Q) {opt=read();if (opt==1) v[read()]?no():yes();else if (opt<=3) {x=read2(),y=read2();write(opt==2?1ll*x+y:1ll*x*y);}else if (opt==4) {ll X=read3(),Y=read3();write(gcd(X,Y));}else if (opt==5) {x=read(),y=read();write(1ll*x*y/gcd(x,y));}else if (opt==6) {x=read(),p=read();write(_power(x,p-2,p));}else if (opt==7) {x=read(),y=read(),p=read();write(_power(x,y,p));}else if (opt==8) {x=read(),y=read(),p=read();write(1ll*_power(y,p-2,p)*x%p);}else if (opt==9) {int n=read(),m=read();write(C(n,m));}else if (opt==10) {ll n=read3(),m=read3();write(lucas(n,m));}else if (opt==11) {l=read(),r=read(),x=read();ll S=(1ll*r*(r+1)*(r+r+1)-1ll*l*(l-1)*(l+l-1))/6;S-=(1ll*r*(r+1)-1ll*l*(l-1))*x;write(S+1ll*x*x*(r-l+1));}else if (opt==12) {l=read(),r=read();write(1ll*fac2[r]*inv2[l-1]%p2);}else { x=read(),y=read4(p3-1); write(_power(x,y,p3)); }}flush();for (int i=1; i<=3; ++i) puts("Flamire AK IOI");return 0;} H 禁止套娃 考虑欧拉定理： a , p a,p a,p 互质时， a x ≡ a x m o d φ ( p ) ( m o d p ) a^x\equiv a^{x\bmod \varphi(p)}\pmod p ax≡axmodφ(p)(modp) 发现要求的式子套了娃 不过欧拉定理也可以套娃 比如 a b c m o d p a^{b^c}\bmod p abcmodp 就可以变成 a b c m o d φ ( φ ( p ) ) m o d p a^{b^{c\bmod \varphi(\varphi(p))}}\bmod p abcmodφ(φ(p))modp 关于那个限制条件，我们发现根据数据的性质，所有 a , p a,p a,p 一定互质 然后就没了。。 （其实这题原定是没有特殊性质，用扩展欧拉定理的，不过后来发现似乎极难实现，有兴趣你也可以试试） 欧拉函数可以线性筛预处理出来，那么时间复杂度为 Θ ( T n log p ) \Theta(Tn\log p) Θ(Tnlogp) 后面那个 log p \log p logp 其实误差很大，完全不可能跑满，其实只是个比较小的常数 不需要怎么卡就可以过了 不过IO优化还是必要的#include<cstdio>#include<cctype>#define gc (l==r&&(r=(l=c)+fread(c,1,1<<21,stdin),l==r)?EOF:*l++)typedef long long ll;const int N=1000000; ll a[41];int n,T,ans,cnt,p[41],pri[100010],v[N+1],phi[N+1];int _power(int x,int y,int p) { //快速幂int s=1;while (y) (y&1)&&(s=1ll*s*x%p),x=1ll*x*x%p,y>>=1;return s;}void makep() { //线性筛v[1]=1,phi[1]=1;for (int i=2,t; i<=N; ++i) {v[i]||(pri[++cnt]=i,phi[i]=i-1,v[i]=i);for (int j=1; j<=cnt&&1ll*pri[j]*i<=N; ++j) {v[t=pri[j]*i]=pri[j];if (i%pri[j]==0) { phi[t]=phi[i]*pri[j]; break; }phi[t]=phi[i]*(pri[j]-1);}}}int pw=-1,pw1,num[10]; char c[1<<21],*l=c,*r=c,cw[1<<21];inline int read() { //fread快读int x=0; char ch=gc;while (!isdigit(ch)) ch=gc;while (isdigit(ch)) x=x*10+(ch^48),ch=gc;return x;}inline void flush() { fwrite(cw,1,pw+1,stdout),pw=-1; }inline void write(int x) { //fwrite快输pw>>20&&(flush(),0);do { num[++pw1]=x; }while (x/=10);do { cw[++pw]=(num[pw1]^48); }while (--pw1);cw[++pw]='\n';}int main() { scanf("%d",&n); for (int i=1; i<=n; ++i) scanf("%lld",a+i);for (makep(),T=read(); T; --T) {p[1]=read(); for (int i=2; i<=n; ++i) p[i]=phi[p[i-1]];ans=a[n]%p[n]; //从顶层开始for (int i=n-1; i; --i) ans=_power(a[i]%p[i],ans,p[i]); //逐层计算write(ans);}return flush(),0; //fwrite快输需要在结束时调用一次flush} 总结 这场比赛是2020年我们办的第一场比赛，也是我们办的题目最多（应该是的？）的一场，说实话办得比较失败（锅一大堆），不过算是从中获得了不少经验，希望下场比赛会好一些吧（将会有一位神仙参与出题&验题） 其实下场比赛也不可能这样了 题目数会减半，而且也不会考这么多玄学的东西了 另外XOI2004（将改名XOI20Apr）极可能咕掉 以后极可能变成两个月办一场 钱？下次一定 看情况吧，我们会尽 快处理好的 收藏（0）