2022 CCPC 威海站

发表于 分类于

成功打星（

不过还是有不尽人意的地方，赛中B题没有给调出来，比较缺乏写暴力的能力。L题比较简单的线性代数也没能想出来。一直在往比较麻烦的贪心上想。

做不出来需要及时更换另一种思路！

A. Dunai

一个比较简单的题目，但我没想好直接WA了一发。

显然只有两种限制：每个种类的制约，以及获得过冠军的总数。

两者求 min 就OK了。

B. Recruitment

可以发现，当 $s_i-1=s_{i+1}$ 时，$x+y-xy=1$。即 $(x-1)(y-1)=0$，$x,y$ 里面至少一个 $1$。

那么只有大于 $1$ 的点是有用的。而 $\prod x_i=s_{n-1}\le 10^9$，那么有用的状态就很少了。

于是直接从开始搜索，用 map<vector<int>,status> 记录所有状态以及前驱就ok了。

需要注意一些细节，及时判掉不合法的状态。

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
#include <bits/stdc++.h>
using namespace std;
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define VI vector<int>
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<class T>inline void read(T &x) {
    x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) f|=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+(ch^48);
    if(f) x=-x;
}
template<class T,class... V>
inline void read(T &a,V&... b){read(a); read(b...);}
#define CASES int ___;for(read(___);___--;)
mt19937 rnd(random_device{}());
const int N = 1e5+5;

vector<int> divide(int n) {
    vector<int> vec;
    vec.clear();
    fo(i,1,sqrt(n))
        if(n%i == 0) {
            vec.pb(i);
            if(i*i!=n)
                vec.pb(n/i);
        }
    sort(all(vec));
    return vec;
}

vector<int> adj[60];
int bel[60],pos[60],col[60];
int tim;
void dfs(int u) {
    if(!adj[u].size()) {
        ++tim;
        printf("%d ",col[u]);
        return;
    }
    assert(adj[u].size() == 2);
    dfs(adj[u][0]);
    pos[bel[u]] = tim;
    dfs(adj[u][1]);
}

int n,a[N],cnt;
vector<int> w;

struct node {
    map<vector<int>,node>::iterator ite;
    int x,y;
};

map<vector<int>,node> ma[32];

inline vector<int> update(vector<int> a,int x,int y) {
    int z = x*y,i;
    i = lower_bound(all(a),z)-a.begin();
    ff(j,i,a.size()-1)
        a[j]=a[j+1];
    a.pop_back();

    i = lower_bound(all(a),x)-a.begin();
    a.pb(x);
    fd(j,a.size()-2,i)
        swap(a[j+1],a[j]);
    
    i = lower_bound(all(a),y)-a.begin();
    a.pb(y);
    fd(j,a.size()-2,i)
        swap(a[j+1],a[j]);
    return a;
}

inline void check() {
    int m = w.size()+1;
    DEBUG(m);
    vector<int> b;
    b.pb(a[n]);

    ma[m-1][b] = {ma[0].end(),0,0};
    for(int t=m-1;t>=0;t--)
        if(ma[t].size() == 0)
            return;
        else if(t!=0) {
            for(auto ma_it = ma[t].begin(); ma_it != ma[t].end(); ma_it++) {
                auto s = ma_it -> fi;
                ff(i,0,s.size()) {
                    int z = s[i];
                    fo(x,2,sqrt(z))
                        if(z%x==0) {
                            int y = z/x;
                            if(z-x-y != w[t-1])
                                continue;
                            ma[t-1][update(s,x,y)] = {ma_it,x,y};
                        }
                }
            }
        }
        else {
            set<pair<int,int>> val;
            int tot = 0;
            auto v = (ma[t].begin()) -> fi;
            for(auto x:v) {
                ++tot;
                col[tot]=x;
                val.insert({x,tot});
            }
            DEBUG(tot);
            auto add = [&](int x,int y,int z) {
                auto it = val.lower_bound({x,0});
                int xx = (*it).se;
                val.erase(it);
                it = val.lower_bound({y,0});
                int yy = (*it).se;
                val.erase(it);

                val.insert({x*y,++tot});
                bel[tot] = z;
                adj[tot].pb(xx);
                adj[tot].pb(yy);
            };
            auto it = ma[t].begin();
            for(int j=1;j<=m-1;j++) {
                auto u = it -> se;
                add(u.x,u.y,j);
                it = u.ite;
            }
            dfs(tot);
            for(int i=1;i<=cnt;i++) printf("%d ",1);
            printf("\n");
            for(int i=2,k=n-1,j=0;i<=n;i++)
                if(a[i] - a[i-1] == -1)
                    printf("%d\n",k--);
                else
                    printf("%d\n",pos[++j]);
            exit(0);
        }
}

