周末作业20170410

题解

A - Binary Simulation

题目链接
题目大意：

一串2进制串，给出一些区间，将每个区间的每个数取反，经过一些变幻候，求一个位置上的数位多少

解题思路：

线段树，树状数组，[a,b]在树状数组中将a到n的相关数+1；然后在b+1到n相关数-1；这样就实现了对一个区间的操作，最后算出这个数被操作了几次，偶数次则不变，奇数次则取反

AC代码：

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

using namespace std;
const int maxn=1e5+5;
char s[maxn<<4],c;
int bit[maxn<<4],len;
int lowbit(int x){
    return x&(-x);    //与其相反数按位取反，奇数等于1，2的次幂等于本身，其余偶数等于2的最高次幂（例如：6等于2.10等于3）
}
void add(int x,int val){
    while(x<=len){
        bit[x]+=val;
        x+=lowbit(x);
    }
}
void updata(int x,int y){
    add(x,1);
    add(y+1,-1);
}
int sum(int x){
    int ans=0;
    while(x){
        ans+=bit[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    int T,ncase=0,n,a,b;
    scanf("%d",&T);
    char str[5];
    while(T--){
        memset(bit,0,sizeof(bit));
        scanf("%s",s);
        len=strlen(s);
        scanf("%d",&n);
        printf("Case %d:\n",++ncase);
        for(int i=0;i<n;i++){
            scanf("%s",str);
            if(str[0]=='I'){
                scanf("%d%d",&a,&b);
                updata(a,b);
            }
            else {

                scanf("%d",&a);
                if(sum(a)%2==0)
                    printf("%c\n",s[a-1]);
                else {
                    if(s[a-1]=='1')
                        printf("0\n");
                    else printf("1\n");
                }
            }
        }
    }
    return 0;
}

**B - Points in Segments **
题目链接
题目大意：

在数轴上给出一些数，然后给出一些区间，求出每个区间在数轴上有多少个数

解题思路：

因为是有序的，用upper_bound（b）-lower_bound（a）即可，即为区间在数轴上的数字个数

AC代码：

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

using namespace std;
typedef long long LL;
LL a[100005],x,y;
int T,ncase,n,m;
int main(){
    scanf("%d",&T);
    while(T--){
        printf("Case %d:\n",++ncase);
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            scanf("%lld",a+i);
        for(int i=0;i<m;i++){
                scanf("%lld%lld",&x,&y);
            int ans=upper_bound(a,a+n,y)-a;
            ans-=lower_bound(a,a+n,x)-a;
            printf("%d\n",ans);
        }
    }
}

C - Calm Down
题目链接
题目大意：

给出大圆半径R和相同小圆的个数n，大圆与每个小圆相切，相邻小圆相切，求小圆半径r

解题思路：

因为相切，所以相邻的两个小圆心到大圆心构成一个等腰三角形，(R-r)*sin((2pi/n)/2)=r，开始以为答案是整数就必须输出整数，结果不是

AC代码：

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

using namespace std;
const double pi=acos(-1.0);
int main(){
    double R,ans;
    int n,T,ncase=0;
    scanf("%d",&T);
    while(T--){
        scanf("%lf%d",&R,&n);
        ans=(R*sin(pi/n))/(1+sin(pi/n));

        printf("Case %d: %.10f\n",++ncase,ans);
    }
    return 0;
}

**D - Neighbor House **
题目链接
题目大意：

有一些邻居需要粉刷墙体，现有3种颜色且每个人的每个颜色消耗各不相同，但是相邻的两个颜色不能相同，求满足条件的最小消耗

解题思路：

每当考虑一个人粉刷时，就应该考虑他的上一个邻居是什么颜色（如这个是1，上个就只能是2，3），dp【i】【j】表示第i个人刷第i中颜色

AC代码：

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

using namespace std;
int val[25][5],dp[25][6];
int main(){
    int T,ncase=0,n;
    scanf("%d",&T);
    while(T--){
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=3;j++)
                scanf("%d",&val[i][j]);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=3;j++){
                if(j==1)
                    dp[i][j]=val[i][j]+min(dp[i-1][7],dp[i-1][6]);
                else if(j==2)
                    dp[i][j]=val[i][j]+min(dp[i-1][7],dp[i-1][8]);
                else dp[i][j]=val[i][j]+min(dp[i-1][9],dp[i-1][10]);
            }
        }
        int ans=0x3f3f3f3f;
        for(int i=1;i<=3;i++)
            ans=min(ans,dp[n][i]);
        printf("Case %d: %d\n",++ncase,ans);
    }
    return 0;
}

E - Array Queries
题目链接
题目大意：

给出一组数字，然后给出一些区间，求每个区间的最小值

解题思路：

线段树，在线段树种保存每个区间的最小值

AC代码：

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

using namespace std;
int mtree[400005];
void build(int k,int l,int r){
    if(l==r){
        scanf("%d",&mtree[k]);
        return ;
    }
    int mid=(r+l)>>1;
    build(k<<1,l,mid);
    build((k<<1)|1,mid+1,r);
    mtree[k]=min(mtree[k<<1],mtree[(k<<1)|1]);
}
int findx(int k,int l,int r,int a,int b){
    if(l>=a&&r<=b)
        return mtree[k];
    int mid=(r+l)>>1,ans=0x3f3f3f3f;
    if(mid>=a)
        ans=min(ans,findx(k<<1,l,mid,a,b));
    if(mid<b)
        ans=min(ans,findx((k<<1)|1,mid+1,r,a,b));
    return ans;

}
int main(){
    int T,n,m,ncase=0,x,y;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        build(1,1,n);
        printf("Case %d:\n",++ncase);
        for(int i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            int ans=findx(1,1,n,x,y);
            printf("%d\n",ans);
        }
    }
    return 0;
}

F - Farthest Nodes in a Tree
题目链接
题目大意：

给出一棵树，求这棵树的直径

解题思路：

现bfs出一个点走的最大的端点，在bfs这个点找到最大值，即为这棵树的直径

AC代码：

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

using namespace std;
struct node {
    int from,to,w,nxt;
}a[30005<<1];
int head[30005],vis[30005],sum[30005],ans,num,n,node;
void addedge(int u,int v,int w){
    a[num].from=u;
    a[num].to=v;
    a[num].w=w;
    a[num].nxt=head[u];
    head[u]=num++;
}
void bfs(int s){
    memset(vis,0,sizeof(vis));
    memset(sum,0,sizeof(sum));
    vis[s]=1;
    queue<int > q;
    q.push(s);
    ans=0;
    while(!q.empty()){
       int tp=q.front();
       q.pop();
       for(int i=head[tp];~i;i=a[i].nxt){
            if(!vis[a[i].to]&&sum[a[i].to]<sum[tp]+a[i].w){
                sum[a[i].to]=sum[tp]+a[i].w;
                vis[a[i].to]=1;
                q.push(a[i].to);
                if(ans<sum[a[i].to]){
                    ans=sum[a[i].to];
                    node=a[i].to;
                }
            }
       }
    }
}
int main(){
    int T,ncase=0,u,v,w;
    scanf("%d",&T);
    while(T--){
        num=0;
        memset(head,-1,sizeof(head));
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            addedge(v,u,w);
        }
        bfs(1);
        bfs(node);
        printf("Case %d: %d\n",++ncase,ans);
    }
    return 0;
}