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;
}

本栏目推荐文章
• 《30岁人生开挂7步法》
• 纪念一下，在国产麒麟linux下跑dotnet8，运行起来了
• 学了这么多编程语言，你学会了几种“Hello world”呢？
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• 7 - for循环while循环 1+2+...+100和
• 第二章 Spring Boot 整合 Kafka消息队列 生产者
• 春眠不觉晓，Java数据类型知多少？基础牢不牢看完本文就有数了
• openresty 1.25.3.1 发布了
• 特朗普开始在YouTube上打竞选广告了 —— 美国总统的竞选广告已经开始媒体投放了
• Windows 7 SP 1 部署 .NET 6/7

看了受制了 第二十天6道题 看了受制了 第二十天7道题 看了受制了 第八天6道题 看了受制了 第六天4道题 看了受制了 第15天6道题 看了受制了 第十六天6道题 看了受制了 第十八天3道题 看了受制了 第十一天4道题 看了受制了 第十三天4道题 看了受制了 第十四天1道题