溢流眼泪

2021-02-05 23:43 已编辑 C++

关注

【解题报告】2021牛客寒假算法基础集训营 3

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

2021牛客寒假算法基础集训营 3
【建议看一下解法的时间复杂度再酌情选择看题解】

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

时间复杂度 $O(Tk)$

【题目描述】 $T$ 组样例。每组给定 $a,b,p$ ，要求构造出一对数字 $ta,tb$
满足 $ta\equiv a\pmod p$ ， $tb\equiv b\pmod p$ ，且 $\gcd(ta,tb)\ \%\ p$ 最大
【数据范围】 $T\le 10^6$ , $0\le a,b<p<2\times10^4$ ，其中 $p$ 一定是素数 $0\le ta,tb\le 2^{63}-1$
【思路】
（1）根据打表易得，如果不是 $a=0且b=0$ 的话， $\gcd(ta,tb)\ \%\ p$ 最大值为 $p-1$
（2）我们作一个简单构造： $ta=p(xxx)+a$ 且 $ta=(p-1)(xxx)$
容易构造出来 $ta=(p-a)(p-1),tb=(p-b)(p-1)$
（3）但是有可能 $\gcd(ta,tb)\%p\ne p-1$ ，咋办呢？我们每次给 $ta$ 增大一些，并且还能继续保持 $ta\equiv a\pmod p$ 以及 $ta\equiv 0\pmod{p-1}$ ，我们增大多少呢？增大 $p(p-1)$ 即可。

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 内卷 | 数据结构 + 贪心

时间复杂度 $O(5n\log(5n))$

【题目描述】
每个人的考试有五个等第期望得分： $A_i,B_i,C_i,D_i,E_i$
要求获得 $A$ 等的人最多不超过 $k$ 个人。
问你每个人选择一个等第期望分数后， $\max\{每个人选择的等第期望分\}-\min\{每个人选择的等第期望分\}$ 最小是多少。
【数据范围】 $1\le k\le n\le 10^5$
$1\le E_i \le D_i \le C_i \le B_i \le A_i \le 10^9$
【思路】
（1）首先默认每个人都是最低分 $E_i$
（2）怎么改变答案？让其中分数最低的人分数更高些，即选择高一等地的期望分数。
（3）重复这个过程，记录每次的 $\max-\min$ ，直到选择 $A$ 等的人超过 $k$ 或者分数最低的人都是 $A$ 等了为止。
（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

搜索 $O(n\times64^k)$
状压 $O(k\times2^n\times2^n)$
我这里是状压做法。

【题目描述】
二维平面，有 $n$ 个敌人，每个敌人有坐标 $x_i,y_i$ ，有半径 $r_i$
你有 $k$ 次攻击机会，每次选择一个整数坐标，然后攻击半径 $R$
问你至多摧毁多少个敌人
【数据范围】 $1\le n\le 10$
$1\le k\le 3$
$1\le r_i,R\le 7$
$0\le |x_i|,|y_i|\le7$
【思路】
（1）状态压缩，设 $dp[i][j]$ 表示用 $j$ 次攻击后，能打死的敌人集合为 $i$
（2）状态转移：如果能一击打死敌人集合 $j-i$ 且 $j\&i=i$ ，那么 $dp[j][q] \ |\!= dp[i][q+1]$

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ 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！ | 暴力 (签到)

【题意】
求出最小的数位和等于 $n$ 的数字
【数据范围】 $2021\le n\le 2030$
【思路】
暴力即可，也不用找规律。

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ 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 买礼物 | 数据结构 (线段树+链表)

时间复杂度： $O(n\log n+q\log q)$

