长途

2022-12-20 14:33 已编辑湖南理工学院 Java 发布于北京

关注

湖南理工学院程序设计竞赛新生赛题解

lwy梦境中的斐波那契数列——诈骗签到题

根据数列的定义——

$f (1) = 1$

当 $n\ge 2$ 时， $f (n) = f (n - 1) + n$

容易发现 $f(n)=1+2+...+n=\frac{(1+n)\times n}{2}$

值得一提的是此题要模4399，它不是质数，不能用费马小定理求逆元。

直接算，最后取模即可。

另外很神奇的是，直接嗯算也能过。本来狠狠的卡掉超时的，这让出题人觉得很惊奇，确实考虑疏忽了。数据也没水，想不到跑得飞快能过。（到现在都没懂为啥能过……）

long long res=0;
for(int i=1;i<=n;i++)
{
	res=(res+i)%4399
}

标程如下

int main()
{
    ll n;
    scanf("%lld",&n);
    ll res=n*(n+1)/2%4399;
    printf("%lld\n",res);
}

你还会想起这道题吗

此题不难，但可能很多人会去像蛇形矩阵一样嗯模拟，难度偏高，还要考虑四个角，以及需要考虑还有n=1的恶心情况qwq

对于新生应该做过五子棋的实验内容，也不难想到。用条件语句判断上、下、左、右、对角、反对角即可。这样就写的简洁而优雅

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
// #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
const int N=51;
int a[N][N];
int main()
{
    int n;
    scanf("%d",&n);

    int res=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            if(i==1||j==1||i==n||j==n||i==j||i+j==n+1)
            res+=a[i][j];
        }
    }
    printf("%d\n",res);
}

你还会想起这道题吗(another version)

其实我觉得题面背景写的很有感触……但好像无人关心……

考虑每一个“圈”，它距离边界的距离，例如最外层距离边界是距离是1，从外数第二层距离边界的距离是2。

我们可以用一个数组存每一个“圈”的能量值总和。然后对于下标 $(i, j)$ 它距离边界的距离应该是 $m i n (i, j, n - i + 1, n - j + 1)$ ，也就是与 $0$ 和 $n + 1$ 作差。

然后最后遍历一边这个数组找最大值即可。

数据范围其实也可以加强 $n$ 到 $5000$ 。

标程

const int N=502;
int a[N][N];
int w[N];
int main()
{
    int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            int ans=min({i,j,n-i+1,n-j+1});
            w[ans]+=a[i][j];   
        }
    }

    int res=0;
    for(int i=1;i<=n;i++)
    {
        res=max(res,w[i]);
    }
    printf("%d\n",res);
}

农场大户

题面本人觉得有点难读懂，考察STL的简单应用。

因为商品名是个字符串（还可能是中文emm），考虑用map<string,long long> mp存储每一个商品，然后根据小号的商品数量以及价值算每个商品出售后能带来的收益总和。

下面的代码是用map存了下所有商品的数量总和

int main()
{
    int n,m;//有多少小号，卖出的货物
    scanf("%d%d",&n,&m);
    
    map<string ,long long> number;
    ll res=0;
    for(int i=1;i<=n;i++)
    {
        int z;
        scanf("%d",&z);
        for(int t=1;t<=z;t++)
        {
            string s;
            cin>>s;
            int num;
            scanf("%d",&num);

            number[s]+=num;
        }
    }
    for(int i=1;i<=m;i++)
    {
        string s;
        cin>>s;
        int val;
        scanf("%d",&val);
        res+=1ll*number[s]*val;
        
    }
    printf("%lld\n",res);
}

一道较为复杂的签到题

真正的诈骗签到题。因为世界上肯定有光头，所以世界上所有人头发数量的乘积是 $0$ ……

抱歉因这题诈骗可能带来了不太好的体验……

但很多人可能输出的是 $800000000000000$ ，这并不对，因为这是算的头发数量的和。算乘积的话按那个估计算的话应该根本输出不了

n车摆放问题

简单的组合数学

设 $m\le n$ （不满足的话，互换 $n$ ， $m$ 不影响结果）

