Codeforces Round #409 문제 해결 보고서

801A - Vicious Keyboard
아프다고 말할 수 밖에 없어,systest 카드에 걸렸어.제목: V, K 자모로 구성된 문자열을 주고 임의로 한 문자를 바꾸면 VK 자열의 수량이 가장 크다Solution: VK 수량을 찾고 3중대 K, 또는 3중대 V를 찾거나 시작이 KKV이거나 끝 VVK인 경우 N==2를 주의하여 특판해야 한다.

//Author: Lixiang
#include
#include
const int maxl=101;
struct A{
    char s[maxl];
    int N,cnt;
    void init(){
        scanf("%s",s);
        N=strlen(s);
        for(int i=0;i1;i++)
            if(s[i]=='V'&&s[i+1]=='K')cnt++;
    }
    void work(){
        int flag=0;
        for(int i=0;i2;i++)
            if(s[i]==s[i+1]&&s[i+1]==s[i+2]){
                flag=1;
                break;
            }
        if(N==2){
            if(s[0]==s[1])flag=1;
        }
        else{
            if(s[0]=='K'&&s[1]=='K'&&s[2]=='V')flag=1;
            if(s[N-1]=='V'&&s[N-2]=='V'&&s[N-3]=='K')flag=1;
        }
        printf("%d
",cnt+flag);
    }
}sol;
int main(){
    sol.init();
    sol.work();
    return 0;
}

801B - Valued Keys
수제

//Author: Lixiang
#include
#include
struct B{
    char a[101],b[101],c[101];
    int N;
    void init(){
        scanf("%s%s",a,c);
        N=strlen(a);
    }
    void work(){
        for(int i=0;iif(a[i]>=c[i])b[i]=c[i];
            else{
                puts("-1");
                return ;
            }
        }
        puts(b);
    }
}sol;
int main(){
    sol.init();
    sol.work();
    return 0;
}

800A - Voltage Keepsake
제목: 각 설비마다 단위 시간마다Ai를 소모하고 초기 저장 전력은 Bi이다. 한 충전기는 단위 시간마다 특정한 설비에 P를 충전할 수 있다. 특정한 설비의 전력이 0일 때 모든 작업이 끝나고 설비 작업의 가장 긴 시간을 구한다.Solution: 2점 + 욕심

//Author: Lixiang
#include
#include
using namespace std;
const int maxn=100001;
struct Node{
    long double a,b;
};
struct C{
    Node d[maxn];
    long double P,L,mm;
    int N;
    long double ss;
    void init(){
        ios::sync_with_stdio(false);
        L=0;mm=0;
        cin>>N>>P;
        for(int i=1;i<=N;i++){
            cin>>d[i].a>>d[i].b;
            d[i].b*=100000;
        }
    }
    bool check(long double M){
        long double sum=0;
        for(int i=1;i<=N;i++){
            if(d[i].a*Mcontinue;
            sum+=(d[i].a*M-d[i].b)/P;
            if(sum>M)return 0;
        }
        return 1;
    }
    void work(){
        long double R=1e18,M;
        long double ans=-1;
        while((R-L)>1){
            M=(L+R)/2.0;
            if(check(M)){
                L=M;
                ans=M;
            }
            else R=M;
        }
        if(ans>1e16)puts("-1");
        else cout<100000.0;
    }
}sol;
int main(){
    sol.init();
    sol.work();
    return 0;
}

800B - Volatile Kite
볼록 패키지를 한 번 구하고 연속된 세 개의 점에서 직선 거리 d,ans=min{d/2}까지 구체적으로 코드를 구합니다.

//Author: Lixiang
#include
#include
#include
using namespace std;
int n,top;
double ans;
struct data{
   double x,y;
}p[10001],s[10001];
double mul(data p1,data p2,data p0){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double dis(data a,data b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline bool cmp(data a,data b)
{
    if(mul(a,b,p[0])==0)return dis(a,p[0])0]);
    return mul(a,b,p[0])>0;
}
double dis2(data p1,data p2,data p3){
    double x1=p1.x,y1=p1.y,x2=p3.x,y2=p3.y,x=p2.x,y=p2.y;
    double A=y2-y1,B=x1-x2,C=x2*y1-x1*y2;
    return (A*x+B*y+C)/2.0/sqrt(A*A+B*B);
}
void graham(){
    top=2;data t;
    int k=0;
    for(int i=1;iif((p[k].y>p[i].y)||(p[k].y==p[i].y&&p[k].x>p[i].x))k=i;
    t=p[0];p[0]=p[k];p[k]=t;
    sort(p+1,p+n,cmp);
    s[0]=p[0],s[1]=p[1],s[2]=p[2];
    for(int i=3;iwhile(top&&mul(p[i],s[top],s[top-1])>=0)
           top--;
        s[++top]=p[i];
    }
    ans=min(dis2(s[top],s[0],s[1]),dis2(s[top-1],s[top],s[0]));
    for(int i=0;i1;i++)
        ans=min(ans,dis2(s[i],s[i+1],s[i+2]));
}
int main(){
    scanf("%d",&n);
    for(int i=0;iscanf("%lf%lf",&p[i].x,&p[i].y);
    graham();
    printf("%.10lf
",ans);
    return 0;
}

800C - Vulnerable Kerbals
Solution: 우리가 구한 접두사 곱셈의 순서가 이런 p1, p2,...라고 가정하면pk .생성된 서열은 a1, a2,......ak, 그럼 꼭 있어.×ai ≡pi(mod m)는 반드시 gcd(pi-4-1, m)|pi가 있을 것이다. (이 관계에 따라 pi-4-1, pi와 사이를 연결하면 하나의 DAG가 된다) 따라서 우리는 접두사로 곱할 수 있는 수를 m의 gcd와 분류할 수 있다. 같은 gcd값을 정점으로 하고 서로 다른 gcd값이 정제 관계를 만족시키면 사이를 만들고 최종적으로DAG를 형성하여 가장 긴 길을 한 번 뛰면 된다.방정식과 같은 풀이를 할 때 넘칠 수 있으니 롱롱을 사용하세요.

#include
#include
#include
using namespace std;
const int maxn=200001;
inline long long gcd(long long a,long long b){
    if(b==0)return a;
    else return gcd(b,a%b);
}
inline long long exgcd(long long a,long long b,long long &x,long long &y){
    long long r=a;
    if(b==0)x=1,y=0;
    else{
        r=exgcd(b,a%b,x,y);
        long long t=x;
        x=y;
        y=t-a/b*y;
    }
    return r;
}
long long Equa(long long a,long long b,long long n){
    long long x,y,x0,i;
    long long d=exgcd(a,n,x,y);
    x0=x*(b/d)%n;
    while(x0<0)x0=(x0+n/d)%n;
    return x0;
}
struct E{
    vector <int> ADJL[maxn];
    stack <long long> seq;
    int cnt[maxn],f[maxn],fa[maxn],N,M;
    bool ban[maxn];
    void init(){
        scanf("%d%d",&N,&M);
        for(int i=1,t;i<=N;i++){
            scanf("%d",&t);
            ban[t]=1;
        }
        for(int i=0;iif(!ban[i]){
                cnt[gcd(i,M)]++;
                ADJL[gcd(i,M)].push_back(i);
            }
    }
    void work(){
        vector <int>::iterator it;
        int ans=0,st;
        long long last;
        for(int i=0;i<=M;i++){
            if(cnt[i]==0)continue;
            for(int j=0;jif(cnt[j]==0)continue;
                if(i%j!=0)continue;
                if(f[j]>f[i]){
                    f[i]=f[j];
                    fa[i]=j;
                }
            }
            f[i]+=cnt[i];
            if(f[i]>ans){
                ans=f[i];
                st=i;
            }
        }
        while(st!=0){
            for(it=ADJL[st].begin();it!=ADJL[st].end();it++)
                seq.push(*it);
            st=fa[st];
        }
        printf("%d
",ans);
        if(ans==0)return;
        printf("%I64d",seq.top());
        last=seq.top();
        seq.pop();
        while(!seq.empty()){
            printf(" %I64d",Equa(last,seq.top(),M));
            last=seq.top();
            seq.pop();
        }
        puts("");
    }
}sol;
int main(){
    sol.init();
    sol.work();
    return 0;
}