天天看点
返回

2022蓝桥杯省赛C++ A组（持续更新）ABCDEFGHIJ

目录

  • A
    • Solution
    • Code
  • B
    • Solution
    • Code
  • C
    • Solution
    • Code
  • D
    • Solution
    • Code
  • E
    • Solution
    • Code
  • F
    • Solution
    • Code
  • G
    • Solution
    • Code
  • H
    • Solution
    • Code
  • I
    • Solution
    • Code
  • J
    • Solution
    • Code

A

Solution

按照题意，先切四次把二维码切出来，然后看先切横还是先切竖，取最小值。

但简单证明可以得知，两种方法答案都是443.

Code 

/*************************************
 * @file_name:      A.cpp.
 * @author:         minamidesi
 * @time:           Insert Date/Time.

*************************************/
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define itn int
#define memmax 0x7fffffff
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define endl '\n'

const ll MOD = 1000000007;
const int intmax = 2147483647;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const ll ulmax = 4294967295ll;

// OUTPUT
template <class a, class b>
ostream &operator<<(ostream &os, const pair<a, b> &p)
{
    os << "(" << p.first << " " << p.second << ")";
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << "[";
    if (!v.size())
        os << "]";
    else
        for (int i = 0; i < v.size(); ++i)
            os << v[i] << ",]"[i == v.size() - 1];
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &s)
{
    os << "{";
    if (!s.size())
        os << "}";
    else
        for (typename set<T>::iterator it = s.begin(); it != s.end(); it++)
            os << *it << ",}"[*it == *s.rbegin()];
    return os;
}

inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

inline void write(ll x)
{ //快写
    char F[200];
    ll tmp = x > 0 ? x : -x;
    if (x < 0)
        putchar('-');
    ll cnt = 0;
    while (tmp > 0)
    {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0)
        putchar(F[--cnt]);
}

ll a, b;

void solve()
{
	a += 4;
	a += 20-1;
	a += (22-1)*20;

	b += 4;
	b += 22-1;
	b += (20-1)*22;


    // cout << "a = " << a << endl;
    // cout << "b = " << b << endl;

    // std::cout << "ans = ";


    cout << min(a, b);
}

void run_code()
{
    solve();
}

void run_code_with_time()
{
    clock_t start, finish;
    double totaltime;
    start = clock();

    #ifndef ONLINE_JUDGE
    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    #endif// ONLINE_JUDGE

    //================================================================
    
    run_code();

    //================================================================
    
    #ifndef ONLINE_JUDGE

    finish = clock();
    totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("\n此程序的运行时间为%.36lf秒！\n", totaltime);
    
    #endif //ONLINE_JUDGE
    
}


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    run_code_with_time();

    return 0;
}

B

Solution

推导一下，答案应该为

LLLV

Code 

/*************************************
 * @file_name:      B.cpp.
 * @author:         minamidesi
 * @time:           Insert Date/Time.

*************************************/
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define itn int
#define memmax 0x7fffffff
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define endl '\n'

const ll MOD = 1000000007;
const int intmax = 2147483647;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const ll ulmax = 4294967295ll;

// OUTPUT
template <class a, class b>
ostream &operator<<(ostream &os, const pair<a, b> &p)
{
    os << "(" << p.first << " " << p.second << ")";
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << "[";
    if (!v.size())
        os << "]";
    else
        for (int i = 0; i < v.size(); ++i)
            os << v[i] << ",]"[i == v.size() - 1];
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &s)
{
    os << "{";
    if (!s.size())
        os << "}";
    else
        for (typename set<T>::iterator it = s.begin(); it != s.end(); it++)
            os << *it << ",}"[*it == *s.rbegin()];
    return os;
}

inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

inline void write(ll x)
{ //快写
    char F[200];
    ll tmp = x > 0 ? x : -x;
    if (x < 0)
        putchar('-');
    ll cnt = 0;
    while (tmp > 0)
    {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0)
        putchar(F[--cnt]);
}

ll n;

void solve()
{
    std::cout << "LLLV";
}

