map
Let the Balloon Rise
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 113243 Accepted Submission(s): 44255
Problem Description Contest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges' favorite time is guessing the most popular problem. When the contest is over, they will count the balloons of each color and find the result. This year, they decide to leave this lovely job to you. Input Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1000) -- the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.
A test case with N = 0 terminates the input and this test case is not to be processed.
Output For each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case. Sample Input
5
green
red
blue
red
red
3
pink
orange
pink
0
Sample Output
red
pink
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
map<string,int >cnt;
int main()
{
int n;
cnt.clear(); //清空map；
while(cin>>n)
{
if(n==0) break;
string s;
for(int i=0;i<n;i++)
{
cin>>s;
if(!cnt.count(s)) //查詢map中是否有字元串s；
cnt[s]=1;
else
cnt[s]++;
}
int maxx=0;
map<string ,int>::iterator it,tmp; //map的疊代；
for(it=cnt.begin();it!=cnt.end();it++)
{
if(it->second>maxx)
{
maxx=it->second; //調用map；
tmp=it;
}
}
cout<<tmp->first<<endl;
cnt.clear();
}
return 0;
}
map與pair函數；
B. Parallelogram is Back time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output
Long time ago Alex created an interesting problem about parallelogram. The input data for this problem contained four integer points on the Cartesian plane, that defined the set of vertices of some non-degenerate (positive area) parallelogram. Points not necessary were given in the order of clockwise or counterclockwise traversal.
Alex had very nice test for this problem, but is somehow happened that the last line of the input was lost and now he has only three out of four points of the original parallelogram. He remembers that test was so good that he asks you to restore it given only these three points.
Input
The input consists of three lines, each containing a pair of integer coordinates xi and yi ( - 1000 ≤ xi, yi ≤ 1000). It's guaranteed that these three points do not lie on the same line and no two of them coincide.
Output
First print integer k — the number of ways to add one new integer point such that the obtained set defines some parallelogram of positive area. There is no requirement for the points to be arranged in any special order (like traversal), they just define the set of vertices.
Then print k lines, each containing a pair of integer — possible coordinates of the fourth point.
Example input
0 0
1 0
0 1
output
3
1 -1
-1 1
1 1
Note
If you need clarification of what parallelogram is, please check Wikipedia page:
https://en.wikipedia.org/wiki/Parallelogram
代碼：
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
set<pair<int,int > >s; //定義set，用到了pair函數；
/*pair的應用
pair是将2個資料組合成一個資料，當需要這樣的需求時就可以使用pair，
如stl中的map就是将key和value放在一起來儲存。
另一個應用是，當一個函數需要傳回2個資料的時候，可以選擇pair。
pair的實作是一個結構體，主要的兩個成員變量是first second
因為是使用struct不是class，是以可以直接使用pair的成員變量。*/
int main()
{
int x1,y1,x2,y2,x3,y3;
cin>>x1>>y1>>x2>>y2>>x3>>y3;
s.insert(make_pair(x1+x2-x3,y1+y2-y3));
s.insert(make_pair(x1+x3-x2,y1+y3-y2));
s.insert(make_pair(x2+x3-x1,y2+y3-y1));
cout<<s.size()<<endl;
set<pair<int,int> >::iterator it;
for(it=s.begin();it!=s.end();it++)
cout<<it->first<<" "<<it->second<<endl;
return 0;
}
于本題而言，k恒為3；
A. Lesha and array splitting time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output
One spring day on his way to university Lesha found an array A. Lesha likes to split arrays into several parts. This time Lesha decided to split the array A into several, possibly one, new arrays so that the sum of elements in each of the new arrays is not zero. One more condition is that if we place the new arrays one after another they will form the old array A.
Lesha is tired now so he asked you to split the array. Help Lesha!
Input
The first line contains single integer n (1 ≤ n ≤ 100) — the number of elements in the array A.
The next line contains n integers a1, a2, ..., an ( - 103 ≤ ai ≤ 103) — the elements of the array A.
Output
If it is not possible to split the array A and satisfy all the constraints, print single line containing "NO" (without quotes).
Otherwise in the first line print "YES" (without quotes). In the next line print single integer k — the number of new arrays. In each of the next k lines print two integers li and ri which denote the subarray A[li... ri] of the initial array A being the i-th new array. Integers li, rishould satisfy the following conditions:
- l1 = 1
- rk = n
- ri + 1 = li + 1 for each 1 ≤ i < k.
If there are multiple answers, print any of them.
Examples input
3
1 2 -3
output
YES
2
1 2
3 3
input
8
9 -12 3 4 -4 -10 7 3
output
YES
2
1 2
3 8
input
1
0
output
NO
input
4
1 2 3 -5
output
YES
4
1 1
2 2
3 3
4 4 大意：給你一個數組，問是否能找到元素和不為 0 的子數組。
思路：隻要原數組不全為 0 就肯定 YES 啊，然後不為 0 的元素自己就是一個（隻存在一個元素）數組，碰到 0 的元素，就跟下一個不為的 0 的元素合一塊作為一個數組就行了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int,int> pii;
int n;
int a[110];
pii ans[110];
int main()
{
while(~scanf("%d",&n))
{
int cnt=0,k=0,p=1;
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
if(a[i]!=0)
{
ans[k].first=p;
ans[k++].second=i;
p=i+1;
}
}
if(p!=n+1) // 說明末尾有存在一定數量的 0
ans[k-1].second=n;
if(k==0)
{
puts("NO");
}
else
{
puts("YES");
printf("%d\n",k);
for(int i=0;i<k;i++)
printf("%d %d\n",ans[i].first,ans[i].second);
}
}
return 0;
}
/*
5
1 -1 1 -1 1
*/
可用map習題
B. Santa Claus and Keyboard Check time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output
Santa Claus decided to disassemble his keyboard to clean it. After he returned all the keys back, he suddenly realized that some pairs of keys took each other's place! That is, Santa suspects that each key is either on its place, or on the place of another key, which is located exactly where the first key should be.
In order to make sure that he's right and restore the correct order of keys, Santa typed his favorite patter looking only to his keyboard.
You are given the Santa's favorite patter and the string he actually typed. Determine which pairs of keys could be mixed. Each key must occur in pairs at most once.
Input
The input consists of only two strings s and t denoting the favorite Santa's patter and the resulting string. s and t are not empty and have the same length, which is at most 1000. Both strings consist only of lowercase English letters.
Output
If Santa is wrong, and there is no way to divide some of keys into pairs and swap keys in each pair so that the keyboard will be fixed, print «-1» (without quotes).
Otherwise, the first line of output should contain the only integer k (k ≥ 0) — the number of pairs of keys that should be swapped. The following k lines should contain two space-separated letters each, denoting the keys which should be swapped. All printed letters must be distinct.
If there are several possible answers, print any of them. You are free to choose the order of the pairs and the order of keys in a pair.
Each letter must occur at most once. Santa considers the keyboard to be fixed if he can print his favorite patter without mistakes.
Examples input
helloworld
ehoolwlroz
output
3
h e
l o
d z
input
hastalavistababy
hastalavistababy
output
input
merrychristmas
christmasmerry
output
-1
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
map<char ,char >cnt1;
map<char ,char >cnt2;
char s1[1003],s2[1003];
int main()
{
int same1,same2,flag;
while(~scanf("%s%s",s1,s2))
{
cnt1.clear(),cnt2.clear();
same1=0,same2=0,flag=0;
int len=strlen(s1);
for(int i=0; i<len; i++)
{
char ss1,ss2,t;
ss1=s1[i],ss2=s2[i];
if(ss1>ss2)
{
t=ss1;
ss1=ss2;
ss2=t;
}
if((cnt1[ss1]!=NULL)&&cnt1[ss1]!=ss2)
flag=1;
else
cnt1[ss1]=ss2;
if((cnt2[ss2]!=NULL)&&cnt2[ss2]!=ss1)
flag=1;
else
cnt2[ss2]=ss1;
}
map<char ,char>::iterator it1,it2,its;
// for(it=cnt.begin(); it!=cnt.end(); it++)
// cout<<it->first<<" "<<it->second<<" nani"<<endl;
// printf("store ok!\n");
//再開一個map；
for(it1=cnt1.begin(); it1!=cnt1.end(); it1++)
{
if(it1->first==it1->second)
same1++;
}
for(it2=cnt2.begin();it2!=cnt2.end();it2++)
{
if(it2->first==it2->second)
same2++;
}
its=cnt1.begin(); its++;
for(it1=cnt1.begin(); its!=cnt1.end(); its++,it1++)
{
if(its->first==it1->second||its->second==it1->second)
flag=1;
}
its=cnt2.begin(); its++;
for(it2=cnt2.begin(); its!=cnt2.end(); its++,it2++)
{
if(its->first==it2->second||its->second==it2->second)
flag=1;
}
if(cnt1.size()!=cnt2.size())
flag=1;
if(flag)
{
printf("-1\n");
}
else
{
int m=cnt1.size()-same1;
cout<<m<<endl;
for(it1=cnt1.begin(); it1!=cnt1.end(); it1++)
{
if(it1->first==it1->second)
continue;
else
cout<<it1->first<<" "<<it1->second<<endl;
}
}
}
return 0;
}
set
{A} + {B}
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19006 Accepted Submission(s): 7983
Problem Description 給你兩個集合，要求{A} + {B}.
注:同一個集合中不會有兩個相同的元素.
Input 每組輸入資料分為三行,第一行有兩個數字n,m(0<n,m<=10000),分别表示集合A和集合B的元素個數.後兩行分别表示集合A和集合B.每個元素為不超出int範圍的整數,每個元素之間有一個空格隔開. Output 針對每組資料輸出一行資料,表示合并後的集合,要求從小到大輸出,每個元素之間有一個空格隔開. Sample Input
1 2
1
2 3
1 2
1
1 2
Sample Output
1 2 3
1 2
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MOD=7;
const int N=5;
int main()
{
set<int >s; //定義集合set；
int n,m;
while(cin>>n>>m)
{
int x;
for(int i=0;i<n;i++)
{
scanf("%d",&x);
s.insert(x); //插入元素s；
}
for(int i=0;i<m;i++)
{
scanf("%d",&x);
s.insert(x);
}
set<int>::iterator Ite=s.begin(); //定義set疊代器；
cout<<*Ite; //輸出set中元素；
Ite++;
for(;Ite!=s.end();Ite++)
cout<<" "<<*Ite;
cout<<endl;
s.clear(); //清空set；
}
return 0;
}
set
單詞數
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 48101 Accepted Submission(s): 11728
Problem Description lily的好朋友xiaoou333最近很空，他想了一件沒有什麼意義的事情，就是統計一篇文章裡不同單詞的總數。下面你的任務是幫助xiaoou333解決這個問題。 Input 有多組資料，每組一行，每組就是一篇小文章。每篇小文章都是由小寫字母和空格組成，沒有标點符号，遇到#時表示輸入結束
Output 每組隻輸出一個整數，其單獨成行，該整數代表一篇文章裡不同單詞的總數。 Sample Input
you are my friend
#
Sample Output
4
代碼：
#include<iostream>
#include<cstdio>
#include<set>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000000;
char w[N];
int main()
{
int len;
set<string >words;
while(gets(w)!=NULL)
{
words.clear();
string s;
int len=strlen(w);
if(w[0]=='#')
break;
for(int i=0;i<len;i++)
{
if(w[i]==' '&&!s.empty())
{
words.insert(s);
s.clear();
}
else if(w[i]!=' ')
s+=w[i];
}
if(!s.empty()) words.insert(s);
cout<<words.size()<<endl;
// set<string >::iterator it;
// for(it=words.begin();it!=words.end();it++)
// cout<<"|"<<*it<<"|"<<" ";
// cout<<endl;
}
return 0;
}
![GlobalMapper20把地形資料（tif）轉為可列印的STL格式模型一、為什麼要把地形轉為stl？二、轉換流程[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)