C/C++教程

The 2019 China Collegiate Programming Contest Harbin Site

本文主要是介绍The 2019 China Collegiate Programming Contest Harbin Site,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

打得很烂,打铁了,赛后补到了银牌题差不多(银牌还要手速),只能说实在是经验太少了。加油吧!

J. Justifying the Conjecture

​ 题意:问一个数能不能分解成一个\(x\)和一个\(y\),使得\(x\)是质数而且\(y\)为合数

​ 题解:签到题,对于大于2的偶数显然都可以拆成2+一个偶数,大于5的奇数都可以拆成3+一个偶数,其他特判就行。

K.Keeping Rabbits

​ 题意:n个数,每个数每次增长的概率是\(\frac{a_i}{\Sigma a_j}\),问k天后每个数的期望

​ 题解:容易得知每个数期望增长的大小每天都是固定的(都是按比例增长),因此只需要每个数加上\(\frac{ka_i}{\Sigma a_j}\)就行了

​ 这题其实可以直接观察两天数据直接猜想得出结果,可以节约时间。

F.Fixing Banners

​ 题意:六个字符串,每个里面可以任意选一个字母,问是否能把选出的字母拼成"harbin"

​ 题解:直接处理六个字符串中的h,a,r,b,i,n六个字母。暴力枚举每个字符串选择的字母或者状压dp都可以解决。

​ 比赛上签到想状压也是人才,另外编译器只有编译了调试才有效!!!(浪费半个小时才发现输出错误结果是没编译)

I.Interesting Permutation

​ 题意:对于一个数组\(a[i]\),定义\(f[i]\)为前i个数最大数,\(g[i]\)为前i个数最小值,\(h[i]=f[i]-g[i]\),现给定\(h[i]\),求\(a[i]\)的可能取法。

​ 题解:考虑\(h[i]\)和\(h[i-1]\)的关系,若\(h[i]\neq h[i-1]\),那么这里可能出现最大值变小和最小值变大两种情况,则\(ans*=2\),并且更新可用可插入数,数量为\(h[i]-h[i-1]-1\),否则\(ans*=num\),可插入数用掉一个。

​ 考场上太执着于用暴力的方法推出一个优美的结论了。其实可以分工推导,一部分人写暴力一部分人思考数学推导。而且在数学推导的时候也一直执着于研究\(h[i]\)的值相同的区间,但却没有想以区间分类研究每一个点。而且,在思考问题时并没有清晰的思路,直接在原代码上进行修改(应该备份原代码并且复制粘贴可用的代码帮助重构)。在考场上我们犯了几个严重的错误:

  1. 在每组数据读入没读完就直接return了。以后可以读完再处理数据
  2. 数据范围问题:long long是ACMer的痛

只能说做题经验不足,队伍磨合不够,还要加强训练。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int t,h[100005],n;
const int MOD=1000000007;

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&h[i]);
    if(h[1]!=0||h[n]!=n-1) {puts("0"); return ;}
    int sum=0;LL ans=1;
    for(int i=2;i<=n;i++)
    {
        if(h[i]<h[i-1]) {puts("0"); return ;}
        if(h[i]==h[i-1]) {ans=(ans*sum)%MOD;sum--;}
        else {sum+=h[i]-h[i-1]-1; ans=(ans*2)%MOD;}
    }
    printf("%lld\n",ans);
    return ;
}

int main()
{
    cin>>t;
    while(t--)
        solve();
    return 0;
}

E. Exchanging Gifts

​ 题意:求一个数组在交换顺序后,和原数组对于同一位置上的值不同的位置最大可能为多少个。其中数组有两种表示方法,一种是直接给出,另一种是前两个数组连接。

​ 题解(我的做法):先考虑任意一个可以直接给出的数组,实际上这个结果只跟出现最多次数的元素的个数有关。如果没有比数组长度\(len\)一半大,答案一定为\(len\),否则可以推导得到结果\(2*(len-maxcnt)\)。我们只需要计算要求数组的出现最多次数的元素的个数。可以通过类似线段树的下推操作的办法,从\(n\)下推到\(1\),把\(s_n\)分解为多个直接给出的数组的组合,然后直接求出\(s_n\)的所有元素的个数。这里需要进行读入优化。

​ 通过这题我发现,读入和读入之间的差距真的很大。在这个数据范围之下,使用优化过的快读居然比没有优化过的快读快6倍,而scanf更是惨不忍睹。而且,我之前的细节一直做得不好,memset虽然快,但是在数据量大的时候还是显得浪费时间,不如for循环重置快。之前一直觉得复杂度对就没什么问题,卡常没什么用,看来应该改变一下这个观念了。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

map <int,LL> mp[1000006];
LL cnt[1000006];
int rel[1000006][3],ch[1000006],n;

inline void push_down(int x)
{
    if(ch[x]==1) return ;
    cnt[rel[x][1]]+=cnt[x],cnt[rel[x][2]]+=cnt[x],cnt[x]=0;
}

LL getans(int x)
{
    LL mcnt=-1,len=0;
    for(auto [x,y]: mp[x])
    {
        mcnt=max(mcnt,y);
        len+=y;
    }
    if(mcnt<=len/2) return len;
    else return 2*(len-mcnt); 
}

void sumn()
{
    for(int i=1;i<n;i++)
        if(cnt[i])
        {
            for(auto [x,y] :mp[i])
                mp[n][x]+=y*cnt[i];
        }
}

inline char nc() {
    static char buf[1000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <class T> inline bool input(T &x) {
    x = 0; char c = nc(); bool f(0);
    while (c < '0' || c > '9') { if (c == EOF) return false; f = c == '-', c = nc(); }
    while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = nc(); if (f) x = -x; return true;
}

void solve()
{
    int cntt,tmp;
    input(n);
    for(int i=1;i<=n;i++)
    {
        input(ch[i]);
        if(ch[i]==1)
        {
            input(cntt);
            for(int j=1;j<=cntt;j++)
            {
                input(tmp);
                mp[i][tmp]++;
            }
        }
        else input(rel[i][1]),input(rel[i][2]);
    }
    cnt[n]=1;
    for(int i=n;i;i--)
        push_down(i);
    sumn();
    printf("%lld\n",getans(n));
    for(int i=1;i<=n;i++)
        mp[i].clear();
    memset(cnt,0,sizeof(cnt));
    return ;
}

int main()
{
    int t;
    input(t);
    while(t--)
        solve();
    return 0;
}

这篇关于The 2019 China Collegiate Programming Contest Harbin Site的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!