第十五届吉林省大学生程序设计竞赛

本文主要是介绍第十五届吉林省大学生程序设计竞赛，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

最近刚打完吉林省程序设计竞赛，自己比较菜，成绩不是很好，拖累了两位队友，其中一位队友保研，并在比赛前一天拿到了百度的实习offer.另一位是备战考研。

比赛只过了A,B,E,L,M，最终41名

A题：

题目大意：给你一i个数组，判断数组中元素奇数和偶数的个数差是否小于等于1.

签到题

//
// Created by LiuHongzhe on 2021/11/30.
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll ans;
ll x;
ll dx,dy;
int main()
{
    ll i,j,k;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>x;
        if(x%2==0)
            dx++;
        else
        {
            dy++;
        }

    }
    ans=abs(dx-dy);
    if(ans<=1)
    {
        cout<<"Good"<<endl;
    }else
    {
        cout<<"Not Good"<<endl;
    }
    return 0;
}

B题：

题目大意：给三个数a,b,k,计算a/b,保留k位

签到题

//
// Created by LiuHongzhe on 2021/11/30.
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll i,j;
    ll a, b,k;
    ll t;
    cin>>a>>b>>k;
    if(a==b)
    {
        cout<<"1.";
        for(i=0;i<k;i++)
        {
            cout<<0;
        }
    } else{
        cout<<"0.";
        for(i=0;i<k-1;i++)
        {
            t=a*10/b;
            cout<<t;
            a=a*10%b;
        }
        ll dt=a*10/b;
        a=a*10%b;
        t=a*10/b;

        if(t>=5&&t<=9)
        {
            cout<<dt+1;
        }
        else
        {
            cout<<dt;
        }
    }
    return 0;
}

E题：

给一个数组，判断是否存在两个元素异或等于1

a[i]^a[j]==1&&i!=j
a[i]^a[j]==1&&i!=j
基础知识:
1^1=0;1^0=1;0^1=1;0^0=0;
若a^b=c则 c^a=(a^b)^a=b
则原题可以推理为是否存在a[i]^1属于数组中的元素

//
// Created by LiuHongzhe on 2021/11/30.
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
ll flag;
int main()
{
    ll i,j;
    ll x;
    cin>>t;
    while(t--)
    {
        set<ll>a;
        flag=false;
        n = 0;
        scanf("%lld", &n);
        for(i=0;i<n;i++)
        {
            scanf("%lld", &x);
            a.insert(x);
        }
        for(auto it:a)
        {
            ll dt=it^1;
            ll dx=a.count(dt);
            if(dx==1)
            {
                flag=true;
                break;
            }
        }
        if(flag)
        {
            printf("Yes\n");
        }else
        {
            printf("No\n");
        }
    }
    return 0;
}

L题：

题目大意：给一个字符串S，定义Si为从S的第i位开始的子串，Si有两种处理办法，一种删去最后一个字符，另一种加入一个字符，最后让Si构造成S的最小次数记位d（Si）,求d（Si）中最大的数

//
// Created by LiuHongzhe on 2021/11/30.
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int t;
    cin >> t;
    string s;
    while(t--) {
        cin >> s;
        int i;
        const int sz = s.size();
        for(i = 1; i < sz; ++i) {
            if(s[i] == s[i - 1]) continue;
            else break;
        }
        if(i == sz) cout << sz - 1 << endl;
        else cout << sz * 2 - i << endl;
    }
    return 0;
}

M题：

题目大意：给一个数组，求数组的极差与数组长度的乘积。

签到题

//
// Created by LiuHongzhe on 2021/11/30.
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll a[10005];
ll maxn = -100005;
ll minn = 100005;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++ ){
        cin >> a[i];
        maxn = max(maxn, a[i]);
        minn = min(minn, a[i]);
    }
    ll ans = maxn - minn;
    ans *= n;
    cout << ans << endl;
    return 0;
}

后面题目，比赛中没有做对，比赛结束自己补的，不能保证一定正确

K题：

题目大意：求给定一个长度位2N,括号种类位K的合法的括号数量

对于只有一种括号时，括号的数量是卡特兰数列

对于k种括号时，答案就是卡特兰数列*（k^n）

卡特兰数，应用于：括号化，凸多边形三角划分，给定节点组成二叉搜索树，n对括号正确匹配数目。

此题考查了数学知识：排列组合，快速幂，卡特兰数列

其中排列组合在曾在热身赛中第二题出现过

