1002 Boss Rush

题目链接
官方题解:

#include
#define ll long long
using namespace std;

int n;
ll h;
ll t[20],d[20];
ll dmg[20][100010];
ll sum[(1<<18)+5];
ll f[(1<<18)+5];

void up(ll& a,ll b)
{
    a<b?(a=b):0;
}

bool check(ll x)
{
    for(int i=0;i<(1<<n);i++)f[i]=-1;
    f[0]=0;
    for(int i=0;i<(1<<n);i++)
    {
        if(f[i]<0)continue;
        if(f[i]>=h)return 1;
        int ti=sum[i];
        if(ti>x)continue;
        for(int j=1;j<=n;j++)
        {
            if(((i>>(j-1))&1))continue;
            if(ti+d[j]-1<=x)
                up(f[i|(1<<(j-1))],f[i]+dmg[j][d[j]]);
            else
                up(f[i|(1<<(j-1))],f[i]+dmg[j][x-ti+1]);
        }
    }
    return 0;
}

void solve()
{
    cin>>n>>h;
    ll sum0=0;
    ll r=0;

    for(int i=1;i<=n;i++)
    {
        cin>>t[i]>>d[i];
        r=r+max(t[i],d[i]);
        for(int j=1;j<=d[i];j++)
        {
            cin>>dmg[i][j];
            sum0+=dmg[i][j];
            dmg[i][j]+=dmg[i][j-1];
        }
    }
    if(sum0<h)
    {
        cout<<"-1\n";
        return ;
    }
    for(int i=1;i<(1<<n);i++)
        sum[i]=sum[i-(i&-i)]+t[__builtin_ctz(i&-i)+1];
        //__builtin_ctz() 返回后面的0的个数

    ll l=0;
    while(l<r)
    {
        ll mid=l+(r-l)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l<<"\n";
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

1003 Cyber Language

题目链接

官方题解:

1008 Laser Alarm

题目链接.
题意：给出空间上的$n$条线段，求某个平面与线段相交的最大线段数量。

官方题解:

思路：不共线的三点$A,B,C$确定一个平面，求出平面的法线量$\overrightarrow{AP}$.
若线段$MN$与平面$ABC$相交则$(\overrightarrow{AP}\cdot \overrightarrow{AN})\ast (\overrightarrow{AP}\cdot \overrightarrow{AM})<=0$。
$\overrightarrow{AP}=\overrightarrow{AB}\times \overrightarrow{AC}$
若$\overrightarrow{AB}=(x_1,y_1,z_1),\overrightarrow{AC}=(x_2,y_2,z_2),\overrightarrow{AP}=(x_3,y_3,z_3)$,
则：
$x_3=y_1{z}_2-y_2{z}_1$
$y_3=z_1{x}_2-z_2{x}_1$
$z_3=x_1{y}_2-x_2{y}_1$
所以枚举三个点和所有线段即可得到答案。
点和向量都可以用$(x,y,z)$的方式表示。

#include
#define ll long long
using namespace std;

int n;
struct point
{
    int x,y,z;
}p[105];

//两个点相减求向量或两个向量相减
point jian(point a,point b)
{
    point c;
    c.x=a.x-b.x;
    c.y=a.y-b.y;
    c.z=a.z-b.z;
    return c;
}

//已知向量ab,求a与b的叉积
point chaji(point a,point b)
{
    point c;
    c.x=a.y*b.z-b.y*a.z;
    c.y=a.z*b.x-b.z*a.x;
    c.z=a.x*b.y-b.x*a.y;
    return c;
}
//已知点abc,求平面法向量
point chaji(point a,point b,point c)
{
    point x=jian(b,a);
    point y=jian(c,a);
    return chaji(x,y);
}

//向量点积
int dianji(point a,point b)
{
    return a.x*b.x+a.y*b.y+a.z*b.z;
}

void solve()
{
    cin>>n;
    for(int i=1;i<=n+n;i++)
        cin>>p[i].x>>p[i].y>>p[i].z;

    int ans=0;

    for(int i=1;i<=n*2;i++)
    {
        for(int j=i+1;j<=n*2;j++)
        {
            for(int k=j+1;k<=n*2;k++)
            {
                int res=0;
                //平面法向量
                point pa=chaji(p[i],p[j],p[k]);
                
                //三点共线，法向量为0.
                if(pa.x==0&&pa.y==0&&pa.z==0)continue;
                for(int v=1;v<=n*2;v+=2)
                {
                    point a=jian(p[v],p[i]);
                    point b=jian(p[v+1],p[i]);
                    if((ll)dianji(a,pa)*dianji(b,pa)<=0)res++;
                }
                ans=max(ans,res);
            }
        }
    }
    //特判所有线段都共线
    if(!ans)ans=n;
    
    cout<<ans<<"\n";
}


int main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve();

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

1009 Package Delivery

题目链接.
官方题解:

思路：按照$l$从小到大排序，优先队列维护$r$的最小值，若当前$l<=r_{min}$直接入队，否则进行出队操作直到$l<=r_{min}$.

#include
#define ll long long
using namespace std;
ll mod=1000000007;

int n,k;

struct node
{
    int l,r;
    bool operator>(const node& a) const
    {
        return r > a.r;
    }

}a[100010];



bool cmp1(node a,node b)
{
    if(a.r==b.r)return a.l<b.l;
    else return a.r<b.r;
}

bool cmp2(node a,node b)
{
    if(a.l==b.l)return a.r<b.r;
    else return a.l<b.l;
}


void solve()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r;
    if(k==1)
    {
        cout<<n<<"\n";
        return ;
    }
    sort(a+1,a+1+n,cmp2);
    priority_queue<node,vector<node>,greater<node>>q;
    int ans=0;
    q.push(a[1]);
    for(int i=2;i<=n;i++)
    {
        if(a[i].l<=q.top().r)q.push(a[i]);
        else
        {
                while(q.size()>=k&&a[i].l>q.top().r)
                {
                    ans++;
                    int x=k;
                    while(x--)q.pop();
                }
                if(q.size()&&a[i].l>q.top().r)
                {
                    while(q.size())q.pop();
                    ans++;
                    q.push(a[i]);
                }
                else q.push(a[i]);
        }
    }
    if(q.size())
    {
        ans+=q.size()/k;
        if(q.size()%k!=0)ans++;
    }
    cout<<ans<<"\n";
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int t;cin>>t;
    while(t--)solve();

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

1011 Taxi

题目链接.
题意：有$n$个点，给出其坐标$(x_i,y_i)$和价值$w_i$。有$q$组询问，每组询问给出一个坐标$(x,y)$，求$max(min(|x-x_1|+|y-y_1|,w_1),min(|x-x_2|+|y-y_2|,w_2),...,min(|x-x_n|+|y-y_n|,w_n))$。

官方题解：

所谓的迭代缩小区间就是二分。

#include
#define ll long long
using namespace std;

const int N=100010;

int n,q;
struct node
{
    int w,a,b,c,d;
}p[N];
int x,y;
int ans=0;

bool cmp(node a,node b)
{
    return a.w<b.w;
}

int getmaxn(int mid,int x,int y)
{
    int maxn=0;
    maxn=max(maxn,p[mid].a+(-x-y));
    maxn=max(maxn,p[mid].b+(x-y));
    maxn=max(maxn,p[mid].c+(-x+y));
    maxn=max(maxn,p[mid].d+(x+y));
    return maxn;
}

bool check(int mid,int x,int y)
{
    ans=max(ans,min(p[mid].w,getmaxn(mid,x,y)));
    return p[mid].w>getmaxn(mid,x,y);
}

void solve()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        int w,x,y;cin>>x>>y>>w;
        p[i].w=w;
        p[i].a=x+y;
        p[i].b=-x+y;
        p[i].c=x-y;
        p[i].d=-x-y;
    }
    sort(p+1,p+1+n,cmp);
    for(int i=n-1;i>=1;i--)
    {
        p[i].a=max(p[i].a,p[i+1].a);
        p[i].b=max(p[i].b,p[i+1].b);
        p[i].c=max(p[i].c,p[i+1].c);
        p[i].d=max(p[i].d,p[i+1].d);
    }
    while(q--)
    {
        cin>>x>>y;
        ans=0;
        int l=1,r=n;
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(check(mid,x,y))r=mid;
            else l=mid+1;

        }
        check(l,x,y);
        cout<<ans<<"\n";
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int t;cin>>t;
    while(t--)solve();

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

1012 Two Permutations

题目链接.
官方题解

我还是觉得按照队友的思路写的代码比较清晰，如下。

#include
#define ll long long
using namespace std;
ll mod=998244353;
int n;
int a[3000010];
int b[3000010];
int pa[3000010];
int pb[3000010];
int s[3000010];
ll dp[3000010*2][2];

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],pa[a[i]]=i;
    for(int i=1;i<=n;i++)cin>>b[i],pb[b[i]]=i;
    for(int i=1;i<=n*2;i++)cin>>s[i],dp[i][0]=dp[i][1]=0;
    if(a[1]==s[1])dp[1][0]=1;
    if(b[1]==s[1])dp[1][1]=1;
    for(int i=2;i<=n*2;i++)
    {
        if(pa[s[i]]==pa[s[i-1]]+1)
            dp[i][0]=(dp[i][0]+dp[i-1][0])%mod;
        if(pa[s[i]]+pb[s[i-1]]==i)
            dp[i][0]=(dp[i][0]+dp[i-1][1])%mod;
        if(pb[s[i]]==pb[s[i-1]]+1)
            dp[i][1]=(dp[i][1]+dp[i-1][1])%mod;
        if(pb[s[i]]+pa[s[i-1]]==i)
            dp[i][1]=(dp[i][1]+dp[i-1][0])%mod;
    }
    cout<<(dp[n*2][0]+dp[n*2][1])%mod<<"\n";
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int t;cin>>t;
    while(t--)solve();

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45