2022“杭电杯”中国大学生算法设计超级联赛（3）

1002 Boss Rush

直接二分答案，考虑如何求出$t$时刻内的最大伤害

设$f_S$表示状态为$S$的情况下，在当前二分的时间下造成的伤害最多是多少即可

#include
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int maxs=(1<<18)+5;
int n,t[20],len[20];
ll H,d[20][maxn],sumT[maxs];
int lowbit(int x)
{
    return x&(-x);
}
ll f[maxs];
bool check(ll x)
{
    for(int s=0;s<(1<=H) return true;
        ll nowT=sumT[s];
        if(nowT>x) continue;
        for(int i=0;i>i&1))
            {
                if(nowT+len[i]-1<=x)
                    f[s|(1<>1;
            if(check(mid))
                r=mid-1,ans=mid;
            else l=mid+1;
        }
        printf("%lld\n",ans);
    }
    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

1003 Cyber Language

如果一个字符是小写的且是第一个或者前面是空格就转大写输出

#include
using namespace std;
typedef long long ll;
string s;
int main()
{
    int T; scanf("%d",&T);
    getline(cin,s);
    while(T--)
    {
        getline(cin,s);
        int l=s.length();
        for(int i=0;i='a' && s[i]<='z' && (i==0 || s[i-1]==' '))
                printf("%c",'A'+s[i]-'a');
        printf("\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1005 Spanning Tree Game

若$a<b$，拆成$(u,v,a,1),(u,v,w,0)$

若$b\le a$，拆成$(u,v,b,-1),(u,v,w,0)$

这样拆是因为我们每次肯定会尽量把选择一个的步骤花在能使边权变小的边上

然后我们把这样的边按照边权排序，边权相同的按照最后一个维绝对值从大到小

这样我们就能保证如果遇到了最后一维非0的边，选择了就要花费一个次数，也可以不选

如果遇到的最后一维为0的边，如果对应的非0没选，就一定要选，这里如果非0的选了，$u,v$就已经被加入同一个集合，所以很好考虑

我们记录dp，设$f[i][j][k]$表示前$i$条边，点的并查集为$j$，花费了$k$个a的情况

这样我们就容易转移了，$j$可以把n个四位二进制数压到一起即可

时间复杂度$O(m^{2}st),st=Bell(n)$

#include
using namespace std;
typedef long long ll;
int n,m;
int f[10],tot;
ll rev[25000];
unordered_map  G;
void init(int step,int mx)
{
    if(step>n)
    {
        ll now=0;
        for(int i=1;i<=n;i++)
            now=now<<4|f[i];
        G[now]=++tot; rev[tot]=now;
        return;
    }
    for(int i=1;i<=mx+1;i++)
    {
        f[step]=i;
        init(step+1,max(mx,i));
    }
}
struct edge
{
    int u,v,w,id;
}e[70];
int cnt;
bool cmp(edge x,edge y)
{
    if(x.w!=y.w) return x.w>=4;
                int st=j,val=f[u]==f[v]?0:w;
                if(f[u]!=f[v])
                {
                    int fu=f[u],fv=f[v];
                    for(int k=1;k<=n;k++)
                        if(f[k]==fu) f[k]=fv;
                    int num=0;
                    for(int k=1;k<=n;k++) bh[k]=0;
                    for(int k=1;k<=n;k++)
                        if(!bh[f[k]]) bh[f[k]]=++num;
                    now=0;
                    for(int k=1;k<=n;k++)
                        now=now<<4|bh[f[k]];
                    st=G[now];
                }
                if(!id)
                {
                    for(int k=0;k<=m;k++)
                        if(g[p][j][k]!=-1)
                            g[p^1][st][k]=max(g[p^1][st][k],g[p][j][k]+val);
                }
                else
                {
                    // not included
                    for(int k=0;k<=m;k++)
                        if(g[p][j][k]!=-1)
                            g[p^1][j][k]=max(g[p^1][j][k],g[p][j][k]);
                    // included
                    for(int k=0;k<=m;k++)
                        if(g[p][j][k]!=-1)
                            g[p^1][st][k+id]=max(g[p^1][st][k+id],g[p][j][k]+val);
                }
            }
            p^=1;
            for(int i=1;i<=tot;i++)
                for(int j=0;j<=m;j++)
                    g[p^1][i][j]=-1;
        }
        for(int i=0;i<=m;i++)
            printf("%d\n",g[p][1][i]);
    }
    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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

1006 Dusk Moon

首先，一堆点的最小圆覆盖等价于其凸包的最小圆覆盖，所以我们可以用线段树维护区间的凸包，然后利用最小覆盖圆的算法计算即可

题解中提到随机选点的凸包点的个数期望是$O(\log n)$

这篇论文中好像证明了是$O(n^{\frac{1}{3}})$

总之就是$O(能过)$

double精度好像不够，需要long double

#pragma GCC optimize(3)
#include
using namespace std;
typedef long long ll;
typedef long double db;
const double eps=1e-10;
const int maxn=1e5+5;
const int gs=50; 
struct point
{
    int x,y;
}a[maxn];
int n,m;
int Up[gs],Dw[gs],CC[gs];
int tup[maxn<<2][gs],tdw[maxn<<2][gs];
#define lson now<<1
#define rson now<<1|1
bool cmp_up(int x,int y)
{
    if(a[x].x==a[y].x) return a[x].y>a[y].y;
    return a[x].x1 && 1ll*(a[st[top]].y-a[st[top-1]].y)*(u.x-a[st[top]].x)<=1ll*(u.y-a[st[top]].y)*(a[st[top]].x-a[st[top-1]].x))
            top--;
        st[++top]=CC[i];
    }
    for(int i=1;i<=top;i++)
        C[i-1]=st[i];
    C[top]=0;
    // printf("%d\n",top);
}
bool cmp_dw(int x,int y)
{
    if(a[x].x==a[y].x) return a[x].y1 && 1ll*(a[st[top]].y-a[st[top-1]].y)*(u.x-a[st[top]].x)>=1ll*(u.y-a[st[top]].y)*(a[st[top]].x-a[st[top-1]].x))
            top--;
        st[++top]=CC[i];
    }
    for(int i=1;i<=top;i++)
        C[i-1]=st[i];
    C[top]=0;
    // printf("%d\n",top);
}
void pushup(int now)
{
    merge_up(tup[lson],tup[rson],tup[now]);
    merge_dw(tdw[lson],tdw[rson],tdw[now]);
}
void build(int now,int l,int r)
{
    if(l==r)
    {
        tup[now][0]=tdw[now][0]=r;
        tup[now][1]=tdw[now][1]=0;
        return;
    }
    int mid=l+r>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(now);
}
void modify(int now,int l,int r,int pos)
{
    if(l==r) return ;
    int mid=l+r>>1;
    if(pos<=mid) modify(lson,l,mid,pos);
    else modify(rson,mid+1,r,pos);
    pushup(now);
}
void query(int now,int l,int r,int L,int R)
{
    if(l>=L && r<=R)
    {
        merge_up(Up,tup[now],Up);
        merge_dw(Dw,tdw[now],Dw);
        return;
    }
    int mid=l+r>>1;
    if(L<=mid) query(lson,l,mid,L,R);
    if(midR+eps)
    {
        O=b[i]; R=0;
        for(int j=0;jR+eps)
        {
            O=dpoint((b[i].x+b[j].x)/2,(b[i].y+b[j].y)/2);
            R=dis(O,b[i]);
            for(int k=0;kR+eps)
                    O=center(b[k],b[i],b[j]),R=dis(O,b[i]);
        }
    }
    return ceil(R);
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&a[i].x,&a[i].y);
        build(1,1,n);
        // int pos=0;
        // while(tup[1][pos]) printf("%d ",tup[1][pos]),pos++;
        // printf("\n");
        while(m--)
        {
            int opt,x,y; scanf("%d",&opt);
            if(opt==1)
            {
                scanf("%d",&x);
                scanf("%d%d",&a[x].x,&a[x].y);
                modify(1,1,n,x);
            }
            else
            {
                scanf("%d%d",&x,&y);
                Up[0]=Dw[0]=0;
                query(1,1,n,x,y);
                printf("%d\n",calc());
            }
        }
    }
    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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194

