CF EDU 37 A - C, E - G 题解

传送门
A:
有n个地方, 其中有k个水龙头, 水龙头每秒可以向两边扩展1格, 问把n个地方都浇了至少需要多少秒.

直接暴力算每个需要的最小值, 然后取这些的max值即可.

AC Code

const int maxn = 2e2+5;
int a[maxn], vis[maxn];
void solve()
{
    int n, k; Fill(vis, 0);
    scanf("%d%d", &n, &k);
    for (int i = 1 ; i <= k ; i ++) {
        scanf("%d", &a[i]);
        vis[a[i]] = 1;
    }
    int ans = 1;
    for (int i = 1 ; i <= n ; i ++) {
        if (vis[i]) continue;
        int tmp = inf;
        for (int j = 1 ; j <= k ; j ++) {
            if (abs(i-a[j])+1 < tmp) {
                tmp = abs(i-a[j])+1;
            }
            else break;
        }
        ans = max(ans, tmp);
    }
    printf("%d\n", ans);
}

B: 这道题题意有点难读, 读懂了就很简单了.
就是给出n个人来排队的时间和最多等待的时间, 比如l, r则它是第l秒来的, 第r+1秒走. 叫你输出这n个人喝到茶的时间, 如果他喝不到则输出0. 每个人倒茶需要1秒.

直接模拟做, 每次判断是否到了它要走的时间, 到了就不算他就是了, 然后每次和新的人的第一个值取max即可.

AC Code

const int maxn = 1e3+5;
int cas=1;
pii a[maxn];
int ans[maxn];
void solve()
{
    int n; Fill(ans, 0);
    scanf("%d", &n);
    for (int i = 1 ; i <= n ; i ++) {
        int l, r;
        scanf("%d%d",&l, &r);
        a[i] = mk(l, r);
    }
    int tt = a[1].fi;
    ans[1] = tt;
    tt++;
    for (int i = 2 ; i <= n ; i ++) {
        if (a[i].se < tt) {
            continue;
        }
        tt = max(tt, a[i].fi);
        ans[i] = tt;
        tt++;
    }
    for (int i = 1 ; i <= n ; i ++) {
        printf("%d%c", ans[i], i == n ?'\n':' ');
    }
}

C :
给出一个长度为n的排列. 在给出一个字符串, 如果字符串的第i个字符是’1’则说明对应这个排列的第i个位置可以和第i+1个位置进行调换, 次数不限. 问是否可能那这个排列换成1-n的全排列.

我的做法时暴力, 一串连续的1加一位, 这一串对应于原排列一定是对应位置的一个排列, 否则的话一定不能完成目标, 所以暴力找出这些串然后判断一下即可. 复杂度O(2*n)

AC Code

const int maxn = 2e5+5;
int a[maxn];
char s[maxn];
bool vis[maxn];
void solve()
{
    int n;
    while(~scanf("%d", &n)) {
        for (int i = 1 ; i <= n ; i ++) {
            scanf("%d", &a[i]);
        }
        scanf("%s", s+1);
        int len = strlen(s+1);
        int cnt ;
        int flag = 1;
        for (int i = 1 ; i <= n ; i += cnt) {
            cnt = 1;
            if (s[i] == '0') {
                if (a[i] != i) {
                    flag = 0;
                    break;
                }
            }
            else {
                Fill(vis, 0);
                vis[a[i]] = 1;
                int k;
                for (int j = i + 1 ; j <= n ; j ++) {
                    cnt++;
                    vis[a[j]] = 1;
                    if (s[j] == '0') {
                        k = j;
                        break;
                    }
                }
                for (int j = i ; j <= min(n, k) ; j++) {
                    if (!vis[j]) {
                        flag = 0 ;
                        break;
                    }
                }
            }
            if (!flag) break;
        }
        if (flag) printf("YES\n");
        else printf("NO\n");
    }
}

E:
给出一个n个顶点的无向完全图， 删掉m条边, 问删去后这个图的联通块个数及其每个块的大小. 注意这个联通块的定义是只有两点之间可达他们就属于一个联通块中. (不要和边双搞混)

肯定不能暴力高每个点, 因为一个点最多只能在一个联通块中， 所以我们先把这些点先全部存下来, 然后访问到一个点就删去一个点, 对应的数量++即可, 这个涉及到的删除肯定用stl库来做最好,

!!! 但是注意涉及到删迭代器的千万不要用vector来做, 这个删除很神奇, 也很慢, 会T, 并且有一些其他我也不知道的事情发生, 所以记住不要用vector就行.

那么我们就用set来做(list等也行), 然后bfs即可.

AC Code

int n, m;
map<pii, bool>mp;
vector<int> ans;
set<int>edge;
int bfs(int st) {
    queue<int>q;
    q.push(st);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        ans.back()++;

        for (auto it = edge.begin() ; it != edge.end() ; ) {
            int tmp = *it;
            if (!mp[{u, tmp}]) {
                edge.erase(it++);
                q.push(tmp);
            }
            else it++;
        }
    }
}
void solve()
{
    scanf("%d%d", &n, &m);
    for (int i = 1 ; i <= m ; i ++) {
        int u, v;
        scanf("%d%d",&u, &v);
        mp[{u, v}] = mp[{v, u}] = 1;
    }
    for (int i = 1 ; i <= n ; i ++) {
        edge.insert(i);  // 用set
    }
    while(sz(edge)) {
        ans.pb(0);
        int tmp = *edge.begin();
        edge.erase(edge.begin());
        bfs(tmp);
    }
    sort(ans.begin(), ans.end());
    printf("%d\n", sz(ans));
    for (int i = 0 ; i < sz(ans) ; i ++) {
        printf("%d%c", ans[i], i == sz(ans)?'\n':' ');
    }
}