vector<int> d;
int m;
vector<int> b;

int main() {
    read(n);
    fo(i,1,n)
        read(a[i]);
    fo(i,2,n)
        if(a[i] - a[i-1] == -1) {
            cnt++;
        }
        else {
            if(a[i] - a[i-1] < -1) {
                puts("-1");
                return 0;
            }
            w.pb(a[i] - a[i-1]);
        }
    if(w.size() > 30) {
        puts("-1");
        return 0;
    }
    d = divide(a[n]);
    //for(auto x:d) printf("%d\n",x);
    check();
    puts("-1");
    return 0;
}

C. Grass

$5$ 个点有解当且仅当这 $5$ 个点不共线。

随便找到五个不共线的点，然后枚举 $A$ 点构造即可。

D. Sternhalma

一眼状压DP，不过建图非常麻烦。

可以在图的左下角加多一个三角形就方便很多了。

E. Python Will be Faster than C++

签到题。

F. Mooncake Delivery

将一条路径分为若干个极大相同颜色连续段，一条路径的权值等于（连续段权值和+下一个点的点权）的最大值。

对于相同颜色的点，用Floyd求出两两最短路，然后建一个新图，$(u,w)$ 边权为：枚举与 $u$ 相同颜色的点 $v$ 且 $(v,w)\in E$，连边 $(u,w,dis_{u,v} + val_w)$。

在新图上跑最大值的Floyd即可。

G. Grade 2

发现 $k$ 中大于 $2^{\text{Popcount(x)}}$ 的是没用的，也就是构成一个 $2$ 的次幂的循环节。

然后预处理一下就OK了。

H. Party Animals

留坑。。。

I. Dragon Bloodline

由于每种是 $2^i$，那么贪心就是正确的，因为肯定存在某种最优解是贪心的策略。

于是二分，然后从大到小贪心就ok了。

J. Eat, Sleep, Repeat

可以发现，所有的数都不能越过 $limit_x=0$。

用 $limit_x=0$ 分段，然后统计次数的奇偶性就ok了。

K. I Wanna Maker

对于 $1$ 条件，可以合并成一个。

对于 $2$ 条件，可以枚举左端点的区间，然后右端点的合法方案数是一个分段函数。

L. Novice Magician

首先，若 $\sum b_i$ 不被 $2^{n-1}$ 整除，那么无解。

将 $2,4,6,\cdots$ 这些随便分配到要操作的数中。

那么，每次操作相当于给一半的数加 $x$。

那么相当于要构造一个 $2^n\times 2^n$ 的矩阵 $A$，使得每一行中恰好有一半的是 $1$，一半是 $0$。满足 $xA=b’$ 有整数解，其中 $x,b’ $ 是 $1\times 2^n$ 的矩阵。

若 $A$ 必须有逆，则可以直接求出来。也就是这 $2^n$ 个向量线性无关。

可以如下构造（$n=3$）：

$$
A = \begin{bmatrix}
1 & 1 & 1 & 1 & & & & \
& 1 & 1 & 1 & 1 & & & \
& & 1 & 1 & 1 & 1 & & \
& & & 1 & 1 & 1 & 1 & \
1 & 1 & 1 & & & & & 1\
& 1 & 1 & 1 & & & & 1\
& & 1 & 1 & 1 & & & 1\
& & & 1 & 1 & 1 & & 1
\end{bmatrix}
$$

