题目列表 - 洛谷 | 计算机科学教育新生态 (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;
// }
// }
//4830549std::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;
} 
