runtime error 1. 数组越界 2. 数组开太小了 3. 发生了 / 0 的操纵
异或运算有以下几个性质：
x ^ x = 0
0 ^ x = x
x ^ x ^ x = x
对 大范围 中 较为稀疏的 进行标记时 要使用map 来减少时间复杂度
map 是 有一个才存一个 并且在遍历的时候 也 很好遍历
book标记数组 需要跑一个循环 才知道 到底这个地方到底有没有！！！！！！！
题目描述
Vasya has several phone books, in which he recorded the telephone numbers of his friends. Each of his friends can have one or several phone numbers.
Vasya decided to organize information about the phone numbers of friends. You will be given n strings — all entries from Vasya’s phone books. Each entry starts with a friend’s name. Then follows the number of phone numbers in the current entry, and then the phone numbers themselves. It is possible that several identical phones are recorded in the same record.
Vasya also believes that if the phone number a is a suffix of the phone number b (that is, the number b ends up with a), and both numbers are written by Vasya as the phone numbers of the same person, then a is recorded without the city code and it should not be taken into account.
The task is to print organized information about the phone numbers of Vasya’s friends. It is possible that two different people have the same number. If one person has two numbers x and y, and x is a suffix of y (that is, y ends in x), then you shouldn’t print number x. If the number of a friend in the Vasya’s phone books is recorded several times in the same format, it is necessary to take it into account exactly once.
Read the examples to understand statement and format of the output better.
Input
First line contains the integer n (1 ≤ n ≤ 20) — number of entries in Vasya’s phone books.
The following n lines are followed by descriptions of the records in the format described in statement. Names of Vasya’s friends are non-empty strings whose length does not exceed 10. They consists only of lowercase English letters. Number of phone numbers in one entry is not less than 1 is not more than 10. The telephone numbers consist of digits only. If you represent a phone number as a string, then its length will be in range from 1 to 10. Phone numbers can contain leading zeros.
Output
Print out the ordered information about the phone numbers of Vasya’s friends. First output m — number of friends that are found in Vasya’s phone books.
The following m lines must contain entries in the following format “name number_of_phone_numbers phone_numbers”. Phone numbers should be separated by a space. Each record must contain all the phone numbers of current friend.
Entries can be displayed in arbitrary order, phone numbers for one record can also be printed in arbitrary order.
样例
Input
4
ivan 3 123 123 456
ivan 2 456 456
ivan 8 789 3 23 6 56 9 89 2
dasha 2 23 789
Output
2
dasha 2 23 789
ivan 4 789 123 2 456
格式为 名字 + 数量 + 具体的电话
要对同一个人 查重 并且删除 同一个人的 多个号码 y以x结尾 那么删除 x
map 正常的 能实现正常的 一对一 的 映射
set 能实现查重
map <string, set<string>> alls;
能实现 一对多的 映射 并且进行查重
auto 能自动 存储类型
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>//一对多 同一个人 又可能有重复的 只保留一个
#include <map>
#include <set>
using namespace std; //若 同一个人的 多个号码 y以x结尾
map <string, set<string>> alls;
int main() // 那么就删除x 后缀 就记录
{
int n, t;
scanf("%d", &n);
string str , ss;
for(int i = 1 ; i <= n ; i ++)
{
cin >> str >> t;
for(int j = 1 ; j <= t ; j ++)
{
cin >> ss;
alls[str].insert(ss);
}// 0 01 012
}//我需要去删除相同的后缀 2 12 612
printf("%d\n",alls.size());
for(auto t : alls)// t 取出来了 <string, set<string>>
{
auto c = t.second;// 取出来了 set
for(auto tt : c)// 取出字符串
{
for(int i = 1 ; i < tt.size() ; i ++)
{
if(c.count(tt.substr(0 + i,tt.length()))) // 在set 中 找到 有没有 那个后缀的字符串
{
c.erase(tt.substr(0 + i,tt.length())); // 然后在set 中 进行删除
}
}
}
cout << t.first << " " << c.size() << " ";
for(auto tt : c)
{
cout << tt << " ";
cout << "\n";
}
}
return 0;
}
map 本身无sort函数
map<string, int> alls;// 记录 一个字符串 出现的次数
如果要让它 按照value 进行排序的话 要借助vector
C++ 代码
#include <iostream>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
map <string, int> alls;//按照字符串出现的次数 进行排序
typedef pair <string, int > PII;
bool cmp(PII a, PII b)
{
return a.second > b.second;
}
int main()
{
for(int i = 0 ; i < 4 ; i ++)
{
string str;
getline(cin, str);
alls[str] ++;
}
vector <PII> vec(alls.begin(), alls.end());
sort(vec.begin(), vec.end(), cmp);
for(auto t : vec)
cout << t.first << " " << t.second << "\n";
return 0;
}
vector 实现 任意位置 插入 和 删除 单个元素 及 区间元素
vector alls.begin()
找到容器中最小的和最大的元素
返回第一个 最小的元素 和 最大的元素 的下标
int idx = min_element(alls.begin() + it, alls.end()) - alls.begin();
int idx1 = max_element(alls.begin() + it, alls.end()) - alls.begin();
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{ // 0 1 2 3 4
vector<int>alls;// 1 2 3 4 5
for(int i = 1 ; i <= 5 ; i ++)
alls.push_back(i); // 删除小标为2 的元素
// alls.erase(alls.begin() + 2);
// for(auto t : alls)
// printf("%d ",t);
// printf("\n");
// alls.erase(alls.begin() , alls.begin() + 3); //删除 [0--3) 之间的元素
// for(auto t : alls)
// printf("%d ",t);
alls.insert(alls.begin() + 3 , 999); // 在下标为3的位置上 插入 999
for(auto t : alls)
printf("%d ", t);
return 0;
}
题目要求一个全排列 要求字典序最小 先尽量让1 放前面 然后是2 然后是3 https://vjudge.net/contest/435159#problem/B
可使用 vector 对单个删除时 全体往前移动
在对单个位置 增加时 后边全体后移
也可实现对单个的删除和 插入
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
int n;
vector <int> alls;
scanf("%d", &n);
for(int i = 0 ; i < n ; i ++)
{
int c;
scanf("%d", &c);
alls.push_back(c);
}
int it = 0;
while(1)
{
if(it >= n - 1)
break;
int idx = min_element(alls.begin() + it, alls.end()) - alls.begin(); // 2
int val = alls[idx];
alls.erase(alls.begin() + idx);//删除掉 当前最小的元素
alls.insert(alls.begin() + it, val);// 在当前位置 再进行插入
if(it == idx)//当前位置就是最下的
it = idx + 1;
else
it = idx;
}
for(auto t : alls)
printf("%d ",t);
printf("\n");
}
return 0;
}
https://codeforces.com/contest/1519/problem/C
vector 的简单应用 可用于分组
类似 链式前向星 每个表头 都是 一条链表
注意 下面一个for循环 写的顺序 不一样 导致tle
本身已经优化到了 极致 但是还tle 分析程序 发现 有一个最占时间复杂度的
可以考虑 换一种 枚举的方式
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
typedef long long ll;
ll u[maxn], s[maxn], ans[maxn];
vector <ll> alls[maxn];
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
int n;
scanf("%d", &n);
for(int i = 1 ; i <= n ; i ++)
{
scanf("%lld", &u[i]);//大学
ans[i] = 0;
alls[i].clear();
}
for(int i = 1 ; i <= n ; i ++)
scanf("%lld", &s[i]); // 技能
for(int i = 1 ; i <= n ; i ++)
alls[u[i]].push_back(s[i]);//分组 1 <= k <= n
for(int i = 1 ; i <= n ; i ++)
{
sort(alls[i].begin(), alls[i].end() , greater<int>());
for(int j = 1 ; j < alls[i].size(); j ++)
{
alls[i][j] += alls[i][j - 1];
}
}
// for(int k = 1 ; k <= n ; k ++) <<<<<<<<<<<<< 时间复杂度 是占 最多的 >>>>>>>>>>>>
// { 无论如何 两个for循环的时间复杂度为O（n^2)
// for(int i = 1 ; i <= n ; i ++)
// {
// int cnt = (alls[i].size() / k) * k; //每个学校 选多少人
// if(cnt != 0 && cnt <= alls[i].size())// 0
// ans[k] += alls[i][cnt - 1];//
// }
// }
for(int i = 1 ; i <= n ; i ++)//枚举多少个学校 当前 时间复杂度 肯定比 O（n^2） 小
{
int k = alls[i].size();//k = 4 如果k为0的话 下层for循环 还进不去
for(int j = 1 ; j <= k ; j ++)
ans[j] += alls[i][((k / j) * j) - 1];
}
for(int k = 1 ; k <= n ; k ++)
printf("%lld ",ans[k]);
printf("\n");
}
return 0;
}
div3 map 降低大量的时间复杂度
1e4组 测试样例
要标记的数字接近2e5 并且要遍历所有 里边存的出现次数 > 1 的数组
使用 for循环 那么最坏的 时间复杂度为O(1e4 * 2e5) 会tle
如果改用 map 进行存储 那么它 会 一个数只要出现了 才会存一个 会大大降低空间复杂度
并且在遍历的时候 只有跑 已经出现过的 没有出现过的 就不会遍历
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int a[200000 + 10];
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
int n;
scanf("%d", &n);
map <int, int> alls;
for(int i = 1 ; i <= n ; i ++)
{
scanf("%d", &a[i]);
if(a[i] - i)
alls[a[i] - i] ++;
else
alls[a[i] - i + 2e5] ++;
}
ll res = 0;
for(auto t : alls)
{
if(t.second > 1)
{
res += (t.second - 1) * 1LL * (1 + t.second - 1) * 1LL / 2 * 1LL;
}
}
printf("%lld\n" ,res);
}
return 0;
}
字符串排序
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct note{
int v;
char s[50];
char m[50];
char x[50];
char h[50];
}a[1000000+5];
bool cmp(note A,note B)
{
int temp=strcmp(A.s,B.s);
int len1=strlen(A.s);
int len2=strlen(B.s);
if(len1<len2)
{ return A.s<B.s; //先返回长度短的
}
else if(len1==len2&&temp!=0) // 如果长度相等返回字典序最小的
return temp<0;
else if(len1==len2&&temp==0)// 如果一样 返回
{ return A.v<B.v;
}
}
int main()
{ int n;
scanf("%d",&n);//n组
for(int i=1;i<=n;i++)
{ scanf("%s %s %s %s",a[i].s,a[i].m,a[i].x,a[i].h);
a[i].v=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{ printf("%s %s %s %s\n",a[i].s,a[i].m,a[i].x,a[i].h);
}
return 0;
}
