Preface
后天就要比国赛了，这次才堪堪写了三年的题
感觉这场的题就是给人一种很难受的感觉，填空题多得要死，而且皮亚诺曲线的那个说实话挺麻烦的
然后还有个极其傻逼的大模拟题（出租车），导致可做题数量很少
不过这场的压轴是个很经典的题，而且正好最近学校数学专题出到了一模一样的题目，然后传统艺能线段树也是一眼题，所以可能正式打的话结果会不错？
不管怎么样希望后天RP++吧，争取混个国一水点综测加分的说
合数个数
枚举即可，答案为1713
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
inline bool is_prime(CI x)
{
for (RI i=2;i*i<=x;++i) if (x%i==0) return 0; return 1;
}
int main()
{
freopen("CODE.out","w",stdout);
int ans=0; for (RI i=2;i<=2020;++i)
if (!is_prime(i)) ++ans; return printf("%d",ans),0;
}
含2天数
还是枚举题，注意闰年，答案为1994240
#include<cstdio>
#include<iostream>
#include<cmath>
#define RI register int
#define CI const int&
using namespace std;
const int mouth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int ans;
int main()
{
freopen("CODE.out","w",stdout);
auto fix=[&](CI y,CI m)
{
if (m!=2) return false;
return y%400==0||(y%4==0&&y%100!=0);
};
auto calc=[&](int x)
{
while (x) { if (x%10==2) return 1; x/=10; } return 0;
};
for (RI y=1900,m,d;y<=9999;++y)
for (m=1;m<=12;++m) for (d=1;d<=mouth[m]+fix(y,m);++d)
if (calc(y)||calc(m)||calc(d)) ++ans;
return printf("%d",ans),0;
}
本质上升序列
考虑暴力DP，用\(f_i\)表示以\(i\)为结尾的本质不同的LIS个数
由于要求本质不同，所以在处理完\(s_i\)后要把所有\(s_j=s_i,j<i\)的\(f_j\)变为\(0\)
总复杂度\(O(n^2)\)，答案为3616159
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200;
const char s[N+1]="tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf\
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij\
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad\
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhewl";
long long f[N+1],ans;
int main()
{
freopen("CODE.out","w",stdout);
RI i,j; for (i=0;i<N;++i) for (f[i]=1,j=0;j<i;++j)
if (s[j]<s[i]) f[i]+=f[j]; else if (s[j]==s[i]) f[j]=0;
for (i=0;i<N;++i) ans+=f[i]; return printf("%lld",ans),0;
}
咫尺天涯
感觉算是做过的所有蓝桥杯的代码填空题中最难的一个了，不过写了这题后面另一个皮亚诺曲线的题就不用写了
大致的思路就是递推答案，考虑如果已经求出\(k-1\)阶的答案为\(F(k-1)\)，则\(k\)阶的答案可以表示为拆分成\(3\times 3\)个小的区域，其中每个区域都是一个\(k-1\)阶皮亚诺曲线
每个\(k-1\)阶的答案已经知道了，然后考虑这些块之间产生的新的答案，不难递推出\(F(k)\)
计算新的影响的话由于数据范围直接枚举会产生贡献的点即可，但直接求两点间的皮亚诺曲线距离不是很方便
所以我们可以写一个函数用来求某个坐标到原点的皮亚诺曲线长度，由于这个就是F题的核心了，所以就放在后面在讲
然后放着耐心跑一会就可以得到答案184731576397539360
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=13;
int pw[N],ans;
inline int calc(CI k,int x,int y)
{
if (!k) return 0;
int shift=x/pw[k]*3,type=shift==3;
if (type) shift+=3-y/pw[k]-1; else shift+=y/pw[k];
if (shift%2==1) x=pw[k]-x%pw[k]-1;
if (type) return (shift+1)*pw[k]*pw[k]-calc(k-1,x%pw[k],y%pw[k])-1;
else return shift*pw[k]*pw[k]+calc(k-1,x%pw[k],y%pw[k]);
}
signed main()
{
freopen("CODE.out","w",stdout);
RI i,j; for (pw[1]=1,i=2;i<=12;++i) pw[i]=3LL*pw[i-1];
for (i=1;i<=12;++i)
{
int ret=0; for (j=0;j<pw[i+1];++j)
{
ret+=abs(calc(i,j,pw[i])-calc(i,j,pw[i]-1));
ret+=abs(calc(i,pw[i],j)-calc(i,pw[i]-1,j));
}
ans=9LL*ans+2LL*ret;
}
return printf("%lld",ans),0;
}
玩具蛇
比D题简单到不知道哪里去了，直接爆搜即可，答案552
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=5,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int ans; bool vis[N][N];
inline void DFS(CI x,CI y,CI cur)
{
if (cur==16) return (void)(++ans); vis[x][y]=1;
for (RI i=0;i<4;++i)
{
int nx=x+dx[i],ny=y+dy[i];
if (nx<1||nx>4||ny<1||ny>4) continue;
if (!vis[nx][ny]) DFS(nx,ny,cur+1);
}
vis[x][y]=0;
}
int main()
{
freopen("CODE.out","w",stdout);
for (RI i=1;i<=4;++i) for (RI j=1;j<=4;++j) DFS(i,j,1);
return printf("%d",ans),0;
}
皮亚诺曲线距离
主要就是要实现某点到原点的距离，这个显然可以递归实现
就是通过一些判断求出这个位置是在那个\(k-1\)阶皮亚诺曲线中，然后看图发现有些位置要反着算贡献，有些位置要正着算，简单推导一下即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=40;
int pw[N],k,x1,y1,x2,y2;
inline int calc(CI k,int x,int y)
{
if (!k) return 0;
int shift=x/pw[k]*3,type=shift==3;
if (type) shift+=3-y/pw[k]-1; else shift+=y/pw[k];
if (shift%2==1) x=pw[k]-x%pw[k]-1;
if (type) return (shift+1)*pw[k]*pw[k]-calc(k-1,x%pw[k],y%pw[k])-1;
else return shift*pw[k]*pw[k]+calc(k-1,x%pw[k],y%pw[k]);
}
signed main()
{
scanf("%lld%lld%lld%lld%lld",&k,&x1,&y1,&x2,&y2); k=min(k,39LL);
RI i,j; for (pw[1]=1,i=2;i<=k;++i) pw[i]=3LL*pw[i-1];
return printf("%lld",abs(calc(k,x1,y1)-calc(k,x2,y2))),0;
}
出租车
额对于这个题我只能说如果考场上看到了还是绕的远远的吧，稍微YY了下感觉建图细节有亿点点多
有这个时间不去把后面分值高的题目多拿点部分分啥的，我认为是不明智的
除非你能光速切完其它的所有题然后回来慢悠悠的写，否则还是不建议开的
其实说白了就是一个模拟建图然后跑最短路的题目，但由于涉及到等红绿灯这个东西细节爆炸，完全不想写了
答疑
你看出租车和这个傻逼题是一个分值的，所以比赛的时候千万不要被题目顺序搞了，毕竟4小时10题还要对拍，策略还是很重要的
这题没啥好说的，最经典的贪心问题，把所有人按照需要的总时间之和从小到大排序后模拟一遍即可
证明的话就是经典的接水模型，通过证明此时交换任意两个人都不会导致答案变优
复杂度\(O(n\log n)\)，也不知道给个\(n=1000\)的范围是不是给不会调用库函数的人手写\(O(n^2)\)排序准备的
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
struct Data
{
int s,a,e;
inline Data(CI S=0,CI A=0,CI E=0)
{
s=S; a=A; e=E;
}
friend inline bool operator < (const Data& A,const Data& B)
{
return A.s+A.a+A.e<B.s+B.a+B.e;
}
}a[N]; int n; long long ans,lst;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d%d%d",&a[i].s,&a[i].a,&a[i].e);
for (sort(a+1,a+n+1),i=1;i<=n;++i) ans+=lst+a[i].s+a[i].a,lst+=a[i].s+a[i].a+a[i].e;
return printf("%lld",ans),0;
}
奇偶覆盖
典中典的题，感觉和21年的括号序列以及22年的那个主席树比起来差的不是一点半点
首先二维平面上的矩形覆盖，一眼扫描线，并把覆盖奇数次看作\(1\)，覆盖偶数次看作\(0\)，此时问题转化为区间\(0/1\)反转与求区间的\(0/1\)个数
很显然直接用线段树维护区间\(0/1\)个数，然后维护个反转次数的标记，如果下传的时候标记是奇数就交换\(0/1\)个数
但是这样直接做会有一个问题就是会把未被覆盖的位置也统计上去，那也好办
我们额外维护下未被覆盖的位置的个数然后减去即可，具体实现的话由于扫描线维护区间内\(0\)的个数可以转化成区间最小值的出现次数（因为区间\(+1\)操作永远在\(-1\)之前，因此不会有负数）
那么用一个二元组\((x,y)\)表示区间最小值为\(x\)，\(x\)出现的次数为\(y\)，在pushup的时候更新即可
最后还有一个细节就是这题的数据范围需要离散化，而离散化的扫描线就不适合直接维护闭区间了
因为这样叶子节点的权值会没有定义，并且合并两个区间的时候中间的\(mid\)和\(mid+1\)间的贡献就计算不清
处理方法也很简单，把线段树上区间统一改为左闭右开即可，具体实现可以看代码
总复杂度\(O(n\log n)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
struct Data
{
int x,l,r,opt;
inline Data(CI X=0,CI L=0,CI R=0,CI OPT=0)
{
x=X; l=L; r=R; opt=OPT;
}
friend inline bool operator < (const Data& A,const Data& B)
{
return A.x<B.x;
}
}x[N]; int n,cnt,rsty[N],cnty,x_1,y_1,x_2,y_2; long long ans[2];
class Segment_Tree
{
private:
struct segment
{
pi num,val; int tag;
}node[N<<2];
#define N(x) node[x].num
#define V(x) node[x].val
#define T(x) node[x].tag
#define L(x) node[x].len
#define TN CI now=1,CI l=1,CI r=cnty-1
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline void apply(CI now,CI mv)
{
if (mv&1) swap(N(now).fi,N(now).se); V(now).fi+=mv; T(now)+=mv;
}
inline void pushup(CI now)
{
N(now).fi=N(now<<1).fi+N(now<<1|1).fi;
N(now).se=N(now<<1).se+N(now<<1|1).se;
if (V(now<<1).fi<V(now<<1|1).fi) V(now)=V(now<<1); else
if (V(now<<1).fi>V(now<<1|1).fi) V(now)=V(now<<1|1); else
V(now)=pi(V(now<<1).fi,V(now<<1).se+V(now<<1|1).se);
}
inline void pushdown(CI now)
{
if (T(now)) apply(now<<1,T(now)),apply(now<<1|1,T(now)),T(now)=0;
}
public:
inline void build(TN)
{
N(now).fi=V(now).se=rsty[r+1]-rsty[l]; if (l==r) return;
int mid=l+r>>1; build(LS); build(RS); pushup(now);
}
inline void modify(CI beg,CI end,CI mv,TN)
{
if (beg<=l&&r<=end) return apply(now,mv); int mid=l+r>>1; pushdown(now);
if (beg<=mid) modify(beg,end,mv,LS); if (end>mid) modify(beg,end,mv,RS); pushup(now);
}
inline pi query(void)
{
pi tmp=N(1); if (!V(1).fi) tmp.fi-=V(1).se; return tmp;
}
#undef N
#undef V
#undef T
#undef TN
#undef LS
#undef RS
}SEG;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<=n;++i)
{
scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
x[++cnt]=Data(x_1,y_1,y_2,1); x[++cnt]=Data(x_2,y_1,y_2,-1);
rsty[++cnty]=y_1; rsty[++cnty]=y_2;
}
sort(rsty+1,rsty+cnty+1); cnty=unique(rsty+1,rsty+cnty+1)-rsty-1;
for (i=1;i<=cnt;++i)
{
x[i].l=lower_bound(rsty+1,rsty+cnty+1,x[i].l)-rsty;
x[i].r=lower_bound(rsty+1,rsty+cnty+1,x[i].r)-rsty;
}
for (SEG.build(),sort(x+1,x+cnt+1),x[cnt+1].x=x[cnt].x,i=1;i<=cnt;++i)
{
SEG.modify(x[i].l,x[i].r-1,x[i].opt);
pi tmp=SEG.query(); int dlt=x[i+1].x-x[i].x;
ans[0]+=1LL*tmp.fi*dlt; ans[1]+=1LL*tmp.se*dlt;
}
return printf("%lld\n%lld",ans[1],ans[0]),0;
}
蓝跳跳
真是无比逆天的巧合，学校的数学专题刚好出了这题一模一样的版本，不过数据范围不一样而且模数是NTT模数，这题的模数属实逆天
回到题目不难发现很容易写一个暴力DP，设\(f_i\)表示当前一共跳了\(i\)步，且上一步跳的步数在\([1,p-1]\)范围内的方案数，\(g_i\)表示当前一共跳了\(i\)步，且上一步跳的步数在\([p,k]\)范围内的方案数，则显然有转移：
然后不难发现如果我们把\(g_n\)的表达式带回到第一个式子，就得到：
虽然后面是两个求和符号的复合，但不难看出如果把\(i+j\)看作一体的话其实也是一个\(\sum_{t=p+1}^{t=k+p-1} c_t\times f_{n-t}\)的形式
换句话说，这是一个常系数齐次线性递推的模型，一般常见且好写的做法就是矩阵快速幂，写的好的话可以拿到这题80%的分数
正解的话有两种做法，一种是用多项式取模来优化常系数齐次线性递推模型，不过由于模数不是NTT模数（TMD甚至不是质数），所以要写MTT或者三模NTT
或者注意到这里的\(p+k\)的范围其实不大，其实可以扔掉NTT，直接暴力\(O((p+k)^2)\)进行多项式取模，总复杂度为\(O((p+k)^2\times \log L)\)，可以轻松跑过
#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=4005,mod=20201114;
int a,b,k,f[N],g[N],t[N],ans; long long c;
inline int sum(CI x,CI y)
{
return x+y>=mod?x+y-mod:x+y;
}
inline int sub(CI x,CI y)
{
return x-y<0?x-y+mod:x-y;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
struct Poly
{
int a[N];
inline Poly(void) { memset(a,0,sizeof(a)); }
inline int& operator [] (CI x) { return a[x]; }
friend inline Poly operator * (Poly A,Poly B)
{
Poly C; RI i,j; for (i=0;i<k;++i) for (j=0;j<k;++j) C[i+j]=sum(C[i+j],1LL*A[i]*B[j]%mod);
for (i=(k-1)*2;i>=k;C[i]=0,--i) for (j=1;j<=k;++j) C[i-j]=sum(C[i-j],1LL*C[i]*t[j]%mod);
return C;
}
friend inline Poly operator ^ (Poly A,long long p)
{
Poly mul; mul[0]=1; for (;p;p>>=1,A=A*A) if (p&1) mul=mul*A; return mul;
}
};
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; scanf("%d%d%lld",&a,&b,&c); k=a+b-1;
for (f[0]=i=1;i<=k;++i)
{
for (j=1;j<=min(b-1,i);++j) f[i]=sum(f[i],sum(f[i-j],g[i-j]));
for (j=b;j<=min(a,i);++j) g[i]=sum(g[i],f[i-j]);
}
for (i=1;i<=k;++i) f[i]=sum(f[i],g[i]);
if (c<=k) return printf("%d",f[c]),0;
for (i=1;i<=b-1;++i) t[i]=1;
for (i=1;i<=b-1;++i) for (j=b;j<=a;++j) ++t[i+j];
Poly D; D[1]=1; D=D^(c-1);
//for (i=0;i<k;++i) printf("%d\n",D[i]);
for (i=0;i<k;++i) ans=sum(ans,1LL*D[i]*f[i+1]%mod);
return printf("%d",ans),0;
}
Postscript
完了突然转念一想好多板子我打的是一点不熟，上次省赛已经因为忘板子被教育了
但由于好多SB实践课期末要交报告最近也是一直在忙这些零碎的东西，稍微空出来的时间还在补《Island》的杂谈以及看《Clannad》
六级和期末考试也临近了，这个月压力很大啊的说，不过熬过去就到暑假爽训的时间了，起飞