[原创]2016女生赛 【（7+2）/10】

2017-07-24 20:01:34 Tabris_ 阅读数：357

博客爬取于2020-06-14 22:39:31
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/76037429

感觉今天都好没状态啊。

dalao题解

A HDU 5702 Solving Order

——————————————————————————————————————
结构体排序没什么好说的。。

B HDU 5703 Desert

——————————————————————————————————————
给你一个整数，问你划分方法有多少种，然后用二进制输出，{1,2}{2,1}算两种

退了一下，发现 结果就是2n−12^{n-1}

所以输出个11,和n−1n-1个00就行了

C HDU 5704 Luck Competition

——————————————————————————————————————
n（2~100）个人参加一个游戏，
每个人选择1~100范围的数。
然后得到所有数的平均数，再*=2/3，设得到的数为m。
如果一个人选的数，比m小，且相距m最为接近，那么其便在所有选数相同的人中等概率中奖。

现在，我们也参加比赛，其他n-1个人所选择的数也已经确定了，并且我们知道。
问你，选什么数拥有最高中奖率，并输出。

数据量比较小,暴力枚举然后在模拟计算就行了

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
# include <bits/stdc++.h>
using namespace std;
int vis[150];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(vis,0,sizeof(vis));
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n-1;i++)
        {
            int x;
            scanf("%d",&x);
            vis[x]++;
        }
        double P=-1;
        int output=-1;
        for(int ans=100;ans>=0;ans--)
        {
            vis[ans]++;
            int sum=0;
            for(int j=0;j<=100;j++)
            {
                sum+=vis[j]*j;
            }
            double ave=sum;
            ave=(ave/(double)n);
            ave*=2;
            ave=ave*1.0/3.0;
            if(ans<=ave)
            {
                int pos;
                for(int j=(int)ave;j>=0;j--)
                {
                    if(vis[j]>0)
                    {
                        pos=j;
                        break;
                    }
                }
                if(pos==ans)
                {
                    double pp=1/(double)vis[ans];
                    if(pp>P)
                    {
                        P=pp;
                        output=ans;
                    }
                }
                else
                {
                    if(0>P)
                    {
                        P=0;
                        output=ans;
                    }
                }
            }
            vis[ans]--;
        }
        printf("%d %.2f\n",output,P);
    }
}

D HDU 5705 Clock

——————————————————————————————————————
给你一个时间,问你下一次时针和分针夹角为a度的时刻是多少,如果不是整数则把秒数向下取整

暴力模拟即可,

为了方便比较 可以扩大倍数,使得时针1s动1个单位

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>
# define maxs 20002020
# define mme(i,j) memset(i,j,sizeof(i))
using namespace std;

# define abs(x) ((x)<0?-(x):(x))

int deg(int &h,int &m,int &s){
    int hh = (h*60*60+m*60+s);
    int mm = (h*60*60+m*60+s)*12;
    hh %= 720*60;
    mm %= 720*60;
    int t = abs(hh-mm);
    return min(t,720*60-t);
}

void add1(int &h,int &m,int &s){
    s++;
    if(s == 60){
        m++;
        s=0;
    }
    if(m == 60) {
        h++;
        m=0;
    }
    if(h == 12){
        h = 0;
    }
}

int main(){
    // h  1/720   1
    // m  1/60    12
    // s  1       720
    int _ = 1,kcase=0;
    int h,m,s,x,p,tp,th,tm,ts;
    while(~scanf("%d:%d:%d",&h,&m,&s)){
        scanf("%d",&x); x*=120;
        p = deg(h,m,s);
        while(true){
            th=h,tm=m,ts=s;
            add1(h,m,s);
            tp = deg(h,m,s);
            if(tp == x) break;
            if(tp<x&&p>x){
                h=th,m=tm,s=ts;
                break;
            }
            if(x<tp&&p<x){
                h=th,m=tm,s=ts;
                break;
            }
            p=tp;
//            printf("%d:%d:%d  %d - %d\n",h,m,s,tp,x);
        }

        printf("Case #%d: %02d:%02d:%02d\n",++kcase,h,m,s);

    }
    return 0;
}

