首页 > 编程语言 >2019 山东省大学生程序设计竞赛

2019 山东省大学生程序设计竞赛

时间：2023-08-02 13:01:01浏览次数：39  
标签：竞赛 return int solve long 2019 pair 程序设计 mod

A. Calandar

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
typedef pair<int,int> pii;
typedef pair<string,int> psi;


int res = LLONG_MIN;
map<string,int> cc;
map<int,string> tt;

void solve() {
    int ya , ma , da;
    string s;
    cin >> ya >> ma >> da >> s;
    int yb ,mb,db;
    cin >> yb >> mb >> db;
    int cnt = (yb*12 + mb)*30 + db;
    cnt -= (ya * 12 + ma) * 30 + da;

    int t =  cc[s];
    t = ( t + cnt );
    t = ( t % 5 + 5 ) % 5;
    cout << tt[t] << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    cc["Monday"] = 1;
    cc["Tuesday"] = 2;
    cc["Wednesday"] = 3;
    cc["Thursday"] = 4;
    cc["Friday"] = 0;

    tt[1] = "Monday";
    tt[2] = "Tuesday";
    tt[3] = "Wednesday";
    tt[4] = "Thursday";
    tt[0] = "Friday";



    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

B. Flipping Game

把初始状态和最终状态做异或，然后当做初始状态，此时最终状态是全0。然后我们发现其实 1 的位置对答案没有影响。这样的话我们的状态就不需要设计位置，只记录数量即可。

\(f[i][j]\)表示\(i\)次操作后剩\(j\)个1 的方案数。答案自然就是\(f[k][0]\)。考虑如何计算转移枚举\(l\)表示第次\(i\)操作操作了\(l\)个 0，\(m-l\)个 1，则\(i-1\)次操作后剩下\(x\)个 1，则有\(x+l-(m-l)=j,x=j-2l+m\)，所以状态的转移为

\[f[i][j]=\sum f[i-1][x] \times C_{n-x}^{l}\times C_x^{m-l} \]

#include<bits/stdc++.h>

using namespace std;

#define int long long
const int mod = 998244353;
const int N = 105;
int fact[N], invFact[N];

int power(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod, y >>= 1;
    }
    return ans;
}

int inv(int x) {
    return power(x, mod - 2);
}

int C(int x, int y) {
    return fact[x] * invFact[x - y] % mod * invFact[y] % mod;
}

void init() {
    fact[0] = 1, invFact[0] = inv(1);
    for (int i = 1; i < N; i++)
        fact[i] = fact[i - 1] * i % mod, invFact[i] = inv(fact[i]);
    return;
}


