第二学期第二次训练

A - Binary Simulation

题目大意：给一串二进制数，现在有两种指令：

1.I a b 转换a位到b位的数字（0-1,1-0）
2. Q a 查询第a位数字

解题思路：使用树状数组记录转换次数，询问时根据转换次数决定0还是1

AC代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int bit[100005],n;
char raw[100005];
int lowbit(int x)
{
    return x&(-x);
}
void add(int p,int x)
{
    while (p<=n)
    {
        bit[p]+=x;
        p+=lowbit(p);
    }
}
int sum(int p)
{
    int s=0;
    while (p)
    {
        s+=bit[p];
        p-=lowbit(p);
    }
    return s;
}
int main()
{
    int t,Case=0;
    scanf("%d",&t);
    while (t--)
    {
        memset(bit,0,sizeof(bit));
        scanf("%s",raw);
        n=strlen(raw);
        int tt;
        scanf("%d",&tt);
        printf("Case %d:\n",++Case);
        while(tt--)
        {
            char ch;
            getchar();
            scanf("%c",&ch);
            if (ch=='I')
            {
                int a,b;
                scanf(" %d %d",&a,&b);
                add(a,1);
                add(b+1,-1);
            }
            else
            {
                int a;
                scanf(" %d",&a);
                printf("%d\n",sum(a)%2?1^(raw[a-1]-'0'):(raw[a-1]-'0'));
            }
        }
    }
    return 0;
}

B - Points in Segments

题目大意：给定一串数，按从小到大的标号排好，现有q组询问形如：a,b,表示询问a~b的闭区间内有多少数

解题思路：因为输入数字递增，可以用二分法查找a和b的位置，然后相减

AC代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#define pi acos(0.0)*2
#define maxn 100005
#define INF 1<<30
using namespace std;
int n,q;
int a[100005];
int main()
{
    int t,Case=0;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d",&n,&q);
        printf("Case %d:\n",++Case);
        for (int i=0;i<n;i++) scanf("%d",&a[i]);
        while (q--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int ans=upper_bound(a,a+n,y)-lower_bound(a,a+n,x);
            printf("%d\n",ans);
        }
    }
    return 0;
}

C - Calm Down

题目大意：给出一个圆的半径，在园内部沿着圆周填充n个小圆，使之恰好铺满圆周

解题思路：简单数学题

AC代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define pi acos(0.0)*2
using namespace std;
int main()
{
    int t,Case=0;
    scanf("%d",&t);
    while (t--)
    {
        double R,n,r;
        scanf("%lf%lf",&R,&n);
        double a=sin(pi/n);
        r=R*a/(1+a);
        printf("Case %d: %lf\n",++Case,r);
    }
    return 0;
}

D - Neighbor House

题目大意：有n个房子排成一列，每个房子有三种颜色来粉刷，各有不同的代价，相邻两个房子不能同色，求最少费用

解题思路：dp，状态转移方程：

dp[i][0]=min(dp[i-1][1]+a[i-1][0],dp[i-1][2]+a[i-1][0])
dp[i][1]=min(dp[i-1][0]+a[i-1][1],dp[i-1][2]+a[i-1][1])
dp[i][2]=min(dp[i-1][0]+a[i-1][2],dp[i-1][1]+a[i-1][2])
0,1,2代表不同颜色

AC代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define pi acos(0.0)*2
#define maxn 100005
#define INF 1<<30
using namespace std;
int a[20][3],n,dp[21][3];
int ans;
int main()
{
    int t,Case=0;
    scanf("%d",&t);
    while (t--)
    {
        ans=INF;
        scanf("%d",&n);
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<3;j++)
                scanf("%d",&a[i][j]);
        }
        for (int i=1;i<=n;i++)
        {
            dp[i][1]=min(dp[i-1][0]+a[i-1][1],dp[i-1][2]+a[i-1][1]);
            dp[i][0]=min(dp[i-1][1]+a[i-1][0],dp[i-1][2]+a[i-1][0]);
            dp[i][2]=min(dp[i-1][0]+a[i-1][2],dp[i-1][1]+a[i-1][2]);
        }
        printf("Case %d: %d\n",++Case,min(dp[n][2],min(dp[n][1],dp[n][0])));
    }
    return 0;
}

E - Array Queries

题目大意：给定n个数字，有询问形如：a，b，询问a~b全闭区间内的最小值

解题思路：线段树，每个节点（除了叶子节点）储存区间内最小值，注意空间开4倍，血的教训。

AC代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define pi acos(0.0)*2
#define maxn 100005
#define INF 100005
using namespace std;
int n,dat[4*maxn];
void init(int n_)
{
    n=1;
    while (n<n_) n*=2;
    for (int i=0;i<2*n-1;i++) dat[i]=INF;
}
void update(int k,int a)
{
    k=n-1+k;
    dat[k]=a;
    while (k)
    {
        k=(k-1)/2;
        dat[k]=min(dat[k*2+1],dat[k*2+2]);
    }
}
int query(int a,int b,int k,int l,int r)
{
    if (r<a || l>b) return INF;
    if (a<=l && r<=b) return dat[k];
    else
    {
        int vl=query(a,b,2*k+1,l,(l+r)/2);
        int vr=query(a,b,2*k+2,(l+r)/2+1,r);
        return min(vl,vr);
    }
}
int main()
{
    int t,Case=0;
    scanf("%d",&t);
    while (t--)
    {
        int nn,q;
        scanf("%d%d",&nn,&q);
        init(nn);
        printf("Case %d:\n",++Case);
        for (int i=0;i<nn;i++)
        {
            int x;
            scanf("%d",&x);
            update(i,x);
        }
        for (int i=0;i<q;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            printf("%d\n",query(a-1,b-1,0,0,n-1));
        }
    }
    return 0;
}

F - Farthest Nodes in a Tree

题目大意：给定一棵树，求最远的两个节点间的距离

解题思路：两次bfs，第一次从随机一个点开始，寻找最远的点，并记录，第二次从那个最远的点寻找距离自己最远的点，这两点的距离就是树的直径，证明略去。

AC代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#define pi acos(0.0)*2
#define maxn 100005
#define INF 1<<30
using namespace std;
struct node
{
    int to,cost;
    node(int x,int y):to(x),cost(y){}
};
vector<node> G[30005];
int n,pos_1,pos_2,dis;
bool vis[30005];
void dfs(int u,int d)
{
    vis[u]=1;
    if (d>dis) {dis=d;pos_1=u;}
    for (int v=0;v<G[u].size();v++)
    {
        if (G[u][v].to!=u && !vis[G[u][v].to])
        {
            dfs(G[u][v].to,d+G[u][v].cost);
        }
    }
}
int main()
{
    int t,Case=0;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d",&n);
        dis=-1;
        memset(vis,0,sizeof(vis));
        for (int i=0;i<=n;i++) G[i].clear();
        for (int i=0;i<n-1;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            G[v].push_back(node(u,w));
            G[u].push_back(node(v,w));
        }
        dfs(0,0);
        dis=-1;
        memset(vis,0,sizeof(vis));
        dfs(pos_1,0);
        printf("Case %d: %d\n",++Case,dis);
    }
    return 0;
}