此时，显然棋盘上最多是能放 $m$ 个棋子。它应该是占据了这 $m$ 列的每一列，接下来我们要决定每一列它处在哪一行，相当于给 $m$ 个有编号的人挑选 $n$ 个有标号的座位，方案数为 $A_n^m=\frac{n!}{(n-m)!}$

注意要开long long ，数据给的很良心。

const int N=21;
ll fact[N];//阶乘
ll A(int n,int m)
{
    return fact[n]/fact[n-m];
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);

    fact[0]=1;
    for(int i=1;i<N;i++) fact[i]=fact[i-1]*i;

    if(n<m) swap(n,m);//保证m<=n

    printf("%d\n",m);
    ll res=A(n,m);
    printf("%lld\n",res);
}

美食

个人中有 $m$ 个人撒谎，问题在于无法确定是哪些人撒谎，如果像样例解释那样暴力枚举，其时间复杂度至少为 $\mathcal{O}(\tbinom{n}{m})$ ，显然是不可接受的。

反向思考，考虑枚举辣度值，并检查当前辣度值 $x$ 是否满足恰好有 $m$ 个人撒谎。撒谎的人按照 $x$ 值一分为二：

对于 $p_i \geq x$ 的人来说，实话应该是 $0$ ，那么如果他的感受为 $1$ ，则对说谎总人数造成 $1$ 的贡献。
对于 $p_{i} < x$ 的人来说，实话应该是 $1$ ，那么如果他的感受为 $0$ ，则也对说谎的总人数造成 $1$ 的贡献。

按照上述方法统计一个撒谎人数的前缀和 $p r e$ 和后缀和 $s u f$ ，从前向后枚举辣度值，如果 $p r e_{i} + s u f_{i} = m$ ，那么将答案加 $1$ 。不过由于辣度值的值域达到了 $1 0^{9}$ ，我们不能直接枚举，离散化一下后枚举每个辣度区间即可。

瓶颈在于排序和离散化，时间复杂度 $\mathcal{O}(n \log n)$ 。

constexpr int N=1e6+10;
int p[N];
bool q[N];
int pre[N],suf[N],fake[N];

void solve() {
    int n,m,L,R;
    cin>>n>>m>>L>>R;
    vector<int> num{L,R+1};
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) cin>>q[i];
    for(int i=1;i<=n;i++) num.push_back(p[i]+1);

    sort(num.begin(),num.end());
    num.erase(unique(num.begin(),num.end()),num.end());

    auto get=[&](int x) {
        return upper_bound(num.begin(),num.end(),x)-num.begin()-1;
    };

    for(int i=1;i<=n;i++) {
        int cur=get(p[i]+!q[i]);
        if(q[i]) suf[cur]++;
        else pre[cur]++;
    }

    int t=num.size()-1,ans=0;
    for(int i=1;i<=t;i++) fake[i]+=pre[i]+=pre[i-1];
    for(int i=t-1;i>=0;i--) fake[i]+=suf[i]+=suf[i+1];
    for(int l=get(L),r=get(R+1);l<r;l++)
        if(fake[l]==m) ans+=num[l+1]-num[l];
    cout<<ans;
}

皮卡丘的梦幻之旅(easy version)

解法1

考虑爆搜(递归搜索)，最坏情况下走1步，要走15次，每次有 $m$ 种选择方式。

所以时间复杂度为 $O(m^{15})$ ，最坏即 $O(3^{15})$ ，大致为 $1 0^{7}$ ，并且实际上是肯定比这个小的，所以必定能过。

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
// #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl

