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

2023年10月15日
今天是补题大作战！

AcwingRound125 A 数量

题目理解

语法题

代码实现

void solve()
{

    int cnt = 0;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        if(i % 2 == 0 && i % 3 != 0)
            cnt++;

    cout << cnt;

    return;
}

AcwingRound125 B 三元组

题目理解

分三种情况讨论：

• a[0] == a[1] == a[2]
• a[0] != a[1] == a[2]
• a[1] != a[2]

代码实现

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    ll cnt = 0;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());

    if(a[1] == a[2] && a[1] != a[0])
    {
        for(int i = 0; i < n; i++)
            if(a[i] > a[2])
                break;
            else
                cnt++;

        ll k = cnt - 2;

        cout << (k + 1) * k / 2;
    }else if(a[1] != a[2]){
        for(int i = 2; i < n; i++)
            if(a[i] > a[2])
                break;
            else 
                cnt++;

        cout << cnt; 
    }else if(a[1] == a[2] && a[1] == a[0])
    {
        for(int i = 0; i < n; i++)
                if(a[i] > a[2])
                    break;
                else
                    cnt++;

            ll res = 0;
            ll k = cnt - 2;

            while(k >= 1)
            {
                res += ((k + 1) * k) >> 1;
                k--;
            }       
            cout << res;
    }
    return;
}

Acwing487 金明的运算方案

题目理解

代码实现

int n, m;
PII master[N];
vector<PII> servent[N];
int f[M];

void solve()
{
	cin >> m >> n;

	for(int i = 1; i <= n; i++)
	{
		int v, p, q;
		cin >> v >> p >> q;
		p *= v;
		if(!q) master[i] = {v, p};
		else servent[q].push_back({v, p});
	}


	for(int i = 1; i <= n; i++)
		for(int u = m; u >= 0; u--)
		{
			for(int j = 0; j < 1 << servent[i].size(); j++)	// 二的n次种方案
			{
				int v = master[i].v, w = master[i].w;

				for(int k = 0; k < (int)servent[i].size(); k++)	// 枚举每一个从品
					if(j >> k & 1)
					{
						v += servent[i][k].v;
						w += servent[i][k].w;
					}
				if(u >= v) f[u] = max(f[u], f[u - v] + w);
			}
		}


	cout << f[m] << endl;
	return;
}

Acwing291 蒙德里安的梦想

题目理解

代码实现

const int N = 12, M = 1 << N;

int n, m;
ll f[N][M];
bool st[M];


void solve()
{
	while(cin >> n >> m, n || m)
	{
		memset(f, 0, sizeof f);
		memset(st, 0, sizeof st);

		// 预处理所有的状态，是否不存在连续奇数个0
		for(int i = 0; i < 1 << n; i++)
		{
			st[i] = true;
			int cnt = 0;

			for(int j = 0; j < n; j++)
				if(i >> j & 1) // 当前这一位是1
				{
					if(cnt & 1) st[i] = false;	//cnt & 1 == cnt % 2
					cnt = 0;
				}else cnt++;

			if(cnt & 1) st[i] = false;  // 查看连续的空着的个数是否为奇数
		}

		// 开始dp
		f[0][0] = 1; 	// 最开始的时候
		for(int i = 1; i <= m; i++)
			for(int j = 0; j < 1 << n; j++)
				for(int k = 0; k < 1 << n; k++)
					if((j & k) == 0 && st[j | k])
						f[i][j] += f[i - 1][k];

		cout << f[m][0] << endl;
	}


	return;
}

Acwing1064 小国王

题目理解

代码实现

const int N = 12, M = (1 << N) + 10, K = 110;
int n, m;
ll f[N][K][M];
vector<ll> state;	// 每一个合法状态
ll id[M], cnt[M];		// 每一个状态和下标直接的映射关系， cnt是每一个状态中1的个数
vector<ll> head[M];		// 每一个状态可以转移到的其他状态


bool check(int u)
{
	for(int i = 0; i < n; i++)
		if((u >> i & 1) && (u >> (i + 1) & 1))
			return false;

	return true;
}

int count(int u)
{
	int res = 0;
	for(int i = 0; i < n; i++)
		if(u >> i & 1)res++;

	return res;
}

void solve()
{
	cin >> n >> m;

	
	// 找到合法状态
	for(int i = 0; i < 1 << n; i++)
		if(check(i))		// 是否存在两个连续的1
			state.push_back(i);	

	// 处理哪两个状态可以相互转移
	for(int i = 0; i < (int)state.size(); i++)
		for(int j = 0; j < (int)state.size(); j++)
		{
			int a = state[i], b = state[j];
			if((a & b) == 0 && check(a | b))	// 条件
				head[a].push_back(b);
		}


	f[0][0][0] = 1;
	for(int i = 1; i <= n + 1; i++)	// 多算一行hh，可以把答案好写
		for(int j = 0; j <= m; j++)
			for(int a = 0; a < (int)state.size(); a++)
				for(int b = 0; b < (int)head[state[a]].size(); b++)
				{
					int c = count(state[a]);
					if(j >= c)	// 一定要满足摆放的上限
						f[i][j][state[a]] += f[i - 1][j - c][head[state[a]][b]];

				}

	
	cout << f[n + 1][m][0];		// 拜访了n + 1行，但是摆了0个
	return;
}

Div.3 Round863 B Conveyor Belts

题目大意

给了传送带的阶数，给了启起始位置，和终止位置，每跨一级是一个花费。问最小花费是多少

题目理解

很明显我在阶数相同的地方，无需花费，因为直接可以到达。所以花费最少就是阶数差，只需要判断终点和起点，分别在第几圈然后做差即可。

