2021牛客寒假算法基础集训营 3

A 模数的世界 | 数论 + 构造

时间复杂度

  • 【题目描述】 组样例。每组给定 ，要求构造出一对数字
    满足 ，，且 最大
  • 【数据范围】 , ，其中 一定是素数
  • 【思路】
    （1）根据打表易得，如果不是 的话， 最大值为
    （2）我们作一个简单构造： 且
    容易构造出来
    （3）但是有可能 ，咋办呢？我们每次给 增大一些，并且还能继续保持 以及 ，我们增大多少呢？增大 即可。 
int main()
{
    int T;scanf("%d",&T);
    while(T--){
        ll a,b,p;
        scanf("%lld%lld%lld",&a,&b,&p);
        ll ta = (p - a) * (p - 1);
        ll tb = (p - b) * (p - 1);
        if(a == 0 && b == 0){
            puts("0 0 0");
            continue;
        }
        while(1){
            if(__gcd(ta,tb) % p == p-1){
                printf("%d %d %d\n",p-1,ta,tb);
                break;
            }
            ta += p*(p - 1);
        }
    }
    return 0;
}

B 内卷 | 数据结构 + 贪心

时间复杂度

  • 【题目描述】
    每个人的考试有五个等第期望得分：
    要求获得 等的人最多不超过 个人。
    问你每个人选择一个等第期望分数后， 最小是多少。
  • 【数据范围】
  • 【思路】
    （1）首先默认每个人都是最低分
    （2）怎么改变答案？让其中分数最低的人分数更高些，即选择高一等地的期望分数。
    （3）重复这个过程，记录每次的 ，直到选择 等的人超过 或者分数最低的人都是 等了为止。
    （4）怎么快速记录当前所选人的最小分数？用小顶堆。 
const int MAX = 1e5+50;

int aa[MAX][10];
struct node{
    int a,b,val;
    bool operator <(const node &ND)const{
        return val > ND.val;
    }
};
priority_queue<node>Q;
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    int mx = 0;
    int cnt = 0;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= 5;++j)
            scanf("%d",&aa[i][j]);
        Q.push({i,5,aa[i][5]});
        mx = max(mx,aa[i][5]);
    }
    int res = mx - Q.top().val;
    while(1){
        node t = Q.top();
        Q.pop();
        Q.push({t.a,t.b-1,aa[t.a][t.b-1]});
        if(t.b - 1 == 1)cnt++;
        if(t.b - 1 == 0)break;
        if(cnt > k)break;
        mx = max(mx,aa[t.a][t.b-1]);
        res = min(res,mx - Q.top().val);
    }
    printf("%d",res);
    return 0;
}

C 重力坠击 | 搜索 或 状压DP

搜索
状压
我这里是状压做法。

  • 【题目描述】
    二维平面，有 个敌人，每个敌人有坐标 ，有半径
    你有 次攻击机会，每次选择一个整数坐标，然后攻击半径
    问你至多摧毁多少个敌人
  • 【数据范围】


  • 【思路】
    （1）状态压缩，设 表示用 次攻击后，能打死的敌人集合为
    （2）状态转移：如果能一击打死敌人集合 且，那么 
/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 1e6+50;

struct node{
    int x,y,r;
}aa[20];
bool dp[2100][5];
int shu[2100];
bool can[2100];
bool ok(int x,int y,int r,int k){
    int dx = abs(x - aa[k].x);
    int dy = abs(y - aa[k].y);
    int dis = dx * dx + dy * dy;
    return dis <= (r + aa[k].r) * (r + aa[k].r);
}
void init(int n,int x,int r){
    for(int i = 0;i < x;++i){
        int t = i;
        int cnt = 0;
        while(t){
            cnt += t%2;
            t/=2;
        }
        shu[i] = cnt;
    }
    for(int i = -7;i <= 7;++i)
    for(int j = -7;j <= 7;++j){
        int tmp = 0;
        for(int k = 0;k < n;++k){
            tmp = tmp * 2;
            if(ok(i,j,r,k))tmp++;
        }
        can[tmp] = 1;
        for(int k = 0;k < x;++k){        /// 杀死敌人的集合的子集也要枚举
            if((k & tmp) == k)can[k] = 1;
        }
    }

}
int main()
{
    int n,k,R;
    scanf("%d%d%d",&n,&k,&R);
    for(int i = 0;i < n;++i){
        scanf("%d%d%d",&aa[i].x,&aa[i].y,&aa[i].r);
    }
    init(n,(1<<n),R);
    for(int i = 0;i <= k;++i)
        dp[0][i] = 1;

    for(int i = 0;i < (1<<n);++i){
        for(int j = i;j < (1<<n);++j){
            if((i & j) == i){
                if(can[j-i]){
                    for(int p = 1;p <= k;++p)
                        dp[j][p] |= dp[i][p-1];
                }
            }
        }
    }
    int mx = 0;
    for(int i = 0;i < (1<<n);++i){
        if(dp[i][k]){
            mx = max(mx,shu[i]);
        }
    }
    printf("%d",mx);
    return 0;
}

