两个整数L(1<=L<=10000)和M(1<=M<=100)。 接下来有M组整数,每组有一对数字。
可能有多组输入数据,对于每组输入数据,输出一个数,表示移走所有区间的树之后剩下的树的个数。
500 3 100 200 150 300 470 471
298
#include<bits/stdc++.h> using namespace std; int vis[10001]; void CHU(int from,int to){ for(int i=from;i<=to;i++){ vis[i]=1; } return; } int main(){ int L,M; while(cin>>L>>M){ int from,to; memset(vis,0,sizeof(vis)); for(int i=0;i<M;i++){ cin>>from>>to; CHU(from,to); } int ans=0; for(int i=0;i<=L;i++){ if(vis[i]==0){ ans++; } } cout<<ans<<endl; } return 0; }
//设置一个数组,布尔数组或者int数组都可 #include <stdio.h> #include <stdbool.h> //不能const bool arr[10001]; int main(){ int l,m,count,x,y; scanf("%d%d",&l,&m); for(int i=0;i<l;i++){ arr[i]=true;//种树 } count=l+1; while(m--){ scanf("%d%d",&x,&y); for(int j=x;j<=y;j++){ if(arr[j]){ arr[j]=false; count--; } } } printf("%d",count); }
跟大部分的人都差不多,小白也能看懂,定义一个数组,注意点是数组的大小务必得是L+1,比如说L=100,那么就有101棵树! #include<iostream> using namespace std; int main(){ int l,m; int from,to;//区间 while(cin >> l >> m){ //判断 if(l > 10000 || m > 100) break; //正文 int arr[l + 1]; for(int i = 0; i <= l; i++){ arr[i] = 1; } for(int i = 0; i < m; i++){ cin >> from >> to; for(int j = 0; j <= to - from; j++){ arr[from - 1 + j] = 0; } } int residual = 0; //剩余 for(int i = 0; i <= l; i++){ if(arr[i] == 1) residual++; } cout << residual << endl; } return 0; }
#include<iostream> #include<vector> #include<algorithm> using namespace std; bool cmp(vector<int>a,vector<int>b) { if(a[0]==b[0]) return a[1]<b[1]; //区间左边界相等,则右边界小的排在前 return a[0]<b[0]; //区间左边界小,则排在前 } int main() //即求所有区间的并集 { int L,m; while(scanf("%d %d",&L,&m)!=EOF) { vector<vector<int> >nums(m,vector<int>(2)); //存储区间 for(int i=0;i<m;i++) scanf("%d %d",&nums[i][0],&nums[i][1]); sort(nums.begin(),nums.end(),cmp); //排序 int sum=0,left=1,right=0; for(int i=0;i<nums.size();i++) //类似于合并区间 { if(nums[i][0]>right) //前后区间不相交 { sum+=right-left+1; //加上前面的累积 left=nums[i][0]; right=nums[i][1]; //更新 } else right=max(right,nums[i][1]); } sum+=right-left+1; //共有sum树被移走 int res=L-sum+1; printf("%d\n",res); } }
#include<stdio.h>//初始化有树的位置为-1 无树的位置为0, 计算-1的个数及树木的个数 int main() { int n,m,a,b,i,j,tree[10000],num=0; scanf("%d%d",&n,&m); //初始化,注意用memset初始化时只可以初始化为0或者-1 并且别忘记本题的长度为L+1 memset(tree, -1, sizeof(int) * (n+1)); for(i=1;i<=m;i++)//减去树木 { scanf("%d%d",&a,&b); for(j=a;j<=b;j++) tree[j]=0; } for(i=0;i<=n;i++)//计算剩余树木 if(tree[i]==-1) num++; printf("%d",num); }
#include<iostream> using namespace std; int main(){ int a[10001]; int L,M; while(cin>>L>>M){ for(int i=0;i<=L;i++){ a[i]=1; } int begin[100],end[100]; for(int i=0;i<M;i++){ cin>>begin[i]>>end[i]; } for(int i=0;i<M;i++){ for(int j=begin[i];j<=end[i];j++){ a[j]=0; } } int sum=0; for(int i=0;i<=L;i++){ if(a[i]==1){ sum++; } } cout<<sum<<endl; } return 0; }
#include <bits/stdc++.h> using namespace std; int has[10005]; int main(){ int n,m; while(cin>>m>>n){ memset(has,0,sizeof has); for(int i=0;i<n;i++){ int a,b; cin>>a>>b; has[a]++,has[b+1]--; } int ans=0; for(int i=1;i<=m;i++) { has[i]+=has[i-1]; if(has[i-1]==0) ans++; } if(has[m]==0) ans++; cout<<ans<<endl; } return 0; }
#include <math.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
int L,M,t1,t2,*a;
while(scanf("%d%d",&L,&M)){
a = (int *)malloc(sizeof(int)*(L+1));
for(int i=0;i<=L;a[i++]=0);
for(int i=0;i<M;i++){
scanf("%d%d",&t1,&t2);
for(;t1<=t2;a[t1++]=1);
}
int count = 0;
for(int i=0;i<=L;i++){
if(!a[i]){
count++;
}
}
printf("%d\n",count);
}
return 0;
}
我想知道这段代码哪里错了,为什么一直报超出了限制的内存?
#include <iostream> #include <string> #include <vector> #include <map> #include <queue> #include <stack> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> //rand ( ), srand ( ) #include <ctime> //time ( ) using namespace std; char arr[10001]; int main ( ) { int L, M, a, b; while ( cin >> L >> M ) { memset ( arr, 1, sizeof ( arr ) ); while ( M -- ) { cin >> a >> b; memset ( arr + a, 0, b - a + 1 ); } int ans = 0; for ( int i = 0; i <= L; i ++ ) { if ( arr[i] ) ans ++; } cout << ans << endl; } return 0; }
这道题基本用一个数组就行了,大家代码都一样。
我来分享一个我踩到的坑,我的代码一开始是这样的:
int road[10001]; int main() { while (cin >> L >> M) { memset(road, 1, sizeof(int) * L); //.... } }
之前也有用过 memset
,没想到这次居然踩到坑了,这个代码运行是不成功的,因为 memset(road, 1, sizeof(int) * L);
并不会把 arr
数组变成 1。我在查看时发现所有的元素都变成了 16843009
!
这***的就很见鬼了,我一开始还以为是系统的 bug 后来查了一下资料才发现是我对 memset
理解的错误。
memset(数组名, 值, sizeof(数组名));
因为memset是按字节赋值,对每个字节赋值同样的值,这样int四个字节会附相同的值(这也是它为什么是在 cstring
里的原因)。而0二进制代码全为0,不容易错。
那么赋值为 1 时呢?你看啊,一个 int
四个四节,每个字节变成 1,那就是:
00000001 00000001 00000001 00000001
转换成10进制也就是16843009。
以后用 memset
的时候就要注意了,一般拿它来置零就行了,要想赋值为别的值,就用 algorithm
里的 fill
吧。
void fill (ForwardIterator first, ForwardIterator last, const T& val);
当然这个会稍微慢一点。
#include<iostream> #include<vector> using namespace std; int main() { int L, M; while (cin >> L >> M) { vector<int> data(L + 1, 1); int start, end, cnt = 0; for (int i = 0; i < M; i++) { cin >> start >> end; for (int i = start; i <= end; i++) data[i] = 0; } for (vector<int>::iterator it = data.begin(); it != data.end(); it++) if (*it == 1) cnt++; cout << cnt << endl; } return 0; }
#include<iostream> #include<vector> #include<string> #include<stdio.h> #include<queue> #include<algorithm> using namespace std; class tree{ public: int left,right; bool operator < (const tree &b){ return left<b.left; } }; int main(){ int n,m; while(cin>>n>>m){ vector<tree> v(m); for(int i=0;i<m;++i) cin>>v[i].left>>v[i].right; sort(v.begin(),v.end()); int cnt=n+1; int last=0; for(int i=0;i<m;++i) if(v[i].left>=last){ cnt-=v[i].right-v[i].left+(v[i].left!=last); last=v[i].right; } else{ if(v[i].right>last){ cnt-=v[i].right-last; last=v[i].right; } } cout<<cnt<<endl; } }
#include<iostream> using namespace std; int main() { int l, m; cin >> l >> m; int a[100][2]; int* tree=new int[l+1]; for (int i = 0; i<m; i++) { cin >> a[i][0] >> a[i][1]; } int count = 0; for (int i = 0; i<=l; i++) tree[i]=1; for (int i = 0; i<m; i++){ for(int j=a[i][0];j<=a[i][1];j++){ tree[j]=0; } } int total = 0; for (int i = 0; i<=l; i++) { if(tree[i]!=0) total++; } cout << total << endl; }
用了散列的想法,其实和讨论中其他人的思想差不多,比如我只是没有用meset函数去赋值。也是 每次输入区间的时候就开始计算砍的树木,看过了就吧hash数组里面的0改为1标记一下,下次再遇到 重复区间,就不用再计数了,我自己觉得有个缺点就是,每次我都必须遍历区间里面的每一个点, 很浪费时间。(2019考研复试一定要上岸!) #include<stdio.h>
int main()
{
int L,m;
while(scanf("%d",&L)!=EOF)
{
scanf("%d",&m);
int hashTable[10000]={0};
int a[10000][2],i,j;
int sum=0;
for(i=0;i<m;++i)
{
scanf("%d%d",&a[i][0],&a[i][1]);
for(j=a[i][0];j<=a[i][1];++j)
{
if(hashTable[j]!=1)
{
sum++;
hashTable[j]=1;
}
}
}
printf("%d\n",L-sum+1);
}
return 0;
}
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int l = scanner.nextInt(); int m = scanner.nextInt(); int[] record = new int[l + 1]; for (int i = 0; i < m; i++) { int x = scanner.nextInt(); int y = scanner.nextInt(); for (int j = x; j <=y ; j++) { record[j]=1; } } int count=0; for (int i = 0; i <= l; i++) { if (record[i]==0) count++; } System.out.println(count); } }
#include<iostream> #include<cstring> using namespace std; int T[10001] = { 0 };//用数组储存 int fun1(int L) { for (int i = 0; i <= L; i++) { T[i] = 1; } return 0; //L区间内的树置为1 } int fun2(int m) { int n1, n2; for (int i = 0; i < m; i++) { cin >> n1 >> n2; for (int i = n1; i <= n2; i++) { T[i] = 0; } } return 0; //拔掉的m个区间内的树置为0 } int main() { int sum = 0; int L; int m; while (cin >> L >> m) { fun1(L); fun2(m); for (int i = 0; i <= L; i++) { sum += T[i]; } cout << sum << endl; sum = 0;//注意输出完成后将结果再次置0 } }
#include<iostream> #include<cstdio> using namespace std; const int Maximum = 10001; bool road[Maximum]; int main(){ int length,CaseNum; scanf("%d%d",&length,&CaseNum); for(int i=0; i<=length; i++){ road[i] = true; } int number = length+1; while(CaseNum--){ int left,right; scanf("%d%d",&left,&right); for(int j=left; j<=right; j++){ if(road[j]){ road[j] = false; number--; } } } printf("%d\n",number); return 0; }