第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 全题解

比赛链接：这里

OP

好多大佬哦~

A 切蛋糕

这道题是特判题（SpecialJudge），第一眼没看见，读完题就决定放了。

由于宽松的步数限制，可以暴力做，即先通过2047次切割把蛋糕切为2048份，即可保证分配时误差值小于 1 / 1024。再找出可行的 c 满足 fabs( c / 2048 - 1 / k ) <= 1 / 1024，即为给每份包装进 c 个 1 / 211。

注：经测试，蛋糕可以有剩余。

//标准做法以后再补（flag）

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;
#define ll long long
 
int main ()
{
    int k,two=1,i,j;
    cin>>k;
    for(i=1; i<=2048; i++)
    {
        if(fabs((double)i/2048.0-1.0/k)<=1.0/1024)break;
    }
    int c=i;
    printf("%d\n",2047+k);//输出总步数
    for(i=0; i<=10; i++)
    {
        for(j=1; j<=two; j++)
            printf("1 %d\n",i,cou++);
        two*=2;
    }
    for(j=1; j<=k; j++)
    {
        printf("2 %d",c);
        for(i=1; i<=c; i++)printf(" 11");
        printf("\n");
    }
    return 0;
}

B 小宝的幸运数组

用 a[ i ] 表示从第一项加到第 i 项的和，则区间 [ i , j ] 的和为 a[ j ] - a[ i - 1 ] 。

若区间 [ i , j ] 的和满足能被 k 整除，则有 ( a[ j ] - a[ i - 1 ] ) % k ==0，
即 a[ j ] % k == a[ i - 1 ] % k，
所以此问题等价为找出 a[ i ] % k 相等的最远距离。
O( k n2 )遍历显然不现实，我们可以对 [ 0 , k - 1 ] 的每一个数存下最前位置和最后位置，再遍历 [ 0 , k - 1 ] 找出左右距离最远的。

求余对四则运算封闭

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
 
ll a[N];
int main ()
{
    int t;
    cin>>t;
    while(t--)
    {
        int b[100005]={0},l[100005]={0},r[100005]={0};//b计数，l,r存左右位置
        int n,k,i,g,a=0,m=0;
        cin>>n>>k;
        b[0]=1;l[0]=0;//数组无元素时
        for(i=1;i<=n;i++)
        {
            scanf("%d",&g);
            a+=g;
            a%=k;
            if(!b[a]){l[a]=i;b[a]++;}
            else{r[a]=i;b[a]++;}
        }
        for(i=0;i<k;i++)
        {
            if(b[i]>=2&&r[i]-l[i]>m)//有左有右
            m=r[i]-l[i];
        }
        if(m)printf("%d\n",m);
        else printf("-1\n");
    }
    return 0;
}

C 上进的凡凡

首先依题意，每个数构成的长度为一的数组均为nice的。

若某数大于等于前数，则标注成1，否则标记为0，统计每段连续1的长度，对于长度为 n 的连续1，代表了一段长度为 n + 1 的非降数组，此数组中长度大于等于二的子数组有 n * ( n - 1 ) / 2 个。

累加每一段非降数组的子数组个数，再加上总共的元素个数，即为结果。

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
#include <bits/stdc++.h> 
using namespace std;
 
int main()
{
    int a[100005]={0};
    int n,i,j,c;
    long long ans=0;
    cin>>n;
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    for(i=n;i>=2;i--)if(a[i]>=a[i-1])a[i]=1;else a[i]=0;//标注
    a[1]=0;
    int l,r;
    l=1,r=1;
    ans=n;//单元素数组
    while(l!=n)
    {
        //printf("%lld %d\n",ans,r);
        while((!a[l+1])&&l<=n)l++;//类似于滑窗
        r=l+1;
        while(a[r+1]&&r<=n)r++;
        if(l<=n&&r<=n){
        int len=r-l+1;
        ans+=(long long)len*(len-1)/2;
        l=r+1;}
        if(l>n)l=n;//防溢出
    }
    printf("%lld",ans);
    return 0;
}

D Seek the Joker I

巴什博弈

也可以现推：
先手者抽牌+后手者抽牌 为一轮

若保证先手者必赢，则最后一轮开始时需满足桌面有 1 < n <= k + 1 张牌，先手者取 n - 1 张，后手者必输；
则倒数第二轮开始时，需满足桌面有 k + 2 < n <= 2 * k + 2 张牌，先手者取至剩 k + 2 张，无论后手者如何取，均可满足先手者必赢的最后一轮条件；
同理，倒数第三轮开始时，需满足桌面有 2 * k + 3 < n <= 3 * k + 3 张牌，先手者取至剩 2 * k + 3 张，无论后手者如何取，均可满足先手者必赢的最后一轮条件；

