首页 > 其他分享 >《看了受制了》第二十天,7道题,合计97道

《看了受制了》第二十天,7道题,合计97道

时间:2023-09-19 23:59:55浏览次数:43  
标签:道题 return int res ll 受制 include 97 Mod

2023年9月19日

牛客,ACWING图论!思前想后,这个图论一定要从00.1!!!

牛客周赛 游游的字符串

题目理解

输出kyou,然后剩下的都是o即可

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#define x first
#define y second
using namespace std;
typedef long long ll;

const int Mod = 1e9 + 7;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){ return qmi(x, Mod - 2);}
ll mo(ll x){ return (x % Mod + Mod) % Mod;}


int main() {

    int n, k;
    cin >> n >> k;

    if(k * 3 > n)
    {
        cout << -1;
        return 0;
    }

    for(int i = 1; i <= k ; i++)
        cout << "you";
    
    n -= k * 3;

    while(n--)
        cout << "o";

    return 0;
}

牛客周赛 游游的整数拆分

题目理解

需要判断,n中能有几个3的倍数,如果n就是3的倍数,那么是个数 - 1,不然是个数 * 2

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#define x first
#define y second
using namespace std;
typedef long long ll;

const int Mod = 1e9 + 7;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){ return qmi(x, Mod - 2);}
ll mo(ll x){ return (x % Mod + Mod) % Mod;}


int main() {

    ll n;
    cin >> n;

    if(n <= 3)
    {
        cout << 0;
    }else{

        ll f = n / 3;
        ll t = n % 3;
        if(t)
            cout << f * 2;
        else
            cout << f - 1;

    }

    return 0;
}

牛客周赛 游游的整数操作

题目理解

这个题目很巧妙,因为每次减法操作会把所有的复数变为0,所以如果正向考虑的话,会被什么时候?哪一步操作变为0,而感到困惑。所以我们换个思想。

  • 首先记录所有的操作,因为所有的数,操作是一样的,那么就可以整个求和
  • 然后我们因为存在减法的,那么很有可能前面加了很多也不如我这一个减法减的多。所以需要统计一下最低减到多少.以及最后的操作结果是什么?
  • 所以,我们只要看最后的结果。如果a[i] + sum >= 0那么就加上a[i] + sum
  • 如果a[i] + sum < 0,说明肯定变成0过,那么就加上sum + min_sum

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#define x first
#define y second
using namespace std;
typedef long long ll;

const int Mod = 1e9 + 7, N = 1e5 + 10;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){ return qmi(x, Mod - 2);}
ll mo(ll x){ return (x % Mod + Mod) % Mod;}

ll a[N];
ll n, k;

int main() {

    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];

    ll sum = 0, min_sum = 0;

    for(int i = 1, op, x; i <= k; i++)
    {
        cin >> op >> x;

        sum += op == 1? x : -x;
        min_sum = min(min_sum, sum);
    }    

    ll res = 0;
    for(int i = 1; i <= n; i++)
    {
        if(a[i] + min_sum >= 0)
            res = mo(a[i] + res + sum);
        else
            res = mo(res + sum - min_sum);
    }

    cout << res;
    return 0;
}

牛客周赛 游游的因数

题目理解

这个题的范围比较大,所以要考虑一下简单的数论。那么我们可以得到的是a * b的因数,为a的因数和b的因数,然后分别相乘组成的各种情况即可。
时间复杂度是loga * logb,没问题。记住用set去重即可。

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;

const int Mod = 1e9 + 7;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){ return qmi(x, Mod - 2);}
ll mo(ll x){ return (x % Mod + Mod) % Mod;}

ll b, a;

int main() {

    cin >> a >> b;

    vector<ll> ka, kb;

    for(int i = 1; i <= a / i; i++)
        if(a % i == 0)
        {
            ka.push_back(i);
            if(a / i != i)
                ka.push_back(a / i);
        } 

    for(int i = 1; i <= b / i; i++)
        if(b % i == 0)
        {
            kb.push_back(i);
            if(b / i != i)
                kb.push_back(b / i);
        } 
    
    set<ll> res;

    for(int i = 0; i < ka.size(); i++)
        for(int j = 0; j < kb.size(); j++)
            res.insert(ka[i] * kb[j]);
    
    cout << res.size() << endl;
    for (auto iter = res.begin(); iter != res.end(); ++iter) {
        cout << *iter << " ";
    }

    return 0;
}

