当前位置：网站首页>Codeforces Round ＃787 (Div. 3)

Codeforces Round ＃787 (Div. 3)

2022-07-18 10:26:00 【InfoQ】

​ Temporary supplementary questions before school competition codeforces The school game is coming soon , I haven't hit the question for too long , Afraid of being beaten violently in the school game , So I wrote a set of div3, Found that many will not , Then write a solution to the problem and review it , Shun Yishun idea .

A. Equidistant Letters The question ： A relatively simple question means , The distance between two identical letters is required to be the same , But the same letter can appear up to two times in this string , Then put the same letters together , Look again, the length is not very big , No more than 52 individual , So Sort directly nlogn feasible .52*1e3, Of course, there are O（n） Just record the complexity directly

B. Minor Reduction The question ： In a that does not contain a preamble 0 In a numeric string , You can do one operation , Add their numbers and , Then replace two numbers .

Ideas ： At first glance, it feels very difficult , But only once , Start thinking about how to replace , First, if the two numbers are added, the possible value is 【0,18】 in , And after the addition and existence >=10, Then it must be better than adding only one digit , Then carefully observe that if you add two numbers after adding , In fact, it does not change its original number of characters , And at least two numbers are greater than or equal to 1 Of , And what must be added is 1x, It must be smaller , So look back and forward , The first to two numbers is the best , But if there are no two numbers , The first summation should be optimal , It can get bigger

C. Detective Task The question ： There is a picture , Personally , At some point in the middle, it was stolen by someone . Ask everyone if the painting was still there when he looked at it , The answer may be  (1) /  nothing  (0) /  Forget the  (?). Good people tell the truth / Forget the , The person who stole it will choose a random answer . Ask how many people may be thieves at most

Ideas ： A good idea is to think about if the current position is a thief , Then it must not appear before 0 Of （ empty ）, And it must not appear after 1（ Yes ）, So keep maintaining this section , Can double pointer , You can also prefix and , The prefix and I used by myself are good, but it's a little complicated .

// The front is full of yes, Behind all no// There is no no, There is no yes


D. Vertical Paths The question ： Given an array p[N], among p[i] by i Parent node ,1. Find non coincidence , And the minimum number of paths covering all nodes ,2, And output the path respectively , The path is output in the order from the parent node to the child node .

Ideas ： Minimum number of paths covering all nodes , And it must meet the order from the upper layer to the lower layer , It's not hard to imagine. , Each leaf node can be used as the endpoint of the answer , Then think about the fact and dfs It's very similar , From the beginning dfs Search to the end , That is to find the first leaf node , Then dye this path directly , This situation is optimal . The test is the realization problem .



 }
 dfs(-1,rt);
 cout<<tot<<endl;
 for(i=1;i<=tot;i++)
 {
 cout<<ans[i].size()<<endl;
 for(j=ans[i].size()-1;j>=0;j--)
 {
 if(j!=0) cout<<ans[i][j]<<&quot; &quot;;
 else cout<<ans[i][j]<<endl;
 }
 }
 cout<<endl;
 for(i=1;i<=n;i++) {
 edges[i].clear();
 ans[i].clear();
 }
}
return 0;

}

E. Replace With the Previous, Minimize The question ： Given a string , Ask in execution k What is the string with the smallest dictionary order after this operation ？ Definition of one operation ： For letters in any string s, Set all in the string to s Convert the letters of to s-1 namely b Can be converted to a,c Can be converted to b,……,z Can be converted to y.

Ideas ： The first requirement is the smallest dictionary order , So it must be as small as possible from the first place , Then I'll just run violently , See how many letters the first can be reduced to , And then mark it , It means that you can walk all the way after meeting these , So it's a very simple greed .

​
原网站

版权声明
本文为[InfoQ]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/199/202207152143469683.html

边栏推荐

猜你喜欢

随机推荐