#
摘要: 首先聲明 這個代碼是錯的。。。
#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...
閱讀全文
這題其實當時就應該想到，但只想到kruskal的程度，覺得不對，就沒敢敲。看了下解題報告，原來可以巧妙的利用一下n號集合，怎么說呢，把邊從大到小排序，然后像做最大生成樹那樣增加邊。
1.如果兩個頂點在同一集合，就把這個集合同一掛到n號集合下面去，由于題目中沒有n這個點，所以掛在n下的就算找到圈了。
2.如果兩個頂點不在同一集合,且兩個頂點都不在n集合，那么請隨意:-)。
3.如果有一個頂點在n集合中，這里要特別注意，害我RE了無數回，要把不是n的那個集合掛到n下面去。想想嘛，本來找到圈了，結果掛到0-n-1下面，又會認定為沒有圈了。
（此題算法參考了標程，但是標程寫得實在太挫了，好像故意要讓人看不懂似的，跟tc里的變態們一個樣，難道標程就不應該寫的友好一點？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語言標準提供了一種數據類型 long long
目前的平臺上 long long 是8字節的 64位整數
表示的數范圍是 [-2^63, 2^63-1]
那么如何輸入輸出這個類型的數據呢
long long test;
scanf("%lld", &test);
printf("%lld", test);
--------------------------------------------------------------------------------
在gcc4+Linux (2.6.15)下面,這樣的輸入輸出是沒有問題的
但是在Windows下面
一些老的編譯器,這樣的代碼是沒法正確工作的
原因是C-Runtime-Library不支持這個參數
在XP+DevC++ 4.9 下面
這個得變成windows的特殊方式指定類型
%lld 得用 %I64d 替換
JL強大。。
光庭杯的題目，可能是由于自己太菜了，別人認為是很水的題目自己也沒做出來。 而且賽后發現這個題很惡心，除了高斯消元以外還考高精度，long long 都過不了，只能用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;//選絕對值最大的
if(id!=i)//找到了絕對值最大所在行，交換行
{
for(t=j;t<=m;t++)swap(rec[i][t],rec[id][t]);
}
if(rec[i][j]==0){i--;continue;}//說明該j列第i行以下全是0了，則處理當前行的下一列
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;//無解
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;
}
今天早上，終于過了GRE機考，心里那個痛快啊。 issue兩篇都是自己寫過的高頻，argument也寫過，再加上ACM隊+CS專業深厚的敲鍵盤功力，哥一下子洋洋灑灑寫了600，700單詞，寫完還剩10分鐘，我汗， 再添點，繼續寫，反正字數越多越好。最后剩五分鐘，開始檢查issue,發現了一些拼寫錯誤，我感覺韋曉亮交的這一招確實還是蠻管用的，能讓你在短時間內將文章的錯誤減少到最低。恩，然后是agrument ，以前也寫過的，反駁的思路比較清晰，一氣呵成 ，大概500個單詞吧。
機經奉上，考點：南京大學圖書館
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."
我選了前者，感覺前面的那個題觀點更有新意。
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。
給出的長度值必須是常量表達式。正如這里給出的，長度值必須定義為整型字面值常量或是已用常量值初始化的整數類型的const對象。
這條語句把bitvec定義為含有32個位的bitset對象。和vector的元素一樣，bitset中的位是沒有命名的，程序員只能按位置來訪問它們。位集合的位置編號從0開始，因此，bitvec的位序是從0到31。以0位開始的位串是低階位（low-order bit），以31位結束的位串是高階位(high-order bit)。
表3-6 初始化bitset對象的方法
|
bitset<n> b;
|
b有n位，每位都為0
|
|
bitset<n> b(u);
|
b是unsigned long型u的一個副本
|
|
bitset<n> b(s);
|
b是string對象s中含有的位串的副本
|
|
bitset<n> b(s, pos, n);
|
b是s中從位置pos開始的n個位的副本
|
1.
用unsigned值初始化bitset對象
當用unsigned long值作為bitset對象的初始值時，該值將轉化為二進制的位模式。而bitset對象中的位集作為這種位模式的副本。如果bitset類型長度大于unsigned long值的二進制位數，則其余的高階位置為0；如果bitet類型長度小于unsigned long值的二進制位數，則只使用unsigned值中的低階位，超過bitet類型長度的高階位將被丟棄。
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
上面的三個例子中，0到15位都置為1。由于bitvec1位數少于unsigned long的位數，因此bitvec1的初始值的高階位被丟棄。bitvec2和unsigned long長度相同，因此所有位正好放置了初始值。bitvec3長度大于32，31位以上的高階位就被置為0。
2. 用string對象初始化bitset對象
當用string對象初始化bitset對象時，string對象直接表示為位模式。從string對象讀入位集的順序是從右向左：
string strval("1100");
bitset<32> bitvec4(strval);
bitvec4的位模式中第2和3的位置為1，其余位置都為0。如果string對象的字符個數小于bitset類型的長度，則高階位將置為0。
string對象和bitset對象之間是反向轉化的：string對象的最右邊字符（即下標最大的那個字符）用來初始化bitset對象的低階位（即下標為0的位）。當用string對象初始化bitset對象時，記住這一差別很重要。
不一定要把整個string對象都作為bitset對象的初始值。相反，可以只用某個子串作為初始值：
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]開始包含四個字符的子串來初始化bitvec5。照常，初始化bitset對象時總是從子串最右邊結尾字符開始的，bitvec5的從0到3的二進制位置為1100，其他二進制位都置為0。如果省略第三個參數則意味著取從開始位置一直到string末尾的所有字符。本例中，取出str末尾的四位來對bitvec6的低四位進行初始化。bitvec6其余的位初始化為0。這些初始化過程的圖示如下：
3.5.2 bitset對象上的操作
多種bitset操作（表3-7）用來測試或設置bitset對象中的單個或多個二進制位：
表3-7 bitset操作
|
b.any()
|
b中是否存在置為1的二進制位？
|
|
b.none()
|
b中不存在置為1的二進制位嗎？
|
|
b.count()
|
b中置為1的二進制位的個數
|
|
b.size()
|
b中二進制位的個數
|
|
b[pos]
|
訪問b中在pos處的二進制位
|
|
b.test(pos)
|
b中在pos處的二進制位是否為1？
|
|
b.set()
|
把b中所有二進制位都置為1
|
|
b.set(pos)
|
把b中在pos處的二進制位置為1
|
|
b.reset()
|
把b中所有二進制位都置為0
|
|
b.reset(pos)
|
把b中在pos處的二進制位置為0
|
|
b.flip()
|
把b中所有二進制位逐位取反
|
|
b.flip(pos)
|
把b中在pos處的二進制位取反
|
|
b.to_ulong()
|
用b中同樣的二進制位返回一個unsigned long值
|
|
os << b
|
把b中的位集輸出到os流
|
1. 測試整個bitset對象
如果bitset對象中有一個或多個二進制位置為1，則any操作返回true，也就是說，其返回值等于1;相反，如果bitset對象中的二進制位全為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的二進制位的個數，可以使用count操作，該操作返回置為1的二進制位的個數：
size_t bits_set = bitvec.count(); // returns number of bits that are on
count操作的返回類型是標準庫中命名為size_t的類型。size_t類型定義在cstddef頭文件中，該文件是C標準庫的頭文件stddef.h的C++版本。它是一個與機器相關的unsigned類型，大小可以保證存儲內存中對象。
與vector和string中的size操作一樣，bitset的size操作返回bitset對象中二進制位的個數，返回值的類型是size_t:
size_t sz = bitvec.size(); // returns 32
2. 訪問bitset對象中的位
可以用下標操作符來讀或寫某個索引位置的二進制位，同樣地，也可以用下標操作符測試給定二進制位的值或設置某個二進制位的值：
// assign 1 to even numbered bits
for (int index = 0; index != 32; index += 2)
bitvec[index] = 1;
上面的循環把bitvec中的偶數下標的位都置為1。
除了用下標操作符，還可以用set、test和reset操作來測試或設置給定二進制位的值：
// equivalent loop using set operation
for (int index = 0; index != 32; index += 2)
bitvec.set(index);
為了測試某個二進制位是否為1，可以用test操作或者測試下標操作符的返回值：
if (bitvec.test(i))
// bitvec[i] is on
// equivalent test using subscript
if (bitvec[i])
// bitvec[i] is on
如果下標操作符測試的二進制位為1，則返回的測試值的結果為true，否則返回false。
3. 對整個bitset對象進行設置
set和reset操作分別用來對整個bitset對象的所有二進制位全置1和全置0：
bitvec.reset(); // set all the bits to 0.
bitvec.set(); // set all the bits to 1
flip操作可以對bitset對象的所有位或個別位按位取反：
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對象的值
to_ulong操作返回一個unsigned long值，該值與bitset對象的位模式存儲值相同。僅當bitset類型的長度小于或等于unsigned long的長度時，才可以使用to_ulong操作：
unsigned long ulong = bitvec3.to_ulong();
cout << "ulong = " << ulong << endl;
to_ulong操作主要用于把bitset對象轉到C風格或標準C++之前風格的程序上。如果bitset對象包含的二進制位數超過unsigned long的長度，將會產生運行時異常。本書將在6.13節介紹異常（exception），并在17.1節中詳細地討論它。
5. 輸出二進制位
可以用輸出操作符輸出bitset對象中的位模式：
bitset<32> bitvec2(0xffff); // bits 0 ... 15 are set to 1; 16 ... 31 are 0
cout << "bitvec2: " << bitvec2 << endl;
輸出結果為：
bitvec2: 00000000000000001111111111111111
6. 使用位操作符
bitset類也支持內置的位操作符。C++定義的這些操作符都只適用于整型操作數，它們所提供的操作類似于本節所介紹的bitset操作。5.3節將介紹這些操作符。
轉自：
http://www.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.時間類外推錯誤，比如說 10 years ago , tendency .... and so on ... 攻擊的方法是
the situation may have changed over the extended period of time.
2.第二個是結論錯誤，要考慮副作用。
side-effects
3.可能有其他手段也能解決這個問題
maybe other methods can also solve the problems , perhps ....herhps...
【題目】少年宮游樂廳內懸掛著300個彩色燈泡，這些燈泡或明或暗，十分有趣。這300個燈泡按1—300編號，它們的亮暗規則是：第一秒，全部燈泡變亮；第二秒，凡編號為2的倍數的燈泡由亮變暗；第三秒，凡編號為3的倍數的燈泡改變原來的亮暗狀態，即亮的變即亮的變暗，暗的變亮；一般地第n秒凡編號為n的倍數的燈泡改變原來的亮暗狀態。這樣繼續下去到第300秒時，亮著的燈泡有幾個？
【解答】根據奇數個約數的自然數是完全平方數。
拉奇數次的燈亮著，每個燈拉的次數是編號的約數的個數。
有奇數個約數的自然數是完全平方數，
比300小的完全平方數有17×17＝289，因此亮著的燈有17個
|
關于這個規律的證明，第一種是數學方法。后來我又想了想，如果用小學生思維，可以這樣證明。
因為一個數的約數總是成對出現的，比如 6=2*3 如果我們找到了一個約數，就必能找到第二個。
而完全平方數有一個n=a*a 這兩個數是一樣的 所以約束個數就是奇數個了，也許這個更好理解一些
PS:想當年哥小學數奧掛金牌的時候 咋不記得有這類題目？ 鄙視自己。。。
賽后看了別人的代碼，發現只要排序就行了。。。。不過確實沒想到用next_permutation啊。。。。。 悔啊。。。。