CodeForces Round #514 (div2)

题意：问可以休息多少次。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 1e5 + ;

int n, L, a;

int t[N], l[N];

int main(){

    scanf("%d%d%d", &n, &L, &a);

    for(int i = ; i <= n; ++i)

        scanf("%d%d", &t[i], &l[i]);

    t[n+] = L;

    t[] = l[] = ;

    int ans = ;

    for(int i = ; i <= n; ++i){

        int dif = t[i+] - t[i] - l[i];

        ans += dif/a;

    }

    cout << ans << endl;

    return ;

}

B：B - Forgery

题意：一次能给边上一圈填上'#'，问这个图形合法不合法。填的时候不能越界。

直接去check行不行就好啦。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 1e3 + ;

char s[N][N];

int dx[] = {,,,,,,,};

int dy[] = {,,,,,,,};

int n, m;

bool in(int x, int y){

    if(x <  || x > n) return false;

    if(y <  || y > m) return false;

    return true;

}

bool check2(int x, int y){

    for(int i = ; i < ; ++i){

        int xx = x + dx[i];

        int yy = y + dy[i];

        if(!in(xx,yy) || s[xx][yy] != '#') return false;

    }

    return true;

}

bool check(int x, int y){

    for(int b = ; b < ; ++b){

        if(check2(x-dx[b], y-dy[b]))  return true;

    }

    return false;

}

int main(){

    scanf("%d%d", &n, &m);

    for(int i = ; i <= n; ++i) scanf("%s", s[i]+);

    for(int i = ; i <= n; ++i)

        for(int j = ; j <= m; ++j){

            if(s[i][j] == '#'){

                if(!check(i,j)){

                    puts("NO");

                    return ;

                }

            }

    }

    puts("YES");

    return ;

}

C：C - Sequence Transformation

题意：给你[1,n]的数，每次会输出整个序列的gcd，然后可以删除一个数，然后问gcd的字典序排列最大是多少。

题解：发现如果存在奇数，然后我们就会导致 gcd恒为1。那么我们肯定是先删除奇数。

然后把奇数删完了之后，剩下了2,4,6,8,我们把这些数都/2，变成了新的1,2,3,4,然后再删除奇数就ok了。递归解决问题。

然后就是如果出现了 1, 2, 3。那么肯定是按照顺序删除 1 2 3最好了。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 1e5 + ;

int n;

vector<int> vc;

void dfs(int k, int n){

    if(n == ) return ;

    if(n == ){

        printf("%d %d %d", k, k, k*);

        return ;

    }

    if(n == ){

        printf("%d ", k);

        return ;

    }

    if(n == ){

        printf("%d %d", k, *k);

        return ;

    }

    for(int i = ; i <= n; i += ){

        printf("%d ", k);

    }

    dfs(k*, n/);

}

int main(){

    scanf("%d", &n);

    dfs(, n);

    return ;

}

D：D - Nature Reserve

题意：有n个保护动物，然后就是让你画一个○，使得所有的动物都在圈内，并且只有1个交点。

不是很想多讲，二分乱搞就好了，注意精度。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 1e5 + ;

pll p[N];

int n, f1 = , f2 = ;

double eps = 1e-;

bool check2(double x1, double y1, double x2, double y2){

    long double len = y2;

    len *= len;

    long double dis = (long double)(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);

    return len >= dis;

}

bool check(double len){

    double lp = -1e7, rp = 1e7;

    for(int i = ; i <= ; ++i){

        int lsz = , rsz = ;

        double mid = (lp+rp) / ;

        for(int k = ; k <= n; ++k){

            if(check2(p[k].fi,p[k].se,mid,len));

            else if(p[k].fi <= mid ) lsz++;

            else rsz++;

        }

        if(lsz && rsz) return false;

        if(lsz+rsz == ) return true;

        if(lsz) rp = mid;

        else lp = mid;

    }

    return false;

}

int main(){

    scanf("%d", &n);

    for(int i = ; i <= n; ++i){

        scanf("%d%d", &p[i].fi, &p[i].se);

        if(p[i].se > ) ++f1;

        else ++f2, p[i].se = -p[i].se;

    }

    if(f1 && f2){

        puts("-1");

        return ;

    }

    double l = , r = 1e15;

    for(int i = ; i <= ; ++i){

        double mid = (l+r)/;

        if(check(mid)) r = mid;

        else l = mid;

    }

    printf("%.10f", r);

    return ;

}

E：Split the Tree

题意：给定1棵以1为根的树，让你将这棵数分成竖着的几条链，问链最少是多少条，并且每一条链要求点的个数少于L，路径之和少于S。

题解：

从叶子网上爬，然后通过二分和倍增查看最多能到哪里，然后将这个点指到可以去的那个点为止。

然后不是叶子就接受叶子传上来的最远可以到哪里，如果到不了这个点就把这个点当做新的起点继续去找，如果可以到这个点就记录下最远可以去哪里就好了。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 1e5 + ;

int anc[N][];

int a[N];

LL sum[N];

int n, l; LL S;

vector<int> vc[N];

int deep[N];

void dfs(int o){

    for(int x : vc[o]){

        deep[x] = deep[o] + ; sum[x] = sum[o] + a[x];

        anc[x][] = o;

        for(int i = ; i < ; ++i)

            anc[x][i] = anc[anc[x][i-]][i-];

        dfs(x);

    }

}

int get(int o, int k){

    for(int i = ; i >= ; --i){

        if((k>>i)&) o = anc[o][i];

    }

    return o;

}

int to[N];

int ans;

int Find(int o){

    int ll = , rr = l;

    while(ll <= rr){

        int mid = ll+rr >> ;

        int p = get(o, mid);

        if(sum[o]-sum[p] <= S) ll = mid+;

        else rr = mid-;

    }

    return get(o, ll-);

}

void solve(int o){

    to[o] = -;

    for(int x : vc[o]){

        solve(x);

        if(to[x] == - || deep[to[x]] >= deep[o]) continue;

        if(to[o] == -) to[o] = to[x];

        else if(deep[to[o]] > deep[to[x]]) to[o] = to[x];

    }

    if(to[o] == -) ans++, to[o] = Find(o);

}

int main(){

    scanf("%d%d%lld", &n, &l, &S);

    for(int i = ; i <= n; ++i){

        scanf("%d", &a[i]);

        if(a[i] > S){

            puts("-1");

            return ;

        }

    }

    for(int i = ,v; i <= n; ++i){

        scanf("%d", &v);

        vc[v].pb(i);

    }

    sum[] = a[]; deep[] = ;

    dfs(); solve();

    cout << ans << endl;

    return ;

}

巴特西

CodeForces Round #514 (div2)

最新文章

热门文章