标签：道题 return int res ll 受制 include 97 Mod

2023年9月19日

牛客，ACWING图论！思前想后，这个图论一定要从0到0.1！！！

牛客周赛游游的字符串

题目理解

输出k个you，然后剩下的都是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

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

2023年9月19日

牛客周赛游游的字符串

题目理解

代码实现

牛客周赛游游的整数拆分

题目理解

代码实现

牛客周赛游游的整数操作

题目理解

代码实现

牛客周赛游游的因数

题目理解

代码实现

牛客周赛游游的字符串

题目理解

代码实现

牛客周赛游游的排列构造

题目理解

代码实现

Acwing1129 热浪

题目理解

代码实现

邻接矩阵

邻接表

相关文章

赞助商

阅读排行

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

2023年9月19日

牛客周赛 游游的字符串

题目理解

代码实现

牛客周赛 游游的整数拆分

题目理解

代码实现

牛客周赛 游游的整数操作

题目理解

代码实现

牛客周赛 游游的因数

题目理解

代码实现

牛客周赛 游游的字符串

题目理解

代码实现

牛客周赛 游游的排列构造

题目理解

代码实现

Acwing1129 热浪

题目理解

代码实现

邻接矩阵

邻接表

相关文章

赞助商

阅读排行

牛客周赛游游的字符串

牛客周赛游游的整数拆分

牛客周赛游游的整数操作

牛客周赛游游的因数

牛客周赛游游的字符串

牛客周赛游游的排列构造