E HDU 5706 GirlCat

——————————————————————————————————————
一个n*m的网格,每个格子有一个字母 ,问你能构成的girl和cat的个数

爆搜即可

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
# include <bits/stdc++.h>
# define maxs 202002
using namespace std;
int ok;
int n,m;
char a[1005][1005];
int fx[4]={0,0,1,-1};
int fy[4]={1,-1,0,0};
void Dfs(int x,int y,int num)
{
    if(num==0)if(a[x][y]!='g')return ;
    if(num==1)if(a[x][y]!='i')return ;
    if(num==2)if(a[x][y]!='r')return ;
    if(num==3)if(a[x][y]!='l')return ;
    if(num==3)
    {
        ok++;
        return ;
    }
    for(int i=0;i<4;i++)
    {
        int xx=x+fx[i];
        int yy=y+fy[i];
        if(xx>=0&&x<n&&yy>=0&&yy<m)
        {
            Dfs(xx,yy,num+1);
        }
    }
}
void Dfs2(int x,int y,int num)
{
    if(num==0)if(a[x][y]!='c')return ;
    if(num==1)if(a[x][y]!='a')return ;
    if(num==2)if(a[x][y]!='t')return ;
    if(num==2)
    {
        ok++;
        return ;
    }
    for(int i=0;i<4;i++)
    {
        int xx=x+fx[i];
        int yy=y+fy[i];
        if(xx>=0&&x<n&&yy>=0&&yy<m)
        {
            Dfs2(xx,yy,num+1);
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)scanf("%s",a[i]);
        int output=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(a[i][j]=='g')
                {
                    ok=0;
                    Dfs(i,j,0);
                    output+=ok;
                }
            }
        }
        printf("%d ",output);
        output=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(a[i][j]=='c')
                {
                    ok=0;
                    Dfs2(i,j,0);
                    output+=ok;
                }
            }
        }
        printf("%d\n",output);
    }
}

F HDU 5707 Combine String

——————————————————————————————————————
给你三个字符串,问你能不能将a,b合并成c,且a,b字符串的字母顺序不被改变

设f[i][j] 表示当前,到达a[i],b[j]的时候,能不能凑成c[0~i+j-1],

转移的时候就是

if(a[i−1]==c[i+j−1])f[i][j]∣(位或)=f[i−1][j];if(b[j−1]==c[i+j−1])f[i][j]∣(位或)=f[i][j−1];if(a[i-1]==c[i+j-1]) f[i][j]\Big |(位或)=f[i-1][j];\\ if(b[j-1]==c[i+j-1]) f[i][j]\Big |(位或)=f[i][j-1];

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
# include<bits/stdc++.h>
typedef long long int LL;
using namespace std;

# define abs(x) ((x)>0?(x):-(x))

const int N = 100000+7;
const int M = 10000000+7;
/***************************************************/

char a[2222],b[2222],c[2222];

int f[2222][2222];

int main(){
    while(~scanf("%s",a)){
        scanf("%s",b);
        scanf("%s",c);

        int la=strlen(a);
        int lb=strlen(b);
        int lc=strlen(c);

        if(lc!=la+lb){
            puts("No");
            continue;
        }

        memset(f,0,sizeof(f));
        f[0][0]=1;

        for(int i=0;i<=la;i++)for(int j=0;j<=lb;j++){
            if(i==0&&j==0) continue;
            if(i>0&&a[i-1]==c[i+j-1]) f[i][j] |=f[i-1][j];
            if(j>0&&b[j-1]==c[i+j-1]) f[i][j] |=f[i][j-1];
        }

        puts(f[la][lb]?"Yes":"No");
    }
    return 0;
}

G HDU 5708 Alice and Bob

