锐客网

  1. 首页 > it技术 > >

cf训练赛20190730


cf训练赛20190730

  • 总结：
  • A. Dungeons and Candies
  • B. Maximum Xor Secondary
  • C. k-Multiple Free Set
  • D. Valera and Elections
  • E. Color Stripe
  • F. Work Group

  • A. Dungeons and Candies
  • B. Maximum Xor Secondary(后补)
  • C. k-Multiple Free Set
  • D. Valera and Elections(后补)
  • E. Color Stripe(后补)
  • F. Work Group
总结： 做题手感太差。明明全是水题，但是思路就容易卡死，其实有想到正确做法的，但是要么思路没成型，要么就是不知道操作性怎么样没敢试。结果到最后思路偏了卡题卡到最后也就写了一题。听完讲题思路对了直接快速AC。
A. Dungeons and Candies B. Maximum Xor Secondary 题意：给一个数字数组，其子串（长度大于等于2）中最大和第二大的数异或的值为幸运数，找所有子串（长度大于等于2）中最大的幸运数。
解：
单调栈处理每个数 左边第一个比自己大的数和右边第一个比自己大的数。对于当前数i，左边第一个比自己大的数和自己异或构成一个幸运数，右边第一个比自己大的数和自己构成一个幸运数。每个数得到至多两个幸运数，所有幸运数最大的就是答案。
int a[100005]; int L[100005]; int R[100005]; int main() { int n; cin>>n; for(int i=1; i<=n; i++) cin>>a[i]; stack lq,rq; for(int i=1 ; i<=n ; i++) { while(lq.size() && lq.top()< a[i]) lq.pop(); if(lq.empty())L[i] = 0; elseL[i] = lq.top(); lq.push(a[i]); } for(int i=n; i>=1 ; i--) { while(rq.size() && rq.top()< a[i]) rq.pop(); if(rq.empty())R[i] = 0; elseR[i] = rq.top(); rq.push(a[i]); } int ans=0; for(int i=1; i<=n; i++) { if(L[i]) { ans=max(L[i]^a[i],ans); } if(R[i]) { ans=max(R[i]^a[i],ans); } } cout<

C. k-Multiple Free Set 题意：给一个不同数字的数字数组，一个k，要求删去一些数，使得数组中不能出现两个数x,y，使得x是y的k倍，求删去数的最小个数。
解：最开始想的太麻烦了，思路偏了，导致浪费了很多时间在这个水题上。实际上只需要将数组sort一下，对于每个数，lower_bound查找是否这个数乘k的数在数组里，在的话就删掉，就能保证删的最少。
ll a[100005]; bool mark[100005]; int main() { ll n,k,ans=0,x; scanf("%lld %lld",&n,&k); for(int i=0; i

D. Valera and Elections 题意：给一棵树从点1~n，给出某些边坏掉了，选择一个k点，每次可以修好从1 ~ k以内的所有边，问最小选择几个，都哪些点，可以使树上所有边都是好的。
解：
学长讲题的时候思路太绕我没听懂。我好久没写过图论的题了，连存图都不会了，但是觉得明明可以从1直接遍历整个树，如果当前点最下面没有坏边或者下面没有点了，而这个点和他父亲节点之间是条坏边，那么就要这个点，其他情况全不要。这样得到的点集就是答案。我花了点时间复习了一下链式前向星存图，然后一边就过了。
struct edge { int to; int next; int t; }E[maxn*2]; int head[maxn]; int ans[maxn]; int cnt=0,tot=0; void add(int u,int v,int t) { E[cnt].to=v; E[cnt].t=t; E[cnt].next=head[u]; head[u]=cnt++; } int dfs(int u,int pre) { int flag,sf=0; for(int i=head[u]; i!=-1; i=E[i].next) { int v=E[i].to; if(v==pre)continue; flag=dfs(v,u); if(flag==0&E[i].t==2) ans[tot++]=v; if(flag==1||E[i].t==2) sf=1; } return sf; } int main() { memset(head,-1,sizeof(head)); memset(E,0,sizeof(E)); memset(ans,0,sizeof(ans)); int n; cin>>n; int u,v,t; for(int i=1; i<=n-1; i++) { cin>>u>>v>>t; add(u,v,t); add(v,u,t); } dfs(1,0); cout<

E. Color Stripe 题意：
给一个大写字母串，只含26个大写字母的前K个，想让他相邻两个字母不能相同，每次可以把其中一个字母变成26个大写字母的前K个中的一个，问你最少多少次操作能够做到。
解：
浪费超多时间的水题，最后还没做出来，气的不行，听完讲题才知道自己脑回路卡死在了一起处理上，其实可以分情况的。其实很简单，就是分情况处理，当k=2时，只能是ABABA或者BABAB的情况，直接暴力；当k>2，当有相同的，s[i]==s[i+1]，那就把是s[i+1]换成一个与s[i]和s[i+2]都不同的，一边遍历完事。
int n,k; int solvel(string &s) { int ans1=0; for(int i=0; i【cf训练赛20190730】if(j>=k||i+2>=n) { for(int z=0; z>n>>k) { cin>>s; int cnt=0,ans=0; ; if(k==2) { for(int i=0; i

F. Work Group

    推荐阅读


    上一篇：磁盘调度算法的模拟实现

    下一篇：时间性能分析——时间复杂度计算