发现做ACM题用STL 就像开挂，很多写了一堆代码的东西一下就KO了，不过还是要学习本质的东西~
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<Key>,
class Allocator = allocator<pair<const Key,T> > > 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<const Key, T> 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<Key,T>::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<const Key,T>)
|
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
| 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:
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> |
欧拉回路
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
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 < N < 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。当N为0时输入结
束。
Output
每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。
Sample Input
3 3
1 2
1 3
2 3
3 2
1 2
2 3
0
Sample Output
网上说要用并查集,唉~~不懂啊,算法白痴,按自己的思路做,欧拉回路每个节点必有偶数个度(通路可以有0个或2个为基数),基本思路就这样
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
}
Input
第一行一个整数 T 代表case数。
每个case第一行是两个整数 n（1≤ n≤ 100000）, p( 1≤p≤1000000),第二行是n个整数
1≤a(k) ≤10000( 1≤k≤n).
Output
每个case输出一行，存在连续个a，这些a的和能被p整除就输出“Yes”,否则输出“No”.
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]-sum[j])%p==0和 sum[i]%p==sum[j]%p 相同 顿时开悟
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;
}
第二题.........
a[742683613984] 删除8个数,使其变为最小的4位数~~
当时就写了思路就交了:
从前面往后退,a[i]>=a[i+1],就删了a[i],如此重复
#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");
}
蜜蜂在爱，而花朵在等待
就这样吧，能多久就多久，如果有一天，峰回路转，如果你还记得我，如果我还爱着你
漫天的星星如同破碎的钻石，明亮光耀，抬头仰望，总觉得他们离我并不遥远，只要登上屋顶，在搭上一张梯子，伸出手就能摘到，闪光灯果实。事实证明，那只是一场美丽的幻觉而已，于是我们哭着说，星星是骗子，在长大以后才渐渐明白，欺骗我们的，从来不是星星，而是自己那颗，被欲望填塞的看不清真相的心！
给我一个微笑，我就跟你千山万水
爱情也总是在患得患失的时候最美好，如果永远没有开始，也永远不会消逝，可是，谁又会按捺得住不去开始呢？
当明天开幕的时候，我总是醒着出场的
生活其实宁静美好，爱情仍只是一切偶然，不乏崎岖，但本来，不必如此的
只要你快乐，我会时时刻刻爱你，我也会保有独立的自己，我是我的爱情最执着的牧者
我在无数个夜里凌晨里把仅有的记忆碎片倒出来，敝帚自珍的数着，如同幸福的小乞丐，甘愿在自欺欺人里沉沦
天黑黑的看我，我嘿嘿的看它
树绿了又黄了，干枯了有复苏了，花开了又谢了，枯萎了又绽放了，生命的规律都是如此，更何况一场爱情
我心的天空，风云莫测，既然无法看透，不妨欣赏
生命的方程式，爱情只是一个未知数，常数是我们自己，一颦一笑一投足，其实总是那么简单，只要不纠缠，不解那个解不开的结
他许给我这么多快乐，我不能不快乐，不能许给我爱情，我便独自收留我的爱情
喜欢还是不喜欢，没有应该还是不应该，只能怪你好运或者不好运，遇见了好人还是坏人
只要时间足够，彼岸亦有花香
铭刻是记忆的方式，遗忘时间的本事
天空是灰色的，好在我穿了彩色的衣裳，所以看起来，还不至于太坏
爱能留是福，啊难守该悟
承袭了我所有寂寞和悲伤的你，可不可以偶尔不要恨我
我想我可以忍住悲伤，假装生命中没有你
未来某一天，想起你说的永远，手中握着你给点誓言，多美
生命是一种缘，不曾期待的灿烂会在你的淡薄从容中不期而至
别说爱情会老，别只会在摇头时微笑，甜蜜的时光只有你我知道，风在林梢鸟儿在叫，爱会上瘾，爱是安眠药，梦里花落知多少，可不可以不要醒太早
兼职开始第二天，珊在两个男的陪同下走来，我和几个师姐刚好遇到。是不是女生都容易羡慕妒忌恨，我和师姐聊天，她就和那两个男的聊天，而且越聊越起劲。。。之前面试时遇到珊，长的挺漂亮，感觉人也应该不错。想起了一个故事，一ACMer因看ACM比赛见到一个礼仪小姐很漂亮，就想认识她，经过心理斗争，最后都没定下方法。9大经理说直接当面告诉她因看比赛时看到你，因此对你一见钟情，留下联系电话，结果听天由命了。世界上就三种事，我的事，你的事，老天的事。你的事我管不了，老天的事天说了算，唯一能做的就是我的事，要怎么做就看自己的了。这次我主动了，要了珊的电话，她拿过我的手机，输入了她的手机号码（她是唯一一个这样做的人，我问其他女生拿电话时都是直接说出号码的），然后就一起走了一段路，真的很想拉她的手。但之后我发信息给她她都不回。。。今天她和一个男的一起走，我和那男的一起进更衣室，换完衣服我以为他要等珊的，没想到他马上就走了，当我出来时珊问我那个男的呢，我说他走了，珊不信，叫我喊他的名字，我喊了几次，珊才相信，我和珊走了一小段路，我问她问什么不回我短信，她很不高兴的说“谁有你那么多流量!”。。。伤心啊，女生都是见哪个帅就爱哪个吗？.........
用了一个下午终于AC了，不过代码很笨拙，不过还是很有成就感~~~~~~~~
不过这个大数相加处理得不怎么好，注释就不上了，代码感觉不怎么好，有待学习~！！
#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;
}