ICPC2024昆明 VP

B. 金牌

优先填空，再整块补。

 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


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e2+7, mod=1e9+7;

int n,k,m;
int a[N];

void solve(){
    cin>>n>>k;
    vector<int>lft;
    ll ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ans+=a[i]/k;
        lft.push_back(k-a[i]%k);
    }
    cin>>m;
    sort(lft.begin(),lft.end());
    for(auto x:lft){
        if(m>=x){
            m-=x;
            ans++;
        }
    }
    ans+=m/k;
    cout<<ans<<endl;
}

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

G. 乐观向上

异或和的性质

$$ f(x)=\begin{cases} x, & x\%4=0 \\ 1, & x\%4=1 \\ x+1, & x\%4=2 \\ 0, & x\%4=3 \end{cases} $$

所以如果 $n%4=0 || n=1$ 此时无法构造。

交换 0 和 1，的位置，之后每 4 个交换一次即可。

 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


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

void solve(){
    int n;
    cin>>n;
    if(n==1||n%4==0){
        cout<<"impossible\n";
        return;
    }
    vector<int>a;
    for(int i=0;i<n;i++){
        a.push_back(i);
    }
    swap(a[0],a[1]);
    for(int i=1;i<=n;i++){
        if(i%4==0)swap(a[i-1],a[i]);
    }
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

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

A. 两星级竞赛

啥调题，谁知道卡题点在 QA 里。

暴力模拟即可， $s_i=s_j$ 时，要让当前评分总和小的排前面。

 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


#include <bits/stdc++.h>
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
#define int long long
const int N=1e6+7,mod=1e9+7;

ll n,m,k;
vector<pii>pos;
vector<int>sum(N+10),tmp[N+10];

bool cmp(pii a,pii b){
    if(a.first==b.first){
        return sum[a.second]<sum[b.second];
    }
    return a.first<b.first;
}

void solve()
{
    cin>>n>>m>>k;
    vector<vector<int>>a(n+10,vector<int>(m+10));
    pos.clear();
    for(int i=1;i<=n;i++){
        tmp[i].clear();
        sum[i]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m+1;j++){
            cin>>a[i][j];
            if(j==1){
                pos.push_back({a[i][j],i});
            }
            else{
                if(a[i][j]==-1)tmp[i].push_back(j);
                else sum[i]+=a[i][j];
            }
        }
    }
    sort(pos.begin(),pos.end(),cmp);
    int now=-1,lst=-1;
    for(auto [x,y]:pos){
        if(x==lst)now--;
        int lft=max(0ll,now+1-sum[y]);
        for(auto xx:tmp[y]){
            if(lft>k){
                lft-=k;
                a[y][xx]=k;
                sum[y]+=k;
            }
            else {
                a[y][xx]=lft;
                sum[y]+=lft;
                lft=0;
            }
        }
        if(lft>0){
            cout<<"No\n";
            return;
        }
        now=sum[y];
        lst=x;
    }
    cout<<"Yes\n";
    for(int i=1;i<=n;i++){
        for(int j=2;j<=m+1;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

I. 左移

找到串上所有的连续段，每段贡献为长度除二，如果有偶数长度的段，可以减少一个贡献。

 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


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

void solve(){
    string s;
    cin>>s;
    int n=s.size();
    vector<int>a;
    for(int i=0;i<n;i++){
        if(s[i]==s[(i-1+n)%n])continue;
        int tmp=i;
        int cnt=0;
        while(s[tmp]==s[i]){
            tmp=(tmp+1)%n;
            cnt++;
        }
        a.push_back(cnt);
    }
    int ans=0;
    if(a.empty()){
        ans=n/2;
    }
    else{
        bool flag=0;
        for(auto x:a){
            ans+=x/2;
            if(x%2==0)flag=1;
        }
        if(flag)ans--;
    }
    cout<<ans<<endl;
}

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

E. 学而时习之

由题意可知，答案是三段的 GCD（$a_1…a_{l-1},a_l…a_r,a_{r+1}…a_n$），前后两段可以通过预处理得到，关键在于找到合适的中间段，即操作段。

st 表优化暴力版：

$st_{i,j}$ 表示从 i 开始，长度为 $2^j$ 的片段的 gcd 值。

 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


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=3e5+7, mod=1e9+7;

ll st[N][20],ex[20],lg[N];

void solve(){
    ll n,k;
    cin>>n>>k;
    vector<ll>a(n+10),b(n+10);
    vector<pair<ll,ll>>l,r;
    ll now=0,ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]+k;
        st[i][0]=b[i];
        ll tmp=__gcd(now,a[i]);
        ans=tmp;
        if(tmp==now)continue;
        l.push_back({i-1,now});
        now=tmp;
        
    }
    l.push_back({n,now});
    now=0;
    for(int i=n;i>0;i--){
        ll tmp=__gcd(now,a[i]);
        if(tmp==now)continue;
        r.push_back({i+1,now});
        now=tmp;
    }
    
    r.push_back({1,now});
    for(int j=1;ex[j]<=n;j++){
        for(int i=1;i+ex[j]-1<=n;i++){
            st[i][j]=__gcd(st[i][j-1],st[i+ex[j-1]][j-1]);
        }
    }
    for(auto x:l){
        for(auto y:r){
            ll tl=x.first,tr=y.first;
            if(tr-tl-1<=0)continue;
            ll tmp=__gcd(x.second,y.second);
            ll t=__gcd(st[tl+1][lg[tr-tl-1]],st[tr-1-ex[lg[tr-tl-1]]+1][lg[tr-tl-1]]);
            tmp=__gcd(tmp,t);
            ans=max(ans,tmp);
        }
    }
    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    lg[0]=lg[1]=0,ex[0]=1,ex[1]=2;
    for(int i=2;i<=N;i++){
        lg[i]=lg[i/2]+1;
        if(i<=22)ex[i]=ex[i-1]<<1;
    }
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

L. 漫步野径

$f(x,y)=x+y$，如果有 i 条额外的路在通往 $(x,y)$ 的路上，则 $f(x,y)=x+y-i$。

所以先算出没有额外小径时总的值，再计算每条额外小径能优化的值。

首先按 yi 升序排列，xi 降序排列，保证从上到下遍历，每次的斜线都能在 LIS 中找到对应的位置。

用树状数组来维护最大 LIS 长度。

具体过程：

假设左上角为 (0,0), 右下角为 (p,q)。

我们从上到下遍历路径，并且同一行左侧的路径的区域一定能覆盖到右侧的路径的区域。

每一条路径，首先减去他能覆盖到的所有区域，再加上已经被覆盖过，无法多重贡献的区域。

LIS 通过树状数组来实现。

用 lst 数组来储存 LIS 值对应的横坐标。

树状数组中储存的是所有横坐标小于等于 x 的斜线端点中，能够形成的最长上升子序列，即能用上几个端点来减少贡献。

然后用 lst 找到这个 LIS 对应的最新的 x 坐标，加上多减的值。

 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



#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e6+7, mod=1e9+7;

ll n,p,q,mx[N],lst[N];
pair<ll,ll>a[N];

bool cmp(pair<ll,ll> x,pair<ll,ll> y){
    if(x.second==y.second)  return x.first>y.first;
    return x.second<y.second;
}

void add(ll x,ll v,int op){
    for(;x<=p;x+=(x&-x)){
        if(op)mx[x]=max(mx[x],v);
        else mx[x]=v;
    }
}

ll ask(int x){
    ll res=mx[0];
    for(;x>0;x-=(x&-x))res=max(res,mx[x]);
    return res;
}

ll calc(ll x,ll y){
    if(x>p||y>q)return 0;
    return (p-x+1)*(q-y+1);
}

void solve(){
    cin>>n>>p>>q;
    int tot=0;
    ll ans=(p+1)*(1+q)*q/2+(q+1)*(1+p)*p/2;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        lst[i]=p+1;
        x++,y++;
        if(x<=p&&y<=q)a[++tot].first=x,a[tot].second=y;
    }
    sort(a+1,a+1+tot,cmp);
    for(int i=1;i<=tot;i++){
        ll x=ask(a[i].first-1)+1;
        ans-=calc(a[i].first,a[i].second)-calc(lst[x],a[i].second);
        lst[x]=a[i].first;
        add(a[i].first,x,1);
    }
    for(int i=1;i<=tot;i++){
        add(a[i].first,0,0);
    }
    cout<<ans<<endl;
}

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

M. 意大利美食

一眼丁真，直接放弃了

关键一句：等价于找一条过两顶点的弦，使得圆严格落在弦的同侧且到弦的距离 ≥ $r$，并在这条弦与多边形边界围成的那一块区域里取面积最大者。

弦合法 + 双指针
- 把顶点序列「摊平」成长度 $2n$ 的循环数组（首尾再补一个顶点，便于计算面积），这样任何跨越 $[i,,j]$（$j$ 可跑到 $i+n$）的连续段都对应多边形上的一块“扇形”。
- 枚举左端点 $i$，用指针 $j$ 往右推，维持条件：
  1. 圆心在弦 $\overline{P_iP_j}$ 的左侧（叉积 $\text{cross}(P_i,P_j,C)>0$）；
  2. 弦到圆心的距离 $\ge r$。这保证了圆整颗都在弦外侧 → 弦与多边形分出的左边那块一定无菠萝。
快速求这块区域面积
- 预处理前缀数组 sum[k] = Σ_{t<k} (P_t×P_{t+1})（即累积叉积），可 O(1) 求出任意连续段 $i\sim j$ 围出的多边形面积：
  $$ A_{i,j}= \bigl(\text{sum}[j]-\text{sum}[i] + P_j\times P_i \bigr)/2 $$
  这里乘积是有符号的；因为顶点按逆时针给出，所以取绝对值或直接比较即可。
双指针保证每个顶点只前进一次 → 总 $O(n)$。

 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


#include <bits/stdc++.h>
using namespace std;
using i128 = __int128;
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

struct Node{
    ll x,y;
    ll crs(const Node&b)const{return x*b.y-y*b.x;}
    Node operator-(const Node &b)const{return Node{x-b.x,y-b.y};}
    ll len()const {return x*x+y*y;}
};

ll cross(Node a,Node b,Node p){
    return (a-p).crs(b-p);
}

void solve(){
    int n;
    cin>>n;
    vector<Node>p(2*n+10);
    vector<i128>sum(2*n+10);
    int x0,y0,r0;
    cin>>x0>>y0>>r0;
    Node c=Node{x0,y0};
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        p[i]=p[i+n]=Node{x,y};
    }
    p[2*n+1]=p[1];
    for(int i=2;i<=2*n+1;i++){
        sum[i]=sum[i-1]+(i128)p[i-1].crs(p[i]);
    }
    auto check=[&](int x,int y){
        ll res=cross(p[x],p[y],c);
        return res>0&&(i128)res*res>=(i128)r0*r0*(p[x]-p[y]).len();
    };

    ll ans=0;
    for(int i=1,j=2;i<=n;i++,j=max(j,i+1)){
        while(j<=2*n+1&&check(i,j)){
            ans=max((i128)ans,sum[j]-sum[i]+p[j].crs(p[i]));
            j++;
        }
    }
    cout<<ans<<endl;
}

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

