Codeforces Round #392 (Div. 2) 题解

题目链接：http://codeforces.com/contest/758

A. Holiday Of Equality

题意：给n个数，其中最大的为max，求每个数与max的差的绝对值的和。

解法：

#include <bits/stdc++.h>
using namespace std;
int n, a[110];
int main(){
    scanf("%d",&n);
    int mx = 0;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]), mx = max(mx, a[i]);
    if(n==1) return 0*puts("0");
    int ans = 0;
    for(int i=1; i<=n; i++) ans += mx-a[i];
    printf("%d\n", ans);
    return 0;
}

B. Blown Garland

题意：一共有四种颜色的灯RBYG，现在有！处表示这个位子的灯泡坏掉了，我们现在需要在！处放置四种颜色的灯泡，使得最终的序列，保证每连续的四个灯泡都具有四种不同的颜色。问我们需要添加多少个R,B,Y,G.保证答案唯一。

解法：每一段四个字符所在相对位置必须相同，比如abcdabcd，如果abcdbacd的话肯定会有一个区间有重复，这里就是bcdb两个b重复了，所以相对位置必须相同，即每个字符%4都相同。

#include <bits/stdc++.h>
using namespace std;
char s[110];
int res[4];
int tot[4];
int cnt[4];
int main(){
    scanf("%s",s);
    int n=strlen(s);
    for(int i=0; i<n; i++){
        tot[i%4]++;
        if(s[i]=='R') res[0]=i%4,cnt[0]++;
        if(s[i]=='B') res[1]=i%4,cnt[1]++;
        if(s[i]=='Y') res[2]=i%4,cnt[2]++;
        if(s[i]=='G') res[3]=i%4,cnt[3]++;
    }
    for(int i=0;i<4;i++) printf("%d ", tot[res[i]]-cnt[i]);
    return 0;
}

C. Unfair Poll

题意：有n行m列学生，有一位老师在课上会问k个问题，在行上，是按照1，2。。。。n-1，n，n-1.。。。1这样的顺序提问，求学生当中回答问题个数最多和最少的个数，以及在第x行第y位的同学回答的问题数

解法：不难发现，当n>1时，1，2，……，n-1，n，n-1，……3，2为一个循环节，即有2*n-2行，其中每个循环节第1行以及第n行都只回答一次，其他都回答了两次，然后直接用二维数组进行模拟即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL ans[110][110];
int main(){
    int n,m,x,y,t;
    LL k;
    cin>>n>>m>>k>>x>>y;
    if(n>1) t=(2*n-2)*m;
    else t=m;
    for(int i=2; i<n; i++){
        for(int j=1; j<=m; j++){
            ans[i][j]=k/t*2;
        }
    }
    for(int j=1;j<=m;j++) ans[1][j]=ans[n][j]=k/t;
    int p = k%t;
    for(int i=1; i<=n&&p; i++){
        for(int j=1; j<=m&&p; j++){
            if(p){
                ans[i][j]++;
                p--;
            }
        }
    }
    for(int i=n-1; i>1&&p; i--){
        for(int j=1; j<=m&&p; j++){
            if(p){
                ans[i][j]++;
                p--;
            }
        }
    }
    LL mx = -__INT64_MAX__, mi = __INT64_MAX__;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            mx = max(mx, ans[i][j]);
            mi = min(mi, ans[i][j]);
        }
    }
    cout << mx <<" " << mi << " " << ans[x][y] << endl;
    return 0;
}

D. Ability To Convert

题意：给一个n和长度不超过60的数字字符串k，问将k转换为n进制能得到的最小的数字是多少。

解法：dp[i]表示当前位置为i能得到的最小值，然后枚举转移即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[66];
char str[66];
int n, num[66];
int main(){
    scanf("%d%s",&n,str);
    int len = strlen(str);
    LL inf = __INT64_MAX__;
    for(int i=0; i<len; i++){
        num[i+1]=str[i]-'0';
        dp[i+1]=inf;
    }
    dp[0]=0;
    LL now = 0;
    for(int i=1; i<=len; i++){
        now = 0;
        for(int j=i; j<=len; j++){
            now = now*10+num[j];
            if(now>=n) break;
            if(dp[i-1]>=inf/n) break;
            if(num[i]==0&&j>i) break;
            if(dp[i-1]*n>=inf-now) continue;
            dp[j] = min(dp[j], dp[i-1]*n+now);
        }
    }
    printf("%lld\n", dp[len]);
    return 0;
}