D Happy New Year！ | 暴力 (签到)

  • 【题意】
    求出最小的数位和等于 的数字
  • 【数据范围】
  • 【思路】
    暴力即可，也不用找规律。 
/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
bool check(int s,int x){
    int cnt = 0;
    while(s){
        cnt += s%10;
        s /= 10;
    }
    return cnt == x;
}

int main()
{
    int n;cin >> n;
    int st = n + 1;
    int cnt = 0;
    while(n){
        cnt += n%10;
        n /= 10;
    }
    while(1){
        if(check(st,cnt)){
            cout << st;
            break;
        }
        st++;
    }
    return 0;
}

E 买礼物 | 数据结构 (线段树+链表)

时间复杂度：

  • 【题意】
    有 个柜子，每个柜子有礼物编号
    有 个询问
    如果询问 ，表示第 个柜子的礼物被买走
    如果询问 ，表示询问在区间 的柜子中，是否有两个柜子的礼物编号相同。
  • 【数据范围】

    礼物买走操作均合法。
  • 【思路】
    （1）我们把相同编号的礼物像链表一样，串起来
    对于某个位置 ，我们记录前驱 和后继 。
    前驱指的是往前最近的位置 ，使得 ，若不存在则
    后继指的是往后最近的位置 ，使得 ，若不存在则
    （2）如果我们要查询 ，即找到区间里是否有两个相同编号的礼物，即找到区间里**是否有一个 ** 满足 (或者同理的，)
    （3）因为我们预处理出如果没有后继，则 ，所以只要寻找**区间内 的最小值即可**，就是一个线段树题了。
    （4）买走某个礼物，即让一个链的中间断开，然后两端再连上，即： 
const int MAX = 1e6+50;

int aa[MAX];
int pos[MAX];
int last[MAX];
int nxt[MAX];
const int MAX_LEN = MAX;

int seg_tree[MAX_LEN << 2];
int Lazy[MAX_LEN << 2];
//从下往上更新 节点
void push_up (int root) {
    seg_tree[root] = min(seg_tree[root << 1], seg_tree[root << 1 | 1]);      //最小值改min
}
//从上向下更新，左右孩子
void push_down (int root, int L, int R) {
    if(Lazy[root]){
        Lazy[root << 1] += Lazy [root];
        Lazy[root << 1 | 1] += Lazy[root];
        int mid = (L + R) >> 1;
        seg_tree[root << 1] +=  Lazy[root] * (mid - L + 1);
        seg_tree[root << 1 | 1] += Lazy[root] * (R - mid);
        Lazy[root] = 0;
    }
}
//建树
void build (int root, int L, int R) {
    Lazy[root] = 0;
    if(L == R) {
        seg_tree[root] = nxt[L];
        return ;
    }
    int mid = (L + R) >> 1;
    build(root << 1, L, mid);
    build(root << 1 | 1, mid + 1, R);
    push_up(root);
}

//区间查询
int query (int root, int L, int R, int LL, int RR) {
    if (LL <= L && R <= RR) return seg_tree[root];
    push_down(root, L, R);     //每次访问都去检查Lazy 标记
    int Ans = INF;
    int mid = (L + R) >> 1;
    if(LL <= mid) Ans = min(Ans, query(root << 1, L, mid, LL, RR));    //最小值改min
    if(RR > mid) Ans = min(Ans, query(root << 1 | 1, mid + 1, R, LL, RR)); //最小值改min
    return Ans;
}
//单点修改 可以改为某值，或者+-某值
void update(int root, int L, int R, int pos, int val) {
    if(L == R){
        seg_tree[root] = val;    //点直接变为某值
        return ;
    }
    int mid = (L + R) >> 1;
    if(pos <= mid) update(root << 1, L, mid, pos, val);
    else update(root << 1 | 1, mid + 1, R, pos, val);
    push_up(root);
}
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i = 1;i <= n;++i){
        scanf("%d",&aa[i]);
        if(pos[aa[i]]){
            last[i] = pos[aa[i]];
            nxt[pos[aa[i]]] = i;
        }
        else last[i] = 0;

        pos[aa[i]] = i;
        nxt[i] = n + 1;
    }
    build(1,1,n);
    for(int i = 0;i < q;++i){
        int op;scanf("%d",&op);
        if(op == 1){
            int x;scanf("%d",&x);
            nxt[last[x]] = nxt[x];
            last[nxt[x]] = last[x];
            update(1,1,n,x,n+1);
            update(1,1,n,last[x],nxt[x]);
            nxt[x] = n + 1;
            last[x] = 0;
        }else{
            int a,b;scanf("%d%d",&a,&b);
            int qu = query(1,1,n,a,b);
            if(qu <= b)puts("1");
            else puts("0");
        }
    }
    return 0;
}