void solve() {
    int n, m, k, s0 = 0;
    string s1, s2;
    cin >> n >> k >> m >> s1 >> s2;
    for (int i = 0; i < n; i++)
        s0 += s1[i] != s2[i];
    vector f(k + 1, vector(n + 1, 0));
    f[0][s0] = 1;
    for (int i = 1; i <= k; i++)
        for (int j = 0; j <= n; j++) // 第 i 次操作后有j 个 1 的方案数
            for (int l = 0, x; l <= m && l <= j ; l++) { // l
                x = j - 2 * l + m;
                if (x < 0 || x > n) continue;
                if( n - x < l || x < m - l ) continue;
                f[i][j] = (f[i][j] + f[i - 1][x] * C(n - x, l) % mod * C(x, m - l) % mod) % mod;
            }
    cout << f[k][0] << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    init();
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C. Wandering Robot

手推样例就可以发现，答案只能出现在第一轮操作和最后一轮操作中。每一轮操作可以移动的向量是相同的。我们可以推出第一轮移动过程中所有的点，然后用向量运算找到最后一轮的点，然后取最大值即可。

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
typedef pair<int, int> pii;
typedef pair<string, int> psi;


void solve() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    int x = 0, y = 0;
    int res = 0;
    vector<pair<int, int>> t;
    for (auto i: s) {
        if (i == 'L') x--;
        else if (i == 'R') x++;
        else if (i == 'U') y++;
        else y--;
        res = max(res, abs(x) + abs(y));
        t.emplace_back(x, y);
    }
    for (auto [x, y]: t) {
        x += t.back().first * (k - 1), y += t.back().second * (k - 1);
        res = max(res, abs(x) + abs(y));
    }
    cout << res << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

D. Game on a Graph

可以发现的是，两个人的最优操作会导致两个人一定会吧图删成一棵树，所以我们判断图是否联通，然后再计算多少次可以删成树即可。

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
typedef pair<int, int> pii;
typedef pair<string, int> psi;

class dsu{
private:
    vector<int> fa;
public:
    dsu( int n = 1 ){
        fa = vector<int>( n+1 , -1 );
    }
    int getfa( int x ){
        if( fa[x] < 0 ) return x;
        return fa[x] = getfa( fa[x] );
    }
    void merge( int x , int y ){
        x = getfa(x) , y = getfa(y);
        if( x == y ) return ;
        if( fa[x] > fa[y] ) swap( x , y );
        fa[x] += fa[y] , fa[y] = x;
    }
    bool same( int x , int y ){
        x = getfa(x) , y = getfa(y);
        return ( x == y );
    }
};

void solve() {
    int k;
    string s;
    cin >> k >> s;
    int n , m ;
    cin >> n >> m;
    dsu d(n);
    for( int i = 1 , x , y ; i <= m ; i ++ )
        cin >> x >> y , d.merge(x ,y);
    for( int i = 1 ; i < n ; i ++ ){
        if( d.same( 0 , i ) ) continue;
        cout << (s.front()=='1')+1 << "\n";
        return;
    }
    int t = m - n + 2;
    t = (t - 1) % k;
    cout << (s[t]=='1') + 1 << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

E. BaoBao Loves Reading

对于第\(i\)次看的书\(a_i\)，统计出\(last[a_i]\)表示上一次看\(a_i\)的时间，记\(g[i]\)为\([last[a_i]+1,i-1]\)之间从书架拿书的次数。如果\(g[i]\ge k\)，说明第\(i\)看书必须从书架上取书。我们可以枚举\(k\)的值，统计出$g[i]\ge k $的数量就是答案，这个可以用桶加后缀和实现。

现在问题就落在了如何求\(g[i]\)，这个询问区间中元素种类的个数可以用树状数组维护元素最后出现的下标即可。

#include<bits/stdc++.h>

using namespace std;

#define int long long
int mod;

int power(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod, y >>= 1;
    }
    return ans;
}

struct BinaryIndexedTree {
#define lowbit(x) ( x & -x )
    int n;
    vector<int> b;

    BinaryIndexedTree(int n) : n(n), b(n + 1) {};

    void add(int i, int y) {
        for (; i <= n; i += lowbit(i)) b[i] += y;
        return;
    }

    int calc(int i) {
        int sum = 0;
        for (; i; i -= lowbit(i)) sum += b[i];
        return sum;
    }

    int calc(int l, int r) {
        return calc(r) - calc(l - 1);
    }

};

void solve() {
    int n;
    cin >> n;
    vector<int> f(n+1), last(n+1);
    BinaryIndexedTree bit(n);
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        if (last[x] == 0) f[n]++;
        else f[bit.calc(last[x]+1, i-1)]++, bit.add(last[x], -1);
        bit.add(i, 1), last[x] = i;
    }
    for( int i = n-1 ; i >= 1 ; i -- ) f[i] += f[i+1];
    for( int i = 1 ; i <= n ; i ++ ) cout << f[i] << " \n"[i==n];
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

F. Stones in the Bucket

最优解一定变成平均数。注意总和除 n 可能会产生余数，余数部分是必须用操作一删掉的。

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
typedef pair<int,int> pii;
typedef pair<string,int> psi;

void solve() {
    int n , k = 0;
    cin >> n;
    vector<int> a(n);
    for( auto & i : a )
        cin >> i , k += i;
    k /= n;
    int res = 0;
    for( auto i : a )
        if( i > k ) res += i - k;
    cout << res << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

H. Tokens on the Segments

首先 y 值是无用的。

做一个贪心，对于左端点相同的区间，选择右端点最小的。

#include<bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> e(n);
    for (auto &[l, r]: e)
        cin >> l >> r;
    sort(e.begin(), e.end());
    int l = 0, pos = 0, res = 0;
    priority_queue<int, vector<int>, greater<int>> q;

    while (pos < n) {
        if (q.empty() && e[pos].first > l) l = e[pos].first;
        while (pos < n && e[pos].first <= l) q.push(e[pos].second), pos++;
        while (!q.empty() && q.top() < l) q.pop();
        if (!q.empty() && q.top() >= l) q.pop(), l++, res++;
    }
    while (!q.empty()) {
        if( q.top() >= l ) l ++ , res ++;
        q.pop();
    }
    cout << res << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

K. Happy Equation

打表知道\(a\)为奇数时，答案为\(1\)

考虑当\(a\)为偶数是，\(a=t2^k\),所以\(a^x=t^x2^{kx}\)。所以当\(kx>p\)时，\(a^x\equiv 0(\mod 2^p)\)

再来考虑\(x\)，首先当\(x<p\)时，可以直接暴力求解，当\(x>p\)时，只考虑\(x^a\equiv 0 (\mod 2^p)\)的情况。

此时\(x\)只能为偶数，令\(x=t2^k\),则\(x^a=t^a2^{ka}\)，解\(ka\ge p\)得\(k\ge \left \lceil \frac p a \right \rceil = k’\)，所以\(x\)至少为\(2^{k’}\),在\([0,2^p]\)中\(x\)的倍数有\(\frac{2^p}{2^{k’}}=2^{p-k’}\)，还要减去\([0,p-1]\)中的倍数。

#include<bits/stdc++.h>

using namespace std;

#define int long long
int mod;

int power(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod, y >>= 1;
    }
    return ans;
}

void solve() {
    int a, p;
    cin >> a >> p;
    mod = (1 << p);

    if (a & 1) {
        cout << "1\n";
        return;
    }

    int res = 0;
    for (int i = 1; i < p; i++)
        res += power(a, i) == power(i, a);
    int k = (p + a - 1 ) / a;
    res += (1ll << (p - k)) - (p - 1) / ( 1ll << k );
    cout << res << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

L. Median

其实我们发现，不同的联通块之间不会产生任何影响，我们只需要考虑单个联通块内部，我们可以用搜索统计处每个点有多少个点一定比当前点小，多少个点一定比当前点大，只要数量没有超过半数，就一定存在合法的解。

但是要注意，题目可能会出现本身矛盾的情况，所以判断图中是否存在环这点用拓扑序求解就好了。

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
typedef pair<int, int> pii;
typedef pair<string, int> psi;

vector<int> vis;

void dfs(int x, const vector<vector<int>> &e) {
    for (int y: e[x]) {
        if (vis[y]) continue;
        vis[y] = 1, dfs(y, e);
    }
    return;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> e(n + 1), g(n + 1);
    vector<int> lower(n + 1), upper(n + 1);
    vector<int> inner(n + 1);
    for (int i = 1, x, y; i <= m; i++)
        cin >> x >> y, e[x].push_back(y), g[y].push_back(x), inner[y]++;

    int cnt = 0;
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (inner[i] == 0) q.push(i), cnt++;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (auto y: e[x]) {
            inner[y]--;
            if (inner[y] == 0)cnt++, q.push(y);
        }
    }
    if (cnt != n) {
        for (int i = 1; i <= n; i++)
            cout << 0;
        cout << "\n";
        return;
    }

    for (int i = 1; i <= n; i++) {
        vis = vector<int>(n + 1);
        dfs(i, e);
        for (int j = 1; j <= n; j++)
            lower[i] += vis[j];
    }
    for (int i = 1; i <= n; i++) {
        vis = vector<int>(n + 1);
        dfs(i, g);
        for (int j = 1; j <= n; j++)
            upper[i] += vis[j];
    }


    for (int i = 1, T = n / 2; i <= n; i++) {
        if (lower[i] <= T and upper[i] <= T) cout << 1;
        else cout << 0;
    }
    cout << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

M. Sekiro

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
typedef pair<int,int> pii;
typedef pair<string,int> psi;

void solve() {
    int n , k;
    cin >> n >> k;
    for( ; n > 1 && k ; k -- )
        n = ( n + 1 ) / 2 ;
    cout << n << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

标签：竞赛,return,int,solve,long,2019,pair,程序设计,mod
From： https://www.cnblogs.com/PHarr/p/17600388.html

相关文章

  • Windows Server 2019 OVF, updated Jul 2023 (sysin) - VMware 虚拟机模板
    WindowsServer2019OVF,updatedJul2023(sysin)-VMware虚拟机模板2023年7月版本更新，现在自动运行sysprep，支持ESXiHostClient部署更新日期：FriJul28202317:12:00GMT+0800，阅读量:6244请访问原文链接：https://sysin.org/blog/windows-server-2019-ovf/，查看最......
  • Windows Server 2019 中文版、英文版下载 (updated Jul 2023)
    WindowsServer2019中文版、英文版下载(updatedJul2023)WindowsServer2019Version1809，2023年7月更新请访问原文链接：https://sysin.org/blog/windows-server-2019/，查看最新版。原创作品，转载请保留出处。作者主页：sysin.org本站将不定期发布官方原版风格月度更新IS......
  • 2023 CISCN 第十六届全国大学生信息安全竞赛 初赛 WriteUp
    2023CISCN第十六届全国大学生信息安全竞赛初赛WriteUp引言第十六届全国大学生信息安全竞赛——创新实践能力赛http://www.ciscn.cn/competition/securityCompetition?compet_id=38时光荏苒，又是一年一度的国赛了！这篇writeup是xdlddw战队的队友一起写的，非常感谢队......
  • 基于JAVA的程序设计语言网上考试系统
    科技进步的飞速发展引起人们日常生活的巨大变化，电子信息技术的飞速发展使得电子信息技术的各个领域的应用水平得到普及和应用。信息时代的到来已成为不可阻挡的时尚潮流，人类发展的历史正进入一个新时代。在现实运用中，应用软件的工作规则和开发步骤，采用Java技术建设VisualC程序设计......
  • [GUET-CTF2019]number_game
    [GUET-CTF2019]number_game  打开题目，立刻定位关键函数for(i=0;i<=4;++i){for(j=0;j<=4;++j){for(k=j+1;k<=4;++k){if(*(&unk_601060+5*i+j)==*(&unk_601060+5*i+k))......
  • 暑期竞赛培训 Day 11—— < 树状数组 >
    本文大部分内容来自教练的博客[https://www.cnblogs.com/hbhszxyb/]。树状数组一、适用范围：树状数组是一个查询和修改复杂度都为log(n)的数据结构，常常用于查询任意区间的所有元素之和。与前缀和的区别是支持动态修改,log(n)的时间进行修改，log(n)查询。支持如下操作：[1]单......
  • Windows漏洞CVE-2019-0708
    Windows漏洞CVE-2019-0708标签（空格分隔）：网络攻防技术1.python-exp攻击步骤(1)开启Windows7的远程桌面服务：在windows7系统中依次选择【控制面板】→【系统和安全】→【允许远程访问】打开远程访问服务。(2)下载漏洞利用脚本：在互联网上搜索CVE-2019-0708相关的漏洞利用脚本，可......
  • 【230730-3】已知:2^a=5,2^b=10,2^c=80 求:2019a-4039b+2020c=?
    ......
  • 暑期竞赛配训 Day 1，本蒟蒻的第一篇题解qwq！
    洛谷P8725[蓝桥杯2020省AB3]画中漂流：-[1]读题：在梦境中，你踏上了一只木䇝，在江上漂流。根据对当地的了解，你知道在你下游D米处有一个峡谷，如果你向下游前进大于等于D米则必死无疑。现在你打响了急救电话，T秒后救援队会到达并将你救上岸。水流速度是1m/s，你现在有M点体力......
  • 2020年百度程序设计大赛初赛
     解题思路：签到题。首先找出最少补充x[i]需要消耗掉多少瓶水。从而在得到摄入的最小值importjava.util.Scanner;importjava.util.Collections;importjava.util.ArrayList;importjava.util.StringTokenizer;publicclassMain{publicstaticvoidmain(String[]arg......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99