——————————————————————————————————————
两个人走格子，从(1,1)开始走 ,每次可以从(x,y)走到(x+1,y),(x,y+1),(x+k,y+k)
轮到谁的时候不能走了 就输了.
两个人足够聪明 然后问你谁能赢,Alice先

手写了几组k,然后发现有一个规律, 然后就打表观察了下 ,然后就总结了下规律然后AC.了…

这个规律有点不好描述 自己看吧 打表代码为solve()函数

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
# include <bits/stdc++.h>
# define maxs 20002020
# define mme(i,j) memset(i,j,sizeof(i))
using namespace std;

# define abs(x) ((x)<0?-(x):(x))

int a[111][111],b[111][111];
void solve(){
    int n = 20;
    int m = 20;
    int k =  4;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==0){
                a[i][j+1]=1;
                a[i+1][j]=1;
                a[i+k][j+k]=1;
            }
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)
            printf(" %d",a[i][j],i+j);
        puts("");
    }

    return ;
}

int main(){
//    solve();
    int _ = 1,q,k,n,m;
    for(scanf("%d",&_);_--;){
        scanf("%d%d",&q,&k);
        for(int i=1;i<=q;i++){
            scanf("%d%d",&n,&m);
            if(n<m) swap(n,m);
            int flag = m/(k+1);
            if(k == 1){
                if(n%2==0||m%2==0) puts("Alice");
                else               puts("Bob");
            }
            else {
                if(m%(k+1)==0||(m-flag+n)&1)  puts("Alice");
                else               puts("Bob");
            }
        }
    }
    return 0;
}

H HDU 5709 Claris Loves Painting

——————————————————————————————————————
有n(<=1e5)个点的树，每个点都有颜色（颜色可能重复），有m(<=1e5)个询问，每次询问(x,d)问在x的子树中，与x的距离不超过d的节点有多少种不同的颜色。强制要求在线。

维护两颗线段树,并还要有合并的操作,不是特别懂…
看claris的博客吧

1

I HDU 5710 Digit-Sum

——————————————————————————————————————
我们要找出最小的正整数n满足——
aS(n)==bS(2n)
a,b的范围都在[1,100]
s(x)为x的所有位的和

首先能明确的是

s(2n)=2s(n)−9Ls(2n) = 2s(n)-9L___L为n里面大于5的数字的个数L为n里面大于5的数字的个数

因为大于55就会进位,相当于−10+1=9-10+1 = 9

所以有

a×s(n)=b×s(2n)=>a×s(n)=b×(2s(n)−9L)=>(2∗b−a)×s(n)=b×9L=>Ls(n)=2∗b−ab∗9a\times s(n) =b\times s(2n) \\ => a\times s(n) = b\times (2s(n)-9L)\\=>(2*b-a)\times s(n) = b\times9L\\=>\dfrac{L}{s(n)} = \dfrac{2*b-a}{b*9}

  1. a=2ba=2b，则L=0L=0，S为任意值。可得最小的n=1n=1；
  2. a>2ba>2b，则L<0L<0，矛盾！则无满足的nn，输出00；
  3. a<2ba<2b，S=9bL2b−a≤5LS=\frac{9bL}{2b−a}≤5L(至少有L个5)，即必须满足b≤5ab≤5a，否则无满足的n，输出0。

然后考虑数n的选取，

我们假设有l的长度是[0,4]范围，有L的长度是[5,9]范围

我们不妨假设答案n仅有长度为L，且每一位都是5
然后得到了把数位和sum分撒出去。

对于sum余下的数值，我们依次加到尾巴上。
如果sum最后把长度为L的字串都填充为‘9‘之后，还有剩余，那么在前面贪心填充。

J HDU 5711 Ingress

——————————————————————————————————————
n（16）个点
m（n^2）条双向边
K（50）次hack机会
最远走L（2000）路程

每个点的初始点权为ai
每个点每hack一次点权下降bi

队友补的 我还不会 待补…