2017百度之星预赛A

自用笔记算法

2017百度之星预赛A

HDU 6108

题目要求

根据小学数学的知识，我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之，如果一个数每一位加起来是3的倍数，则这个数肯定是3的倍数。
现在给定进制P，求有多少个B满足P进制下，一个正整数是B的倍数的充分必要条件是每一位加起来的和是B的倍数。

第一行一个正整数T表示数据组数(1<=T<=20)。
接下来T行，每行一个正整数P(2 < P < 1e9)，表示一组询问。
对于每组数据输出一行，每一行一个数表示答案。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
int solve(int x){
    int ans=0;
    int m=sqrt(x+0.5);
    for(int i=1;i<=m;i++){
        if(x%i==0){
            if(i*i==x) ans++;
            else ans+=2;
        }
    }
    return ans;
}
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        int p;
        scanf("%d",&p);
        printf("%d\n",solve(p-1));
    }
    return 0;
}

思路

计算后发现最后就是求p-1的因数个数

HDU 6110

题目要求

求树上路径交集长度
给出边的序号 每次询问2个边的序号

参考AC代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
#define maxn 500050
#define mm(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
using namespace std;
struct node{
    int to,w;
    node(int to,int w):to(to),w(w){}
};
vector<node>e[maxn];
struct path{
    int a,b,c;
    path(){}
    path(int a,int b,int c):a(a),b(b),c(c){}
}p[maxn],T[maxn<<2];
int deep[maxn],f[maxn],anc[maxn][25];
int dist[maxn];
void dfs(int x,int fa){
    anc[x][0]=f[x];
    for(int i=1;i<=20;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
    for(int i=0;i<e[x].size();i++){
        int next=e[x][i].to;
        if(next!=fa){
            f[next]=x;
            deep[next]=deep[x]+1;
            dist[next]=dist[x]+e[x][i].w;
            dfs(next,x);
        }
    }
}
int lca(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    for(int i=20;i>=0;i--) if(deep[anc[x][i]]>=deep[y]) x=anc[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--) if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
    return f[x];
}
void init(){
    mm(f,0),mm(anc,0),mm(deep,0),mm(dist,0);
    deep[1]=1;
    dfs(1,0);
}
int cmp(int a,int b){
    return deep[a]<deep[b];
}
path mix(path x,path y){
    if(!x.c || !y.c) return path(0,0,0);
    int cs[6];
    cs[1]=lca(x.a,y.a);
    cs[2]=lca(x.a,y.b);
    cs[3]=lca(x.b,y.a);
    cs[4]=lca(x.b,y.b);
    sort(cs+1,cs+1+4,cmp);
    int Max=max(deep[x.c],deep[y.c]),Min=min(deep[x.c],deep[y.c]);
    if(deep[cs[1]]<Min || deep[cs[3]]<Max) return path(0,0,0);
    return path(cs[3],cs[4],lca(cs[3],cs[4]));
}
void build(int rt,int l,int r){
    if(l==r){
        T[rt]=p[l];
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    T[rt]=mix(T[rt<<1],T[rt<<1|1]);
}
path query(int rt,int l,int r,int L,int R){
    if(l>=L && r<=R) return T[rt];
    int m=(l+r)>>1;
    if(m>=R) return query(lson,L,R);
    if(m<L) return query(rson,L,R);
    return mix(query(lson,L,R),query(rson,L,R));
}
int main(){
//    freopen("input.txt","r",stdin);
    int n,m,Q;
    while(~scanf("%d",&n)){
        for(int i=0;i<=n;i++) e[i].clear();
        for(int i=1;i<n;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            e[u].push_back(node(v,w));
            e[v].push_back(node(u,w));
        }
        init();
        scanf("%d",&m);
        for(int i=1;i<=m;i++){
            scanf("%d%d",&p[i].a,&p[i].b);
            p[i].c = lca(p[i].a,p[i].b);
        }
        build(1,1,m);
        scanf("%d",&Q);
        for(int i=1;i<=Q;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            path ans = query(1,1,m,a,b);
            printf("%lld\n",dist[ans.a]+dist[ans.b]-2*dist[ans.c]);
        }
    }
    return 0;
}

思路

lca求交集+线段树维护区间
算出路径的4个lca 按照深度排序 若1的深度小于最小值或者3的深度小于最大值 这时不存在交集
否则返回3->4 就是该段的区间交集
接着对区间的合并用线段树 方便构建和查询
算区间长度用lca即可

HDU 6112

题目要求

今天是2017年8月6日，农历闰六月十五。
小度独自凭栏，望着一轮圆月，发出了“今夕何夕，见此良人”的寂寞感慨。
为了排遣郁结，它决定思考一个数学问题：接下来最近的哪一年里的同一个日子，和今天的星期数一样？比如今天是8月6日，星期日。下一个也是星期日的8月6日发生在2023年。
小贴士：在公历中，能被4整除但不能被100整除，或能被400整除的年份即为闰年。

第一行为T，表示输入数据组数。
每组数据包含一个日期，格式为YYYY-MM-DD。
1 ≤ T ≤ 10000
YYYY ≥ 2017
日期一定是个合法的日期
对每组数据输出答案年份，题目保证答案不会超过四位数。

参考AC代码

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
#include<bits/stdc++.h>
using namespace std;
int check(int year){
    if((year%4==0 && year%100!=0) || year%400==0) return 366;
    return 365;
}
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        string s;
        cin>>s;
        int year=(s[0]-'0')*1000+(s[1]-'0')*100+(s[2]-'0')*10+s[3]-'0';
        int month=(s[5]-'0')*10+s[6]-'0';
        int day=(s[8]-'0')*10+s[9]-'0';
        int i;
        if(check(year)==366 && month==2 && day==29){
            int ans=0;
            for(i=year+1;;i++){
                ans+=check(i);
                if(ans%7==0 && check(i)==366) break;
            }
        }
        else if(month>=3){
            int ans=0;
            for(i=year+1;;i++){
                ans+=check(i);
                if(ans%7==0) break;
            }
        }
        else{
            int ans=0;
            for(i=year;;i++){
                ans+=check(i);
                if(ans%7==0) break;
            }
            i++;
        }
        printf("%d\n",i);
    }
    return 0;
}