const int N=20;
int res;
int a[4];
int n,m;
void dfs(int now)
{
    if(now>=n)
    {
        if(now==n) res++;
        return ;
    }
    for(int i=1;i<=m;i++)
    {
        dfs(now+a[i]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d",&a[i]);

    dfs(0);
    printf("%d\n",res);
}

解法2

考虑组合数学，因为 $m$ 很小，我们枚举这 $m$ 种方式分别是用了多少次。

如 $m = 3$ 时，我们可以这样三层循环枚举每种方式用的次数

for(int i=0;i<=n;i++)
{
    for(int j=0;j<=n;j++)
    {
        for(int k=0;k<=n;k++)
        {
			if()
        }
    }
}

接下来的问题就类似于。 $n u m$ 个小球，其中 $i$ 个红球， $j$ 个黑球， $k$ 个蓝球，排成一行有多少种排列方式

~~根据高中知识~~，排列方式应该为 $\frac{num!}{i!\times j!\times k!}$

也就是说

$m = 1$ 时，只有红球，排列方案为 $\frac{num!}{i!}$

$m = 2$ 时，只有红球和黑球，排列方案为 $\frac{num!}{i!\times j!}$

$m = 3$ 时，有红球，黑球，蓝球，排列方案为 $\frac{num!}{i!\times j!\times k!}$

时间复杂度 $O (n^{3})$ ，也就是最坏是 $O(15\times 15\times 15)$

同时，注意 $15!$ 超过了int范围，需要开long long

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
// #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl

const int N=20;
int fact[N];//阶乘
int a[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d",&a[i]);
    fact[0]=1;
    for(int i=1;i<=n;i++) fact[i]=i*fact[i-1];

    int res=0;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            for(int k=0;k<=n;k++)
            {
                if(i*a[1]+j*a[2]+k*a[3]==n)
                {
                    int m=i;
                    if(m>=2) m+=j;//m<2时则不管j，此时m=i
                    if(m==3) m+=k;//m<3时则不管k，此时m=i+j

                     int ans=fact[num]/(fact[i]*fact[j]*fact[k]);
                     res+=ans;
                }
            }
        }
    }
    printf("%d\n",res);
}

皮卡丘的梦幻之旅(middle version)

解法

考虑dp动态规划。

$d p [i]$ 表示恰好到达距离 $i$ 有多少种方式。对于移动方法 $a [j]$ ，有转移方程 $dp[i]=\sum\limits _{j=1}^m dp[i-a[j]]$

最终的答案即为 $d p [n]$

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
// #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl

const int INF=0x3f3f3f3f,mod=998244353;


const int N=5003,M=5003;
int a[M];
int dp[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d",&a[i]);
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(i>=a[j]) dp[i]=(dp[i]+dp[i-a[j]])%mod;
        }
    }
    printf("%d\n",dp[n]);
}

皮卡丘的梦幻之旅(hard version)

生成函数多项式题

设 $f (x) [x^{i}]$ 表示是否有能走第 $i$ 步的方式

然后 $f (x)^{k}$ 则代表了走了 $k$ 次后到达相应位置的方案数。也就是说我们用 $k$ 划分独立的方案数

所以有 $F(x)=f(x)^1+f(x)^2+...+f(x)^n=\frac{f(x)^{n+1}-f(x)}{f(x)-1}=\frac{f(x)}{1-f(x)}$

多项式求逆，多项式乘法搞一搞即可。

模板有点长，为了不影响版面，所以标程这里只表示核心部分

int main()
{
    scanf("%d%d",&n,&m);
    Poly f(n+1);
    for(int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        f[x]++;
    }

    Poly g(n+1);
    for(int i=1;i<=n;i++)
    {
        if(f[i]) g[i]=mod-f[i];
    }
    g[0]=1;
    Poly res=mul(f,Inv(g,n+1));
    printf("%lld\n",res[n]);
}

n个数的高精度乘法

由于最终结果对10000取模，所以我们只需要看后面四位数就行了。

读入字符串，取每个数的最后四位数转换为数字，如果不足四位就都取，然后相乘取模即可。

因为最初题面给的 $n$ 为 $1 0^{4}$ 但实际数据有 $2\times 10^4$ ，实属抱歉！！！

const int N=20004;
int main()
{
    int n;
    scanf("%d",&n);
    int res=1;
    while(n--)
    {
        string s;
        cin>>s;
        int w=0;
        reverse(s.begin(),s.end());
        for(int i=0,t=1;i<min(4,(int)s.size());i++,t*=10)
        {
            w+=(s[i]-'0')*t;
        }
        res=res*w%10000;
    }
    printf("%d\n",res);
}

轩哥的疑惑

签到题。输出场上有多少题即可

