首页 > 编程语言 >广东工业大学文远知行杯新生程序设计竞赛(重现赛)

广东工业大学文远知行杯新生程序设计竞赛(重现赛)

时间:2022-12-17 18:23:30浏览次数:62  
标签:知行杯 int double LL 文远 cin long ans 程序设计

A. 迫真算法部・ACの裏技 (Nowcoder49259 A)

题目大意

给定键盘输入顺序,问是否按了CTRL C后按了 CTRL V

解题思路

模拟即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    bool ok = false, haveC = false, haveV = false;
    while(n--){
        string s;
        cin >> s;
        if (s.size() == 4)
            ok = true;
        else if (s.size() == 6)
            ok = false;
        else if (ok && s[0] == 'C')
            haveC = true;
        else if (ok && s[0] == 'V' && haveC)
            haveV = true;
    }
    if (haveV)
        cout << "Yes" << '\n';
    else 
        cout << "No" << '\n';

    return 0;
}



B. qqdd抢餐券 (Nowcoder49259 B)

题目大意

给定\(n\)条线段覆盖,输出所有被少于\(k\)条线段覆盖的区间。

解题思路

范围不大,直接计数即可,也可以差分。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 1e5 + 8;
int cnt[N], t, k;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    cin >> t >> k;
    for(int i = 1; i <= t; ++ i){
        int l, r;
        cin >> l >> r;
        cnt[l] ++;
        cnt[r + 1] --;
    }
    vector<pair<int, int>> ans;
    int st = 0;
    bool ok = true;
    int sum = 0;
    for(int i = 0; i <= 120; ++ i){
        sum += cnt[i];
        if (ok && sum >= k){
            ans.push_back({st, i - 1});
            ok = false;
        }else if (sum < k){
            if (!ok)
                st = i;
            ok = true;
        }
    }
    if (ok)
        ans.push_back({st, 120});
    cout << ans.size() << '\n';
    for(auto &i : ans)
        cout << i.first << '-' << i.second << '\n';

    return 0;
}



C. 智慧之神的简单题 (Nowcoder49259 C)

题目大意

问有多少个正整数组满足\(a+b+c \leq S, a \times b \times c \leq T\)

解题思路

范围不大,直接计数即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int s, t;
    cin >> s >> t;
    int ans = 0;
    FOR(i, 0, s + 1)
        FOR(j, i, s + 1)
            FOR(k, j, s + 1)
                ans += (i + j + k <= s && 1ll * i * j * k <= t);
    cout << ans << '\n';

    return 0;
}



D. 赚硬币 (Nowcoder49259 D)

题目大意

\(n\)场比赛,第一名获 \(A\)元,第二名获 \(B\)元,第三名获 \(C\)元。现在 \(Alice\)获 \(27\)元, \(Bob,Mazige\)获 \(14\)元。且 \(Bob\)有一场第一名, \(Mazige\)没有一场第一名。问 \(n\)的大小以及某场的第二名是谁。

解题思路

由于\(n(A + B + C) = 14 + 14 + 27 = 55\)。而 \(A > B > C\),因此只能 \(n = 5, A+B+C = 11\)

感觉上其他场互不区分,即理论上结果应该相同,盲猜就是 \(M\)。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    cout << "5 Mazige" << '\n';

    return 0;
}



E. 柒小队打麻将 (Nowcoder49259 E)

题目大意

给定\(n, k\),问 \(n^{9^{k}}\)模10等于多少。

解题思路

根据欧拉定理,\(n^{9^{k}} \mod 10 = n^{9^{k} \mod \varphi(10)} \mod 10\)

由于\(\varphi(10) = 4\),而 \(9^{k} \mod 4 = 1\),所以 \(n^{9^{k}} \mod 10 = n \mod 10\)。

直接输出最后一位即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        string n, k;
        cin >> n >> k;
        cout << n.back() << '\n';
    }

    return 0;
}



F. 亚子和燐子的game (Nowcoder49259 F)

题目大意

给定\(n\)个数字,进行一种操作,为

  • 选择一个不小于\(3\)的数字,令其变为原来的 \(\frac{1}{3}\)向下取正。

最后让所有数相同,问最小的操作次数。

解题思路

每个数只能操作\(\log\)次,依次记录每个数变成可变成的数所需要的次数。

最后看哪些数是所有数都能变到的,取操作次数最小的即可。

复杂度为\(O(n\log^2 n)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const LL inf = 1e18 + 7;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    map<LL, LL> cnt, ans;
    for(int i = 0; i < n; ++ i){
        LL x;
        cin >> x;
        LL cc = 0;
        while(x >= 3){
            ans[x] += cc;
            cnt[x] ++;
            ++ cc;
            x /= 3;
        }
    }
    LL val = inf;
    for(auto &i : cnt)
        if (i.second == n)
            val = min(val, ans[i.first]);
    if (val == inf)
        cout << "Lose" << '\n';
    else 
        cout << val << '\n';

    return 0;
}