//
// Created by LiuHongzhe on 2021/11/30.
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll k;
ll N=1e9+7;
ll ans;
ll fastpow1(ll a, ll n) {//快速幂
    ll base = a;
    ll res = 1;
    while(n) {
        if(n & 1)
            res = (base * res) % N;
        base = (base * base) % N;
        n >>= 1;
    }
    return res;
}
ll fun(ll n,ll m)//排列组合
{
    if(m==0)
        return 1;
    ll a[n+5];
    for(int i=1;i<=n;i++)
    {
        a[i]=i;
    }
    for(int j=2;j<=m;j++)
    {
        ll t=j;
        for(int i=n-m+1;i<=n;i++)
        {
            if(__gcd(t,a[i])>1)
            {
                ll dy=__gcd(t,a[i]);
                a[i]=a[i]/dy;
                t=t/dy;
                if(t==1)
                    break;
            }
        }
    }
    ll sum=1;
    for(int i=n-m+1;i<=n;i++)
    {
        sum=(sum*a[i])%N;
    }
    return sum;
}
int main()
{
    cin>>n>>k;
    ll x1= fastpow1(k,n);
    ll x2= fun(2*n,n);
    ll x3=fun(2*n,n-1);
    x3=(x2+N-x3)%N;
    ans=(x3*x1)%N;
    cout<<ans;
    return 0;
}

H题：

根据给出的路径，计算每条边权的期望值，然后求和，结果在用费马小定理处理

费马小定理：

b/a mod p

==>b*a^-1 mod p

==> b*a^p-2 mod p

此代码在处理期望部分可能存在bug,(对于分布期望不会求解。。。。。)

//
// Created by LiuHongzhe on 2021/11/30.
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k;
ll x,y,z;
int b[300005];
ll ans;
ll N=998244853;
vector<vector<vector<ll>>>cnt;
ll fastpow1(ll a, ll n) {//快速幂
    ll base = a;
    ll res = 1;
    while(n) {
        if(n & 1)
            res = (base * res) % N;
        base = (base * base) % N;
        n >>= 1;
    }
    return res;
}
void method01(){
    ll i,j;
    for(i=0;i<=n;i++)//打表
    {
        vector<vector<ll>>cnt1;
        for(j=0;j<=i;j++)
        {
            vector<ll>cnt2;
            cnt1.push_back(cnt2);
        }
        cnt.push_back(cnt1);
    }
    ll u,v,w;
    for(i=0;i<m;i++)//数据录入
    {

        cin>>u>>v>>w;
        if(u<v)
            swap(u,v);
        cnt[u][v].push_back(w);
    }
}
void method02(){
    ll i;
    for(i=0;i<k;i++)
    {
        cin>>b[i];
    }
}
void method03(){//求x,y
    ll i,j;
    ll sum=1;
    y=1;
    for(i=k-1;i>0;i--)
    {
        ll dx=b[i];
        ll dy=b[i-1];
        if(dx<dy)
            swap(dx,dy);
        ll len=cnt[dx][dy].size();
        y=(y*len)%N;
        if(len==0)
        {
            cout<<"Stupid Msacywy!"<<endl;
            exit(0);
        }
    }
    x=0;
    for(i=k-1;i>0;i--)
    {
        ll dx=b[i];
        ll dy=b[i-1];
        if(dx<dy)
            swap(dx,dy);
        ll add=0;
        for(j=0;j<cnt[dx][dy].size();j++)
        {
            add=add+cnt[dx][dy][j];
        }
        ll len=cnt[dx][dy].size();
        ll de=(add*sum*y/len)%N;
        x=(x+de)%N;
        sum=(sum*10)%N;
    }
}
void method04(){
    // x/y;
    ll ans=fastpow1(y,N-2);
    ans=(ans*x)%N;
    cout<<ans;
}
int main()
{
    cin>>n>>m>>k;
    method01();
    method02();
    method03();
    method04();
    return 0;
}

C题：

题目大意：给定x0;且xn=(a*x(n-1)+b)%m;是否存在xi是给定的一个数（给定的数<m）

此题涉及线性同余方程求解和BSGS算法

然后自己手动推理了一下公式的转化

G题：

题目大意：给一个01矩阵（其中空缺位置为-1）和每行每列的异或值，复原此矩阵。

用到同E题的异或性质，做法类似玩数独游戏，每次对某行或者某列只有一个未知元素的优先处理。既先对处理位置做一个拓扑排序，然后依次处理即可。（但我不会写拓扑排序。。。）

后面补题后更新

下面是官方简要题解和省赛原题

链接：https://pan.baidu.com/s/1e5w2P6tbPSmR-NfazYdXNA
提取码：uwd9

比赛终榜

第十五届吉林省大学生程序设计竞赛 - 正式赛

这篇关于第十五届吉林省大学生程序设计竞赛的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

第十五届吉林省大学生程序设计竞赛

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