代码实现

void solve()
{
	ll n, x1, y1, x2, y2;
	cin >> n >> x1 >> y1 >> x2 >> y2;

	ll l1 = min(min(x1, n - x1 + 1), min(y1, n - y1 + 1));
	ll l2 = min(min(x2, n - x2 + 1), min(y2, n - y2 + 1));

	cout << abs(l1 - l2) << endl;

	return;
}

Div.3 Round863 C Restore the Array

题目大意

给了你n-1个数，这n-1个数，是n个数中两两比较大的那个值。问你原序列，可能是什么样子？

题目理解

首先，第一个和倒数第二个值一定要输出，然后中间大的我们去两者的小值即可。

代码实现

void solve(){
    int n;
    cin >> n;
    vector<int>b(n-1), a;
    for(int i = 0; i < n - 1; i++) cin >> b[i];
    a.push_back(b[0]);
    for(int i = 0; i < n - 2; i++){
        a.push_back(min(b[i], b[i + 1]));
    }
    a.push_back(b[n - 2]);
    for(auto i : a) cout << i << ' ';
    cout << "\n";
}

蓝桥杯第一次双周赛 A题 三带一

题目理解

直接map统计，看是否存在3和1即可

代码实现

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

    map<char, int> mp;

    for(int i = 0; i < 4; i++)
    {
        if(!mp.count(s[i]))
        {
            mp[s[i]] = 1;
        }else
            mp[s[i]]++;
    }

    int a, b, i = 0;
    for(auto p:mp)
    {
        if(i % 2) a = p.y;
        else b = p.y;
        i++;
    }

    if(a == 3 && b == 1 || a == 1 && b == 3)
    {
        cout << "Yes" << endl;
    }else 
        cout << "No" << endl;
    return;
}

蓝桥杯第一次双周赛 B 数树数

题目理解

遇到R乘2，遇L * 2 + 1即可

代码实现

void solve()
{

	int n, q;
	cin >> n >> q;

	while(q--)
	{
		string s;
		cin >> s;
		int res = 1;
		for(int i = 0; i < (int)s.size(); i++)
		{
			if(s[i] == 'R')
				res *= 2;
			else
				res = res * 2 - 1;
		}
		cout << res << endl;
	}

	return;
}

蓝桥杯第一次周赛 C 分组

题目理解

直接二分极差，然后判断在这个极差下的分组能否小于等于k，如果不行就扩大极差，如果可以就减小极差

代码实现

const int N = 1e5 + 10;
int a[N], k, n;

bool check(int u)
{
    int cnt = 1, idx = 1;

    for(int i = 1; i <= n; i++)
    {
        if(a[i] - a[idx] > u)
        {
            cnt++;
            idx = i;
        }
    }

    if(cnt > k) return false;
    return true;
}

void solve()
{
    
    cin >> n >> k;

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

    sort(a + 1, a + 1 + n);

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

蓝桥杯第一次双周赛 D 锻炼

题目理解

多个完全背包，把每个需要可以连续锻炼的天数看作一个单独的完全背包。然后用map存下来，对于每个时间段进行求解完全背包即可。然后把答案累加

代码实现

const int N = 2e5 + 10, M = (1 << 20) + 10;
ll f[M];
void solve()
{
	vector<ll> p;
	ll qq = 1;
	for(int i = 0; i < 22; i++)
	{
		p.push_back(qq);
		qq *= 2;
	}
	int n, m, q;
	cin >> n >> m >> q;
	ll res = 0;
	unordered_map<int, int> mp;
	int idx = 1;

	for(int i = 0; i < q; i++)
	{
		int x, day;
		cin >> x;

		day = x - idx;
			
		idx = x + 1;
		if(day <= 0 && i != q - 1) continue;
		if(!mp.count(day))
			mp[day] = 1;
		else mp[day]++;	

		if(i == q - 1)
		{
			if(!mp.count(n - x))
				mp[n-x] = 1;
			else 
				mp[n-x]++;
		}	
	}	

	vector<ll> v, w;

	for(int i = 0; i < m; i++)
	{
		ll a, b;
		cin >> a >> b;
		w.push_back(b);
		v.push_back(p[a]);
	}

	for(auto p : mp)
	{
		int V = p.x;
		memset(f, 0, sizeof f);
		for(int i = 0; i < m; i++)
			for(int j = v[i]; j <= V; j++)	// 完全背包正着枚举
			{
				f[j] = max(f[j], f[j - v[i]] + w[i]);
			}

		res += f[V] * p.y;
	}

	cout << res;
	return;
}

本栏目推荐文章
• 《看了受制了》第四十二天，11道题，合计261道题
• CF261D Maxim and Increasing Subsequence 题解
• 『题解』ABC261Ex Game on Graph
• rsync 遇到中文乱码文件名无法同步，并报错：rsync: rename "/test1/abc/abc/opt/abc/abc/abcx-V2/img_abc/.δ\#261\#352\#314\#342-3.jpg.wdPu5C" -> "abc/xx-V2/img_abc/δ\#261\#352\#314\#342-3.jpg": Input/outputerror (5)
• CF261E Maxim and Calculator 题解
• ABC261F 题解
• ABAP-MIGO批导(261移动类型)
• macOS Ventura 13.3.1 (22E261) Boot ISO 原版可引导镜像
• macOS Ventura 13.3.1 (22E261) 正式版发布，ISO、IPSW、PKG 下载
• Qt开发经验小技巧261-265

261261e 22e261 e261 261f 261d 经验 技巧261 265 题解261f abc 原版 镜像ventura 22e261 题解calculator maxim 261e 正式版ventura 22e261 macos