G. 我最好的朋友 (Nowcoder49259 G)

题目大意

给定\(1\times n\)的格子,两人轮流操作,每次操作可以选择一个格子放置一个棋子,同时可以选择对称格子上也放一个棋子(如果原来该格没棋子),也不可以不放。

问两者绝顶聪明的情况下,两者谁胜。

解题思路

把问题拆解成有若干个一对和一个单个(如果\(n\)是奇数),操作就是

  • 拿走一对
  • 拿走一个
  • 将一对拆成两个单个的,并拿走一个

打表得知当\(n\)是 \(4\)的倍数时后手必胜,否则先手必胜。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 200;
int dp[N][N];

int solve(int x, int y){
    if (dp[x][y] != -1)
        return dp[x][y];
    int v1 = 1, v2 = 1, v3 = 1;
    if (x > 0){
        v1 = solve(x - 1, y);
        v2 = solve(x - 1, y + 1);
    }
    if (y > 0){
        v3 = solve(x, y - 1);
    }
    if (v1 == 0 || v2 == 0 || v3 == 0)
        dp[x][y] = 1;
    else 
        dp[x][y] = 0;
    return dp[x][y];
}

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    // memset(dp, -1, sizeof(dp));
    // dp[0][0] = 0;
    // for(int i = 0; i < N; ++ i)
    //     for(int j = 0; j < N; ++ j){
    //         solve(i, j);
    //     }
    // for(int i = 0; i < N; ++ i){
    //     debug(i * 2, dp[i][0]);
    //     debug(i * 2 + 1, dp[i][1]);
    // }
    int t;
    cin >> t;
    while(t--){
        LL n;
        cin >> n;
        if ((n & 1) || ((n / 2) & 1)){
            cout << "Mazige" << '\n';
        }else{
            cout << "Not Mazige" << '\n';
        }
    }

    return 0;
}



H. 马子哥的奖金 (Nowcoder49259 H)

题目大意

给定\(n\)个数,要求选择 \(k\)个数,其乘积最大,输出该最大值模\(10^9+7\)。

负数取模规则为正数取模的相反数。

解题思路

分类讨论下。

按绝对值排序,先取前\(k\)个绝对值最大的。

如果是正数则皆大欢喜。

如果是负数的话,为了变为正数,有两种操作

  • 已选的绝对值最小的负数未选的绝对值最大的正数交换(如果有)
  • 已选的绝对值最小的正数未选的绝对值最大的负数交换(如果有)

如果无法变为正数,则取绝对值最小的\(k\)个

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const LL mo = 1e9 + 7;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<LL> a(n);
    for(auto &i : a){
        cin >> i;
    }
    sort(a.begin(), a.end(), [](LL a, LL b){
            return abs(a) > abs(b);
            });
    int kp = -1, kn = -1;
    int cnt = 0;
    for(int i = 0; i < k; ++ i){
        cnt ^= (a[i] < 0);
        if (a[i] > 0)
            kp = i;
        else if (a[i] < 0)
            kn = i;
    }
    // first k
    if (cnt == 0){
        LL ans = 1;
        for(int i = 0; i < k; ++ i)
            ans = ans * abs(a[i]) % mo;
        cout << ans << '\n';
        return 0;
    }
    int kkp = -1, kkn = -1;
    for(int i = k; i < n; ++ i){
        if (kkp == -1 && a[i] > 0)
            kkp = i;
        if (kkn == -1 && a[i] < 0)
            kkn = i;
    }
    // swap biggest last positive with smallest k neg
    if (kkp != -1 && (kkp < kkn || kkn == -1 || kp == -1)){
        LL ans = 1;
        for(int i = 0; i < k; ++ i){
            if (i == kn)
                continue;
            ans = ans * abs(a[i]) % mo;
        }
        ans = ans * a[kkp] % mo;
        cout << ans << '\n';
        return 0;
    }
    // swap biggest last negative with smallest k positive
    if (kkn != -1 && kp != -1){
        LL ans = 1;
        for(int i = 0; i < k; ++ i){
            if (i == kp)
                continue;
            ans = ans * abs(a[i]) % mo;
        }
        ans = ans * abs(a[kkn]) % mo;
        cout << ans << '\n';
        return 0;
    }
    // ans < 0, last k
    LL ans = 1;
    for(int i = n - 1; i > n - 1 - k; -- i){
        ans = ans * abs(a[i]) % mo;
    }
    cout << -ans << '\n';

    return 0;
}



I. 奇迹和魔法都是存在的 (Nowcoder49259 I)

题目大意