1009 Package Delivery

贪心的，我们尽可能在一个快递的$r_i$去取，然后用一个优先级队列维护当前时刻可以被取的，右端点最靠左的$k$个即可

时间复杂度$O(n\log n)$

#include
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
typedef pair PII;
struct point
{
    int l,r,id;
}a[maxn],b[maxn];
int n,k,vis[maxn];
bool cmpl(point x,point y)
{
    return x.l q;
    while(T--)
    {
        scanf("%d%d",&n,&k);
        while(!q.empty()) q.pop();
        for(int i=1;i<=n;i++) vis[i]=0;
        for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i,b[i]=a[i];
        sort(a+1,a+n+1,cmpl); sort(b+1,b+n+1,cmpr);
        int now=0,ans=0;
        for(int i=1;i<=n;i++)
        {
            if(vis[b[i].id]) continue;
            while(now

#include
using namespace std;
typedef long long ll;
typedef pair PII;
const int maxn=5e4+5;
const int inf=0x3f3f3f3f;
bitset  f[maxn],S[650],tmp;
int n,m,q;
int sz,id[maxn];
vector  qu,G[maxn];
int du[maxn],qx[maxn<<1],qy[maxn<<1];
int ql[maxn<<1],qr[maxn<<1],gs;
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&q);
        qu.clear();
        for(int i=1;i<=n;i++) du[i]=0,G[i].clear(),f[i].reset();
        int x,y;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            du[x]++;
            G[y].push_back(make_pair(x,i));
        }
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d%d%d",&qx[i],&qy[i],&ql[i],&qr[i]);
            f[qy[i]][i]=1;
            qu.push_back(make_pair(ql[i],i));
            qu.push_back(make_pair(qr[i]+1,-i));
        }
        sort(qu.begin(),qu.end());
        sz=sqrt(qu.size()); gs=0;
        for(int i=0;i0) S[gs][tmp]=1;
            else S[gs][-tmp]=0;
        }
        queue  Q;
        for(int i=1;i<=n;i++)
            if(!du[i]) Q.push(i);
        while(!Q.empty())
        {
            int u=Q.front(); Q.pop();
            for(auto v:G[u])
            {
                int to=v.first,i=v.second;
                int pos=upper_bound(qu.begin(),qu.end(),make_pair(i,inf))-qu.begin();
                tmp=S[pos/sz];
                for(int j=pos/sz*sz;j0) tmp[temp]=1;
                    else tmp[-temp]=0;
                }
                f[to]|=f[u]&tmp;
                du[to]--;
                if(!du[to]) Q.push(to);
            }
        }
        for(int i=1;i<=q;i++)
        {
            if(f[qx[i]][i])
                printf("YES\n");
            else printf("NO\n");
        }
    }
    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

