NEFU 2021大一寒假集训总结赛 全题解

比赛链接：这里

OP

肝了两个半小时A，没过……
sl大佬也写题解了

A SET

最大公约数
感谢老师的标程~

思路

任选两数 a,b 做 2*a-b 运算，可以理解成 a + a - b ，即 a 加上两数的差；
如果我们现在有 2 * a - b , a 即可通过 2 * ( 2 * a - b ) - a 得到 a + 2 * ( a - b )，即 a 加上两数差的二倍；
如果我们现在有 3 * a - 2 * b , 2 * a - b 即可通过 2 * ( 3 * a - 2 * b ) - ( 2 * a - b ) 得到 a + 3 * ( a - b )，即 a 加上两数差的三倍；

此时，对于 a , b 两数，能组成的所有数可以构成一个含 a , b 、公差为 a - b 的等差数列。

那所有可能被加入集合的元素即满足
ai+mj∗(ai−aj)a_i+ m_j * ( a_i - a_j )（ aj 可以为计算出的元素值）

枚举显然是不现实的，我们可以使式子更加普适，转化成如下形式
amin+m∗gcd（a2−a1,a3−a2,...,an−an−1）a_{min}+ m * gcd（ a_{2}-a_{1},a_{3}-a_{2},...,a_{n}-a_{n-1}）

现在只需算出 gcd 并用 k 与 amin 的差对其取模即可。

我的过程可能不太好理解，可以直接参照sl大佬的题解。

看到标程之前的碎碎念：已知是需要去重，因为选两个相同的数，产生的还是那个数。好像还和等差数列有关。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+5;
ll gcd(ll a,ll b)
{
    while(a&&b)
    {
        if(a>b)a%=b;
        else b%=a;
    }
    return a+b;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll n,k,a[N]={0},i,j;
        scanf("%lld%lld",&n,&k);
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
        }
        sort(a+1,a+1+n);
        ll g=0;
        for(i=2;i<=n;i++)
        {
            g=gcd(g,a[i]-a[i-1]);
        }
        if(g&&(a[1]-k)%g==0||a[1]==k)printf("YES\n");//注
        else printf("NO\n");
    }
    return 0;
}

注：标程存在的bug已通过特判修复：如果元素值均相同，g将为0，无法进行求余运算，此时若题给元素值不等于目标值，则NO，等于则YES。
感谢ph大佬的hack数据。

B 密码解锁

快速幂取模+找规律

思路

我是通过打表发现，对于每个基 a ，在 k 增长时，结果有一定的周期性。
但是具体的循环节和循环起点我没发现规律，便直接让代码自己去找。

先存下 k 取较小值（1,2,3…）时的的结果，每算出一个新值，便与前面的所有值比对，如果有相同的值，便可以找到循环节和循环起点，再计算 k 对应的值就好了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long qs(long long a,long long b,long long p)
{
    long long ans=1%p;
    while(b)
    {
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return  ans;
}
int main()
{
    ll a,k,i,j,li[20]={0},mbc,xhj=0;//mbc为第一次循环结束位置，xhj为循环节长度
    cin>>a>>k;
    li[1]=a;
    mbc=1;
    for(i=2;i<20&&!xhj;i++,mbc++)
    {
        li[mbc+1]=qs(li[mbc],li[mbc],1000);
        for(j=1;j<=mbc;j++)
        {
            if(li[j]==li[mbc+1])
            {
                xhj=mbc+1-j;
            }
        }
    }
    if(k>mbc-xhj)
    {k-=mbc-xhj;
    k%=xhj;
    printf("%lld",li[mbc-xhj+k]);}
    else printf("%lld",li[k]);
    return 0;
}

C 夕日坂

个人是用滑窗做的

思路

即先累乘，至成绩大于目标值时，除掉前面的，同时计算以被除掉的数为起点的区间长。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int a[100005],n,i,j,b,l[100005];
    ll m;
    cin>>n>>m;
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    ll tim=1;
    b=1;
    for(i=1;i<=n;i++)
    {
        tim*=a[i];
        while(tim>m)//大于目标值
        {
            l[b]=i-b;//更新区间长
            tim/=a[b];
            b++;//更新起始位置
        }
    }
    for(i=b;i<=n;i++)//如果最后一段始终没有超过目标值
    {
        l[i]=n-i+1;
    }
    for(i=1;i<=n;i++)
    {
        if(i!=1)printf(" ");
        printf("%d",l[i]);
    }
    return 0;
}

D 小林的AC

字符串处理

思路

分别计数aceptd六个字母的出现次数，统计每个字母能组成单词份数的最小值即可（份数即出现次数 / 在单个单词中的个数）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    char g[50005];
    while(cin>>g)
    {
        int i,a=0,c=0,e=0,p=0,t=0,d=0;
        for(i=0;g[i];i++)
        {
            if(g[i]=='a')a++;
            else if(g[i]=='c')c++;
            else if(g[i]=='e')e++;
            else if(g[i]=='p')p++;
            else if(g[i]=='t')t++;
            else if(g[i]=='d')d++;
        }
        int ans=min(e/2,c/2);
        ans=min(ans,a);
        ans=min(ans,p);
        ans=min(ans,t);
        ans=min(ans,d);
        printf("%d\n",ans);
    }
    return 0;
}

E 小林刷题

贪心

思路

这道题特别像这个。