F:
先给出d(i) 的定义为i的因子个数, d(2) = 2, d(1) = 1.
给出n个数, q次操作,
1 l r 代表把l - r 中所有的数变成对应的a[l];
2 l r 求 ∑ri=la[i] $\underset{i=l}{\overset{r}{\sum }}a[i]$
当然我们先nlogn预处理出d数组, 然后这种问题是经典的区间更新中的单点更新, 这种问题一般是每个点被修改的次数有限, 像这里应该是被修改6次左右(当a[i] <= 2时修改其就是没有意义的了), 所以我们要维护一个区间max值, 当被修改的区间中有区间的max<=2, 那么这个区间应该直接跳过, 因为修改没有意义了. 求和也是线段树直接搞就是了.
复杂度为O(6*nlogn).

AC Code

const int maxn = 3e5 + 5;
const int maxm = 1e6 + 5;
int cas=1;
int d[maxm];
void init() {
    for (int i = 1 ; i <= 1000000 ; i ++) {
        for (int j = i ; j <= 1000000 ; j += i) {
            d[j]++;
        }
    }
}
ll a[maxn];
struct Tree
{
    int tl, tr; ll val, mx;
}tree[maxn<<2];

void pushup(int id)
{
    tree[id].val = tree[id<<1].val + tree[id<<1|1].val;
    tree[id].mx = max(tree[id<<1].mx, tree[id<<1|1].mx);
}
void build(int id, int l, int r)
{
    tree[id].tl = l, tree[id].tr = r;
    if(l == r){
        tree[id].val = tree[id].mx = a[l];
        return ;
    }
    int mid = (r+l)>>1;
    build(id<<1, l, mid);
    build(id<<1|1, mid+1, r);
    pushup(id);
}

void update(int id, int ul, int ur)
{
    int l = tree[id].tl, r = tree[id].tr;
    if (ul <= l && r <= ur && tree[id].mx <= 2) return ;
    if(l == r){
        tree[id].val = tree[id].mx = d[a[l]];
        a[l] = d[a[l]];
        return ;
    }
    int mid = (l+r) >> 1;
    if (ul <= mid) update(id<<1, ul, ur);
    if (ur > mid) update(id<<1|1, ul, ur);
    pushup(id);
}

ll ans ;
void query(int id, int ql, int qr)
{
    int l = tree[id].tl, r = tree[id].tr;
    if(ql <= l && r <= qr ) {
        ans += tree[id].val;
        return ;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) query(id<<1, ql, qr);
    if (qr > mid) query(id<<1|1, ql, qr);
}

void solve()
{
    int n, q; init();
    scanf("%d%d",&n, &q);
    for(int i = 1 ; i <= n ; i ++) {
        scanf("%lld", &a[i]);
    }
    build(1, 1, n);
    while(q--){
        int op, l, r;
        scanf("%d%d%d",&op, &l, &r);
        if(op == 1){
            update(1, l, r);
        }
        else {
            ans = 0; query(1, l, r);
            printf("%lld\n", ans);
        }
    }
}

G:
定义L(x, p)表示的一个无限的序列, 其中的数为y (y > x)，且gcd(y, p) == 1. 现在给出t次询问, 每次给出x p k 询问L(x, p)数列的第k大是那个数.

很明显第k大用二分来做, 就是如何check这个二分的ans, 问题就转变为这个ans 和 p 互质的问题, 那么很容易想到判断k大的条件就是和p互质的num(1 - ans) - num(1 - x) == k , 并且ans要尽可能的小, 那么明显问题就变成了求1-n 中和p互质的个数, 这就是容斥啊.

AC Code

vector<int>ve;
void cal(int n) {
    ve.clear();
    for (int i = 2 ; i*i <= n ; i ++) {
        if (n % i == 0) {
            while(n % i == 0) n /= i;
            ve.pb(i);
        }
    }
    if (n != 1) ve.pb(n);
}
ll rongchi(ll x) // 求1-x中和p互质的个数.
{
    ll sum = 0;
    for (int i = 1 ; i < (1<<sz(ve)) ; i ++ ) {
        ll tmp = 1 , cnt = 0;
        for (int j = 0 ; j < sz(ve) ; j ++) {
            if (i & (1<<j)) {
                tmp *= ve[j];
                cnt++;
            }
        }
        if (cnt & 1)  sum += x / tmp;
        else sum -= x / tmp;
    }
    return x - sum;
}
void solve()
{
    int x, p, k;
    scanf("%d%d%d", &x, &p, &k);
    cal(p);
    ll num1 = rongchi((ll)x);
    ll l = x + 1 , r = inf, mid, ans;
    while(r >= l) {
        mid = (l + r) >> 1;
        ll num2 = rongchi(mid);
        if (num2 - num1 >= k) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    printf("%lld\n", ans);
}