【AtCoder】Japanese Student Championship 2019 Qualification题解_综合

Japanese Student Championship 2019 Qualification题解

A. Takahashi Calendar

◇题目传送门◆

题目大意

定义Product Day为以 $n$ - $d$ 表示一个日期时，当 $d$ 是一个两位数且每位数字至少大于 $2$ 时， $d$ 的个位数和十位数的乘积等于 $n$ 。

给定一个 $n$ 和 $d$ ，求总共有多少个Product Day。

分析

按照题意直接枚举即可。

参考代码

#include<cstdio>
#include<algorithm>
using namespace std;int main() {
    #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint n,d;scanf("%d %d",&n,&d);int cnt=0;for(int i=1;i<=n;i++)for(int j=10;j<=d;j++) {
    int d1=j%10,d10=j/10;if(d1<2||d10<2)continue;if(d1*d10==i)cnt++;}printf("%d\n",cnt);return 0;
}

B. Kleene Inversion

◇题目传送门◆

题目大意

给定一个有 $N$ 个元素的序列 $A$ ，要求求出将序列 $A$ 复制 $K$ 次接上后的逆序对的个数模 $10^9+7$ 的值。

分析

考虑 $A$ 中的一个逆序对 $(i, j)$ 在重复 $K$ 次后的贡献。对于一个位置 $j+kN(0≤k≤K)j+kN(0\le k\le K)$ 来说，前面有 $k$ 个位置上的数 $A_i$ 比它大，所以这个逆序对的贡献就是 $1+2+3+?+K=K(K+1)21+2+3+\cdots+K=\frac{K(K+1)}{2}$ 。

但我们发现对于一个数对 $(i, j)$ ，当 $i < j$ 且 $A_i>A_j$ 时也是有贡献的，因为复制后数 $A_i$ 就跑到数 $A_j$ 后面去了，分析一下就发现这种数对的贡献就是 $1+2+3+?+(K?1)=(K?1)K21+2+3+\cdots+(K-1)=\frac{(K-1)K}{2}$ 。

实现时注意要求取模，即除以 $2$ 要变成乘上 $2$ 的逆元。

参考代码

#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;
const int Maxn=2000;
const ll Mod=1e9+7;int N,A[Maxn+5];
ll K;ll QuickPow(ll a,ll k) {
    ll ret=1;while(k) {
    if(k&1)ret=(ret*a)%Mod;a=(a*a)%Mod;k>>=1;}return ret;
}int main() {
    #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d %lld",&N,&K);for(int i=1;i<=N;i++)scanf("%d",&A[i]);ll ans=0;for(int i=1;i<=N;i++)for(int j=i+1;j<=N;j++)if(A[i]>A[j])ans++;ll ans1=0;for(int i=1;i<=N;i++)for(int j=1;j<i;j++)if(A[i]>A[j])ans1++;ll inv2=QuickPow(2,Mod-2);printf("%lld\n",(ans*K%Mod*(K+1)%Mod*inv2%Mod+ans1*K%Mod*(K-1)%Mod*inv2%Mod)%Mod);return 0;
}

C. Cell Inversion

◇题目传送门◆

题目大意

给定一个只由B和W组成的字符串，每次操作可将一段区间内的所有字符颜色全部翻转，即B变W，或者W变B。求将所有的字符全部变成W的方案数。（不同顺序也要计算）

分析

首先记一个翻转第 $l$ 到第 $r$ 块的操作是 $(l, r)$ 。

不难发现对于两个操作 $l_1,r_1),(l_2,r_2)$ ，按照 $l_1,r_2),(l_2,r_1)$ 操作的效果是相同的。这就是说，一个块的变化只取决于它是作为左端点还是右端点。

进一步分析可发现，对于一个块 $i$ ，若将它作为左端点翻转后，它只能够影响第 $i ? 1$ 块和第 $i$ 块是否同色；同理，当它作为一个右端点时，它影响了第 $i$ 块和第 $i + 1$ 块是否同色。

故考虑将所有的位置看作一个个的左右括号，则这个问题就变成求有多少种方案使得左右括号匹配。

