比赛地址

题目链接

题目：

给出指定\(n\)，求解出一段区间\([l,r]\)使得\(\sum\limits_{i=l}^ri=n\)

解析：

从点0，1两点作为起点分别向左右延伸长度，每次延伸单位长度时，这段区间和也加1，因此答案为\([1-n,n]\)

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

int main() {
    int T;
    long long t;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld", &t);
        printf("%lld %lld\n", 1 - t, t);
    }
}

题目链接

题目：

给出底数\(n\)，由若干不同的\(n^i(i\ge0)\)组成的数中，第\(k\)大的数是多少

解析：

即\(n^i\)只有出现或者不出现两种可能，也就是说它的系数只能是0或1，这样第\(k\)大对应的系数即为\(k\)对应的二进制形式

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

long long n, k, mod = 1e9 + 7;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &n, &k);
        long long t = 1, ans = 0;
        while (k) {
            if (k & 1) ans = (ans + t) % mod;
            k >>= 1;
            t = t * n % mod;
        }
        printf("%lld\n", ans);
    }
}

题目链接

题目：

给出一组下标\(a(a_i\le n)\)，每次可以指定一个\(x\)，将\(x\nmid a_i\)则消除\(a_i\)，问最少指定几个\(x\)

解析：

• 对于特殊情况如果\(a\)的长度为\(0\)，则直接输出\(0\)

• 考虑如何一次清除，可以用类似埃筛的思想，对于任意一个不在\(a\)中的下标，考虑它小于\(n\)的倍数是否在数组中，如果均不在数组中，则输出这个值

  优化： 考虑证明结论如果n的后一半数中，存在某个值不在下标序列中，则这个值可以作为答案。充分性显然成立，必要性考虑\(n\)的前一半数如果作为答案，则一定有一个它的倍数属于\(n\)的后一半数，且不在下标序列中

• 上述情况都不满足时，输出\(n,n-1\)即可消除所有的数（因为\(x=n\)时，无法消除\(n\)）

  #include
  using namespace std;

  const int maxn = 3e5 + 5;
  char str[maxn];

  int main() {
  int T;
  int n;
  char ch;
  scanf("%d", &T);
  while (T--) {
  scanf("%d %c%s", &n, &ch, str);
  bool ok = 0;
  for (int i = 0; i < n; ++i)
  if (str[i] != ch) {
  ok = true;
  break;
  }
  if (ok) {
  for (int i = n / 2; i < n; ++i) {
  if (str[i] == ch) {
  ok = false;
  printf("1\n%d\n", i + 1);
  break;
  }
  }
  if (ok)
  printf("2\n%d %d\n", n - 1, n);
  }
  else printf("0\n");
  }
  }

题目链接

题目：

现在有\(n\)个人，有诚实的人也有撒谎的人。诚实的人只说真话，撒谎的人只说假话，他们共说了\(m\)句话，以\(i\quad j\quad identity\)的形式给出，代表\(i\)认为\(j\)是什么身份，如果言语不合法则输出-1，否则输出最多的撒谎者个数

解析：

这道题与UVA 10158非常类似，如果\(i\)认为\(j\)是诚实的人，则\(i,j\)同真同假，反之一真一假，设\([1,n]\)代表1\(\sim n\)是诚实的人的情况，\([n+1,2n]\)代表是撒谎者的情况，初始时对于所有撒谎情况赋予权重1

• 如果属于同真同假，则判断是否二者已处于一真一假的状态，如果是则集合加入失败，反之将\((i,j)\)与\((i+n,j+n)\)加入同一集合
• 如果属于一真一假，则判断是否二者已处于同真同假的状态，如果是则集合加入失败，反之将\((i,j+n)\)与\((i+n,j)\)加入同一集合

最后统计答案时，考虑遍历所有人，如果未加入答案集合中，则添加\(\max\{sz_{撒谎者}，sz_{诚实的人}\}\)，并将其本身与连带关系加入答案集合

注意：

由于已有关系仍然可能出现，而在建立过程中更改了\(sz\)数组，所以此时要对建立关系的步骤进行忽略

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m;
const int maxn = 4e5 + 5;
int p[maxn], sz[maxn];

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

bool set2(int x, int y) {
    int x1 = find(x), x2 = find(y), y1 = find(x + n), y2 = find(y + n);
    if (x1 == x2) return false;
    if (x1 == y2 || x2 == y1) return true;
    sz[x1] += sz[y2];
    sz[y1] += sz[x2];
    p[y2] = x1;
    p[x2] = y1;
    return true;
}

bool set1(int x, int y) {
    int x1 = find(x), x2 = find(y), y1 = find(x + n), y2 = find(y + n);
    if (x1 == y2 || x2 == y1) return false;
    if (x1 == x2) return true;
    sz[x1] += sz[x2];
    sz[y1] += sz[y2];
    p[x2] = x1;
    p[y2] = y1;
    return true;
}

