題目列表 - 洛谷 | 計算機科學教育新生態 (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;
}