2011年12月11日

## 简单的贪心（最优）

http://acm.nyist.net/JudgeOnline/problem.php?pid=6

#include<iostream>
#include
<algorithm>
#include
<cmath>
using namespace std;
double ri[600],sum;
int main()
{

int i,n,m;
cin
>>m;

while(m--)

{
sum
=0;
cin
>>n;

for(i=0;i<n;i++)

{
cin
>>ri[i];
}

sort(ri,ri
+n);

for(i=n-1;i>=0;i--)

{
sum
+=sqrt(ri[i]*ri[i]-1);

if(sum>=10)

{

break;
}

}

cout
<<n-i<<endl;
}

return 0;
}

posted @ 2011-12-11 16:37 bersaty 阅读(96) | 评论 (0)编辑 收藏

## 欧拉回路问题~

hdoj 1878 和 http://acm.nyist.net/JudgeOnline/problem.php?pid=42

#include<stdio.h>
#include
<string.h>
int d[1001],set[1001];
int w;
int find(int x)
{

int i,j,r=x;

while(r!=set[r]) r=set[r];//根节点
/*    i=x;
while(i!=r)
{
j=set[i];
set[i]=r;
i=j;
}
*/

return r;
}

void unio(int x,int y)
{
x
=find(x);
y
=find(y);

if(x>y) set[x]=y;

else set[y]=x;

if(x!=y) w--;
}