char str[1000];
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i <= n; ++i)
            sz[i] = 0, p[i] = i;
        for (int i = n + 1; i <= 2 * n; ++i)
            sz[i] = 1, p[i] = i;
        int a, b;
        bool ok = true;
        while (m--) {
            scanf("%d%d%s", &a, &b, str);
            if (str[0] == 'i')
                ok &= set2(a, b);
            else ok &= set1(a, b);
        }
        for (int i = 1; i <= n; ++i)
            if (find(i) && find(i + n)) {
                sz[0] += max(sz[find(i)], sz[find(i + n)]);
                p[find(i)] = p[find(i + n)] = 0;
            }
        if (ok)
            printf("%d", sz[0]);
        else
            printf("-1");
        printf("\n");
    }
}

题目链接

题目：

给出一个高度为\(k\)的满二叉树，编号按层次遍历，现要给每个节点染色，其中相邻节点不能均为（红、橙）（白、黄）（绿、蓝）三对中某一对，且有些节点色彩已被指定，问染色方案数

解析：

根据Easy Version的结论，对于每个节点来说，如果父节点颜色已被确定，则该节点有4种方案，所以当某些节点（假设总个数未\(cnt_{else}\)）未被指定颜色节点影响时，贡献为\(4^{cnt_{else}}\)

对于那些被影响的节点，考虑使用\(map\)存储每个节点的颜色属于的对，并且对他的所有父节点进行标记（被影响），\(cnt_{else}=2^k-1-map_{size}\)，考虑进行搜索（假设\(v[0,1,2]\)分别代表当前节点取某个颜色对中的颜色时，可行的方案数）不难得到以下转移式

\[\text{init} :v=\{2,2,2\}\ or\ \{x_0,x_1,x_2\}\ \text{x is depend on its color}\\
v[0]=v[0]*(v_{son}[1]+v_{son}[2]) \\
v[1]=v[1]*(v_{son}[0]+v_{son}[2]) \\
v[2]=v[2]*(v_{son}[0]+v_{son}[1])
\]

最后答案即为\((v_1[0]+v_1[1]+v_1[2])\times 4^{cnt_{else}}\)

注意：

博主也不知道为什么，这里使用\(map\)可以AC，但使用\(unordered_map\)会TLE在第9个样例（若有同学知晓，可否评论区指点一二）

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

const int maxn = 3e5 + 5;
char str[maxn];

map<long long, int> m;
int k, n;
const long long mod = 1e9 + 7;

long long ksm(long long a, long long b) {
    long long ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

vector<long long> dfs(long long x) {
    vector<long long> t = { 2,2,2 };
    if (m.count(x) && ~m[x]) {
        for (int i = 0; i < 3; ++i)
            t[i] = i == m[x];
    }
    for (long long i : {x << 1, x << 1 | 1}) {
        if (!m.count(i)) continue;
        vector<long long> s = dfs(i);
        t[0] = (t[0] * (s[1] + s[2]) % mod) % mod;
        t[1] = (t[1] * (s[0] + s[2]) % mod) % mod;
        t[2] = (t[2] * (s[0] + s[1]) % mod) % mod;
    }
    //printf("%lld:%lld %lld %lld\n", x, t[0], t[1], t[2]);
    return t;
}

int main() {
    long long v;
    char ch;
    scanf("%d%d", &k, &n);
    while (n--) {
        scanf("%lld %c%*s", &v, &ch);
        switch (ch) {
        case 'r':
        case 'o': m[v] = 0; break;
        case 'w':
        case 'y': m[v] = 1; break;
        default: m[v] = 2;
        }
        v >>= 1;
        while (v) {
            if (!m.count(v))
                m[v] = -1;
            else break;
            v >>= 1;
        }
    }
    vector<long long> ans = dfs(1);
    printf("%lld", (ans[0] + ans[1] + ans[2]) % mod * ksm(4, (1ll << k) - 1 - m.size()) % mod);
}

题目链接

题目：

将\(s\)个物品分为\(n\)堆，每堆编号从\(1\sim n\)，且保证每堆至少有一个物品，问是否对于任意一种物品分发方式都存在一个连续区间\([l,r]\)使得，这段区间内对应堆中物品数量和为\(k\)

解析：

当\(s=k\)时，即每次取所有堆的情况，显然成立

当\(s<k\)时，取所有物品也到不了\(k\)，显然不成立

对于\(s>k\)的情况，考虑构造一个所用物品最小，且不满足条件的分配方式

\[\underbrace{1, 1, 1, \dots}_{k-1},\ k+1,\ \underbrace{1,1,1,\dots}_{k-1},\ k+1,\ \dots
\]

不难发现这样的构造方式下，需要对每个堆分发一个物品，剩下的物品数量为\(s-n\)，而下标为\(k\)的倍数的位置，需要再多分配\(k\)个物品，总计为\(\lfloor \frac{n}{k}\rfloor k\)个物品，那么当\(s-n<\lfloor \frac{n}{k}\rfloor k\)时无法构造

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

int main() {
    int T;
    long long s, n, k;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld%lld", &s, &n, &k);
        if (s == k) printf("YES\n");
        else if (s < k) printf("NO\n");
        else printf("%s\n", n / k * k > s - n ? "YES" : "NO");
    }
}