题解 P4403 【[BJWC2008]秦腾与教学评估】

· · 题解

【题目描述】

在秦腾进入北京大学学习的第一个学期，就不幸遇到了前所未有的教学评估。

在教学评估期间，同学们被要求八点起床，十一点回宿舍睡觉，不 准旷课，上课不准迟到，上课不准睡觉……甚至连著名的北大三角地也在教学评估期间被以影响校容的理由被拆除。这些“变态”规定令习惯了自由自在随性生活学习的北大同学叫苦不迭。

这一天又到了星期五，一大早就是秦腾最不喜欢的高等代数课。可是因为是教学评估时期，不能迟到，于是他在八点五分的 时候挣扎着爬出了宿舍，希望能赶快混进在八点钟已经上课了的教室。

可是，刚一出宿舍楼门他就傻眼了: 从宿舍到教学楼的路上已经站满了教学评估团的成员。他们的目的就是抓住像他这样迟到的学生，扣除学校的分数。

秦腾当然不能让评估团得逞。他经过观察发现，整个评估团分成了n个小组，每个小组的成员都分布在从宿舍楼到教学楼的路上的某一段，并且同一小组的成员间的距离是相等的。于是，我们可以用三个整数S, E, D来描述评估团的小组: 既该小组的成员在从宿舍到教学楼的路上的：S, S + D, S + 2D, …, S + KD (K \in Z, S + KD ≤ E, S + (K + 1)D > E)位置。

观察到了教学评估团的这一特点，又经过了认真的思考，秦腾想出了对策: 如果在路上的某一位置有奇数个教学评估团成员，他就可以运用调虎离山，声东击西，隔山打牛，暗度陈仓……等方法，以这一地点为突破口到达教学楼。

但是由于 教学评估团的成员的十分狡猾，成员位置安排的设计极其精妙，导致在整条路上几乎没有这样的位置出现。即使由于安排不慎重出现了这样的位置，最多也仅有一个。

现在秦腾观察出了所有小组的安排，但是由于整个教学评估团的人数太多，他实在看不出这样的位置是否存在。

现在，你的任务是写一个程序，帮助他做出判断。

【输入输出格式】

输入文件的第一行为一个整数T。

接下来输入T组相互独立的测试数据。

每组测试数据的第一行包含一个整数，代表n接下来的n行，每行三个整数S_i, E_i, D_i， 代表第i个小组对应的三个参数。

根据题意，Count应为奇数。

【输入输出样例】

教学评估团的总人数不大于10^8。

输入文件的大小不大于2048KB。 【题目大意】 在一条线段上有许多点。这些点可以用$3n$个整数来表示，每行的三个整数分别为$S_i,E_i,D_i$，表示有许多个点在$S, S + D, S + 2D, …, S + KD (K \in Z, S + KD ≤ E, S + (K + 1)D > E)$位置。求在这一条线段上是否有一个点上的点的个数为奇数，保证解最多只有一个，若无解则输出“``Poor QIN Teng:( ``”（不包含引号），否则就输出那个唯一的点个个数以及有多少个点在它的上面，有$T$组相互独立的测试数据，对于每组数据输出一行答案，格式如前所述。 【题解】 - 解法一 我会暴力！ 考虑直接用一个数组来存储每个点上的点的个数，然后暴力扫描即可。若搜不到答案即无解，输出“``Poor QIN Teng:( ``”（不包含引号）即可，但是由于$S_i$以及$E_i$太大，数组的空间不够，因此只能够得到部分的分数，期望得分$0$~$30$，实际得分$20$分。 - 解法二 考虑在解法一的基础上进行改进，用一个函数$calc()$来计算每个点上的点的个数，在这里我用$calc(i)$来表示第$i$个点上的点的个数，但是容易超时，期望得分$0$~$50$分，实际得分$0$分。 - 解法三 我们考虑在解法二的基础上进行优化，我们可以把$calc()$函数的时间复杂度降为$O(n)$，并用$calc(i)$来表示点$1$到点$i$上的点的个数，并且考虑二分。怎么进行二分呢？因为题目中说了答案最多只有一个，所以如果$calc(mid)\;mod\;2=1$那么答案一定小于等于$mid$，否则答案一定大于$mid$。最后的点$l$就是答案（在这里我用$l$来表示当前二分的左边界，并用$r$来表示当前二分的右边界），最后再用$O(n)$的复杂度扫一次有多少个点在点$i$的上面然后按题目要求输出即可，还有一点要注意的是要开$long\;long$哦。期望得分$0$~$100$分，实际得分$100$分，时间复杂度约为$O(T \times n\;log_2\;r)$，其中$r$表示的是最大的$E_i$。 解法一代码~ ``` #include <cstdio> #include <cstring> int a[1000001]; int max(int x,int y) { return x>y?x:y; } int main() { int t=0; scanf("%d",&t); while(t--) { memset(a,0,sizeof(a)); int n=0,r=0; scanf("%d",&n); for(int i=1;i<=n;i++) { int x=0,y=0,z=0; scanf("%d %d %d",&x,&y,&z); for(int j=x;j<=y;j+=z) { a[j]++; } r=max(r,y); } bool flag=false; for(int i=0;i<=r;i++) { if(a[i]%2==1) { flag=true; printf("%d %d\n",i,a[i]); break; } } if(flag==false) { printf("Poor QIN Teng:(\n"); } } return 0; } ``` 解法二代码~ ``` #include <cstdio> #include <cstring> int x[1000001],y[1000001],z[1000001]; int n=0,r=0; int max(int x,int y) { return x>y?x:y; } int calc(int px) { int ans=0; for(int i=1;i<=n;i++) { for(int j=x[i];j<=y[i];j+=z[i]) { if(j==px) { ans++; } } } return ans; } int main() { int t=0; scanf("%d",&t); while(t--) { n=0,r=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d %d %d",&x[i],&y[i],&z[i]); r=max(r,y[i]); } bool flag=false; for(int i=1;i<=r;i++) { int tx=calc(i); if(tx%2==1) { flag=true; printf("%d %d\n",i,tx); break; } } if(flag==false) { printf("Poor QIN Teng:(\n"); } } return 0; } ``` 下面上AC代码~ ``` #include <cstdio> #include <cstring> long long x[1000001],y[1000001],z[1000001]; long long n=0,l=0,r=0; long long min(long long x,long long y) { return x<y?x:y; } long long max(long long x,long long y) { return x>y?x:y; } long long calc(long long d) { long long da=0; for(long long i=1;i<=n;i++) { if(x[i]<=d) { da+=(min(d,y[i])-x[i])/z[i]+1; } } return da; } int main() { long long t=0; scanf("%lld",&t); while(t--) { long long ans=0; l=0,r=0,n=0; scanf("%lld",&n); for(long long i=1;i<=n;i++) { scanf("%lld %lld %lld",&x[i],&y[i],&z[i]); r=max(r,y[i]); } if(calc(r)%2==0) { printf("Poor QIN Teng:(\n"); continue; } while(l<r) { long long mid=(l+r)/2; if(calc(mid)%2==1) { r=mid; } else { l=mid+1; } } for(long long i=1;i<=n;i++) { if(x[i]>l || y[i]<l) { continue; } if((l-x[i])%z[i]==0) { ans++; } } printf("%lld %lld\n",l,ans); } return 0; } ```