论坛 › 物联网 › hpu萌新训练赛（三）

莫张周刘王 发表于 2025-4-5 03:14:11

hpu萌新训练赛（三）

集合
直接埃氏筛，边筛边合并就行。留意先 ans = b - a + 1 然后再计算。 分别是 j 和 j - i 这两个数来举行计算。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> PII;

bool st;
int f;

int find(int x)
{
        if (x != f) f = find(f);
        return f;
}

int main()
{
        int a, b, p; scanf("%d%d%d", &a, &b, &p);
        int ans = b - a + 1;
        for (int i = a; i <= b; i ++) f = i;
        for (int i = 2; i <= b; i ++)
        {
                if (!st)
                {
                        if (i >= p)
                        for (int j = i + i; j <= b; j += i) // j 和 j - i 是两个数，他们两个都有 i 这个质数。
                        {
                                st = true;
                                if (j - i >= a && find(j) != find(j - i))
                                {
                                        int fa = find(j), fb = find(j-i);
                                        f = fb;
                                        ans --;
                                }

                        }
                        else for (int j = i + i; j <= b; j += i)
                        st = true;
                }
        }
       
        printf("%d", ans);
        return 0;
}

迷宫寻路
这个是一道非常典型的 dfs 题目。
走过的记得更新为 # 即可。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> PII;
constexpr int N = 110;
char g;

int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
int n, m;
int ans;
int cnt;
void dfs(int x, int y)
{
        if (x == n && y == m)
        {
                ans = 1;
                return;
        }
        g = '#';
        // // cnt++;
        // if (cnt > 1e5)
        // {
        //         ans = 1e9;
        //         return;
        // }
        for (int i = 0; i < 4; i++)
        {
                int ux = x + dx, uy = y + dy;
                if (ux > n || ux < 1 || uy > m || uy < 1 || g == '#')
                        continue;
                dfs(ux, uy);
        }
}

void solve()
{
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                {
                        char ch;
                        cin >> ch;
                        g = ch;
                }
        dfs(1, 1);
        if (ans == 1)
        {
                printf("Yes");
        }
        else
                printf("No");
}

signed main()
{
        int _ = 1;
        // cin >> t;
        while (_--)
        {
                solve();
        }
        return 0;
}
P1464 Function
这个题目用到了影象化搜索的方法。假如我已经计算过 w(a, b, c) 了，那我就把他存下来，如许以后就不需要再举行重复计算了。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> PII;

int dp;

i64 w(i64 a, i64 b, i64 c)
{
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20)
{
    if (dp) return dp;
    dp = w(20, 20, 20);
    return dp;
}
if (a < b && b < c)
{
    if (dp) return dp;
    if (!dp) dp = w(a, b, c - 1);
    if (!dp) dp = w(a, b - 1, c - 1);
    if (!dp) dp = w(a, b - 1, c);
    dp = dp + dp - dp;
    return dp;

}
if (!dp) dp = w(a - 1, b, c);
if (!dp) dp = w(a-1, b-1, c);
if (!dp) dp = w(a-1, b, c-1);
if (!dp) dp=w(a - 1, b - 1, c - 1);
return dp + dp + dp - dp;
}

int main()
{
i64 a, b, c;
while (cin >> a >> b >> c)
{
    if (a == -1 && b == -1 && c == -1)
    {
      return 0;
    }
    printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));
}
return 0;
}

P1009 阶乘之和
这个题目用到了一个东西叫做大数，也叫高精度。可以用 c++ 代码实现，也可以用 python 来实现。python 来实现比较简单一点。
n = int(input())
x = 1
ans = 0
for i in range(1, n + 1):
    x *= i
    ans += x
print(ans)
P1496 火烧赤壁
这个题目用到了离散化和差分。
#include <bits/stdc++.h>
using i64 = long long;
using namespace std;
typedef pair<int, int> PII;

vector<int> id;

int get(int x)
{
return lower_bound(id.begin(), id.end(), x) - id.begin() + 1;
}

/*
把数映射到另一个东西里面
*/