给定一个长度为\(n\)的数组\(a\),有 \(q\)次询问,每次询问给定一个区间 \([l,r]\),问对该区间进行若干次操作后,最终剩下一个数的情况(原下标不同,情况就不同)。

操作为: 选择一个区间\([l,r]\),保留其中最大的数,或者第一个数,其余数都删掉。

解题思路

从简考虑,考虑操作的区间为\(2\)。对于该区间的两个数\(a\), \(b\),如果 \(a <= b\),则留哪个都可以,反之 \(b\)必定会被删掉。

由此可得出最终能留下来的数,都是其值大于等于 \(a[l]\),其答案就是其个数。

由于询问数不多,对于每个询问直接暴力答案即可。时间复杂度为\(O(nq)\)

如果询问数较大,可用莫队+权值树状数组离线或主席树在线求解。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, t;
    cin >> n >> t;
    vector<int> a(n);
    for(auto &i : a)
        cin >> i;
    while(t--){
        int l, r;
        cin >> l >> r;
        -- l;
        -- r;
        int ans = 0;
        for(int i = l; i <= r; ++ i)
            ans += (a[i] >= a[l]);
        cout << ans << '\n';
    }

    return 0;
}



J. 狐臭的等比数列 (Nowcoder49259 J)

题目大意

给定\(n\)个数,问包含这\(n\)个数的等比数列的最小项数值。

解题思路

被最后一题耗了太多时间,这题还没怎么看,晚点补。

神奇的代码



K. 玩石头 (Nowcoder49259 K)

题目大意

给定\(n\)块石头的重量及其时髦值,要求垒石头,要求下面的石头重量严格大于上面所有石头重量的和。问时髦值的最大值。

解题思路

由于每次所需要的石头重量翻倍,由于石头重量最多\(10^9\),因此最多就选择\(30\)个石头,其时髦值和最大也就 \(30 \times 100 = 30000\) ,因此设\(dp[i]\)表示时髦值和为 \(i\)时候,最下面的石头的重量的最小值,直接转移即可。

注意要从重量小到大考虑石头。

时间复杂度为\(O(3000n)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const LL inf = 1e18;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<LL> dp(3001, inf);
    dp[0] = 0;
    vector<pair<LL, int>> f(n);
    for(auto &i : f)
        cin >> i.first >> i.second;
    sort(f.begin(), f.end(), [](const pair<LL, int>& a, const pair<LL, int>& b){
            return a.first < b.first;
            });
    for(int i = 0; i < n; ++ i){
        LL a;
        int b;
        a = f[i].first;
        b = f[i].second;
        for(int j = 3000; j >= b; -- j){
            if (a > dp[j - b])
                dp[j] = min(dp[j], dp[j - b] + a);
        }
    }
    int ans = 0;
    for(int i = 3000; i >= 0; -- i)
        if (dp[i] != inf){
            ans = i;
            break;
        }
    cout << ans << '\n';
    return 0;
}



L. jjgg的难题 (Nowcoder49259 L)

题目大意

给定\(n,s\),求最小的进制 \(p\),满足 \(n\)在 \(p\)进制下各个数位的和为 \(s\)

解题思路

注意\(n \leq 10^{10}\)

先暴力枚举\(p\)从\(1\)到\(10^5\)判断。

当 \(p\)大于 \(10^5\)时, \(n\)在 \(p\)进制下最多两位 (\(p^2 > 10^{10} > n\))

设 \(a = n \% p, b = n / p\),此时 \(b\)的取值只有 \(1\)到\(10^5\)种情况,枚举该\(b\),则 \(a = s - b\),判断\(n - a\)是否被 \(b\)整除,是的话 \(p = (n - a) / b\) ,取最小的\(p\)即可。

注意 \(n == s\)时 \(p = n + 1\)的特殊情况。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const LL inf = 1e18;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    LL n, s;
    cin >> n >> s;
    LL ans = inf;
    auto calc = [](LL x, int base){
        LL cnt = 0;
        while(x){
            cnt += x % base;
            x /= base;
        }
        return cnt;
    };
    for(int i = 2; i <= 100000; ++ i){
        if (calc(n, i) == s){
            ans = i;
            break;
        }
    }
    if (ans == inf){
        for(int i = 1; i <= 100000; ++ i){
            LL mod = s - i;
            if (n > mod && (n - mod) % i == 0){
                LL p = (n - mod) / i;
                if (p != 1){
                    ans = min(ans, p);
                }
            }
        }
    }

    if (ans == inf)
        ans = -1;
    if (n == s && ans == -1)
        ans = n + 1;
    cout << ans << '\n';

    return 0;
}



M. Poppin'Party的star★ (Nowcoder49259 M)

题目大意

给定一个矩形长宽\(a,b\),问能画出的最大五角星的面积。

解题思路

这个五角星竟然可以旋转。

