E
观察到s(m)<=108，所以r是可以枚举的
但是枚举完后再开根号，时间复杂度为O(T*r*sqrt(n))≈O(100*100*1e6)
赛时还想了一种自认为更优的做法。
考虑枚举i，枚举完i就能得到r，判断是否满足条件（当然，就像分解质因数那样，n/i也要判断）
然后直接这么写会出点小问题，比如11=10*1+1，i=1时11%1=0
在i比较小时，再从1-108枚举r即可。
这么做是O(Tsqrt(n))的，可惜卡了很久常数没卡过。
放一份代码纪念一下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+5;
int S[N];
int cal(int x){
int ret=0;
while(x){
ret=ret+x%10;
x/=10;
}
return ret;
}
int s(int x){
if(x<N) return S[x];
else {
int a1=x/1000000;
int a2=x%1000000;
return S[a1]+S[a2];
}
}
void solve(){
int n;cin>>n;
int up=sqrt(n),ans=0;
for(int i=1;i<=up;i++){
if(i>108){
int r=n%i;
if(r==s(i)) ans++;
if(i*i!=(n-r)){
if( r<((n-r)/i) && r==s((n-r)/i)) ans++;
}
}
else {
for(int r=1;r<=108;r++){
if( r<i && r<n && (n-r)%i==0 && r==s(i) ) {
// cout<<i<<" "<<r<<"\n";
ans++;
// cout<<"ans: "<<ans<<endl;
}
if(i*i!=(n-r)){
if( r<((n-r)/i) && r<n && (n-r)%i==0 && r==s((n-r)/i) ) {
// cout<<(n-r)/i<<" "<<r<"\n";
ans++;
// cout<<"ans2: "<<ans<<endl;
}
}
}
}
}
cout<<ans<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
for(int i=1;i<N;i++) S[i]=cal(i);
int T;
cin>>T;
while(T--) solve();
return 0;
}
但现场过的队伍基本是直接枚举r，然后分解质因数用Pollard_Rho算法实现，跑了300ms直接冲过了
就变成了一道无趣的PR板子题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=998244353;
int ksm(int a,int b){
int ret=1;a%=MOD;
for(;b;b>>=1,a=(ll)a*a%MOD)if(b&1)ret=(ll)ret*a%MOD;
return ret;
}
long long ksm(long long a,long long b,long long p){
long long ret=1;
for(;b;b>>=1,a=(__int128)a*a%p)
if(b&1)ret=(__int128)ret*a%p;
return ret;
}
bool Miller_Rabin(long long p){
if(p<3||(p&1)==0)return p==2;
long long s,a,k=0,t=p-1;
while(!(t&1)){
t>>=1;
k++;
}
for(int tc=1;tc<=9;tc++){
a=rand()%(p-2)+2;//生成[2,p-1]的质数
s=ksm(a,t,p);
if(s==1||s==p-1)continue;
for(int i=0;i<k-1;i++){
s=(__int128)s*s%p;
if(s==p-1)break;
}
if(s!=p-1)return 0;
}
return 1;
}
long long Pollard_Rho(long long x){
long long s=0,t=0;
long long c=(long long)rand()%(x-1)+1;
int step=0,goal=1;
long long val=1;
for(goal=1; ;goal<<=1,s=t,val=1){
for(step=1;step<=goal;step++){
t=((__int128)t*t+c)%x;
val=(__int128)val*abs(t-s)%x;
if(step%127==0){
//隔一段时间算一次
long long d=gcd(val,x);
if(d>1)return d;
}
}
long long d=gcd(val,x);
if(d>1)return d;
}
}
// decom存放的是质因数
vector<long long> decom;
void solve(long long x){
if(x<2)return;
if(Miller_Rabin(x)){
decom.push_back(x);// 这里的x是质因数
return;
}
long long p=x;
while(p>=x)p=Pollard_Rho(x);//may be p=x;
while(x%p==0)x/=p;
solve(x);solve(p);
}
int S(ll x){
int ret=0;
while(x){ret+=x%10;x/=10;}
return ret;
}
ll p[105],q[105],ans=0;
void dfs(int step,ll m,int r){
if(step==(int)decom.size()+1){
if(m>r && r==S(m)) ans++;
return;
}
dfs(step+1,m,r);
ll tmp=1;
for(int i=1;i<=q[step];i++){
tmp*=p[step];
dfs(step+1,m*tmp,r);
}
}
void work(){
ll n;cin>>n;
ans=0;
for(int r=1;r<=108;r++){
ll t=n-r;
decom.clear();
solve(t);
int cnt=0;
memset(p,0,sizeof p);
memset(q,0,sizeof q);
for(auto v:decom){
p[++cnt]=v;
//cout<<v<<" ";
while(t%v==0){
t/=v;
q[cnt]++;
}
}
dfs(1,1,r);
// if(decom.size()) cout<<"\n r="<<r<<"\n";
}
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--){
work();
}
}
PR算法可以参考：
Pollard Rho算法_rollard rho-CSDN博客
Pollard-Rho - BBD186587 - 博客园 (cnblogs.com)
K
队友签到的
#include<bits/stdc++.h>
using namespace std;
const int N=5e5;
string s;
int n;
bool f[N+5];
void Kafka()
{
cin>>s;
n=s.length();
s='?'+s;
f[0]=1;
for(int i=1;i<=n;++i)
{
string tmp="";
f[i]=0;
for(int j=0;j<=4;++j)
{
if(i-j<1) break;
tmp=s[i-j]+tmp;
if(j==2&&tmp=="ava"&&f[i-j-1]) f[i]=1;
if(j==4&&tmp=="avava"&&f[i-j-1]) f[i]=1;
}
// cout<<"f["<<i<<"]="<<f[i]<<'\n';
}
cout<<(f[n]?"Yes":"No")<<'\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
for(cin>>T;T--;) Kafka();
return 0;
}
A
首先发现最终状态是确定的，过程中怎么拿并不影响最终状态。
所以其实是一道诈骗题，算出能操作几次然后判奇偶即可。
考虑从1到n枚举i，若i最终能出现在终态里，则序列a中一定存在一些数，它们的gcd=i
（显然这些数也要是i的倍数）
复杂度看起来是Nloglog的，但实际上跑不满。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0;bool f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return f?x:-x;
}
const int N=1e5+5;
int gcd(int x,int y){
if (y==0) return x;
return gcd(y,x%y);
}
int n;
int d[N];
void work(){
cin >> n;
int cnt=0;
for (int i=1;i<N;i++)
d[i]=0;
for (int i=1;i<=n;i++){
int x;
cin >> x;
d[x]=1;
}
for (int i=1;i<N;i++){
if (d[i]) continue;
int tmp=0;
for (int j=i*2;j<N;j+=i){
//cerr << "j=" << j << endl;
if (d[j]) tmp=gcd(j,tmp);
if (tmp==i){
//cerr << "i=" << i << endl;
cnt++;
break;
}
}
}
if (cnt&1) cout << "dXqwq" << endl;
else cout << "Haitang" << endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--) work();
return 0;
}
J
这种题有一个trick：考虑能构造出的满足条件的区间数目的上界和下界，然后再进行调整
先想办法构造出长为(n-m)的序列，并且不能构成三角形
然后末尾按x+1 x+2 x+3加入，这样保证一定能新凑出m个三角形。
现在问题变成给定x，如何构造一个[1，x]的排列使得不能构成三角形。
1.x%3=0
可以把x分成3组，比如x=9，有如下构造：
1 4 7，2 5 8，3 6 9
2.x%3=1
同理可以把x分成3组，比如x=10，有如下构造：
1 4 7，2 5 8，3 6 9
那10怎么办？直接塞在最前面得到
10 ，1 4 7，2 5 8，3 6 9
3.x%3=2
同理，把最大的两个塞到前面去，比如x=11
11 10 ，1 4 7，2 5 8，3 6 9
然后就做完了
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+5;
int a[N];
void solve(){
int n,m;cin>>n>>m;
if(m>n-3) {
cout<<-1<<"\n";
return;
}
int k=n-m;
if(k%3==0){
int group=k/3;
for(int i=1,d=1;i<=group;i++,d++){
a[(i-1)*3+1]=d;
}
for(int i=1,d=group+1;i<=group;i++,d++){
a[(i-1)*3+3]=d;
}
for(int i=1,d=2*group+1;i<=group;i++,d++){
a[(i-1)*3+2]=d;
}
for(int i=3*group+1;i<=n;i++) a[i]=i;
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
cout<<"\n";
}
else if(k%3==1){
int group=k/3;
for(int i=1,d=1;i<=group;i++,d++){
a[(i-1)*3+1]=d;
}
for(int i=1,d=group+1;i<=group;i++,d++){
a[(i-1)*3+3]=d;
}
for(int i=1,d=2*group+1;i<=group;i++,d++){
a[(i-1)*3+2]=d;
}
cout<<n<<" ";
for(int i=1;i<=group*3;i++) cout<<a[i]<<" ";
for(int d=3*group+1;d<n;d++) cout<<d<<" ";
cout<<"\n";
}
else {
int group=k/3;
for(int i=1,d=1;i<=group;i++,d++){
a[(i-1)*3+1]=d;
}
for(int i=1,d=group+1;i<=group;i++,d++){
a[(i-1)*3+3]=d;
}
for(int i=1,d=2*group+1;i<=group;i++,d++){
a[(i-1)*3+2]=d;
}
cout<<n<<" "<<n-1<<" ";
for(int i=1;i<=group*3;i++) cout<<a[i]<<" ";
for(int d=3*group+1;d<=n-2;d++) cout<<d<<" ";
cout<<"\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--) solve();
}
标签：10,return,int,ll,多校,long,2024,牛客,ret From： https://www.cnblogs.com/liyishui2003/p/18349796