显然第一个位置是左括号。那么我们发现，当两个块相同时，它们就不是相同的括号；当两个块不同时，它们是不同的括号。最后将它们匹配即可。

注意检查是否恰好各有 $N$ 个左括号或者右括号。

参考代码

#include<stack>
#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;
const int Maxn=1e5;
const ll Mod=1e9+7;int N;
char s[Maxn*2+5];int main() {
    #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d",&N);scanf("%s",s+1);ll ans=1,cnt=0,tmp=0;for(int i=1;i<=N*2;i++)if((cnt&1)^(s[i]=='B'))cnt++;else ans=(ans*cnt)%Mod,cnt--,tmp++;for(int i=1;i<=N;i++)ans=ans*i%Mod;printf("%lld\n",tmp==N?ans:0);return 0;
}

D. Classified

◇题目传送门◆

题目大意

给定一个有 $N$ 个点的无向完全图，要求将所有的边标上一个数字，使得从任意一个点出发，经过偶数次走后回到该点。输出任意一个方案。

分析

不难发现一个二分图就是一个满足要求的图。

那么我们考虑将一个图分成许多个二分图即可，这个可以用递归解决。

参考代码

#include<cstdio>
#include<algorithm>
using namespace std;const int Maxn=500;int N,A[Maxn+5][Maxn+5];void Solve(int l,int r,int id) {
    if(l==r)return;int mid=(l+r)>>1;for(int i=l;i<=mid;i++)for(int j=mid+1;j<=r;j++)A[i][j]=id;Solve(l,mid,id+1),Solve(mid+1,r,id+1);
}int main() {
    #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d",&N);Solve(1,N,1);for(int i=1;i<N;i++) {
    for(int j=i+1;j<N;j++)printf("%d ",A[i][j]);printf("%d\n",A[i][N]);}return 0;
}

E. Card Collector

◇题目传送门◆

题目大意

有 $N$ 张卡片放在一个 $H×WH\times W$ 的网格上，每张卡片有一个数字 $A_i$ ，放在 $R_i,C_i)$ 上，现要求每行只能取走一张卡片，每列取走一张卡片。求取走的所有卡片上的 $A_i$ 之和的最大值。

分析

考虑费用流解法：对于每行每列建一个点，每张卡片建一个点，每张卡片到原点连一条容量为 $1$ ，费用为 $A_i$ 的边；每张卡片到对应的行和列上连一条容量为 $+∞+\infty$ 费用为 $0$ 的边；每个行列的点向汇点连一条容量为 $1$ ，费用为 $0$ 的边，最后跑一遍最大费用最大流就是了。

这显然是过不去的。仔细分析一下就会发现，对于一条增广路径，只要它被增广了，它就不会再被增广了。

考虑重新构图：将行列分别建点，将第 $i$ 张卡片的所处的对应的行和列的点相连，权值为 $A_i$ ，问题就变成了对于一个二分图，求最大匹配且让权值和最大。

考虑一个类似与Kruskal的算法。将边从大到小排序后逐次加入。由于我们只需判断是否有最大匹配，所以我们利用Hall定理判定即可。

参考代码

#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;
const int Maxn=1e5;int N,H,W;
struct Edge {
    int u,v,val;
};
bool operator < (Edge lhs,Edge rhs) {
    return lhs.val<rhs.val;}
Edge A[Maxn+5];int fa[Maxn*2+5],siz[Maxn*2+5],cnt[Maxn*2+5];
void init() {
    for(int i=1;i<=Maxn*2;i++)fa[i]=i,siz[i]=1,cnt[i]=0;
}
int find(int x) {
    if(fa[x]==x)return fa[x];return fa[x]=find(fa[x]);
}int main() {
    #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d %d %d",&N,&H,&W);for(int i=1;i<=N;i++) {
    scanf("%d %d %d",&A[i].u,&A[i].v,&A[i].val);A[i].v+=H;}sort(A+1,A+N+1);reverse(A+1,A+N+1);init();ll ans=0;for(int i=1;i<=N;i++) {
    int v1=find(A[i].u),v2=find(A[i].v);if(v1==v2) {
    if(siz[v1]==cnt[v1])continue;ans+=A[i].val,cnt[v1]++;} else {
    if(siz[v1]+siz[v2]<cnt[v1]+cnt[v2]+1)continue;else {
    fa[v2]=v1;siz[v1]+=siz[v2],cnt[v1]+=cnt[v2]+1;siz[v2]=cnt[v2]=0;ans+=A[i].val;}}}printf("%lld\n",ans);return 0;
}

