疑似首刀A

A. 小苯的xor构造

易得 ，输出 k 0 即可。

print(input(), 0)

B.小苯的权值计算

按题意计算即可

from math import gcd
n = int(input())
a = [0] + list(map(int, input().split()))
b = [0]
g = 0
for i in range(1, n):
    g = gcd(g, a[i]^a[i+1])
print(g)

C.小苯的01矩阵构造

考虑初始全 的情况下进行翻转操作。

不难发现，每次翻转，行和列的异或和均会变化，因此 一定为偶数。

当 为奇数时无解， 为偶数时在对角线放置 个 即可。

n, k = map(int, input().split())
if k % 2 == 1:
    print(-1)
else:
    g = [[0 for i in range(n)] for j in range(n)]
    for i in range(k//2):
        g[i][i] = 1
    for i in g:
        print(*i, sep='')

D.小苯的重排构造

不难发现 的值只有 两种，其中 只能由 产生。

我们可以把 视作 基础上 ，只需考虑如何 。

令 中由 个 , 个 。

不难得出 可行的 的范围为 ，对应 和 两种情况。

满足条件的情况下，我们可以先在开头放置 个 ，在交替放置 , ，即可构造出 。

特判 全 时 ， 只能为 。

n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
c1 = c2 = 0
for i in range(1, n+1):
    c1 += a[i] == 1
    c2 += a[i] == 2
if c1 == n:
    if k == n-1:
        print(*a[1:])
    else:
        print(-1)
else:
    if max(0, c2 - c1 - 1) + n - 1 <= k <= c2 - 1 + n - 1:
        ans = []
        for i in range(k-(n-1) + 1):
            ans.append(2)
        c2 -= k-(n-1) + 1
        for i in range(min(c1, c2)):
            ans.append(1)
            ans.append(2)
        ans += [1] * (c1 - c2)
        print(*ans)
    else:
        print(-1)

E.小苯的xor图

看到异或和考虑拆位。

对每一位考虑，。

观察到长度为 的简单路径可以由点的邻居和点的邻居的邻居构成。

因此可以统计每个点周围有几个 ,几个 。

计算时遍历 的所有邻居，因为我们已经处理了每个点周围有几个 ,几个 ，因此此时可以直接计算出 为起始的所有路径的异或和。

每条路径均会计算两次，因此最后要把答案除 。

注意 自己也是点的邻居的邻居，计算时要去掉自己。

时间复杂度

void solve(){
    ll n = read(), m = read();
    vector<ll> a(n+1);
    for(ll i=1;i<=n;i++) a[i] = read();
    vector<vector<ll>> w(32, vector<ll>(n+1));
    for(ll i=1;i<=n;i++){
        for(ll bit=31;bit>=0;bit--){
            if((a[i]>>bit)&1){
                w[bit][i] = 1;
            }
        }
    }
    vector<vector<ll>> g(n+1);
    vector<PLL> egs;
    vector<ll> cnei(n+1);
    for(ll i=1,u,v;i<=m;i++){
        u = read(), v = read();
        g[u].pb(v);
        g[v].pb(u);
        egs.pb({u, v});
        cnei[u]++;
        cnei[v]++;
    }
    ll ans = 0;
    for(ll bit=31;bit>=0;bit--){
        vector<ll> nei(n+1);
        ll t = 0;
        for(ll i=1;i<=n;i++){
            for(auto v:g[i]){
                nei[i] += w[bit][v];
            }
        }
        for(ll i=1;i<=n;i++){
            if(w[bit][i]==1){
                for(auto v:g[i]){
                    if(w[bit][v]==1){
                        t += (nei[v]-1);
                    }
                    else{
                        t += cnei[v] - nei[v];
                    }
                }
            }
            else{
                for(auto v:g[i]){
                    if(w[bit][v]==0){
                        t += nei[v];
                    }
                    else{
                        t += (cnei[v] - nei[v] - 1);
                    }
                }
            }
        }
        ans = (ans + t * ((1<<bit)%MOD)%MOD)%MOD;
        //print(t);
    }
    print(ans*ksm(2, MOD-2)%MOD);
}  

F. 小苯的前缀gcd构造

比较神秘的复杂度，加了三个剪枝就过了。

不难发现，如果 不是 的倍数，则 ，这和选择 是一样的效果。

因此我们可以搜索所有的 是 的倍数的序列，暴力求出每一种的答案。

但是直接交会，可以加上以下几个剪枝：

• 时一定无解
• 时输出 个
• 第一个数的范围只可能在 中。

g = [[] for i in range(51)]
g[1].append(1)
for i in range(2, 51):
    for j in range(1, i+1):
        if i % j == 0:
            g[i].append(j)
            
def find(n, m, x):
    for fi in range(min(m, x),(x+n-1)//n-1,-1):
        stk = [[[fi], 1, fi]]
        while stk:
            v, s, xx = stk.pop()
            if s == n:
                if xx == x:
                    return v
                continue
            la = v[-1]
            for ne in g[la]:
                stk.append([v+[ne],s+1,xx+ne])
    return [-1] 
                    
for _ in range(int(input())):
    n, m, x = map(int, input().split())
    if x < n:
        print(-1)
    elif x % n == 0:
        print(*[x//n for i in range(n)])
    else:
        print(*find(n, m, x))