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

最近刚打完吉林省程序设计竞赛,自己比较菜,成绩不是很好,拖累了两位队友,其中一位队友保研,并在比赛前一天拿到了百度的实习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

比赛终榜

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

上一篇:javascript 浏览器定位


下一篇:在基类中公有,子类私有继承,main()中不能被访问