【题意】
有 $n$ 个柜子，每个柜子有礼物编号 $a_i$
有 $q$ 个询问
如果询问 $1\ x$ ，表示第 $x$ 个柜子的礼物被买走
如果询问 $2\ a\ b$ ，表示询问在区间 $[a,b]$ 的柜子中，是否有两个柜子的礼物编号相同。
【数据范围】 $1\le n,q\le 5\times10^5$
$1\le a_i\le 10^6$
礼物买走操作均合法。
【思路】
（1）我们把相同编号的礼物像链表一样，串起来
对于某个位置 $i$ ，我们记录前驱 $last[i]$ 和后继 $nxt[i]$ 。
前驱指的是往前最近的位置 $last[i]$ ，使得 $a_{last[i]}=a_i$ ，若不存在则 $last[i]=0$
后继指的是往后最近的位置 $nxt[i]$ ，使得 $a_{nxt[i]}=a_i$ ，若不存在则 $nxt[i]=n+1$
（2）如果我们要查询 $2\ a\ b$ ，即找到区间里是否有两个相同编号的礼物，即找到区间里**是否有一个 $nxt[i]$ ** 满足 $nex[i]\le b$ (或者同理的， $last[i]\ge a$ )
（3）因为我们预处理出如果没有后继，则 $nxt[i]=n+1$ ，所以只要寻找**区间内 $nxt[i]$ 的最小值即可**，就是一个线段树题了。
（4）买走某个礼物，即让一个链的中间断开，然后两端再连上，即： $nxt[last[i]]=nxt[i]\\last[nxt[i]]=last[i]\\nxt[i]=n+1\\last[i]=0$

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 匹配串 | 字符串

时间复杂度： $O(n|S_i|)$
虽然看似很大，但是思路和标程差不多。并且题目保证输入串的总长 $\le 10^6$

【题意】
有 $n$ 个模式串。模式串指的是中间包含 $\#$ 的，其他都是小写字母的串。
一个模式串的匹配串指的是该模式串的 $\#$ 位置替换为空或者任意长度的小写字母串。
问你，同时满足这 $n$ 个匹配串的模式串的个数为多少？
如果为 $\inf$ 种，输出 -1。
【数据范围】 $1\le n\le 10^6$
题目保证输入串的总长 $\le 10^6$
【思路】
（1）容易想出来，要么匹配串的个数为 $0$ ，要么为 $\inf$ 个。
（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 糖果 | 并查集

【题意】 $n$ 个小盆友，第 $i$ 个小盆友想要 $a_i$ 个糖 $m$ 对好朋友，好朋友的好朋友不一定是你的好朋友。
每个人拿糖的个数不得少于 $a_i$ ，也不得少于他所有朋友拿到的糖。
【数据范围】 $1\le n\le 10^6$
$0\le m\le 10^6$
$1\le a_i\le 10^9$
【思路】
跑并查集。每个人在该人所有朋友糖里面拿最大值即可。

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ 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 数字串 | 贪心

【题意】 $a$ 为 $1$ ，依次类推 $z$ 为 $26$
给定一个字符串，请你给出另一个不同的字符串，使得他们的字符串转成数字串都相同。
比如 $cwc=cbcc=3233$
【数据范围】
给定字符串长度 $\le 10^6$
输出字符串长度必须 $\le 2\times 10^6$
【思路】
贪心。
如果有能拆成两个的你就拆，分别从 $11\sim 19$ 以及 $21\sim 26$
如果有能和的两个的你就和，分别为 $aa\sim aj$ 以及 $ba\sim bf$
如果匹配完了没有变动的，就是无法给出，输出 $-1$

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ 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

时间复杂度： $O(n)$

【题意】
给定一个长度为 $n$ 的序列 $S$
如果存在某个 $i\in[1,n-1]$ ，满足 $S_i=S_{i+1}$ ，则 $S$ 序列有一点美观度。
问你， $S$ 的所有子序列中，美观度最大的为多少。
子序列：原序列删除一些位置(或不删除)后产生的序列
【数据范围】 $2\le n\le 10^6$
$1\le s_i\le 10^6$
【思路】
（1）明显的动态规划。设 $dp[i]$ 表示**末尾为数字 $i$ ，能得到的最大美观度**
（2）转移： $dp(S_i)=\max\{dp(S_i)+1,dp(S_{i-1})\}$
如果你这一位选 $S_i$ ，那就是上一次末尾选择 $S_i$ 的美观度+1，或者是末尾选择了上一位 $S_{i-1}$ 的美观度。
其实 $dp(S_{i-1})$ 是一个前面状态的 $max$ 值。

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ 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 加法和乘法 | 博弈

时间复杂度： $O(n)$

【题意】
桌上有 $n$ 张牌，每张牌数字 $a_i$
两人轮流行动。每次每人选择两张 $a_i、a_i$ ，然后选择使用加法或者乘法替换这两张牌。
即删掉 $a_i、a_j$ ，用 $a_i+a_j$ 替换或用 $a_i\times a_j$ 替换。
如果只剩一张牌了，该牌为奇数则先手赢，否则为后手赢。
问你先手必胜还是后手必胜。
【数据范围】 $1\le n\le 10^6$
$1\le a_i\le 10^9$
【思路】
（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;
}