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
", 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 ?'
':' ');
    }
}

C:長さnの配列を与える.1つの文字列が与える、文字列のi番目の文字が"1"であれば、この配列に対応するi番目の位置がi+1番目の位置と入れ替わることができる、回数に制限はない.この配列を1-nの全配列に変えることができるかどうかを聞く.
私のやり方は暴力で、一連の連続した1に1位を加えて、この一連は元の配列に対応して必ず対応する位置の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
");
        else printf("NO
");
    }
}

E:n個の頂点の無方向完全図を与え、m個の辺を削除し、削除後のこの図の連通ブロックの個数とその各ブロックの大きさを問う.このインターフェースブロックの定義は、2つの点の間でのみ彼らが1つのインターフェースブロックに属することに注意する.(辺と混同しないで)
各点を暴力的に高くすることはできません.1つの点は最大1つのインターフェースブロックにしかないので、私たちはまずこれらの点をすべて保存して、それから1つの点にアクセスして1つの点を削除して、対応する数++でいいです.この削除はstlライブラリで行うのが一番いいです.
!!! しかし、削除反復器にかかわることに注意してvectorを使わないでください.この削除は不思議で、遅いです.Tができます.そして、他の私も知らないことがあります.vectorを使わないでください.
ではsetで(listなどでもいい)、bfsでいいです.
AC Code

int n, m;
mapbool>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
", sz(ans));
    for (int i = 0 ; i < sz(ans) ; i ++) {
        printf("%d%c", ans[i], i == sz(ans)?'
':' ');
    }
}

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]Σi=l r a[i]を求めるもちろん我々はまずnlognでd配列を前処理し,その後この問題は古典的な区間更新における単点更新であり,この問題は一般的に各点が修正される回数が限られているが,ここでは6回程度修正されるべきである(a[i]<=2の場合に修正するのは意味がない),したがって区間max値を1つ維持する必要がある.修正された区間に区間の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
", ans);
        }
    }
}

G:L(x,p)が表す無限のシーケンスを定義し、その数はy(y>x)であり、gcd(y,p)==1である.ここでt回の質問をする、x p kの質問L(x,p)の数列を与えるたびにk番目に大きいのはその数である.
明らかにk番目に大きいのは2点で、どのようにこの2点のansをcheckして、問題はこの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<1 , cnt = 0;
        for (int j = 0 ; j < sz(ve) ; j ++) {
            if (i & (1<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
", ans);
}