A.Prefix and Suffix Array
算法本质
思维
题目大意
对于字符串S，给你所有的前缀字符串、后缀字符串（除了本身、空字符串）。
判断s是否是回文字符串。
思路推演
所有给出的长度相等的字符串，判断其是否倒置相等。
B.Not Dividing
算法本质
思维
题目大意
给一数组a[]长度为n，可以给任意元素+1操作，最多操作2n次。
保证其a[i+1]%a[i] != 0。
输出操作后的数组a[]。
思路推演
对于一组a[i] 和 a[i+1]：
- 修改
a[i]
如果遇到了3 3*4*5这样的数字，不止需要改修2次，pass - 修改
a[i+1]
如果保证a[i]!=1，则a[i+1]至多修改一次，就上保证前者不为1的一次修改，2n次修改足矣
C.Scoring Subsequences
算法本质
思维、数据结构
题目大意
给定长度为n的数组a[]，其有收益和成本2个属性：
- 收益
所有元素的乘积 除以 长度的阶乘 - 成本
其收益最大的子数组（可能为自己或空）的最大长度
现在请给出n个前缀a[]的数组成本。
思路推演
子数组的收益，随着元素个数的增加，有明显的单调性。
所以是可以用二分来做的。
二分做法相对简单多样，不与介绍。
下面说一下此题原本的O(n)做法。
仔细观察，会发现其实收益的计算方式很简单——讲所有元素排序，从较小值开始，如果其值小于保留元素的个数，则丢弃较小值。
所有完全只有一个优先列队历便即可。
另外题目给的a[]是有序的，这代表可以可以只用一个双端队列，达到O(n)做法。
不过因为本身有序，好像用优先队列，也不会增加复杂度
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn];
inline void solve()
{
//init
cin>>n;
rep(i,1,n) cin>>a[i];
//cal
deque <int> q;
for (int i=1; i<=n; i++)
{
q.push_back(a[i]);
if (q.front() < q.size())
q.pop_front();
cout<<q.size()<<" ";
}
cout<<endl;
return;
}D.Counting Factorizations
算法本质
思维、dp
题目大意
已知任何一个正整数都可以用素数指数幂的形式表示，例如24 = 2^3 * 3^1。
则设立一函数，例子：f(24) = {2 3 3 1} = {2 1 3 3} = f(54)。
现在给出2n个元素，组成了上述的集合，请输出多少正整数的函数值为当前集合。
n <= 2e3思路推演
如果随便选n个元素当底数，则有$n!$种情况，如果考虑重复，则还需要除以除去重复数字的阶乘。
所以可以发现，此题的重点，就是处理各种重复情况。
将集合里只有素数可以当底数（且不能重复）。
则把集合里的素数种类列出来，这些是有可能作为底数的存在，设有m类。（其他元素必定为指数）
我们定义一个基础值res = n!，然后除以必定为指数的元素的重复部分。
接下来根据有m类素数，但是只选择其中n种，意味还需要丢掉m-n个素数，而每丢掉一个素数，得到的值都是res除以其重复的次数（相当于乘以其小球分数）。
现阶段的题意，可以转化为：
有n个不同的小球，每种小球的分数为a[i]，现在要求选k个小球出来，
得分为所有小球分数相乘，现在输出将所有情况的得分相加值。选择dp优化，dp[x][y]表示前x个数丢掉y个。dp[x][y] = dp[x-1][y] + dp[x-1][y-1]*a[x]
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn];
int dp[maxn][maxn];
int fac[maxn];
bool is_prime(int x)
{
if (x==1) return false;
for (int i=2; i*i<=x; i++)
if (x%i==0)
return false;
return true;
}
inline void solve()
{
//init
cin>>n;
for (int i=1; i<=2*n; i++)
cin>>a[i];
fac[0] = 1; //预处理阶乘，要处理到2n
for (int i=1; i<=2*n; i++)
fac[i] = fac[i-1]*i%mod;
//cal
int res=fac[n];
map<int, int> not_prime, prime; //val --> count
vector <int> prime_list;
prime_list.push_back(0);
for (int i=1; i<=2*n; i++)
{
if (is_prime(a[i])) //是素数
prime[a[i]]++;
else
not_prime[a[i]]++;
}
for (auto u:not_prime) //除以非素数的重复部分
{
res *= qpow(fac[u.second], mod-2, mod);
res %= mod;
}
for (auto u:prime) //除以素数的重复部分（未彻底处理）
{
res *= qpow(fac[u.second-1], mod-2, mod);
res %= mod;
prime_list.push_back(u.first);
}
m = prime.size(); //m表示素数的“种类”数
if (m < n) //特殊判断s
{
cout<<0<<endl;
return;
}
//cal 2
dp[1][0] = 1;
dp[1][1] = qpow(prime[prime_list[1]], mod-2, mod);
for (int x=2; x<=m; x++)
{
for (int y=0; y<=min(m-n, x); y++)
{
dp[x][y] = dp[x-1][y]; //dp转移公式
if (y>0)
dp[x][y] += dp[x-1][y-1] * qpow(prime[prime_list[x]], mod-2, mod);
dp[x][y] %= mod;
}
}
int ans = dp[m][m-n] * res % mod;
//output
cout<<ans<<endl;
return;
}
评论 (0)