J. 冲向黄金城

改进 dijkstra, dis 储存两个值 {第 i 张车票，这一张车票走了 j 米}，松弛的时候，如果该边和当前车票公司一致，且加上距离后不超过车票的距离，直接转移。否则向后转移，替换新的车票状态。

名称	类型 & 维度	下标/键含义	存放的具体值	作用
`e`	`vector<vector<array<ll,3>>> e(n+1);`	`e[u]`：城市 u 的邻接表 `array<ll,3>{v,c,w}`	对于每条铁路 `(u,v,c,w)`： • `v` —— 相邻城市编号 • `c` —— 铁路所属公司编号 • `w` —— 铁路长度	无向图邻接表。遍历边时能直接拿到“下一城‑公司‑长度”三个字段
`tk`	`vector<pair<ll,ll>> tk(k+1);`	`tk[i] = {a_i, b_i}`	旅客第 i 张车票的信息： • `a_i` —— 这张票允许乘坐的公司编号 • `b_i` —— 该票一次最多可累积的总里程	保留所有车票的顺序与参数，Dijkstra 拓展状态时要用
`pos`	`vector<vector<int>> pos(m+1);`	`pos[c]`：公司 c 出现在哪些票序号上	依次 push 每一张属于该公司的票下标 i	把“公司 c → 票的先后位置”映射出来，后续二分定位“下一张可用票”
`rmq`	`vector<vector<vector<int>>> rmq(m+1, vector<vector<int>>(21));`	第一维 `c`：公司编号第二维 `j`：稀疏表层级 (≥0) 第三维 `idx`：`pos[c][idx]` 对应的票	`rmq[c][0][idx] = b_i` —— 公司 c 的第 idx 张票的最大里程更高层 `j` 里存预处理后的区间最大值	以公司为单位建稀疏表 (Sparse Table)，支持 `get(c,l,r)` O(1) 查询“公司 c 在票区间 [l,r] 里的 b_i 最大值”
`vis`	`vector<ll> vis(n+1);`	`vis[u] == 1`/`0`	城市 u 是否已被 Dijkstra 弹出确定过最优状态	保证每个城市只处理一次
`dist`	`vector<pair<ll,ll>> dist(n+1,{1e18,1e18});`	`dist[u] = {ticket_id, used_len}`	抵达城市 u 的当前最小票号 `ticket_id` 及在该票里已走的累计里程 `used_len`	Dijkstra 的比较键：始终优先保证“更靠前的票号”，其次里程更小
λ `get`	—	参数 `(c,l,r)`	返回 `pos[c]` 区间 `[l,r]` 里最大的 `b_i`	稀疏表的 O(1) 取区间最大
λ `bin_find`	—	参数 `(L,c,x)`	在公司 c 的票里，找最早且票号 ≥ L 且 b_i ≥ x 的票编号；若不存在返回 ‑1	快速定位“还能继续坐公司 c 并且里程够用”的下一张票

