QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#227542#1286. Ternary String CountingRickyRE 5ms3912kbC++142.6kb2023-10-27 17:49:312023-10-27 17:49:32

Judging History

你现在查看的是最新测评结果

  • [2023-10-27 17:49:32]
  • 评测
  • 测评结果:RE
  • 用时:5ms
  • 内存:3912kb
  • [2023-10-27 17:49:31]
  • 提交

answer

#include<iostream>
#include<set>
#include<map>
#include<time.h>
#include<random>
#include<vector>
#include<iomanip>
#include<string.h>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;
//#pragma optimize(2)
#define fi first
#define se second
#define ll long long
#define ull unsigned ll
#define str string
#define db double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue
#define pqMax(x) pq< x >
#define pqMin(x) pq< x ,vector< x >,greater< x > >
#define MP make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define lowbit(x) ((x)&(-(x)))
#define sz(x) ((int) (x).size())
#define ms(a,t) memset(a,t,sizeof(a))
#define FORe(i, u, v) for (int i = h[u], v; v = e[i].to, i; i = e[i].nxt)
const ll INF = 0x3f3f3f3f;
const int maxn = 100+10;
const int maxm = 1e6+10;
const ll mod = 1e9+7;
const db eps = 1e-6;
//ll read() {
//	ll x=0,f=1;char ch=getchar();
//	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
//	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
//	return x*f;
//}
int n,m;
int l[maxn],r[maxn],v[maxn];
int p[maxn][4],q[maxn][4];
int f[maxn][maxn][maxn];
void Solve() {
	cin >> n >> m;
	for(int i = 0; i <= n; i++) p[i][1] = p[i][2] = p[i][3] = i+1;
	for(int i = 1; i <= n; i++) q[i][1] = q[i][2] = q[i][3] = 0;
	for(int i = 1; i <= m; i++) {
		cin >> l[i] >> r[i] >> v[i];
		p[r[i]][v[i]] = min(p[r[i]][v[i]],l[i]);
		q[r[i]][v[i]] = max(q[r[i]][v[i]],l[i]);
	}
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= n; j++) {
			for(int k = 0; k <= n; k++) {
				f[i][j][k] = 0;
			}
		}
	}
	f[0][0][0] = 1;
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= n; j++) {
			for(int k = 0; k <= n; k++) {
				if(j >= p[i][1] || k >= p[i][2] || j < q[i][2] || k < q[i][3]) {
					f[i][j][k] = 0;
					continue;
				}
				f[i+1][j][k] = (f[i+1][j][k] + f[i][j][k]) % mod;
				f[i+1][i][k] = (f[i+1][i][k] + f[i][j][k]) % mod;
				f[i+1][i][j] = (f[i+1][i][j] + f[i][j][k]) % mod;
			}
		}
	}
	/*
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= n; j++) {
			for(int k = 0; k <= n; k++)
				cout<<f[i][j][k]<<' ';
			cout<<'\n';
		}
		cout<<'\n';
	}
	*/
	ll sum = 0;
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= n; j++) {
			sum = (sum + f[n][i][j]) % mod;
		}
	}
	cout<<sum<<'\n';
}
int main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
//	ios::sync_with_stdio(0);
//	cin.tie(0); cout.tie(0);
	int tt; cin >> tt ; while(tt--)
	Solve();
	return 0;
}
/*
调试先查四件事
1. 数组开够没
2. ijk写错没
3. int爆了没
4. double取等了没
*/


详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3728kb

input:

4
1 0
2 0
3 0
5 2
1 3 3
4 5 1

output:

3
9
27
18

result:

ok 4 tokens

Test #2:

score: 0
Accepted
time: 3ms
memory: 3720kb

input:

741
5 3
1 5 3
3 4 2
1 4 3
4 3
2 4 2
1 4 1
2 3 3
10 3
9 10 2
3 6 3
1 9 1
3 4
2 3 2
1 3 2
2 3 3
1 3 3
10 4
6 6 1
9 10 2
4 8 3
4 10 3
6 3
1 4 3
2 4 2
2 2 2
4 3
1 4 1
1 1 2
2 3 1
5 3
4 5 2
4 5 1
1 4 3
9 3
2 3 2
1 9 2
2 4 2
4 3
1 3 3
2 3 2
1 2 3
8 4
5 8 1
4 8 1
3 5 3
1 3 3
9 3
4 5 1
1 5 3
3 8 2
8 3
5 7 2...

output:

90
0
0
0
24300
0
0
0
768
0
0
972
2916
0
6480
864
0
0
0
0
0
0
0
0
6
0
0
0
0
0
96
0
6
0
0
0
0
0
0
0
108
0
0
0
2916
0
0
0
0
0
0
0
0
0
0
324
8748
0
0
0
0
0
0
4320
0
0
0
18
0
0
0
0
0
0
0
0
0
0
0
1992
0
0
450
0
162
1656
0
0
0
0
0
54
0
18
0
0
0
0
744
0
1620
324
0
0
36
36
0
0
60
6
54
0
0
0
0
0
0
0
0
243
810...

result:

ok 741 tokens

Test #3:

score: 0
Accepted
time: 5ms
memory: 3912kb

input:

332
17 5
4 9 1
4 6 1
7 17 1
5 5 1
5 6 3
13 5
10 12 3
8 13 2
1 10 3
2 9 1
9 10 1
19 5
11 13 1
9 17 2
1 7 1
4 4 2
3 9 1
15 4
8 11 2
9 14 3
10 12 2
4 5 2
12 4
3 9 2
7 8 1
1 7 3
6 7 3
16 5
4 14 3
1 5 1
2 10 1
2 12 3
6 9 3
20 4
10 17 3
4 20 3
17 19 3
8 17 1
20 5
11 11 1
9 13 1
1 5 3
17 17 3
3 18 3
17 5
1...

output:

0
0
0
2047032
0
0
0
0
0
839808
0
0
0
0
0
0
0
0
0
0
0
0
44641044
0
20412
0
0
0
0
0
0
0
6
0
0
0
0
81
0
0
0
0
0
0
0
0
0
0
0
313155072
0
0
0
0
0
0
0
0
0
5400
0
10368
0
0
0
0
14580
0
0
0
217728
40310784
0
0
218700
0
0
0
0
1620
0
0
0
0
0
108
146304
0
0
0
466560
288
0
0
0
0
0
0
0
276138
0
0
0
0
0
0
0
52488...

result:

ok 332 tokens

Test #4:

score: -100
Runtime Error

input:

5
1000 0
1000 5
779 779 2
543 840 3
30 477 1
10 295 3
463 741 1
1000 6
379 569 1
249 826 2
194 819 3
90 400 1
614 808 2
102 868 2
1000 8
463 981 1
680 857 3
560 623 1
209 659 1
55 957 2
244 327 1
321 888 3
37 204 3
1000 5
336 851 3
410 676 1
522 911 2
165 962 1
258 330 3

output:


result: