TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!) (B,C,D)
B
这道题的大意是给你一个数\(n\),我们可以把这个\(n\),变成\(x_1^{y_1} * x_2^{y_2} ...... x_j^{y_j}\),如果变成这样的形式，我们可以得到一个值
\({x_1} * {y_1}+{x_2} * y_2 +...+ x_j * y_j\),我们要把这个数变得尽量的大，但是这里面的\(x\)只能是任意个不同的质数（x是由不同的质数相乘得到的）
对于这个\(n\),我们先可以把他变成\(x_1^{y_1} * x_2^{y_2} ...... x_j^{y_j}\)，然后对于幂次，如果是1，那么我们可以使用一次，可以$ (x_1+x_2+x_3) * 1)$,对于幂次为2的，我们可以让他使用两次，最后一次是第\(2\)次，可以让 $ (x_2+x_3) * 1)$,对于幂次为3的，可以利用\(3\)次，那么对于第三段，这里面的数幂次都是大于等于\(3\)的
那么我们可以求一个数组 \(sum[i]\)是\(i\)到最大幂次（我们这里用\(30\)),的数的乘积，这里面所有的数都只会出现一次，符合条件，而且每一个数都在最大价值的用到了
#include <iostream>
#include <algorithm>
#include <vector>
#include<map>
using namespace std;
#define int long long
int t,n;
void solve()
{
cin>>n;
map<int,int>cnt;
for (int i=2;i*i<=n;i++)
{
if (n%i==0)
{
int tot=0;
while (n%i==0)
{
n/=i;
tot++;
}
cnt[i]=tot;
}
}
if (n>1)
{
cnt[n]=1;
}
vector<int>sum(40,1);
for (auto[x,tot]:cnt)
{
sum[tot]*=x;
}
for (int i=30;i>=1;i--)
{
sum[i]*=sum[i+1];
}
int ans=0;
for (int i=1;i<=30;i++)
{
if (sum[i]>1)
{
ans+=sum[i];
}
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
C
这个题大意是给出一个长度为\(n\)的数，还有一个\(s\),我们需要构造两个数组\(x\)和\(y\),
并且满足\(x_i+y_i=a_i\)和\((s-x_i)*(s-y_i)>=0\)
我们也可以得到一个\(F\),其中\(F\)的公式求出如下
\[F=a_1\times x_2+y_2\times x_3+y_3\times x_4 \ldots y_{n-2}\times x_{n-1}+y_{n-1}\times a_n \]然后对于\(x\)和\(y\),我们要怎么构造呢
反正是乘法，那我们要尽量大的和大的相乘，那么\(x\)或者\(y\),要么是那个可以成为的最大的那一个，要么是较小的那一个,那么我们可以记录每一个\(a_i\),我们都可以得到一个\(mx_i,mi_i\),然后再求最小
我们还用到了
\(f[i] [0]\)说明这\(y_i\)是\(mi_i\),那么\(x_i\)就是\(mx_i\)
\(f[i] [1]\)说明这\(y_i\)是\(mx_i\),那么\(x_i\)就是\(mi_i\)
然后按照题目中给出的求\(min\)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn=2e5+10;
#define int long long
int f[maxn][2];
int a[maxn],mi[maxn],mx[maxn];
int n,t,s;
void solve()
{
cin>>n>>s;
for (int i=1;i<=n;i++)
{
cin>>a[i];
if (a[i]>=2*s)
{
mi[i]=s;
mx[i]=a[i]-s;
}
else if (a[i]>=s)
{
mx[i]=s;
mi[i]=a[i]-s;
}
else
{
mi[i]=0;
mx[i]=a[i];
}
}
f[2][0]=a[1]*mi[2];
f[2][1]=a[1]*mx[2];
for (int i=3;i<n;i++)
{
f[i][0]=min(f[i-1][0]+mx[i-1]*mi[i],f[i-1][1]+mi[i-1]*mi[i]);
f[i][1]=min(f[i-1][0]+mx[i-1]*mx[i],f[i-1][1]+mi[i-1]*mx[i]);
}
int ans=min(f[n-1][0]+mx[n-1]*a[n],f[n-1][1]+mi[n-1]*a[n]);
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
D
这个题大意是我们一开始在\(1\)的位置，如果我们走到了\(i\)位置上，那么下一步我们可以走到\(i+a_i\)上
我们可以把\(a_i\)变成一个\(y\),（\(y\)可以是\(a_i\) )\(\lvert y \lvert <=n\),如果走到的位置\(pos\),\(1<=pos<=n\),那么他还需要继续走，如果不在这一个范围里，那么说明他可以不再走了，游戏结束
我们可以把\(a_i\)变成\(y\),可以让我们游戏结束可以确定是走了多少步的改变有多少种（不出现死循环）
我们有两种不同的情况
如果从\(1\)就可以直接结束，那么有太多种了，就算是\(1\)到不了的点不管怎么改变都可以
所谓正难则反，我们就用所有的改变方法，再减去那些会达到死循环的变化
对于那些可以不会进入死循环的那些点，如果要再是进入那些不会进行死循环的点，那么就相当于这个路程已经出现了循环，那么是不可的
还不可以进入那些本来就是死循环的节点，也是不可
所以不可变成的有\(siz[u]+n-(siz[0]-1)\)个（我们反向建图，对于那些出界的点，我们一律记为\(0\)，从\(0\)出发，\(siz[i]\)是从0到达\(i\)有多少个节点,用到\(siz[0]\)如果用到要记得减一，不包括本身\(0\))
如果从\(1\)出发就是一个死循环，那么对于从\(1\)到\(i\)这一路，没有出现循环之前，每一个点都有以下几种改变可以让这个路径变成可以到达点\(0\)
如果此时在\(i\)点
第一种，直接出界，我们发现，每一个位置，都有\(n+1\)个可以直接变成点\(0\),(这里的\(0\)不是单纯的\(0\),而是绝对值大于\(n\)的数)
第二种，从\(i\)走到那些可以到达\(0\)的位置，而且那些一定位置一定是没出界的，所以不会重复，有\(siz[0]-1\)个点
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
const int maxn=2e5+10;
int n,t;
vector<int>g[maxn];
int siz[maxn],f[maxn],a[maxn];
vector<bool>vis;
void dfs(int u)
{
siz[u]=1;
for (auto v:g[u])
{
dfs(v);
siz[u]+=siz[v];
}
return ;
}
void solve()
{
cin>>n;
vis=vector<bool>(n+1,false);
for (int i=0;i<=n;i++)
{
g[i].clear();
siz[i]=0;
}
for (int i=1;i<=n;i++)
{
cin>>a[i];
int nxt=i+a[i];
if (nxt>n||nxt<=0) nxt=0;
g[nxt].push_back(i);
f[i]=nxt;
if (nxt==0) vis[i]=true;
}
dfs(0);
int ans=0;
if (siz[1])
{
ans=n*(2*n+1);
int u=1;
while (u)
{
ans-=siz[u];
ans-=(n-(siz[0]-1));
u=f[u];
}
}
else
{
vector<int>v(n+1,0);
int u=1;
while (u)
{
if (v[u]) break;
v[u]=1;
ans+=n+1;
ans+=siz[0]-1;
u=f[u];
}
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}