A - Zero-Sum Ranges
令 \(s_n=\sum\limits_{i=1}^n a_i\),相当于找满足 \(l\le r,s_r-s_{l-1}\) 的点对 \((l,r)\) 的个数,直接搞就完事了。
#include<iostream>
#include<cstdio>
#include<unordered_map>
using namespace std;
const int N=200005;
int n;
int a[N];
long long sum[N];
unordered_map<long long,int>pre;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i];
long long ans=0;
pre[0]++;
for(int i=1;i<=n;i++)
ans+=pre[sum[i]],pre[sum[i]]++;
printf("%lld",ans);
return 0;
}
B - Find Symmetries
对于一条斜率为 \(-1\) 的斜线上的点是等价的,枚举这条直线,暴力判断是否合法即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=305;
int n;
char s[N+N][N+N];
int solve(int sx,int sy)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(s[sx+i-1][sy+j-1]!=s[sx+j-1][sy+i-1]) return 0;
if(sx==1) return n-sy+1;
else return n-sx+1;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
s[i+n][j]=s[i][j+n]=s[i+n][j+n]=s[i][j];
int ans=0;
for(int i=1;i<=n;i++)
{
int j=1;
ans+=solve(i,j);
}
for(int j=2;j<=n;j++)
{
int i=1;
ans+=solve(i,j);
}
printf("%d",ans);
return 0;
}
C - Painting Machines
考虑计算恰好在第 \(i\) 步停止的方案数。
可以发现,最后两个机器之间间隔为 \(1\) 或 \(0\)。总共 \(i\) 个机器,头尾机器的位置已经确定,总共 \(i-1\) 个空,放入 \(n-1-i\) 个空,方案数为 \(C_{i-1}^{n-i-1}\)。
\(k\) 个机器可以随便排列,后面 \(n-1-k\) 个机器也可以随便排列,所以还要乘上 \(k!(n-1-k)!\)。
但是你发现这有可能将 \(1\sim i-1\) 步停止的方案也算进去,减掉就好了。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000005;
const int MOD=1000000007;
int n;
int ksm(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=1LL*res*a%MOD;
a=1LL*a*a%MOD,b>>=1;
}
return res;
}
int fac[N],inv[N];
void init(int n=1000000)
{
fac[0]=1;
for(int i=1;i<=n;i++)
fac[i]=1LL*fac[i-1]*i%MOD;
inv[n]=ksm(fac[n],MOD-2);
for(int i=n;i>=1;i--)
inv[i-1]=1LL*inv[i]*i%MOD;
return;
}
int C(int n,int m)
{
if(m>n) return 0;
else return 1LL*fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int f[N];
int main()
{
init();
scanf("%d",&n);
for(int i=1;i<=n-1;i++)
f[i]=1LL*C(i-1,n-i-1)*fac[i]%MOD*fac[n-i-1]%MOD;
for(int i=n-1;i>=1;i--)
f[i]=(1LL*f[i]-f[i-1]+MOD)%MOD;
int ans=0;
for(int i=1;i<=n-1;i++)
ans=(ans+1LL*f[i]*i)%MOD;
printf("%d",ans);
return 0;
}
D - Go Home
最后肯定是到 \(1\) 或 \(n\),肯定是先走到人数多的那边,少的一方肯定是要帮着多的一方尽快到达家然后他们再回家。
我们可以看做是少的一方的人变成了多的一方的人,就可以变成一个子问题,递归解决即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n,s;
int x[N];
long long p[N];
long long solve(int l,int r,int t)
{
if(s<=x[l]) return (long long)x[r]-s+abs((long long)x[t]-x[r]);
if(s>=x[r]) return (long long)s-x[l]+abs((long long)x[t]-x[l]);
if(p[l]>=p[r])
{
p[l]+=p[r];
return solve(l,r-1,l)+(t==r?x[r]-x[l]:0);
}
else
{
p[r]+=p[l];
return solve(l+1,r,r)+(t==l?x[r]-x[l]:0);
}
}
int main()
{
scanf("%d%d",&n,&s);
for(int i=1;i<=n;i++)
scanf("%d%lld",&x[i],&p[i]);
if(s<=x[1]) printf("%lld",(long long)x[n]-s);
else if(s>=x[n]) printf("%lld",(long long)s-x[1]);
else if(p[1]<p[n]) printf("%lld",solve(1,n,1));
else printf("%lld",solve(1,n,n));
return 0;
}
E - Inversions
考虑按照 \(a_i\) 从小到大填数,令 \(b_i\) 表示 \(a_i\) 的排名,那么总方案数为
\[\prod\limits_{i=1}^n(a_i-b_i+1) \]记为 \(S\)。
考虑一个点对 \((i,j)\) 的贡献,令 \(c_i\) 表示 \(a_i\) 从小到大排序后第 \(i\) 个位置原来在哪里,则 \((i,j)\) 的贡献为:
如果 \(j\le i,a_j\le a_i\),这和将 \(a_i\) 改为 \(a_j\) 的方案数是相同的,那么就可以用 \(a_i=a_j\) 的方案数除以 \(2\) 来计算贡献:
\[\frac{S}{2}\cdot\frac{a_j-b_j}{a_i-b_i+1}\cdot\left(\prod\limits_{k=b_j+1}^{b_i-1}\frac{a_{c_k}-k}{a_{c_k}-k+1}\right) \]如果 \(j\gt i,a_j\le a_i\),我们可以求 \(j\le i,a_j\le a_i\) 时的方案数,用总方案数减去它:
\[S-\frac{S}{2}\cdot\frac{a_j-b_j}{a_i-b_i+1}\cdot\left(\prod\limits_{k=b_j+1}^{b_i-1}\frac{a_{c_k}-k}{a_{c_k}-k+1}\right) \]这个东西 \(a_j-b_j\) 和 \(a_{c_k}-k\) 可能为 \(0\),直接前缀和可能不太好搞。
考虑维护两个式子中相同的那个部分,按照 \(a_i\) 从小到大扫,每次相当于全局乘上 \(\frac{a_i-b_i}{a_i-b_i+1}\),将 \(i\) 位置修改为 \(a_i-b_i\),然后区间求和,线段树维护即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<unordered_map>
#include<algorithm>
using namespace std;
const int N=200005;
const int MOD=1000000007;
int n;
int a[N],b[N],c[N];
int ksm(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=1LL*res*a%MOD;
a=1LL*a*a%MOD,b>>=1;
}
return res;
}
int getinv(int x)
{
return ksm(x,MOD-2);
}
struct BIT
{
int C[N];
BIT()
{
memset(C,0,sizeof(C));
return;
}
int lowbit(int x)
{
return x&-x;
}
void add(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i))
C[i]=(C[i]+y)%MOD;
return;
}
int getsum(int x)
{
int res=0;
for(int i=x;i>0;i-=lowbit(i))
res=(res+C[i])%MOD;
return res;
}
int query(int l,int r)
{
return (getsum(r)-getsum(l-1)+MOD)%MOD;
}
}TC;
struct Segment_Tree
{
struct Node
{
int l,r;
int sum,tag;
}tree[N<<2];
void push_up(int i)
{
tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%MOD;
return;
}
void mul(int i,int v)
{
tree[i].sum=1LL*tree[i].sum*v%MOD;
tree[i].tag=1LL*tree[i].tag*v%MOD;
return;
}
void push_down(int i)
{
if(tree[i].tag==1) return;
mul(i*2,tree[i].tag);
mul(i*2+1,tree[i].tag);
tree[i].tag=1;
return;
}
void build(int i,int l,int r)
{
tree[i].l=l,tree[i].r=r;
tree[i].tag=1;
if(l==r)
{
tree[i].sum=0;
return;
}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
push_up(i);
return;
}
void modifyadd(int i,int u,int v)
{
if(tree[i].l==tree[i].r)
{
tree[i].sum=(tree[i].sum+v)%MOD;
return;
}
push_down(i);
if(u<=tree[i*2].r) modifyadd(i*2,u,v);
else modifyadd(i*2+1,u,v);
push_up(i);
return;
}
void modifymul(int i,int l,int r,int v)
{
if(l<=tree[i].l&&tree[i].r<=r) return mul(i,v);
push_down(i);
if(l<=tree[i*2].r) modifymul(i*2,l,r,v);
if(r>=tree[i*2+1].l) modifymul(i*2+1,l,r,v);
push_up(i);
return;
}
int query(int i,int l,int r)
{
if(l>r) return 0;
if(l<=tree[i].l&&tree[i].r<=r) return tree[i].sum;
push_down(i);
int res=0;
if(l<=tree[i*2].r) res=(res+query(i*2,l,r))%MOD;
if(r>=tree[i*2+1].l) res=(res+query(i*2+1,l,r))%MOD;
return res;
}
}T;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
c[i]=i;
sort(c+1,c+n+1,[=](const int &x,const int &y){return a[x]<a[y];});
for(int i=1;i<=n;i++)
b[c[i]]=i;
for(int i=1;i<=n;i++)
if(a[i]<b[i])
{
printf("0");
return 0;
}
int sum=1;
for(int i=1;i<=n;i++)
sum=1LL*sum*(a[i]-b[i]+1)%MOD;
T.build(1,1,n);
int ans=0;
int inv2=getinv(2);
for(int k=1;k<=n;k++)
{
ans=(ans+1LL*T.query(1,1,c[k]-1)*getinv(a[c[k]]-b[c[k]]+1)%MOD*sum%MOD*inv2)%MOD;
ans=(ans+1LL*TC.query(c[k]+1,n)*sum)%MOD;
ans=(ans-1LL*T.query(1,c[k]+1,n)*getinv(a[c[k]]-b[c[k]]+1)%MOD*sum%MOD*inv2%MOD+MOD)%MOD;
TC.add(c[k],1);
T.modifymul(1,1,n,1LL*(a[c[k]]-b[c[k]])*getinv(a[c[k]]-b[c[k]]+1)%MOD);
T.modifyadd(1,c[k],a[c[k]]-b[c[k]]);
}
printf("%d",ans);
return 0;
}
F - 01 on Tree
把一个节点看作一个遍历的序列,初始时为 \(v_i\),每次将一个点合并到它的父亲上,表示选了父亲之后马上就选它,一直这样操作直到剩下根节点。可以发现这样操作方案可以和所有遍历方案一一对应。
考虑合并两个节点,不妨设第一个节点有 \(a_1\) 个 \(1\),\(b_1\) 个 \(1\),第二个节点有 \(a_1\) 个 \(1\),\(b_1\) 个 \(0\)。第一个放在第二个前的贡献为 \(b_1a_2\);反之贡献为 \(b_2a_1\)。
假如第一个放在第二个前面更优,即 \(b_1a_2\le b_2a_1\Leftrightarrow \frac{a_1}{b_1}\ge \frac{a_2}{b_2}\)。
每次找到最大的 \(\frac{a_i}{b_i}\),合并到父亲,用 std::set
维护一下就好了。
#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
const int N=200005;
int n;
int fa[N];
int v[N];
struct Node
{
int a,b;
bool operator < (const Node &rhs)const
{
return (long long)a*rhs.b>(long long)b*rhs.a;
}
}c[N];
multiset<pair<Node,int>>S;
int f[N];
int getf(int v)
{
if(v==f[v]) return v;
else return f[v]=getf(f[v]);
}
int nxt[N];
int main()
{
scanf("%d",&n);
for(int i=2;i<=n;i++)
scanf("%d",&fa[i]);
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
for(int i=1;i<=n;i++)
if(v[i]==0) c[i].a++;
else c[i].b++;
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=2;i<=n;i++)
S.insert({c[i],i});
long long ans=0;
while(!S.empty())
{
auto [p,v]=*S.begin();
S.erase(S.begin());
int u=getf(fa[v]);
f[v]=f[fa[v]];
if(u!=1) S.erase(S.find({c[u],u}));
ans+=(long long)c[u].b*c[v].a;
c[u].a+=c[v].a,c[u].b+=c[v].b;
if(u!=1) S.insert({c[u],u});
}
printf("%lld",ans);
return 0;
}
标签:AtCoder,return,Contest,int,res,long,023,include,MOD
From: https://www.cnblogs.com/zhou-jk/p/17733476.html