E. Broken Tree

题意：对于一棵树有n个点，n-1条边，每条边有4个值x，y，w，p，x是离根进的点，y是另一个点，p和w都是特征值，又定义了broken tree的要求是一条边的p小于它所连子树的所有边的w，要求把给定的树装换成w和最大的非broken树（转换过程中只能减不能加，而且树的的w必定为正整数）

解法：参考：http://blog.csdn.net/bigwaterlon/article/details/54633217

描述来自上面：先分析误解问题，如果一棵树本身有存有边的p小于子树w和的话是一定无解的（因为不能加）。

在分析构造w和最大的树的问题，直接构造有点难度，于是我们不妨先把他变成一颗最小的非broken树，然后再尽可能加回来。

那就是分成两布：

第一步：将给定的树尽可能变小且是非broken的树，每次将这条边减少（p-子树w和）和将本身w变成1的费用的最小值（因为w最少是1），如果过程中发现有存在p小于子树w和的一定无解。从叶子向上。

第二步：将之前转化好的树和原来的树对比，在可以的范围内增加，从根向下。记录可以修改的最大值，对于和根相连的子树可以修改的最大值就是和原来的值的差，之后逐层传递，修改能增加的最大值。

最后输出就好了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1000010;
struct Edge{
    LL x,y,w,p;
}E[maxn], edge[maxn];
LL w[maxn], ww[maxn];
int n;
vector <int> G[maxn];
void dfs1(int x, int y, int id){
    for(int i=0; i<G[y].size(); i++){
        int nextid = G[y][i];
        dfs1(edge[nextid].x,edge[nextid].y,nextid);
    }
    if(id==0) return;
    if(edge[id].p<w[y]){
        puts("-1");
        exit(0);
    }
    LL temp = min(edge[id].w-1,edge[id].p-w[y]);
    edge[id].p-=temp;
    edge[id].w-=temp;
    w[x] += w[y]+edge[id].w;
}
void dfs2(int x, int y, int id, int val){
    if(id!=0){
        LL temp=min((LL)val, E[id].p-edge[id].p);
        edge[id].p+=temp;
        edge[id].w+=temp;
        val = min((LL)(val-temp),edge[id].p-w[y]);
        ww[id]=temp;
    }
    for(int i=0;i<G[y].size();i++){
        int nextid = G[y][i];
        if(id==0) val = 2e9;
        dfs2(edge[nextid].x,edge[nextid].y,nextid,val);
        val -= ww[nextid];
        ww[id] += ww[nextid];
    }
}
int main(){
    scanf("%d", &n);
    for(int i=1; i<n; i++){
        scanf("%lld%lld%lld%lld",&edge[i].x,&edge[i].y,&edge[i].w,&edge[i].p);
        E[i]=edge[i];
        G[edge[i].x].push_back(i);
    }
    dfs1(0,1,0);
    dfs2(0,1,0,2e9);
    printf("%d\n", n);
    for(int i=1; i<n; i++){
        printf("%lld %lld %lld %lld\n", edge[i].x, edge[i].y, edge[i].w, edge[i].p);
    }
    return 0;
}

F. Geometrical Progression
题意：给定 n, l and r ，求项数为n, 公比不为1，且数列每一项都属于[l,r]范围的不同的 等比数列 的个数。

解法：好题，好题。参考博客：http://www.cnblogs.com/smartweed/p/6323297.html

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b){
    return b==0?a:gcd(b,a%b);
}
LL qsm(LL a, LL n){
    LL ret=1;
    while(n){
        if(n&1) ret=ret*a;
        a=a*a;
        n/=2;
    }
    return ret;
}

int main(){
    LL l,r,n,ans=0;
    cin>>n>>l>>r;
    if(n>24) return 0*puts("0");
    if(n==1) return 0*printf("%lld\n",r-l+1);
    if(n==2) return 0*printf("%lld\n", (r-l+1)*(r-l));
    LL fz,fm,up;
    up = pow(2,double(log2(1e7+50)/(n-1)));
    for(LL p=1; p<=up; p++){
        for(LL q=p+1; q<=up; q++){
            if(gcd(p,q)==1){
                fz=qsm(q,n-1);
                fm=qsm(p,n-1);
                if(l*fz/fm>r) continue;
                ans += (r*fm/fz)/fm-(l-1)/fm;
            }
        }
    }
    return 0*printf("%lld\n", ans*2);
}