牛客周赛 游游的字符串

题目理解

基础题,模拟即可

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;

const int Mod = 1e9 + 7;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){ return qmi(x, Mod - 2);}
ll mo(ll x){ return (x % Mod + Mod) % Mod;}

string s;

int main() {

    cin >> s;

    for(int i = 0; i < s.size(); i++)
    {
        if(s[i] >= 'A' && s[i] <= 'Z')
        {
            if(s[i] == 'Z')
                cout << "A";
            else
                cout << (char)(s[i] + 1);
        }
        else if(s[i] >= 'a' && s[i] <= 'z')
        {
            if(s[i] == 'a')
                cout << 'z';
            else
                cout << (char)(s[i] - 1);
        }else
            cout << s[i];
    }

    return 0;
}

牛客周赛 游游的排列构造

题目理解

需要思考一下,a[i]是前i个中最大的,那么需要k个。

  • 我们只需要从n - k + 1开始取,取k个放前面必然是最大的。
  • 然后每个不能连起来,那就从1开始输出即可。
  • 输出够k个后,就不能在输出大的了。就需要来输出从1开始的值。

代码实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;

const int Mod = 1e9 + 7;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){ return qmi(x, Mod - 2);}
ll mo(ll x){ return (x % Mod + Mod) % Mod;}


int main() {

    ll n, k;

    cin >> n >> k;

    ll t = n - k + 1;
    ll tmp = 1;

    while(n > 0)
    {
        if(k > 0)
        {
            cout << t++ << " ";
            k--;
        }else
            cout << tmp++ << " ";
        n--;

        if(n <= 0)
            break;
        
        cout << tmp++ << " ";
        n--;
    }   

    return 0;
}

Acwing1129 热浪

题目理解

就是最短路,练习题。

代码实现

邻接矩阵

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;

const int Mod = 1e9 + 7, N = 2560;
const int INF = 0x3f3f3f3f3f;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){ return qmi(x, Mod - 2);}
ll mo(ll x){ return (x % Mod + Mod) % Mod;}
int T, c, ts, te;
int g[N][N], d[N];
bool st[N];

int dijkstra()
{
    memset(d, INF, sizeof d);

    d[ts] = 0;

    for(int i = 1; i <= T; i++)
    {
        int t = -1;

        for(int j = 1; j <= T; j++)
            if(!st[j] && (t == -1 || d[t] > d[j]))
                t = j;

        st[t] = true;

        for(int j = 1; j <= T; j++)
            d[j] = min(d[j], d[t] + g[t][j]);
    }

    return d[te];
}

int main() {

    cin >> T >> c >> ts >> te;
    memset(g, INF, sizeof g);

    for(int i = 1; i <= c; i++)
    {
        int a, b, v;
        cin >> a >> b >> v;
        g[a][b] = min(g[a][b], v);
        g[b][a] = min(g[b][a], v);
    }


    cout << dijkstra();
    return 0;
}

邻接表

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int Mod = 1e9 + 7, N = 1e5 + 10, M = N * 2;
const int INF = 0x3f3f3f3f3f;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){ return qmi(x, Mod - 2);}
ll mo(ll x){ return (x % Mod + Mod) % Mod;}


int h[N], ne[M], e[M], idx, w[M];
int d[N], n, m, s, en;
bool st[N];

void add(int a, int b, int c)
{
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx++;   // w 是边权重,e是到哪里,ne是
}

int dijkstra()
{
    memset(d, INF, sizeof d);

    d[s] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, s});

    while(q.size())
    {
        auto t = q.top();
        q.pop();

        int cur = t.y;

        if(st[cur]) continue;
        st[cur] = true;
        for(int i = h[cur]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] > d[cur] + w[i]){
                d[j] = d[cur] + w[i];
                q.push({d[j], j});
            }
        }
    }

    return d[en];
}

