CodeforcesRound#798(Div.2)A-D（未完成）-创新互联

A 题面

在这里插入图片描述

创新互联建站网络公司拥有十余年的成都网站开发建设经验，超过千家客户的共同信赖。提供成都网站制作、成都网站建设、网站开发、网站定制、友情链接、建网站、网站搭建、成都响应式网站建设公司、网页设计师打造企业风格，提供周到的售前咨询和贴心的售后服务样例输入

3
6 4 2
aaaaaa
bbbb
5 9 3
caaca
bedededeb
7 7 1
noskill
wxhtzdy

样例输出

aabaabaa
aaabbcc
dihktlwlxnyoz

样例解释

在这里插入图片描述

官方题解

在这里插入图片描述

官方代码

#includeusing namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
 
    int t; cin>>t;
    while (t--)
    {
        int n,m,k; cin>>n>>m>>k;
        string a,b,c; cin>>a>>b;
        sort(a.begin(),a.end(),greater());
        sort(b.begin(),b.end(),greater());
 
        int ak=0,bk=0;
        while (!a.empty() && !b.empty())
        {
            bool gde=b.back()

题意给定a，b两个字符串，长度分别为n，m，不会有某个字符既在a中又在b中。同时给你一个整数k。你可以每次在a或b中取出一个字母放入c中，直到其中至少一个字符串为空。要求不能连续在同一个字符串中连续选取k个字母。输出所有选择中，字典序最小的结果。
题解为了使字典序最小，首先将a，b内部进行排序，这样每次我们可以直接取出a，b各自最小的字符，将他们进行比较，将小的那一个字符取出放入c中即可。注意，如果在某个字符串中已经连续取k个了，就需要换一个字符串取。那就统计一下目前位置已经连续在哪个字符串中取了几次就可以了。所以在a中取字符的条件是：a剩下的最小字符比b的小，并且没有在a中连续取k次。否则就在b中取。（注意a，b两字符串之间没有相同元素，内部可能有）代码 
C++,
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        +
       
       
        m
       
       
        )
       
      
      
       O(n+m)
      
     
    O(n+m)#includeusing namespace std;

#define int long long

signed main()
{
    int T;
    cin >>T;
    
    while(T --)
    {
        int n, m, k;
        cin >>n >>m >>k;
        
        string a, b;
        cin >>a >>b;
        
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        
        int i = 0, j = 0, cnt = 0, t = -1;
        
        string c;
        
        while(i< n && j< m)
        {
            if(a[i]< b[j] && !(t == 0 && cnt == k) || a[i] >b[j] && t == 1 && cnt == k)
            {
                if(t == 1) cnt = 1;
                else cnt ++;
                t = 0;
                c += a[i ++];
            }
            else
            {
                if(t == 0) cnt = 1;
                else cnt ++;
                t = 1;
                c += b[j ++];
            }
        }
        
        cout<< c<< endl;
    }
}pypy3,
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        +
       
       
        m
       
       
        )
       
      
      
       O(n+m)
      
     
    O(n+m)T = int(input())

for u in range(T):
    
    n, m, k = map(int, input().split())
    a = input()
    b = input()
    
    a = ''.join(sorted(a))
    b = ''.join(sorted(b))
    
    c = ""
    cnta = cntb = i = j = 0
    
    while i< n and j< m:
        if cnta< k and a[i]< b[j] or cntb == k:
            cnta += 1
            cntb = 0
            c += a[i]
            i += 1
        else:
            cntb += 1
            cnta = 0
            c += b[j]
            j += 1
            
    print(c)B 
题面
样例输入4
3
1 2 3
5
2 3 4 5 1
4
2 3 1 4
1
1
样例输出2 3 1
1 2 3 4 5
1 2 4 3
-1
样例解释## 官方题解
官方代码 
C++ Code (Main solution)#includeusing namespace std;
 
bool took[1005];
int p[1005];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
 
    int t; cin>>t;
    while (t--)
    {
        int n; cin>>n;
        for (int i=1;i<=n;i++) cin>>p[i];
        for (int i=1;i<=n;i++) took[i]=0;
        
        if (n==1)
        {
            cout<<"-1\n";
            continue;
        }
 
        for (int i=1;i<=n-2;i++)
        {
            int k=1;
            while (took[k] || k==p[i]) ++k;
            cout<C++ Code (O(n) solution)#includeusing namespace std;

int t,n,A[1010],B[1010];

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&A[i]);
            B[i] = i;
        }
        if(n==1)
        {
            printf("-1\n");
            continue;
        }
        for(int i=1; i
题意给定一个排列A，请你给出一个新的排列B，使A，B任何位置不相等，也就是对于任何i，A[i]!=B[i]。要求输出字典序最小的B。
题解1这题n很小，可以用
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         2
        
       
       
        )
       
      
      
       O(n^2)
      
     
    O(n2)复杂度做。如果只有一个数字，那么A[1]==B[1]，此题无解，否则有解。对于前n-2个数，只需要选择该位置能选择的最小的数：对于B[i]，未在B[1]~B[i-1]出现且不等于A[i]的数中最小的一个，这样的做法可以让前n-2个数是字典序最小的。最后两个数也一定可以找到字典序最小的排列，即尝试先小后大，如果会导致A[i]==B[i]，那么先大后小即可。代码1 
C++,
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         2
        
       
       
        )
       
      
      
       O(n^2)
      
     
    O(n2)#includeusing namespace std;

#define int long long

