7.【2024初三年前集训测试2】
2024初三年前集训测试2
\(T1\) 上海
\(0pts\)
死因
- \(__int128\) 不支持 \(pow\) 。
- 事实上我打了一个快速幂
（在一千行代码里翻出来就行）。但是我打 \(qpow\) 时忘打 \(q\) 了，然后本地运行还没报错……就交上去了 - 之后结果就是，没过编。。。
- 改成
龙龙就对了。
题解
- 还是比较好打的，给一个正整数 \(k(1\leq k\leq 10^{12})\) ，判断是否有一个正整数 \(n\) 使得 \(n^2\) 为 \(k\) 的倍数且 \(n\) 不是 \(k\) 的倍数。
- 想到对其进行分解质因数，一个数的平方质因子次数都是偶数，也就是说，假如 \(k\) 的质因子次数都为 \(1\) 那么就是无解的。
- 而有解情况就是 \(k\) 有次数大于 \(1\) 的质因子 （不是 \(square~free~number\) ）。解就是 \(\LARGE\sum\limits_{i=1}^np_i^{\large\lceil\dfrac{c_i}{2}\rceil}\) 。
- 因此记录质因子以及次数，之后处理一下即可。
代码
说的再多也不如代码好使。
#include<bits/stdc++.h>
#define int __int128//long long就够了
#define N (1000010)
#define sort stable_sort
using namespace std;
namespace IO
{
#define ll __int128
const int MAX=1<<24;
char buf[MAX],*p1=buf,*p2=buf;
char obuf[MAX],*o=obuf;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<24,stdin),p1==p2)?EOF:*p1++)
//template<typename T>
//inline T read()
inline int read()
{
int x=0;bool f=1;
char c=gc();
for(;c<48||c>57;c=gc())if(c=='-')f=0;
for(;c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c^48);
return f?x:~x+1;
}
void print(ll x){if(x>9)print(x/10);*o++=(x%10)+'0';}
void pit(ll x){if(x<0)*o++='-',x=~x+1;print(x);}
void write(ll x,char end){pit(x);*o++=end;}
void flush(){fwrite(obuf,o-obuf,1,stdout);}
#undef ll
}
using IO::read;using IO::write;using IO::flush;using std::complex;
inline int min(int x,int y){return y&((y-x)>>31)|x&(~(y-x)>>31);}
inline int max(int x,int y){return x&((y-x)>>31)|y&(~(y-x)>>31);}
inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}
long long n,m;
int qpow(int x,int b)
{
int ans=1;
for(;b;b>>=1){if(b&1)ans=(ans*x);x=(x*x);}
return ans;
}
int pr[100],cnt[100],tot,ans=1;
signed main()
{
init_set();
n=read();
int len(sqrt(n)),nn(n);
for(int i(2);i<=len;++i)
{
if(!(nn%i))pr[++tot]=i,++cnt[tot],nn/=i;
for(;!(nn%i);nn/=i)++cnt[tot];
}
if(nn>1)pr[++tot]=nn,++cnt[tot];
for(int i(1);i<=tot;++i)
{
if(cnt[i]!=1)break;
if(i==tot)puts("-1"),exit(0);
}
for(int i(1);i<=tot;++i)
ans*=pow(pr[i],((cnt[i]+1)>>1));
write(ans,' ');
flush();
return 0;
}
\(T2\) 华二
\(0pts\)
话说为啥这次模拟赛题目名字这么瞩目。
题解
- 一个 \(1\leq a_i\leq 9\) 的数列，当 \(\gcd(a_i,a_{i+1})=1\) 时，就可以把它们的位置交换。
- 显然，对于（ \(1\) ， \(5\) ， \(7\) ）这三个法外狂徒来说，它们可以随意地变换位置。
- 对于 \((2,3)\) \((2,7)\) \((2,9)\) \((3,4)\) \((4,9)\) \((8,9)\) 六对数来说，也是可以交换的。
- 并且我们发现，可以将 \(6\) 单独分出来，因为它不能与其他数交换（ \(1\) ， \(5\) ， \(7\) ）除外，所以可以用 \(6\) 作为一个分隔符。而（ \(2\) ， \(4\) ， \(8\) ），（ \(3\) ， \(9\) ）不能与自己组内的数交换，所以基本框架就有了。
- 对于（ \(1\) ， \(5\) ， \(7\) ）可以在最后再处理，先去处理其他数。
- 将一样的数字看成一类，扫描数组，记录每个数字出现的次数，当我们在数组里扫到 \(6\) 或扫到最后一个数时，对每个组的数字出现的次数进行计算，之后将两个出现次数求一下组合数。 \(\large\dbinom{n}{m}=\dbinom{n}{n-m}\) 。然后乘起来就可以了。
- 之后将（ \(1\) ， \(5\) ， \(7\) ）进行处理，将它们插入到数组中，那就是 \(\dbinom{n}{x}+\dbinom{n-x}{y}+\dbinom{n-x-y}{z}\) （ \(x\) ， \(y\) ， \(z\) ）是出现次数，\(n\) 是总数，接着乘起来就行了。
代码
#include<bits/stdc++.h>
#define int long long
#define N (1000010)
#define sort stable_sort
using namespace std;
namespace IO
{
#define ll long long
const int MAX=1<<24;
char buf[MAX],*p1=buf,*p2=buf;
char obuf[MAX],*o=obuf;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<24,stdin),p1==p2)?EOF:*p1++)
//template<typename T>
//inline T read()
inline int read()
{
int x=0;bool f=1;
char c=gc();
for(;c<48||c>57;c=gc())if(c=='-')f=0;
for(;c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c^48);
return f?x:~x+1;
}
void print(ll x){if(x>9)print(x/10);*o++=(x%10)+'0';}
void pit(ll x){if(x<0)*o++='-',x=~x+1;print(x);}
void write(ll x,char end){pit(x);*o++=end;}
void flush(){fwrite(obuf,o-obuf,1,stdout);}
#undef ll
}
using IO::read;using IO::write;using IO::flush;using std::complex;
inline int min(int x,int y){return y&((y-x)>>31)|x&(~(y-x)>>31);}
inline int max(int x,int y){return x&((y-x)>>31)|y&(~(y-x)>>31);}
inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}
long long n,m;
void init_set()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
#ifdef ONLINE_JUDGE
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
}
int qpow(int x,int b)
{
int ans=1;
for(;b;b>>=1){if(b&1)ans=(ans*x);x=(x*x);}
return ans;
}
int x,y;
int P(998244353),a[100010],jc[100010],ans=1,tot;
int op[20];
int exgcd(int a,int b,int &x,int &y)
{
if(!b){x=1,y=0;return a;}
int d=exgcd(b,a%b,y,x);
y-=(a/b*x);
return d;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int inv_it(int a,int P=P){int d(exgcd(a,P,x,y));return(x%P+P)%P;}
int jc_C(int n,int m,int P=P){return((jc[n]*inv_it(jc[m]))%P*inv_it(jc[n-m]))%P;}
signed main()
{
init_set();
n=read();
jc[0]=jc[1]=1;
for(int i(1);i<=n+1;++i)jc[i]=(jc[i-1]*i)%P;
for(int i(1);i<=n;++i)a[i]=read();
int r(1),x(0),y(0);
for(;r<=n;++r)
{
++op[a[r]];
if(a[r]==6||r==n)
x=op[2]+op[4]+op[8],
y=op[3]+op[9],
ans=(ans*jc_C(x+y,x))%P,
op[2]=op[3]=op[4]=op[8]=op[9]=0;
}
x=n-op[5]-op[7];
ans=(ans*jc_C(x,op[1]))%P;
x+=op[5];
ans=(ans*jc_C(x,op[5]))%P;
x+=op[7];
ans=(ans*jc_C(x,op[7]))%P;
write(ans,' ');
flush();
return 0;
}
\(T3\) 高爸
\(40pts\) （唯一得上的分）
（恼！）
- 场上打了个暴力，本来是枚举力量值，改成了三分，（其实是错的）。然后得了 \(40\) 。
- 之后下午开始改题，从 \(5\) 点左右开始改 \(T3\) 改到 \(9\) 点半发现三分错了，没绷住。。。
题解
- 平衡树，线段树，树状数组都可以，这里选择又快码量又少的树状数组。
- 首先这个不是普通树状数组，而是权值树状数组。权值树状数组就是存数组下标的数组，数组存储下标对应的值有几个数。
- 需要进行排序，去重也就是离散化。
- 之后将值存入树状数组，对每个值进行三分，由于树状数组 \(O(\log n)\) ，三分 \(O(\log_3(n))\) ， \(n\) 次询问，所以最后是 \(O(n\log^2n)\) 。
代码
#include<bits/stdc++.h>
#define int long long
#define N (1000010)
#define sort stable_sort
using namespace std;
namespace IO
{
#define ll unsigned long long
const int MAX=1<<24;
char buf[MAX],*p1=buf,*p2=buf;
char obuf[MAX],*o=obuf;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<24,stdin),p1==p2)?EOF:*p1++)
//template<typename T>
//inline T read()
inline int read()
{
int x=0;bool f=1;
char c=gc();
for(;c<48||c>57;c=gc())if(c=='-')f=0;
for(;c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c^48);
return f?x:~x+1;
}
void print(ll x){if(x>9)print(x/10);*o++=(x%10)+'0';}
void pit(ll x){if(x<0)*o++='-',x=~x+1;print(x);}
void write(ll x,char end){pit(x);*o++=end;}
void flush(){fwrite(obuf,o-obuf,1,stdout);}
#undef ll
}
using IO::read;using IO::write;using IO::flush;using std::complex;
inline signed min(signed x,signed y){return y&((y-x)>>31)|x&(~(y-x)>>31);}
inline long long min(long long x,long long y){return y&((y-x)>>63)|x&(~(y-x)>>63);}
inline signed max(signed x,signed y){return x&((y-x)>>31)|y&(~(y-x)>>31);}
inline long long max(long long x,long long y){return x&((y-x)>>63)|y&(~(y-x)>>63);}
inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}
long long n,m;
void init_set()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
#ifdef ONLINE_JUDGE
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
}
int a[100010],tot;
int cf[100010];
int hi,lo,op[100010],hit[100010];
struct aa{int num,sum;}c[100010];
inline signed lowbit(signed x){return x&(~x+1);}
void update(signed x)
{for(signed i(hit[x]);i<=tot;i+=lowbit(i))c[i].sum+=a[x],++c[i].num;}
inline pair<int,int>query(signed x)
{
int ans1(0),ans2(0);
for(;x;x-=lowbit(x))ans1+=c[x].num,ans2+=c[x].sum;
return make_pair(ans1,ans2);
}
signed main()
{
init_set();
n=read();hi=read(),lo=read();
for(signed i(1);i<=n;++i)a[i]=op[i]=read(),cf[i]=cf[i-1]+a[i];
sort(op+1,op+1+n);
tot=unique(op+1,op+1+n)-op-1;
for(signed i(1);i<=n;++i)
hit[i]=lower_bound(op+1,op+1+tot,a[i])-op;
write(0,'\n');update(1);
for(signed t(2);t<=n;++t)
{
update(t);
signed l(1),r(tot);
unsigned int ans(0);
for(;l<=r;)
{
signed len((r-l)/3),ml(l+len),mr(r-len);
pair<int,int>lres=(query(ml)),rres(query(mr));
unsigned int Orz((lres.first*op[ml]-lres.second)*hi+(cf[t]-lres.second-(t-lres.first)*op[ml])*lo);
unsigned int OTZ((rres.first*op[mr]-rres.second)*hi+(cf[t]-rres.second-(t-rres.first)*op[mr])*lo);
if(Orz<=OTZ)r=mr-1,ans=Orz;
else l=ml+1,ans=OTZ;
}
write(ans,'\n');
}
flush();
return 0;
}
\(T4\) 金牌
\(\Huge但是打了一场模拟赛，又垫底了。qwq\)