百度了下发现在正方形的情况下五角星还是以一种独特的角度摆放的。

猜测矩阵也可以切掉多余的当成正方形来做,结果好像不对。

鉴定:不可做。

不神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)

const long double inf = 1e18;
const long double pi = acos(-1);
const long double sin18 = sin(18.0 / 180 * pi);
const long double sin36 = sin(36.0 / 180 * pi);
const long double sin72 = sin(72.0 / 180 * pi);
const long double sin108 = sin(108.0 / 180 * pi);
const long double cos18 = cos(18.0 / 180 * pi);
const long double cos72 = cos(72.0 / 180 * pi);
const long double cos108 = cos(108.0 / 180 * pi);
const long double tan54 = tan(54.0 / 180 * pi);
const long double eps = 1e-10;

long double calcB(long double a){
    return 2.0 * a * sin18;
}

long double hoc(long double a){
    long double b = calcB(a);
    return a + a + b;
}

long double vec(long double a){
    return hoc(a) * cos18;
}

long double star(long double a){
    return 5.0 * 0.5 * a * a * sin36;
}

long double wubian(long double b){
    return 5.0 * 0.5 * b * b / 2 * tan54;
}


long double area(long double a){
    long double b = calcB(a);
    long double s1 = star(a);
    long double s2 = wubian(b);
    return s1 + s2;
}

long double solve(long double (*f)(long double), long double up){
    long double l = 0, r = up;
    while(l + eps < r){
        long double mid = (l + r) / 2;
        if (f(mid) <= up)
            l = mid;
        else 
            r = mid;
    }
    return l;
}

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    long double x, y;
    cin >> x >> y;
    long double ff = min(x, y);
    long double a = sqrt(ff * ff / ((sin72 * sin72 + (1 + cos72) * (1 + cos72)) * sin108 * sin108 * 2 * (1 - cos108)));
    long double b = min(solve(hoc, x), solve(vec, y));

    // cout << fixed << setprecision(10) << area(a) << ' ' << area(b) << '\n';
    // cout << fixed << setprecision(10) << area(a) << '\n';

    return 0;
}



标签:知行杯,int,double,LL,文远,cin,long,ans,程序设计
From: https://www.cnblogs.com/Lanly/p/16989312.html

相关文章

  • python面向对象程序设计
    python-面向对象程序设计1:类类就是一个图纸类不可以直接使用类中的行为叫类方法类中的特性叫类属性2:对象对象时根据类创建出来的,可以直接使用一个类可以创建多个对象每......
  • 面对对象程序设计
    classGeese:'''大雁类'''def__init__(self,beak,wing,claw):print('我是大雁类!我有以下特征:')print(beak)print(wing)p......
  • 程序设计模式急救笔记
    打完游戏发现考试内容一点没看,紧急抢救,精神状态不甚正常,慎读。例子有的不是很好,为了考试的时候抄个UML图方便罢了。0.UML图1.关联关系类A用到了类B,A->B类A用到了类B......
  • 循环结构程序设计
    循环结构程序设计while循环语句C语言包含3大基本结构:顺序结构、选择结构、循环结构while语句的一般形式:while(表达式)语句只有当循环条件表达式为真,就执行循环......
  • 【读书笔记】Windows程序设计5
    Windows程序设计一、起步1.1.第一个Windows程序main.c#include<windows.h>intWINAPIWinMain(HINSTANCEhInstance,HINSTANCEhPrevInstance,PSTRszCmdLine,in......
  • 汇编语言程序设计,计算比赛成绩
    一、设计内容与设计要求1.课程设计目的:《汇编语言程序设计》是计算机专业的重要的专业基础课,通过本课程设计使学生进一步巩固课堂所学,全面熟悉、掌握8088宏汇编语言程序设计......
  • 选择结构程序设计
    选择结构程序设计if语句的一般形式if语句包含3种形式:if(表达式)语句表达式:可以是关系表达式、逻辑表达式,甚至是数值表达式关系表达式:两个数值进行比较的式子......
  • 顺序程序设计
    顺序程序设计三种基本结构顺序结构:代码从前往后依次按顺序运行选择结构:根据条件选择运行某部分代码循环结构:反复执行某部分代码数据形式常量和变量数据有两种表现......
  • 【补题】2022年中国大学生程序设计竞赛女生专场
    比赛链接2022年中国大学生程序设计竞赛女生专场A.减肥计划签到题暴力模拟,如果模拟到最重的人到队首还没有人连续获胜\(k\)轮,那么答案显然就是最重的人。方便起见可以......
  • 2022-2023-1 20221319《计算机基础与程序设计》课程总结
    班级:https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP作业要求:https://www.cnblogs.com/rocedu/p/9577842.html#WEEK15作业目标:课程总结作业正文:https://www.cnb......