以此类推，若 n 满足存在正整数 a 使得 ( a - 1 ) * k + a < n <= a * k + a ，则先手者必赢，化简后则等价为 ⌈ n / ( k + 1 ) ⌉ * ( k + 1 ) - k < n。（ ⌈ n / ( k + 1 ) ⌉ 即为 a ）

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;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        if(ceil(1.0*n/(k+1))*(k+1)-k<n)
        printf("yo xi no forever!\n");
        else printf("ma la se mi no.1!\n");
    }
    return 0;
}

补充：也可以说 若 n 满足存在正整数 a 使得 n = ( a - 1 ) * k + a ，等价于 ( n - 1 ) / ( k + 1 )为整数时，先手必输
代码如下

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

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        if((n-1.0)/(k+1.0)-(int)((n-1.0)/(k+1.0))>0.000001)//这里如果是1e-4就会WA
        printf("yo xi no forever!\n");
        else printf("ma la se mi no.1!\n");
    }
    return 0;
}

E Seek the Joker II

威佐夫博弈

这个不太好现推了，走结论吧。

( a < b )
( sqrt(5.0) + 1 ) * ( b - a ) / 2 = a 时，先手必输。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    double mysticalConstant = (1.0+sqrt(5.0))/2.0;
    int T;
    cin>>T;
    while(T--)
    {
        int n,x;
        cin>>n>>x;
        int a=x-1,b=n-x;
        if(a>b) swap(a,b);
        int temp = (b-a)*mysticalConstant;
        if(temp!=a) cout<<"yo xi no forever!\n";
        else cout<<"ma la se mi no.1!\n";
    }
    return 0;
}

F 成绩查询ing

需要构建两组映射：名字与个人信息，成绩与名字
这里多构建了一组：名字与序号（nn），序号与个人信息（stu），成绩与名字（ms）

成绩对应的名字用set存可以直接按字典序排列

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
#include <bits/stdc++.h>
using namespace std;
map<int,set<string> >ms;
set<string>::iterator it;
map<string,int>nn;
struct stud
{
    int gra,sex,num;
    //string na;
}stu[100005];
int main()
{
    int n,i;
    string ge;
 
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>ge;
        nn[ge]=i;
        scanf("%d%d%d",&stu[i].gra,&stu[i].sex,&stu[i].num);
        ms[stu[i].gra].insert(ge);
    }
    int t,o;
    cin>>t;
    while(t--)
    {
        scanf("%d",&o);
        if(o==1)
        {
            cin>>ge;
            printf("%d %d %d\n",
                   stu[nn[ge]].gra,stu[nn[ge]].num,stu[nn[ge]].sex);//注意顺序
        }
        else
        {
            scanf("%d",&o);
            if(!ms[o].empty())
            {
                for(it=ms[o].begin();it!=ms[o].end();it++)
                {
                    printf("%s\n",(*it).c_str());
                }
            }
        }
    }
    return 0;
}

G 贪吃的派蒙

先找出派蒙的位置（pmi），计算出派蒙左边的人一轮下来所要吃的最少数量ami和最多数量amx，

依靠 ami < k && amx + pmn >= k 判断第一次轮到派蒙时能不能被派蒙吃尽，如果不能，总量减去派蒙吃掉的（pmn）后，每轮ami与amx加上派蒙外所有人的最小值与最大值，再进行比较。amx > 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
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int main ()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k,pmi,pmn=0,i,f=0;
        int r[100005]= {0};
        cin>>n>>k;
        for(i=1; i<=n; i++)
        {
            scanf("%d",&r[i]);
            if(r[i]>pmn)
            {
                pmn=r[i];
                pmi=i;
            }
        }
        ll ami=pmi-1,amx=0;
        for(i=1; i<pmi; i++)amx+=r[i];
        if(ami<k&&amx+pmn>=k)f=1;
        else
        {
            while(amx<=k)
            {
                k-=pmn;
                ami+=n-1;//+所有人的最小值
                for(i=pmi+1; i<=n; i++)amx+=r[i];//+后面人的最大值
                for(i=1; i<pmi; i++)amx+=r[i];//+前面人的最大值
                if(ami<k&&amx+pmn>=k)
                {
                    f=1;
                    break;
                }
            }
        }
        if(f)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

H 数羊

打表找规律

m = 0 时，A( n , 0 ) = n + 2 ;（n = 1 时特判 A( 1, 0 ) = 2 ）
m = 1 时，A( n , 1 ) = 2 * n ；
m = 2 时，A( n , 2 ) = 2n。

