《看了受制了》第四十六天，11道题，合计290道题

2023年10月22日

牛客小白月赛 数位dp？

题目理解

两个要求，要最后的值是偶数，所以不是偶数就÷10，答案加一即可。

代码实现

int main()
{
    int n;
    cin >> n;
    int res = 0;
    while(n % 2 != 0)
        n /= 10, res ++;
    cout << res;
}

牛客小白月赛 灵异背包？

题目理解

答案和是偶数，就是答案，不是就减去最小的奇数

代码实现

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
int main()
{
    ll res = 0;
    vector<ll> vec;
    int n;
    cin >> n;
    ll k;
    for(int i = 1; i <= n; i++)
    {
        cin >> k;
        res += k;
        if(k % 2 == 1) vec.push_back(k);
    }
    sort(vec.begin(), vec.end());
    
    if(res % 2) cout << res - vec[0];
    else cout << res;
}

牛客小白月赛 mex和gcd的乘积

题目理解

如果mex不是1，那么gcd必是1
如果mex是1，那么gcd就会大
所以答案，要么就是整个序列的mex,要么就是0旁边的最大值。
如果整个序列都是0，那么值只能是0

代码实现

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> vis(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        vis[a[i]] = 1;
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
            if (i + 1 < n) {
                ans = max(ans, a[i + 1]);
            }
            if (i - 1 >= 0) {
                ans = max(ans, a[i - 1]);
            }
        }
    }

    int mex = 0;
    while (vis[mex]) {
        mex++;        
    }

    if (mex > 1) {
        ans = max(ans, mex);
    }    
    cout << ans << '\n';

    return 0;
}

牛客小白月赛 2^20

题目理解

可以发现，子弹是无限的，所以并不会打光。
那么就是两个操作：

• x = x * 2
• x = x + 1
  那么就枚举操作即可，操作是不超过20的。

代码实现

typedef long long ll;
const int N = 1048576 + 10, M = 1048576;
int a[N];
int step[N];

bool check(int u)
{
    int q = 1;
    while(q < u) q *= 2;
    if(u == q) return false;
    return true;
}

int bfs(int u)
{

    if(u == 0) return 0;
    
    int ans=20;
    for(int i=0;i <= 20;i++){ //累加20次
        int temp = u;
        int cnt = 0;
        while(temp % 2 == 0) cnt++,temp/=2;  //统计01后面串有几个0
        ans = min(ans, i + 20 - cnt);  //20-cnt就是有左移的次数
        u++;
    }
    return ans;
}

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        
        cout << bfs(n % M) << endl;
    }
    return 0;
}

Acwing周赛 A 蜗牛爬

题目理解

就如果大于5，就是n - 5 + 1
如果小于等于就是1

代码实现

int main()
{
    int n;
    cin >> n;
    if(n <= 5) cout << 1;
    else cout << n - 5 + 1;
    return 0;
}

Acwing周赛 B 替换字符

题目理解

枚举每一个位置的错误个数，用最小的那个即可。

代码实现

typedef pair<int, int> PII;
const int N = 1010;
vector<PII> q;
int main()
{
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    for(int i = 0; i <= m - n; i++)
    {
        int cnt = 0;
        for(int k = 0, j = i; k < n; k++, j++)
            if(s[k] != t[j])
                cnt++;

        q.push_back({cnt, i});
    }       
    sort(q.begin(), q.end());


    int flag = q[0].y;
    int res = q[0].x;
    cout << res << endl;
    for(int k = 0, j = flag; k < n; k++, j++)
        if(s[k] != t[j])
            cout << k + 1 << " ";
    return 0;
}

Acwing周赛 扩展字符串

题目理解

预处理出来能求出的长度。如果超出了就返回'.'
如果:

• 是0，就返回s[k - 1]
• 是a的区间就返回a[k - 1]
• 是b的区间就返回b[k - 1]
• 是c的区间就返回c[k - 1]
• 是s的话就划分成子问题，继续递归。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e5 + 10, Mod = 1e9 + 7;
const ll INF = 2e18;

ll len[N + 5];
string s = "DKER EPH VOS GOLNJ ER RKH HNG OI RKH UOPMGB CPH VOS FSQVB DLMM VOS QETH SQB";
string a = "DKER EPH VOS GOLNJ UKLMH QHNGLNJ A";
string b = "AB CPH VOS FSQVB DLMM VOS QHNG A";
string c = "AB";

