Ìâ½â£º
Ò»µÀË®Ì⡣ˮµÄ²»ÄÜÔÚË®¡£
´ÓÑùÀý¾Í¿ÉÒÔ¿´³öÀ´ËüÕÒµÄ˳ÐòÁË¡£
Ö±½Ó¶ÔÄãÊäÈëµÄÊý×Ö¿ª¸ùºÅ£¬È»ºóÒ»¸öÒ»¸öÍùÏÂËõ£¬Ö±µ½ÏÂÒ»¸öÊýÒª´óÓÚµÚÒ»¸öÊý¾ÍÍ£¡£ È»ºó¶ÔʣϵĿª¸ùºÅ£¬Ò»Ö±¿ªÍê¾ÍºÃÁË£¬
ÁíÍâÒ»¸ö¿ìËٵķ½·¨¡£ÓÃÍøÉϵġ£ÏÈ°ÑÁ½¸öƽ·½ÊýÄÜÏà¼ÓµÄµ½µÄÊý×ÖÇò³öÀ´È»ºó¼Ç¼¡£ÕâÑùÎÒÃǵÚÈý²ãÑ»·¾Í¿ÉÒÔÏÈÅжÏÔÙÑ»·ÁË¡£
int mpt[5000010] ={0}; //mpt[i] = 1±íʾi Äܹ»ÓÃÁ½¸öÍêȫƽ·½ÊýÏà¼Ó¶øµÃ¡£ int n; void init() {
for(int i = 0 ; i*i <= n ; i ++) for(int j = 0 ; j*j <=n ; j ++)
if(i*i+j*j <= n) mpt[i*i+j*j] = 1; }
int main() {
int flag = false; scanf(\ init();
for(int i = 0 ; i * i <= n ; i ++) {
for(int j = 0 ; j * j <= n ; j ++){
if(mpt[n - i*i - j*j] == 0) continue; //Èç¹ûʣϵIJîÓÃÁ½¸öÍêȫƽ·½Êý²»ÄÜ×éºÏ³öÀ´¾Í²»¼ÌÐø
for(int k = 0 ; k * k <= n ; k ++) {
int temp = n - i*i - j*j - k*k; double l = sqrt((double) temp); if(l == (int)l ) {
printf(\ flag = true; break; } }
if(flag)break; }
if(flag)break; }
return 0; }
£¨9£© ½»»»Æ¿×Ó
ÓÐN¸öÆ¿×Ó£¬±àºÅ 1 ~ N£¬·ÅÔÚ¼Ü×ÓÉÏ¡£
±ÈÈçÓÐ5¸öÆ¿×Ó£º 2 1 3 5 4
ÒªÇóÿ´ÎÄÃÆð2¸öÆ¿×Ó£¬½»»»ËüÃǵÄλÖᣠ¾¹ýÈô¸É´Îºó£¬Ê¹µÃÆ¿×ÓµÄÐòºÅΪ£º 1 2 3 4 5
¶ÔÓÚÕâô¼òµ¥µÄÇé¿ö£¬ÏÔÈ»£¬ÖÁÉÙÐèÒª½»»»2´Î¾Í¿ÉÒÔ¸´Î»¡£
Èç¹ûÆ¿×Ó¸ü¶àÄØ£¿Äã¿ÉÒÔͨ¹ý±à³ÌÀ´½â¾ö¡£
ÊäÈë¸ñʽΪÁ½ÐУº
µÚÒ»ÐÐ: Ò»¸öÕýÕûÊýN£¨N<10000£©, ±íʾƿ×ÓµÄÊýÄ¿
µÚ¶þÐУºN¸öÕýÕûÊý£¬Óÿոñ·Ö¿ª£¬±íʾƿ×ÓÄ¿Ç°µÄÅÅÁÐÇé¿ö¡£
Êä³öÊý¾ÝΪһÐÐÒ»¸öÕýÕûÊý£¬±íʾÖÁÉÙ½»»»¶àÉٴΣ¬²ÅÄÜÍê³ÉÅÅÐò¡£
ÀýÈ磬ÊäÈ룺 5
3 1 2 5 4
³ÌÐòÓ¦¸ÃÊä³ö£º 3
ÔÙÀýÈ磬ÊäÈ룺 5
5 4 3 2 1
³ÌÐòÓ¦¸ÃÊä³ö£º 2
Ìâ½â£º
ÕâµÀÌâÄ¿¾ÍÊǵäÐ͵ÄÌ°ÐÄÌâÁË¡£
´Ó×î×ó±ßµÄÄǸöϱ꿪ʼ£¬ÍùÓÒ±ßÕÒ×îСµÄÊý×Ö¡£
È»ºó´Ó´Î×ó±ßµÄÄǸöϱ꿪ʼ£¬ÕÒÊ£ÓàÓұߵÄ×îСµÄÊý×ÖÈ»ºó½»»»¡£ ÕâÑùµÄ¸´ÔÓ¶ÈÊÇO(n*n); »á³¬Ê±¡£
ÒòΪÕâ¸öÌâÄ¿µÄ±àºÅÊÇ1~n£»
ËùÒÔ¿ÉÒÔÓÃÁ½¸öÊý×飬һ¸ö´æÊäÈëµÄÊý×飬һ¸ö±êʶ¸ÃÊýÓ¦¸ÃÊÇÔÚµÚ¼¸¸öλÖᣠȻºóÖ±½ÓÒ»¸öÑ»·£¬
#include
const int maxn=1e5+10;
int main() {
int num[maxn],bb[maxn]; int n,sum=0; cin>>n;
for(int i=1;i<=n;++i) {
cin>>num[i]; bb[num[i]]=i; }
for(int i=1;i<=n;++i) {
if(num[i]==i) continue; else if(num[i]!=i) {
if(i==num[num[i]]) swap(num[i],num[num[i]]),++sum; else sum+=2; } }
cout< //Õâ¸ö´úÂë¿ÉÄÜ»¹ÓеãBUG¡£