#
摘要: 首先声明 这个代码是错的。。。
#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.cppblog.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啊。。。。。 悔啊。。。。