m = 2 时需要用到快速幂。

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
#include<bits/stdc++.h>
#define ll long long
const ll mod=998244353;
using namespace std;
ll qm(ll m)
{
    ll ans=1,n=2;
    while(m)
    {
        if(m&1)ans=ans*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return ans%mod;
}
int main()
{
    ll t,n,m;
    cin>>t;
    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        if(m==0)
        {
            if(n==1)printf("2\n");//特判
            else printf("%lld\n",n+2);
        }
        else if(m==1)
        {
            printf("%lld\n",2*n);
        }
        else printf("%lld\n",qm(n));
    }
    return 0;
}

I 买花

若第一天买 a 朵，则第二天有 a * 11(B) 朵，第三天有 a * 111(B) 朵，……，第十五天有 a * 111 1111 1111 1111(B) 朵，则直接遍历[ 11 , 111 , … , 111 1111 1111 1111 ](B)，目标量能否被其中元素整除，若能则可行。

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;
 
int main()
{
    int k[]={3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767};
    int i/*0-13*/,n,t;
    cin>>t;
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<=13;i++)
            if(n%k[i]==0)break;
        if(i==14)printf("N0\n");//说明没有能整除情况
        else printf("YE5\n");
    }
    return 0;
}

J 这是一题简单的模拟

可以直接用二维数组建图，检验题给数据。

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
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int n,m,f,t,co,a,mi=0x7fffffff,i;
    cin>>n>>m;
    int r[302][302]= {0};
    while(m--)
    {
        scanf("%d%d%d",&f,&t,&co);
        r[f][t]=co;
        r[t][f]=co;
    }
    cin>>a;
    int p[302]= {0},c[302]= {0},g,fl;//p存储题给顺序，c检验重复城
    while(a--)
    {
        fl=1;
        memset(p,0,sizeof p);
        memset(c,0,sizeof c);
        cin>>g;
        for(i=1; i<=g; i++)
        {
            scanf("%d",&p[i]);
            if(!c[p[i]])c[p[i]]=1;
            else fl=0;//如有重复城
        }
        if(g!=n||!fl)continue;
        fl=1;
        f=0;
        int cou=0;
        for(i=1; i<=g&&fl; i++)
        {
            if(r[f][p[i]])cou+=r[f][p[i]];
            else fl=0;
            f=p[i];
        }
        if(r[f][0]&&fl)cou+=r[f][0];//注意回家路
            else fl=0;
        if(fl&&cou<=mi)mi=cou;
    }
    if(mi<0x7fffffff)printf("%d",mi);
    else printf("-1");
    return 0;
}

K 黑洞密码

字符串处理，注意好对26溢出的处理即可。

注：对于二维数组 a[ 4 ][ 4 ] ，a[ 0 ][ 5 ] 即代表 a[ 1 ][ 0 ]，这个在这里很好用。

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
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int a[4][4]={0},in=0,ch=0,i=0,j;
    char c[4][4],g;
    for(i=1;i<=32;i++)
    {
        scanf("%c",&g);
        if(g>='0'&&g<='9')a[0][in++]=g-'0';
        else c[0][ch++]=g;
    }
    for(i=0;i<=3;i++)
    {
        for(j=0;j<=3;j++)
        {
            if(c[i][j]>='A'&&c[i][j]<='Z')
            {
                if(c[i][j]+a[i][j]>'Z')c[i][j]='a'+c[i][j]+a[i][j]-'Z';
                else c[i][j]+=a[i][j];
            }
            else
            {
                if(c[i][j]+a[i][j]>'z')c[i][j]='A'+c[i][j]+a[i][j]-'z';
                else c[i][j]+=a[i][j];
            }
        }
        for(j=3;j>=0;j--)printf("%c",c[i][j]);
    }
    return 0;
}

L 建立火车站

二分，对于长度，端点值及其右侧均为可行解，故向左取整。

注：存在 k = 0 的测试组

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;
 
int main()
{
    long long a[100005];
    long long n,k,i;
    cin>>n>>k;
    for(i=1; i<=n; i++)scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    long long l=1,r=a[n]-a[1]+5;
    while(l<r)
    {
        long long mid=l+r>>1;
        long long cou=0;
        for(i=2; i<=n; i++)
        {
            //if(a[i]-a[i-1]>=mid)
            {
                cou+=(a[i]-a[i-1]-1)/mid;
            }
        }
        if(cou<=k)r=mid;
        else l=mid+1;
    }
    printf("%lld",l);
    return 0;
}

ED

做到最后莫划水，打表有惊喜。

打表天下第一！

算法竞赛 > 比赛与题集
第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 全题解
https://tanyuu.github.io/2021.01-06/第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 全题解/
作者
F Juny
发布于
2021年1月31日
许可协议