赛时在 \(T2\) 浪费时间太多，导致 \(T4\) 暴力没时间想了，总是想把 \(T2\) 这种题当大型分讨来做
A. 花间叔祖
观察性质可以发现，答案要么是1，要么是2，把是1的情况找出来剩下的就是2。
考虑什么时候是1，如果一个数列模上一个数结果相同，那么他们的差一定是这个模数的整数倍，直接求差的 \(gcd\) 即可
点击查看代码
#include<bits/stdc++.h>
const int maxn=2e5+10;
using namespace std;
int n,a[maxn],mod,flag;
int temp;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=2;i<=n;i++)
{
temp=__gcd(a[i]-a[i-1],temp);
if(!mod)
{
if(temp==1)
{
flag=1;
break;
}
mod=temp;
}
else
{
// cout<<mod<<" "<<temp<<endl;
if(__gcd(mod,temp)==1)
{
flag=1;
break;
}
else
{
mod=__gcd(mod,temp);
}
}
}
if(flag)
{
cout<<2;
}
else
{
cout<<1;
}
return 0;
}
/*
10
3785 5176 10740 7744 3999 3143 9028 2822 4748 6888
*/
B. 合并r
方案数很多，考虑\(DP\)，这里我们把题目看为，先选 \(k\) 个1，再由这 \(k\) 个1分裂为 \(n\) 个数的方案数
设 $ f_i,_j $ 表示为当前由 \(i\) 个数组成的和为 \(j\) 的方案数，每个值可以直接分为原来的\(1/2\)，所以是由 \(j*2\) 个转移的
而在 \(j-j*2\) 的值都可以由这 \(i\) 个数替换几个 \(j\) 成 \(j*2\)组成，这些方案是在 \(j*2\) 的方案中存在的（\(j*2\)也是由这些
值替换而来），所以 \(f_i,_j\) = $ f_{i-1,_j-1} $ + \(f_{i,_j * 2}\)
点击查看代码
#include<bits/stdc++.h>
#define de double
const int mod=998244353;
const int maxn=5e3+10;
using namespace std;
int n,k,f[maxn][maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k;
f[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=i;j>=1;j--)
{
f[i][j]=f[i-1][j-1];
if(j*2<=i)f[i][j]+=f[i][j*2];
f[i][j]%=mod;
}
}
cout<<f[n][k];
return 0;
}
C. 回收波特
[ARC149D] Simultaneous Sugoroku
思路很巧，注意到值域很小，所以对值域操作，每次以坐标分为两部分，让小的一部分向多的一部分连边，他们最后的位置是
相反的，每次舍掉小的一部分，最后没有指令了，但值域还有，那值域中的点即为不能到原点，细节看代码
点击查看代码
#include<bits/stdc++.h>
const int maxn=2e6+10;
using namespace std;
int m,n,x[maxn],to[maxn],ans[maxn],lst[maxn],d;
void get(int x)
{
if(ans[x]||lst[x])return ;
get(to[x]);
ans[x]=ans[to[x]],lst[x]=-lst[to[x]];
}
int main()
{
// freopen("bot_ex3.in","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>x[i];
int p=0,l=1,r=1e6;
for(int i=1;i<=m;i++)
{
cin>>d;
if(p<l)p+=d;
else if(p>r)p-=d;
if(p<l||p>r)continue;
ans[p]=i;
if(p-l<r-p)
{
for(int j=l;j<p;j++)to[j]=2*p-j;
l=p+1;
}
else
{
for(int j=r;j>p;j--)to[j]=2*p-j;
r=p-1;
}
}
for(int i=l;i<=r;i++) lst[i]=i-p;
for(int i=1;i<=n;i++)
{
get(x[i]);
if(ans[x[i]])cout<<"Yes "<<ans[x[i]]<<'\n';
else cout<<"No "<<lst[x[i]]<<'\n';
}
return 0;
}
最后处理不能到的坐标是 \(i-p\) ，首先这个区间到最后了（没有连边），那么每次 \(p\) 就是向区间方向移动（自己手模一下），
要么是一直不到 \(l\)，最后一定大于0，直接减，要么就是由不到 \(l\) 到超过 \(r\) ，再一直向左，这样最后坐标是小于0的，还是
直接减就行。
D. 斗篷
对于每个点维护 \(L_{x, y}\) 表示这个点向左上延伸的最大距离，维护 \(R_{x, y}\) 表示这个点向右上延伸的最大距离；维护 \(len\) 表示这个
点向左延伸到的位置。枚举每个点 \((x, y)\) 作为三角形的右下角，枚举 \((x, t)\) 作为三角形的左下角，显然
\(t\in [\max(pre_{x, y}, y - L_{x, y}), y-1]\) ，如果 \(t\) 满足 \(R_{x, t}\ge y-t\) ，则对答案产生 \(1\) 的贡献。
考虑优化：简单移项有 \(R_{x,t}+t\ge y\) 。
令 \(L=\max(pre_{x, y}, y - L_{x, y}), R=y-1\) ，即统计 \([L, R]\) 区间内满足 \(R_{x,t}+t\ge y\) 的 \(t\) 的个数。
单点修改，区间查询，用树状数组维护
点击查看代码
#include<bits/stdc++.h>
const int maxn=6010;
using namespace std;
int r,c;
long long ans;
char s[maxn][maxn<<1];
int L[2][maxn<<1],R[2][maxn<<1];
int C[maxn<<1];
struct lsx
{
inline int lowbit(int x){return x&-x;}
inline void add(int x,int y)
{
while(x<=c)
{
C[x]+=y;
x+=lowbit(x);
}
}
inline int query(int x)
{
int temp=0;
while(x)
{
temp+=C[x];
x-=lowbit(x);
}
return temp;
}
}e;
vector<int>q[maxn<<1];
void solve()
{
int now=1,pre=0;
memset(L,0,sizeof L),memset(R,0,sizeof R);
for(int t=3;t<=r;t+=2,swap(now,pre))
{
memset(C,0,sizeof C),memset(L[now],0,sizeof L[now]),memset(R[now],0,sizeof R[now]);
int len=0;
for(int i=1;i<=c;i++)
if(s[t][i]=='x')
{
if(i>2&&(s[t-1][i-1]==92||s[t-1][i-1]==47))L[now][i]=L[pre][i-2]+1;
else L[now][i]=0;
if(i<c&&(s[t-1][i+1]==92||s[t-1][i+1]==47))R[now][i]=R[pre][i+2]+1;
else R[now][i]=0;
if(s[t][i-1]=='-')len++;
else len=0;
int temp=min(len,L[now][i]);
if(temp) ans+=e.query(i)-e.query(i-temp*4-1);
for(int j=0;j<q[i].size();j++) e.add(q[i][j],-1);
q[i].clear();
if(R[now][i])
{
e.add(i,1);
if(i+R[now][i]*4<=c)q[i+R[now][i]*4].push_back(i);
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>r>>c;
r=r*2-1,c=c*2;
string tmp;
getline(cin,tmp);
for(int i=1;i<=r;i++)
{
getline(cin,tmp);
for(int j=1;j<=c;j++)s[i][j]=tmp[j-1];
}
solve();
reverse(s+1,s+r+1);
solve();
cout<<ans;
return 0;
}