Codeforces Round #471 (Div. 2)

Codeforces Round #471 (Div. 2)

比赛链接

QAQ终于补完了这场的题。。感觉后面几题还都挺好的就写个（非常）简略的总结叭。

A. Feed the cat

简单贪心+模拟。

#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define ll long long
using namespace std;
long double ans;
int main(){int a,b,H,D,C,N;scanf("%d%d",&a,&b);scanf("%d%d%d%d",&H,&D,&C,&N);ans=((H-1)/N+1)*C;// printf("%.15lfn",(double)ans);if (a<20) H+=D*((19-a)*60+60-b);//printf("%dn",H);ans=min(ans,(long double)((int)((H-1)/N+1)*C)*0.8);printf("%.15lfn",(double)ans);return 0;
}

B. Not simply beatiful strings

枚举几种情况特判一下即可。

#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define ll long long
#define N 100005
using namespace std;
int n,ch[30]; char s[N];
int main(){scanf("%s",s+1); n=strlen(s+1);int cnt=0;rep (i,1,n){if (!ch[s[i]-'a']) cnt++;ch[s[i]-'a']++;}if (cnt<=1 || cnt>4){ puts("No"); exit(0); }int mx=0; rep (i,0,25) mx=max(mx,ch[i]);int mi=n+1; rep (i,0,25) if (ch[i]) mi=min(mi,ch[i]);if (cnt==3 && mx==1){ puts("No"); exit(0); }if (cnt==2 && mi==1){ puts("No"); exit(0); }puts("Yes");return 0;
}

C. Sad powers

先转化为求 [1,r]−[1,l−1] [ 1 , r ] − [ 1 , l − 1 ] $[1,r]-[1,l-1]$ ，然后按照 n13 n 1 3 $n^{frac13}$ 分类一下。 106 10 6 $10^6$ 以内的预处理出3次及以上的。2次的直接开根号下取整即可。

//考场上搞了很久爆了很多发qaq，以至于分数特别的低。。

#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define ll long long
#define N 1000005
#define inf 1000000000000000000ll
#define sqr(x) ((x)*(x))
using namespace std;
ll a[N*30],l,r,ans; int q,tot;
void pre(){rep (i,2,1000000){long double tmp=(long double)i*i*i;while (tmp && tmp<=(long double)inf){if ((ll)floor(sqrt(tmp))!=sqrt(tmp)) a[++tot]=(ll)tmp;if (tmp*(long double)i<=inf) tmp*=i; else break;}}sort(a+1,a+1+tot); tot=unique(a+1,a+1+tot)-a-1;
}
int main(){/*freopen("C.in","r",stdin);freopen("C.out","w",stdout);*/pre();// printf("%dn",tot);scanf("%d",&q);while (q--){cin>>l>>r;int pl=upper_bound(a+1,a+1+tot,l-1)-a-1;int pr=upper_bound(a+1,a+1+tot,r)-a-1;ans=pr-pl;ans+=(ll)sqrt(r);ans-=(ll)sqrt(l-1);cout<<ans<<endl;}return 0;
}

D. Scissors

思路比较显然，就是枚举串 t t $t$ 的断点然后判断是否可行。kmp预处理出串 t" role="presentation">tt$t$ 和串 s s $s$ 拼接起来的 next" role="presentation">nextnext$mathrm{next}$ 数组以及翻转后的，然后预处理出 w1 w2 w 1 w 2 $w1 w2$ ， w1[i] w 1 [ i ] $w1[i]$ 表示串 t+s t + s $t+s$ 中 next n e x t $mathrm{next}$ 值为 i i $i$ 的最小在原串中的下标， w2[i]" role="presentation">w2[i]w2[i]$w2[i]$ 表示 t+s t + s $t+s$ 翻转后的串中 next n e x t $mathrm{next}$ 值为 i i $i$ 的最大在原串中的下标。然后就可以 O(1)" role="presentation">O(1)O(1)$O(1)$ 判断了。

