Codeforces #263 div2 解题报告

时间：2024-01-06 16:38:14

比赛链接：http://codeforces.com/contest/462

这次比赛的时候，刚刚注冊的时候非常想好好的做一下，可是网上喝了个小酒之后。也就迷迷糊糊地看了题目，做了几题。一觉醒来发现rating掉了非常多，那个心痛啊！

只是。后来认真的读了题目，发现这次的div2并非非常难！

官方题解：http://codeforces.com/blog/entry/13568

A. Appleman and Easy Task

解析：

        一个水题，推断每一个细胞周围是否都是有偶数个相邻细胞。

 

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <stack>

using namespace std;

#define Lowbit(x) ((x)&(-(x)))

#define ll long long

#define mp make_pair

#define ff first

#define ss second

#define pb push_back

const int MAXN=1005;

ll a[30];

int n;

char str[105][105];

bool check(int i, int j){

    int tmp = 0;

    if(i>0&&str[i-1][j]=='o')

        ++tmp;

    if(i<n-1&&str[i+1][j]=='o')

        ++tmp;

    if(j>0&&str[i][j-1]=='o')

        ++tmp;

    if(j<n-1&&str[i][j+1]=='o')

        ++tmp;

    if(tmp%2)

        return false;

    return true;

}

int main(){

    #ifdef LOCAL

        freopen("1.in", "r",stdin);

        //freopen("1.out", "w", stdout);

    #endif

    int i,j;

    scanf("%d", &n);

    for(i=0; i<n; ++i){

        scanf("%s", str[i]);

    }

    bool flag = true;

    for(i=0; i<n&&flag; ++i){

        for(j=0; j<n&&flag; ++j){

            if(!check(i,j)){

                flag = false;

                break;

            }

        }

    }

    printf("%s", flag?

"YES":"NO");

    return 0;

}

B. Appleman and Card Game

解析：

       
两个水题，贪心问题，直接统计每一个字母出现的次数。然后sort一下，每次取最大的。

       可是，这里要注意一下数据范围。结果用long long表示。在计算过程中须要强制类型转换。尤其k在计算中一定要是long long型



代码：

//#define LOCAL

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <stack>

using namespace std;

#define Lowbit(x) ((x)&(-(x)))

#define ll long long

#define mp make_pair

#define ff first

#define ss second

#define pb push_back

const int MAXN=1005;

ll a[30];

char str[100010];

int main(){

    #ifdef LOCAL

        freopen("1.in", "r",stdin);

        //freopen("1.out", "w", stdout);

    #endif

    int n;

    ll k;

    scanf("%d%I64d", &n, &k);

    scanf("%s", str);

    int len = strlen(str);

    memset(a, 0, sizeof(a));

    for(int i=0; i<n; ++i){

        a[str[i]-'A']++;

    }

    sort(a,a+26);

    ll sum = 0;

    for(int i=25; i>=0&&k>0; --i){

        if(k>=a[i]){

            sum += a[i]*a[i];

            k -= a[i];

        }

        else{

            sum += k*k;

            k-=k;

        }

    }

    printf("%I64d\n", sum);

    return 0;

}

C. Appleman and Toastman

解析：

       三个水题，贪心嘛，每次将最小的那个数字单独拆开。能够用sort也能够用priority_queue。

 

代码：

//#define LOCAL

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <stack>

using namespace std;

#define Lowbit(x) ((x)&(-(x)))

#define ll long long

#define mp make_pair

#define ff first

#define ss second

#define pb push_back

const int MAXN=1005;

int main(){

    #ifdef LOCAL

        freopen("1.in", "r",stdin);

        //freopen("1.out", "w", stdout);

    #endif

    int i,n;

    ll sum = 0;

    ll score = 0,tmp;

    priority_queue< ll, vector<ll>, greater<ll> >pq;

    scanf("%d", &n);

    for(i=0; i<n; ++i){

        scanf("%I64d", &tmp);

        sum += tmp;

        pq.push(tmp);

    }

    score = sum;

    while(pq.size()>1){

        score += sum;

        tmp = pq.top();

        pq.pop();

        sum -= tmp;

    }

    printf("%I64d", score);

    return 0;

}

D. Appleman and Tree