我们可以把排序问题拆分成从输入顺序开始的足够多次对换，只要我们找到能更趋近与所求结果的对换条件，我们便可以依照此条件直接排序。

假设现在有两道题，i 与 i + 1，我们要找到一种使对换后做两题时耗费的精力值更小的条件。

对换前，消耗精力值之和为
(b1+b2+...+bi−1)∗ai+(b1+b2+...+bi−1)∗ai+1+bi∗ai+1(b_1+b_2+...+b_{i-1})*a_i+(b_1+b_2+...+b_{i-1})*a_{i+1}+b_i*a_{i+1}

对换后，消耗精力值之和为
(b1+b2+...+bi−1)∗ai+bi+1∗ai+(b1+b2+...+bi−1)∗ai+1(b_1+b_2+...+b_{i-1})*a_i+b_{i+1}*a_i+(b_1+b_2+...+b_{i-1})*a_{i+1}

减掉相同部分后，若满足对换后小于对换前，则有
bi+1∗ai<bi∗ai+1b_{i+1}*a_i<b_i*a_{i+1}

这道题的条件便是 bi+1 / ai+1 < bi / ai

通过结构体+cmp实现。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct pro
{
    int a,b;
}p[500005];
bool cmp(pro x,pro y)
{
    return (double)x.b/x.a<(double)y.b/y.a;
}
int main()
{
    int n,i;
    cin>>n;
    for(i=1;i<=n;i++)scanf("%d%d",&p[i].a,&p[i].b);
    sort(p+1,p+n+1,cmp);
    ll bs=0,ans=0;
    for(i=1;i<=n;i++)
    {
        ans+=bs*p[i].a;
        bs+=p[i].b;
    }
    printf("%lld",ans);
    return 0;
}

F 小林移石子

中位数

思路

即找到一点，距离所有点的距离之和最短。
这个点便是所有点坐标的中位数。

和 货仓选址 基本相同

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int n,i,a[100005];
    cin>>n;
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    ll ans=0;
    for(i=1;i<=n;i++)
    {
        ans+=abs(a[i]-a[n+1>>1]);
    }
    printf("%lld",ans);
    return 0;
}

G 语汐玩游戏

思路

在游戏规则限制内，从顺时针或逆时针方向看，三个牌的顺序是无法被改变的。

如样例来说，从顺时针方向读，三个牌的顺序永远是 ABCABCA…，如果目标顺序相同，则可解，如目标顺序不相同，如 ACBABCA… ，则不可解。

接收之后比对顺序即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int a[6]={0},b[6]={0},ac=0,bc=0,f=-1,i,j;
    char s[5];
    cin>>s;
    for(i=0;i<=1;i++)
    {
        if(s[i]=='A')a[ac++]=1;
        else if(s[i]=='B')a[ac++]=2;
        else if(s[i]=='C')a[ac++]=3;
    }
    cin>>s;
    for(i=1;i>=0;i--)
    {
        if(s[i]=='A')a[ac++]=1;
        else if(s[i]=='B')a[ac++]=2;
        else if(s[i]=='C')a[ac++]=3;
    }
    cin>>s;
    for(i=0;i<=1;i++)
    {
        if(s[i]=='A')b[bc++]=1;
        else if(s[i]=='B')b[bc++]=2;
        else if(s[i]=='C')b[bc++]=3;
    }
    cin>>s;
    for(i=1;i>=0;i--)
    {
        if(s[i]=='A')b[bc++]=1;
        else if(s[i]=='B')b[bc++]=2;
        else if(s[i]=='C')b[bc++]=3;
    }
    for(i=3;i<=5;i++)b[i]=b[i-3];//延长目标串
    for(i=0;i<3;i++)
    {
        if(b[i]==a[0])//比对
        {
            for(j=1;j<=2;j++)
            {
                if(b[i+j]!=a[j])f=0;
            }
            if(f==-1)f=1;
        }
    }
    if(f==1)printf("YES");
    else printf("NO");
    return 0;
}

H 字符串之谜

DP

思路

对于每一个 b ，能和前面的每一个 a 组成一个 ab 串；
对于每一个 c ，能和前面的每一个 ab 串组成一个 abc 串。

更新记录目前 a，ab，abc 的个数即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    char a[1000006];
    ll i,ans=0,on=0,tw=0,tr=0;
    cin>>a;
    for(i=0;a[i];i++)
    {
        if(a[i]=='a')on++;
        else if(a[i]=='b')tw+=on;
        else if(a[i]=='c')tr+=tw;
    }
    printf("%lld",tr);
    return 0;
}

I 小林取数

贪心

思路

求最大和，即可看成求所有的和后，如果不满足条件，就减去最小的、能使总和满足条件的数（非整十数）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int n,a[102],i,mark=0,sum=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]%10!=0)//标记非整十数
        {
            if(!mark)mark=a[i];
            else mark=min(mark,a[i]);
        }
        sum+=a[i];//累加
    }
    if(sum%10!=0)printf("%d",sum);
    else
    {
        if(mark)printf("%d",sum-mark);
        else printf("0");
    }
    return 0;
}

ED

特别感谢老师的proA标程！！！

算法竞赛 > 比赛与题集
NEFU 2021大一寒假集训总结赛 全题解
https://tanyuu.github.io/2021.01-06/NEFU 2021大一寒假集训总结赛 全题解/
作者
F Juny
发布于
2021年2月5日
许可协议