思路

转化为求7的倍数
需要注意月份小于3 需要加前一年的天数 最后i++
月份大于等于3 需要加今年的天数
最后特判闰年的2月29号即可

HDU 6113

题目要求

度度熊是一个喜欢计算机的孩子，在计算机的世界中，所有事物实际上都只由0和1组成。
现在给你一个n*m的图像，你需要分辨他究竟是0，还是1，或者两者均不是。
图像0的定义：存在1字符且1字符只能是由一个连通块组成，存在且仅存在一个由0字符组成的连通块完全被1所包围。
图像1的定义：存在1字符且1字符只能是由一个连通块组成，不存在任何0字符组成的连通块被1所完全包围。
连通的含义是，只要连续两个方块有公共边，就看做是连通。
完全包围的意思是，该连通块不与边界相接触。

本题包含若干组测试数据。
每组测试数据包含：
第一行两个整数n,m表示图像的长与宽。
接下来n行m列将会是只有01组成的字符画。
满足1<=n,m<=100
如果这个图是1的话，输出1；如果是0的话，输出0，都不是输出-1。

参考AC代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
#define maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int g[105][105];
int dirx[4]={0,0,1,-1};
int diry[4]={1,-1,0,0};
int vis[105][105];
int n,m;
int f;
void dfs1(int x,int y){
    if(x<1 || x>n || y<1 || y>m) return;
    vis[x][y]=1;
    for(int i=0;i<4;i++){
        int xx=x+dirx[i];
        int yy=y+diry[i];
        if(!vis[xx][yy] && g[xx][yy]==1) dfs1(xx,yy);
    }
}
void dfs2(int x,int y){
    if(x<1 || x>n || y<1 || y>m){
        f=0;
        return;
    }
    vis[x][y]=1;
    for(int i=0;i<4;i++){
        int xx=x+dirx[i];
        int yy=y+diry[i];
        if(!vis[xx][yy]) dfs2(xx,yy);
    }
}
int main(){
//    freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        int stx=-1,sty=-1;
        for(int i=1;i<=n;i++){
            char s[105];
            scanf("%s",s+1);
            for(int j=1;j<=m;j++){
                g[i][j]=s[j]-'0';
                if(g[i][j]==1) stx=i,sty=j;
            }
        }
        if(stx==-1 && sty==-1){
            printf("-1\n");
            continue;
        }
        mm(vis,0);
        dfs1(stx,sty);
        int flag=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(g[i][j]==1 && vis[i][j]==0){
                    flag=1;
                    break;
                }
            }
            if(flag) break;
        }
        if(flag){
            printf("-1\n");
            continue;
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(g[i][j]==0 && vis[i][j]==0){
                    f=1;
                    dfs2(i,j);
                    if(f==1) cnt++;
                }
                if(cnt>1) break;
            }
            if(cnt>1) break;
        }
        if(cnt==0) printf("1\n");
        else if(cnt==1) printf("0\n");
        else printf("-1\n");
    }
    return 0;
}

思路

实际就是1的连通块个数和0的被包围连通块个数
若图中没有1 输出-1 若1的连通块个数不为1 输出-1
寻找0被包围的连通块个数 在之前vis的基础上进行dfs f用来判断是否被包围 若到达边界则未被包围
被包围的0连通块个数为1 输出0 个数为0 输出1 否则输出-1

本文标题:2017百度之星预赛A

文章作者:Hippopmonkey

发布时间:2017-08-14, 10:40:21

最后更新:2017-08-15, 15:15:08

原始链接:http://xuboming8.github.io/2017/08/14/2017百度之星复赛A/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 2017百度之星预赛A
    1. 1.1. HDU 6108
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 6110
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 6112
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 6113
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
|