F. Candy Retribution

◇题目传送门◆

题目大意

求一个长度为 $N$ 数列 $A$ 满足如下条件：

$?i,Ai≥0\forall i,A_i\ge 0$ 且 $A_i$ 为整数；
$L≤∑i=1NAi≤RL\le \sum_{i=1}^{N}A_i\le R$ ；
将 $A$ 从大到小排序后， $A_M=A_{M+1}$ 。

求一共有这种序列多少个。

分析

不难发现我们可以列出这样一个等式： $?s∈[L,R],∑i=1NAi=s\forall s\in[L,R],\sum_{i=1}^{N}A_i=s$ 。

这个方程的正整数解的方案数可以通过隔板法计算，为 $∑s=LR(s+N?1N?1)\sum_{s=L}^{R}\dbinom{s+N-1}{N-1}$ 。

但要快速计算这个式子的结果呢？

考虑加上一个常量 $B$ ，则式子变为： $∑i=1NAi+B=R\sum_{i=1}^{N}A_i+B=R$ 。

这样就可以快速地计算出结果了，为 $(R+NN)?(L+N?1N)\dbinom{R+N}{N}-\dbinom{L+N-1}{N}$ 。

接下来考虑最后一个条件：

设当前 $∑i=1NAi=s\sum_{i=1}^{N}A_i=s$ ：

设排序后 $A_M=x$ ，不难得出如下不等式组： ${∑i=1MAi≥Mx∑i=M+1NAi<(N?M)x\begin{cases}\sum_{i=1}^{M}A_i\ge Mx\\\sum_{i=M+1}^{N}A_i<(N-M)x\end{cases}$

将第一个不等式的所有 $A_i$ 全部减掉 $x$ ，再代入等式得到剩下的 $N ? M$ 项的和为 $s ? M x$ 。

对于剩下的 $N ? M$ 个数，求出小于等于 $x$ 的方案数即可，这可以用容斥实现。

参考代码

#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;
const int Maxn=1e6;
const ll Mod=1e9+7;ll fac[Maxn+5],inv_fac[Maxn+5];
ll QuickPow(ll a,ll k) {
    ll ret=1;while(k) {
    if(k&1)ret=(ret*a)%Mod;a=(a*a)%Mod;k>>=1;}return ret;
}
void init() {
    fac[0]=1;for(int i=1;i<=Maxn;i++)fac[i]=fac[i-1]*i%Mod;inv_fac[0]=1,inv_fac[Maxn]=QuickPow(fac[Maxn],Mod-2);for(int i=Maxn-1;i>=1;i--)inv_fac[i]=inv_fac[i+1]*(i+1)%Mod;
}
ll C(int n,int m){
    return fac[n]*inv_fac[m]%Mod*inv_fac[n-m]%Mod;}ll calc(int n,int m,int num,int l,int r) {
    if(num-1LL*r*m<0)return 0;else num-=(r*m);ll ret=0;for(int i=0,dir=1;i<=n-m&&num>=0;i++,num-=l,dir*=-1)ret=(ret+1LL*dir*C(num+n,n)%Mod*C(n-m,i)%Mod+Mod)%Mod;return ret*C(n,m)%Mod;
}
ll Solve(int n,int m,int num) {
    ll ret=C(n+num,n);for(int i=num;i>=1;i--) {
    int del=(calc(n,m,num,i,i)-calc(n,m,num,i,i+1)+Mod)%Mod;ret=(ret-del+Mod)%Mod;}return ret;
}int main() {
    #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint N,M,L,R;init();scanf("%d %d %d %d",&N,&M,&L,&R);printf("%lld\n",(Solve(N,M,R)-Solve(N,M,L-1)+Mod)%Mod);return 0;
}