头像

华胥梦断




在线 


最近来访(5)
用户头像
我醒醒
用户头像
wscjx2
用户头像
1013308992
用户头像
沈清秋
用户头像
.x


华胥梦断
18小时前

参考文献

PAT甲级辅导课

C++ 代码

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

const int N = 1e4+10;

int n = 0;
int w[N], l[N];
int sum = -1;


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

    int res = -1, l = 0, r = 0;
    for(int i = 1, start = 0; i <= n; ++i)
    {
        if(sum < 0) sum = 0, start = i;
        sum += w[i];
        if(res < sum )
        {
            res = sum;
            l = w[start], r = w[i];
        }
    }
    if(res < 0) res = 0, l = w[1], r = w[n];
    cout << res << " " << l <<" " << r << endl;

    return 0;
}



参考文献

C++ 代码

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

int n, k;
string s;

bool isprime(int x)
{
    if(x == 0) return false;
    if(x == 1) return true;
    for(int i = 2; i <= x / i; ++i)
    {
        if(x % i == 0) return false;
    }
    return true;
}

int main()
{
    cin >> n >> k;
    getchar();
    getline(cin, s);

    for(int i = 0 ; i <= s.size()-k; ++i)
    {
        auto str = s.substr(i,k);

        LL x = stoi(str);
        if(isprime(x)) 
        {
            cout << str << endl;
            return 0;
        }

    }
    cout << "404" << endl;

    return 0;
}



参考文献

抄的别人的题解,主要是为了方便自己复习
https://www.acwing.com/solution/content/13204/

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 410;

int n, k,p;
int v[31];

int reSum = -1;
vector<int> path, ans;


/**
i当前递归到的因子,n:选取的因子数i^p的和(初始化为n),
cnt 选取的因子的个数,sum:选取的因子数之和
**/
void DFS(int i, int n, int cnt, int sum)
{
    if(n == 0 && cnt == k)
    {
        if(sum > reSum)
        {
            reSum = sum;
            ans = path;
        }
        return ;
    }

    while(i > 0)
    {
        //剪枝防止递归爆栈
        if(n - v[i] >= 0 && cnt + 1 <= k)
        {
            path[cnt] = i;
            DFS(i,n-v[i], cnt+1, sum+i);
        }
        --i;
    }
}

int main()
{

    cin >> n >> k >> p;
    path.resize(k);
    int i = 0;
    while(pow(++i, p) <= n)
        v[i] = pow(i,p);

    --i;
    DFS(i,n,0,0);
    if(reSum == -1) puts("Impossible");
    else
    {
        cout << n << " = " << ans[0] << "^" << p;
        for(int i = 1; i < ans.size(); ++i)
            cout << " + " << ans[i] << "^" << p;
    }

}



参考文献

思路源自PAT甲级辅导课

C++ 代码

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

int main()
{
    int n = 0;
    cin >> n;

    vector<int> res;
    for(int i = 2; i <= n / i; ++i)
    {
        if(n % i == 0)
        {
            vector<int> seq;
            for(int m = n, j = i; m % j == 0; ++j)
            {
                seq.push_back(j);
                m /= j;
            }
            if(seq.size() > res.size()) res = seq;
        }
    }

    if(res.size() == 0) //特判
        res.push_back(n);

    cout <<res.size() << endl;
    for(int i = 0; i < res.size(); ++i)
    {
        cout << res[i];
        if(i < res.size() -1)
            cout << "*";
    }

    return 0;
}



参考文献

参考PAT甲级辅导课

C++ 代码

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

LL gcd(LL a, LL b)
{
    // if(a < b)
    //     swap(a, b);
    return b == 0 ? a : gcd(b, a%b);
}

int main()
{
    LL a=0, b=1;
    int n = 0;
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        LL c,d;
        scanf("%lld/%lld", &c, &d);

        LL t = gcd(c,d);

        c /= t, d /= t;

        t = gcd(b ,d); //当心 b*d的积溢出
        a = d /t * a + b/t * c;
        b = b/t*d;

        t = gcd(a,b);
        a /= t, b /= t;

    }

    if(b == 1) cout << a << endl;
    else
    {
        if(a >= b)
        {
            cout << a /b << " ";
            a %= b;
        }
        cout << a << "/" << b << endl;
    }
    return 0;
}



参考文献

C++ 代码

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

bool prime(int x)
{
    for(int i = 2; i <= x /i; ++i)
    {
        if(x % i == 0)
            return false;
    }
    return true;
}

map<int,int> mp;

