A
核心思路
直接把其中一个数置为1就好了。
// Problem: A. Exponential Equation
// Contest: Codeforces - TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/contest/1787/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
void solve()
{
int n;
cin>>n;
int y=1;
if(n%2)
{
cout<<-1<<endl;
return ;
}
cout<<n/2<<" "<<1<<endl;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
B
核心思路
我们可以把任何一个数表示为:\(n=a_1^{p_1}*a_2^{p_2}*....a_k^{p_k}\).
100=2^2*5*2=(2*5)^2;
n=2^2*3^3*5*4=(2*3*5)^2*3*4;
所以总的做法就是这样先对指数排序，然后一个一个合并。不要怀疑自己的做法，指针分析不清楚的时候，自己多画图吧。
// Problem: B. Number Factorization
// Contest: Codeforces - TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/contest/1787/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
const int N = 1e6 + 10;
struct S
{
int a, p;
}s[N];
int cmp(S x, S y)
{
return x.p < y.p;
}
void solve()
{
int m;
int cnt = 0;
cin >> m;
int i, sum;
for (i = 2;i <= m / i;i++)
{
sum = 0;
while (m % i == 0)
{
sum++;
m /= i;
}
if (sum > 0)
s[cnt++] = { i,sum };
}
if (m > 1)
s[cnt++] = { m,1 };
sort(s, s + cnt, cmp);
int k = 0, ans = 0;
for (int i = 0;i < cnt;i++)
{
int sum = 1;
int t = s[k].p;
for (int j = k;j < cnt;j++)
{
sum *= s[j].a;
s[j].p = s[j].p - t;
}
k++;
sum *= t;
ans += sum;
}
if (s[cnt - 1].p)
ans += s[cnt - 1].a * s[cnt - 1].p;
cout << ans << endl;
}
signed main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}
C
核心思路
首先分析操作性质：\(a_i=x_i+y_i\).然后我们发现\(x_i,y_i\)只会出现在:\(y_{i-1}*x_i+y_i*x_{i+1}=y_{i-1}*x_i+(a_i-x_i)*x_{i+1}\).
然后我们可以发现这是一个一元函数，因为我们把\(y_{i-1}和x_{i+1}\)先看成常数就好了，所以\(x_i\)取最值那么这一部分也是可以取得到最值的。
所以这个题目的思路也就是先从局部最小值，然后分析出来整个函数的最大值和最小值。因此我们可以使用dp来做。
集合定义：\(dp[i][0/1]表示的的是F函数再x_i取得最大值/最小值\)
集合划分：可以由两个状态转移过来
- \(x_{i-1}取得最大值\)
- \(x_{i-1}取得最小值\)
// Problem: C. Remove the Bracket
// Contest: Codeforces - TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/contest/1787/problem/C?mobile=true
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
const int N=1e6+10;
int a[N],v[N][2],dp[N][2];
int n,s;
void solve()
{
cin>>n>>s;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=2;i<=n-1;i++)
{
if(a[i]<=2*s)//这里就只能都小于s了。
{
v[i][0]=min(a[i],s);
v[i][1]=a[i]-v[i][0];
}
else
{
v[i][1]=s;
v[i][0]=a[i]-s;
}
}
//初始化
v[1][1]=v[1][0]=a[1];
v[n][1]=v[n][0]=a[n];
for(int i=2;i<=n;i++)
{
dp[i][1]=min(dp[i-1][1]+v[i-1][0]*v[i][1],dp[i-1][0]+v[i-1][1]*v[i][1]);
dp[i][0]=min(dp[i-1][1]+v[i-1][0]*v[i][0],dp[i-1][0]+v[i-1][1]*v[i][0]);
}
cout<<min(dp[n][1],dp[n][0])<<endl;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}