这样就一定有逆元，打表找找逆元的规律就可以了。

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
const int N = 2050;
int f[N][N],a[N];
bool b[N][N];
ll ans[N];
int n;
int main() {
    cin>>n;
    int m = (1<<n);
    int sum = 0;
    ff(i,0,m) {
        read(a[i]);
        sum += a[i];
    }
    if(sum % (m/2) != 0)
        return puts("NO")&0;
    ff(i,0,m/2) {
        ff(j,0,m/2)
            a[i+j] -= 2*j,b[i][i+j] = 1;
        ff(j,0,m/2-1)
            a[i+j] -= 2*j,b[i+(m/2)][i+j] = 1;
        a[m-1] -= (m-2);
        b[i+(m/2)][m-1] = 1;
    }
    ff(i,0,m/2-1) {
        ff(j,0,m) {
            if(j==i||j-(m/2-1)==i)
                ans[i] += 1ll * ((m/2)-1) * a[j];
            else
                ans[i] -= a[j];
        }
    }
    ans[m/2-1] = 1ll * (m/2) * a[m-2];
    ff(i,0,m/2) {
        ff(j,0,m) {
            if(j+1==i||j-(m/2-1)==i)
                ans[i+(m/2)] -= 1ll * ((m/2)-1) * a[j];
            else
                ans[i+(m/2)] += a[j];
        }
    }
    ff(i,0,m) ans[i] /= (m/2);
    printf("YES\n%d\n",m);
    ff(i,0,m) {
        printf("%lld",ans[i]);
        ff(j,0,m)
            if(b[i][j])
                printf(" %d",j);
        printf("\n");
    }
    return 0;
}

M. String Master

为了让字典序最大，我们需要让一尽可能地多。

先去掉一些边边角角的情况。

然后考虑枚举开始时二进制的长度 $i$，枚举从第 $j$ 位开始。贪心，从 $j$ 开始选，为了字典序最大，我们要使得 $j\sim 0$ 位都是 $1$。

然后写一堆比较函数之类的就ok了。

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
const int M = 59;

struct node{
    ll n;
    int l,p;
    node() {n=p=0; l=1;}
    node(ll _n,int _l,int _p) {n=_n,l=_l,p=_p;}
    inline bool x() {return (n>>(l-p-1))&1;}
    friend inline bool operator<(const node &A,const node &B) {
        if(A.n!=B.n)
            return A.n<B.n;
        return A.p<B.p;
    }
    friend inline bool operator>(const node &A,const node &B) {
        if(A.n!=B.n)
            return A.n>B.n;
        return A.p>B.p;
    }
    inline void set(ll x) {
        if(x == 0) {
            return;
        }
        ll sum = 0;
        fo(i,1,M) {
            ll tmp = (1ll<<i) - (1ll<<(i-1));
            if(i==1) tmp++;
            if(sum + tmp * i > x) {
                l = i; break;
            }
            sum += tmp * i;
        }
        sum = x-sum;
        n = ((l==1)?0:(1ll<<(l-1))) + (sum/l);
        p = sum % l;
    }
    inline ll get() {
        if(l==1)
            return n;
        ll sum = 1;
        ff(i,1,l)
            sum += 1ll * ((1ll<<i) - (1ll<<(i-1))) * i;
        return sum + (n - (1ll<<(l-1))) * l + p;
    }
    inline void nxt() {
        p++;
        if(p!=l)
            return;
        p = 0; n++;
        if(lowbit(n) == n && n != 1) {
            l++;
        }
    }
};

inline bool cmp(node A,node B,int n) {
    if(A.n < 0)
        return 0;
    fo(i,1,n) {
        if(A.x() != B.x())
            return A.x() > B.x();
        A.nxt(); B.nxt();
    }
    return 0;
}
inline void print(node A,int n) {
    ff(i,0,n)
        putchar(A.x()+'0'),A.nxt();
    putchar('\n');
}

inline void work(ll l,ll r,int n) {
    node L,R,ans={-1,-1,-1},x;
    for(ll i = l;i <= min(10ll,r);i ++) {
        x.set(i);
        ans = cmp(ans,x,n)?ans:x;
    }
    for(ll i = max(r-M,l);i <= r; i++) {
        x.set(i);
        ans = cmp(ans,x,n)?ans:x;
    }

    l = max(11ll,l);
    L.set(l); R.set(r);
    fo(i,2,M) {
        node nl = {1ll<<(i-1), i, 0}, nr = {(1ll<<i)-1, i, i-1};
        if(nl>R || nr<L)
            continue;
        if(nl < L) nl = L;
        if(nr > R) nr = R;
        ff(j,0,i) {
            ll tmp = 1ll<<(j+1);
            x = {nr.n|(tmp-1), i, i-1-j};
            if(x > nr) x.n -= tmp;
            if(!(x<nl)) ans = cmp(ans,x,n)?ans:x;
        }
    }
    print(ans,n);
}

int main() {
    CASES {
        ll l,r;
        int n;
        read(l,r,n);
        work(l-1,r-n,n);
    }
    return 0;
}