void run_code()
{
    solve();
}

void run_code_with_time()
{
    clock_t start, finish;
    double totaltime;
    start = clock();

    #ifndef ONLINE_JUDGE
    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    #endif// ONLINE_JUDGE

    //================================================================
    
    run_code();

    //================================================================
    
    #ifndef ONLINE_JUDGE

    finish = clock();
    totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("\n此程序的运行时间为%.36lf秒！\n", totaltime);
    
    #endif //ONLINE_JUDGE
    
}


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    run_code_with_time();

    return 0;
}

C

Solution

用乘法结合律，不难看出 s = ∑ i = 1 n ∗ ∑ j = i + 1 n a j s=\sum_{i=1}^{n}*\sum_{j=i+1}^{n}a_j s=∑i=1n​∗∑j=i+1n​aj​

直接前缀和a化简为 O ( n ) O(n) O(n)算法即可。

Code 

#include<bits/stdc++.h>

typedef long long ll;

ll n;
ll a[200005];
ll pre[200005];

void solve()
{

    std::cin >> n;
    for(int i=1; i<=n; i++)
    {
        std::cin >> a[i];
        pre[i] = pre[i-1] + a[i];
    }

    ll res = 0;
    for(int i=1; i<=n; i++)
    {
        res += a[i]*(pre[n]-pre[i]);
    }

    // std::cout << "ans = ";

    std::cout << res;
}


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

#ifndef ONLINE_JUDGE
    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
#endif// ONLINE_JUDGE

    // std::cin >> T;
    // T=1;
    // while(T--)
    solve();
}

D

Solution

Code

E

Solution

DP做法：令

dp[i]

为结点i爬到树顶的时间的期望值。

显然，

dp[n] = 0

，即树根爬到树根的时间期望值为0.

Code

F

Solution

Code

G

Solution

大概就是 O ( n   l o g   n ) O(n\ log\ n) O(n log n)的LIS做法中，实时更新长度的最大值。

注意边界情况。

具体看代码。

Code 

/*************************************
 * @file_name:      G.cpp.
 * @author:         minamidesi
 * @time:           Insert Date/Time.

*************************************/
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define itn int
#define memmax 0x7fffffff
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define endl '\n'

const ll MOD = 1000000007;
const int intmax = 2147483647;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const ll ulmax = 4294967295ll;

// OUTPUT
template <class a, class b>
ostream &operator<<(ostream &os, const pair<a, b> &p)
{
    os << "(" << p.first << " " << p.second << ")";
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << "[";
    if (!v.size())
        os << "]";
    else
        for (int i = 0; i < v.size(); ++i)
            os << v[i] << ",]"[i == v.size() - 1];
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &s)
{
    os << "{";
    if (!s.size())
        os << "}";
    else
        for (typename set<T>::iterator it = s.begin(); it != s.end(); it++)
            os << *it << ",}"[*it == *s.rbegin()];
    return os;
}

inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

inline void write(ll x)
{ //快写
    char F[200];
    ll tmp = x > 0 ? x : -x;
    if (x < 0)
        putchar('-');
    ll cnt = 0;
    while (tmp > 0)
    {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0)
        putchar(F[--cnt]);
}

ll n, k;
ll a[100005];
ll b[100005];
ll res;

void solve()
{
	std::cin >> n >> k;
	for(int i=1; i<=n; i++)
	{
		std::cin >> a[i];
	}

	ll len = 0;
	for(int i=1; i<=n; i++)
	{
		if(b[len] <= a[i])
		{
			b[++len] = a[i];

			ll tmp = min(n, len+k);
			res = max(res, tmp);
		}
		else
		{
			ll pt = upper_bound(b+1, b+len+1, a[i]) - b;
			b[pt] = a[i];

			ll tmp = min(n, pt+k);
			res = max(res, tmp);
		}
	}

    // std::cout << "ans = ";

    std::cout << res;
}

void run_code()
{
    solve();
}

