周末作业20170522

题解

A - The Balance （POJ 2142）

题目详情

题目大意：

给出a，b两种砝码，用两种都尽可能少的砝码，秤出一定重量，如果有多种解法。则输出x+y最小的那一个。

解题思路：

显然是求ax+by=k（扩展欧几里得算法a*x+b*y=Gcd(a,b)的解一定存在，将a，b，k 同除以g=gcd（a，b）然后就变为了（a/g）x+(b/g）y=1,然后将所得答案乘以k ，不过所的答案可能是负的，因为天平可以左右放置。x 的通解为x0 + b*t 吗？
也就是说， a 关于 b的逆元是一个关于b同余的，那么根据最小整数原理，一定存在一个最小的正整数，它是a关于b的逆元，而最小的肯定是在（0，b）之间的，而且只有一个

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;
LL gcd_e(LL a,LL b,LL &x,LL &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    LL ans=gcd_e(b,a%b,x,y);
    LL temp=x;
    x=y;
    y=temp-a/b*y;
    return ans;
}
int main(){
    LL a,b,k;
    while(~scanf("%lld%lld%lld",&a,&b,&k)){
        if(a+b+k==0)
            break;
        LL x,y;
        LL g=gcd_e(a,b,x,y);
        a/=g;
        b/=g;
        k/=g;
        LL x1,y1;
        x1=x*k;
        x1=(x1%b+b)%b;//取最小正整数，
        y1=(k-a*x1)/b;
        if(y1<0) y1=-y1;
        y=y*k;  //反过来先满足y
        y=(y%a+a)%a;
        x=(k-b*y)/a;
        if(x<0) x=-x;
        if(x+y>x1+y1){
            x=x1;y=y1;
        }
        printf("%lld %lld\n",x,y);
    }
    return 0;
}

**C - 开关问题 POJ - 1830 **

题目详情

题目大意：

有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关，最多只能进行一次开关操作。你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序）

解题思路：

高斯消元，建立方程，a[i][j]表示两个开关相关联，n+1列为始末状态是否发生改变（详情见代码）

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int a[35][35];
int gauss(int n){
    int i,j,k;
    for(i=1,j=1;i<=n&&j<=n;j++){//从行遍历
        for(k=i;k<=n&&!a[k][j];k++);//找到第j列不为0的那一行
        if(a[k][j]){
            for(int r=1;r<=n+1;r++)
                swap(a[k][r],a[i][r]);//交换至第i行，确认第i行的数据
            for(int r=1;r<=n;r++){//然后对其他行就行消元
                if(r!=i&&a[r][j]){
                    for(int q=i;q<=n+1;q++)
                        a[r][q]^=a[i][q];//异或
                }
            }
            i++;//对其他行消元后就确定了这一行，i++寻找下一行
        }

    }
    for(int h=i;h<=n;h++){//如果进行了i次消元候，本来后面每一行的所有元素都会为0，如果有a[i~n][n+1]不为0，说明不能完全消元，实现目标
        if(a[h][n+1])
            return -1;
    }
    return 1<<(n-i+1);//自由变量有多少个，每个自由变量都有两种状态
}
int main(){
    int T,x,y,n,k;
    scanf("%d",&T);
    while(T--){
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i][n+1]);
        for(int i=1;i<=n;i++){//看开是结尾的结果是否改变，没变为0，改变为1
            scanf("%d",&k);
            a[i][n+1]^=k;
            a[i][i]=1;
        }
        while(~scanf("%d%d",&x,&y)&&x+y)
            a[y][x]=1;
        int ans=gauss(n);
        if(ans==-1)
            printf("Oh,it's impossible~!!\n");
        else printf("%d\n",ans);
    }
    return 0;
}

E - GCD HDU - 1695

题目详情

题目大意：

（1，b）和（1，d）中各选出一个数使这两个数的gcd为k。问这样的组合有多少种
ps：（1，2）（2,1）算一个

解题思路：

将b，d各自除以k，就变成求两个集合中俩互质数的对数。但是要注意控制一个变量大于另一个。为了不重复，注意用long long
（容斥定理）所有不与x互素的数的个数= 1个因子倍数的个数 - 2个因子乘积的倍数的个数 + 3个……-……

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long LL;
const int N=100005;
vector<int> a[N];
int vis[N];
void prim(){
    memset(vis,0,sizeof(vis));
    for(int i=0;i<N;i++)
        a[i].clear();
    for(int i=2;i<N;i+=2)
        a[i].push_back(2);
    for(int i=3;i<N;i+=2){
        if(!vis[i]){
            for(int j=i;j<N;j+=i){
                vis[j]=1;
                a[j].push_back(i);
            }
        }
    }
}
int solve(int len,int s,int op){//len表示序列长度序列的长度。s表示a【op】中的前几个因子
    int cnt=0,v=1;
    for(int i=0;i<a[op].size();i++){
        if((1<<i)&s){
            cnt++;
            v*=a[op][i];//前s个因子的乘积
        }
    }
    int num=len/v;//len除以v表示以v为因子的数在序列中有几个
    if(cnt%2==0) num=-num;//容斥定理
    return num;
}
int main(){

    int T,ncase=0,h,b,c,d,k;
    prim();
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d%d%d",&h,&b,&c,&d,&k);
        if(k==0){
            printf("Case %d: 0\n",++ncase);
            continue;
        }
        if(b>d) swap(b,d);
        b/=k;
        d/=k;
        LL ans=0;
        for(int i=1;i<=d;i++){
            int len=min(i,b);//因为（1，2）（2,1）算一个，所以严格控制d中选中元素大于等于b中选中元素
            ans+=len;
            for(int j=1;j<(1<<a[i].size());j++)
                ans-=solve(len,j,i);
        }
        printf("Case %d: %lld\n", ++ncase, ans);

    }
    return 0;
}

