HDU 5719 Arrange - dblank

HDU 5719 Arrange

Problem Description
Accidentally, Cupid, god of desire has hurt himself with his own dart and fallen in love with Psyche.

This has drawn the fury of his mother, Venus. The goddess then throws before Psyche a great mass of mixed crops.

There are n heaps of crops in total, numbered from 1 to n.

Psyche needs to arrange them in a certain order, assume crops on the i-th position is Ai.

She is given some information about the final order of the crops:

  1. the minimum value of A1,A2,...,Ai is Bi.
  2. the maximum value of A1,A2,...,Ai is Ci.

She wants to know the number of valid permutations. As this number can be large, output it modulo 998244353.

Note that if there is no valid permutation, the answer is 0.

Input
The first line of input contains an integer T (1≤T≤15), which denotes the number of testcases.

For each test case, the first line of input contains single integer n (1≤n≤105).

The second line contains n integers, the i-th integer denotes Bi (1≤Bi≤n).

The third line contains n integers, the i-th integer denotes Ci (1≤Ci≤n).

Output
For each testcase, print the number of valid permutations modulo 998244353.

Sample Input

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

Sample Output
1
0

题意:有n个木棍,让你选择一个范围在[l,r]间的长度,这个长度不会和这n个中的任意两个构成三角形,问你这样的长度有多少。

思路:根据三角形边的关系,对于两个长度a, b(a>=b), c的范围在(a-b, a+b), 如果我们找到一个对于a的最大范围的b,就包含了所有包含a的情况,就是排序完的line[i]和line[i-1],然后我们可以得到一个区间[line[i] - line[i-1] + 1, line[i] + line[i-1] - 1]这个区间内的长度是不合法的,然后我们要找到总的合法区间,根据这个区间的端点排序,然后直接过一遍,统计答案就可以了。

#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<iostream>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e5 + 10, Mod = 998244353;
typedef long long ll;
using namespace std;
ll a[N];
struct node
{
    ll l, r;
    bool operator < (const node &P) const
    {
        return l<P.l || (l == P.l && r < P.r);
    }
    node() {}
    node(ll _l, ll _r)
    {
        l = _l;
        r = _r;
    }
} p[N];
int main()
{
    int n;
    ll l, r;
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%d%I64d%I64d", &n, &l, &r);
        for(int i = 1; i <= n; i++)
            scanf("%I64d", &a[i]);
        sort(a+1, a+1+n);
        int k = 0;
        for(int i = 1; i<n; i++)
        {
            ll minx = max(a[i+1] - a[i]+1, l);
            ll maxx = min(r, a[i+1] + a[i]-1);
            if(maxx>=minx)
                p[++k] = node(minx, maxx);
        }
        sort(p+1, p+1+k);
        ll ans = 0, last = l-1;
        for(int i = 1; i<=k; i++)
        {
            if(p[i].l > last+1)
            {
                ans += p[i].l - last - 1;
            }
            if(last < p[i].r)
                last = p[i].r;
        }
        printf("%I64dn", ans+r-last);
    }
    return 0;
}

 

 

相关文章

发表新评论