Codeforces Round #409 Div2题解

比赛链接：http://codeforces.com/contest/801

A. Vicious Keyboard

题意：给出一个只含VK的字符串，你可以把其中一个换成另一个，问最多有几个VK

解法：暴力替换

#include <bits/stdc++.h>
using namespace std;
int cal(string s){
    int sz=s.size();
    int ans=0;
    for(int i=0;i<sz-1;i++) if(s[i]=='V'&&s[i+1]=='K') ans++;
    return ans;
}

int main(){
    string s;
    cin>>s;
    int ans=cal(s);
    int sz=s.size();
    for(int i=0; i<sz; i++){
        if(s[i]=='V'){
            s[i]='K';
            ans = max(ans, cal(s));
            s[i]='V';
        }else{
            s[i]='V';
            ans = max(ans, cal(s));
            s[i]='K';
        }
    }
    printf("%d\n", ans);
    return 0;
}

B. Valued Keys

题意：定义一个对两个字符串x,y的f(x,y)函数，返回的是一个字符串。这个返回的字符串的每一位i是x和y在相应位置上的字符的较小值。告诉你x和f(x,y)，求y。

解法：贪心。看代码

#include <bits/stdc++.h>
using namespace std;
char z[110];
int main(){
    string x,y;
    cin>>x>>y;
    int sz=x.size();
    for(int i=0;i<sz;i++){
        if(x[i]==y[i]){
                z[i]='z';
        }else if(y[i]>x[i]){
            puts("-1");
            return 0;
        }else{
            z[i]=y[i];
        }
    }
    printf("%s\n", z);
    return 0;
}

C. Voltage Keepsake

题意：给你n个装置，每个装置每分钟耗电p ，本身储存电c。然后你有一个充电器，（随时充，转移不耗时，想怎么换着充都行）。问你让所有装置都能保持工作的最大时间是多少。

解法：可以用x秒，显然小于x秒时也可使用。故考虑二分时间。得到了时间，我们就可以算出p的贡献为p*t。然后遍历每台机器，若cost[i]*t > stored[i], 说明这台机器需要分配资源。所有机器分配完之后的总资源还大于等于0则说明可以运行到t。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
LL n, p;
struct node{
    LL a,b;
}device[maxn];
bool check(double t){
    double sum = (double)p*t;
    for(int i=1; i<=n; i++){
        if(device[i].a*t>device[i].b){
            sum -= (double)(device[i].a*t-device[i].b);
        }
    }
    return sum>=0;
}
int main(){
    scanf("%lld%lld",&n,&p);
    LL sum = 0;
    for(int i=1; i<=n; i++){
        scanf("%lld%lld", &device[i].a,&device[i].b);
        sum += device[i].a;
    }
    if(p>=sum){
        puts("-1");
        return 0;
    }
    double l=0,r=1e18,ans;
    for(int i=0; i<100; i++){
        double mid=(l+r)/2.0;
        if(check(mid)) ans=mid,l=mid;
        else r=mid;
    }
    printf("%.10f\n", ans);
    return 0;
}

D. Volatile Kite

题意：给你一个凸多边形，问至少移动多少距离（每个点都可以移动）使得不是凸多边形

解法：对相邻的三个点来说，选定中间点，使得三个点同时向中间移动直到共线就好，所以转化成点到线段的距离。

#include <bits/stdc++.h>
using namespace std;
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x=_x;
        y=_y;
    }
    Point operator-(const Point &b)const{
        return Point(x-b.x, y-b.y);
    }
    double operator^(const Point&b)const{
        return x*b.y-y*b.x;
    }
    double operator*(const Point&b)const{
        return x*b.x+y*b.y;
    }
};
Point p[1100];
struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e){
        s=_s;
        e=_e;
    }
};
double dist(Point a, Point b){
    return sqrt((a-b)*(a-b));
}
Point NearestPointToLineSeg(Point P,Line L){
    Point result;
    double t=(((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s)));
    if(t>=0 && t<=1){
        result.x = L.s.x+(L.e.x-L.s.x)*t;
        result.y = L.s.y+(L.e.y-L.s.y)*t;
    }else{
        if(dist(P,L.s)<dist(P,L.e)) result = L.s;
        else result = L.e;
    }
    return result;
}
int n;
double solve(int i){
    int pre=(i-1+n)%n;
    int afe=(i+1)%n;
    Line L;
    L.s=p[pre],L.e=p[afe];
    Point now=p[i];
    Point Next=NearestPointToLineSeg(now,L);
    double ans=dist(now,Next);
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lf%lf", &p[i].x,&p[i].y);
    }
    double ans = 1e18;
    for(int i=0;i<n;i++){
        ans = min(ans, solve(i)/2);
    }
    printf("%.10f\n", ans);
    return 0;
}

E. Vulnerable Kerbals

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
typedef long long LL;
vector<int>ans,G[maxn],b[maxn];
bool vis[maxn];
int dp[maxn],pre[maxn];
LL exgcd(LL a, LL b, LL &x, LL &y){
    LL d = a;
    if(b!=0){
        d=exgcd(b,a%b,y,x),y-=(a/b)*x;
    }else{
        x=1,y=0;
    }
    return d;
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    vis[0]=0;
    while(n--){
        int x;
        scanf("%d",&x);
        vis[x]=1;
    }
    for(int i=1; i<m; i++){
        if(!vis[i]) b[__gcd(i,m)].push_back(i);
    }
    for(int i=1; i<m; i++)
        for(int j=i+i;j<m;j+=i) G[i].push_back(j);
    int t=0;
    for(int i=1; i<m; i++){
        int sz=b[i].size();
        dp[i]=max(dp[i],sz);
        for(int j=0;j<G[i].size();j++){
            int v=G[i][j];
            int tmp=dp[i]+b[v].size();
            if(dp[v]<tmp){
                dp[v]=tmp;
                pre[v]=i;
            }
        }
        if(dp[i]>dp[t]){
            t=i;
        }
    }
    while(t){
        for(int i=0;i<b[t].size();i++) ans.push_back(b[t][i]);
        t=pre[t];
    }
    printf("%d\n", ans.size()+(!vis[0]));
    reverse(ans.begin(),ans.end());
    if(!ans.empty()){
        LL a=ans[0];
        printf("%d", ans[0]);
        for(int i=1;i<ans.size();i++){
            LL x=0,y=0;
            LL b=m;
            LL g = exgcd(a,b,x,y);
            x=x*(ans[i]/g);
            x=(x%m+m)%m;
            printf(" %lld", x);
            a=a*x%m;
        }
    }
    if(!vis[0]) printf(" 0\n");
    else printf("\n");
    return 0;
}

有一个交流帖，链接如下：http://tieba.baidu.com/p/5076330276