【蓝桥杯】第十四届C++B组省赛

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int ret = 0;
	vector<int> v(100);
	for (int i = 0; i < 100; i++)
	{
		cin >> v[i];
	}
	int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
	for (int i = 1; i <= 12; i++)
	{
		for (int j = 1; j <= days[i]; j++)
		{
			string s("2023");
			if (i < 10) s += "0";
			s += to_string(i);
			if (j < 10) s += "0";
			s += to_string(j);
			int k = 0;
			for (int l = 0; l < v.size() && k < 8; l++)
			{
				if ((s[k] - '0') == v[l]) k++;
			} 
			if (k == 8) ret++;
		}
	}
	cout << ret << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
	double len = 23333333;
	double H = 11625907.5798;
	for (int i = 0; i < len / 2; i++)
	{
		double sum = 0;
		sum -= i* (i / len)*log2(i / len) + (len - i)*((len - i) / len)*log2((len - i) / len);
		if (abs(sum - H) < 0.1)
		{
			cout << i << endl;
			break;
		}
	}
	return 0;
} 

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin >> n;
	int vl = INT_MIN, vr = INT_MAX;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		vr = min(a / b, vr);
		vl = max(a / (b + 1) + 1, vl);
	}
	cout << vl << " " << vr << endl; 
	return 0;
} 

#include <bits/stdc++.h>
using namespace std;

int t, n;
int T[11], D[11], L[11];
bool used[11] = {}; // 标记是否安排过了当前飞机
int flag = 0; // 标记全部飞机是否安全降落

void dfs(int x, int time) // x表示安排到了第几架飞机，			
{                         // time表示前面一架飞机降落后的时间
	if (x >= n) // 根据题目要求枚举到了最后一架飞机
	{
		flag = 1;
		return;
	}
	for (int i = 0; i < n; i++) // 一架一架的尝试
	{  
		// 当前飞机还没被安排，在天上可以停留的时间>前面飞机降落的最后时间
		if (!used[i] && T[i] + D[i] >= time) 
		{
			used[i] = true; // 如果满足条件就让这个飞机降落
			// 这架飞机降落后下一架飞机可能还没来，或者后面一架飞机在天空盘旋等待
			dfs(x + 1, max(T[i], time) + L[i]);
			used[i] = false;
		}
	}
}
int main()
{
	cin >> t;
	while (t--)
	{
		cin >> n;
		for (int i = 0; i < n; i++)
			cin >> T[i] >> D[i] >> L[i];
		dfs(0, 0); // 第0架飞机在0时刻降落
		if (flag) cout << "YES" << endl;
		else cout << "NO" << endl;
		flag = 0;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int dp[10];

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		int sz = s.size();
		dp[s[sz - 1] - '0'] = max(dp[s[sz - 1] - '0'], dp[s[0] - '0'] + 1);
	}
	int ret = 0;
	for (int i = 0; i < 10; i++)
		ret = max(ret, dp[i]);
	cout << (n - ret) << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

int m, n;
char arr[51][51];
int dx[8] = {-1, 1, 0, 0, -1, 1, 1, -1};
int dy[8] = {0, 0, -1, 1, 1, 1, -1, -1};
bool used[51][51];

bool check(int i, int j)
{
	for (int i = 0; i <= m; i++)
		for (int j = 0; j <= n; j++)
			used[i][j] = false;
	queue<pair<int, int>> q;
	q.push({i, j});
	used[i][j] = true;
	while (q.size())
	{
		int a = q.front().first, b = q.front().second;
		q.pop();
		for (int k = 0; k < 8; k++)
		{
			int x = a + dx[k], y = b + dy[k];
			if (x < 1 || x > m || y < 1 || y > n) return true;
			if (arr[x][y] == '0' && !used[x][y])
			{
				q.push({x, y});
				used[x][y] = true;
			}
		}
	}
	return false;
}

void dfs(int i, int j)
{
	for (int k = 0; k < 4; k++)
	{
		int x = i + dx[k], y = j + dy[k];
		if (x > 0 && x <= m && y > 0 && y <= n && arr[x][y] == '1')
		{
			arr[x][y] = '0';
			dfs(x, y);	
		} 
	}
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		cin >> m >> n;
		for (int i = 1; i <= m; i++)
			for (int j = 1; j <= n; j++)
				cin >> arr[i][j];
		for (int i = 1; i <= m; i++)
			for (int j = 1; j <= n; j++)
				if (arr[i][j] == '1' && !check(i, j))
					arr[i][j] = '0';
		int ret = 0;
		for (int i = 1; i <= m; i++)
			for (int j = 1; j <= n; j++)
				if (arr[i][j] == '1')
				{
					ret++;
					dfs(i, j);
				}
		cout << ret << endl;
	}
	return 0;
}

#include<iostream>
using namespace std;

long long ret = 0, cnt = 0;

int main()
{
    int k;
    cin >> k;
    string str;
    char c1, c2;
    cin >> str >> c1 >> c2;
    int l = 0, r = k - 1;
    while (1)
    {
        if (r == str.size()) break;
        if (str[l] == c1) cnt++;
        if (str[r] == c2) ret += cnt;
        l++, r++;
    }
    cout << ret << endl;
    return 0;
}

// 样例输入
5 3
1 4 2 8 7

// 样例输出
17 7

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];
	while (k--)
	{
		int index = 0;
		for (int i = 0; i < v.size(); i++)
			if (v[index] > v[i])
				index = i;
		if (index - 1 >= 0) v[index - 1] += v[index];
		if (index + 1 < n) v[index + 1] += v[index];
		v.erase(v.begin() + index);
	}
	for (int e : v)
		cout << e << " ";
	return 0;
} 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pr = pair<ll, ll>;
const int N = 1e6;
struct { ll prev, next; } a[N]; // 记录对应位置前后的下标，方便删除
ll update[N], ret[N]; // update用于记录每个元素需要更新的值，
 					  // 需要累加的值暂时存到这个数组中
priority_queue<pr, vector<pr>, greater<pr>> pq;

int main()
{
    ll n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        ll x; cin >> x;
        a[i].prev = i - 1;
        a[i].next = i + 1;
        pq.push({x, i});
    }
    while (pq.size() > n - k)
    {
        ll v = pq.top().first, id = pq.top().second;
        pq.pop();
        if (update[id]) // id下标对应的元素有被累加过
        {
            pq.push({v + update[id], id});// 加入小堆中重新选择最小值
            update[id] = 0;
        }
        else
        {
            ll l = a[id].prev, r = a[id].next;
            // 将当前的值加到前后元素上
            update[l] += v;
            update[r] += v;
            // 删除节点
            a[l].next = r;
            a[r].prev = l;
        }
    }
    while (pq.size())
    {
        ll v = pq.top().first, id = pq.top().second;
        pq.pop();
        ret[id] = v + update[id];
    }
    for (auto e : ret)
        if (e) cout << e << " ";
    return 0;
}

// 样例输入
6 4
1 2 1
1 3 1
3 4 2
3 5 2
4 6 3
2 6 5 1

// 样例输出
10 7 13 14

// 样例输入
6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5
4

// 样例输出
4