F 匹配串 | 字符串

时间复杂度：
虽然看似很大，但是思路和标程差不多。并且题目保证输入串的总长

  • 【题意】
    有 个模式串。模式串指的是中间包含 的，其他都是小写字母的串。
    一个模式串的匹配串指的是该模式串的 位置替换为空或者任意长度的小写字母串。
    问你，同时满足这 个匹配串的模式串的个数为多少？
    如果为 种，输出 -1。
  • 【数据范围】
    题目保证输入串的总长
  • 【思路】
    （1）容易想出来，要么匹配串的个数为 ，要么为 个。
    （2）我们把所有匹配串的最长不包含 的那一个前缀拿出来，把所有匹配串的最长不包含 的那一个后缀拿出来。
    （3）每一个串和那个前缀和后缀去对应。前缀正着比，后缀倒着比。如果有一个是 ，那就直接跳掉，因为这个可以任意填充。如果两个串这一位的字母不同了，那么就无法构造出匹配串。 
/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 1e6+50;

string ss[MAX];
bool sam(int x,int y,bool rear){
    bool flag = true;
    if(!rear){
        for(int i = 0;i < ss[y].size();++i){
            if(ss[y][i] == '#')break;
            if(ss[x][i] == '#')break;
            if(ss[x][i] != ss[y][i]){
                flag = false;
                break;
            }
        }
    }else{
        for(int i = 0;i < ss[y].size();++i){
            if(ss[y][ss[y].size()-1-i] == '#')break;
            if(ss[x][ss[x].size()-1-i] == '#')break;
            if(ss[x][ss[x].size()-1-i] != ss[y][ss[y].size()-1-i]){
                flag = false;
                break;
            }
        }
    }
    return flag;
}
int main()
{
    int n;scanf("%d",&n);
    bool flag = true;
    int mx1 = -1,mx2 = -1;
    int id1 = 0,id2 = 0;
    for(int i = 1;i <= n;++i){
        cin >> ss[i];
        for(int j = 0;j < ss[i].size();++j){
            if(ss[i][j] == '#'){
                if(mx1 < j-1){
                    mx1 = j-1;
                    id1 = i;
                }
                break;
            }
        }
        for(int j = ss[i].size()-1;j >= 0;--j){
            if(ss[i][j] == '#'){
                if(mx2 < (int)ss[i].size()-1-j){
                    mx2 = ss[i].size()-1-j;
                    id2 = i;
                }
                break;
            }
        }
    }
    for(int i = 1;flag && i <= n;++i){
        if(!sam(i,id1,0))flag = false;
        if(!sam(i,id2,1))flag = false;
    }
    if(flag)puts("-1");
    else puts("0");
    return 0;
}

G 糖果 | 并查集

  • 【题意】 个小盆友，第 个小盆友想要 个糖 对好朋友，好朋友的好朋友不一定是你的好朋友。
    每个人拿糖的个数不得少于 ，也不得少于他所有朋友拿到的糖。
  • 【数据范围】

  • 【思路】
    跑并查集。每个人在该人所有朋友糖里面拿最大值即可。 
/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 1e6+50;

ll aa[MAX];
vector<int>V[MAX];
int bh[MAX];
ll mx[MAX];
void dfs(int x,int c){
    bh[x] = c;
    for(auto it : V[x]){
        if(bh[it])continue;
        dfs(it,c);
    }
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    ll sum = 0;
    for(int i = 1;i <= n;++i)scanf("%lld",&aa[i]);
    for(int i = 1;i <= m;++i){
        int ta,tb;scanf("%d%d",&ta,&tb);
        V[ta].push_back(tb);
        V[tb].push_back(ta);
    }
    int cnt = 0;
    for(int i = 1;i <= n;++i){
        if(!bh[i])dfs(i,++cnt);
        mx[bh[i]] = max(mx[bh[i]],aa[i]);
    }
    for(int i = 1;i <= n;++i){
        sum += mx[bh[i]];
    }

    printf("%lld",sum);
    return 0;
}

