11.4 模拟赛
这分数羞于出口（fuck）
T1 大空魔术
题目：
宇佐见莲子是一个向往太空旅行的大学生。但迫于月面旅行团高额的费用，她暂时放弃了幻想，开
始专心于物理学的研究。
在一次偶然的经历中，莲子发现了两种新的粒子，她将这两种粒子命名为「粒子 A」和「粒子 B」 。
莲子发现，两种粒子在不受外界刺激的情况下可以保持稳态，并且会相互吸引。多个粒子在相互的
吸引力作用下会形成一个有序的序列。
莲子还发现，当特定种类的两个粒子以特定方式排列时，给予它们一种特定的刺激，就会发生「互
毁」现象：两个粒子会发生完全的物质-能量转换，转化为大量能量。
经过长时间的研究，莲子发现了「互毁」现象发生的条件：当前仅当相邻的两个粒子呈现：”AB”
或”BB” 的形式时，给予特定刺激后它们才会发生「互毁」 。
现在，莲子在实验室中将众多粒子排成了多个序列，她想通过给予刺激的方式，用这些粒子得到尽
可能多的能量，即留下尽可能少的粒子。
由于粒子会相互吸引，每当相邻的两个粒子发生「互毁」后，它们左右两侧的粒子还会拼在一起，
仍然保持一个序列的形态。
但粒子数实在是太多了，于是她找到你，请你帮助她求出最后剩余粒子数的最小值。
输入：
第 1 行一个整数 t，代表粒子序列的个数。
第 2∼ t 行，第 i + 1 行包含一个只由字符 ‘A’ 和 ‘B’ 构成的字符串 \(s_i\) ，描述了一个粒子序列。
输出：
一个整数，代表最后剩余粒子数
样例：
3
AAA
BABA
AABBBABBBB
3
2
0
解题思路：
对于这个有序序列，我们能删就删，尽管有 ABBA这种情况，我们发现会有 两种删法，但是它产生的贡献却都是一样的，都是 2，所以我们可以根据这个贪心，枚举子串，### 利用一下栈，然后碰上A就入栈，碰上B就出栈，因为无论什么情况，造成出栈的一定是有B的子串，所以枚举到最后只需要看一下还剩下多少就OK了，
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <cstdlib>
#define inf 0x3f
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return x*f;
}
std::stack<char> s;
int main()
{
int t=read();
while(t--)
{
std::string ch;
std::cin>>ch;
for(int i=0;i<=ch.length();i++)
{
if(ch[i]=='A')
{
s.push(ch[i]);
continue;
}
else if(ch[i]=='B')
{
if(s.empty())
{
s.push(ch[i]);
}
else
{
//char top=s.top();
s.pop();
}
}
}
printf("%d\n",s.size());
}
return 0;
}
T2 夜桜街道
题目描述：
深夜，离开实验室后，莲子与好友梅丽相约来到了一条长满樱花树的街道，她们决定从街道的左侧
某个位置出发向右走，欣赏沿途的每一棵樱花。
她们发现，这条街道上共有 n 棵樱花树，从左到右的编号依次为 1,2,···n，每一棵樱花树都有自
己的美丽值，编号为 i 的樱花树的美丽值为\(a_i\)。
莲子喜欢惊喜的感觉。若她以某个位置作为起点向右走，她看到一棵樱花树的惊喜度定义为：从起
点到这棵树途经的所有树中，比这棵树的美丽值小的个数。
梅丽决定用平均值描述莲子的平均惊喜度。她定义区间 [l,r] 的平均惊喜度为，从樱花树 l 开始走，
向右走到樱花树 r 时，看到所有樱花树的惊喜度之和，除以区间中樱花树的个数。
现在，莲子和梅丽想知道，以樱花树 1 为起点，分别以樱花树 1 ∼ n 为终点时，莲子的平均惊喜
度之和。
由于她俩都不喜欢小数，你只需要输出这个值对 998244353 取模的结果。
输入：
第 1 行一个整数 n，表示樱花树的棵树。
第 2 行有 n 个整数，第 i 个整数表示编号为 i 的樱花树的美丽值\(a_i\)。
输出：
一行一个整数，表示答案。
样例：
6
1 1 4 5 1 4
748683269
数据：
对于测试点 1 ∼ 6 ，保证 n ≤ 1000。
对于测试点 1 ∼ 10，保证 n ≤ 5000。
对于测试点 1 ∼ 20，保证 n ≤\(10^6\)。
对于所有测试点，保证 n ≤\(10^6\) ，0 ≤\(a_i\)≤\(2^{30}-1\)。
解题思路:
我们输入每个\(a_i\)的时候我们可以用树状数组去维护一下它前面的比它小的数,怎么统计，我们就可以考虑权值树状数组，但是数据开不了，所以需要离散化一下，然后在，如果
离散化的话，就求个顺序对，然后，再利用逆元，求解就行了。
代码：
未进行离散化的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <cstdlib>
#define inf 0x3f
#define lowbit(x) x&(-x)
#define int long long
const int maxn=1e6;
const int mod=998244353;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n;
int num[maxn],s[maxn],tree[maxn],inv[maxn];
int MAX;
void add(int x,int k)
{
for(int i=x;i<=MAX;i+=lowbit(i))
{
tree[i]++;
}
}
int find(int x)
{
int sum=0;
for(int i=x;i>=1;i-=lowbit(i))
{
sum+=tree[i];
}
return sum;
}
signed main()
{
n=read();
for(int i=1;i<=n;i++)
{
num[i]=read();
MAX=std::max(MAX,num[i]);
}
for (int i = 1; i <= n; i++)
{
s[i]=find(num[i]-1);//小于等于的为 find(num[i]),
//std::cout<<s[i]<<"TEXT"<<std::endl;
add(num[i],1);
}
int ans=0;
inv[1]=1;
/*for(int i=1;i<=n;i++)
{
// -k * r_-1
inv[i]=(-p/i)*inv[p%i];
} */
for(int i=2;i<=n;i++)
{
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
for(int i=1;i<=n;i++)
{
s[i]+=s[i-1];
s[i]%=mod;
ans=(ans+inv[i]%mod*s[i])%mod;
ans%=mod;
// std::cout<<inv[i]<<std::endl;
// std::cout<<ans<<std::endl;
}
printf("%lld",ans);
return 0;
}
进行了离散化的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <cstdlib>
#define inf 0x3f
#define lowbit(x) x&(-x)
#define int long long
const int maxn=1e6;
const int mod=998244353;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){ if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n;
int num[maxn],s[maxn],tree[maxn],inv[maxn];
int MAX;
void add(int x,int k)
{
for(int i=x;i<=MAX;i+=lowbit(i))
{
tree[i]++;
}
}
int find(int x)
{
int sum=0;
for(int i=x;i>=1;i-=lowbit(i))
{
sum+=tree[i];
}
return sum;
}
int b[maxn];//离散化用的数组
signed main()
{
n=read();
for(int i=1;i<=n;i++)
{
num[i]=read();
b[i]=num[i];
MAX=std::max(MAX,num[i]);
}
std::sort(b+1,b+n+1);//从小到大排序
int len = std::unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)
{
num[i]=std::lower_bound(b+1,b+len+1,num[i])-b;
MAX=std::lower_bound(b+1,b+len+1,MAX)-b;
}
for (int i = 1; i <= n; i++)
{
s[i]=find(num[i]-1);//小于等于的为 find(num[i]),
//std::cout<<s[i]<<"TEXT"<<std::endl;
add(num[i],1);
}
int ans=0;
inv[1]=1;
/*for(int i=1;i<=n;i++)
{
// -k * r_-1
inv[i]=(-p/i)*inv[p%i];
} */
for(int i=2;i<=n;i++)
{
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
for(int i=1;i<=n;i++)
{
s[i]+=s[i-1];
s[i]%=mod;
ans=(ans+inv[i]%mod*s[i])%mod;
ans%=mod;
// std::cout<<inv[i]<<std::endl;
// std::cout<<ans<<std::endl;
}
printf("%lld",ans);
return 0;
}
T3科学世纪
问题描述：
t 组数据，每次给定整数 p,q，求一个最大的整数 x，满足 p 可以被 x
整除，并且 q 不能整除 x。
输入：
第 1 行一个整数 t，代表数据组数。
第 2 ∼ t + 1 行，每行两个整数 p,q，代表给定的两个参数。
输出：
共 t 行，每一行代表对应的 x 的值。
样例：
输入：
3
10 4
12 6
179 822
输出：
10
4
179
思路分析：
显然，如果 \(p<q\),那么\(p|x\)的时候，\(p\not|x\),很显然，\(p\)就符合输出的条件，那么我们这个时候输出p 就好了，同时，\(p\) % \(q\) !=0的时候，也就输出\(p\)就好了,
那现在就是考虑其他情况的时候，我们考虑一下，\(p\)和\(q\)的质因子，但是\(p\)中有比\(q\)质因子大的，但它对答案并不产生贡献，我们做的是枚举删除某个质因子，然后寻求最大值（为什么要删去一个，删去多个就会使得\(x\)下降，导致不是最优解）
所以解法就是 :枚举 \(q\)的每一个质因子，然后令\(p\)去除以它，直到\(p\)中的质因子的数要小于\(q\)中质因子数，然后比较出最大值来，然后就是答案；
总复杂度 O（\(t\sqrt{q}\)）
先对 \(p,q\) 质因数分解，设 \(\{a_i\}\) 为质数集，\(\{b_i\}\) 为对应质数的次数：
$$p=\prod a_{i}^{b1_i}$$
$$q=\prod a_{i}^{b2_i}$$
有 \((x|p) \land (q\nmid {x})\)，则 \(x\) 质因数分解后有：
$$x=\prod a_{i}^{b3_i}$$
$$p=k\times x =k\times \prod a_{i}^{b3_i}(k\in \mathbf{N}^*)$$
$$∃a_j|q,\ b3_j < b2_j$$
第二个条件表示 \(x|p\)，第三个条件表示存在一个整除 \(q\) 的质数 \(a_j\)，它在 \(x\) 中的次数比在 \(q\) 中的次数要小，从而使 \(q\nmid x\)。
显然，最优的 \(x\) 一定是 \(p\) 抠去一些质因子 \(a_j\)，使得该质因子在 \(p\) 中的次数小于 \(q\) 中的次数后剩下的值。
显然抠去的质因子最多有一个。
所以可以枚举 \(q\) 的所有质因子并进行计算。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define int long long
#define INF (1e13 + 7)
#define MANX MAXN
#define MAXN 2000000
using namespace std;
inline int read()
{
int x = 0, f = 1; char c = getchar();
while (c > '9' || c < '0') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') {x = x * 10 + (c ^ 48); c = getchar();}
return f * x;
}
int a[MAXN], b[MAXN], numa, numb;
signed main()
{
int t = read();
while (t--)
{
int p = read(), q = read();
if (q > p || p % q != 0) {cout << p; puts(""); continue;}//---
int x = p, y = q, ans = 1;//---
for (int i = 2; i <= sqrt(y); i++)
{
if (y % i == 0)
{
numa = 0, numb = 0;
while (x % i == 0) x /= i, numa++;
while (y % i == 0) y /= i, numb++;
int num = numa - numb + 1, k = p;//p的质数的数量减去q质数的数量
for (int j = num; j; j--) k /= i;
ans = max(ans, k);
}
}
if (y != 1)
{
numa = 0, numb = 0;
while (x % y == 0) x /= y, numa++;
numb++;
int num = numa - numb + 1, k = p;
for (int i = num; i; i--) k /= y;
ans = max(ans, k);
}
cout << ans;
puts("");
}
return 0;
}
版权声明：本文为abc123efg456-a1b2原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。