#
摘要: 首先聲明 這個(gè)代碼是錯(cuò)的。。。
#include<iostream>#include<algorithm>#include<cstdio>using namespace std;int dp[100];int n,m;int dir[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1...
閱讀全文
這題其實(shí)當(dāng)時(shí)就應(yīng)該想到，但只想到kruskal的程度，覺(jué)得不對(duì)，就沒(méi)敢敲。看了下解題報(bào)告，原來(lái)可以巧妙的利用一下n號(hào)集合，怎么說(shuō)呢，把邊從大到小排序，然后像做最大生成樹(shù)那樣增加邊。
1.如果兩個(gè)頂點(diǎn)在同一集合，就把這個(gè)集合同一掛到n號(hào)集合下面去，由于題目中沒(méi)有n這個(gè)點(diǎn)，所以掛在n下的就算找到圈了。
2.如果兩個(gè)頂點(diǎn)不在同一集合,且兩個(gè)頂點(diǎn)都不在n集合，那么請(qǐng)隨意:-)。
3.如果有一個(gè)頂點(diǎn)在n集合中，這里要特別注意，害我RE了無(wú)數(shù)回，要把不是n的那個(gè)集合掛到n下面去。想想嘛，本來(lái)找到圈了，結(jié)果掛到0-n-1下面，又會(huì)認(rèn)定為沒(méi)有圈了。
（此題算法參考了標(biāo)程，但是標(biāo)程寫(xiě)得實(shí)在太挫了，好像故意要讓人看不懂似的，跟tc里的變態(tài)們一個(gè)樣，難道標(biāo)程就不應(yīng)該寫(xiě)的友好一點(diǎn)？bsz）
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
struct node
{
int a;
int b;
int v;
bool operator<(node other)
{return v<other.v;}
}e[2000010];
int ans;
int f[100100];
int r[100000];
int n,m;
int find(int x)
{
if(f[x]==x)
return x;
else f[x]=find(f[x]);
return f[x];
}
int main()
{
//freopen("Pseudoforest.in","r",stdin);
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
ans=0;
if(n==0&&m==0) break;
for(i=0;i<=n;i++)
f[i]=i;
for(i=0;i<m;i++)
scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].v);
sort(e,e+m);
for(i=m-1;i>=0;i--)
{
int a=find(e[i].a);
int b=find(e[i].b);
if(a>b)
swap(a,b);
if(a!=b)
{
ans+=e[i].v;
f[a]=b;
}
else if(a==b&&b!=n)
{
ans+=e[i].v;
f[a]=n;
}
}
printf("%d\n",ans);
}
return 0;
}
C語(yǔ)言標(biāo)準(zhǔn)提供了一種數(shù)據(jù)類型 long long
目前的平臺(tái)上 long long 是8字節(jié)的 64位整數(shù)
表示的數(shù)范圍是 [-2^63, 2^63-1]
那么如何輸入輸出這個(gè)類型的數(shù)據(jù)呢
long long test;
scanf("%lld", &test);
printf("%lld", test);
--------------------------------------------------------------------------------
在gcc4+Linux (2.6.15)下面,這樣的輸入輸出是沒(méi)有問(wèn)題的
但是在Windows下面
一些老的編譯器,這樣的代碼是沒(méi)法正確工作的
原因是C-Runtime-Library不支持這個(gè)參數(shù)
在XP+DevC++ 4.9 下面
這個(gè)得變成windows的特殊方式指定類型
%lld 得用 %I64d 替換
JL強(qiáng)大。。
光庭杯的題目，可能是由于自己太菜了，別人認(rèn)為是很水的題目自己也沒(méi)做出來(lái)。 而且賽后發(fā)現(xiàn)這個(gè)題很惡心，除了高斯消元以外還考高精度，long long 都過(guò)不了，只能用double,不知道出題人怎么想的。。。
#include<iostream>
#include<cmath>
using namespace std;
//高斯消元
const int maxn=60;
int n,m;
int rec[maxn][maxn];
int cop[maxn][maxn];
inline int fab(int x){return x>0?x:-x;}
inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}
double gauss()
{
int i,j,k,t;
for(i=0,j=0;i<n,j<m;i++,j++)
{
int id=i;
for(k=i+1;k<n;k++)if(fab(rec[k][j])>fab(rec[id][j]))id=k;//選絕對(duì)值最大的
if(id!=i)//找到了絕對(duì)值最大所在行，交換行
{
for(t=j;t<=m;t++)swap(rec[i][t],rec[id][t]);
}
if(rec[i][j]==0){i--;continue;}//說(shuō)明該j列第i行以下全是0了，則處理當(dāng)前行的下一列
for(k=i+1;k<n;k++)
{
if(rec[k][j]==0)continue;
for(t=j;t<=m;t++)rec[k][t]=rec[k][t]^rec[i][t];
}
}
for(k=i;k<n;k++)if(rec[k][m]!=0)return 0;//無(wú)解
if(i<=m) return pow(2.0,m-i);
}
int main()
{
int t;
int i,j;
int q;
int casenum=0;
scanf("%d",&t);
while(t--)
{
casenum++;
memset(rec,0,sizeof(rec));
memset(cop,0,sizeof(cop));
scanf("%d%d",&n,&m);
int num;
for(i=1;i<=m;i++)
{
scanf("%d",&num);
for(j=1;j<=num;j++)
{
int tem;
scanf("%d",&tem);
rec[tem-1][i-1]=1;
cop[tem-1][i-1]=1;
}
}
scanf("%d",&q);
printf("Case %d:\n",casenum);
for(i=1;i<=q;i++)
{
int k;
for(j=0;j<n;j++)
for(k=0;k<m;k++)
rec[j][k]=cop[j][k];
for(j=0;j<n;j++)
scanf("%d",&rec[j][m]);
double ans=gauss();
printf("%.0lf\n",ans);
}
}
return 0;
}
今天早上，終于過(guò)了GRE機(jī)考，心里那個(gè)痛快啊。 issue兩篇都是自己寫(xiě)過(guò)的高頻，argument也寫(xiě)過(guò)，再加上ACM隊(duì)+CS專業(yè)深厚的敲鍵盤(pán)功力，哥一下子洋洋灑灑寫(xiě)了600，700單詞，寫(xiě)完還剩10分鐘，我汗， 再添點(diǎn)，繼續(xù)寫(xiě)，反正字?jǐn)?shù)越多越好。最后剩五分鐘，開(kāi)始檢查issue,發(fā)現(xiàn)了一些拼寫(xiě)錯(cuò)誤，我感覺(jué)韋曉亮交的這一招確實(shí)還是蠻管用的，能讓你在短時(shí)間內(nèi)將文章的錯(cuò)誤減少到最低。恩，然后是agrument ，以前也寫(xiě)過(guò)的，反駁的思路比較清晰，一氣呵成 ，大概500個(gè)單詞吧。
機(jī)經(jīng)奉上，考點(diǎn)：南京大學(xué)圖書(shū)館
issue 的兩道題目是：
43"To be an effective leader, a public official must maintain the highest ethical and moral standards."
63"To truly understand your own culture—no matter how you define it—requires personal knowledge of at least one other culture, one that is distinctly different from your own."
我選了前者，感覺(jué)前面的那個(gè)題觀點(diǎn)更有新意。
argument 是
207.It is known that in recent years, industrial pollution has caused the Earth's ozone layer to thin, allowing an increase in the amount of ultraviolet radiation that reaches the Earth's surface. At the same time, scientists have discovered, the population of a species of salamander that lays its eggs in mountain lakes has declined. Since ultraviolet radiation is known to be damaging to delicate tissues and since salamander eggs have no protective shells, it must be the case that the increase in ultraviolet radiation has damaged many salamander eggs and prevented them from hatching. This process will no doubt cause population declines in other species, just as it has in the salamander species.
聲明
#include <bitset>
using std::bitset;
bitset的定義和初始化
bitset<32> bitvec; //32位，全為0。
給出的長(zhǎng)度值必須是常量表達(dá)式。正如這里給出的，長(zhǎng)度值必須定義為整型字面值常量或是已用常量值初始化的整數(shù)類型的const對(duì)象。
這條語(yǔ)句把bitvec定義為含有32個(gè)位的bitset對(duì)象。和vector的元素一樣，bitset中的位是沒(méi)有命名的，程序員只能按位置來(lái)訪問(wèn)它們。位集合的位置編號(hào)從0開(kāi)始，因此，bitvec的位序是從0到31。以0位開(kāi)始的位串是低階位（low-order bit），以31位結(jié)束的位串是高階位(high-order bit)。
表3-6 初始化bitset對(duì)象的方法
|
bitset<n> b;
|
b有n位，每位都為0
|
|
bitset<n> b(u);
|
b是unsigned long型u的一個(gè)副本
|
|
bitset<n> b(s);
|
b是string對(duì)象s中含有的位串的副本
|
|
bitset<n> b(s, pos, n);
|
b是s中從位置pos開(kāi)始的n個(gè)位的副本
|
1.
用unsigned值初始化bitset對(duì)象
當(dāng)用unsigned long值作為bitset對(duì)象的初始值時(shí)，該值將轉(zhuǎn)化為二進(jìn)制的位模式。而bitset對(duì)象中的位集作為這種位模式的副本。如果bitset類型長(zhǎng)度大于unsigned long值的二進(jìn)制位數(shù)，則其余的高階位置為0；如果bitet類型長(zhǎng)度小于unsigned long值的二進(jìn)制位數(shù)，則只使用unsigned值中的低階位，超過(guò)bitet類型長(zhǎng)度的高階位將被丟棄。
bitset<16> bitvec1(0xffff); // bits 0 ... 15 are set to 1
// bitvec2 same size as initializer
bitset<32> bitvec2(0xffff); // bits 0 ... 15 are set to 1; 16 ... 31 are 0
// on a 32-bit machine, bits 0 to 31 initialized from 0xffff
bitset<128> bitvec3(0xffff); // bits 32 through 127 initialized to zero
上面的三個(gè)例子中，0到15位都置為1。由于bitvec1位數(shù)少于unsigned long的位數(shù)，因此bitvec1的初始值的高階位被丟棄。bitvec2和unsigned long長(zhǎng)度相同，因此所有位正好放置了初始值。bitvec3長(zhǎng)度大于32，31位以上的高階位就被置為0。
2. 用string對(duì)象初始化bitset對(duì)象
當(dāng)用string對(duì)象初始化bitset對(duì)象時(shí)，string對(duì)象直接表示為位模式。從string對(duì)象讀入位集的順序是從右向左：
string strval("1100");
bitset<32> bitvec4(strval);
bitvec4的位模式中第2和3的位置為1，其余位置都為0。如果string對(duì)象的字符個(gè)數(shù)小于bitset類型的長(zhǎng)度，則高階位將置為0。
string對(duì)象和bitset對(duì)象之間是反向轉(zhuǎn)化的：string對(duì)象的最右邊字符（即下標(biāo)最大的那個(gè)字符）用來(lái)初始化bitset對(duì)象的低階位（即下標(biāo)為0的位）。當(dāng)用string對(duì)象初始化bitset對(duì)象時(shí)，記住這一差別很重要。
不一定要把整個(gè)string對(duì)象都作為bitset對(duì)象的初始值。相反，可以只用某個(gè)子串作為初始值：
string str("1111111000000011001101");
bitset<32> bitvec5(str, 5, 4); // 4 bits starting at str[5], 1100
bitset<32> bitvec6(str, str.size() - 4); // use last 4 characters
這里用str中從str[5]開(kāi)始包含四個(gè)字符的子串來(lái)初始化bitvec5。照常，初始化bitset對(duì)象時(shí)總是從子串最右邊結(jié)尾字符開(kāi)始的，bitvec5的從0到3的二進(jìn)制位置為1100，其他二進(jìn)制位都置為0。如果省略第三個(gè)參數(shù)則意味著取從開(kāi)始位置一直到string末尾的所有字符。本例中，取出str末尾的四位來(lái)對(duì)bitvec6的低四位進(jìn)行初始化。bitvec6其余的位初始化為0。這些初始化過(guò)程的圖示如下：
3.5.2 bitset對(duì)象上的操作
多種bitset操作（表3-7）用來(lái)測(cè)試或設(shè)置bitset對(duì)象中的單個(gè)或多個(gè)二進(jìn)制位：
表3-7 bitset操作
|
b.any()
|
b中是否存在置為1的二進(jìn)制位？
|
|
b.none()
|
b中不存在置為1的二進(jìn)制位嗎？
|
|
b.count()
|
b中置為1的二進(jìn)制位的個(gè)數(shù)
|
|
b.size()
|
b中二進(jìn)制位的個(gè)數(shù)
|
|
b[pos]
|
訪問(wèn)b中在pos處的二進(jìn)制位
|
|
b.test(pos)
|
b中在pos處的二進(jìn)制位是否為1？
|
|
b.set()
|
把b中所有二進(jìn)制位都置為1
|
|
b.set(pos)
|
把b中在pos處的二進(jìn)制位置為1
|
|
b.reset()
|
把b中所有二進(jìn)制位都置為0
|
|
b.reset(pos)
|
把b中在pos處的二進(jìn)制位置為0
|
|
b.flip()
|
把b中所有二進(jìn)制位逐位取反
|
|
b.flip(pos)
|
把b中在pos處的二進(jìn)制位取反
|
|
b.to_ulong()
|
用b中同樣的二進(jìn)制位返回一個(gè)unsigned long值
|
|
os << b
|
把b中的位集輸出到os流
|
1. 測(cè)試整個(gè)bitset對(duì)象
如果bitset對(duì)象中有一個(gè)或多個(gè)二進(jìn)制位置為1，則any操作返回true，也就是說(shuō)，其返回值等于1;相反，如果bitset對(duì)象中的二進(jìn)制位全為0,則none操作返回true。
bitset<32> bitvec; // 32 bits, all zero
bool is_set = bitvec.any(); // false, all bits are zero
bool is_not_set = bitvec.none(); // true, all bits are zero
如果需要知道置為1的二進(jìn)制位的個(gè)數(shù)，可以使用count操作，該操作返回置為1的二進(jìn)制位的個(gè)數(shù)：
size_t bits_set = bitvec.count(); // returns number of bits that are on
count操作的返回類型是標(biāo)準(zhǔn)庫(kù)中命名為size_t的類型。size_t類型定義在cstddef頭文件中，該文件是C標(biāo)準(zhǔn)庫(kù)的頭文件stddef.h的C++版本。它是一個(gè)與機(jī)器相關(guān)的unsigned類型，大小可以保證存儲(chǔ)內(nèi)存中對(duì)象。
與vector和string中的size操作一樣，bitset的size操作返回bitset對(duì)象中二進(jìn)制位的個(gè)數(shù)，返回值的類型是size_t:
size_t sz = bitvec.size(); // returns 32
2. 訪問(wèn)bitset對(duì)象中的位
可以用下標(biāo)操作符來(lái)讀或?qū)懩硞€(gè)索引位置的二進(jìn)制位，同樣地，也可以用下標(biāo)操作符測(cè)試給定二進(jìn)制位的值或設(shè)置某個(gè)二進(jìn)制位的值：
// assign 1 to even numbered bits
for (int index = 0; index != 32; index += 2)
bitvec[index] = 1;
上面的循環(huán)把bitvec中的偶數(shù)下標(biāo)的位都置為1。
除了用下標(biāo)操作符，還可以用set、test和reset操作來(lái)測(cè)試或設(shè)置給定二進(jìn)制位的值：
// equivalent loop using set operation
for (int index = 0; index != 32; index += 2)
bitvec.set(index);
為了測(cè)試某個(gè)二進(jìn)制位是否為1，可以用test操作或者測(cè)試下標(biāo)操作符的返回值：
if (bitvec.test(i))
// bitvec[i] is on
// equivalent test using subscript
if (bitvec[i])
// bitvec[i] is on
如果下標(biāo)操作符測(cè)試的二進(jìn)制位為1，則返回的測(cè)試值的結(jié)果為true，否則返回false。
3. 對(duì)整個(gè)bitset對(duì)象進(jìn)行設(shè)置
set和reset操作分別用來(lái)對(duì)整個(gè)bitset對(duì)象的所有二進(jìn)制位全置1和全置0：
bitvec.reset(); // set all the bits to 0.
bitvec.set(); // set all the bits to 1
flip操作可以對(duì)bitset對(duì)象的所有位或個(gè)別位按位取反：
bitvec.flip(0); // reverses value of first bit
bitvec[0].flip(); // also reverses the first bit
bitvec.flip(); // reverses value of all bits
4. 獲取bitset對(duì)象的值
to_ulong操作返回一個(gè)unsigned long值，該值與bitset對(duì)象的位模式存儲(chǔ)值相同。僅當(dāng)bitset類型的長(zhǎng)度小于或等于unsigned long的長(zhǎng)度時(shí)，才可以使用to_ulong操作：
unsigned long ulong = bitvec3.to_ulong();
cout << "ulong = " << ulong << endl;
to_ulong操作主要用于把bitset對(duì)象轉(zhuǎn)到C風(fēng)格或標(biāo)準(zhǔn)C++之前風(fēng)格的程序上。如果bitset對(duì)象包含的二進(jìn)制位數(shù)超過(guò)unsigned long的長(zhǎng)度，將會(huì)產(chǎn)生運(yùn)行時(shí)異常。本書(shū)將在6.13節(jié)介紹異常（exception），并在17.1節(jié)中詳細(xì)地討論它。
5. 輸出二進(jìn)制位
可以用輸出操作符輸出bitset對(duì)象中的位模式：
bitset<32> bitvec2(0xffff); // bits 0 ... 15 are set to 1; 16 ... 31 are 0
cout << "bitvec2: " << bitvec2 << endl;
輸出結(jié)果為：
bitvec2: 00000000000000001111111111111111
6. 使用位操作符
bitset類也支持內(nèi)置的位操作符。C++定義的這些操作符都只適用于整型操作數(shù)，它們所提供的操作類似于本節(jié)所介紹的bitset操作。5.3節(jié)將介紹這些操作符。
轉(zhuǎn)自：
http://m.shnenglu.com/ylfeng/archive/2010/03/26/110592.html
TOPIC: ISSUE1 - "We can usually learn much more from people whose views we share than from people whose views contradict our own; disagreement can cause stress and inhibit learning."
WORDS: 682 TIME: 00:45:00 DATE: 2010-4-6 23:56:17
At first glance of the topic , it is maybe a little sensible ,the speaker claims that we can usually learn much more from the people whose views we share than from people whose views contradict our own. But when I think twice , the further reflection reveals that it is not just easy on the surface as it looks .we should bring the topic to a dialectical analysis.
admittedly , I have to point out that , indeed , we can of course learn much things from the people whose views we share because we have the similarities on the problems so we can learn from each other to deep our understanding. When I come to the algorithm study of Suffix Array, I usually turn to ACrush for help, who is the real topcoder in the world when we mention the coders in the world and he is also the No.1 in topcoder web site -www.topcoder.com/tc. From him , I learn more about the suffix array and I eventually get a deeper understanding of the algorithm. In fact , I have to think him a lot .So , from the case , we can easily draw a conclusion that we can learn much more from people whose views we share because maybe he can bring you to a deeper understanding.
But on the other hand, we can't deny that the contradict views are very significant and necessary , since the different views can help us correct our mistakes . Take one person for example , vinsalius,a surgeon , who is considered to be the most famous person in the history , challenged the theory
of Galen in that field , who was in dominate for a long time .The result later proved that vinsalius was right and it help the public to have a correct understanding of human body.
And history need different ideas. In many situation , the different ideas is the source to the advancement of the history . Without it , the watt can't invent the steam engine and we can't own such a rapid speed of development and of course we can't step into the modern age.Without it ,the Edison will not invent the light bult , the human beings will still live in the dark , it is awful ,right? And without it , maybe the earth is still the center of the universe and the earth is still flat. Maybe it is a little uncredible , but if we are in the situation without the ideas differ from the previous ones, those imaginations will be possible.
Ok, to be more objective , I still have to remain you of being careful with the ideas that are contradict our own. Not every idea that differs from us is a good one.A different idea, maybe if of value or not ,we should not trust it easily and also we should not rule it out without our consideration.The best way is to give it the proper analysis after you take action and with the method you can adopt the correct idea , abandoning the uncorrect. In my eyes , it is also a character that every student need to own so that we can have a dialectical view to one given issue.
OK, to sum up. The speaker's assert is not very sensible because it is just meaningful in one side , omiting the other. To be objective , we have to notice that not only we can learn much from the people whose views we share but also we can learn much from that people whose ideas are different from us . The different views are very significant to person's life and to the history of all human beings of all around the world. We should learn to have a dialectical views toward the two sides.As a student , we must have the skill to tell which is wrong and which is not when we encount with a idea which is contradictory with our own becasue it is a basic principle to all student in modern age.
TOPIC: ARGUMENT1 - The following appeared in a memorandum written by the vice president of Nature's Way, a chain of stores selling health food and other health-related products.
"Previous experience has shown that our stores are most profitable in areas where residents are highly concerned with leading healthy lives. We should therefore build our next new store in Plainsville, which has many such residents. Plainsville merchants report that sales of running shoes and exercise clothing are at all-time highs. The local health club, which nearly closed five years ago due to lack of business, has more members than ever, and the weight training and aerobics classes are always full. We can even anticipate a new generation of customers: Plainsville's schoolchildren are required to participate in a 'fitness for life' program, which emphasizes the benefits of regular exercise at an early age."
WORDS: 453 TIME: 00:30:00 DATE: 2010-4-6 23:56:17
When I scan the argument first , it is a little sensible ,but when I think twice , I think it is not so credible on the surface as the speaker said. The speak draw a rash conclusion that they should build their next neew store in Plainsville.As far as I can see, the article suffers from many flaws.
At first , the author fail to build the relationship between the profit and the store which he plans to build.The experience is previous , it can't stand for the situation today.Maybe in nowadays , the stores can not make any money,right?
The author also mentioned that the people in Plainsville concerned with leading healthy lives.At first , we have no evidence that can prove the people concern with leading healthy lives. The merhants' report can only prove that the sales of running shoes and exercise clothing are good ,it can't tell us the people like to lead healthy lives.And the case of local health club is the same, it can just mean nothing. I wonder why the club closed five years ago, maybe the real cause is the people don't have the need to lead a healthy lives.
OK, the last students' evidence , maybe a little sensible.But further reflection reveals that even though they have to participate in the program by force ,they also have no need to be the buyers of the store.
Ok , as I analyzed above , the author fail to build a relationship between the healthy lives and the evidence.Even though the citizens there really need a healthy lives , they also don't need to buy the things in the store , maybe it is very expensive,or they don't like the style and so on.
The speack fail the think the other methods that can make profit.
Even though the people there really like to go to the store that the speaker want to build , it has still some problem because maybe it is not profitable. First , you can't know how many people will buy your products and secondly, maybe the cost is very high and you can't make money at all ,you need to pay a lots of tax and other kinds of payment so that you can not ensure that your store will profitable.
OK, in my eyes, the argument is full with all kinds of flaws. the speaker build a worng relationsip between the healthy lives and the profitable store.And the eviendences he use is also full with flaws .So I have to remind you to have a dialectical view to this argument and if I was the speak in the argument , I should think twice before I draw this conclusion.
1.時(shí)間類外推錯(cuò)誤，比如說(shuō) 10 years ago , tendency .... and so on ... 攻擊的方法是
the situation may have changed over the extended period of time.
2.第二個(gè)是結(jié)論錯(cuò)誤，要考慮副作用。
side-effects
3.可能有其他手段也能解決這個(gè)問(wèn)題
maybe other methods can also solve the problems , perhps ....herhps...
【題目】少年宮游樂(lè)廳內(nèi)懸掛著300個(gè)彩色燈泡，這些燈泡或明或暗，十分有趣。這300個(gè)燈泡按1—300編號(hào)，它們的亮暗規(guī)則是：第一秒，全部燈泡變亮；第二秒，凡編號(hào)為2的倍數(shù)的燈泡由亮變暗；第三秒，凡編號(hào)為3的倍數(shù)的燈泡改變?cè)瓉?lái)的亮暗狀態(tài)，即亮的變即亮的變暗，暗的變亮；一般地第n秒凡編號(hào)為n的倍數(shù)的燈泡改變?cè)瓉?lái)的亮暗狀態(tài)。這樣繼續(xù)下去到第300秒時(shí)，亮著的燈泡有幾個(gè)？
【解答】根據(jù)奇數(shù)個(gè)約數(shù)的自然數(shù)是完全平方數(shù)。
拉奇數(shù)次的燈亮著，每個(gè)燈拉的次數(shù)是編號(hào)的約數(shù)的個(gè)數(shù)。
有奇數(shù)個(gè)約數(shù)的自然數(shù)是完全平方數(shù)，
比300小的完全平方數(shù)有17×17＝289，因此亮著的燈有17個(gè)
|
關(guān)于這個(gè)規(guī)律的證明，第一種是數(shù)學(xué)方法。后來(lái)我又想了想，如果用小學(xué)生思維，可以這樣證明。
因?yàn)橐粋€(gè)數(shù)的約數(shù)總是成對(duì)出現(xiàn)的，比如 6=2*3 如果我們找到了一個(gè)約數(shù)，就必能找到第二個(gè)。
而完全平方數(shù)有一個(gè)n=a*a 這兩個(gè)數(shù)是一樣的 所以約束個(gè)數(shù)就是奇數(shù)個(gè)了，也許這個(gè)更好理解一些
PS:想當(dāng)年哥小學(xué)數(shù)奧掛金牌的時(shí)候 咋不記得有這類題目？ 鄙視自己。。。
賽后看了別人的代碼，發(fā)現(xiàn)只要排序就行了。。。。不過(guò)確實(shí)沒(méi)想到用next_permutation啊。。。。。 悔啊。。。。