Codeforces Round #527 (Div. 3) A-D2 + F

cf-1092-A

题意 给你t组 每组一个 长度 种类

输出组成长度 还是比较好组成的

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <cmath>
#include <vector>
#include <set>
#include <sstream>
#include <stack>
using namespace std;
#define dbg(x) cout<<#x<<\" = \"<< (x)<< endl
int num[35];

int main()
{
    int t;
    scanf(\"%d\",&t);
    while(t--)
    {
        memset(num,0,sizeof(num));
        int len,b,tmp = 1;
        scanf(\"%d%d\",&len,&b);
        int ans = len/b;
        len = len%b;
        while(len)
        {
            num[tmp]++;
            tmp++;
            len--;
        }
        for(int i = 1;i<=b;++i)
        {
            num[i]+=ans;
            while(num[i])
            {
                printf(\"%c\",\'a\'+i-1);
                num[i]--;
            }
        }
        printf(\"\\n\");
    }
    return 0;
}

cf-1092-B

题意 给你n个人 能力相同的组成一队 组成n/2个队

排序一下 加减就可以了

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <cmath>
#include <vector>
#include <set>
#include <sstream>
#include <stack>
using namespace std;
#define dbg(x) cout<<#x<<\" = \"<< (x)<< endl
int num[1025],arr[1025];
stack<int >tmp;
int main()
{
    int n,cnt = 0;
    long long sum = 0;
    scanf(\"%d\",&n);
    for(int i = 1;i<=n;++i)
        scanf(\"%d\",&arr[i]);
    sort(arr+1,arr+1+n);
    for(int i = 1;i<=n;++i)
    {
        cnt++;
        if(cnt%2==0) sum+=arr[i];
        else sum-=arr[i];
    }
    printf(\"%lld\\n\",sum);
    return 0;
}

cf-1092-C

题意 给你n长度 n-1个前缀 n-1个后缀

我们用string substr匹配就行 一开始要确定哪个n-1的是前缀 哪个是后缀

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <cmath>
#include <vector>
#include <set>
#include <sstream>
#include <stack>
using namespace std;
#define dbg(x) ;
//cout<<#x<<\" = \"<< (x)<< endl
char ans_[10025];
string str[10025];
vector < int > ans[10025];
vector<string > tmp[10025];
int main()
{
    int n,flag = 0;
    string str1,str2,str1_,str2_;
    cin >> n;
    for(int i =1;i<=2*n-2;++i)
    {
        cin >>str[i];
        int len = str[i].length();
        ans[len].push_back(i);
        tmp[len].push_back(str[i]);
    }
    if(n==2)
    {
        cout << \"S\" <<\"P\" << endl;
        return 0;
    }
    str1 = tmp[n-1][0];
    str2 = tmp[n-1][1];
    str1_ = tmp[n-2][0];
    str2_ = tmp[n-2][1];
    dbg(str1);
    dbg(str2);
    dbg(str1_);
    dbg(str2_);
    if(str1.substr(0,n-2)==str1_&&str2.substr(1,n-2)==str2_)
    {
        ans_[ans[n-1][0]-1] = \'P\';
        ans_[ans[n-1][1]-1] = \'S\';
        ans_[ans[n-2][0]-1] = \'P\';
        ans_[ans[n-2][1]-1] = \'S\';
        str1 = str1_;
        str2 = str2_;
    }
    else if(str1.substr(0,n-2)==str2_&&str2.substr(1,n-2)==str1_)
    {
        ans_[ans[n-1][0]-1] = \'P\';
        ans_[ans[n-1][1]-1] = \'S\';
        ans_[ans[n-2][0]-1] = \'S\';
        ans_[ans[n-2][1]-1] = \'P\';
        str1 = str2_;
        str2 = str1_;
    }
    else if(str1.substr(1,n-2)==str1_&&str2.substr(0,n-2)==str2_)
    {
        ans_[ans[n-1][0]-1] = \'S\';
        ans_[ans[n-1][1]-1] = \'P\';
        ans_[ans[n-2][0]-1] = \'S\';
        ans_[ans[n-2][1]-1] = \'P\';
        str1 = str2_;
        str2 = str1_;
    }
    else if(str1.substr(1,n-2)==str2_&&str2.substr(0,n-2)==str1_)
    {
        ans_[ans[n-1][0]-1] = \'S\';
        ans_[ans[n-1][1]-1] = \'P\';
        ans_[ans[n-2][0]-1] = \'P\';
        ans_[ans[n-2][1]-1] = \'S\';
        str1 = str1_;
        str2 = str2_;
    }
    dbg(str1);
    dbg(str2);
    for(int i = n-3;i>=1;i--)
    {
        str1_ = tmp[i][0];
        str2_ = tmp[i][1];
        dbg(str1_);
        dbg(str2_);

        if(str1.substr(0,i)==str1_&&str2.substr(1,i)==str2_)
        {
        //cout << \"ok\" << endl;
        ans_[ans[i][0]-1] = \'P\';
        ans_[ans[i][1]-1] = \'S\';
        str1 = str1_;
        str2 = str2_;
        }
        else if(str1.substr(0,i)==str2_&&str2.substr(1,i)==str1_)
        {
        //cout << \"OK \" << endl;
        ans_[ans[i][0]-1] = \'S\';
        ans_[ans[i][1]-1] = \'P\';
        str1 = str2_;
        str2 = str1_;
        }
        dbg(str1);
        dbg(str2);
    }
    dbg(n);
    ans_[2*n] = \'\\0\';
    cout << ans_ << endl;
    return 0;
}

 cf-1092-d

d1 可以竖着放 建议先看D2 只要栈中栈顶元素 和数组元素是偶数 就可以减 然后和d2差不多 只要存在2个以及以上的元素 就是NO

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <cmath>
#include <vector>
#include <set>
#include <sstream>
#include <stack>
using namespace std;
#define dbg(x) ;
//cout<<#x<<\" = \"<< (x)<< endl
const int MAX_N = 300025;
stack <int > st;
int arr[MAX_N];
int main()
{
    int n,maxx=-1;
    bool flag = true;
    scanf(\"%d\",&n);
    for(int i = 1;i<=n;++i) scanf(\"%d\",&arr[i]);
    for(int i = 1;i<=n;++i)
    {
        if(i==1)
        {
            st.push(arr[i]);
        }
        else
        {
            dbg(arr[i]);
            dbg(st.top());
            if(st.empty())
                {
                    st.push(arr[i]);
                    continue;
                }
            else if((abs(arr[i]-st.top()))%2==0)
            {
                st.pop();
            }
            else
            {
                    st.push(arr[i]);
            }
        }
    }
    dbg(st.size());
    dbg(st.top());
    if(st.size()>1) flag = false;
    if(flag) puts(\"YES\");
    else puts(\"NO\");
    return 0;
}

cf-1092-d2

题意 俄罗斯方块 不过只能横着放 我们怎么做呢

我们知道 如果你是一个倒 V 肯定不行 所以我们维护一个单调递减的栈

并且我们要知道 由于不能竖着放 所以只有栈为空 或者栈只剩一个 且剩下的这个要满足小于maxx

上面这句话观察 样例

5

4 3 3 4 1
和 

5

4 3 3 4 5

的区别

maxx是什么呢 是出栈的元素里最大的 相同就出栈  如果栈元素个数大于等于2 肯定是NO

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <cmath>
#include <vector>
#include <set>
#include <sstream>
#include <stack>
using namespace std;
#define dbg(x) cout<<#x<<\" = \"<< (x)<< endl
const int MAX_N = 300025;
stack <int > st;
int arr[MAX_N];
int main()
{
    int n,maxx=-1;
    bool flag = true;
    scanf(\"%d\",&n);
    for(int i = 1;i<=n;++i) scanf(\"%d\",&arr[i]);
    for(int i = 1;i<=n;++i)
    {
        if(i==1)
        {
            st.push(arr[i]);
        }
        else
        {
            if(st.empty())
                {
                    st.push(arr[i]);
                    continue;
                }
            if(st.top()==arr[i])
            {
                maxx  =max(maxx,st.top());
                st.pop();
            }
            else
            {
                if(arr[i]>st.top())
                {
                    flag = false;
                    break;
                }
                else
                {
                    st.push(arr[i]);

                }
            }
        }
    }
    //cout << \"maxx \" << maxx << endl;
    if(!st.empty()&&st.top()<maxx) flag = false;
    if(st.size()>1) flag = false;
    if(flag) puts(\"YES\");
    else puts(\"NO\");
    return 0;
}

cf-1092-F

题意 给你一棵树 定义一个点的ans为其他点到这个点的边数乘上点权之和

sum 是这个点为儿子的点权和

val是这个点儿子对这个点的贡献

ans是所有点的答案

我们第一遍dfs预处理sum和val

在第二遍dfs的时候 我们要知道 ans根就是val根 然后以5为例 等于右边的贡献 加上左边的贡献

右边的贡献就是val[5] 左边的贡献是 5 的祖先的答案 减去 val[5] 减去sum[5] 加上一条连着5的新边的贡献 就是Sum-sum[5]

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <cmath>
#include <vector>
#include <set>
#include <sstream>
#include <stack>
using namespace std;
#define dbg(x) cout<<#x<<\" = \"<< (x)<< endl
const int MAX_N = 200025;
long long sum[MAX_N],val[MAX_N],ans[MAX_N],ans_,Sum;
int p[MAX_N],eid,cnt[MAX_N];
bool vis[MAX_N];
void init()
{
    memset(vis,false,sizeof(vis));
    memset(p,-1,sizeof(p));
    eid = 0;
}
struct edge
{
    int v,next;
}e[MAX_N<<1];
void add(int u,int v)
{
    e[eid].v = v;
    e[eid].next = p[u];
    p[u] = eid++;
}

void dfs1(int s)
{
    vis[s] = true;
    bool leaf = true;
    for(int i = p[s];i+1;i=e[i].next)
    {
        int v = e[i].v;
        if(!vis[v]) dfs1(v),leaf = false,vis[v] = true;
        sum[s] += cnt[v];
        val[s] += val[v]+sum[s];
        if(leaf) sum[s] = cnt[s],val[s] = 0;
    }
}
void dfs2(int s)
{
    ans[s] = val[s];
    vis[s] = true;
    bool leaf = true;
    for(int i = p[s];i+1;i=e[i].next)
    {
        int v = e[i].v;
        if(!vis[v])
        {
            dfs2(v);
            leaf = false;
            vis[v] = true;
            ans[v] = ans[s] - 2*sum[v] + Sum;
            ans_ = max(ans[v],ans_);
        }
    }
}
int main()
{
    int n,a,b;
    Sum = 0;
    init();
    scanf(\"%d\",&n); for(int i = 1;i<=n;++i) scanf(\"%d\",&cnt[i]),Sum+=cnt[i];
    for(int i = 1;i<n;++i)
    {
        scanf(\"%d%d\",&a,&b);
        add(a,b),add(b,a);
    }
    dfs1(1);
    memset(vis,false,sizeof(vis));
    dfs2(1);
    printf(\"%lld\\n\",ans_);
    return 0;
}