void run_code_with_time()
{
    clock_t start, finish;
    double totaltime;
    start = clock();

    #ifndef ONLINE_JUDGE
    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    #endif// ONLINE_JUDGE

    //================================================================
    
    run_code();

    //================================================================
    
    #ifndef ONLINE_JUDGE

    finish = clock();
    totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("\n此程序的运行时间为%.36lf秒！\n", totaltime);
    
    #endif //ONLINE_JUDGE
    
}


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    run_code_with_time();

    return 0;
}

H

Solution

Code

I

Solution

显然，如果这个数可以拆分成 x 1 y 1 ⋅ x 2 y 2 x_1^{y_1}·x_2^{y_2} x1y1​​⋅x2y2​​的形式，则这个数可以表达为 x 2 ⋅ y 3 x^2·y^3 x2⋅y3的形式。

尝试枚举 x 1 x_1 x1​，看这个数除以 x 1 x_1 x1​的平方后能不能开立方，或者除以 x 1 x_1 x1​的立方后能不能开平方。

我们假设 x 1 < x 2 x_1<x_2 x1​<x2​，则枚举到两个数相同即可，复杂度为 O ( n 1 / 5 ) O(n^{1/5}) O(n1/5) ，1e18开五次方大概在4000左右，1s应该能过。

Code 

/*************************************
 * @file_name:      I.cpp.
 * @author:         minamidesi
 * @time:           Insert Date/Time.

*************************************/
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define itn int
#define memmax 0x7fffffff
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define endl '\n'

const ll MOD = 1000000007;
const int intmax = 2147483647;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const ll ulmax = 4294967295ll;

// OUTPUT
template <class a, class b>
ostream &operator<<(ostream &os, const pair<a, b> &p)
{
    os << "(" << p.first << " " << p.second << ")";
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << "[";
    if (!v.size())
        os << "]";
    else
        for (int i = 0; i < v.size(); ++i)
            os << v[i] << ",]"[i == v.size() - 1];
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &s)
{
    os << "{";
    if (!s.size())
        os << "}";
    else
        for (typename set<T>::iterator it = s.begin(); it != s.end(); it++)
            os << *it << ",}"[*it == *s.rbegin()];
    return os;
}

inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

inline void write(ll x)
{ //快写
    char F[200];
    ll tmp = x > 0 ? x : -x;
    if (x < 0)
        putchar('-');
    ll cnt = 0;
    while (tmp > 0)
    {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0)
        putchar(F[--cnt]);
}

ll T;
ll n;

void solve()
{
    std::cin >> n;

    // std::cout << "ans = ";

    // 1e5 4e3 = 4e8

    for(ll i = 1; i*i*i*i*i<=n; i++)
    {
        ll j = pow(n/i/i, 1.0/3);
        if(n/i/i == j*j*j)
        {
            std::cout << "yes\n";
            return ;
        }

        j = pow(n/i/i/i, 1.0/2);
        if(n/i/i/i == j*j)
        {
            std::cout << "yes\n";
            return ;
        }
    }

    dp[i] = dp[i-1]


    std::cout << "no\n";


}

void run_code()
{
    // std::cout << "limit = " << pow(1e18, 0.2) << endl;


    std::cin >> T;
    for(int i=1; i<=T; i++)
        solve();
}

void run_code_with_time()
{
    clock_t start, finish;
    double totaltime;
    start = clock();

    #ifndef ONLINE_JUDGE
    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    #endif// ONLINE_JUDGE

    //================================================================
    
    run_code();

    //================================================================
    
    #ifndef ONLINE_JUDGE

    finish = clock();
    totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("\n此程序的运行时间为%.36lf秒！\n", totaltime);
    
    #endif //ONLINE_JUDGE
    
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    run_code_with_time();


    return 0;
}

J

Solution

看了一眼觉得是差分约束，写了个Dijkstra，但处理不了负边，显然不合理。。。

待修改。。

Code 

/*************************************
 * @file_name:      J.cpp.
 * @author:         minamidesi
 * @time:           Insert Date/Time.

*************************************/
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define itn int
#define memmax 0x7fffffff
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define endl '\n'

