2023年9月23日

今天周六，尽力做了做，虽然Acwing没能AK。。没读懂题。

Acwing5152 简单输出

题目理解

基础语法

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>
#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;
const int INF = 0x3f3f3f3f;

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;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        for(int j = 1; j <= t; j++)
            cout << j << " ";
        cout << endl;
    }

    return 0;
}

Acwing5153 删除

题目理解

改题目难点在于，如何快速判断一个数是否为8的倍数。

• 当且仅当一个数的最后一位能被2或5整除，这个数就能被2或5整除。

• 当且仅当一个数的最后两位能被4或25整除，这个数就能被4或25整除。

• 当且仅当一个人的最后三位能被8或125整除，这个数就能被8或125整除。

• 当且仅当一个数各个位上的数字之和能被3或9整除，这个数就能被3或9整除

• 当且仅当一个数的最后一位的两倍与剩下的数之差能被7整除（或最后三位与剩下的数只差能被7正整除），这个数就能被7整除。

• 当且仅当一个数的奇数位上的数之和与偶数位上的数之和的差值为11的倍数。

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>
#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;
const int INF = 0x3f3f3f3f;

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++)
        for(int j = i + 1; j < s.size(); j++)
            for(int k = j + 1; k < s.size(); k++)
            {
                int t = (int)(s[i] - 48) * 100 + (int)(s[j] - 48) * 10 + (int)(s[k] - 48);
                if(t % 8 == 0 && i < j && j < k)
                {
                    cout << "YES" << endl;
                    cout << t;
                    return 0;
                }
            }

    for(int i = 0 ; i < s.size(); i++)
        for(int j = i + 1; j < s.size(); j++)
        {
            int t = (int)(s[i] - 48) * 10 + (int)(s[j] - 48);
            if(t % 8 == 0 && i < j)
            {
                cout << "YES" << endl;
                cout << t;
                return 0;
            }
        }

    for(int i = 0 ; i < s.size(); i++)
    {
        int t = (int)(s[i] - 48);
        if(t % 8 == 0)
        {
            cout << "YES" << endl;
            cout << t;
            return 0;
        }
    }
    cout << "NO";
    return 0;
}

Acwing5155 牛的基因学

题目理解

这个题目读懂以后非常EZ。哎，阅读理解不过关。。。
1. 理解最大值

我们可以得到以下几点：

• 就是相同字符的数量
• 我们需要不断进行左移
  2. 如何构造最大值
  
  注意一下几点：
• 观察这个序列，我们可以看当i为0，j为0 1 2时，它的基因虽然是在左移，但是达到的效果是和每一个对比！！
• 观察下面的当i为不同的情况也是一样的。
• 那么最大值，就是n个出现次数最多的！！
• 所以我们可以让构造的串就是n个出现次数最多的字符。

那么当我们长度为n的串，出现次数最多的个数为x，那么我们的答案就是：

最后在取模即可，快速幂、x的n次枚举都可以~

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>
#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;
const int INF = 0x3f3f3f3f;

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 n, cnt = 0;
string s;
ll a[30];


int main() {

    cin >> n >> s;

    for(int i = 0 ; i < n; i++)
        a[(int)(s[i]) - 64]++;

    sort(a + 1, a + 30);

    ll res = 0;
    ll maxx = a[29];

    for(int i = 29; i >= 26; i--)
        if(maxx == a[i])
            cnt++;

    cout << qmi(cnt, n);

    return 0;
}

Acwing1353 滑雪场设计

题目理解

因为雪山的高度，都是0 ~ 100，那么高度差有是17，直接枚举每一个区间即可。

代码实现

#include <iostream>
using namespace std;
int a[1002], n, m, ans = 0x3f3f3f3f, l = 0;
int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(l = 0; l <= 100 - 17; l ++ ) {
        m = 0;
        for(int i = 1; i <= n; i ++ ) {
            if(a[i] < l) m += (a[i] - l) * (a[i] - l);
            else if(a[i] > l + 17)  m += (a[i] -  l - 17) * (a[i] -  l - 17);
        }
        ans = min(ans, m);
    }
    cout << ans;
}

Acwing903 昂贵的聘礼

题目理解

