你说的对，但是我觉得应该先把 qual C 写完再去学什么东西。
CF
codeforces.
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
int n;
char s[110];
int main(){
scanf("%s",s+1);n=strlen(s+1);
for(int i=1;i<=n;i++){
if(s[i]=='C'){
for(int j=i+1;j<=n;j++){
if(s[j]=='F'){
puts("Yes");return 0;
}
}
puts("No");
return 0;
}
}
puts("No");
return 0;
}
K Cakes
对，但为啥要切红题。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
int n,m;
int main(){
scanf("%d%d",&m,&n);
int mx=0;
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
mx=max(mx,x);
}
printf("%d\n",max(2*mx-m-1,0));
return 0;
}
Two Alpinists
每个位置范围区间。对。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
const int mod=1000000007;
int n,a[100010],b[100010],l[100010],r[100010];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
for(int i=1;i<=n;i++){
if(a[i]==a[i-1])l[i]=1,r[i]=a[i];
else l[i]=r[i]=a[i];
}
for(int i=n;i>=1;i--){
if(b[i]==b[i+1])l[i]=max(l[i],1),r[i]=min(r[i],b[i]);
else l[i]=max(l[i],b[i]),r[i]=min(r[i],b[i]);
}
int ans=1;
for(int i=1;i<=n;i++){
if(l[i]>r[i]){
puts("0");return 0;
}
ans=1ll*ans*(r[i]-l[i]+1)%mod;
}
printf("%d\n",ans);
return 0;
}
Friction
样例有 ccf 子序列。
首先瞪着题面瞪半天发现不同列之间可以独立开，然后就可以枚举相邻两列算。证明不会，感觉是对的就是对的。
那直接 \(dp_{i,j}\) 为一个挪了 \(i\) 一个挪了 \(j\) 的最小代价。代价可以前缀和统计一下。就完了。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
int n,m,ans,dp[310][310],val[310][310];
char s[310][310];
int solve(int x){
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
val[i][j]=0;dp[i][j]=0x3f3f3f3f;
}
}
dp[0][0]=0;
for(int i=0;i<=n;i++){
for(int l=n-i,r=n;l>=1;l--,r--){
if(s[l][x]==s[r][x+1])val[i][0]++;
}
}
for(int i=1;i<=n;i++){
for(int l=n,r=n-i;r>=1;l--,r--){
if(s[l][x]==s[r][x+1])val[0][i]++;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
val[i][j]=val[i-1][j-1]-(s[n-i+1][x]==s[n-j+1][x+1]);
}
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
if(i)dp[i][j]=min(dp[i][j],dp[i-1][j]+val[i-1][j]);
if(j)dp[i][j]=min(dp[i][j],dp[i][j-1]+val[i][j-1]);
}
}
return dp[n][n];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=1;i<m;i++)ans+=solve(i);
printf("%d\n",ans);
return 0;
}
Encyclopedia of Permutations
看到的时候感觉很典。实际上好像也很典？
看起来就很康托展开，那看看康托展开的式子：每个位置 \(i\) 的贡献是 \(i\) 开头的逆序对个数乘 \((n-i)!\) 最后 \(+1\)。那算个数。
四种情况：（设 \(cnt_i\) 为 \(<i\) 有几个数空着）
- \(i\to j\)：需要 \(a_i>a_j\)，贡献 \(cnt_n!\)。
- \(i\to 0\)：每个 \(0\) 有贡献 \((cnt_n-1)!cnt_i\)。
- \(0\to j\)：每个 \(j\) 贡献 \((cnt_n-1)!(cnt_n-cnt_j)\)。
- \(0\to 0\)：每个 \(0\) 贡献 \(\frac{cnt_n!}2\)。
那只需要统计 \(cnt_n-cnt_i\) 的后缀和和 \(0\) 的后缀个数和，再树状数组算个逆序对。最后要加上 \(cnt_n!\)。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
const int mod=1000000007,inv2=(mod+1)>>1;
int n,ans,a[500010],cnt[500010],jc[500010];
struct BIT{
int c[500010];
#define lowbit(x) (x&-x)
void update(int x,int val){
while(x<=n)c[x]+=val,x+=lowbit(x);
}
int query(int x){
int sum=0;
while(x)sum+=c[x],x-=lowbit(x);
return sum;
}
}c;
int main(){
scanf("%d",&n);jc[0]=1;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i])cnt[a[i]]--;
jc[i]=1ll*jc[i-1]*i%mod;
}
for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1]+1;
int num=0,pre=0,suf=0;
for(int i=n;i>=1;i--){
if(a[i]==0){
ans=(ans+1ll*jc[n-i]*inv2%mod*jc[cnt[n]]%mod*num)%mod;
num++;
ans=(ans+1ll*jc[n-i]*jc[cnt[n]-1]%mod*suf)%mod;
}
else{
ans=(ans+1ll*jc[n-i]*jc[cnt[n]-1]%mod*cnt[a[i]]%mod*num)%mod;
suf=(suf+cnt[n]-cnt[a[i]])%mod;
ans=(ans+1ll*jc[n-i]*jc[cnt[n]]%mod*c.query(a[i]))%mod;
c.update(a[i],1);
}
}
ans=(ans+jc[cnt[n]])%mod;
printf("%d\n",ans);
return 0;
}