链接：https://www.nowcoder.com/acm/contest/215/A
来源：牛客网
第一行一个整数 n (1 <= n <= 10
5
)i
第二行 n 个整数 a
(1 <= a
i
<= 10
5
)
输出一个整数，表示满足上述条件的数对个数。
满足条件的有 (1, 2), (2, 3) 两对。
预处理出来 2e5以内的完全平方数（<500个),然后遍历每一个a[i],尝试枚举所有的完全平方数看是否可行即可，注意最后除二，因为
每一对都算了两次。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define pb push_back 5 #define mp make_pair 6 #define pii pair<int,int> 7 LL a[100010]; 8 int vis[200110]; 9 vector<LL>S; 10 int main(){ 11 memset(vis,0,sizeof(vis)); 12 for(LL i=1;i*i<=200000;++i)S.pb(i*i); 13 int n; 14 scanf("%d",&n); 15 for(int i=1;i<=n;++i){ 16 scanf("%lld",a+i); 17 vis[a[i]]++; 18 } 19 LL ans=0; 20 for(int i=1;i<=n;++i){ 21 vis[a[i]]--; 22 for(auto x:S){ 23 //cout<<x<<endl; 24 if(x-a[i]>0 && vis[x-a[i]]!=0) ans+=vis[x-a[i]]; 25 } 26 vis[a[i]]++; 27 } 28 cout<<ans/2<<endl; 29 return 0; 30 }
链接：https://www.nowcoder.com/acm/contest/215/B
来源：牛客网
第一行包括两个整数n,m，表示顶点数和边数
n <= 100000, m <= 200000
接下来m行每行两个整数u,v，表示u,v之间有一条无向边，保证数据合法
一行一个整数表示最小颜色数
观察发现，只要出现奇环，那么答案就是3，否则答案就是2.没有特判一个点的情况也AC了= =
找环的长度只需要dfs一下，d[i]记录根到此点的距离，u->x访问第二次的时候，环长度就是d[u]+1-d[x]。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=100010; 4 std::vector<int> g[maxn]; 5 int d[maxn]={-1}; 6 bool vis[maxn]; 7 void dfs(int u,int fa){ 8 vis[u]=1; 9 d[u]=d[fa]+1; 10 for(auto x:g[u]){ 11 if(x==fa) continue; 12 if(vis[x]){ 13 if((d[u]+1-d[x])%2==1){ 14 cout<<3<<endl; 15 exit(0); 16 } 17 } 18 else{ 19 dfs(x,u); 20 } 21 } 22 } 23 int main(){ 24 int n,m,u,v; 25 cin>>n>>m; 26 while(m--){ 27 scanf("%d%d",&u,&v); 28 g[u].push_back(v); 29 g[v].push_back(u); 30 } 31 dfs(1,0); 32 cout<<2<<endl; 33 return 0; 34 }
原文：https://www.cnblogs.com/zzqc/p/9859319.html