2020牛客寒假算法基础集训营1
这套题整体来说还是很简单的。
A.honoka和格点三角形
这个题目不是很难，不过要考虑周全，面积是1，那么底边的长度可以是1也可以是2，
注意底边1和2会有重复的，所以要注意去除这个重复部分的。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+;
typedef long long ll;
const int mod=1e9+;
int main(){
ll n,m,ans=;
scanf("%lld%lld",&n,&m);
ans=*(m-)%mod*m%mod*(n-)%mod;
ans+=*(n-)%mod*n%mod*(m-)%mod;
ans+=*(m-)%mod*(m-)%mod*(n-)%mod;
ans+=*(n-)%mod*(n-)%mod*(m-)%mod;
ans%=mod;
printf("%lld\n",ans);
return ;
}
A
B.kotori和bangdream
这个题目也很简单，因为每一个音符的概率都是确定的。。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+;
typedef long long ll; int main(){
int n,x,a,b;
cin>>n>>x>>a>>b;
double ans=n*x*a+n*(-x)*b;
ans/=100.0;
printf("%.2f\n",ans);
return ;
}
B
C.umi和弓道
这个可能看起来稍微复杂一点，不过整体还是很简单，
把所有可以投影到y轴的投影到y轴，可以投影到x轴的投影到x轴。
然后排个序，求长度最短的n-k个点。
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+;
typedef long long ll;
long double dx[maxn],dy[maxn];
long double x[maxn],y[maxn];
int judge(ll x,ll y){
if(x>&&y>) return ;
if(x<&&y>) return ;
if(x<&&y<) return ;
if(x>&&y<) return ;
}
int main(){
ll n,k;
long double x0,y0;
scanf("%Lf%Lf%lld%lld",&x0,&y0,&n,&k);
int f=judge(x0,y0);
int num=,numx=,numy=;
for(int i=;i<=n;i++){
scanf("%Lf%Lf",&x[i],&y[i]);
int ans=judge(x[i],y[i]);
if(ans==f) num++;
else if(x0*x[i]>) numx++;
else if(y0*y[i]>) numy++;
}
if(num+numx>k&&num+numy>k){
printf("-1\n");
return ;
}
int cntx=,cnty=;
for(int i=;i<=n;i++){
if(x[i]*x0<){
// cout<<"i="<<i<<" x[i]="<<x[i]<<" y[i]="<<y[i]<<endl;
dy[++cnty]=(y0-y[i])/(x0-x[i])*(-x0)+y0;
// printf("dy[%d]=%Lf\n",cnty,dy[cnty]);
}
if(y0*y[i]<){
dx[++cntx]=(x0-x[i])/(y0-y[i])*(-y0)+x0;
}
}
int res=n-k;
sort(dy+,dy++cnty);
sort(dx+,dx++cntx);
long double ans=2e9;
for(int i=res;i<=cntx;i++){
// printf("dx[%d]=%Lf\n",i,dx[i]);
ans=min(ans,dx[i]-dx[i-res+]);
}
for(int i=res;i<=cnty;i++){
// printf("dy[%d]=%Lf dy[%d]=%Lf\n",i,dy[i],i-res+1,dy[i-res+1]);
ans=min(ans,dy[i]-dy[i-res+]);
}
printf("%.6Lf\n",ans);
return ;
}
C
D.hanayo和米饭
这个太签到了
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+;
typedef long long ll; int vis[maxn]; int main(){
int n;
scanf("%d",&n);
for(int i=;i<n;i++){
int x;
scanf("%d",&x);
vis[x]=;
}
for(int i=;i<=n;i++){
if(!vis[i]){
printf("%d\n",i);
return ;
}
}
}
D
E.rin和快速迭代
这个题目f函数其实求的就是约数的个数，这个还是很好求的，
把这个数唯一分解，x=p1^a1*p2^a2*....*pn^an
那么这个数的约数的个数就是 num=(a1+1)*(a2+1)*...*(an+1)
这个就暴力求就可以了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+;
typedef long long ll;
const int mod=1e9+;
ll v[maxn],isp[maxn],m;
void init1()
{
for(int i=;i<maxn;i++){
if(v[i]==){
isp[m++]=i;
v[i]=i;
}
for(int j=;j<m;j++){
if(v[i]<isp[j]||i*isp[j]>maxn) break;
v[i*isp[j]]=isp[j];
}
}
}
ll judge(ll x){
ll ans=,p=;
for(int i=;i<m;i++){
while(x%isp[i]==){
// printf("isp[%d]=%d\n",i,isp[i]);
p++,x/=isp[i];
}
ans*=p,p=;
if(x==) break;
}
if(x>) ans*=;
// printf("x=%lld ans=%lld\n",x,ans);
return ans;
} int main(){
init1();
ll n,res=;
scanf("%lld",&n);
while(n>) n=judge(n),res++;
printf("%lld\n",res);
return ;
}
E
F.maki和tree
这个题目我觉得我写的挺复杂的，
我是先预处理出白色块的连通块。
然后对于每一个黑块去枚举它周围的白色连通块。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+;
typedef long long ll;
struct node{
int v,nxt;
node(int v=,int nxt=):v(v),nxt(nxt){}
}e[maxn*];
int head[maxn],cnt;
void add(int u,int v){
e[++cnt]=node(v,head[u]);
head[u]=cnt;
e[++cnt]=node(u,head[v]);
head[v]=cnt;
}
int f[maxn],sum[maxn];
char s[maxn];
void dfs(int u,int pre){
f[u]=pre,sum[u]=;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==pre) continue;
dfs(v,u);
if(s[u]!='B'&&s[v]!='B') sum[u]+=sum[v];
}
}
void dfs1(int u,int pre){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==pre) continue;
if(s[u]!='B'&&s[v]!='B') sum[v]=max(sum[v],sum[u]);
dfs1(v,u);
}
}
ll ans=;
void dfsans(int u,int pre){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==pre) continue;
dfsans(v,u);
}
if(s[u]!='B') return ;
ll all=;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(s[v]=='B') continue;
all+=sum[v];
ans-=sum[v]*(sum[v]-)/;
}
ans+=all*(all-)/;
}
int main(){
int n;
scanf("%d%s",&n,s+);
for(int i=;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
dfs(,-),dfs1(,-);
dfsans(,-);
printf("%lld\n",ans);
}
F
G.eli和字符串
这个题目很简单，直接暴力枚举26个字母即可。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=2e5+;
typedef long long ll;
char s[maxn];
int num[],pos[][maxn];
int main(){
int n,k;
scanf("%d%d%s",&n,&k,s+);
int slen=strlen(s+);
for(int i=;i<=slen;i++){
int x=s[i]-'a';
num[x]++;
pos[x][num[x]]=i;
}
int ans=inf;
for(int i=;i<;i++){
if(num[i]<k) continue;
int cnt=;
for(int j=k;j<=num[i];j++) ans=min(ans,pos[i][j]-pos[i][j-k+]+);
}
if(ans>=inf) ans=-;
printf("%d\n",ans);
return ;
}
G
H.nozomi和字符串
这个是一个二分，二分最大长度即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+;
typedef long long ll;
const int mod=1e9+;
char s[maxn];
int n,k,slen;
int num[][maxn];
bool check(int x){
for(int i=x;i<=slen;i++){
int len0=num[][i]-num[][i-x];
int len1=num[][i]-num[][i-x];
if(len0<=k||len1<=k) return true;
}
return false;
}
int main(){
scanf("%d%d%s",&n,&k,s+);
slen=strlen(s+);
for(int i=;i<=slen;i++){
num[][i]=num[][i-];
num[][i]=num[][i-];
num[s[i]-''][i]++;
}
int l=,r=n,ans=;
while(l<=r){
int mid=(l+r)>>;
if(check(mid)) ans=mid,l=mid+;
else r=mid-;
}
printf("%d\n",ans);
return ;
}
H
I.nico和niconiconi
这个是一个dp，注意细节的处理。
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+;
typedef long long ll;
char cur[]={'n','i','c','o'},s[maxn];
ll dp[maxn];
int main(){
ll n,a,b,c;
scanf("%lld%lld%lld%lld%s",&n,&a,&b,&c,s+);
for(int i=;i<=n;i++){
dp[i]=max(dp[i-]+a,dp[i]);
if(i>=) dp[i]=max(dp[i],dp[i-]+b);
if(i>=) dp[i]=max(dp[i],dp[i-]+c);
}
ll ans=;
int num=,pos=,slen=strlen(s+);
s[++slen]='~';
for(int i=;i<=slen;i++){
if(s[i]==cur[pos]) {
pos++;
if(pos==) num++,pos=;
}
else{
ll res=dp[num];
if(pos>=){
if(num>=) res=max(dp[num-]+b,res);
if(num>=) res=max(dp[num-]+c,res);
}
ans+=res,num=,pos=;
if(s[i]==cur[pos]) pos++;
}
}
printf("%lld\n",ans);
return ;
}
/*
19 1 2 5
niconiconiniconico
*/
I
J.u's的影响力
这个推一下就会发现，x和y的指数都是斐波那契数列的一项，a^b的指数是斐波那契数列的前缀和。
所以都可以用矩阵快速幂解决，斐波那契数列前缀和也可以用矩阵快速幂解决。
推荐资料：大斐波拉契数列及斐波拉契前缀和(m阶前缀和)求解
斐波那契数列总(这个挺好的）
但是这个还有几个点需要注意，第一个：斐波那契数列求的是指数，所以不可以直接对mod取模，而是要对mod-1取模，因为费马小定理。
ap-1 mod p == 1 所以只可以对p-1取模。
第二个就是a是p的倍数时，不满足费马小定理，这个要分开考虑。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const long long mod = 1e9+; int UP;
struct mat
{
long long mn[][];
mat() {
for(int i = ;i<UP;i++) {
for(int j = ;j<UP;j++) {
mn[i][j]=;
}
}
for(int i = ;i<UP;i++) {
mn[i][i] = ;
}
}
void init(){
for(int i=;i<UP;i++){
for(int j=;j<UP;j++){
mn[i][j]=;
}
}
}
mat operator * (const mat& a) {
mat res;
for(int i = ;i<UP;i++) {
res.mn[i][i] = ;
}
for(int i=;i<UP;i++) {
for(int j=;j<UP;j++) {
for(int k=;k<UP;k++) {
res.mn[i][j] += mn[i][k]*a.mn[k][j]%(mod-);
res.mn[i][j] %= (mod-);
}
}
}
return res;
}
}; mat fast(mat a,long long c) {
mat res = mat();
while(c) {
if(c&) res = res * a;
a = a*a;
c >>= ;
}
return res;
}
ll quick_mul(ll a,ll b,ll mod)
{
ll ans = ;
while(b)
{
if (b & ) ans = (ans + a) % mod;
a = (a + a) % mod;
b >>= ;
}
return ans;
} ll quick_pow(ll a,ll b,ll mod)
{
ll ans = ;
while(b)
{
if (b & ) ans = quick_mul(ans, a, mod);
a = quick_mul(a, a, mod);
b >>= ;
}
return ans;
}
int main(){
UP=;
ll n,x,y,a,b;
scanf("%lld%lld%lld%lld%lld",&n,&x,&y,&a,&b);
if(n==) {
printf("%lld\n",x%mod);
return ;
}
if(n==){
printf("%lld\n",y%mod);
return ;
}
if(x%mod==||y%mod==||a%mod==){
printf("0\n");
return ;
}
mat res;res.init();
res.mn[][]=,res.mn[][]=res.mn[][]=res.mn[][]=;
res=fast(res,n-);
x=quick_pow(x,res.mn[][],mod);
y=quick_pow(y,res.mn[][],mod);
a%=mod,a=quick_pow(a,b,mod);
UP=,res.init();
res.mn[][]=res.mn[][]=res.mn[][]=;
res.mn[][]=res.mn[][]=res.mn[][]=;
res=fast(res,n-);
a=quick_pow(a,res.mn[][]+res.mn[][],mod);
printf("%lld\n",quick_mul(quick_mul(a,x,mod),y,mod));
return ;
}
J