这个题目读完以后建图方式不难，就是每一个替代品，到主物品进行建图，这个我也可以达到。
难点在于，枚举的方式。我一开始枚举的方式是不同的物品的起点，然后阶级限制是abs(le[i] - now) <= m，这样的话枚举的阶级限制就成了2m，与题意的m不符合的。
那么就需要更改我们的枚举方式，采用枚举酋长的等级。因为必然是要和酋长进行交换的，那么我们只需要从酋长的等级 - m,开始枚举，定上下界即可。

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>
#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;
const int INF = 0x3f3f3f3f;

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



const int N = 110;

int g[N][N], d[N];
int p[N], le[N];
bool st[N];
int n, m, res = INF;

int dijkstra(int u)
{
    memset(d, INF, sizeof d);
    memset(st, 0, sizeof st);

    d[0] = 0;


    for(int i = 1; i <= n + 1; i++)
    {
        int t = -1;
        for(int j = 0; j <= n; j++)
            if(!st[j] && (t == -1 || d[j] < d[t]))
                t = j;

        st[t] = true;

        for(int j = 1; j <= n; j++)
            if(d[j] > d[t] + g[t][j] && le[j] <= u + m && le[j] >= u)
                d[j] = d[t] + g[t][j];
    }

    return d[1];
}

int main() {

    memset(g, INF, sizeof g);
    scanf("%d%d", &m, &n);

    for(int i = 0; i <= n; i++) g[i][i] = 0;

    for(int i = 1; i <= n; i++)
    {
        int cnt;
        scanf("%d%d%d", &p[i], &le[i], &cnt);
        g[0][i] = min(g[0][i], p[i]);
        while(cnt--)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            g[a][i] = min(g[a][i], b);
        }
    }

    for(int i = le[1] - m; i <= le[1]; i++)
        res = min(res, dijkstra(i));

    cout << res;
    return 0;
}

AtcoderABC321 A

题目理解

判断是否严格下降

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>
#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;
const int INF = 0x3f3f3f3f;

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;}
vector<int> vec;
int n, X;
int a[110];
int b[110];
bool check(int mid)
{

    memcpy(b, a, sizeof a);
    b[n] = mid;
    sort(b + 1, b + 1 + n);
    int p = 0;

    for(int i = 2; i < n; i++)
        p += b[i];
    
    if(p >= X) return true;

    return false;
}

int main() {
    cin >> n >> X;
    int sum = 0;
    for(int i = 1; i <= n - 1; i++)
    {
        cin >> a[i];
        sum += a[i];
    }

    sort(a + 1, a + n);

    if(sum - a[1] < X)
    {
        cout << -1;
    }else{
        int l = 0, r = 100;
        while(l < r)
        {
            int mid = (l + r) >> 1;

            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        cout << l;
    }

    return 0;
}

AtcoderABC321 B

题目理解

如果和减最小的 < x,就根本不行，输出0即可。不然二分找答案。

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>
#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;
const int INF = 0x3f3f3f3f;

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;}
vector<int> vec;
int n, X;
int a[110];
int b[110];
bool check(int mid)
{

    memcpy(b, a, sizeof a);
    b[n] = mid;
    sort(b + 1, b + 1 + n);
    int p = 0;

    for(int i = 2; i < n; i++)
        p += b[i];
    
    if(p >= X) return true;

    return false;
}

int main() {
    cin >> n >> X;
    int sum = 0;
    for(int i = 1; i <= n - 1; i++)
    {
        cin >> a[i];
        sum += a[i];
    }

    sort(a + 1, a + n);

    if(sum - a[1] < X)
    {
        cout << -1;
    }else{
        int l = 0, r = 100;
        while(l < r)
        {
            int mid = (l + r) >> 1;

            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        cout << l;
    }

    return 0;
}

本栏目推荐文章
• chromedriver 114以后版本下载地址
• 库克透露苹果已有接班人计划，或从这四人中诞生；谷歌创始人亲自给 Gemini 写代码丨 RTE 开发者日报 Vol.114
• chromedriver 爬虫组件更新，114版本以上
• BLOG114
• 【杂题乱写】AtCoder-ARC114
• 文心一言 VS 讯飞星火 VS chatgpt （114）-- 算法导论10.2 7题
• Databend 开源周报第 114 期
• 第 114 场双周赛 - 3 贪心
• Go每日一库之114：go-fuzz
• 《看了受制了》第二十四天，7道题，合计114道题

114114d 114f 练习赛114 114e chromedriver recommended currently 114 permutation division 114f arc chromedriver版本 地址114 acwing 114 abstractions programming笔记114 simulation wizardry uva 114