A.Got Any Grapes?
题目大意：
给出三种葡萄的数目\(x,y,z\)，给出三个人要吃的数目\(a,b,c\)，已知第一人只吃第一种葡萄，第二人只吃前两种葡萄，第三人三种葡萄都吃，问是否可以满足他们的要求。\((1\leqslant x,y,z,a,b,c\leqslant 10^{5})\)
解题思路：
直接模拟即可。从要求多的开始处理，最后剩下的给要求少的；这样若一个人存在无法满足要求的情况，那么一定无解。
小代码
#incIude <bits/stdc++.h>
#define int long long
using namespace std;
int x,y,z,a,b,c;
signed main()
{
scanf("%lld%lld%lld",&x,&y,&z);
scanf("%lld%lld%lld",&a,&b,&c);
a-=x;
if (a<0) { printf("NO"); return 0; }
b-=y-a;
if (b<0) { printf("NO"); return 0; }
c-=z-b;
if (c<0) { printf("NO"); return 0; }
printf("YES");
return 0;
}
B.Yet Another Array Partitioning Task
题目大意：
我们定义一个序列的“美丽度”为序列前\(m\)大的数的和。给出长度为\(n\)的一个序列\(a_{i}\)，要求将序列\(a\)分为\(k\)个连续子序列，使得每个连续子序列长度至少为\(m\)，每个元素不重不漏，且所有子段“美丽度”的和最大。输出最大的“美丽度”之和与划分方案。\((1\leqslant n\leqslant 2\times 10^{5},m\geqslant 1,k\geqslant 2,m\times k\leqslant n,-10^{9}\leqslant a_{i}\leqslant 10^{9})\)
解题思路：
因为“原序列中前\(m\times k\)大的数”字太多了，所以下面用“天选之数”代替
显然，最大的美丽度之和就是"原序列中前\(m\times k\)大的数"之和。先求出最大美丽度和并统计哪些数是天选之数；划分子段时，记录目前子段有多少个天选之数，若当前子段已经有\(m\)个了，那么在当前位置划分一下即可。
挂分小技巧 但是，要注意除了要记录哪些数是天选之数，还要记录每个天选之数的个数；否则会出现以下情况：对于所有\(a_{i}=x\)，部分\(a_{i}\)属于天选之数，部分\(a_{i}\)不属于天选之数，因为没记录天选之数的个数，所以对于部分不属于天选之数的\(a_{i}\)也用于划分子段了——但它其实并不能用。
再次注意到\(a_{i}\)的范围，再次用map搞桶数组。
坏代码
#incIude <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,k;
struct node{
int x,d;
}a[N];
map <int,int> mp;
int l,sum;
int cnt=1,s[N];
bool cmp1(node x,node y) { return x.x>y.x; }
bool cmp2(node x,node y) { return x.d<y.d; }
signed main()
{
scanf("%lld%lld%lld",&n,&m,&k);
for (int i=1;i<=n;i++)
{
scanf("%lld",&a[i].x);
a[i].d=i;
}
sort(a+1,a+1+n,cmp1);
for (int i=1;i<=m*k;i++)
{
sum+=a[i].x;
mp[a[i].x]++;
}
sort(a+1,a+1+n,cmp2);
int ct=0;
for (int i=1;i<=n;i++)
{
if (mp[a[i].x]) { ct++; mp[a[i].x]--; }
if (ct>=m) { ct=0; s[++cnt]=i; }
}
printf("%lld\n",sum);
for (int i=2;i<=k;i++) printf("%lld ",s[i]);
return 0;
}
C.Trailing Loves
题目大意：
给出\(n\)，求 \(n!\) 在\(b\)进制下末尾\(0\)的个数。\((1\leqslant n\leqslant 10^{18},2\leqslant b\leqslant 10^{12})\)
解题思路：
作为一个数论知识储备基本为0的蒟蒻 一道数论黄题足以让我欲哭无泪
什么？另一道题面相同的题是蓝题？
联想到短除法的过程，能够想到对于一个数\(n\)，其在\(b\)进制下末尾0的个数\(p\)就是它能整除\(b\)的个数，即$$n=k^{\ p}\times w$$于是分别给\(n!,b\)分解分解质因子，形如$$b={p_{1}}^{a1} {p_{2}}^{a2}… {p_{3}}^{a3}, n!={p_{1}}^{e1} {p_{2}}^{e2}… {p_{3}}^{e3}$$那么最后的答案就是\(min\{\lfloor\frac{e_{i}}{a_{i}}\rfloor\}\)
但是考虑到给\(n!\)分解质因子不现实，发现只需要给\(b\)分解即可；因为\(n!=1\times 2\times…\times n\)，所以每\(p\)个数中就有一个数的质因子含\(p\)，于是乎\(e_{i}=\sum_{i=1}^{r}\lfloor \frac{n}{p^{i}} \rfloor,p^{r}\leqslant n< p^{r+1}\)
难绷的代码
#incIude <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,b;
struct node{
int x,num;
}p[N];
int cnt;
int ans=inf;
signed main()
{
scanf("%lld%lld",&n,&b);
for (int i=2;i*i<=b;i++)//b的质因子
{
if (b%i==0)
{
p[++cnt].x=i;
while (b%i==0) { p[cnt].num++; b/=i; }
}
}
if (b>1) p[++cnt]={b,1};
for (int i=1;i<=cnt;i++)
{
int r=1,e=0;
while (n/r>=p[i].x)
{
r*=p[i].x;
e+=n/r;
}
ans=min(ans,e/p[i].num);
}
printf("%lld",ans);
return 0;
}
D.Food Fill
题目大意：
给出长度为\(n\)的序列\(c_{i}\)，定义区间\([l,r]\)合法当且仅当\(c_{l}=c_{l+1}=…=c_{r}\)。每次操作可以选择一个\(c_{i}\)并将\(c_{i}\)所在的合法区间修改为其他数，求使得\([1,n]\)为合法区间的最少操作次数。\((1\leqslant n,c_{i}\leqslant5000)\)
解题思路：
一眼区间\(dp\)。
设状态\(f_{i,j}\)表示使区间\([i,j]\)合法的最小代价。状态转移方程如
\[f_{i,j}=\begin{cases} f_{i+1,j-1}+1,c_{i}=c_{j}\\ min(f_{i+1,j},f_{i,j-1})+1,c_{i}\neq c_{j} \end{cases}\]和木板涂色简直一样一样的
修代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5010;
int n;
int cnt,c[N];
int f[N][N];
signed main()
{
scanf("%lld",&n);
for (int i=1,x,pre=0;i<=n;i++)
{
scanf("%lld",&x);
if (x!=pre) c[++cnt]=x;
pre=x;
}
for (int len=2;len<=cnt;len++)
{
for (int i=1;i+len-1<=cnt;i++)
{
int j=i+len-1;
if (c[i]==c[j]) f[i][j]=f[i+1][j-1]+1;
else f[i][j]=min(f[i+1][j],f[i][j-1])+1;
}
}
printf("%lld",f[1][cnt]);
return 0;
}
E.Arithmetic Progession
题目大意：
已知有一个长度为\(n\)的序列\(a_{i}\)，保证它升序排序后是个等差数列。每次有两种询问：
- "? i" 询问\(a_{i}\)的值
- "> x" 询问序列中是否存在严格大于\(x\)的数
可以问不超过60个询问。
要求输出等差数列的首项与公差。\((2\leqslant n\leqslant 10^{6},0\leqslant a_{i}\leqslant 10^{9})\)
解题思路：
不会
F.Please,another Qeuries on Array?
题目大意：
给出长度为\(n\)的序列\(a\)，现在要完成\(q\)次操作，有以下两种操作形式：
- "MULTIPLY , l , r , x"，对于\(i\in[l,r]\)，使得\(a_{i}=a_{i}\times x\)
- "TOTIENT , l , r"，输出 \(\varphi(\prod_{i=l}^{r}{a_{i}})\mod10^{9}+7\)
\((1\leqslant n\leqslant 4\times 10^{5},1\leqslant q\leqslant 2\times 10^{5},1\leqslant a_{i},x\leqslant 300)\)
解题思路：
区修区查，一眼线段树。问题在于怎样维护\(\varphi\)值。
首先，欧拉函数的计算方式为$$\varphi(n)=n\times \prod_{i=1}^{k}{\frac{p_{i}-1}{p_{i}}} $$其中\(p_{i}\)是\(n\)的质因子，\(k\)是\(n\)的质因子的个数。
所以，要求欧拉函数，就需要维护\(a_{i}\)的质因子。注意到\(a_{i}\)与\(x\)的范围不超过300，而300以内的质数有62个，所以容易想到状态压缩维护。
然后没了？
求大佬帮看代码 本地能跑但评测机上TLE
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=2e5+5;
const int MOD=1e9+7;
int n,q,a[N];
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293};
struct node{
int l,r;//左右子树编号
int sum;//区间乘
int tag1,tag2;//懒惰标记
int p;//质因子状压
}tr[N*4];
int inv[100],f[100];
int qsm(int x,int y)
{
int res=1;
while (y)
{
if (y&1){
res=(res*x)%MOD;
}
y>>=1,x=(x*x)%MOD;
}
return res;
}
void push_up(int id)
{
tr[id].sum=(tr[id<<1].sum*tr[(id<<1)+1].sum)%MOD;
tr[id].p=tr[id<<1].p|tr[(id<<1)+1].p;
}
void push_down(int id)
{
int l=id<<1,r=(id<<1)+1;
if (tr[id].tag1>1)
{
tr[l].sum=(tr[l].sum*qsm(tr[id].tag1,tr[l].r-tr[l].l+1))%MOD;
tr[r].sum=(tr[r].sum*qsm(tr[id].tag1,tr[r].r-tr[r].l+1))%MOD;
tr[l].tag1*=tr[id].tag1,tr[l].tag1%=MOD;
tr[r].tag1*=tr[id].tag1,tr[r].tag1%=MOD;
}
if (tr[id].tag2)
{
tr[l].p|=tr[id].tag2,tr[l].tag2|=tr[id].tag2;
tr[r].p|=tr[id].tag2,tr[r].tag2|=tr[id].tag2;
}
tr[id].tag1=1,tr[id].tag2=0;
}
void build(int id,int l,int r)
{
tr[id].l=l,tr[id].r=r,tr[id].tag1=1;
if (l==r)
{
tr[id].sum=a[l];
for (int i=0;i<62;i++) if (a[l]%prime[i]==0) tr[id].p|=(1ll<<i);
return ;
}
int mid=(l+r)>>1;
build(id<<1,l,mid);
build((id<<1)+1,mid+1,r);
push_up(id);
}
void _update(int id,int l,int r,int x,int _p)
{
if (l<=tr[id].l&&tr[id].r<=r)
{
tr[id].sum=(tr[id].sum*qsm(x,tr[id].r-tr[id].l+1))%MOD;
tr[id].tag1*=x,tr[id].tag1%=MOD;
tr[id].tag2|=_p,tr[id].p|=_p;
return ;
}
push_down(id);
int mid=(tr[id].l+tr[id].r)>>1;
if (mid>=r) _update(id<<1,l,r,x,_p);
if (mid<l) _update((id<<1)+1,l,r,x,_p);
push_up(id);
}
pii _query(int id,int l,int r)
{
if (l<=tr[id].l&&tr[id].r<=r) return mp(tr[id].sum,tr[id].p);
pii res=mp(1,0);
push_down(id);
int mid=(tr[id].l+tr[id].r)>>1;
if (mid>=r)
{
pii a=_query(id<<1,l,r);
res.first=(res.first*a.first)%MOD;
res.second|=a.second;
}
if (mid<l)
{
pii b=_query((id<<1)+1,l,r);
res.first=(res.first*b.first)%MOD;
res.second|=b.second;
}
return res;
}
signed main()
{
scanf("%lld%lld",&n,&q);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);
inv[1]=1;
for (int i=2;i<=300;i++) inv[i]=MOD-(MOD/i)*inv[MOD%i]%MOD;
for (int i=0;i<62;i++) f[i]=inv[prime[i]]*(prime[i]-1)%MOD;
char op[10];
int l,r,x;
while (q--)
{
scanf("%s",op);
if (op[0]=='M')//区间乘
{
scanf("%lld%lld%lld",&l,&r,&x);
int p=0;
for (int i=0;i<62;i++) if (x%prime[i]==0) p|=(1ll<<i);
_update(1,l,r,x,p);
}
else
{
scanf("%lld%lld",&l,&r);
pii ret=_query(1,l,r);//返回的乘积与质因子状态
int res=ret.first,phi=ret.second;//乘积，状态
for (int i=0;i<62;i++) if (phi&(1ll<<i)) res=(res*f[i])%MOD;
printf("%lld\n",res%MOD);
}
}
return 0;
}