算是真正的数论第一题吧。。。。。
看了polya和burnside的定理证明。。。有点看不懂,是离散数学方面群论的内容,不过离散学的不好,忘掉了好多,打算再复习复习了。
然后看到一片题解特别好,都是看这个看懂的,好赞。
http://hi.baidu.com/novosbirsk/item/24427377630e0440ef1e53ff
不过……感觉昨晚这道题都不知道哪里用到了polya啊摔!
QAQ
然后发现流输入真的好慢!!
*******************************************************************************
惭愧,发现这根本不算polya定理,只能算是置换群。
#include <iostream> #include <algorithm> #include <cstring> using namespace std; #define maxn 10010 #define inf 999999999 int vis[maxn],cow[maxn],ncow[maxn],pos[maxn*10]; int main() { int n; cin>>n; int i,j,k; int mii=inf; //memset(vis,0,sizeof(vis)); for(i=0;i<n;i++) { cin>>cow[i]; ncow[i]=cow[i]; pos[cow[i]]=i; mii=min(mii,cow[i]); } sort(ncow,ncow+n); int visit=n; int st,len,sum,tmin; int t1,t2; int ans=0; while(visit) { i=0; while(vis[i]) i++; st=i; len=sum=0; tmin=inf; while(1) { tmin=min(tmin,cow[i]); vis[i]=1; visit--; sum+=cow[i]; len++; // cout<<"i="<<i<<"sum="<<sum<<"len="<<len<<endl; i=pos[ncow[i]]; if(i==st) break; } if(len==1) {//cout<<"***"<<endl; continue;} t1=sum-tmin+tmin*(len-1); t2=tmin+mii+sum+len*mii; // cout<<"t1="<<t1<<"t2="<<t2<<endl; ans+=t1<t2?t1:t2; } cout<<ans<<endl; return 0; }
*******************************************
hdu 4985也是一个置换群的题,不过是大水题……
然后我为什么wa了好多发呢……因为把它排序了…………………………
over