集！挡！波！

感觉有点像博弈的一道贪心题。

首先可以证明，lwy不可能赢，因为他使用的【波】都能被你【挡】掉，所以【波】的情况都不需要再考虑了。

当lwy【集】的时候，就是你使用【波】取得胜利的最好时刻。但同时，你需要有一点能量值才能使用【波】。所以首先当lwy使用【集】/【挡】的时候，你需要先积攒一点能量；当lwy再使用【集】的时候，你再【波】，即可取得胜利。其余情况都是平局。

const int N=1003;
char s[N];
int main()
{
    int n;
    scanf("%d",&n);

    scanf("%s",s+1);

    int flag=0;
    for(int i=1;i<=n;i++)
    {
        if((s[i]=='J'||s[i]=='D')&&flag==0) flag=1;
        else if(s[i]=='J'&&flag==1)
        {
            puts("win");
            return 0;
        }
    }
    puts("draw");
}

挑选未婚夫

题意简化如下：每个数字拥有一个独特的帅气值，我们需要从1到n的这些数字中，找到这些数字里面的最大帅气值。每个数字的帅气值定义如下——

对于一个数x来说，在k进制下，他可以得到形如a b c d e（每个字母代表一个数，-1<字母<k），那么数字x的帅气值就为（a+b+c+d+e+5），abcde是每一位上的数字，而5则是总位数的数量。

我们需要在1到n的每个数字中，找出最大的帅气值。

对于数字n，我们将起转化为k进制的数字，假设我们得到的数字为a b c d e f。如果对于a，我们进行-1操作，那么对于b c d e f，无论我们怎么操作，a-1 x x x x x（x为未知数）总是小于n的，而且对于这样的数，我们很容易推知，将其化作a-1 k-1 k-1 k-1 k-1 k-1时，所找到的最大帅气值是最优解。

以上，是对于一般情况的推论。除此之外，会出现一些异常情况，如：

最为特殊的是a=1的情况，在此情况下，a进行-1操作后变成0，会导致位数的更替，这种情况下，我们需要考虑更多。如b=k-1的时候，我们将a-1，无法对b造成任何影响，且失去2个帅气值，但若我们对于b进行-1操作，仅仅失去1个帅气值，在这种情况下，选择对b进行-1操作是最优解。

考虑到上面这种特殊情况后，我们还需要注意到一个问题——进行-1操作后，转化成a-1 k-1 k-1 k-1 k-1 k-1或 1 b-1 k-1 k-1 k-1 k-1或k-1 k-1 k-1 k-1 k-1，的形式下，一定都为最优解吗？答案是否定的。

我们同样有三个相应的形式所反驳——

n可以转化成a k-1 k-1 k-1 k-1 k-1时；

n可以转化成1 k-2 k-1 k-1 k-1 k-1时；

n可以转化成a, 1 k-1 k-1 k-1 k-1 k-1时。

#include<bits/stdc++.h>
#include<iostream>

using namespace std;

const int N=1e5+10;

int main()
{ 
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	long long cnt=0,num[N],n,k,ans[3],sum=0;
	cin>>n>>k;
    while(n)
	{
		ans[0]+=n%k;
		num[cnt++]=n%k;
		n/=k;		
	}
    ans[0]+=cnt;
    ans[1]=ans[2]=cnt;
	ans[1]+=(cnt-1)*(k-1)+num[cnt-1]-1;
	if(num[cnt-1]==1)ans[1]-=1;
	for(int i=cnt-1;i>=0;i--)
	{
		if(num[i]!=0&&i!=cnt-1)
		{
			ans[2]+=(k-1)*i;
			ans[2]+=num[i]-1;
            break;
		}
        ans[2]+=num[i];
	}
	for(int i=0;i<3;i++)
	{
		sum=max(ans[i],sum);
	}
	cout<<sum;
	return 0;
}

看到有人用python写的很短qwq

n,k=map(int,input().split())
u=1
ans=0
while n>=u:
    cur=min(k-1,n//u)
    ans+=cur+1
    n-=cur*u
    u*=k
if n+u//k>=u:
    print(ans+1)
else:
    print(ans)