signed main()
{
    int T;
    cin >>T;
    
    while(T --)
    {
        int n;
        cin >>n;
        
        vectora(n + 1), b(1, 0), st(n + 1, 0);
        for(int i = 1; i<= n; i ++)
            cin >>a[i];
        
        if(n == 1)
        {
            cout<< -1<< endl;
            continue;
        }
        
        for(int i = 1; i<= n - 2; i ++)
        {
            for(int j = 1; j<= n; j ++)
                if(!st[j] && j != a[i])
                {
                    b.push_back(j);
                    st[j] = 1;
                    break;
                }
        }
        
        for(int i = 1; i<= n; i ++)
            if(!st[i])
                b.push_back(i);
        
        if(a[n - 1] == b[n - 1] || a[n] == b[n])
            swap(b[n - 1], b[n]);
        
        for(int i = 1; i<= n; i ++)
            cout<< b[i]<< ' ';
        
        cout<< endl;
    }
}
题解2当n==1时，无解，否则有解。因此，在前n-2个数选取完毕后，最后2个数必定有解。首先将b赋值为1：n，此为字典序最小的排列。然后考虑a，k从1到n-2交换，假设前k-1个数已经为字典序最小，而a[k]==b[k]，只需要将b[k]与b[k+1]交换，则可以保证前k个数字典序最小，证明：因为之前所有交换都发生在b[1~k]之间，所以b[k+1~n]仍然有序，b[k]<=k<=min(b[k+1~n])，所以在min(b[k~n])=b[k]，若要保证a[k]!=b[k]，则b[k]需要与后面的数交换，为使字典序最小，则交换后面最小的数，即b[k+1]。如此则保证了前k个数字典序最小。而最后两个数只需要保证不与a对应位置相等即可。代码2 
pypy3,
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)T = int(input())

for _ in range(T):
    
    n = int(input())
    a = list(map(int, input().split()))
    b = sorted(a)
    
    if n == 1:
        print(-1)
        continue
    
    for i in range(n - 1):
        if a[i] == b[i]:
            b[i], b[i + 1] = b[i + 1], b[i]
        
    if a[-1] == b[-1]:
        b[-1], b[-2] = b[-2], b[-1]
    
    print(" ".join(map(str, b)))C 
题面
样例输入4
2
1 2
4
1 2
2 3
2 4
7
1 2
1 5
2 3
2 4
5 6
5 7
15
1 2
2 3
3 4
4 5
4 6
3 7
2 8
1 9
9 10
9 11
10 12
10 13
11 14
11 15
样例输出0
2
2
10
样例解释
官方题解
官方代码#includeusing namespace std;
 
vector>g(300005);
int ch[300005],dp[300005];
 
void dfs(int p, int q)
{
    ch[p]=1,dp[p]=0; int s=0;
    for (auto it : g[p]) if (it!=q)
    {
        dfs(it,p); s+=dp[it];
        ch[p]+=ch[it];
    }
    for (auto it : g[p]) if (it!=q)
    {
        dp[p]=max(dp[p],s-dp[it]+ch[it]-1);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
 
    int t; cin>>t;
    while (t--)
    {
        int n; cin>>n;
        for (int i=1;i<=n;i++) g[i].clear();
        for (int i=1;i>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
 
        dfs(1,0);
        cout<
题意给你一棵树，根节点为1，根节点的度不大于2，其他节点的度不大于3。首先根节点被感染了，并且每次迭代，感染的节点会像相邻节点扩散一个单位。在每次迭代前，你可以删掉一个节点，那么就不能通过这个节点扩散了，那么可能可以救下一些节点，问你最多能救下多少个节点。
题解总节点数=救下的节点数+删除的节点数+感染的节点数。
这是一棵有根树。
如果在感染t前删掉t节点，则能救下t节点的所有子孙节点。
我们考虑感染t：
a. 如果t没有孩子节点，则删不删t没有区别。
b. 如果t有一个孩子节点，则删t能救下最多节点。
c. 如果t有两个孩子节点，则必定删除一个感染一个，选择能救下最多的方式。
因为每次可以删除一个节点，可以保证每次只感染一个节点。
我们对t定义两个变量：如果感染t，能救下的节点数；如果删除t，能救下的节点数。
答案为：如果感染1，能救下的节点数。代码 
C++,
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)#includeusing namespace std;

#define int long long

vectorh[300010], st;

pairdfs(int x)
{
    vector>children;
    for(auto & y : h[x])
        if(!st[y])
        {
            st[y] = 1;
            children.push_back(dfs(y));
        }
    
    if(!children.size()) return {0, 0};
    else if(children.size() == 1) return{children[0].second, children[0].second + 1};
    else return {max(children[0].first + children[1].second, children[0].second + children[1].first), 
                2 + children[0].second + children[1].second};
}

signed main()
{
    int T;
    cin >>T;
    
    while(T --)
    {
        int n;
        cin >>n;
        
        st = vector(n + 1, 0);
        for(int i = 1; i<= n; i ++)
            h[i] = vector(0);
        
        for(int i = 1; i< n; i ++)
        {
            int u, v;
            cin >>u >>v;
            h[u].push_back(v);
            h[v].push_back(u);
        }
        
        st[1] = 1;
        
        cout<< dfs(1).first<< endl;
    }
}pypy3,
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)
                
                
     你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
            

            名称栏目：CodeforcesRound#798(Div.2)A-D（未完成）-创新互联            

            网站路径：http://cqcxhl.cn/article/djodpj.html


    
        其他资讯
        
            
                    sap系统sa的简单介绍
                

                    mysql服务器安全设置 mysql 安全设置
                

                    怎么判断mysql存在 mysql怎么判断是否存在某个表
                

                    什么是帝国cms字段 帝国cms模板教程
                

                    php做大数据开发 php做大数据分析

重庆分公司，新征程启航

CodeforcesRound#798(Div.2)A-D（未完成）-创新互联

其他资讯