首页 > 代码库 > Codeforces Round #263 (Div. 2) A-D

Codeforces Round #263 (Div. 2) A-D

2024-07-19 19:02:26   214人阅读

就是一次手速场啊，1000+个三道题的啊。还有就是一定要注意数据范围，好多人被查掉了。

A，再一次被样例坑了一下，注意是每个点相邻的o的个数是否都为偶数个。

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-12
///#define M 1000100
///#define LL __int64
#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)?0:x)

using namespace std;

const int maxn = 110;

char str[maxn][maxn];
int dx[] = {1, 0, 0, -1};
int dy[] = {0, 1, -1, 0};
int main()
{
    int n;
    while(~scanf("%d",&n))
    {

        for(int i = 0; i < n; i++) cin >>str[i];
        if(n == 1)
        {
            cout<<"YES"<<endl;
            continue;
        }
        int flag = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                int cnt = 0;
                for(int k = 0; k < 4; k++)
                {
                    int x = i+dx[k];
                    int y = j+dy[k];
                    if(x < 0 || y < 0 || x >= n || y >= n)
                    {
                        continue;
                    }
                    if(str[x][y] == 'o') cnt++;
                }
                if(cnt%2)
                {
                    flag = 1;
                    break;
                }
            }
            if(flag) break;
        }
        if(flag) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}
B。根据第一组样例我们就可以得到这题是一个贪心的策略尽量选最多的啊。哈希一下每种字母有多少个。


#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-12
///#define M 1000100
///#define LL __int64
#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)?0:x)

using namespace std;

const int maxn = 100010;

LL vis[100];

char str[maxn];

int main()
{
    LL n;
    LL k;
    while(cin >>n>>k)
    {
        cin >>str;
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n; i++)
        {
            vis[str[i]-'A']++;
        }
        sort(vis, vis+26);
        LL ans = 0LL;
        for(int i = 25; i >= 0; i--)
        {
            if(vis[i] <= k)
            {
                ans += vis[i]*vis[i];
                k -= vis[i];
            }
            else
            {
                ans += k*k;
                break;
            }
        }
        cout<<ans<<endl;
    }
}

C。贪心的思想，每次去掉最小的，可以得到一个小的规律。sort一下在求一遍就ok了啊。

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-12
///#define M 1000100
///#define LL __int64
#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)?0:x)

using namespace std;

const int maxn = 500010;

LL sum[maxn];
LL num[maxn];
LL cnt[maxn];

int main()
{
    LL n;
    while(cin >>n)
    {
        for(int i = 0; i < n; i++)
            scanf("%I64d",&num[i]);
        sort(num, num+n);
        LL ans = 0LL;
        for(LL i = 0LL; i < n-1; i++)
            ans += (i+2)*num[i];
        ans += n*num[n-1];
        cout<<ans<<endl;
    }
}

D。树形dp，dp[x][0]表示在经过这个节点对于他的上面没有出现1的情况(对于上面来说这个节点没有1，有两种情况：1，就是这个节点以及它的所有子节点没有出现过1；2，这个节点以及子节点里面出现了1，但是从这里断开了，所以对于上面来说他起到的作用就是0.)，dp[x][1]表示经过这个节点出现了1的情况。

当为叶子的时候如果这个节点为1则dp[x][1] = dp[x][0] = 1,否则dp[x][1] = 0,dp[x][0] = 1。如果它的子节点中有多个1，你就要枚举选择的是哪个1，其他的就得选择0，所以组合一下所有的情况。

D. Appleman and Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Appleman has a tree with n vertices. Some of the vertices (at least one) are colored black and other vertices are colored white.

Consider a set consisting of k (0?≤?k?<?n) edges of Appleman‘s tree. If Appleman deletes these edges from the tree, then it will split into(k?+?1) parts. Note, that each part will be a tree with colored vertices.

Now Appleman wonders, what is the number of sets splitting the tree in such a way that each resulting part will have exactly one black vertex? Find this number modulo 1000000007 (109?+?7).

Input

The first line contains an integer n (2??≤?n?≤?105) — the number of tree vertices.

The second line contains the description of the tree: n?-?1 integers p0,?p1,?...,?pn?-?2 (0?≤?pi?≤?i). Where pi means that there is an edge connecting vertex (i?+?1) of the tree and vertex pi. Consider tree vertices are numbered from 0 to n?-?1.

The third line contains the description of the colors of the vertices: n integers x0,?x1,?...,?xn?-?1 (xi is either 0 or 1). If xi is equal to 1, vertex i is colored black. Otherwise, vertex i is colored white.

Output

Output a single integer — the number of ways to split the tree modulo 1000000007 (109?+?7).

Sample test(s)
input
3
0 0
0 1 1
output
2
input
6
0 1 1 0 4
1 1 0 0 1 0
output
1
input
10
0 1 2 1 4 4 4 0 8
0 0 0 1 0 1 1 0 0 1
output
27
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-10
///#define M 1000100
///#define LL __int64
#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)?0:x)

using namespace std;

const int maxn = 100010;

#define mod 1000000007

LL dp[maxn][2];
int num[maxn];

vector<int>g[maxn];

LL q_mod(LL a,LL b,LL n)
{
    LL ret=1;
    LL tmp=a;
    while(b)
    {
        //基数存在
        if(b&0x1) ret=ret*tmp%n;
        tmp=tmp*tmp%n;
        b>>=1;
    }
    return ret;
}
LL Del(LL x,LL y,LL z)
{

    x=x*z;
    x=x%mod;
    x=x*q_mod(y,mod-2,mod);
    x=x%mod;
    return x;
}

void dfs(int x)
{
    int flag = 0;
    LL sum = 1;
    int n = g[x].size();
    for(int i = 0; i < n; i++)
    {
        int y = g[x][i];
        dfs(y);
        flag = 1;
        sum *= dp[y][0];
        sum %= mod;
    }
    if(!flag)
    {
        if(num[x])
        {
            dp[x][0] = 1;
            dp[x][1] = 1;
        }
        else
        {
            dp[x][0] = 1;
            dp[x][1] = 0;
        }
        return;
    }
    if(num[x])
    {
        dp[x][1] = sum;
        dp[x][0] = sum;
    }
    else
    {
        dp[x][0] = sum;
        dp[x][1] = 0;
        for(int i = 0; i < n; i++)
        {
            int y = g[x][i];
            dp[x][1] += Del(sum, dp[y][0], dp[y][1]);
            dp[x][1] %= mod;
        }
        dp[x][0] += dp[x][1];
        dp[x][0] %= mod;
    }
    return;
}

int main()
{
    int n;
    while(cin >>n)
    {
        int x;
        for(int i = 0; i <= n; i++) g[i].clear();
        for(int i = 1; i < n; i++)
        {
            scanf("%d",&x);
            g[x].push_back(i);
        }
        for(int i = 0; i < n; i++) scanf("%d",&num[i]);
        memset(dp, 0, sizeof(dp));
        dfs(0);
        cout<<dp[0][1]<<endl;
    }
    return 0;
}


Codeforces Round #263 (Div. 2) A-D


联系
我们