**F - The Fortified Forest POJ - 1873 **

题目详情

题目大意：

给出一些树，每棵树有坐标，高度，以及价值，要求砍掉一些树，用那些木材，将其它树围起来，要求花最小的代价，代价相同，要求砍掉最少的树。

解题思路：

（凸包，枚举）这道题完全没有思路，但是看见范围只有15，就知道肯定可以暴力，枚举之类的。后面才知道只是求凸包周长

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

struct node{
    int x,y,v,l;
}p[20];

vector<node> a;
double dis(node p1,node p2){//求两点之间的长度
    return sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+((p1.y-p2.y)*(p1.y-p2.y)));
}
int multiply(node p0,node p1,node p2){//求他们的叉积（两个向量）
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool cmp(node p1,node p2){//极坐标排序，逆时钟方向
    if(multiply(a[0],p1,p2)>0) return true;
    else if(multiply(a[0],p1,p2)==0&&dis(a[0],p1)<dis(a[0],p2)) return true;//三点共线，选距离小的
    return false;
}
double Graham(int len){//表示总共砍掉树后的木材
    if(a.size()==1)//只剩下一棵树是，就不需要围了
         return len;
    if((a.size()==2))//剩下两棵树时是距离的两倍（注意：是围起来）
        return len-2*dis(a[0],a[1]);
    for(int i=1;i<a.size();i++){
        if(a[i].y<a[0].y||(a[i].y==a[0].y&&a[i].x<a[0].x))
            swap(a[0],a[i]);//选出最下端的钱（或者是左下端）
    }
    sort(a.begin()+1,a.end(),cmp);
    vector<node> s;
    s.push_back(a[0]);
    s.push_back(a[1]);
    s.push_back(a[2]);
    for(int i=3;i<a.size();i++){
         while(s.size()>=2&&multiply(s[s.size()-2],s[s.size()-1],a[i])<=0)
            s.pop_back();//凹进去的点不考虑了，（假定ABC在图形中心线右边，因为一给点B在AC连线的左侧（称为凹进去），那么AC肯定小于AB+BC）
        s.push_back(a[i]);
    }
    s.push_back(s[0]);//形成一个环
    double ans=0;
    for(int i=0;i<s.size()-1;i++)
        ans+=(dis(s[i],s[i+1]));//求凸包周长
    return len-ans;
}
int n,ncase;
int main(){
    while(~scanf("%d",&n)&&n){
        for(int i=0;i<n;i++)
            scanf("%d%d%d%d",&p[i].x,&p[i].y,&p[i].v,&p[i].l);
        int best_val=0x3f3f3f3f,best_num,best_state;//分别表示最好情况的价值，砍掉的数目
        double best_extra;//最好情况剩下的木材
        for(int i=1;i<(1<<n)-1;i++){//因为数目只有15，用位运算表示砍掉的树
            a.clear();
            int temp_val=0,temp_len=0;
            for(int j=0;j<n;j++){
                if(!((1<<j)&i))
                    a.push_back(p[j]);//存贮剩下的数目
                else{
                    temp_val+=p[j].v;
                    temp_len+=p[j].l;
                }
            }
            if(temp_val>best_val) continue;
            double extra=Graham(temp_len);
            if(extra>=0){//要是剩下的为负数，那么木材不够用，不考虑
                if(temp_val<best_val){
                    best_val=temp_val;
                    best_num=n-a.size();
                    best_state=i;
                    best_extra=extra;
                }
                else if(temp_val==best_val&&(best_num>n-a.size())){//价值相同，砍掉树木数量最少
                    best_num=n-a.size();
                    best_state=i;
                    best_extra=extra;
                }
            }
        }
        printf("Forest %d\nCut these trees:",++ncase);
        for(int i=0;i<n;i++)
            if((1<<i)&best_state)  printf(" %d",i+1);//用位运算找出砍掉的树的数目
        printf("\nExtra wood: %.2f\n\n",best_extra);
    }
    return 0;
}