void solve()
{
int n;
scanf("%d", &n);
int mmax = -1, mmin = 2e9;
map<i64, i64> c;
vector<PII> cor;
for (int i = 0; i < n; i++)
{
    int l, r;
    scanf("%d%d", &l, &r);
    id.push_back(l);
    id.push_back(r);
    cor.push_back({l, r});
}
sort(id.begin(), id.end());
id.erase(unique(id.begin(), id.end()), id.end());

for (auto : cor)
{
    int xx = get(x), yy = get(y);
    c += 1, c -= 1;
    mmin = min(mmin, xx);
    mmax = max(mmax, yy);
}
for (int i = mmin; i < mmax; i++)
{
    c += c;
    // cout<<c<<' ';
}
// printf("mmin = %d mmax = %d", mmin, mmax);
int ans = 0,l=0,r=0;
while(r<mmax){
    while(l<mmax && c==0)l++,r++;
    while(r<mmax && c!=0)r++;
    int ln=id,rn=id;
    ans+=(rn-ln);
    // printf("l = %d r = %d\n", l, r);
    l = r;
}
cout << ans<<'\n';
}

signed main()
{
int t = 1;
// cin >> t;
while (t--)
{
    solve();
}
return 0;
}
P1469 找筷子
这个题目用到了异或的一个性子，对一个数同时异或两次的话这个数就相当于没有异或。所以直接默认一开始为 0 ，然后不停异或就行了。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long i64;

void solve()
{
int n; scanf("%d", &n);
int x = 0;
for (int i = 0; i < n; i++)
{
    int u; scanf("%d", &u);
    x ^= u;
}
cout << x;
}

signed main()
{
int t = 1;
// cin >> t;
while (t--)
{
    solve();
}
return 0;
}
P2626 斐波那契数列（升级版）
这个题目的关键在于分解质因数。求斐波那契数列的话，直接递推即可。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> PII;
constexpr int N = 50 + 10;
i64 f;
const int M = 2147483648;

void init()
{
        f = 1;
        f = 1;
        for (int i = 3; i <= 48; i++)
                f = f + f;
        for (int i = 1; i <= 48; i++)
        {
                f %= M;
        }
}

void solve()
{
        init();
        // for (int i = 1; i <= 48; i ++)
        // {
        //         cout << f << "\n";
        // }
        int n;
        cin >> n;
        i64 x = f;
        map<int, int> mp;
        int mmin = 2e9;
        for (int i = 2; i * i <= x; i++)
        {
                if (x % i == 0)
                {
                        mmin = min(mmin, i);
                        while (x % i == 0)
                        {
                                mp++;
                                x /= i;
                        }
                }
        }
        if (x > 1)
        {
                mmin = min(mmin, int(x));
                mp++;
        }
        printf("%lld=", f);
        for (auto m : mp)
        {
                if (m.first == mmin)
                {
                        printf("%d", m.first);
                        for (int i = 2; i <= m.second; i++)
                                printf("*%d", m.first);
                }
                else
                        for (int i = 1; i <= m.second; i++)
                                printf("*%d", m.first);
        }
}

signed main()
{
        int _ = 1;
        // cin >> t;
        while (_--)
        {
                solve();
        }
        return 0;
}
P3879 阅读明白
这个题目用到了 map<string, vector> 这个 stl 容器。会用这个容器的话然后举行一下去重就能做出来了。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> PII;

int main()
{
int n; scanf("%d", &n);
map<string, vector<int>> mp;
for (int i = 1; i <= n; i ++)
{
    int x; scanf("%d", &x);
    for (int j = 1; j <= x; j ++)
    {
      string u; cin >> u;
      mp.push_back(i);
    }
}
int m; scanf("%d", &m);
while (m --)
{
    string s; cin >> s;
    sort(mp.begin(), mp.end());
    mp.erase(unique(mp.begin(), mp.end()), mp.end());
    for (int i = 0; i < mp.size(); i ++)
    {
      printf("%d ", mp);
    }
    printf("\n");
}
return 0;
}

P1024 一元三次方程求解
这个题目直接暴力就行了，不外是浮点数暴力，每次加上 0.01 然后判定这个答案行不可。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> PII;

double a, b, c, d;

double ck(double x)
{
        double l = x - 0.001, r = x + 0.001;
        if ((a * pow(r, 3) + b * pow(r, 2) + r*c + d < 0) && (a * pow(l, 3) + b * pow(l, 2) + c * l + d > 0) ||(a * pow(r, 3) + b * pow(r, 2) + r*c + d > 0) && (a * pow(l, 3) + b * pow(l, 2) + c * l + d < 0))
                return true;
        return false;
}

void solve()
{
        cin >> a >> b >> c >> d;
        for (double i = -100.0; i <= 100.0; i += 0.01)
        {
                if (ck(i))
                printf("%.2lf ", i);
        }
}

signed main()
{
        int _ = 1;
        // cin >> t;
        while (_--)
        {
                solve();
        }
        return 0;
}

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

查看完整版本: hpu萌新训练赛（三）