正常偏下发挥吧。
Rank
A. 黑客
签到题。
题目中的关键点是只有 \(x\) 和 \(y\) 的和在区间 \(\left[0,999\right]\) 内才合法，因此我们只枚举和在这个范围内的两个值，寻找约分前的值即可，复杂度为 \(\mathcal{O(999^2)}\)。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=1e6+5;
const int mod=1e9+7;
ll A,B,C,D,ans;
namespace Wisadel
{
short main()
{
// freopen(".in","r",stdin),freopen(".out","w",stdout);
// // cin.tie(0),cout.tie(0);
// ios::sync_with_stdio(0);
A=qr,B=qr,C=qr,D=qr;
fo(i,1,999)
fo(j,1,999-i)
if(__gcd(i,j)==1)
{
ll l1=ceil(1.0*A/i),r1=B/i,l2=ceil(1.0*C/j),r2=D/j;
ll t=min(r1,r2)-max(l1,l2)+1;
if(t>0) ans=(ans+t%mod*(i+j)%mod+mod)%mod;
}
printf("%lld\n",ans);
return Ratio;
}
}
int main(){return Wisadel::main();}
B. 密码技术
原[ARC107C] Shuffle Permutation
也是很水的题，赛时的想法很接近正解了，但就差一点。
若第 \(i\) 行和第 \(j\) 行均可与第 \(k\) 行交换，那么第 \(i\) 行也可与第 \(j\) 行交换。知道了这一点，大概就能猜出来这单独的一组的方案数为组容量的阶乘。
还有一个性质就是，行与行之间的交换不会影响列之间的交换，所以依据乘法原理，答案为二者相乘。
因此我们行列分开找，每次利用并查集找到分组情况，然后得阶乘的积即可。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=1e5+5;
const int mod=998244353;
int n,k;
int a[55][55],fx[55],siz[55];
ll ans=1,jc[N];
namespace Wisadel
{
int Wfind(int x)
{
if(x!=fx[x]) return fx[x]=Wfind(fx[x]);
return x;
}
short main()
{
// freopen(".in","r",stdin),freopen(".out","w",stdout);
n=qr,k=qr;
memset(a,0x7f,sizeof a);
fo(i,1,n) fo(j,1,n) a[i][j]=qr;
jc[1]=1;
fo(i,2,n) jc[i]=jc[i-1]*i%mod;
fo(i,1,n) fx[i]=i;
fo(i,1,n)
fo(j,i+1,n)
{
bool can=1;
fo(o,1,n) if(a[i][o]+a[j][o]>k) {can=0;break;}
if(!can) continue;
int _1=Wfind(i),_2=Wfind(j);
fx[_1]=_2;
}
fo(i,1,n) siz[Wfind(i)]++;
fo(i,1,n) if(siz[i]) ans=ans*jc[siz[i]]%mod;
memset(siz,0,sizeof siz);
fo(i,1,n) fx[i]=i;
fo(i,1,n)
fo(j,i+1,n)
{
bool can=1;
fo(o,1,n) if(a[o][i]+a[o][j]>k) {can=0;break;}
if(!can) continue;
int _1=Wfind(i),_2=Wfind(j);
fx[_1]=_2;
}
fo(i,1,n) siz[Wfind(i)]++;
fo(i,1,n) if(siz[i]) ans=ans*jc[siz[i]]%mod;
printf("%lld\n",ans);
return Ratio;
}
}
int main(){return Wisadel::main();}
C. 修水管
题面爆改计划，膜拜 HDK 光速找到原题。
期望的题，挺恶心的，挂一篇我觉得很好的题解润了。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=255;
const int mod=998244353;
int n,r,d[N];
double p[N],fp[N],pf[N][N],f[N][N];
namespace Wisadel
{
short main()
{
// freopen(".in","r",stdin),freopen(".out","w",stdout);
int T=qr;
while(T--)
{
n=qr,r=qr;
fo(i,0,n-1) cin>>p[i],d[i]=qr;
fo(i,0,n-1)
{
pf[i][0]=1;
fo(j,1,r) pf[i][j]=pf[i][j-1]*(1-p[i]);
}
memset(f,0,sizeof f),memset(fp,0,sizeof fp);
f[0][0]=pf[0][r];
f[0][1]=fp[0]=1-f[0][0];
fo(i,1,n-1) fo(j,0,r)
{
fp[i]+=f[i-1][j]*(1-pf[i][r-j]);
f[i][j]+=f[i-1][j]*pf[i][r-j];
if(j) f[i][j]+=f[i-1][j-1]*(1-pf[i][r-j+1]);
}
double ans=0;
fo(i,0,n-1) ans+=d[i]*fp[i];
printf("%.10lf\n",ans);
}
return Ratio;
}
}
int main(){return Wisadel::main();}
D. 货物搬运
一眼平衡树，但赛时看 T3 看麻了只打了暴力。
果然最后还是分块+双端队列碾过去了。
没啥好说的，分块就是暴力，一看就懂。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=1e5+5;
const int mod=998244353;
int n,q,m,sq,ans;
int c[355][N];
deque<int> dq[N];
namespace Wisadel
{
void Wget(int &x){x=(x+ans-1)%n+1;}
short main()
{
// freopen(".in","r",stdin),freopen(".out","w",stdout);
n=qr;sq=sqrt(n);m=n/sq+1;int x;
fo(i,0,n-1) x=qr,dq[i/sq].push_back(x),c[i/sq][x]++;
q=qr;
while(q--)
{
int op=qr,l=qr,r=qr;
Wget(l),Wget(r);
if(l>r) swap(l,r);
l--;
int lbl=l/sq,rbl=r/sq;
if(op==1)
{
if(lbl==rbl)
{
r=r%sq-1,x=dq[rbl][r];
dq[rbl].erase(dq[rbl].begin()+r);
dq[lbl].insert(dq[lbl].begin()+l%sq,x);
}
else
{
for(int i=lbl;i<rbl;)
{
x=dq[i].back(),dq[i].pop_back(),c[i][x]--,i++;
dq[i].push_front(x),c[i][x]++;
}
r%=sq,x=dq[rbl][r];
dq[rbl].erase(dq[rbl].begin()+r),c[rbl][x]--;
dq[lbl].insert(dq[lbl].begin()+l%sq,x),c[lbl][x]++;
}
}
else
{
int k=qr;Wget(k);ans=0;
if(lbl==rbl)
fo(i,l%sq,r%sq-1) ans+=dq[lbl][i]==k;
else
{
fo(i,lbl+1,rbl-1) ans+=c[i][k];
fo(i,l%sq,dq[lbl].size()-1) ans+=dq[lbl][i]==k;
fo(i,0,r%sq-1) ans+=dq[rbl][i]==k;
}
printf("%d\n",ans);
}
}
return Ratio;
}
}
int main(){return Wisadel::main();}
末
计数题+期望题，最ex的数学知识全弄到一场了。
发挥感觉一般，还没到挂很多分的地步，得加把劲。
点击查看HDK
完结撒花~
标签：ch,int,qr,12,lx,ans,CSP,模拟,fo From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18335202