Codeforces Round #514 (Div. 2)

Codeforces Round #514 (Div. 2)

https://codeforces.com/contest/1059

A

#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 10000005
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,int>pli;
typedef pair<int,char> pic;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long mod=1e9+7;
const double oula=0.57721566490153286060651209;
using namespace std;

int n,L,k;
vector<pii>ve;

int main(){
    std::ios::sync_with_stdio(false);
    cin>>n>>L>>k;
    int x,y;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        ve.pb({x,y});
    }
    int ans=0;
    int pos=0;
    for(int i=0;i<ve.size();i++){
        if(ve[i].first-pos>=k) ans+=(ve[i].first-pos)/k;
        pos=ve[i].first+ve[i].second;
    }
    if(L-pos>=k){
        ans+=(L-pos)/k;
    }
    cout<<ans<<endl;


}

B

模拟

#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 10000005
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,int>pli;
typedef pair<int,char> pic;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long mod=1e9+7;
const double oula=0.57721566490153286060651209;
using namespace std;

int n,m;
string str[1005];
bool book[1005][1005];

void Check(int x,int y){
    if(str[x][y]=='#'&&str[x][y+1]=='#'&&str[x][y+2]=='#'&&str[x+1][y]=='#'&&str[x+1][y+2]=='#'&&str[x+2][y]=='#'&&str[x+2][y+1]=='#'&&str[x+2][y+2]=='#'){
       book[x][y]=1;book[x][y+1]=1;book[x][y+2]=1;book[x+1][y]=1;book[x+1][y+2]=1;book[x+2][y]=1;book[x+2][y+1]=1;book[x+2][y+2]=1;
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>str[i];
    for(int i=0;i<n-2;i++){
        for(int j=0;j<m-2;j++){
            Check(i,j);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(str[i][j]=='#'){
                if(!book[i][j]){
                    cout<<"NO"<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"YES"<<endl;
}

C

数论

题意：给出n,有值为1-n的数字，每去掉一个值后输出剩下值的gcd，使输出的字典序最大

思路：因为相邻的两个数互质，所以要先把奇数都去掉，剩下的都是2的倍数，然后再去掉2,6,10..这样的数，使剩下的都是4的倍数，以此类推

有种情况是剩下的数为3个，比如 x,2x,3x,这样的话，gcd的值为x,x,3x

#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 10000005
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,int>pli;
typedef pair<int,char> pic;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long mod=1e9+7;
const double oula=0.57721566490153286060651209;
using namespace std;


int main(){
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int nn=(n+1)/2;
    int ans=1;
    if(n==3){
        cout<<ans<<" "<<ans<<" "<<ans*3<<endl;
        return 0;
    }
    while(n){
        for(int i=1;i<=nn;i++) cout<<ans<<" ";
        ans<<=1;
        n>>=1;
        nn=(n+1)/2;
        if(n==3){
            cout<<ans<<" "<<ans<<" "<<ans*3<<endl;
            break;
        }
    }
}

D

二分+几何

题意：给定n个点，求最小圆半径，使圆可以覆盖这n个点且与x轴相交

思路：二分圆的半径，遍历每个点，求该点可以被圆覆盖的区间，最后看看区间是否有交集

#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 10000005
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double>pdd;
typedef pair<int,char> pic;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long mod=1e9+7;
const double oula=0.57721566490153286060651209;
using namespace std;

vector<pdd>ve;

int sgn(double x){
    if(x<0) return -1;
    if(x<eps) return 0;
    return 1;
}

bool Check(double mid){
    double L=-100000000000000000.0,R=100000000000000000.0,dist;
    for(int i=0;i<ve.size();i++){
        if(ve[i].second>mid*2) return false;
        dist=sqrt(2*mid*ve[i].second-ve[i].second*ve[i].second);
        if(L<ve[i].first-dist) L=ve[i].first-dist;
        if(R>dist+ve[i].first) R=dist+ve[i].first;
    }
    return L<R;
}

int main(){
    double x,y;
    int n;
    scanf("%d",&n);
    int flag1=0,flag2=0;
    for(int i=1;i<=n;i++){
        scanf("%lf %lf",&x,&y);
        ve.pb({x,y});
        if(y>0) flag1=1;
        else if(y<0) flag2=1;
    }
    if(flag1&&flag2){
        puts("-1");
        return 0;
    }
    for(int i=0;i<ve.size();i++){
        ve[i].second=fabs(ve[i].second);
    }
    double L=0,R=100000000000000000.0,mid;
    for(int i=1;i<=100;i++){///因为精度问题调不好，所以直接用for循环。。。
        mid=(L+R)/2;
        if(Check(mid)){
            R=mid;
        }
        else{
            L=mid;
        }
    }
    printf("%.7f
",L);

}

E

贪心+倍增

题意：问一棵树最少可以被分为多少条垂直路径，路径长小于等于L，点权值之和小于等于S

思路：一个个点暴力过去会超时，所以用倍增法，看看一个点最多可以向上走多少个点，符合条件就选择

#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 100005
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double>pdd;
typedef pair<int,char> pic;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long mod=1e9+7;
const double oula=0.57721566490153286060651209;
using namespace std;

ll n,L,S;
ll a[100005];
vector<int>ve[100005];
ll parent[maxn][35],val[maxn][35];
int len[maxn];
int ans;

void dfs1(int now){
    for(int i=0;i<ve[now].size();i++){
        parent[ve[now][i]][0]=now;
        val[ve[now][i]][0]=a[now];
        dfs1(ve[now][i]);
    }
}

ll dfs2(int now){
    ll sum=0;
    for(int i=0;i<ve[now].size();i++){
        sum=max(sum,dfs2(ve[now][i]));
    }
    if(sum==0){
        ans++;
        return len[now]-1;
    }
    return sum-1;
}

int main(){
    cin>>n>>L>>S;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]>S){
            cout<<-1<<endl;
            return 0;
        }
    }
    int x;
    for(int i=2;i<=n;i++){
        cin>>x;
        ve[x].pb(i);
    }
    dfs1(1);
    for(int i=1;i<=18;i++){
        for(int j=1;j<=n;j++){
            parent[j][i]=parent[parent[j][i-1]][i-1];
            val[j][i]=val[parent[j][i-1]][i-1]+val[j][i-1];
        }
    }
    for(int i=1;i<=n;i++){
        ll sum=a[i],now=i;
        len[i]=1;
        for(int j=18;j>=0&&sum<=S&&len[i]<=L;j--){
            if(parent[now][j]&&sum+val[now][j]<=S&&len[i]+(1<<j)<=L){
                sum+=val[now][j];
                now=parent[now][j];
                len[i]+=(1<<j);
            }
        }
    }
    dfs2(1);
    cout<<ans<<endl;
}