模拟赛
水题场。
T1 colorful
签。
感觉题挺好，正难则反，找出四角都相同的。
在这两排有 6 个四角相同的矩形
对于两排来说，我们只需要记录相同的列的个数，然后能直接算出个数。
发现桶排每次清空复杂度太高，考虑每次只开一排的桶，只会有 \(n\) 个。
code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 405;
int n,m,tot,c[N][N],cnt[N];
unordered_map<int,int> mp;
LL sum,fac[N];
int main()
{
freopen("colorful.in","r",stdin);
freopen("colorful.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum+=i*j;
fac[0]=0; fac[1]=1;
for(int i=2;i<=m;i++) fac[i]=fac[i-1]+i;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&c[i][j]);
for(int i=1;i<=n;i++)
{
tot=0; mp.clear();
for(int j=1;j<=m;j++) {if(!mp[c[i][j]]) mp[c[i][j]]=++tot;}
for(int k=i;k<=n;k++)
{
for(int j=1;j<=m;j++)
{
if(c[i][j]==c[k][j]) cnt[mp[c[i][j]]]++;
}
for(int j=1;j<=tot;j++) sum-=fac[cnt[j]],cnt[j]=0;
}
}
printf("%lld\n",sum);
return 0;
}
T2 travel
签没签。
区间修改，求和。
赛时糊了一个珂朵莉，但是没有颜色段均摊的珂朵莉是假的！
（想不到差分），区间修改直接想差分，最后遍历一遍统计和就行了。
有一点细节。
点code
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define P pair<int,int>
const int N = 2e6+5,mod = 1e9+7;
int n,m,S,T,tot;
P a[N];
LL ans=1;
inline LL qpow(LL a,int b)
{
LL res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod; b>>=1;
}
return res;
}
int main()
{
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&S,&T);
for(int i=1;i<=m;i++)
{
int c,x,y; scanf("%d%d%d",&c,&x,&y);
a[++tot]={x,-1}; if(y<T) a[++tot]={y+1,1};
}
sort(a+1,a+1+tot); a[0].first=S; a[++tot].first=T+1;
for(int i=0;i<tot;i++)
{
n+=a[i].second;
if(a[i+1].first>a[i].first)
ans=(ans*qpow(n,a[i+1].first-a[i].first))%mod;
}
printf("%lld\n",ans);
return 0;
}
T3 线段树
签。
既然断点任选了，那和树也没关系了，就是区间问题，dp。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int n,q;
long long s[N][N],f[N][N];
int main()
{
freopen("segment.in","r",stdin);
freopen("segment.out","w",stdout);
scanf("%d%d",&n,&q);
memset(f,0x3f,sizeof(f));
for(int i=1;i<=q;i++)
{
int x,y; scanf("%d%d",&x,&y);
s[x][y]++;
}
for(int k=1;k<=n;k++)
for(int i=n;i>=1;i--) s[k][i]+=s[k][i+1];
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++) s[i][k]+=s[i-1][k];
for(int i=1;i<=n;i++) f[i][i]=s[i][i];
for(int len=2;len<=n;len++)
{
for(int l=1,r=len+l-1;r<=n;l++,r++)
{
for(int k=l;k<r;k++)
{
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]-s[l][r]);
}
}
}
printf("%lld\n",f[1][n]);
return 0;
}
T4 薛定谔的猫和巴甫洛夫的狗
trick，统计方案数可以用这种情况出现的概率乘总方案数。
计算概率明显比方案要好求，而且发现是基环树。
找到 \(n\) 所在环编号最小的点作为开始点，然后 dp 向后推是否有猫的概率。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3+5,mod = 1e9+7;
#define LL long long
int T,n;
int fa[N],bl[N],tot,b[N];
char s[N];
inline int find(int x) {return x==fa[x]?(x):(fa[x]=find(fa[x]));}
unordered_map<int,int> mp;
LL inv,p[N],ans;
void init()
{
mp.clear(); tot=0; ans=0;
for(int i=1;i<=n;i++) fa[i]=i;
}
inline LL qpow(LL a,int b)
{
LL res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod; b>>=1;
}
return res;
}
int main()
{
freopen("experiment.in","r",stdin);
freopen("experiment.out","w",stdout);
inv=qpow(2,mod-2);
scanf("%d",&T);
while(T--)
{
scanf("%d%s",&n,s+1); init();
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
int fx=find(b[i]); fa[find(i)]=fx;
}
for(int i=1;i<=n;i++)
{
int fx=find(i); if(!mp[fx]) mp[fx]=++tot;
bl[i]=mp[fx]; fa[i]=i;
}
int fl;
for(int i=n;i>=1;i--)
{
if(bl[i]==bl[n])
{
if(find(i)==find(b[i])) fl=i;
fa[find(i)]=find(b[i]);
}
}
for(int l=0;l<2;l++)
for(int r=0;r<2;r++)
{
for(int i=1;i<=n;i++)
{
if(s[i]=='?') p[i]=inv;
else if(s[i]=='C') p[i]=1;
else if(s[i]=='.') p[i]=0;
}
LL q=0;
for(int i=1;i<=n;i++)
{
if(i==fl)
{
q=(l?(p[i]):(mod+1-p[i]))*(r?(p[b[i]]):(mod+1-p[b[i]]))%mod;
p[i]=l; p[b[i]]=r;
}
LL x=p[i],y=p[b[i]];
p[i]=x*y%mod;
p[b[i]]=(y+x*(1+mod-y)%mod)%mod;
}
ans=(ans+p[n]*q%mod)%mod;
}
int cnt=count(s+1,s+1+n,'?');
ans=(ans*qpow(2,cnt)%mod);
printf("%lld\n",ans);
}
return 0;
}