True/FalseWorksheet

NC223711. True/FalseWorksheet

描述

Bob is completing a true/false worksheet, consisting of a list of n problems where each answer is either “true” or “false”. The problems are numbered from 1 to n. They are too hard for Bob, so the TA, Alice, has given Bob m hints. For each hint i, Alice gives Bob an (inclusive) range of questions [l_i , r_i ], and tells him either “all answers in the range are the same” (in other words, either all are “true”, or all are “false”); or “not all of the answers in the range are the same.” Help Bob count how many different answer sequences satisfy the given hints. Since this number may be huge, print the answer modulo 10⁹ + 7.

输入描述

The first line of the input contains two space-separated integers n and m (1 ≤ n ≤5 000, 1 ≤ m ≤ 1 000 000), the number of problems and number of hints, respectively.The next m lines each encode a hint, and contain two space-separated integers l_iand r_i (1 ≤ l_i ≤ r_i ≤ n) followedby either the word same, if all answers in the range are the same, or different, if all answers in the range are notthe same (i.e., at least one answer is “true” and at least one other answer is “false”).

输出描述

Print the number of different answer sequences satisfying all the hints, modulo 10⁹ + 7.

示例1

输入:

5 2
2 4 same
3 5 same

输出:

示例2

输入:

5 3
1 3 same
2 5 same
1 5 different

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 261ms, 内存消耗: 476K, 提交时间: 2021-08-24 11:16:07

#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 5010
#define mod 1000000007
using namespace std;
int n,m,same[maxn],different[maxn],f[maxn];
char s[maxn];
signed main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) same[i]=i;
	for(int i=1,l,r;i<=m;i++){
		scanf("%d %d %s",&l,&r,s);
		if(s[0]=='s') same[r]=min(same[r],l);
		else different[r]=max(different[r],l);
	}
	f[0]=2;
	for(int i=1;i<=n;i++){
		int Max=-mod,Min=mod;
		for(int j=i;j;j--){
			Max=max(Max,different[j]); Min=min(Min,same[j]);
			if(Min>=j && j>Max) f[i]=(f[i]+f[j-1])%mod;
		}
	}
	printf("%d\n",f[n]%mod);
	return 0;
}

上一题

下一题

详情