Codeforces Round #536 (Div. 2) 题解及总结

大半年打一次cf结果因为评测机出锅unrated了，非常不爽。

这次比赛是和@Duanyll大佬合作打的，但因为我很弱出了很多锅坑了他，不过幸好是unrated。

好歹还是A了四道题的，还是总结一下吧。

A. Lunar New Year and Cross Counting

题意

给你一个矩阵，只要满足 $M(i,j)=M(i-1,j-1)=M(i-1,j+1)=M(i+1,j-1)=M(i+1,j+1)='X'$ 就算一个十字架，问有多少个十字架。

题解

大水题， $O(n^{2})$ 按题意模拟即可。代码是dyl大佬写的，我就改了下变量。

char s[505][505];

int main() 
{
    int n=read();
    for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    int ans = 0;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++) 
            if (s[i][j] == 'X' && s[i][j] == s[i - 1][j - 1] && s[i][j] == s[i - 1][j + 1] && s[i][j] == s[i + 1][j - 1] && s[i][j] == s[i + 1][j + 1]) ans++;
    printf("%d",ans);
    return 0;
}

B. Lunar New Year and Food Ordering

题意

一家餐馆有n种菜，每种菜的数量和价格分别是 $a_{i}$ 和 $c_{i}$。

有m个顾客会来点 $d_{j}$ 份的第 $t_{j}$ 种菜。如果第 $t_{j}$ 种菜还有，就提供给顾客；如果不够，那么就用最便宜的菜来凑数（多个相同价格的最便宜的菜按输入顺序排序）；如果所有剩余的菜加起来都不够，那么顾客会愤怒的拿走所有的菜并且一分钱都不给你。

对于每个顾客，输出他们花费的钱。

题解

按照价格为第一关键字，顺序为第二关键字给菜排序，并且用 $bef[]$ 来记录原先的顺序对应的排序后的顺序，然后直接按照题意膜你即可。

一定要开long long!

一定要开long long!

一定要开long long!

还有如果纯模拟可能会T，我后来加了一个 $last$ 变量来记录当前按顺序取到了第几样菜（也就是说 $last$ 之前的菜都取完了不用再考虑了），这样才A的。

我因为long long和不加优化的膜你坑了dyl大佬两次，感到十分抱歉。

struct dish{
    ll num,pri,id;
} s[100005];

ll n,m,t,d,bef[100005],tot,last;

inline bool cmp(dish x,dish y)
{
    return (x.pri==y.pri) ? x.id<y.id : x.pri<y.pri;
}

int main()
{
    n=read(); m=read();
    for (ll i=1;i<=n;i++) s[i].num=read(),s[i].id=i,tot+=s[i].num;
    for (ll i=1;i<=n;i++) s[i].pri=read();
    sort(s+1,s+n+1,cmp);
    for (ll i=1;i<=n;i++) bef[s[i].id]=i;
    last=1;
    for (ll i=1;i<=m;i++)
    {
        t=read(); d=read();
        if (d>tot) 
        {
            tot=0;
            printf("0\n");
            continue;
        }
        tot-=d;
        if (s[bef[t]].num>=d)
        {
            s[bef[t]].num-=d;
            printf("%I64d\n",d*s[bef[t]].pri);
        }
        else
        {
            d-=s[bef[t]].num;
            ll i=last,now=s[bef[t]].num*s[bef[t]].pri;
            s[bef[t]].num=0;
            for (;;)
            {
                if (d>=s[i].num) d-=s[i].num,now+=s[i].pri*s[i].num,s[i].num=0;
                else 
                {
                    s[i].num-=d;
                    now+=s[i].pri*d;
                    last=i;
                    break;
                }
                i++;
            }
            printf("%I64d\n",now);
        }
    }
    return 0;
}

C. Lunar New Year and Number Division

题意

给你 $n$ 个数，保证 $n$ 是偶数，要求将这些数分组（每组至少两个数），求每组的和 的平方和 的最小值。

题解

貌似正解就是按照一大一小分组，我也不知道怎么证明。

ll s[300005];

int main() 
{
    int n=read();
    for (int i = 1; i <= n; i++) s[i]=read();
    sort(s+1,s+n+1);

    ll ans = 0;
    for (int i = 1; i <= n / 2; i++) {
        ans += (s[i]+s[n+1-i])*(s[i]+s[n+1-i]);
    }
    cout<<ans;
    return 0;
}

D. Lunar New Year and a Wander

题意

跟NOIp2018D2T1很像，不过旅行那题规定了只能从走过的城市返回，而且 $m$ 有限制，这道题 $m$ 没有限制而已。

给你一个 $n$ 个点的图，有 $m$ 条双向边，求遍历所有节点的最小字典序。

题解

用优先队列bfs即可，每次选择序号最小的节点进行扩展，将能扩展到的城市入队即可。

一定要在bfs里面输出！我把答案存在最后输出就T了，这tm卡常太严重了

struct Edge{
    int next,to;
} edge[200005];
int n,m,a,b,c,cnt,head[100005];
bool vis[100005];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void bfs()
{
    priority_queue <int,vector<int>,greater<int> > q;
    q.push(1);
    while (!q.empty())
    {
        int x=q.top(); q.pop();
        if (vis[x]) continue;
        vis[x]=1;
        printf("%d ",x);
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to;
            if (vis[y]) continue;
            q.push(y);
        }
    }
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    bfs();
    return 0;
}