Preface
开始做下往年蓝桥杯的决赛题，然后直接被题面搞红温了
最后那个括号序列树的题意是纯让人猜谜吗，出题人多写两句话会似？
其它题目除了把一个超难的大分类讨论放在前面搞人心态外，感觉比省赛还简单一个维度
也许是这场的难题主要是DS题的原因？如果是DP或者数论偏难的话做起来就不舒服了
值得一提的是发现了Luogu上也有蓝桥杯全套的题，这下不得不回归初心了
小蓝与钥匙
一眼题，先\(C_{28}^{14}\)定下哪些人分到的是自己的，然后剩下的用错排公式算就好了
错排公式：\(f(n)=(n-1)\times (f(n-1)+f(n-2))\)，初值：\(f(1)=0,f(2)=1\)
前面以为会爆long long的就用Python写了，答案1286583532342313400
f=[0]*30
f[1]=0
f[2]=1
for i in range(3,15):
f[i]=(i-1)*(f[i-1]+f[i-2])
ret=1
for i in range(15,29):
ret*=i
for i in range(1,15):
ret//=i
print(f[14]*ret)
排列距离
一眼题，直接康托展开得到两个串的康托序后比较下用哪种方式变换更近即可
康托展开：从前往后每一位\(a_i\)，找出后面有多少位的\(a_j\)是小于它的，然后乘上系数\((n-i)!\)即可
也是怕爆long long所以用的Python，答案106148357572143
fact=[1]*20
for i in range(1,18):
fact[i]=fact[i-1]*i
def Cantor(s):
ret=0
for i in range(len(s)):
cur=0
for j in range(i+1,len(s)):
cur+=(s[j]<s[i])
ret+=cur*fact[len(s)-i-1]
return ret
CA=Cantor("aejcldbhpiogfqnkr")
CB=Cantor("ncfjboqiealhkrpgd")
print(min(CB-CA,fact[17]-(CB-CA)))
内存空间
简单模拟题，感觉没什么好说的就硬模拟即可，代码其实很好写
这次学会了用getline了，上次校赛不会这个给我人整麻了
值得一提的是这个语句的语法规则怎么是JAVA的啊，放在C++组搞叛逆是吧
#include<cstdio>
#include<iostream>
#include<string>
#define RI register int
#define CI const int&
using namespace std;
int t; long long ret; string s;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t),getchar();t;--t)
{
RI i; getline(cin,s);
if (s.find('[')!=s.npos)
{
int lst=s.find(']'),L,R,coef=s[0]=='i'?4:8;
while (L=s.find('[',lst+1),R=s.find(']',lst+1),L!=s.npos&&R!=s.npos)
{
int cur=0; for (i=L+1;i<R;++i) cur=cur*10+s[i]-'0';
ret+=1LL*coef*cur; lst=R;
}
} else if (s[0]=='S')
{
int lst=-1,L,R;
while (L=s.find('"',lst+1),R=s.find('"',L+1),L!=s.npos&&R!=s.npos)
ret+=R-L-1,lst=R;
} else
{
int coef=s[0]=='i'?4:8,cur=0;
for (i=0;i<s.size();++i) if (s[i]=='=') ++cur;
ret+=1LL*coef*cur;
}
}
int B=ret%1024,KB=ret/1024,MB,GB;
MB=KB/1024; KB%=1024; GB=MB/1024; MB%=1024;
if (GB) printf("%dGB",GB); if (MB) printf("%dMB",MB);
if (KB) printf("%dKB",KB); if (B) printf("%dB",B);
return 0;
}
最大公约数
一眼题，首先判断序列中原来有没有\(1\)，如果有就直接从它出发把其它数都变成\(1\)即可
否则我们显然就是要用最小的步数先得到一个\(1\)，然后再操作\(n-1\)次即可，因此问题转化为求一个最小的区间使得区间内所有数的\(\gcd\)为\(1\)
很容易想到设\(f_i\)表示所有以\(i\)为结尾的二元组\((a,b)\)的集合，表示区间的\(\gcd=a\)的左端点\(b\)的最大值
由\(\gcd\)的性质\(|f_i|\le \log a_i\)，因此总复杂度\(O(n\log^2 n)\)（用map的话是多一个\(\log\)的，不过这题不卡时间也无所谓）
#include<cstdio>
#include<iostream>
#include<map>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,x,ans=1e9,num1; map <int,int> f;
inline int gcd(CI n,CI m)
{
return m?gcd(m,n%m):n;
}
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",&x); num1+=x==1;
map <int,int> tmp; for (auto [a,b]:f)
if (gcd(a,x)==1) ans=min(ans,i-b); else tmp[gcd(a,x)]=b;
if (!tmp.count(x)) tmp[x]=i; f=tmp;
}
if (ans==1e9) return puts("-1"),0;
return printf("%d",num1?n-num1:ans+n-1),0;
}
owo
最毒瘤的一题来了，一眼看得出就是根据前后缀分类讨论，但细节太多给我CPU搞过载了
不过听说实际上官方的数据极水无比所以很多乱搞做法都能过，所以比赛的时候可以写点骗分的东西试试
具体的做法基本全是看Luogu上的题解，大致思路就是先把串内部的答案固定下来，然后仅考虑拼接时产生的贡献
把所有串的情况分成\(10\)类然后贪心合并就行了，总之恶心至极建议\remake
#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int n,c[10],t[10],ans; char s[N];
/*
0: o-o
1: o-ow
2: o-ww
3: wo-o
4: wo-ow
5: wo-ww
6: ww-o
7: ww-ow
8: ww-ww
9: w
*/
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
{
scanf("%s",s+1); int len=strlen(s+1);
for (j=1;j<=len-2;++j) if (s[j]=='o'&&s[j+1]=='w'&&s[j+2]=='o') ++ans;
if (len==1&&s[1]=='w') ++c[9]; else
if (s[1]=='o'&&s[len]=='o') ++c[0]; else
if (s[1]=='o'&&s[len-1]=='o'&&s[len]=='w') ++c[1]; else
if (s[1]=='o'&&s[len-1]=='w'&&s[len]=='w') ++c[2]; else
if (s[1]=='w'&&s[2]=='o'&&s[len]=='o') ++c[3]; else
if (s[1]=='w'&&s[2]=='o'&&s[len-1]=='o'&&s[len]=='w') ++c[4]; else
if (s[1]=='w'&&s[2]=='o'&&s[len-1]=='w'&&s[len]=='w') ++c[5]; else
if (s[1]=='w'&&s[2]=='w'&&s[len]=='o') ++c[6]; else
if (s[1]=='w'&&s[2]=='w'&&s[len-1]=='o'&&s[len]=='w') ++c[7]; else ++c[8];
for (j=0;j<10;++j) t[j]=c[j]; int ret=0,tmp;
if (t[0]||t[4]) ret+=t[1]+t[3],t[1]=t[3]=0;
if (t[1]&&(t[2]||t[7])) ret+=t[1],t[1]=0;
if (t[3]&&(t[5]||t[6])) ret+=t[3],t[3]=0;
if (t[0]&&t[5]) tmp=min(t[0],t[4]),ret+=tmp*2,t[0]-=tmp,t[4]-=tmp;
tmp=min(t[0],t[5]); ret+=tmp; t[0]-=tmp; t[5]-=tmp; t[2]+=tmp;
if (t[2]&&t[4]) tmp=min(t[0],t[4]),ret+=tmp*2,t[0]-=tmp,t[4]-=tmp;
tmp=min(t[2],t[4]); ret+=tmp; t[2]-=tmp; t[4]-=tmp; t[5]+=tmp;
tmp=min(t[0],t[5]); ret+=tmp; t[0]-=tmp; t[5]-=tmp; t[2]+=tmp;
if (t[0]&&t[7]) tmp=min(t[0],t[4]),ret+=tmp*2,t[0]-=tmp,t[4]-=tmp;
tmp=min(t[0],t[7]); ret+=tmp; t[0]-=tmp; t[7]-=tmp; t[6]+=tmp;
if (t[4]&&t[6]) tmp=min(t[0],t[4]),ret+=tmp*2,t[0]-=tmp,t[4]-=tmp;
tmp=min(t[4],t[6]); ret+=tmp; t[4]-=tmp; t[6]-=tmp; t[7]+=tmp;
tmp=min(t[0],t[7]); ret+=tmp; t[0]-=tmp; t[7]-=tmp; t[6]+=tmp;
tmp=min(t[2],t[7]); ret+=tmp; t[2]-=tmp; t[7]-=tmp;
tmp=min(t[5],t[6]); ret+=tmp; t[5]-=tmp; t[6]-=tmp;
if (t[1]) ret+=t[1]-1,t[1]=1; if (t[3]) ret+=t[3]-1,t[3]=1;
if (tmp=min(t[0],t[4]),tmp&&t[0]==t[4]) { if (--ret,t[1]<t[3]) ++t[1]; else ++t[3]; }
t[0]-=tmp; t[4]-=tmp; ret+=tmp*2; int pre=t[3]+t[6],suf=t[1]+t[2];
tmp=min(min(pre,suf),t[9]); ret+=tmp; pre-=tmp; suf-=tmp; t[9]-=tmp;
if (!(tmp|pre|suf)) t[0]=max(t[0]-1,0); ret+=min(t[0],t[9]);
printf("%d\n",ans+ret);
}
return 0;
}
环境治理
一眼题，显然答案具有可二分性，然后套个Floyd上去就完了，算是这场真正的签到题了
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int n,Q,g[N][N],l[N][N],dis[N][N];
inline int Floyd(void)
{
RI i,j,k; for (k=1;k<=n;++k) for (i=1;i<=n;++i) for (j=1;j<=n;++j)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
int sum=0; for (i=1;i<=n;++i) for (j=1;j<=n;++j) sum+=dis[i][j]; return sum;
}
inline bool check(CI x)
{
RI i,j; for (i=1;i<=n;++i) for (j=1;j<=n;++j) dis[i][j]=g[i][j];
for (i=1,j;i<=n;++i)
{
for (j=1;j<=n;++j) dis[i][j]=max(l[i][j],dis[i][j]-(x/n+(i<=x%n)));
for (j=1;j<=n;++j) dis[j][i]=max(l[j][i],dis[j][i]-(x/n+(i<=x%n)));
}
return Floyd()<=Q;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d%d",&n,&Q),i=1;i<=n;++i)
for (j=1;j<=n;++j) scanf("%d",&g[i][j]);
for (i=1;i<=n;++i) for (j=1;j<=n;++j) scanf("%d",&l[i][j]),dis[i][j]=l[i][j];
if (Floyd()>Q) return puts("-1"),0;
int l=0,r=1e7,mid,ret; while (l<=r)
if (check(mid=l+r>>1)) ret=mid,r=mid-1; else l=mid+1;
return printf("%d",ret),0;
}
选素数
水爆了的数论题，首先不难发现质数和\(1\)是无解的直接判掉
否则我们设\(n\)存在真质因子\(p\in(1,n)\)，则第一次操作后数的可取范围即为\((n-p,n]\)
不难发现较大的\(p\)的选法会囊括较小的\(p\)的选法，因此相当于找\(n\)最大的质因数\(p_{\max}(n)\)
然后我们直接枚举\(i\in(n-p,n]\)，不难发现推理过程和上面一样，最后就是求\(\min_\limits{n-p<i\le n} (i-p_{\max}(i)+1)\)的值
预处理出每个数的最大质因子后就可以\(O(n)\)枚举了，而由于欧拉筛得到的是最小质因子，我们直接改用埃氏筛即可
总复杂度\(O(n\log \log n)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1000005;
int n,mxp[N],ans=1e9; bool vis[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d",&n),i=2;i<=n;++i) if (!vis[i])
for (mxp[i]=i,j=i<<1;j<=n;j+=i) vis[j]=1,mxp[j]=max(mxp[j],i);
if (!vis[n]) return puts("-1"),0;
for (i=n-mxp[n]+1;i<=n;++i) if (vis[i]) ans=min(ans,i-mxp[i]+1);
return printf("%d",ans),0;
}
替换字符
一眼题，但是是分块（乐
感觉好像以前在ynoi做过这种题来着，这题就是分块之后对于散块暴力修改，然后整块就打一个标记
每次修改散块或者最后回答的时候统一处理下整块的信息即可
这里由于字符集的大小很小可以直接暴力，否则应该要用魔改过的并查集
由于一次修改最多带来\(O(\sqrt n)\)个标记，每个标记的处理复杂度是\(O(26)\)的，因此可以把块的大小搞大点会跑的更快
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<utility>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
typedef pair <int,int> pi;
char s[N],x[10],y[10]; int n,m,l,r,sz,blk[N],fa[30]; bool vis[30]; vector <pi> v[N];
inline void reset(CI x)
{
if (v[x].empty()) return;
RI i; for (i=0;i<26;++i) fa[i]=i;
for (auto [u,v]:v[x])
{
for (i=0;i<26;++i) if (fa[i]==u) fa[i]=v; vis[u]=0;
}
for (v[x].clear(),i=(x-1)*sz+1;i<=min(n,x*sz);++i) s[i]=fa[s[i]-'a']+'a';
}
inline void modify(CI l,CI r,CI x,CI y)
{
if (blk[l]==blk[r])
{
reset(blk[l]); for (RI i=l;i<=r;++i)
if (s[i]==x) s[i]=y; return;
}
RI i; reset(blk[l]); reset(blk[r]);
for (i=l;i<=min(n,blk[l]*sz);++i) if (s[i]==x) s[i]=y;
for (i=(blk[r]-1)*sz+1;i<=r;++i) if (s[i]==x) s[i]=y;
for (i=blk[l]+1;i<blk[r];++i) v[i].push_back(pi(x-'a',y-'a'));
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%s",s+1),n=strlen(s+1),sz=sqrt(n)*5,i=1;i<=n;++i) blk[i]=(i-1)/sz+1;
for (scanf("%d",&m),i=1;i<=m;++i) scanf("%d%d%s%s",&l,&r,x,y),modify(l,r,x[0],y[0]);
for (i=1;i<=blk[n];++i) reset(i); return printf("%s",s+1),0;
}
三角序列
思路很顺畅的DS题，不过码量也不大写起来也很快
答案一眼可二分性，先考虑二分高度\(h\)转化为判定性问题
不难想到把询问拆成两端的不完整的，以及中间的完整的部分，其中找到\(l_i,r_i\)所属的三角形可以二分，散块的暴力判断也很简单
此时对于中间那部分，答案显然和\(b_i\)就无关了，我们稍加讨论就发现：
- 当\(a_i\le h\)时，贡献为\(\frac{a_i(a_i+1)}{2}\)
- 当\(a_i>h\)时，贡献为\(\frac{h\cdot(2a_i-h+1)}{2}=h\cdot a_i-\frac{h(h-1)}{2}\)
很自然地想到可以用权值线段树，\(a_i\)为下标，维护每个区间的\(\frac{a_i(a_i+1)}{2},a_i\)的和以及元素的个数，查询的时候就分成大于\(h\)和小于等于\(h\)两部分在线段树上二分即可
然后由于询问涉及到区间，因此上主席树即可，总复杂度\(O(n\log^2n)\)
#include<cstdio>
#include<iostream>
#include<cctype>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
const int N=200005,M=1e6+5;
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
char Fin[S],*A,*B;
public:
Tp inline void read(T& x)
{
x=0; char ch; bool flag=0; while (!isdigit(ch=tc())) if (ch=='-') flag=1;
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc())); if (flag) x=-x;
}
#undef tc
}F; int n,m,a[N],b[N],st[N],rt[N],L,R,v;
class Segment_Tree
{
private:
struct segment
{
int ch[2],num,sum,psum;
}node[M*40]; int tot;
public:
#define lc(x) node[x].ch[0]
#define rc(x) node[x].ch[1]
inline void insert(CI lst,int& now,CI pos,CI l=1,CI r=1e6+1)
{
now=++tot; node[now]=node[lst]; ++node[now].num;
node[now].sum+=pos; node[now].psum+=pos*(pos+1)/2LL;
if (l==r) return; int mid=l+r>>1;
if (pos<=mid) insert(lc(lst),lc(now),pos,l,mid); else insert(rc(lst),rc(now),pos,mid+1,r);
}
inline int query_less(CI lst,CI now,CI h,CI l=1,CI r=1e6+1)
{
if (l==r) return node[now].psum-node[lst].psum; int mid=l+r>>1;
if (h<=mid) return query_less(lc(lst),lc(now),h,l,mid);
else return node[lc(now)].psum-node[lc(lst)].psum+query_less(rc(lst),rc(now),h,mid+1,r);
}
inline int query_greater(CI lst,CI now,CI h,CI l=1,CI r=1e6+1)
{
if (l==r) return node[now].sum-node[lst].sum; int mid=l+r>>1;
if (h>mid) return query_greater(rc(lst),rc(now),h,mid+1,r);
else return node[rc(now)].sum-node[rc(lst)].sum+query_greater(lc(lst),lc(now),h,l,mid);
}
inline int query_num(CI lst,CI now,CI h,CI l=1,CI r=1e6+1)
{
if (l==r) return node[now].num-node[lst].num; int mid=l+r>>1;
if (h>mid) return query_num(rc(lst),rc(now),h,mid+1,r);
else return node[rc(now)].num-node[rc(lst)].num+query_num(lc(lst),lc(now),h,l,mid);
}
#undef lc
#undef rc
}SEG;
inline int check(CI h)
{
auto find=[&](CI x)
{
return upper_bound(st+1,st+n+2,x)-st-1;
};
auto calc=[&](CI id,int L,int R)
{
L-=st[id]-1; R-=st[id]-1;
int A=b[id]?a[id]-L+1:L,B=b[id]?a[id]-R+1:R;
if (A>B) swap(A,B); if (h<=A) return h*(R-L+1);
if (h>=B) return (A+B)*(R-L+1)/2LL;
return (A+h)*(h-A+1)/2LL+h*(B-h);
};
int posL=find(L),posR=find(R);
if (posL==posR) return calc(posL,L,R);
int ret=0; if (posL+1<=posR-1)
{
ret=SEG.query_less(rt[posL],rt[posR-1],h);
ret+=h*SEG.query_greater(rt[posL],rt[posR-1],h+1);
ret-=h*(h-1)/2LL*SEG.query_num(rt[posL],rt[posR-1],h+1);
}
return ret+calc(posL,L,st[posL]+a[posL]-1)+calc(posR,st[posR],R);
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (F.read(n),F.read(m),i=1;i<=n;++i)
F.read(a[i]),F.read(b[i]),st[i]=i!=1?st[i-1]+a[i-1]:1;
for (i=1;i<=n;++i) SEG.insert(rt[i-1],rt[i],a[i]);
for (st[n+1]=st[n]+a[n],i=1;i<=m;++i)
{
F.read(L); F.read(R); F.read(v); int l=1,r=1e6,mid,ret=-1;
while (l<=r) if (check(mid=l+r>>1)>=v) ret=mid,r=mid-1; else l=mid+1;
printf("%lld\n",ret);
}
return 0;
}
括号序列树
这是我的问题吗，反复看了好几遍题意也不知道在讲什么，然后样例上来就一个大情况屁都理解不了，做尼玛
后来没办法看了题解才知道就是先假设这棵树是一棵深度\(2n+1\)的完全二叉树，然后不停地删除表示不合法括号序列的叶子节点，直到所有的叶子节点都是表示某个合法括号序列
然后要在剩下的这棵树上求一个最大匹配，图的一个匹配就是选择一个边集，要满足每个点至多只能在边集里的边的端点出现一次
（所以出题人花一两行把上面的东西讲清楚很难吗？花大300块来受气真是***）
回到题目本身，不难发现从深度小的点向下匹配一定是最优的，否则如果选择跳过等下一层的点来匹配它一定不会更优
而且不难发现上层的每个点至少都会存在一个儿子是可以匹配的，因此答案就是所有奇数层的点的个数
然后后面的做法就很有意思了，可以结合Luogu上的题解里的图看会很清楚
由于形如()((的中间状态和(()(的中间状态在向后转移时可以看作等价的，因此我们可以把这些本质相同的点合并
然后合并完我们观察下系数就会发现是个杨辉三角差分的形式，因此每个点的贡献就很好算了
不过最后要注意合法的括号序列还要保证总和为\(0\)，因此从第\(n+1\)行开始，左下角的一个子树内的贡献就不能被统计入答案了，这个画下图还是很好理解的
最后答案的式子就是
\[\sum_{i=0}^{n-1} C_{2i+1}^i-\sum_{i=\lceil\frac{n}{2}\rceil}^{n-1} C_{2i+1}^{2i-n}
\]
总复杂度\(O(n)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=2000005,mod=998244353;
int n,fac[N],ifac[N],ans;
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;
}
inline void init(CI n)
{
RI i; for (fac[0]=i=1;i<=n;++i) fac[i]=1LL*fac[i-1]*i%mod;
for (ifac[n]=quick_pow(fac[n]),i=n-1;~i;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
return 1LL*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),init(n<<1),i=0;i<n;++i) (ans+=C(2*i+1,i))%=mod;
for (i=(n-1)/2+1;i<n;++i) (ans+=mod-C(2*i+1,2*i-n))%=mod;
return printf("%d",ans),0;
}
Postscript
感觉如果考场上考这场的话还是挺合我口味的，毕竟DS之类的套路记得的还算多
而且没有难的字符串和数论这种我的明显弱项就还好，希望别一口毒奶然后今年全是这些