H 数字串 | 贪心

  • 【题意】 为 ，依次类推 为
    给定一个字符串，请你给出另一个不同的字符串，使得他们的字符串转成数字串都相同。
    比如
  • 【数据范围】
    给定字符串长度
    输出字符串长度必须
  • 【思路】
    贪心。
    如果有能拆成两个的你就拆，分别从 以及
    如果有能和的两个的你就和，分别为 以及
    如果匹配完了没有变动的，就是无法给出，输出 
/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 2e6+50;

char ss[MAX];
bool use[MAX];
int cnt;
char ans[MAX];
int main()
{
    scanf("%s",ss);
    bool upd = false;
    for(int i = 0;i < strlen(ss);++i){
        int t = ss[i] - 'a' + 1;
        if(t >= 11 && t <= 19){
            upd = true;
            char ca = 'a';
            char cb = 'a' + t - 10 - 1;
            ans[++cnt] = ca;
            ans[++cnt] = cb;
        }else if(t >= 21 && t <= 26){
            upd = true;
            char ca = 'b';
            char cb = 'a' + t - 20 - 1;
            ans[++cnt] = ca;
            ans[++cnt] = cb;
        }else if(i){
            if(ss[i-1] == 'a' && use[i-1] == 0 && t <= 9){
                upd = true;
                char ca = 'a' + 10 + t - 1;
                ans[cnt] = ca;
                use[i-1] = use[i] = 1;
            }else if(ss[i-1] == 'b' && use[i-1] == 0 && t <= 6){
                upd = true;
                char ca = 'a' + 20 + t - 1;
                ans[cnt] = ca;
                use[i-1] = use[i] = 1;
            }else{
                ans[++cnt] = ss[i];
            }
        }else{
            ans[++cnt] = ss[i];
        }
    }
    if(!upd)puts("-1");
    else{
        for(int i = 1;i <= cnt;++i)
            printf("%c",ans[i]);
    }
    return 0;
}

I 序列的美观度 | DP

时间复杂度：

  • 【题意】
    给定一个长度为 的序列
    如果存在某个 ，满足 ，则 序列有一点美观度。
    问你， 的所有子序列中，美观度最大的为多少。
    子序列：原序列删除一些位置(或不删除)后产生的序列
  • 【数据范围】
  • 【思路】
    （1）明显的动态规划。设 表示**末尾为数字 ，能得到的最大美观度**
    （2）转移：
    如果你这一位选 ，那就是上一次末尾选择 的美观度+1，或者是末尾选择了上一位 的美观度。
    其实 是一个前面状态的 值。 
/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 1e6+50;

int dp[MAX];
int aa[MAX];
int main()
{
    int n;scanf("%d",&n);
    memset(dp,-1,sizeof(dp));        /// 注意初始化为 -1
    int ans = 0;
    for(int i = 1;i <= n;++i){
        scanf("%d",&aa[i]);
        dp[aa[i]] = max(dp[aa[i]]+1,dp[aa[i-1]]);
        ans = max(ans,dp[aa[i]]);
    }
    printf("%d",ans);
    return 0;
}

J 加法和乘法 | 博弈

时间复杂度：

  • 【题意】
    桌上有 张牌，每张牌数字
    两人轮流行动。每次每人选择两张 ，然后选择使用加法或者乘法替换这两张牌。
    即删掉 ，用 替换 或用 替换。
    如果只剩一张牌了，该牌为奇数则先手赢，否则为后手赢。
    问你先手必胜还是后手必胜。
  • 【数据范围】
  • 【思路】
    （1）易得，我们按照牌的奇偶关系进行思考。枚举每种奇偶关系的加法和乘法
    （2）先手肯定要多删掉偶数，后手肯定要多删掉奇数。
    如果还能操作，先手优先删掉一个偶数(偶 * 偶=偶或者奇+偶=奇)；如果没有偶数只能删掉一个奇数(奇 * 奇=奇)
    如果还能操作，后手优先删掉两个奇数(奇 + 奇 = 偶)；如果只有一个奇数，那么删掉一个奇数(奇 * 偶 = 偶)
    （3）如果只有偶数，易得怎么操作都是后手赢 (偶 + 偶 = 偶 ，偶 * 偶 = 偶)
    直接贪心枚举情况即可 （正确性感觉还是能保证的） 
/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
int main()
{
    int n;scanf("%d",&n);
    int Ji = 0,Ou = 0;
    for(int i = 0;i < n;++i){
        int t;scanf("%d",&t);
        if(t&1)Ji++;
        else Ou++;
    }
    for(int i = 1;i < n;++i){
        if(i&1){
            if(Ou)Ou--;
            else Ji--;
        }else{
            if(Ji>=2)Ji-=2,Ou++;
            else if(Ji)Ji--;
            else Ou--;
        }
    }
    if(Ji)puts("NiuNiu");
    else puts("NiuMei");
    return 0;
}