今天写两个代码的简化问题，注意问题：数组越界，超时间，超内存，for循环内有时需要每次清零，以及==时不要再写成=，因为真的不易检查。
2114 多出的数字
给你m个1到n之间的整数，你能找出1到n中的哪些整数出现了多次吗？
输入
第一行2个整数n,m，直接用空格分隔(n <= 100000, n < m < 2n)，表示有m个1到n之间的整数。
接下来m行，每行一个整数ai（1 <= ai <=n）。
输出
若干行，每行两个数ai和bi，从小到大输出输入数据中出现了超过1次的1到n中的整数ai和它出现的次数bi。
输入样例
5 7
1
1
5
2
4
4
3
输出样例
1 2
4 2
代码一：
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<cstring>
using namespace std;
int a[100001],b[100001];
int main()
{
int n,m,x;
cin>>n>>m;
memset(b,0,sizeof(b));
for(int i=1;i<=m;i++)
{
cin>>x;
for(int j=1;j<=n;j++)
a[j]=j;
for(int j=1;j<=n;j++)
if(x==a[j])
b[j]++;
}
for(int i=1;i<=n;i++)
{
if(b[i]>1)
cout<<a[i]<<" "<<b[i]<<endl;
}
return 0;
}
以上数组用了两个，循环次数较多，容易超时。。。
代码二：
#include <bits/stdc++.h>
using namespace std;
int n,m,a[200005]={},b[100005]={};
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a[m];
b[a[m]]++;
}
for(int i=1;i<=n;i++)
{
if(b[i]>1)
cout<<i<<" "<<b[i]<<endl;
}
return 0;
}
这个是正确的代码。除去第一个代码超时不算的话，还可能导致超内存，即数组越界问题：
输入
第一行2个整数n,m，直接用空格分隔(n <= 100000, n < m < 2n)，在这里可以看出m的大小，当一个在1-n内的数据出现上述范围以上时会越界。
当然第二个也可能出现越界问题，因此一定要读清楚题目，防止越界。
2128 前缀异或
输入一个长度为n(1 <= n <= 100000)数组a[1], a[2], …, a[n]。
输入一个询问数m(1 <= m <= 100000)和m组询问，每组询问形如(l, r)
对于每组询问(l, r)，你需要输出a[l] xor a[l + 1] xor … xor a[r - 1] xor a[r]，即第l个数字到第r个数字的异或。
如果你的算法需要约n*m的时间，你将只能通过第一个测试点。
如果你的算法需要约n+m的时间，你将可以通过本题。
输入
第一行一个整数n
第二行为n个整数a[1], a[2], … a[n]
第三行一个整数m
接下来m行，每行两个整数l, r表示询问。
输出
输出一共m行，对于每一个询问输出一个整数表示结果。
输入样例
3
1 2 3
6
1 1
2 2
3 3
1 2
2 3
1 3
输出样例
1
2
3
3
1
0
代码一：
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int a[100001];
int main()
{
int n,m,x,y,s=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
for(int j=x;j<=y;j++)
s=s^a[j];
cout<<s<<endl;
s=0;
}
return 0;
}
算法需要约nm的时间：
每次循环（y-x）次（按n次算），共m次，即mn次。
这样会超时。。。
代码二：
#include <cstdio>
using namespace std;
int a[200002];
int main()
{
int n,m;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
a[i]=a[i-1]^x;
}
scanf("%d",&m);
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d
",a[r]^a[l-1]);
}
}
这样来算提前n次就把之前的数依次异或过，当输出y-x（l,r）间异或时只需a[r]^a[l-1]一步即可，总计m+n步。