题目列表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h>
using ll=unsigned long long;
#define int ll
const int N=2e5+10;
int k=0;
std::string s;
int a,b,c,d;
void solve()
{
char op;
std::cin>>op;
if(op=='A')
{
std::string s;
for(int i=1;i<=2023;i++)
{
s+=std::to_string(i);
}
//std::cout<<s;
//std::cout<<5484660609<<'\n';
ll ans=0;
int len=s.length();
std::vector<int> v1;
std::vector<int> v2;
std::vector<int> v3;
for(int i=0;i<len;i++)
{
if(s[i]=='2') v1.push_back(i);
if(s[i]=='0') v2.push_back(i);
if(s[i]=='3') v3.push_back(i);
}
for(int i=0;i<v1.size();i++)
{
for(int j=0;j<v2.size();j++)
{
if(v2[j]<=v1[i]) continue;
for(int k=i+1;k<=v1.size();k++)
{
if(v1[k]<=v2[j]) continue;
for(int p=0;p<v3.size();p++)
{
if(v3[p]<=v1[k]) continue;
ans++;
}
}
}
}
std::cout<<ans<<'\n';
}
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t=1;
//std::cin>>t;
while(t--)
{
solve();
}
return 0;
} 答案算出来是5484660609。
把质数存下来枚举判断即可，我不记得筛质数的板子所以写了个isprime。。
#include<bits/stdc++.h>
using ll=unsigned long long;
#define int ll
const int N=2e5+10;
int k=0;
std::string s;
int a,b,c,d;
bool isprime(int x)
{
for(int i=2;i<=x/i;i++)
{
if(x%i==0) return false;
}
return true;
}
void solve()
{
char op;
std::cin>>op;
if(op=='A')
{
std::string s;
for(int i=1;i<=2023;i++)
{
s+=std::to_string(i);
}
//std::cout<<s;
std::cout<<5484660609<<'\n';
ll ans=0;
int len=s.length();
std::vector<int> v1;
std::vector<int> v2;
std::vector<int> v3;
for(int i=0;i<len;i++)
{
if(s[i]=='2') v1.push_back(i);
if(s[i]=='0') v2.push_back(i);
if(s[i]=='3') v3.push_back(i);
}
for(int i=0;i<v1.size();i++)
{
for(int j=0;j<v2.size();j++)
{
if(v2[j]<=v1[i]) continue;
for(int k=i+1;k<=v1.size();k++)
{
if(v1[k]<=v2[j]) continue;
for(int p=0;p<v3.size();p++)
{
if(v3[p]<=v1[k]) continue;
ans++;
}
}
}
}
std::cout<<ans<<'\n';
}else{
// for(int i=1;i<=110000000;i++)
// {
// if(i*i>=23333333333333)
// {
// std::cout<<i;
// break;
// }
// }
//4830549
std::vector<int> v;
for(int i=2;i<=5000000;i++)
{
if(isprime(i)) v.push_back(i);
}
//std::cout<<v.size()<<"xxx\n";
ll ans=0;
for(int i=0;i<v.size();i++)
{
for(int j=i+1;j<v.size();j++)
{
if((double)v[i]*v[i]*v[j]*v[j]<=23333333333333&&v[i]*v[i]*v[j]*v[j]>=2333) ans++;
if((double)v[i]*v[i]*v[j]*v[j]>23333333333333) break;
}
}
std::cout<<ans<<'\n';
//947293
}
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t=1;
//std::cin>>t;
while(t--)
{
solve();
}
return 0;
} 最后算出来是947293，偶对要开double，这题会爆ull，原来double比unsigned longlong大啊。
补个线性筛版本，快很多。
#include<bits/stdc++.h>
using ll=unsigned long long;
#define int ll
const int N=5e6+10;
int k=0;
std::string s;
bool st[N];
void solve()
{
std::vector<int> v;
for(int i=2;i<=5000000;i++)
{
if(!st[i]) v.push_back(i);
for(int j=0;j<v.size()&&v[j]<=5000000/i;j++)
{
st[v[j]*i]=1;
}
}
//std::cout<<v.size()<<"xxx\n";
ll ans=0;
for(int i=0;i<v.size();i++)
{
for(int j=i+1;j<v.size();j++)
{
if((double)v[i]*v[i]*v[j]*v[j]<=23333333333333&&v[i]*v[i]*v[j]*v[j]>=2333) ans++;
if((double)v[i]*v[i]*v[j]*v[j]>23333333333333) break;
}
}
std::cout<<ans<<'\n';
//947293
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t=1;
//std::cin>>t;
while(t--)
{
solve();
}
return 0;
} P8605 [蓝桥杯 2013 国 AC] 网络寻路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
DFS会t一个点。
#include<bits/stdc++.h>
using ll=unsigned long long;
using i128=__int128;
const int N=1e5+10;
std::vector<int> g[N];
ll ans=0;
bool st[N];
void dfs(int fa,int x,int cnt)
{
if(cnt==2)
{
for(auto i:g[x])
{
if(!st[i])
{
ans++;
// break;
}
}
return ;
}
if(cnt>2) return ;
for(auto i:g[x])
{
if(i==fa) continue;
if(st[i]) continue;
st[i]=1;
dfs(fa,i,cnt+1);
st[i]=0;
}
}
void solve()
{
int n,m;
std::cin>>n>>m;
while(m--)
{
int u,v;
std::cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
dfs(i,i,0);
}
std::cout<<ans<<'\n';
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t=1;
//std::cin>>t;
while(t--)
{
solve();
}
return 0;
} 实际上经过两个点，我们直接枚举边就好了，对于一条边的两个端点如果都还连着别的点，情况数就加上。
#include<bits/stdc++.h>
using ll=unsigned long long;
using i128=__int128;
const int N=1e5+10;
ll ans=0;
int u[N],v[N];
int rd[N];
void solve()
{
int n,m;
std::cin>>n>>m;
for(int i=1;i<=m;i++)
{
std::cin>>u[i]>>v[i];
rd[v[i]]++,rd[u[i]]++;
}
for(int i=1;i<=m;i++)
{
if(rd[v[i]]>1&&rd[u[i]]>1)
{
ans+=(rd[v[i]]-1)*(rd[u[i]]-1);
}
}
ans*=2;
std::cout<<ans<<'\n';
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t=1;
//std::cin>>t;
while(t--)
{
solve();
}
return 0;
} 