#include
using namespace std;
typedef long long ll;
const ll inf=1e16;
const int maxn=1e5+5;
struct point
{
    int x,y,w;
}a[maxn],b[maxn],tl[maxn],tr[maxn];
int n,q,ans[maxn];
ll mnx,mxx,mny,mxy;
void solve(int l,int r,int L,int R,int ql,int qr)
{
    if(ql>qr) return;
    if(l==r)
    {
        for(int i=ql;i<=qr;i++)
            ans[b[i].w]=l;
        return;
    }
    int mid=l+r+1>>1;
    int cntl=0,cntr=0;
    for(int i=L;i<=R;i++)
    {
        if(a[i].w=mid) tr[++cntr]=b[i];
        else tl[++cntl]=b[i];
    }
    tmp=ql;
    for(int i=1;i<=cntl;i++) b[tmp++]=tl[i];
    int pos2=tmp-1;
    for(int i=1;i<=cntr;i++) b[tmp++]=tr[i];
    ll tmnx=mnx,tmny=mny,tmxx=mxx,tmxy=mxy;
    mnx=temnx; mny=temny; mxx=temxx; mxy=temxy;
    solve(mid,r,L,pos1,pos2+1,qr);
    mnx=tmnx; mny=tmny; mxx=tmxx; mxy=tmxy;
    solve(l,mid-1,pos1+1,R,ql,pos2);
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&q);
        int x,y,mx=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&x,&y,&a[i].w);
            a[i].x=x+y; a[i].y=x-y;
            mx=max(mx,a[i].w);
        }
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d",&x,&y);
            b[i].x=x+y; b[i].y=x-y;
            b[i].w=i;
        }
        mnx=inf,mxx=-inf,mny=inf,mxy=-inf;
        solve(0,mx,1,n,1,q);
        for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
    }
    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

#include
using namespace std;
typedef long long ll;
const int maxn=6e5+5;
int n,a[maxn],b[maxn],c[maxn];
int posa[maxn],posb[maxn],gs[maxn];
typedef pair PIL;
const ll mod=998244353;
PIL f[2][5];
PIL invalid={-1,-1};
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),posa[a[i]]=i;
        for(int i=1;i<=n;i++) scanf("%d",&b[i]),posb[b[i]]=i,gs[i]=0;
        for(int i=1;i<=2*n;i++) scanf("%d",&c[i]),gs[c[i]]++;
        int flag=0;
        for(int i=1;i<=n;i++) if(gs[i]!=2) flag=1;
        if(flag)
        {
            printf("0\n");
            continue;
        }
        int p=1;
        f[1][0]={1,1}; f[1][1]=invalid;
        f[0][0]=f[0][1]=invalid;
        for(int i=1;i<=2*n;i++)
        {
            int pa=posa[c[i]],pb=posb[c[i]];
            int cnt=-1;
            if(f[p][0].first==pa)
                f[p^1][++cnt]={pa+1,f[p][0].second};
            if(f[p][1].first==pa)
                f[p^1][++cnt]={pa+1,f[p][1].second};
            if(f[p][0]!=invalid && f[p][0].first==i+1-pb)
                f[p^1][++cnt]=f[p][0];
            if(f[p][1]!=invalid && f[p][1].first==i+1-pb)
                f[p^1][++cnt]=f[p][1];
            if(cnt==1 && f[p^1][0].first==f[p^1][1].first)
            {
                f[p^1][0].second+=f[p^1][1].second;
                f[p^1][0].second%=mod;
                f[p^1][1]=invalid;
            }
            p^=1;
            f[p^1][0]=invalid;
            f[p^1][1]=invalid;
        }
        if(f[p][0]!=invalid)
            printf("%lld\n",f[p][0].second);
        else printf("0\n");
    }
    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