Preface
周日从家里颓废了一整天再来学校脑子里装的都是shi，什么都不会了……
A - Move and Win
若两人都不后退直接向对方走去，那么只要根据\(b-a\)的奇偶性就可以判断输赢情况了
若其中某个人后退只要另一个人跟进，那么坐标差的奇偶性不变，还是同上判断
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
int n,a,b;
int main()
{
return scanf("%d%d%d",&n,&a,&b),puts((b-a)&1?"Borys":"Alice"),0;
}
B - Ice Rink Game
刚开始脑抽了各种地方写错……
考虑倒推，考虑记录此时答案的可能区间\(l,r\)，那么对于每个\(a_i\)，\(l\to k\times a_i,k\in Z,r\to t\times a_i-1,t\in Z\)
注意这个区间每次显然会增加\(a_i\)级别，因此要开long long
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int k,a[N]; long long l,r;
int main()
{
RI i; for (scanf("%d",&k),i=1;i<=k;++i) scanf("%d",&a[i]);
for (l=r=2,i=k;i;--i)
{
if (r/a[i]==(l-1)/a[i]) return puts("-1"),0;
l=((l-1)/a[i]+1)*a[i]; r=(r/a[i]+1)*a[i]-1;
}
return printf("%lld %lld",l,r),0;
}
C - Median Sum
C都不会，和陈指导硬想了半小时直接GG
考虑我们如果加入\(\emptyset\)之后中位数其实就是\(\frac{\sum_{i=1}^n a_i}{2}\)，因为此时对于任意一种选取方案，它的补集和它一定在\(\frac{\sum_{i=1}^n a_i}{2}\)的两侧
那么现在去掉\(\emptyset\)后答案就是\(\frac{\sum_{i=1}^n a_i}{2}\)的后缀了，由于只要找到一个存在的直接用bitset优化即可做到\(O(n^2 a_i)\)
#include<cstdio>
#include<bitset>
#define RI register int
#define CI const int&
using namespace std;
const int N=2005;
bitset <N*N> f; int n,a[N],sum;
int main()
{
RI i; for (scanf("%d",&n),f[0]=i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i],f|=f<<a[i];
for (i=(sum+1)>>1;i<=sum;++i) if (f[i]) return printf("%d",i),0; return 0;
}
D - Min Max Repetition
对着我写得一坨shi的代码我都直接自闭了，最后还是看曲明姐姐的实现的……
首先我们发现最少的连续长度是\(\lceil \frac{\max(a,b)}{\min(a,b)+1}\rceil\)，并且答案的构造方式一定是以\(A^kB\)为前缀，\(AB^k\)为后缀
，中间一段连续的\(A\)和一段连续的\(B\)（长度均小于等于\(k\)）
因此我们只需要找出前缀和后缀的分界点就可以快速计算每个位置的值了
注意到最优情况下分界点处必为一个\(1\)，且这个\(1\)为前后缀所共用
假设分界点之前有\(fa\)个\(A\)，\(fb\)个\(b\)，那么有\(fb\le \max(0,\lfloor \frac{fa-1}{k}\rfloor),fa=a-\lceil\frac{b-fb}{k}\rceil+1\)，带入后有\(fb\le \lfloor \frac{a-\lceil\frac{b-fb}{k}\rceil}{k}\rfloor\)
当\(fb\)增大时，左边增大右边减小，因此可以二分找到最大的\(fb\)即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,a,b,c,d,k;
inline int calc(CI x)
{
return (a-((b-x-1)/k+1))/k;
}
int main()
{
for (scanf("%d",&t);t;--t)
{
RI i; scanf("%d%d%d%d",&a,&b,&c,&d); --c; --d; k=(a+b)/(min(a,b)+1);
if (k==1) { for (i=c;i<=d;++i) putchar((i+(b>a))&1?'B':'A'); putchar('\n'); continue; }
int l=0,r=b,mid,fb=0; while (l<=r)
if (mid=l+r>>1,mid<=calc(mid)) fb=mid,l=mid+1; else r=mid-1;
int lim=a-((b-fb-1)/k+1)+1+fb; for (i=c;i<=d;++i)
putchar(i<lim?(i%(k+1)==k?'B':'A'):((a+b-i)%(k+1)?'B':'A')); putchar('\n');
}
return 0;
}
E - Encoding Subsets
复杂度证明题，根本没想到是爆搜就过了，本来陈指导想到了那个区间DP以为复杂度假了就直接扔了
首先假设字符串固定，如何求方案数，设\(f_{l,r}\)表示将\([l,r]\)编码的方案数，\(g_{l,r}\)表示将\([l,r]\)编码为一个字符的方案数，则转移有：
\[f_{l,r}=\sum_{k=l}^{k-1} g_{l,k}\times f_{k+1,r}\\ g_{l,r}=\sum_{d|r-l+1} [\text{d为[l,r]的循环节}] f_{l,l+d-1} \]考虑对于原问题，我们发现此时\(1\)可以任意匹配\(0\)，但是如果匹配之后这一位要是\(1\)则必须都是\(1\)，是一个子串取并的过程
考虑直接把字符串拿来定义状态，记忆化一下即可通过，复杂度证明可以看dalao's blog，大概是\(O(n^5+n^2\times 2^{\frac{n}{8}})\)的
#include<cstdio>
#include<string>
#include<map>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int mod=998244353;
string s; map <string,int> f,g;
inline int F(const string& s);
inline int G(const string& s)
{
if (s=="") return 1; if (s=="0") return 1; if (s=="1") return 2;
if (g.count(s)) return g[s]; int n=s.size(),ans=0;
for (RI i=1,j,k;i<n;++i) if (n%i==0)
{
string t=""; for (j=0;j<i;++j)
{
int c=1; for (k=j;k<n;k+=i) c&=s[k]-'0';
t+=c+'0';
}
(ans+=F(t))%=mod;
}
return g[s]=ans;
}
inline int F(const string& s)
{
if (s=="") return 1; if (f.count(s)) return f[s];
int n=s.size(),ans=0; for (RI i=1;i<=n;++i)
(ans+=1LL*G(s.substr(0,i))*F(s.substr(i,n))%mod)%=mod; return f[s]=ans;
}
int main()
{
return cin>>s,printf("%d",F(s)),0;
}
F - Arcs on a Circle
好巧妙的一题，又学到了有用的计数姿势
首先考虑断环为链，考虑以最长的弧为起点作为链的起点，这样其它的弧在越过起点后多出的部分就无需考虑了，因此现在的弧都变成了线段
本题中最麻烦的莫过于小数坐标无法进行DP，但经过思考我们发现我们不需要知道小数坐标的具体值，只要知道它们的相对顺序即可
具体地，我们用\(n\times c\)个点来表示所有线段的端点，其中整数部分就是\(l_i\times n\)，多出来的就代表它们小数时的相对大小，由于当两条线段相交时的概率可以忽略不计
在\(O(n!)\)枚举每天线段的小数部分的大小关系后，我们设\(f_{i,j,k}\)表示左端点坐标离散化后的不大于\(i\)的线段已经放置完毕，覆盖到的最大的坐标为\(j\)，每条线段是否放置的状态为\(k\)的方案数
转移的时候枚举是否放置每条线段即可，由于小数部分的大小被限定死了，转移是\(O(1)\)的
总复杂度\(O(n!\times 2^n\times (nc)^2)\)
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=305;
int n,c,l[N],f[N][1<<6],cnt,lim; long long ans;
int main()
{
RI i,j,k; for (scanf("%d%d",&n,&c),i=0;i<n;++i) scanf("%d",&l[i]);
sort(l,l+n); lim=1<<n-1; do
{
for (i=0;i<=c*n;++i) for (j=0;j<lim;++j) f[i][j]=0;
for (f[l[n-1]*n][0]=i=1;i<=c*n;++i)
{
int p=i%n-1; if (p<0) continue;
for (j=i;j<=c*n;++j) for (k=0;k<lim;++k)
if (!((k>>p)&1)) f[min(c*n,max(j,i+l[p]*n))][k|(1<<p)]+=f[j][k];
}
ans+=f[c*n][lim-1]; ++cnt;
} while (next_permutation(l,l+n-1));
return printf("%.15lf",1.0*ans/(pow(c,n-1)*cnt)),0;
}
Postscript
我太菜了建议回炉重造（回炉失败.jpg)