426

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;
}

}


#### 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;
}


#### 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;
}


#### 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;
}