声明：由于 AcWing周赛 前两道题难度偏低，为节省时间不摘录第一题

第五周

2. 乘方相加

第一种思路

由于每次只能加上 $k^i$，所以可以将目标数组转化为 k 进制，判断每一位是否 $< 2$, 如果为否，则不能转换

#include <bits/stdc++.h>
using namespace std;

const int N = 100;

typedef long long LL;

int T;
int s[N];
int main()
{
    scanf("%d", &T);
    while (T -- )
    {
        int n, k;
        scanf("%d %d", &n, &k);
        memset(s, 0, sizeof s);

        while (n -- )
        {
            LL x;
            scanf("%lld", &x);
            for (int j = 1; x; j ++, x /= k)
            {
                s[j] += x % k;
            }
        }
        bool flag = true;
        for (int i = 0; i < N; i ++ )
        {
            if (s[i] > 1) 
            {
                flag = false;
                break;
            }
        }
        if (!flag) puts("NO");
        else puts("YES");
    }
    return 0;
}

3. 城市通电

第一种思路

本题求的是最小生成树。

建立发电厂的操作可以通过建立一个虚拟源点解决。

然后将每两个城市连一条电线，由于是双向的，所以一共需要连 $\frac{n * (n - 1)}{2} $ 条线。

然后求最小生成树就可以了。

记得要输出方案，将加入最小生成树的边标记在后面重搜一遍，源点为虚拟源点的是发电厂否则是电线，记录即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 2005;

typedef long long LL;
typedef pair<int, int> PII;

int n;
int x[N], y[N], p[N], k[N];
struct Edge
{
    int a, b; LL w;
    inline bool operator < (const Edge &t) const {
        return w < t.w;
    }
}edges[N * N];
int cnt;
bool st[N * N];

inline int Mattn(int x, int x2, int y, int y2)
{
    return abs(x - x2) + abs(y - y2);
}

inline int find(int x)
{
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}

LL kruskal()
{
    sort(edges, edges + cnt);
    LL res = 0;
    for (int i = 0; i < cnt; i ++ )
    {
        int a = find(edges[i].a), b = find(edges[i].b);
        if (a != b)
        {
            p[a] = b;
            res += edges[i].w;
            st[i] = true;
        }
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d %d", &x[i], &y[i]);
        p[i] = i;
    }
    for (int i = 1; i <= n; i ++ )
    {
        int c;
        scanf("%d", &c);
        edges[cnt ++] = {i, 0, c};
    }
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &k[i]);
        for (int j = 1; j < i; j ++ )
        {
            edges[cnt ++] = {i, j, (LL)(k[i] + k[j]) * Mattn(x[i], x[j], y[i], y[j])};
        }
    }

    printf("%lld\n", kruskal());

    vector<int> a;
    vector<PII> ab;
    for (int i = 0; i < cnt; i ++ )
        if (st[i])
        {
            if (!edges[i].b) a.push_back(edges[i].a);
            else ab.push_back({edges[i].a, edges[i].b});
        }
    printf("%d\n", a.size());
    for (int i = 0; i < a.size(); i ++ ) printf("%d ", a[i]);
    printf("\n%d\n", ab.size());
    for (int i = 0; i <ab.size(); i ++ ) printf("%d %d\n", ab[i].first, ab[i].second);

    return 0;
}