void calc(int n)
{
    cout << n << "=";
    if(n == 1)
    {
        cout << 1 << endl;
        return ;
    }

    //质因数分解算法
    for(int i = 2; i <= n / i; ++i)
    {
        if(n % i == 0)
        {
            while(n % i == 0)
            {
                ++mp[i];
                n /= i;
            }
        }
    }


    if(n != 1) mp[n] = 1;

    int idx = 0, len = mp.size();
    for(const auto&[k ,v] : mp)
    {
        if(v == 1)
            cout << k;
        else
            cout << k << "^" << v;
        if(idx != len-1)
            cout << '*';
        else
            cout << endl;
        ++idx;
    }


}

int main()
{
    int n;
    cin >> n;
    calc(n);
    return 0;
}



参考文献

思路可以参考:https://www.acwing.com/solution/content/73112/

C++ 代码

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

int n = 0;

int calc(int n)
{
    vector<int> nums;
    while(n)
    {
        nums.push_back(n%10);
        n /= 10;
    }
    int res = 0;
    for(int i = nums.size()-1; i >= 0 ;--i)
    {
        int d = nums[i];
        int left = 0, right = 0, power = 1;
        for(int j = nums.size()-1; j > i; --j) left = left * 10 + nums[j];

        for(int j = i-1; j >= 0; --j)
        {
            right = right*10 + nums[j];
            power *= 10;
        }

        if(d == 0) res += left * power;
        else if(d == 1) res += left*power + right + 1;
        else res += (left+1)*power;
    }
    return res;
}

int main()
{
    cin >> n;
    cout << calc(n) << endl;
    return 0;
}



参考文献

https://www.acwing.com/solution/content/57504/

C++ 代码

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

const int N = 5e4+10;
int n = 0;

int in[N], pre[N];
// int l[N], r[N];
unordered_map<int,int> l,r; //注意本题可没有限制节点值的范围,不能再用数组存储左右孩子了
int post[N];

unordered_map<int,int> mp;
int res = 0;

int build(int il ,int ir, int pl, int pr)
{
    if(il > ir) return -1;
    int root = pre[pl];
    int k = mp[root];

    l[root] = build(il, k-1, pl+1, pl+k-il);
    r[root] = build(k+1,ir, pl+k-il+1, pr);

    if(res == 0)
        res = root;
    return root;

}


int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)  scanf("%d", &pre[i]);
    for(int i = 0; i < n; ++i) scanf("%d", &in[i]), mp[in[i]] = i;

    int root = build(0, n-1, 0, n-1);
    cout << res << endl;
    return 0;
}



参考文献

https://www.acwing.com/solution/content/64899/

C++ 代码

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


struct node
{
  int data;
  node* left, *right;
  node(int _da=0):data(_da){
      left = nullptr;
      right = nullptr;
  }
};

const int N = 5e4+10;
int pre[N], ino[N];
vector<int> res;
unordered_map<int, int> mp;

int n = 0;

node* create(int il, int ir, int pl, int pr)
{
    // if(il > ir) return nullptr;
    node* root = new node(pre[pl]);
    int k = mp[pre[pl]];
    if(k > il) //此处如果加了if判断,则必须在node的构造函数中显示初始化letf指针和right指针,否则会导致段错误
        root->left = create(il,k-1,pl+1,pl+k-il); 
    if(k < ir ) root->right = create(k+1, ir,pl+k-il+1,pr);

    return root;
}

void postorder(node* root)
{
    if(root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    res.push_back(root->data);
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%d", &pre[i]);
    for(int i = 0; i < n; ++i)
    {
        scanf("%d", &ino[i]);
        mp[ino[i]] = i;
    }

    auto root = create(0,n-1,0,n-1);
    postorder(root);
    printf("%d\n", res[0]);

    return 0;
}



C++ 代码

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

const int N = 5e4+10;
int n = 0;

LL in[N], pre[N];
LL l[N], r[N];
LL post[N];


unordered_map<LL,LL> mp;
LL res = 0;

void build(LL il ,LL ir, LL pl, LL pr)
{
    LL root = pre[pl];
    LL k = mp[root];
    if(k > il) 
        // l[root]=build(il, k-1, pl+1, pl+k-il);
        build(il, k-1, pl+1, pl+k-il);
    if(k < ir) 
        // r[root]=build(k+1,ir, pl+k-il+1, pr);
        build(k+1,ir, pl+k-il+1, pr);

    if(res == 0)
        res = root;

    // return root;

}


int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)  scanf("%ld", &pre[i]);
    for(int i = 0; i < n; ++i) scanf("%ld", &in[i]), mp[in[i]] = i;

    // LL root = build(0, n-1, 0, n-1);
    build(0, n-1, 0, n-1);
    cout << res << endl;
    return 0;
}