char dfs(ll n, ll k)
{
    if(k > len[n]) return '.';
    if(n == 0) return s[k - 1];

    if(k <= a.size()) return a[k - 1];

    k -= a.size();
    if(k <= len[n - 1]) return dfs(n - 1, k);

    k -= len[n - 1];
    if(k <= b.size()) return b[k - 1];

    k -= b.size();

    if(k <= len[n - 1]) return dfs(n - 1, k);
    k -= len[n - 1];

    return c[k - 1];
}

void solve()
{

    int q;
    cin >> q;
    while(q -- )
    {
        ll n, k;
        cin >> n >> k;
        cout << dfs(n, k);
    }

    return;
}

int main()
{
    len[0] = s.size();
    for(int i = 1; i <= N; i++)
    {
        len[i] = len[i - 1] * 2 + a.size() + b.size() + c.size();
        len[i] = min(len[i], INF);
    }
    int T = 1;
    while(T--) solve();
    return 0;
}

Atcoder325 A 签到题

题目理解

直接输出姓和san即可

代码实现

void solve()
{

	string s, t;
	cin >> s >> t;

	cout << s << " " << "san";

	return;
}

Atcoder325 B World Meeting

题目理解

枚举24个小时，看那个时候是否符合区域。如果符合就加上去

代码实现

const int N = 1010;
int w[N], c[N];
int n, res;

void solve()
{

	cin >> n;

	for(int i = 1; i <= n; i++)
		cin >> w[i] >> c[i];

	for(int i = 0; i <= 24; i++)
	{
		int cnt = 0;

		for(int j = 1; j <= n; j++)
		{

			int k = c[j] + i;
			if(k >= 24) k -= 24;

			if(k >= 9 && k < 18) cnt += w[j];
		}
		
		res = max(res, cnt);
	}

	cout << res;
	return;
}

Div.3 Round905 A - Morning

题目理解

我需要看这个数和需要的数是否一样，一样就res++
不一样就移过去再res++

代码实现

void solve()
{
	string s;
	cin >> s;

	int res = 0;

	char c = '1';

	for(int i = 0; i < 4; i++)
	{
		if(s[i] == c || (s[i] == '0' && c == '9' + 1))
		{
			res ++;
		}else{
			int t = 0;
			if(s[i] == '0')
			{
				t = abs(('9' + 1) - c);
				c = '9' + 1;
			}else{
				t = abs(s[i] - c);
				c = s[i];
			}

			res+=t + 1;
		}
	}

	cout << res << endl;

	return;
}

Div.3 Round905 B

题目理解

如果k是0，就看原本是不是回问
如果差是1，就一定是
如果差是奇数，就要(t - 1) / 2对
如果差是偶数，就要t / 2对

代码实现

#include <iostream>
#include <cstring>
using namespace std;

const int N = 26;
int cnt[N];

bool check(string s)
{
    memset(cnt, 0, sizeof cnt);
    for(char ch : s)
        cnt[ch - 'a']++;
    
    int oddCnt = 0;
    for(int i = 0; i < N; i++)
        if(cnt[i] % 2 == 1)
            oddCnt++;
    
    return oddCnt <= 1;
}

bool isPossible(int n, int k, string s)
{
    int t = n - k;

    if (t == 0) {
        return check(s);
    } else if (t == 1) {
        return true;
    } else {
        memset(cnt, 0, sizeof cnt);
        for(char ch : s)
            cnt[ch - 'a']++;

        int pairs = 0;
        for(int i = 0; i < N; i++)
            pairs += cnt[i] / 2;

        if(t % 2 == 0) {
            return pairs >= t / 2;
        } else {
            if(pairs > (t - 1) / 2)
                return true;
            else if(pairs == (t - 1) / 2) {
                for(int i = 0; i < N; i++)
                    if(cnt[i] % 2 == 1)
                        return true;
                return false;
            } else {
                return false;
            }
        }
    }
}

int main()
{
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        if (isPossible(n, k, s))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}

本栏目推荐文章
• abc290g O(TD)算法
• 290
• 290. 单词规律
• Qt/C++开发经验小技巧286-290
• 《看了受制了》第四十六天，11道题，合计290道题
• 哈希表——解205. 同构字符串及290. 单词规律
• abc290E
• 浅谈 JEP290
• 力扣 290 字母的是否符合规律规律
• AtCoder Beginner Contest 290 Ex Bow Meow Optimization

290290f 290g 290e at_abc 290 abc at beginner atcoder contest 290 单词 规律290 jep 290 算法290g abc td 题解diameter maximum 290f 规律 字母290