Codeforces Round #787 (Div. 3)

校赛前临时补题之codeforces

马上要校赛了，太久没敲题，怕校赛被暴打，于是乎写了一套div3，发现很多不会，然后写一下题解温顾一下，顺一顺思路。

#include

#define bug(a) cout<<"bug1 : "<>t;
    while(t--)
    {
        string s1;
        cin>>s1;
        sort(s1.begin(),s1.end());
        cout< 
B. Minor Reduction 
题意： 
在一个不包含前导0的数字字符串中，可以进行一次操作，将他们的数字和相加，然后替换两个数字就行。
 
思路： 
乍一看感觉还挺难的，但是操作只有一次，开始思考如何替换，首先如果两个数字加完之后可能获得的值在【0,18】中，而其中加完之后和有存在>=10，那么肯定是优于加完之后只有一位数，再仔细观察加完之后如果增加两个数字的话，其实并没有改变它本来的字符数量，而且两个数字最少也是大于等于1的，而新增的一定是1x，肯定是变小了，所以从后往前找，第一个能到两个数字就是最优的，但是如果没有两个数字的情况，就把第一个求和应该是最优的，可以变大
 
#include

#define bug(a) cout<<"bug1 : "<>t;
    while(t--)
    {
        string s1,ans="",s2="";
        cin>>s1;
        int n=s1.length(),flag=0;
        if(n==1){
            cout<0;i--)
        {
            int d1=s1[i]-'0',d2=s1[i-1]-'0';
            if(d1+d2>=10)
            {
                ans="";
                if(i-1>0) for(j=0;j 
C. Detective Task 
题意： 
有一幅画,个人看,中间某一时刻被某一个人偷走了。问每个人他看的时候画还在不在,答案可能是有 (1) / 无 (0) / 忘记了 (?)。好人会说实话/忘记了,偷走的人会随机选一个回答。求最多会有多少个人可能是小偷
 
思路： 
一个比较好想的思路就是思考如果当前位置是小偷的话，那么它之前是一定不能出现0的（空），并且它之后也一定不能出现1（有），所以不断的维护这段区间就行,可以双指针，也可以前缀和，我自己用的前缀和比较好想但是复杂了点。
 
#include

#define bug(a) cout<<"bug1 : "<>t;
    while(t--)
    {
        //memset(s1,'',sizeof s1);
        string s2,s1=" ";
        cin>>s2;
        s1+=s2;
//        cout< 
D. Vertical Paths 
题意： 
给定一个数组p[N],其中p[i]为i的父节点，1.求得不重合，且覆盖所有结点的最小路径数，2,并分别输出该路径，从父节点到子节点的顺序输出该路径。
 
思路： 
覆盖所有节点的最小路径数，并且必须要满足从上层到下层这种顺序，不难想到，每个叶子节点都可以作为答案的端点，然后再想其实和dfs就非常像了，从起点开始dfs搜到底，也就是搜到第一个叶子结点，然后对这一条路直接染色，这种情况就是最优的。考的就是实现问题。
 
#include

using namespace std;
#define endl 'n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn=2e5+100;
vectoredges[maxn],ans[maxn];
int tot;
int ys[maxn];
int dfs(int pre,int idx)
{
	int k=0;
	for(int i=0;i>t;
	while(t--)
	{
		tot=0;
		cin>>n;
		int rt=0;
		for(i=1;i<=n;i++)
		{
			cin>>u;
			if(u==i){
                 rt=i;
                 continue;
			}
			edges[u].push_back(i);

		}
		dfs(-1,rt);
		cout< 
 
 
E. Replace With the Previous, Minimize 
题意： 
给定一个字符串，问在执行k次操作后字典序最小的字符串是什么？
 一次操作的定义：对于任意一个字符串中的字母s，将字符串内所有为s的字母转换为s-1
 即b可以转换为a，c可以转换为b，……，z可以转换为y。
 
思路： 
首先要求的是字典序最小的，所以肯定是从首位开始尽可能小，那么我就直接暴力跑，看首位能减低到字母几，然后标记一下，表示之后遇到这些走过的路都可以走，所以是个很简单的贪心。
 
#include

using namespace std;
#define endl 'n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

bool vis[27];
int main()
{
    IOS
    int n,i,j,t,k;
    string s1;
    cin>>t;
    while(t--)
    {
        memset(vis,false,sizeof vis);
        cin>>n>>k>>s1;
        vis[0]=1;
        for(i=0;i=0;j--)
            {
                if(vis[j]==1) continue;
                else {
                    if(k>0){
                        k--;
                        vis[j]=1;
                    }
                    else {
                        break;
                    }
                }
            }
            s1[i]='a'+max(0,j);
        }
        cout<