吉首大学2019年程序设计竞赛 部分题解

题解

吉首大学2019年程序设计竞赛

B 干物妹小埋

题意：求一个单调不减序列的最大权值和。
分析： 数据范围2e5，用数据结构。按高度排序去重放进线段树中，区间查询最值单点更新即可，注意数据范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
const int N=2e5+10;
int n,b[N],bb[N],vis[N];
long long c[N];
struct node
{
    int l,r;
    long long happy;
} a[N<<2];
void build(int l,int r,int k)
{
    a[k].l=l,a[k].r=r,a[k].happy=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(l,mid,2*k);
    build(mid+1,r,2*k+1);
}
void update(int id,int  num,int k)
{
    if(id==a[k].l&&a[k].r==id)
    {
        a[k].happy=num;
        return ;
    }
    int mid=(a[k].l+a[k].r)>>1;
    if(id<=mid) update(id,num,2*k);
    else update(id,num,2*k+1);
    a[k].happy=max(a[k*2].happy,a[k*2+1].happy);
}
long long query(int l,int r,int k)
{
    if(l<=a[k].l&&r>=a[k].r) return a[k].happy;
    int mid=(a[k].l+a[k].r)>>1;
    if(r<=mid) return query(l,r,2*k);
    else if(l>mid) return query(l,r,2*k+1);
    else return max(query(l,mid,2*k),query(mid+1,r,2*k+1));
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&b[i]);
            bb[i]=b[i];
        }
        for(int i=1; i<=n; i++) scanf("%lld",&c[i]);
        sort(bb+1,bb+n+1);
        int pos,k=unique(bb+1,bb+n+1)-bb-1;
        build(1,k,1);
        for(int i=1; i<=n; i++)
        {
            pos=lower_bound(bb+1,bb+k+1,b[i])-bb;
            long long cnt=query(1,pos,1);
            update(pos,cnt+c[i],1);
        }
        printf("%lld\n",a[1].happy);
    }
    return 0;
}

E 多喝嘤料

题意：喝饮料，三个瓶子或4个瓶盖换一瓶，起初n瓶，求最多能喝多少瓶。
分析：判断边界即可，无法再喝是因为无法兑换了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while True:
    try:
        t=int(input())
        for i in range(t):
            n=int(input())
            ans=n
            kong=gai=n
            while kong//3+gai//4>0:
                n=(kong//3)+(gai//4)
                kong=kong%3+n
                gai=gai%4+n
                ans=ans+n
                # print(n,kong,gai)
            print(ans)
    except:break

F 天花乱坠

题意：一个正n边形，初始每条边都为100。现沿着中点再作正n边形，一直重复，求所构成图案所有边边长和。
分析：这是一个收敛的数列求和取极限问题。根据余弦公式cosb=(a2+b2-c2)/(2ab)，很容易求得新的边长c，由于答案保留两位有效数字，故将精度调为1e-8，高了错误，低了超时。注意精度问题，尽量少作除法，能预处理就先预处理，就这样卡过去了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import  math
from math import pi
while True:
    try:
        n=int(input())
        ans=0
        a=100.0
        angle=1-math.cos((n-2)*pi/n)
        while True:
            ans=ans+a
            a=math.sqrt(a*a*angle/2)
            if a<1e-8:break;
        print("%.2f" %(ans*n))
    except:break

G 说能过那是假的

题意：给你一个由’O’、’R’、’Z’组成的字符串，求正序组成’ORZ’的情况有多少种。
分析： 三层暴力可能超时，考虑预处理。以’R’为中间点，每个’R’对答案的贡献就是左边的’O’的个数乘以右边的’Z’的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while True:
    try:
        s=input()
        leng=len(s)
        a=[[0]*(leng+2) for i in range(2)] # 申请二维数组
        for id in range(leng): # 预处理O
            a[0][id+1]=a[0][id]
            if s[id]=='O':a[0][id+1]=a[0][id+1]+1
        for id in range(leng,0,-1): # 预处理Z
            a[1][id]=a[1][id+1]
            if s[id-1]=='Z':a[1][id]=a[1][id]+1
        ans=0
        for id in range(leng):
            if s[id]=='R':ans=ans+a[1][id+1]*a[0][id+1]
        print(ans)
    except:break

H 蛇皮走位

题意：用26个小写英文字母按反’S’形填充矩阵
分析：分奇偶行直接输出即可。
Python实现：ord(c)表示字符c的ascii值，chr(x)表示数字x对应的ascii字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
while True:
    try:
        n=int(input())
        x=n*2+1
        id=0
        for i in range(x):
            if i&1==0:
                for j in range(x):
                    print(chr(id+97),end="")
                    id=(id+1)%26
            else:
                id=(id+x-1)%26
                for j in range(x):
                    print(chr(id+97),end="")
                    id=(id-1+26)%26
                id=(id+x+1)%26
            print("")
    except:break

J 滑稽树下你和我

题意：n个点的树，每条边有一个距离。求树上任意两点的距离之和。
分析：突破点在于求每条边对答案贡献。也就是算每条边经过多少次，就是这条边左边的所有点乘以右边的所有点（树上每条边都是桥）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
const int N=1e5+10;
int n,tot,head[N];
long long cnt[N];
long long ans;
struct Edge
{
    int to,next,w;
}e[N*2];
void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
    memset(cnt,0,sizeof(cnt));
}
void add(int u,int v,int w)
{
    e[tot].to=v,e[tot].w=w,e[tot].next=head[u];
    head[u]=tot++;
    e[tot].to=u,e[tot].w=w,e[tot].next=head[v];
    head[v]=tot++;
}
void dfs1(int u,int fa)
{
    for(int i=head[u];i+1;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa) continue;
        dfs1(v,u);
        cnt[u]+=cnt[v];
    }
    cnt[u]++;  // 加上自己
}
void dfs2(int u,int fa)
{
    for(int i=head[u];i+1;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa) continue;
        ans=(ans+cnt[v]*(n-cnt[v])*e[i].w%MOD)%MOD;
        dfs2(v,u);
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
         init();
         int u,v,w;
         for(int i=1;i<n;i++)
         {
             scanf("%d%d%d",&u,&v,&w);
             add(u,v,w);
         }
         dfs1(1,1); # 预处理每个点子树所有点数量
         ans=0;
         dfs2(1,1);
         printf("%lld\n",ans);
    }
    return 0;
}