int main()
{

int n,p,q,i;

int a,b,flag,k,j;
scanf(
"%d",&n);

while(n--)

{
scanf(
"%d %d",&p,&q);
w
=p;
memset(d,
0,sizeof(d));
flag
=0;

for(i=1;i<=p;i++set[i]=i;

while(q--)

{
scanf(
"%d %d",&a,&b);

if(a!=b)

{
d[a]
++;d[b]++;
unio(a,b);
}

}

k
=0;

for(i=1;i<=p;i++)

{

if(d[i]&1) k++;

if(d[i]==0

{
k
=1;

break;
}

}

if(flag||(k!=0&&k!=2)||w!=1) printf("No\n");
else printf("Yes\n");
}

return 0;
}

posted @ 2011-12-11 16:33 bersaty 阅读(137) | 评论 (0)编辑 收藏

2011年12月3日

## STL（map）

PS：C++手册真好用~

Map

Maps are a kind of associative containers that stores elements formed by the combination of a key value and a mapped value.

In a map, the key value is generally used to uniquely identify the element, while the mapped value is some sort of value associated to this key. Types of key and mapped value may differ. For example, a typical example of a map is a telephone guide where the name is the key and the telephone number is the mapped value.

Internally, the elements in the map are sorted from lower to higher key value following a specific strict weak ordering criterion set on construction.

As associative containers, they are especially designed to be efficient accessing its elements by their key (unlike sequence containers, which are more efficient accessing elements by their relative or absolute position).

Therefore, the main characteristics of a map as an associative container are:

• Unique key values: no two elements in the map have keys that compare equal to each other. For a similar associative container allowing for multiple elements with equivalent keys, see multimap.
• Each element is composed of a key and a mapped value. For a simpler associative container where the element value itself is its key, see set.
• Elements follow a strict weak ordering at all times. Unordered associative arrays, like unordered_map, are available in implementations following TR1.

Maps are also unique among associative containers in that the implement the direct access operator (operator[]) which allows for direct access of the mapped value.

In their implementation in the C++ Standard Template Library, map containers take four template parameters:
 ```template < class Key, class T, class Compare = less, class Allocator = allocator > > class map; ```
Where the template parameters have the following meanings:

• Key: Type of the key values. Each element in a map is uniquely identified by its key value.
• T: Type of the mapped value. Each element in a map is used to store some data as its mapped value.
• Compare: Comparison class: A class that takes two arguments of the key type and returns a bool. The expression comp(a,b), where comp is an object of this comparison class and a and b are key values, shall return true if a is to be placed at an earlier position than b in a strict weak ordering operation. This can either be a class implementing a function call operator or a pointer to a function (see constructor for an example). This defaults to less<Key>, which returns the same as applying the less-than operator (a<b).
The map object uses this expression to determine the position of the elements in the container. All elements in a map container are ordered following this rule at all times.
• Allocator: Type of the allocator object used to define the storage allocation model. By default, the allocator class template is used, which defines the simplest memory allocation model and is value-independent.
In the reference for the map member functions, these same names (Key, T, Compare and Allocator) are assumed for the template parameters.

This container class supports bidirectional iterators.
Iterators to elements of map containers access to both the key and the mapped value. For this, the class defines what is called its value_type, which is a pair class with its first value corresponding to the const version of the key type (template parameter Key) and its second value corresponding to the mapped value (template parameter T):
 ```typedef pair value_type; ```

Iterators of a map container point to elements of this value_type. Thus, for an iterator called it that points to an element of a map, its key and mapped value can be accessed respectivelly with:
 ```map::iterator it; (*it).first; // the key value (of type Key) (*it).second; // the mapped value (of type T) (*it); // the "element value" (of type pair) ```
Naturally, any other direct access operator, such as -> or [] can be used, for example:
 ```it->first; // same as (*it).first (the key value) it->second; // same as (*it).second (the mapped value) ```

### Member functions

 (constructor) Construct map (public member function)
 (destructor) Map destructor (public member function)
 operator= Copy container content (public member function)

Iterators:
 begin Return iterator to beginning (public member function)
 end Return iterator to end (public member function)
 rbegin Return reverse iterator to reverse beginning (public member function)
 rend Return reverse iterator to reverse end (public member function)

Capacity:
 empty Test whether container is empty (public member function)
 size Return container size (public member function)
 max_size Return maximum size (public member function)

Element access:
 operator[] Access element (public member function)

Modifiers:
 insert Insert element (public member function)
 erase Erase elements (public member function)
 swap Swap content (public member function)
 clear Clear content (public member function)

Observers:
 key_comp Return key comparison object (public member function)
 value_comp Return value comparison object (public member function)

Operations:
 find Get iterator to element (public member function)
 count Count elements with a specific key (public member function)
 lower_bound Return iterator to lower bound (public member function)
 upper_bound Return iterator to upper bound (public member function)
 equal_range Get range of equal elements (public member function)

Allocator:
 get_allocator Get allocator (public member function)

### Member types

of template <class Key, class T, class Compare=less<Key>, class Allocator=allocator<pair <const Key, T> > > class map;

member type definition
key_type Key
mapped_type T
value_type pair<const Key,T>
key_compare Compare
value_compare Nested class to compare elements (see member function value_comp)
allocator_type Allocator
reference Allocator::reference
const_reference Allocator::const_reference
iterator Bidirectional iterator
const_iterator Constant bidirectional iterator
size_type Unsigned integral type (usually same as size_t)
difference_type Signed integral type (usually same as ptrdiff_t)
pointer Allocator::pointer
const_pointer Allocator::const_pointer
reverse_iterator reverse_iterator<iterator>
const_reverse_iterator reverse_iterator<const_iterator>

posted @ 2011-12-03 12:07 bersaty 阅读(299) | 评论 (0)编辑 收藏

2011年11月25日

# 欧拉回路

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5820    Accepted Submission(s): 1987

Problem Description

Input

Output

Sample Input
```3 3
1 2
1 3
2 3
3 2
1 2
2 3
0```

Sample Output
```1
0```

1#include<iostream>
2using namespace std;
3int d[1001],set[1001],a,b;
4int main()
5{
6    int n,m,flag;
7    while(cin>>n&&n)
8    {
9        for(int i=1;i<=n;i++)
10        {
11            d[i]=0;
12            set[i]=i;
13        }

14        cin>>m;
15        flag=0;
16        while(m--)
17        {
18            cin>>a>>b;
19            if(set[a]>set[b])    //判断是否连通用
20                set[a]=set[b];
21            else
22                set[b]=set[a];
23            d[a]++;
24            d[b]++;
25        }

26        for(i=1;i<=n;i++)    //每个节点都必有偶数个度
27            if(d[i]&1)
28            {
29                flag=1;
30                break;
31            }

32        if(!flag)
33            for(i=1;i<=n;i++)
34                if(set[i]!=1)
35                {
36                    flag=1;
37                    break;
38                }

39        if(flag)
40            cout<<"0"<<endl;
41        else
42            cout<<"1"<<endl;
43    }

44    return 0;
45}

posted @ 2011-11-25 11:12 bersaty 阅读(241) | 评论 (0)编辑 收藏

2011年11月21日

## 从一堆数中找出连续的若干个的和 能被P整除~

Input

1≤a(k) ≤10000( 1≤k≤n).

Output

Sample Input

```2
3 5
1 3 2
3 5
4 4 4
```

Sample Output

```Yes
No
```

#include<stdio.h>
long int b[100000]={0};
int main()
{

long int t,n,p,a;

long int c,i,j;
scanf(
"%d",&t);

while(t--)

{
c
=0;
scanf(
"%d %d",&n,&p);

for(i=0;i<n;i++)

{
scanf(
"%d",&a);
a
%=p;

if(!c)

{

for(j=i;j>=0;j--)

{

if(!c)

{
b[j]
=b[j-1]+a;

if(b[j]%p==0)
c
=1;
}

}

b[
0]=a;

if(b[0]%p==0)
c
=1;
}

}

if(c)
printf(
"Yes\n");

else
printf(
"No\n");
}

return 0;
}

sum[i]为前i项和 sum[j]为前j项和
#include<iostream>
long int b[1000000];
int main()
{

long int t,n,p,a,s;

long int c,i;
scanf(
"%d",&t);

while(t--)

{
scanf(
"%ld %ld",&n,&p);
c
=0;
s
=0;
memset(b,
0,p*sizeof(long int));

for(i=0;i<n;i++)

{
scanf(
"%ld",&a);
s
+=a%p;

if(!c)

{

if(b[s%p]==s%p)
c
=1;

else
b[s
%p]=s%p;
}

}

if(c)
printf(
"Yes\n");

else
printf(
"No\n");
}

return 0;
}

posted @ 2011-11-21 11:12 bersaty 阅读(179) | 评论 (0)编辑 收藏

2011年11月5日

## 第六届itat C语言复赛~~~郁闷

a[742683613984]  删除8个数,使其变为最小的4位数~~

#include<stdio.h>
#include
<string.h>

void main()
{

char n[13]="742683613984";

int a[13],i,len,w=0,j;
len
=strlen(n);

for(i=0;i<len;i++)

{
a[i]
=n[i]-'0';
printf(
"%d ",a[i]);
}

printf(
"\n");
i
=0;

do

{

if(a[i]>a[i+1])

{
printf(
"%d \n",a[i]);

for(j=i;j<len;j++)
a[j]
=a[j+1];

i
=0;
w
++;
len
--;

for(i=0;i<len;i++)

{
printf(
"%d ",a[i]);
}

printf(
"\n");
i
=0;
}

else
i
++;
}
while(w<8);
printf(
"\n");
}

posted @ 2011-11-05 13:19 bersaty 阅读(340) | 评论 (2)编辑 收藏

2011年10月3日

## 转

蜜蜂在爱，而花朵在等待

就这样吧，能多久就多久，如果有一天，峰回路转，如果你还记得我，如果我还爱着你

漫天的星星如同破碎的钻石，明亮光耀，抬头仰望，总觉得他们离我并不遥远，只要登上屋顶，在搭上一张梯子，伸出手就能摘到，闪光灯果实。事实证明，那只是一场美丽的幻觉而已，于是我们哭着说，星星是骗子，在长大以后才渐渐明白，欺骗我们的，从来不是星星，而是自己那颗，被欲望填塞的看不清真相的心！

给我一个微笑，我就跟你千山万水

爱情也总是在患得患失的时候最美好，如果永远没有开始，也永远不会消逝，可是，谁又会按捺得住不去开始呢？

当明天开幕的时候，我总是醒着出场的

生活其实宁静美好，爱情仍只是一切偶然，不乏崎岖，但本来，不必如此的

只要你快乐，我会时时刻刻爱你，我也会保有独立的自己，我是我的爱情最执着的牧者

我在无数个夜里凌晨里把仅有的记忆碎片倒出来，敝帚自珍的数着，如同幸福的小乞丐，甘愿在自欺欺人里沉沦

天黑黑的看我，我嘿嘿的看它

树绿了又黄了，干枯了有复苏了，花开了又谢了，枯萎了又绽放了，生命的规律都是如此，更何况一场爱情

我心的天空，风云莫测，既然无法看透，不妨欣赏

生命的方程式，爱情只是一个未知数，常数是我们自己，一颦一笑一投足，其实总是那么简单，只要不纠缠，不解那个解不开的结

他许给我这么多快乐，我不能不快乐，不能许给我爱情，我便独自收留我的爱情

喜欢还是不喜欢，没有应该还是不应该，只能怪你好运或者不好运，遇见了好人还是坏人

只要时间足够，彼岸亦有花香

铭刻是记忆的方式，遗忘时间的本事

天空是灰色的，好在我穿了彩色的衣裳，所以看起来，还不至于太坏

爱能留是福，啊难守该悟

承袭了我所有寂寞和悲伤的你，可不可以偶尔不要恨我

我想我可以忍住悲伤，假装生命中没有你

未来某一天，想起你说的永远，手中握着你给点誓言，多美

生命是一种缘，不曾期待的灿烂会在你的淡薄从容中不期而至

别说爱情会老，别只会在摇头时微笑，甜蜜的时光只有你我知道，风在林梢鸟儿在叫，爱会上瘾，爱是安眠药，梦里花落知多少，可不可以不要醒太早

posted @ 2011-10-03 22:10 bersaty 阅读(87) | 评论 (0)编辑 收藏

2011年10月2日

## 兼职

兼职开始第二天，珊在两个男的陪同下走来，我和几个师姐刚好遇到。是不是女生都容易羡慕妒忌恨，我和师姐聊天，她就和那两个男的聊天，而且越聊越起劲。。。之前面试时遇到珊，长的挺漂亮，感觉人也应该不错。想起了一个故事，一ACMer因看ACM比赛见到一个礼仪小姐很漂亮，就想认识她，经过心理斗争，最后都没定下方法。9大经理说直接当面告诉她因看比赛时看到你，因此对你一见钟情，留下联系电话，结果听天由命了。世界上就三种事，我的事，你的事，老天的事。你的事我管不了，老天的事天说了算，唯一能做的就是我的事，要怎么做就看自己的了。这次我主动了，要了珊的电话，她拿过我的手机，输入了她的手机号码（她是唯一一个这样做的人，我问其他女生拿电话时都是直接说出号码的），然后就一起走了一段路，真的很想拉她的手。但之后我发信息给她她都不回。。。今天她和一个男的一起走，我和那男的一起进更衣室，换完衣服我以为他要等珊的，没想到他马上就走了，当我出来时珊问我那个男的呢，我说他走了，珊不信，叫我喊他的名字，我喊了几次，珊才相信，我和珊走了一小段路，我问她问什么不回我短信，她很不高兴的说“谁有你那么多流量!”。。。伤心啊，女生都是见哪个帅就爱哪个吗？.........

posted @ 2011-10-02 22:59 bersaty 阅读(129) | 评论 (0)编辑 收藏

2011年6月18日

## F(N) HDOJ 2802

long f(long n)
{

long q;

if(n==1)
q
=1;

else if(n==2)
q
=7;

else
q
=(f(n-2)-(n-1)*(n-1)*(n-1)+n*n*n)%2009;

return q;
}

int main()
{

long a[4030];

long n=4020,m,i;

for(i=1;i<=4020;i++)
a[i]
=f(i);

while(scanf("%ld",&m)!=EOF&&m)

{

if(m%4018==0)
printf(
"0\n");

else
printf(
"%ld\n",a[m%4018]);
}

return 0;
}

posted @ 2011-06-18 19:12 bersaty 阅读(162) | 评论 (0)编辑 收藏

## 大菲波数 hdoj 1715

#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>
int main()
{

char s1[1000],s2[1000],sum[1000][1000];

int n,m,len,len1,len2,i,*p,k=1000,w;
n
=3;
strcpy(sum[
1],"1");
strcpy(sum[
2],"1");
strcpy(s1,
"1");
strcpy(s2,
"1");

while(k--)

{

while(n<=k)

{
len1
=strlen(s1),len2=strlen(s2);
len
=len2+2;
p
=(int *)malloc(len*sizeof(int));

for(i=0;i<len;i++)
p[i]
=0;

if(len1==len2)

for(i=len2;i>0;i--)

*(p+i)=(*(s1+i-1)-48)+(*(s2+i-1)-48);

else

{

for(i=len2;i>1;i--)

*(p+i)=(*(s1+i-2)-48)+(*(s2+i-1)-48);

*(p+i)=(*(s2+i-1))-48;
}

for(i=len2;i>0;i--)

{

*(p+i)+=*(p+i+1)/10;

*(p+i-1)+=*(p+i)/10;

*(p+i)=*(p+i)%10;
}

strcpy(s1,s2);

if(p[0]==0)

for(i=0;i<len2;i++)

{
s2[i]
=*(p+i+1)+'0';
}

else

for(i=0;i<=len2;i++)

{
s2[i]
=*(p+i)+'0';
}

s2[i]
='\0';
strcpy(sum[n],s2);
n
++;
}

}

while(scanf("%d",&w)!=EOF)

{

for(i=0;i<w;i++)

{
scanf(
"%d",&m);

if(m==1||m==2)
printf(
"1\n");

else
puts(sum[m]);
}

}

return 0;
}

posted @ 2011-06-18 17:30 bersaty 阅读(259) | 评论 (0)编辑 收藏

• 随笔 - 11
• 文章 - 0
• 评论 - 5
• 引用 - 0

•