#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define per(i,x,y) for (int i=(x); i>=(y); i--)
#define ll long long
#define N 1000005
#define all(x) (x).begin(),(x).end()
using namespace std;
int n,m,k,len,f[N],g[N],w1[N],w2[N]; char s[N],t[N],str[N];
void get_next(char s[],int nxt[]){int k=0; nxt[1]=0;rep (i,2,len){while (k && s[k+1]!=s[i]) k=nxt[k];if (s[k+1]==s[i]) nxt[i]=++k; else nxt[i]=k;}
}
int main(){scanf("%d%d%d%s%s",&n,&m,&k,s+1,t+1);if (k*2>n || k*2<m){ puts("No"); exit(0); }len=0;rep (i,1,m) str[++len]=t[i]; str[++len]='#';rep (i,1,n) str[++len]=s[i];get_next(str,f);len=0;rep (i,1,n) str[++len]=s[i]; str[++len]='#';rep (i,1,m) str[++len]=t[i]; reverse(str+1,str+1+len);get_next(str,g);rep (i,m+2,n+m+1) if (f[i]>=m){int p1=i-m-1; p1=max(p1-2*k,0);printf("Yesn%d %dn",p1+1,p1+1+k); exit(0);}rep (i,0,n) w1[i]=n+1;rep (i,m+2,n+m+1){if (i-m-1>=k){int tmp=f[i];while(tmp){if (i-m-1<w1[tmp]) w1[tmp]=i-m-1; else break;tmp=f[tmp];}tmp=g[i];while (tmp){if (n-(i-m-1)+1>w2[tmp]) w2[tmp]=n-(i-m-1)+1; else break;tmp=g[tmp];}}}w1[0]=0; w2[0]=n+1;rep (i,1,min(k,m)){//左边取i个if (m-i>k) continue;int p1=w1[i]-k+1,p2=w2[m-i];if (p1>=1 && p2+k-1<=n && w1[i]<p2){printf("Yesn%d %dn",p1,p2); exit(0);}}puts("No");return 0;
}

E. Icicles

见注释。

/*
*   枚举T：
*   tim_i表示在T点发射声波，i号点降落的时间
*   i<T:tim_i=a[i]+T-i; i>=T:tim_i=a[i]+i-T;
*   找到最小的满足tim_j<j的j
*   ans=max(min(tim_i|1<=i<j),min(tim_i|j<=i<=n));
*/
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define ll long long
#define N 100005
#define inf 1000000000
using namespace std;
ll read(){char ch=getchar(); ll x=0; int op=1;for (; !isdigit(ch); ch=getchar()) if (ch=='-') op=-1;for (; isdigit(ch); ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';return x*op;
}
int n,L,ans,a[N],pre[N][25],suf[N][25],mi[N][25],lg[N];
int get_min(int x,int y){if (x>y) return inf;int tmp=lg[y-x+1]; return min(mi[x][tmp],mi[y-(1<<tmp)+1][tmp]);
}
int get_min1(int x,int y){if (x>y) return inf;int tmp=lg[y-x+1]; return min(pre[x][tmp],pre[y-(1<<tmp)+1][tmp]);
}
int get_min2(int x,int y){if (x>y) return inf;int tmp=lg[y-x+1]; return min(suf[x][tmp],suf[y-(1<<tmp)+1][tmp]);
}
int main(){n=read(); rep (i,1,n) mi[i][0]=a[i]=read();rep (i,1,n) pre[i][0]=a[i]-i;rep (i,1,n) suf[i][0]=a[i]+i;rep (j,1,20) for (int i=1; i+(1<<j-1)<=n; i++){mi[i][j]=min(mi[i][j-1],mi[i+(1<<j-1)][j-1]);pre[i][j]=min(pre[i][j-1],pre[i+(1<<j-1)][j-1]);suf[i][j]=min(suf[i][j-1],suf[i+(1<<j-1)][j-1]);}lg[1]=0; rep (i,2,n) lg[i]=lg[i>>1]+1;L=1; ans=inf;rep (T,1,n){while (L<=T && T>=2*L-a[L]) L++;//j<T: a[j]+T-j<j ---> T<2*j-a[j]int j=-1;if (L<=T) j=L;else {int l=T,r=n,mid,pos=-1;while (l<=r){mid=l+r>>1;if (get_min(T,mid)<T) pos=mid,r=mid-1; else l=mid+1;}if (pos==-1) continue; j=pos;}//j>T: a[j]+j-T<j ---> T>a[j]int x,y;if (j<=T){x=get_min1(1,j-1)+T;y=min(get_min1(j,T)+T,get_min2(T+1,n)-T);} else{x=min(get_min1(1,T)+T,get_min2(T+1,j-1)-T);y=get_min2(j,n)-T;}ans=min(ans,max(x,y));}if (ans==inf) cout<<-1<<endl; else cout<<ans<<endl;return 0;
}

F. Heaps

树形dp。见注释。

#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define per(i,x,y) for (int i=(x); i>=(y); i--)
#define ll long long
#define N 300005
using namespace std;
ll read(){char ch=getchar(); ll x=0; int op=1;for (; !isdigit(ch); ch=getchar()) if (ch=='-') op=-1;for (; isdigit(ch); ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';return x*op;
}
int n,cnt,head[N],mx[N],dp[N][25],q[N]; ll ans;
struct edge{int to,nxt;
}e[N<<1];
void adde(int x,int y){e[++cnt].to=y; e[cnt].nxt=head[x]; head[x]=cnt;
}
void ins(int x,int y){adde(x,y); adde(y,x);
}
const bool cmp(const int x,const int y){ return x>y; }
void dfs(int u,int pr){for (int i=head[u],v; i; i=e[i].nxt) if ((v=e[i].to)!=pr){dfs(v,u); mx[u]=max(mx[u],mx[v]);}ans+=++mx[u];//k=1的情况dp[u][1]=n;//dp[i][j]表示i号点，深度为j的最大能取到的krep (i,2,20){//深度最多不超过log_{k}^{n}，因为最多在满多叉树的时候满足要求，此时深度为lognint tp=0;for (int j=head[u],v; j; j=e[j].nxt) if ((v=e[j].to)!=pr) q[++tp]=dp[v][i-1];sort(q+1,q+1+tp,cmp);per (j,tp,2) if (q[j]>=j){ dp[u][i]=j; break; }//第k大的值>=k说明能取到k}
}
void solve(int u,int pr){for (int i=head[u],v; i; i=e[i].nxt) if ((v=e[i].to)!=pr){solve(v,u);rep (j,1,20) dp[u][j]=max(dp[u][j],dp[v][j]);}rep (i,1,20){ans+=(ll)(dp[u][i]-dp[u][i+1])*i;if (dp[u][i+1]==0){ ans-=i; break; }}
}
int main(){n=read();rep (i,1,n-1){int x=read(),y=read(); ins(x,y);}dfs(1,0); solve(1,0); cout<<ans<<endl;return 0;
}

总结

赛时通过ABC，rk53，rating+91.

成功地将我掉蓝的大号升回了紫qnq。

//然鹅自己还是菜的一匹啊

//现在似乎一打d1就掉分啊qaq我该怎么办