码字不易,给个赞呗。
我认为难度大致如下,我就用某谷的了:
题号 | A | B | C | D | E | F |
---|---|---|---|---|---|---|
大致难度 | 红 | 红 | 红 | 黄 | 绿 | 蓝 |
A kcal
We have a drink that has A kilocalories of energy per 100 milliliters. How many kilocalories of energy does B milliliters of this drink have?
显然,答案为 $\dfrac {AB}{100}$。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int main(){
int n,i;
double a,b;
cin>>a>>b;
printf("%0.5lf",a*0.01*b);
return 0;
}
B Permutation Check
判断数组是否为一个排列,$1\leq A_i\leq N$,$N\leq 1000$。
一个数组是排列当且仅当:
- $1\leq A_i\leq N $
- 每个数至多出现一次。
前一个条件是题目给定的,用一个桶判断各个数的出现次数,
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int a[12000000]
;int main(){
int n,i;
n=read();
for(int i=1;i<=n;++i){
int x=read();
a[x]++;
if(a[x]>1){
puts("No");
return 0;
}
}
puts("Yes");
return 0;
}
C POW
判断 $A^C$ 和 $B^C$ 的大小,$-10^9\leq A,B\leq10^9$,$1\leq C\leq 10^9$。
第一步判断两个数的正负,第二步判断绝对值大小。实现时可以把 $C$ 为偶数时等效为 $2$,奇数时等效为 $1$。控制结果在long long 范围内。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int main(){
int n,i;
long long a,b,c;
cin>>a>>b>>c;
if(c%2==0)c=2;
else c=1;
if(pow(a,c)>pow(b,c))puts(">");
if(pow(a,c)==pow(b,c))puts("=");
if(pow(a,c)<pow(b,c))puts("<");
return 0;
}
D Kth Excluded
给定集合 $A$,多次询问 $S=C_{N^*}A$ 中第 $k$ 大的数。
预处理 $S$ 中小于 $A_i$ 的数。
例如:
A=[2,3,5,7]
k=3
S=[1,4,6,8,9,10,11,...]
预处理出[2,3,5,7]分别在S中比多少数大,为B=[1,1,2,3]。实际上就是 Ai-i。
用二分找出B中第一个不小于k的位置,为4。
这就说明,S中第3个数之前有4-1=3个空,答案就为3+3=6。
为什么要-1?因为第k个数时吃不到我们二分出来的那个位置的。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
ll s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
ll a[100099];
int main(){
ll n=read(),q=read();
for(int i=1;i<=n;++i){
ll x=read();
a[i]=x-i;
}
for(int i=1;i<=q;++i){
ll k=read();
ll p=lower_bound(a+1,a+n+1,k)-a;
printf("%lld\n",k+p-1);
}
return 0;
}
E White and Black Balls
有多少 $01$ 串满足:
- $N$ 个 $0$ 和 $M$ 个 $1$。
- 对于每一位,其左边(包括该位)的 $0$ 的个数与 $1$ 的个数之差不大于给定常数 $K$。
一个类似于卡特兰数的东西。用一个类似于卡特兰数的证明方法。
我们用一张官方题解的图。我们说明下:
-
x轴表示1的个数,y轴表示0的个数。一个串对应从原点到 $(M,N)$ 的路径。
-
一条合法串对应一条不触线的路径。
任意一条触线的路径可以与 $(-k-1,k+1)$ 到 $(M,N)$ 的路径一一对应。
答案=总方案-非法方案=$C(N+M, N) - C(M+N,M+K+1)$。
特判答案为 $0$ 和 $C(N+M, N)$ 的情况。
code
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll qp(ll a,ll b){
if(b==0)return 1;
if(b==1)return a%mod;
ll x=qp(a,b>>1);
return b&1?x*x%mod*a%mod:x*x%mod;
}
ll f[8000999]={1};
ll c(ll n,ll m){
ll x=f[n],y=f[n-m]*f[m]%mod;
return x*qp(y,mod-2)%mod;
}
int main(){
ll a,b,k;
for(ll i=1;i<=8000000;++i){
f[i]=i*f[i-1]%mod;
}
cin>>a>>b>>k;
if(k+1>a)printf("%lld",c(a+b,a));
else if(a>b+k+1)cout<<0;
else printf("%lld",(c(a+b,a)-c(a+b,b+k+1)+mod)%mod);
}
F - Grid and Tokens
有 $N$ 个棋子,你可以把每个棋子放在 $(l_i\sim r_i,L_i\sim R_i)$ 中。
每行每列至多放一个棋子。求至多放多少棋子。
$N,L,l,R,r\leq 100$
我们再用官方的图来讲一下。
$R_i$ 表示第 $i$ 行,$C_i$ 表示第 $i$ 列。
$U_i$ 连该棋子合法的行,$V_i$ 连列。
一个棋子 $i$ 被放置在 $(a,b)$。就意味着一条 $S\to a\to U_i\to V_i\to b\to D$ 的流。
这样 $a,b$ 就被占用了,木伐再选了。
因此答案就为图的最大流。
大佬能详细写下D题的题解不,看不懂代码,菜鸡哭泣
updated
感谢