AtCoder Beginner Contest 159 D

Beginner Contest 159 D"/>

AtCoder Beginner Contest 159 D

整理的算法模板：ACM算法模板总结（分类详细版）

链接：

A：The Number of Even Pairs

题意：n个球有n个不同的数印在上面，从中任意选取两个球，如果上面数字和为偶数则成功；求选取方案；（求上面的数字是任意的）

思路：有n个偶数，m个奇数，则从n个偶数里面选取2个方案为C(n,2)；从m个奇数里面选取两个方案数为：C(m,2)；答案就是两者相加；

#include <bits/stdc++.h>
using namespace std;
int main()
{int n,m;cin >>n>>m;int ans=0;if(n>=2) ans+=n*(n-1)/2;if(m>=2) ans+=m*(m-1)/2;cout <<ans<<endl;
}

B：String Palindrome

题意：强回文串的定义：长度为奇数，从第1个字符到第((N−1)/2)个字符形成的串也是回文串；从第(N+3)/2个字符到最后一个字符形成的串也是回文串；现给出一个字符串，让你判断他是否是强回文串；

思路：按照题意模拟一下即可；（说了跟没说一样qaq..）

#include <bits/stdc++.h>
using namespace std;
int main()
{string s;cin >>s;int len=s.size();string a,b,c,x,y;b=s.substr(0,(len-1)/2);c=s.substr((len+3)/2-1,len-(len+3)/2+1);a=s,x=b,y=c;reverse(s.begin(),s.end());reverse(b.begin(),b.end());reverse(c.begin(),c.end());if(s==a&&b==x&&c==y) cout <<"Yes"<<endl;else cout <<"No"<<endl;
}

C：Maximum Volume

题意：给出一个长方体的长宽高之和，让你求它体积的最大值；

思路：当长，宽，高相等时，体积最大；

#include <bits/stdc++.h>
using namespace std;
int main()
{double n;cin >>n;printf("%.8f",n/3*(n/3)*(n/3));
}

D：Banned K

题意：n个球，每个球上面都有数字；k取（1~n）；从n个球里面拿出两个球，不包括k，如果这两个球的数字相等就成功了；求，k一次取（1~n）的时候成功的方案数依次是多少；

思路：分析一下复杂度，暴力一看就超时，所以要优化；

记录每个数出现的次数；然后不考虑会不会取到k，先算出来从n个球里面取两个数相等的方案数  sum；考虑k的时候，假设当前第k个球的数字出现的次数res>=2;那么这个球出现的次数要减去1，所以总次数就是sum-res*(res-1)2+(res-1)*(res-2)/2;

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll> mp;
ll a[2*1000005];
vector<ll> v;int main()
{int n;cin >>n;ll sum=0,ans=0;for(int i=0;i<n;i++) cin >>a[i],mp[a[i]]++;for(auto x : mp){ll res=x.second;if(res>=2) sum+=res*(res-1)/2,v.push_back(res);}for(int i=0;i<n;i++){ll x=a[i];if(mp[x]>=2){ll res=mp[x];cout <<sum-res*(res-1)/2+(res-1)*(res-2)/2<<endl;}else cout <<sum<<endl;}
}