整体思路小结

先按城市存图 e。

按票顺序把 (a_i,b_i) 填进 tk；并为每个公司记录出现位置 pos[c]，同时把对应的 b_i 放进 rmq[c][0]。

对每个公司独立做 Sparse Table 预处理 (rmq[c][j])，让“区间最大 b_i”查询变成 O(1)。

Dijkstra 状态 {当前票 id, 在票内已花里程, 当前城市}；扩展时：

如果还能在 当前票 上继续走公司 a_id 的边且里程不超，就直接用；

否则用 bin_find 找 下一张 里程足够的同公司票，再出发。

vis 标记出队；dist 保存“到某城的最优(票,里程)”。

最终 vis[i] 为 1 的城市，就是用完全部 k 张票后可达城市，按题目要求打印。

 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


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<array<ll, 3>>> e(n+1);
    vector<pair<ll,ll>>tk(k+1);
    vector<vector<vector<int>>>rmq(m+1, vector<vector<int>>(21));
    vector<vector<int>>pos(m+1);
    for(int i=1;i<=m;i++){
        int u,v,c,w;
        cin>>u>>v>>c>>w;
        e[u].push_back({v,c,w});
        e[v].push_back({u,c,w});
    }
    for(int i=1;i<=k;i++){
        cin>>tk[i].first>>tk[i].second;
        rmq[tk[i].first][0].push_back(tk[i].second);
        pos[tk[i].first].push_back(i);
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=20;j++){
            rmq[i][j].assign(rmq[i][0].size()+1,0);
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=20;j++){
            for(int l=0;l+(1<<j)-1<rmq[i][0].size();l++){
                rmq[i][j][l]=max(rmq[i][j-1][l],rmq[i][j-1][l+(1<<(j-1))]);
            }
        }
    }
    auto get=[&](int t,int l,int r){
        int p=__lg(r-l+1);
        return max(rmq[t][p][l],rmq[t][p][r-(1<<p)+1]);
    };
    auto bin_find=[&](int L,int t,int x){
        if(pos[t].empty()||pos[t].back()<L)return -1;
        int l=lower_bound(pos[t].begin(),pos[t].end(),L)-pos[t].begin(),r=rmq[t][0].size()-1,ans=r;
        L=l;
        if(l>r||get(t,l,r)<x)return -1;
        while(l<=r){
            int mid=(l+r)>>1;
            if(get(t,L,mid)>=x)r=mid-1,ans=mid;
            else l=mid+1;
        }
        return pos[t][ans];
    };

    vector<ll>vis(n+1);
    vector<pair<ll,ll>>dist(n+1,{1e18,1e18});
    priority_queue<array<ll,3>,vector<array<ll,3>>,greater<>> q;
    dist[1]={1,0};
    q.push({1,0,1});
    while(!q.empty()){
        auto [id,d,u]=q.top();
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto [v,c,w]:e[u]){
            if(tk[id].first==c&&tk[id].second-d>=w){
                if(dist[v].first>id||(dist[v].first==id&&dist[v].second>d+w))
                    q.push({id,d+w,v});
                continue;
            }
            int bid=bin_find(id+1,c,w);
            if(bid==-1)continue;
            if(dist[v].first>bid||dist[v].first==bid&&dist[v].second>w)
                q.push({bid,w,v});
        }
    }
    for(int i=1;i<=n;i++)cout<<vis[i];
    cout<<endl;
}

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