Codeforces Round #551 (Div. 2)

A. Serval and Bus

题意

给到达公交车站的时间t，n条公交路线，每条公交路线中包含第一班车到达的时间si、其后每班车之间的间隔di。
问能坐到的第一班车是在什么时候。

关键词

模拟

思路

对于每班车从si开始累加di，直到结果大于等于t时更新最小时间。
也可以不用累加，直接用公式求。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 100005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;



int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
    int n,t;
    cin>>n>>t;
    vector<int> vt;
    int ans =1;
    int time = INT_MAX;
    for (int i = 0; i < n; ++i)
    {
        int s,d;;
        cin>>s>>d;
        int j=0;
        for (j = s; ; j+=d)
        {
            if(j>=t)
            {
                if (j<time)
                {
                    ans = i+1;
                    time = j;
                }
                break;
            }
        }

    }
    cout<<ans<<endl;

#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

B. Serval and Toy Bricks

题意

给定三视图，还原出每一个水平位置上堆有多少个立方体。

关键词

模拟，贪心

思路

对于给定的三视图，以及水平坐标x，y，如果俯视图中（x，y）有方块，那么这个位置堆叠的立方体的数量就取 min{ 侧视图中该行的高度，正视图中该列的高度 }。
这样的解一定是满足给出的三视图的。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 105
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

int n,m,h;

int front[MAXN], side[MAXN], top[MAXN][MAXN];
int ans[MAXN][MAXN] ={0};
int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif

    cin>>n>>m>>h;
    for (int i = 0; i < m; ++i)
    {
        cin>>front[i];
    }
    for (int i = 0; i < n; ++i)
    {
        cin>>side[i];
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin>>top[i][j];
        }
    }

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if(top[i][j])
            {
                ans[i][j] = min(front[j], side[i]);
            }
            cout<<ans[i][j]<<(j==m-1?"\n":" ");
        }
    }



#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

C. Serval and Parenthesis Sequence

题意

给一个长度为n、由(、)、?三种字符组成的序列，要求将?替换成(或)，使最终结果满足：

  1. 整个序列是一个有效的括号序列。
  2. 序列中任何一个严格前缀（不为空且不为这个序列本身）都不是一个有效的括号序列。
    没有有效解就输出:(。

关键词

贪心

思路

对于给定的n，最后的结果中左括号和右括号个数一定都为n/2，再根据给出的序列求出左右括号还差多少个。
填充时，优先填左括号，左括号填完了再填右括号。
可以在填充时或者填充完成后检查一下其严格前缀是否为有效括号序列即可。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 300005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

int n;
int num[MAXN];

int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif

    cin >> n;
    string s;
    cin >> s;
    bool tag = 1;
    int sum = 0;
    int ll = n/2, rr=  n/2;
    for (int i = 0; i < n; ++i)
    {
        if(s[i] == '(')
        {
            sum++;
            ll--;
        }
        else if(s[i] == ')')
        {
            sum--;
            rr--;
        }
        num[i] = sum;
    }
    int l = 0;
    if (s[0] == ')' || s[n - 1] == '(')
        tag = 0;


    for (int i = 0; i < n; ++i)
    {
        char c = s[i];
        switch (c)
        {
            case '(':
                l++;
                break;
            case '?':
                if(ll>0)
                {
                    s[i] = '(';
                    ll--;
                    l++;
                } else
                {
                    s[i] =')';
                    rr--;
                    l--;
                    if(l==0&& i !=n-1)
                    {
                        tag=  0;
                    }
                }
                break;
            case ')':
                l--;
                if (l == 0 && i!=n-1)
                {
                    tag = 0;
                    break;
                }
                break;
        }
    }
    if (l!=0 || n%2==1)
        tag = 0;
    if (tag)
    {
        cout << s << endl;
    } else
    {
        cout << ":(" << endl;
    }


#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

D. Serval and Rooted Tree

题意

给定一包含n个节点棵树，其中叶子节点为k个。
对于每个非叶子节点，其值为子节点的最大值或最小值；对于每个叶子节点，为其分配[1,k]中的一个值，每个值只能分配给一个叶子节点。
求这棵树最大值为多少。

关键词

树形DP

思路

  • 假设、定义：
    ans：最终结果。
    k：叶子节点的数量。
    dp[i]：节点i的值为ans时，第i个节点为根子树中，大于等于ans节点的数量。
    j:节点 i 的子节点。
    将大于等于ans的值用1来表示。
  • 状态转移：
    i为叶子节点：dp[i]=1.
    i为max：dp[i] = min {dp[j]}。
    i为min：dp[i] = Σ {dp[j]}。
  • 最终结果：
    ans= k - dp[1] + 1 。
  • 理解与解释：
    • 对于单个叶子节点：能取得的最大值肯定为ans，所以值为1。
    • 对于max节点：先回顾dp[i]的定义：大于等于ans的节点的数量，要当前节点能取得最大值，显然，比当前节点大的值数量越少，意味着当前节点值越大，故取子节点dp[i]的最小值。
    • 对于min节点：与max节点同理，要使当前节点值最小，则是比当前节点值大的越多，意味着当前节点值越小，故求子节点dp[i]之和。
    • 最终结果：依题意：1号节点为根节点，所有值中能取到的最大值为k。dp[1]就意味着对于整棵树而言，在[1, k]中大于等于ans的有dp[i]个。
      再说直白点就是dp[1]表示ans为[1, k]中第几大的值。
      所以为k - dp[1] + 1。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 300005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

int n;
int op[MAXN];
int cnt = 0;
int dp[MAXN];
vector<int> G[MAXN];

void dfs(int u)
{
    if(G[u].empty())
    {
        cnt++;
        dp[u] = 1;
    }else
    {
        if(op[u] == 1)
        {
            dp[u] = INT_MAX;
            for (int i = 0; i < G[u].size(); ++i)
            {
                int v = G[u][i];
                dfs(v);
                dp[u] = min(dp[u], dp[v]);
            }
        } else
        {
            dp[u] = 0;
            for (int i = 0; i < G[u].size(); ++i)
            {
                int v = G[u][i];
                dfs(v);
                dp[u] += dp[v];
            }
        }

    }
}

int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
    cin>>n;
    for (int i = 1; i <= n; ++i)
    {
        cin>>op[i];
    }
    for (int i = 2; i <= n; ++i)
    {
        int t;
        cin>>t;
        G[t].pb(i);
    }
    dfs(1);
    cout<<1+cnt-dp[1]<<endl;
#ifdef FILE_IN
    fclose(stdin);
#endif
    return 0;
}

