2021-06-05-6月5日题解
6月5日题解¶
交换¶
题目链接¶
http://icpc.upc.edu.cn/problem.php?cid=2828&pid=9
题目描述¶
给出一个序列A，其中第i个数字为ai，你每次可以选择一个数字不变，将其他数字全部乘以x。其中x为任意素数。 无需考虑这些数字在变换过程中是否超过long long的存储范围。请回答：最少经过多少次操作，可以使得序列中所有数字全部相同。
输入¶
第一行包含一个正整数n，代表序列长度。 接下来一行包含n个正整数，描述序列中的每一个元素。
输出¶
输出一行一个正整数表示答案。
样例输入¶
样例输出¶
提示¶
样例说明： 可以选中第二个数字不变，将第一个数字除以5，然后选中第一个数字不变，将第二个数字除以7。两次操作后，数组中所有数字均变为1。当然还有其他方法，如将两个数字最终都变为35也只需要2次操作。 【数据范围】 对于20%的数据，满足n=2,ai≤106 对于40%的数据，满足n≤10,ai≤106 对于另外20%的数据，满足n≤4∗104,ai≤20 对于100%的数据，满足1≤n≤106,1≤ai≤106
题解¶
对其他数进行做乘法相当于对自己做乘法，可以对每一个数除掉最大公约数互质后，统计和计算质因数的个数即可。
代码¶
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1005000]={0};
ll gcd(ll a,ll b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
ll prime[1005000]={0};
ll is_prime[1005000]={0};
int main()
{
ll cnt=0;
for(ll i=2;i<=1e6;i++)
{
if(!is_prime[i])
prime[++cnt]=i;
for(ll j=1;j<=cnt;j++)
{
if(i*prime[j]>1e6)
break;
is_prime[i*prime[j]]=1;
if(i%prime[j]==0)
break;
}
}
ll n,m=0;
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
m=gcd(a[i],m);
}
ll ans=0;
for(ll i=1;i<=n;i++)
{
a[i]/=m;
for(ll j=1;j<=cnt&&prime[j]*prime[j]<=a[i];j++)
{
while(a[i]%prime[j]==0)
{
ans++;
a[i]/=prime[j];
}
}
if(a[i]!=1)
ans++;
}
printf("%lld\n",ans);
}
Disjoint Set of Common Divisors¶
题目链接¶
http://icpc.upc.edu.cn/problem.php?cid=2826&pid=4
题目描述¶
Given are positive integers A and B. Let us choose some number of positive common divisors of A and B. Here, any two of the chosen divisors must be coprime. At most, how many divisors can we choose? →Definition of common divisor ·An integer d is said to be a common divisor of integers x and y when d divides both x and y. →Definition of being coprime ·Integers x and y are said to be coprime when x and y have no positive common divisors other than 1. →Definition of dividing ·An integer x is said to divide another integer y when there exists an integer α such that y=αx.
Constraints ·All values in input are integers. ·1≤A,B≤1012
输入¶
Input is given from Standard Input in the following format:
A B
输出¶
Print the maximum number of divisors that can be chosen to satisfy the condition.
样例输入¶
样例输出¶
提示¶
样例1解释 12 and 18 have the following positive common divisors: 1, 2, 3, and 6. 1 and 2 are coprime, 2 and 3 are coprime, and 3 and 1 are coprime, so we can choose 1, 2, and 3, which achieve the maximum result. 样例3解释 1 and 2019 have no positive common divisors other than 1.
题解¶
求gcd(A,B)的质因数有多少个即可。
代码¶
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n,m;
cin>>n>>m;
ll k=__gcd(n,m);
ll ans=1;
for(ll i=2; i*i<=k; i++)
{
if(k%i==0)
ans++;
while(k%i==0)
k/=i;
}
if(k!=1)
ans++;
cout<<ans<<endl;
return 0;
}
牛牛的滑动窗口¶
题目链接¶
http://icpc.upc.edu.cn/problem.php?cid=2826&pid=9
题目描述¶
牛牛最近学习了滑动窗口类的算法，滑动窗口算法可以解决一些线性数组的离线静态区间查询类问题。
具体来说，假设对于一个数组进行m次静态区间查询问题。如果这些查询满足条件：∀i,j当li≤lj时，总有ri≤rj。（i,j表示查询的编号，l,r表示查询的左右端点）
接下来只要查询的问题满足可以快速插入和删除单点，就可以使用滑动窗口优化，将这m次查询的复杂度降低到O(n)。
显然，如果对于一个数组的区间查询问题，查询的区间长度给定为k时，总是满足∀i,j当li ≤ lj时，总有ri≤rj这一条件的。
牛牛接下来想要问你的问题也和定长滑动窗口有关。
众所周知，长度为k的滑动窗口从左到右去截取一个长度大小为n的数组时，一共可以截取到n-k+1个子数组。
牛牛将这n-k+1个子数组的极大值与极小值的乘积求和称为该数组的"第k窗口值"。
举个例子，假设长度为5的数组为[1,5,2,4,3]，长度为3的滑动窗口可以截取三个子数组，它们分别为[1,5,2],[5,2,4],[2,4,3]。
所以该数组的“第3窗口值”为1*5+2*5+2*4=23。
对于一个给定大小的数组n，牛牛现在想要知道它的第1,2,3,4,5...n窗口值各是多少，请你编写程序解决他的问题。
输入¶
第一行输入一个正整数n，表示数组的大小。 接下来一行输入n个正整数ai，表示数组的内容
输出¶
输出一行n个正整数，表示滑动窗口的长度分别为1,2,3,4,5...n时，问题的答案。 输出的整数之间用空格隔开，行末不允许有多余空格。
样例输入¶
样例输出¶
提示¶
样例解释： 第1窗口值=1*1+5*5+2*2+4*4+3*3=55 第2窗口值=5*1+5*2+4*2+4*3=35 第3窗口值=5*1+5*2+4*2=23 第4窗口值=5*1+5*2=15 第5窗口值=5*1=5
对于10%的测试数据，保证1≤n≤10 对于20%的测试数据，保证1≤n≤100 对于30%的测试数据，保证1≤n≤1000 对于50%的测试数据，保证1≤n≤6000 对于另外10%的测试数据，保证1≤ai≤10 对于100%的测试数据，保证1≤n≤105,1≤ai≤100
题解¶
暂未想出，思路为单调栈，待补！！！
https://blog.csdn.net/weixin_43346722/article/details/109151074
代码¶
#include<cstdio>
#include<iostream>
using namespace std;
struct node {
int x, num;
}bigstack[101], smallstack[101];
int n, a[100001], ans[100001], bigtop, smalltop, maxn, minn;
int lft, bignow, smallnow;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) {
while (bigtop && bigstack[bigtop].x <= a[i]) bigtop--;
while (smalltop && smallstack[smalltop].x >= a[i]) smalltop--;//栈的弹出
bigstack[++bigtop] = (node){a[i], i};//插入
smallstack[++smalltop] = (node){a[i], i};
maxn = minn = a[i];
lft = i;
bignow = bigtop - 1;
smallnow = smalltop - 1;
while (bignow || smallnow) {//一点一点往后移，算贡献
if (bignow && smallnow) {
if (bigstack[bignow].num >= smallstack[smallnow].num) {
ans[i - lft + 1] += maxn * minn;
ans[i - bigstack[bignow].num + 1] -= maxn * minn;
lft = bigstack[bignow].num;
maxn = bigstack[bignow].x;
bignow--;
}
else {
ans[i - lft + 1] += maxn * minn;
ans[i - smallstack[smallnow].num + 1] -= maxn * minn;
lft = smallstack[smallnow].num;
minn = smallstack[smallnow].x;
smallnow--;
}
continue;
}
if (bignow) {
ans[i - lft + 1] += maxn * minn;
ans[i - bigstack[bignow].num + 1] -= maxn * minn;
lft = bigstack[bignow].num;
maxn = bigstack[bignow].x;
bignow--;
}
else {
ans[i - lft + 1] += maxn * minn;
ans[i - smallstack[smallnow].num + 1] -= maxn * minn;
lft = smallstack[smallnow].num;
minn = smallstack[smallnow].x;
smallnow--;
}
}
ans[i - lft + 1] += maxn * minn;
ans[i + 1] -= maxn * minn;
}
for (int i = 1; i <= n; i++) {
ans[i] += ans[i - 1];//因为是差分，所以要加上前面的
printf("%d ", ans[i]);
}
return 0;
}
等差序列前缀和（双前缀和）¶
听说罗翔老师最近很火。 张三今天迫不及待想犯罪。就决定是爆炸罪了，正好罗老师讲了这个案例。 他一眼就看上了 CaPeF_Yyx 的家 （或许是他太 duliu 了） 。 作为张三，她蛮不讲理，所以他的爆炸会波及部分街道。每次爆炸会造成一定的损坏。 作为张三，她出人意料，所以他的爆炸波及的范围每次都不一样。 作为张三，她十恶不赦，所以他的爆炸会进行m 次 （CaPeF_Yyx 的家也太坚固了吧） 作为张三，她井井有条，所以他的爆炸波及的范围是一个闭区间。 作为张三，她精益求精，所以他的爆炸以等差数列的方式造成伤害。 CaPeF_Yyx 家在偏远角落，街道编号从1~n 。 CaPeF_Yyx 街道刚翻新，每间房屋破坏程度都为0。 罗翔老师可以预测每次爆炸的范围。会给到 CaPeF_Yyx 形如[l,r] 的闭区间。 罗翔老师可以预测每次爆炸的伤害。会给到 CaPeF_Yyx 形如l,r,bg,ed 的 4 个数。 表示形如{ql,ql+1,...,qr-1,qr},ql=bg,qr=ed的等差数列，对于街道ai(l≤i≤r)，造成qi的伤害。 CaPeF_Yyx 找到了 Rainy7 修复街道。可是她必须先知道街道到底损坏了多少。 她还忙着拯救世界呢，CaPeF_Yyx 被吓得不轻，于是只能让你帮助她了。 出题人不想太 duliu ，她让你只要输出所有房屋损害程度的最大值和异或和。 Q：话说为什么不直接用魔法阻止张三？ A：因为 唯我法外狂徒张三永世长存 !!!
输入¶
第一行，两个整数n,m表示房屋的数量，和爆炸次数。
接下来m行，每行四个整数l,r,bg,ed，分别表示等差数列的首项标号，末项标号，首项值，末项值。
输出¶
一行，两个数，分别表示所有房屋损害程度的最大值和异或和。
样例输入¶
样例输出¶
提示¶
样例1解释:
第一次爆炸产生的伤害：[2,4,6,8,10]。
第二次爆炸产生的伤害：[0,1,1,1,0]。
所有爆炸结束后每个房屋的损伤程度：[2,5,7,9,10]。
输出异或和：
。
输出最大值：
。
代码¶
#include <bits/stdc++.h>
using namespace std;
const long long int N = 1e7 + 500;
long long int out[N] = {0};
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
register long long int n, m, l, r, ks, e1, dc, tmp = 0;
register long long int max1 = 0, ans = 0;
cin >> n >> m;
register long long int i;
for (i = 1; i <= m; i++)
{
cin >> l >> r >> ks >> e1;
dc = (e1 - ks) / (r - l);
out[l] = out[l] + ks;
out[l + 1] = out[l + 1] + dc - ks;
out[r + 1] = out[r + 1] - dc - e1;
out[r + 2] = out[r + 2] + e1;
}
for (i = 1; i <= n; i++)
{
out[i] = out[i - 1] + out[i];
tmp += out[i];
max1 = max(max1, tmp);
ans = ans ^ tmp;
}
cout << ans << ' ' << max1 << endl;
return 0;
}