赛时：\(70+50+0+20=140\) \(pts\)
\(A\) \(ball\)
首先最朴素的思路肯定是暴力，\(70\) \(pts\) 拿下。
代码实现
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e7 + 5;
ll n, m;
ll a[N];
int main(){
cin >> n >> m;
for (ll i = 1; i <= n; i++)
a[i] = m;
for (ll i = 1; i <= n; i++){
ll l = a[i] / 3;
if (i == 1)
a[n] += l, a[i] = l, a[i + 1] += l;
else if (i == n)
a[1] += l, a[i] = l, a[i - 1] += l;
else
a[i - 1] += l, a[i] = l, a[i + 1] += l;
}
ll ans = a[1];
for (ll i = 1; i <= n; i++)
ans = max(ans, a[i]);
cout << ans;
return 0;
}
考虑优化。
假设每个人手中的球颜色不同。显然，每个球最多延伸 \(log_3m\) 次。换句话说， \(log\) \(m\) 个人开始，每个人手上的球的变化就是重复的了。只需要枚举前 \(log\) \(m\) 个人即可。
代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
signed main(){
cin >> n >> m;
int x = m / 3;
int val = 0;
for (int i = 2, lst = m; i <= n; i++){
int now = lst / 3 + m;
if (now == lst || i == n){
val = now;
break;
}
lst = now;
}
cout << x + (m + x) / 3 + (val + x) / 3;
return 0;
}
\(B\) \(line\)
第一个问题很好想，只要找出每个圈的四个位置的规律即可。
第二个问题的话只要多加思考就会发现，线段长度就是两个等差数列求和。
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
int q;
int ask(int x){
return x * (x + 1) / 2;
}
int calc(int x){
return ask(x / 2) + ask((x + 1) / 2);
}
signed main(){
cin>>q;
while (q--){
int op;
cin >> op;
if (op == 1){
int x;
cin >> x;
if (x % 4 == 1)
cout << x / 4 + 1 << " " << -(x / 4) << "\n";
else if (x % 4 == 2)
cout << x / 4 + 1 << " " << x / 4 + 1 << "\n";
else if (x % 4 == 3)
cout << -(x / 4 + 1) << " " << x / 4 + 1 << "\n";
else
cout << -(x / 4) << " " << -(x / 4) << "\n";
}
else {
int l, r;
cin >> l >> r;
cout << calc(r) - calc(l) << "\n";
}
}
return 0;
}
\(C\) \(STL\)
思路
首先我们注意到这个 SPJ 是在诈骗。
为什么呢？
注意到 \(\texttt{int}、\texttt{vector}、\texttt{pair}\) 的合法组合事实上是一个后缀表达式，其中 \(\texttt{int}\) 为操作数，\(\texttt{vector}\) 为一元操作符， \(\texttt{pair}\) 为二元操作符。于是合法时方案唯一。
那我们如何构造一个合法方案呢？
看到后缀表达式，我们考虑用一个栈来记录信息。栈中每个元素表示一个区间 \([L,R]\)，表示区间 \([L,R]\) 是一个合法的后缀表达式。每次从右往左扫，遇到 \(\texttt{int}\) 直接将 \([i,i]\) 入栈；遇到 \(\texttt{vector}\) 将栈顶的弹出并放入 \([i,R]\)，在 \(i,i+1\) 之间放入一个 <，再在 \(R,R+1\) 之间放入一个 >；遇到 \(\texttt{pair}\) 将栈顶的 \([i+1,R_1][R_1,R_2]\) 弹出并放入 \([i,R_2]\)，在 \(i,i+1\) 之间放入一个 <，在 \([R_1,R_1+1]\) 之间放入一个 ,，最后在 \([R_2,R_2+1]\) 之间放入一个 > 即可。
以上任何一步需要弹栈时栈空或最终栈中元素个数不为 \(1\) 时无解。
那要是我们不需要构造方案呢？
现在依次考虑上述无解的两个条件。
- 最终栈中元素个数：注意到每遇到一个 \(\texttt{int}\)，栈中元素个数 \(+1\) ；每遇到一个 \(\texttt{vector}\)，栈中元素个数不变；每遇到一个 \(\texttt{pair}\)，栈中元素个数 \(-1\)。
于是我们预处理一个每个位置对栈中元素个数贡献的前缀和 \(sum\)，每次判断 \(sum_r-sum_{l-1}\) 是否为 \(1\) 即可。
- 弹栈时栈不空：对于所有 \(\texttt{vector}\) 出现的位置，我们需要后缀和 \(\ge 1\)；对于所有 \(\texttt{pair}\) 出现的位置，我们需要后缀和 \(\ge 2\)。
当然，我们可以运用 ST 表等 RMQ 算法求出区间后缀和最小值，但是超纲了。
对于 \(\texttt{vector}\) 的条件，我们需要知道 \([l-1,r-1]\) 中的 \(sum_i\) 中是否有 \(\ge sum_r\) 者——即 \(<r\) 的第一个
满足 $ >sum_r$ 的位置是否不存在或 \(<l-1\)；对于 \(\texttt{pair}\) 的条件，我们需要知道 \([l-1,r-1]\) 中的 \(sum_i\)
中是否有 $ >sum_r$ 者——即 \(<r\) 的第一个满足 $ >sum_r$ 的位置是否不存在或 \(<l-1\)。
分别排序后离线链表即可。时间复杂度为 \(O(n \log n + m)\)。
代码实现
#include<bits/stdc++.h>
using namespace std;
int n,m,c[1000005],pre[1000005],Log[1000005],st[22][1000005],l,r,op;char s[15];
struct Link
{
int pre,nxt;char c;
}a[10000005];
int query(int l,int r)
{
if(l>r)return 0x3f3f3f3f;
int k=Log[r-l+1];
return min(st[k][l],st[k][r-(1<<k)+1]);
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s;
if(s[0]=='i')c[i]=1;
else if(s[0]=='v')c[i]=2;
else c[i]=3;
}
for(int i=1;i<=n;i++)pre[i]=pre[i-1]+(c[i]==1?-1:(c[i]==2?0:1));
for(int i=1;i<=n;i++)st[0][i]=pre[i];
for(int i=1;(1<<i)<=n;i++)
{
for(int j=1;j+(1<<i)-1<=n;j++)st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
for(int i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
while(m--)
{
cin>>l>>r>>op;
if(pre[r]-pre[l-1]!=-1||query(l,r-1)-pre[l-1]<=-1)cout<<"No\n";
else
{
cout<<"Yes\n";
if(op==1)
{
stack<pair<int,int> >st;
int tot=0;
for(int i=r;i>=l;i--)
{
if(c[i]==1)
{
a[++tot].c='i';a[++tot].c='n';a[++tot].c='t';
for(int j=0;j<3;j++)a[tot-j].pre=tot-j-1,a[tot-j].nxt=tot-j+1;
if(st.size())a[tot].nxt=st.top().first;
else a[tot].nxt=0;
a[tot-2].pre=0;
st.push(make_pair(tot-2,tot));
}
else if(c[i]==2)
{
int l=st.top().first,r=st.top().second;st.pop();
a[++tot].c='v';a[++tot].c='e';a[++tot].c='c';
a[++tot].c='t';a[++tot].c='o';a[++tot].c='r';a[++tot].c='<';
for(int j=0;j<7;j++)a[tot-j].pre=tot-j-1,a[tot-j].nxt=tot-j+1;
a[tot-6].pre=0;a[tot].nxt=l;a[l].pre=tot;
a[++tot].c='>';
a[tot].pre=r;a[tot].nxt=a[r].nxt;a[r].nxt=tot;
st.push(make_pair(tot-7,tot));
}
else
{
int pl=st.top().first,pr=st.top().second;st.pop();
int ql=st.top().first,qr=st.top().second;st.pop();
a[++tot].c='p';a[++tot].c='a';a[++tot].c='i';a[++tot].c='r';a[++tot].c='<';
for(int j=0;j<5;j++)a[tot-j].pre=tot-j-1,a[tot-j].nxt=tot-j+1;
a[tot-4].pre=0;a[tot].nxt=pl;a[pl].pre=tot;
a[++tot].c=',';
a[tot].pre=pr;a[tot].nxt=ql;a[pr].nxt=tot;a[ql].pre=tot;
a[++tot].c='>';
a[tot].pre=qr;a[tot].nxt=a[qr].nxt;a[qr].nxt=tot;
st.push(make_pair(tot-6,tot));
}
}
for(int i=st.top().first;i;i=a[i].nxt)cout<<a[i].c;
for(int i=1;i<=tot;i++)a[i].pre=a[i].nxt=a[i].c=0;
cout<<'\n';
}
}
}
return 0;
}
\(D\) \(round\)
需要注意，被染黑和被选中是两个不同的概念。被选了，之后就不能选中；被染黑了，之后可能还会被选中。因此，如果试图用递推方程进行转移，可能需要额外的状态（而不是简单的用 \(f_i\) 表示两端为黑色的期望染黑步数）。
首先，由选择的等概率，将问题转化为：等概率随机地给出一个 \(1\) 到 \(n\) 的排列，依次按照数字染黑对应的球和两边的球，问第一次全部染黑的期望步数。这样，只需要对于每个正整数 \(k\)，算出有 \(a_i\) 个排列恰好步数为 \(k\) ，那么答案就是 \(\sum^n_{k=1}k \cdot \frac{a_i}{n!}\)。
其次，由于第一步的作用总是断环为链，因此可以直接考虑：只有两端为黑色的链的期望染黑步数即可，最后只需要答案加一。以下讨论都是基于这种情况的。
对于固定的正整数 \(k\)，我们尝试计算步数小于等于 \(k\) 的方案数。也就是说，前缀长度为 \(k\) 的染黑了序列的排列有多少个。如果不考虑顺序，把这 \(k\) 个数字对应上去，那么第一个数字，它可能出现的位置是 \(1\)（在染黑的端点上）、\(2\)（在染黑的端点的右侧）或 \(3\)，第二个数字相对于第一个数字只能往右移动 \(1\)、\(2\) 或 \(3\)，第三个数字也是，直到第 \(k\) 个数字。同时，第 \(k\) 个数字还需要满足：在第 \(n\)、\(n-1\) 、$$n-2 这三个位置上，意即需要完全染黑所有数字。
于是，可以枚举第 \(k\) 个数字在哪个位置上，就确定了总共要位移的距离 \(len\) ，再枚举相对左边位移了\(1、
2、3\)个位置的数分别有 \(a、b 、c\) 个，需要满足 \(a+2b+3c=len\)，那么贡献就是\footnote{此处细节会
根据你的具体实现而有所不同。}：\(C^a_k \cdot C^b_{k-a} \cdot k\).
其中，最后 阶乘表示恢复顺序的贡献。由于枚举 \(a\) 就能确定 \(b\) 和 \(c\) ，时间复杂度是 \(O(n^2)\)
代码实现
#include<bits/stdc++.h>
using namespace std;
int dp[5005][5005][2],sum[5005][2],ans,n,fac[5005],inv[5005];
const int mod=998244353;
void Add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
int qpow(int x,int y)
{
int res=1;
while(y)
{
if(y&1)res=1ll*res*x%mod;
x=1ll*x*x%mod;y/=2;
}
return res;
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin>>n;//上一个选择在 i 选 j 个仍然搞不定的方案数 0/1 表示是否已经有跨度超过3的位置
fac[0]=inv[0]=1;
for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=qpow(fac[n],mod-2);
for(int i=n-1;i>=1;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
dp[1][1][0]=1;sum[1][0]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
for(int k=max(1,i-3);k<i;k++)Add(dp[i][j][0],dp[k][j-1][0]);
Add(dp[i][j][1],sum[j-1][1]);Add(dp[i][j][1],sum[j-1][0]);
for(int k=max(1,i-3);k<i;k++)Add(dp[i][j][1],mod-dp[k][j-1][0]);
}
for(int j=1;j<=i;j++)Add(sum[j][0],dp[i][j][0]),Add(sum[j][1],dp[i][j][1]);
}
Add(ans,fac[n]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(n+1-i>3)Add(ans,1ll*dp[i][j][0]*fac[n-j]%mod*fac[j-1]%mod*n%mod);
Add(ans,1ll*dp[i][j][1]*fac[n-j]%mod*fac[j-1]%mod*n%mod);
}
}
cout<<1ll*ans*inv[n]%mod;
return 0;
}