E. Serval and Snake

题意

在一个n*n的矩阵中，有一条蛇，这条蛇长度至少为2（一头一尾）。
每次可以询问一个矩形，会返回这个矩形的边界分隔了蛇的身体多少次。
要求在有限次的询问中，求出蛇的头和尾的位置。

关键词

二分

思路

这题有一个很重要的的性质：对于每次查询返回的值，如果为奇数，则表示询问的区间内恰好包含头部或尾部；如果返回的为偶数，则表示该区间内头部和尾部要么全部包含要么一个没有。

  1. 对每行每列进行询问，如果存在返回的值为奇数则保存该行或该列。显然，如果有，则这样的行或列一定成对出现，因为有一首一尾。
  2. 对于已保存的行和列，可以讨论如下三种情况：
    行和列都存在：这意味着，首尾既不在同一行，也不在同一列，是最简单的一种情况，直接组合行和列的两个值即可。假设行为x1、x2，列为y1、y2，有2组合的结果有两种(x1,y1)(x2,y2)、(x1,y2)(x2,y1)，任意查询某种情况的一个点，如果返回值为偶数，则说明这种组合错误，取另一种即可。
    只存在行：这种情况说明，头部和尾部在同一列不同行，行坐标已知，设为x1,x2，假设所在列都为y，在x1,x2中任取一行，在[1,n]的区间内二分枚举y即可。
    【二分思路】：询问(x1,1)(x1,y)这个区间，返回为奇数则说明在[1,y]内存在头部或尾部，将y向靠近左半区间，否则说明不在这个区间内，将y靠近右半区间。
    只存在列：类似于只存在行的情况，对公共行进行二分枚举即可。
对前面性质的分析解释
  1. 如果两个端点（头部和尾部）只有一个在这个区间内：要通向另一个端点，必然是有一条路出去的，蛇的身体其他部分如果也穿过这个区间，必然是“有进有出”的，贡献的次数为偶数次，可以不去讨论，只考虑连向端点的部分。
    区间内只有一个端点
  2. 如果两个端点都在这个区间内、或者都不在：那么会贡献次数的，只有第一点中提到的身体部分，次数一定为偶数，或者为0.
    2个端点都在、都不在区间内

    如此求解，询问次数为2*n+log~2~n，n最大为1000时，也不过2010，不会超过题目的限制。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 300005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

int n;

int ask (int x1, int y1, int x2, int y2)
{
    cout << "? " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
    cout.flush();
    int t;
    cin >> t;
    return t;
}


int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif

    vector<int> row, col;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int r = ask(i, 1, i, n);
        int c = ask(1, i, n, i);
        if (r % 2)
        {
            row.pb(i);
        }
        if (c % 2)
        {
            col.pb(i);
        }
    }

    int x1, x2, y1, y2;
    int l = 1, r = n;
    if (row.size() && col.size())
    {
        // The head and tail in different rows and columns
        x1 = row[0], x2 = row[1];
        y1 = col[0], y2 = col[1];
        if(ask(x1,y1,x1,y1)%2 == 0)
        {
            swap(y1,y2);
        }
    } else if (row.size())
    {
        // In different rows but same column
        x1 = row[0], x2 = row[1];
        while (l < r)
        {
            int m = (l + r) >> 1;
            if (ask(x1, 1, x1, m) % 2)
            {
                r = m;
            } else
            {
                l = m + 1;
            }
        }
        y1 = y2 = l;
    } else
    {
        // In different columns but same row
        y1 = col[0], y2 = col[1];
        while (l < r)
        {
            int m = (l + r) >> 1;
            if (ask(1, y1, m, y1) % 2)
            {
                r = m;
            } else
            {
                l = m + 1;
            }
        }
        x1 = x2 = l;
    }

    cout << "! " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;


#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}
挖 坑 待 填

F. Serval and Bonus Problem

题意

关键词

思路

代码

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,186评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,858评论 3赞 387
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,620评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,888评论 1赞 285
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,009评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,149评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,204评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,956评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,385评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,698评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,863评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,544评论 4赞 335
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,185评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,899评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,141评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,684评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,750评论 2赞 351