int main() {

    memset(h, -1, sizeof h);

    scanf("%d%d%d%d", &n, &m, &s, &en);

    while(m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);

        add(a, b, c);
        add(b, a, c);
    }

    printf("%d", dijkstra());
    return 0;
}

标签:道题,return,int,res,ll,受制,include,97,Mod
From: https://www.cnblogs.com/wxzcch/p/17716182.html

相关文章

  • 《看了受制了》第二十天,6道题,合计90道题
    2023年9月18日今天上午写了Atcoder的翻译,以后对于我这种菜鸡来说,多多少少有点用了。前两个题是贪心,第三个是BFS。Acwing908最大不相交区间数量题目理解全部按右端点进行排序然后如果下一个点的左,比我的右端点还大,那么就肯定不在一个区间然后更新目前的右端点即可代码实......
  • Codeforces Round 897 (Div. 2) A-E
    A.green_gold_dog,arrayandpermutation题意:给出一个长为\(n\)的数组\(a\),找到一个长为\(n\)的排列\(b\),使得\(a\)与\(b\)对应位置上的元素的差尽可能大Solution将数组\(a\)排序,然后令排列\(n,n-1,...,2,1\)对应到对应的元素即可structnode{intx,id;boolope......
  • 《看了受制了》第十九天,7道题,合计84道题
    2023年9月17日今天晚上打了牛客的周赛。题目不是很难的题目,哎,最后一题是位运算,不会啊。。。异或和。。今晚还发现了一个up主,同是21级,大二摘金,我大二哎。每次都会感到世界的层次,认识到自己的弱小。。。而且也发现自己的一些观念上的错误。牛客周赛12小美种树题目理解这个题和......
  • 《看了受制了》第十八天,3道题,合计77道题
    2023年9月16日今天因为acwing题简单,第一次正式AKACWING5149简单计算题目理解真的很简单,就是循环代码实现#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;intmain(){intT;cin>>T;while(T--){int......
  • 《看了受制了》第十七天,4道题,合计74道题
    2023年9月15日小白月赛前三题,PAT一题。这个PAT,我怕是读题都有困难啊。中文都读半天。。。。。ACWIGN1494银行排队题目理解这个题目就是模拟。纯模,数字字符串来回转。代码实现#include<iostream>#include<cstdio>#include<algorithm>#include<vector>#include<queue>us......
  • 【代码随想录算法训练营第二天】977.有序数组的平方、209.长度最小的子数组 、59.螺旋
    Day2-数组2023.9.15Leetcode977有序数组的平方给你一个按非递减顺序排序的整数数组nums,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。初解我还是不能想到暴力解法之外的,对某个问题的最优复杂度也没有概念。就算提示我是用指针,我也想不到思路。现在我知......
  • 《看了受制了》第十六天,6道题,合计70道题
    2023年9月14日题目不难,但是有点恶心。今天写的这个是真受制ACWING1478签到签出题目理解这个就是要把时间都转化成秒,然后排序即可。代码实现#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;intn;pair<int,int>in[12],out[12];stri......
  • Codeforces Round 897 (Div. 2) 考试总结
    前言这次打得很好,相较于div3的脑残题和签到题来说,div2的思维难度更加的大。同时还有除传统题外,其他的题型出现。比如交互题等。这次能在考场上想出三道较于之前是有很大的进步的。赛时实况:ABCDE1E2F√√√××××赛后改题情况:ABCDE1E2F......
  • 关于异或运算的一道题
      和白球的数量无关,  黑球偶数个时,概率0%。   黑球奇数个时,概率100%。  设白球是0,黑球是1    0 0 ——> 0          1 1——> 0   0 1 ——> 1        ......
  • Codeforces Round 897 (Div. 2)
    目录写在前面ABCDE1/E2F写在最后写在前面比赛地址:https://codeforces.com/contest/1867。简略题解。还好没掉分。A令原数列中第\(k\)大对应\(k\)即可。///*By:Luckyblock*/#include<bits/stdc++.h>#defineLLlonglongconstintkN=4e4+10;//============......