const ll MOD = 1000000007;
const int intmax = 2147483647;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const ll ulmax = 4294967295ll;

// OUTPUT
template <class a, class b>
ostream &operator<<(ostream &os, const pair<a, b> &p)
{
    os << "(" << p.first << " " << p.second << ")";
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << "[";
    if (!v.size())
        os << "]";
    else
        for (int i = 0; i < v.size(); ++i)
            os << v[i] << ",]"[i == v.size() - 1];
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &s)
{
    os << "{";
    if (!s.size())
        os << "}";
    else
        for (typename set<T>::iterator it = s.begin(); it != s.end(); it++)
            os << *it << ",}"[*it == *s.rbegin()];
    return os;
}

inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

inline void write(ll x)
{ //快写
    char F[200];
    ll tmp = x > 0 ? x : -x;
    if (x < 0)
        putchar('-');
    ll cnt = 0;
    while (tmp > 0)
    {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0)
        putchar(F[--cnt]);
}

ll n, m, q;

struct edge
{
	ll next, to;
	ll weight;
}edge[100005];

ll head[100005];
ll cnt;

void addedge(ll u, ll v, ll w)
{
	cnt++;
	edge[cnt].next = head[u];
	head[u] = cnt;
	edge[cnt].to = v;
	edge[cnt].weight = w;
}

ll dis[100005];
bool used[100005];
struct node
{
	ll pos;
	ll dis;

	node(ll a, ll b)
	{
		pos = a;
		dis = b;
	}

	friend bool operator<(const node a, const node b )
	{
		return a.dis > b.dis;
	}
};

void dijkstra(ll st)
{
	for(int i=0; i<=n; i++)
		dis[i] = INT_MAX;
	memset(used, false, sizeof(used));

	dis[st] = 0;

	priority_queue<node>q;
	q.push(node(st, 0));

	while(!q.empty())
	{
		node tmp = q.top();
		q.pop();
		ll u = tmp.pos;

		if(used[u])
			continue;
		used[u] = true;

		for(int i=head[u]; i; i=edge[i].next)
		{
			ll v = edge[i].to;
			if(dis[u] + edge[i].weight < dis[v])
			{
				dis[v] = dis[u] + edge[i].weight;

				if(!used[v])
				{
					q.push(node(v, dis[v]));
				}
			}
		}
	}

}

// void print()
// {
// 	std::cout << "shortest path : ";

// 	for(int i=0; i<=n; i++)
// 	{
// 		std::cout << dis[i] << ' ';
// 	}
// 	std::cout << endl;
// }

void solve()
{
	std::cin >> n >> m >> q;
	for(int i=1; i<=m; i++)
	{
		ll u, v, w;
		std::cin >> u >> v >> w;

		addedge(u-1, v, w);
		addedge(v, u-1, -w);
	}

	for(int i=1; i<=q; i++)
	{
		ll u, v;
		std::cin >> u >> v;
		dijkstra(u-1);

		print();

    	// std::cout << "ans = ";


    	if(dis[v] == INT_MAX)
    		std::cout << "UNKNOWN\n";
    	else
    		std::cout << dis[v] << endl;
	}

}

void run_code()
{
    solve();
}

void run_code_with_time()
{
    clock_t start, finish;
    double totaltime;
    start = clock();

    #ifndef ONLINE_JUDGE
    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    #endif// ONLINE_JUDGE

    //================================================================
    
    run_code();

    //================================================================
    
    #ifndef ONLINE_JUDGE

    finish = clock();
    totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("\n此程序的运行时间为%.36lf秒！\n", totaltime);
    
    #endif //ONLINE_JUDGE
    
}


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    run_code_with_time();

    return 0;
}
算法 蓝桥杯 c++ sublime text 概率论
上一篇: 文盲的正则表达式入门，实战篇（欢迎提问，持续更新）如何写出正则？
下一篇: 学会JS的this这一篇就够了，根本不用记（强烈推荐）

继续阅读