解析：

       这是一道DP问题，用到树形DP；

       题意：给了一棵树以及每一个节点的颜色。1代表黑。0代表白，要求的是。假设将这棵树拆成k棵树，使得每棵树恰好有一个黑色节点

       

       dp[v][0 ]表示以v为根没有黑节点子树的数目

       dp[v][1] 表示以v为根有黑节点子树的数目

 

       说实话。我遇到DP还是比較犯怵的，所以在比赛的时候发现这是道DP问题，也就懒得在动用喝醉的大脑了。直接GG了。

 

代码：

//#define LOCAL

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <stack>

using namespace std;

#define Lowbit(x) ((x)&(-(x)))

#define ll long long

#define mp make_pair

#define ff first

#define ss second

#define pb push_back

#define mod 1000000007

const int MAXN=100010;

ll dp[MAXN][2];

vector<int> x[MAXN];

int c[MAXN];

void dfs(int v,int p){

    dp[v][0] = 1;

    dp[v][1] = 0;

    for(int i=0; i<x[v].size(); ++i){

        int u = x[v][i];

        if(u == p)    continue;

        dfs(u,v);

        dp[v][1] = ((dp[v][1]*dp[u][0])%mod+(dp[v][0]*dp[u][1])%mod)%mod;

        dp[v][0] = (dp[v][0]*dp[u][0])%mod;

    }

    if(c[v])    dp[v][1] = dp[v][0];

    else    dp[v][0] =(dp[v][0]+dp[v][1])%mod;

}

int main(){

    #ifdef LOCAL

        freopen("1.in", "r",stdin);

        //freopen("1.out", "w", stdout);

    #endif

    int tmp;

    int n;

    scanf("%d", &n);

    for(int i=1; i<n; ++i){

        scanf("%d", &tmp);

        x[i].pb(tmp);

        x[tmp].pb(i);

    }

    for(int i=0; i<n; ++i){

        scanf("%d", &c[i]);

    }

    dfs(0,-1);

    printf("%I64d", dp[0][1]);

    return 0;

}

E. Appleman and a Sheet of Paper

解析：

       说实话这个题目根本不须要怎么多读，直接看例子的分析就知道题意了。就是简单的叠纸条，然后查询区间的纸条总厚度

        这里能够用BIT（树状数组）。也能够用线段树。

       这里的代码，我用的是树状数组。

       本题解答的一个巧妙的地方就是，假设左边叠的长。那么我们能够反过来把右边的叠过来，可是纸条的左右方向要转向，所以这里用了一个flag标记左右的方向。其它部分就和普通的树状数组是一样的做法。

代码：

//#define LOCAL

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <stack>

using namespace std;

#define Lowbit(x) ((x)&(-(x)))

//#define ll long long

#define mp make_pair

#define ff first

#define ss second

#define pb push_back

#define mod 1000000007

const int MAXN=100010;

int c[MAXN], s[MAXN],n;

void ADD(int p, int val){

    s[p] += val;

    while(p<=n){

        c[p] += val;

        p += Lowbit(p);

    }

}

int getsum(int p){

    int sum = 0;

    while(p>0){

        sum += c[p];

        p -= Lowbit(p);

    }

    return sum;

}

int main(){

    #ifdef LOCAL

        freopen("1.in", "r",stdin);

        //freopen("1.out", "w", stdout);

    #endif

    int i, p;

    scanf("%d%d", &n, &p);

    memset(c, 0, sizeof(c));

    memset(s, 0, sizeof(s));

    for(i=1; i<=n; ++i)

        ADD(i, 1);

    int l=1, r=n;

    int x,y,z;

    int flag = 0;

    for(int k=0; k<p; ++k){

        scanf("%d", &x);

        if(x == 1){

            scanf("%d", &y);

            int fg = ((y*2)>(r-l+1));

            int mid;

            if(flag)    mid = r-y;

            else     mid = l+y-1;

            int ll = mid-l+1; int rr = r-mid;

            if(ll<=rr){

                for(i=l; i<=mid; ++i)

                    ADD(2*mid+1-i, s[i]);

                l = mid+1;

            }

            else{

                for(i=mid+1; i<=r; ++i)

                    ADD(2*mid+1-i, s[i]);

                r = mid;

            }

            flag ^= fg;     //标记。假设左边长。那么就向左叠，而且从右向左读；

                            //假设左边短，那么就向右叠，而且从左向右读。

        }

        else{

            scanf("%d%d", &y,&z);

            if(flag)    printf("%d\n", getsum(r-y)-getsum(r-z));

            else    printf("%d\n", getsum(l+z-1)-getsum(l+y-1));

        }

    }

    return 0;

}

相关文章