「CF611X」Good Bye 2015

智商基本已经放弃我了，身败名裂后的题解。

因为太弱加上是个高三狗，所以就只有ABCD了QAQ

A. New Year and Days

求2016年有多少个星期n

求2016年有多少个月有n号

可以算好答案输出

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<vector>
#include<algorithm>
#include<map>
#define inf 1000000000
#define ll long long 
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,l,ans;
char ch[10];
int d[12]={31,29,31,30,31,30,31,31,30,31,30,31};
int main()
{
    n=read();
    scanf("%s",ch);
    scanf("%s",ch);
    l=strlen(ch);
    if(ch[l-1]=='k')
    {
        if(n==5||n==6)ans=53;
        else ans=52;
    }
    else 
    {
        for(int i=0;i<12;i++)
            if(n<=d[i])ans++;
    }
    printf("%d\n",ans);
    return 0;
}

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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<vector>

#include<algorithm>

#include<map>

#define inf 1000000000

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,l,ans;

char ch[10];

int d[12]={31,29,31,30,31,30,31,31,30,31,30,31};

int main()

{

n=read();

scanf("%s",ch);

l=strlen(ch);

if(ch[l-1]=='k')

{

if(n==5||n==6)ans=53;

else ans=52;

}

else

{

for(int i=0;i<12;i++)

if(n<=d[i])ans++;

}

printf("%d\n",ans);

return 0;

}

B. New Year and Old Property

求L-R中有多少十进制数转为二进制只有1个0

枚举0在哪一位，然后再枚举1的个数

#include<set>
#include<map>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long 
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll a,b;
ll bin[65];
int cal(ll n)
{
    int ans=0;
    for(int i=1;i<=60;i++)
    {
        ll now=bin[i]+bin[i-1]-1;
        if(now<=n)ans++;
        for(int j=i+1;j<=60;j++)
        {
            now+=bin[j];
                if(now<=n)ans++;
                else break;
        }
    }
    return ans;
}
int main()
{
    bin[0]=1;for(int i=1;i<=60;i++)bin[i]=bin[i-1]<<1;
    a=read();b=read();
    printf("%d",cal(b)-cal(a-1));
    return 0;
}

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

#include<set>

#include<map>

#include<cmath>

#include<vector>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

inline ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll a,b;

ll bin[65];

int cal(ll n)

{

int ans=0;

for(int i=1;i<=60;i++)

{

ll now=bin[i]+bin[i-1]-1;

if(now<=n)ans++;

for(int j=i+1;j<=60;j++)

{

now+=bin[j];

if(now<=n)ans++;

else break;

}

return ans;

}

int main()

{

bin[0]=1;for(int i=1;i<=60;i++)bin[i]=bin[i-1]<<1;

a=read();b=read();

printf("%d",cal(b)-cal(a-1));

return 0;

}

C. New Year and Domino

求一个子矩形有多少种放置1*2的方式

二维前缀和，子矩形的边界就暴力一下

#include<set>
#include<map>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long 
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int h,w,q;
char a[505][505];
int b[505][505];
int main()
{
    h=read();w=read();
    for(int i=1;i<=h;i++)
        scanf("%s",a[i]+1);
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            if(i!=1||j!=1)
            {
                b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
                if(a[i][j]=='.')
                {
                    if(a[i-1][j]=='.')b[i][j]++;
                    if(a[i][j-1]=='.')b[i][j]++;
                }
            }
    q=read();
    int a1,b1,a2,b2,ans;
    while(q--)
    {
        a1=read();b1=read();a2=read();b2=read();
        ans=b[a2][b2]-b[a1-1][b2]-b[a2][b1-1]+b[a1-1][b1-1];
        for(int i=b1;i<=b2;i++)
            if(a[a1][i]=='.'&&a[a1-1][i]=='.')ans--;
        for(int i=a1;i<=a2;i++)
            if(a[i][b1]=='.'&&a[i][b1-1]=='.')ans--;
        printf("%d\n",ans);
    }
    return 0;
}

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

#include<set>

#include<map>

#include<cmath>

#include<vector>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

inline ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int h,w,q;

char a[505][505];

int b[505][505];

int main()

{

h=read();w=read();

for(int i=1;i<=h;i++)

scanf("%s",a[i]+1);

for(int i=1;i<=h;i++)

for(int j=1;j<=w;j++)

if(i!=1||j!=1)

{

b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1];

if(a[i][j]=='.')

{

if(a[i-1][j]=='.')b[i][j]++;

if(a[i][j-1]=='.')b[i][j]++;

}

q=read();

int a1,b1,a2,b2,ans;

while(q--)

{

a1=read();b1=read();a2=read();b2=read();

ans=b[a2][b2]-b[a1-1][b2]-b[a2][b1-1]+b[a1-1][b1-1];

for(int i=b1;i<=b2;i++)

if(a[a1][i]=='.'&&a[a1-1][i]=='.')ans--;

for(int i=a1;i<=a2;i++)

if(a[i][b1]=='.'&&a[i][b1-1]=='.')ans--;

printf("%d\n",ans);

}

return 0;

}

D. New Year and Ancient Prophecy

设计F(i , j)为最后一个数字长度为i，结尾在j的方案数

则F(i , j) = ∑ F(k, j – i) (k < i) + F(i , j – 1) （若以j结尾长为 i 的数大于上一个相邻的长为 i 的数）

两个数的比较用哈希表+二分来加速，或者用预处理来实现

#include<set>
#include<map>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long 
#define mod 1000000007
#define H 515347067
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
ll mul[5005],hs[5005];
ll f[5005][5005],s[5005][5005];
char ch[5005];
int gethash(int l,int r)
{
    int t=(hs[r]-hs[l-1]*mul[r-l+1])%H;
    return t<0?t+H:t;
}
bool check(int len,int pos)
{
    int b=pos-len+1,a=b-len;
    if(a<1||ch[b]=='0')return 0;
    int l=0,r=len-1,ans=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(gethash(a,a+mid-1)==gethash(b,b+mid-1))ans=mid,l=mid+1;
        else r=mid-1;
        }
    if(ans<=len-1&&ch[a+ans]<ch[b+ans])return 1;
    return 0;
}
int main()
{

    n=read();
    scanf("%s",ch+1);
    mul[0]=1;for(int i=1;i<=5000;i++)mul[i]=mul[i-1]*17%H;
    for(int i=1;i<=n;i++)
    {
        hs[i]=hs[i-1]*17+ch[i]-'0';
        hs[i]%=H;
    }
    for(int i=1;i<=n;i++)
    {
        f[i][i]=1;
        for(int j=i+1;j<=n;j++)
        {
            if(ch[j-i+1]!='0')f[i][j]=s[i-1][j-i];
            if(check(i,j))f[i][j]=(f[i][j]+f[i][j-i])%mod;
        }
        for(int j=1;j<=n;j++)
            s[i][j]=(s[i-1][j]+f[i][j])%mod;
    }
    cout<<s[n][n];
    return 0;
}

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

#include<set>

#include<map>

#include<cmath>

#include<vector>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

#define mod 1000000007

#define H 515347067

using namespace std;

inline ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

ll mul[5005],hs[5005];

ll f[5005][5005],s[5005][5005];

char ch[5005];

int gethash(int l,int r)

{

int t=(hs[r]-hs[l-1]*mul[r-l+1])%H;

return t<0?t+H:t;

}

bool check(int len,int pos)

{

int b=pos-len+1,a=b-len;

if(a<1||ch[b]=='0')return 0;

int l=0,r=len-1,ans=0;

while(l<=r)

{

int mid=(l+r)>>1;

if(gethash(a,a+mid-1)==gethash(b,b+mid-1))ans=mid,l=mid+1;

else r=mid-1;

}

if(ans<=len-1&&ch[a+ans]<ch[b+ans])return 1;

return 0;

}

int main()

{

n=read();

scanf("%s",ch+1);

mul[0]=1;for(int i=1;i<=5000;i++)mul[i]=mul[i-1]*17%H;

for(int i=1;i<=n;i++)

{

hs[i]=hs[i-1]*17+ch[i]-'0';

hs[i]%=H;

}

for(int i=1;i<=n;i++)

{

f[i][i]=1;

for(int j=i+1;j<=n;j++)

{

if(ch[j-i+1]!='0')f[i][j]=s[i-1][j-i];

if(check(i,j))f[i][j]=(f[i][j]+f[i][j-i])%mod;

}

for(int j=1;j<=n;j++)

s[i][j]=(s[i-1][j]+f[i][j])%mod;

}

cout<<s[n][n];

return 0;

}

比赛完挂后，gwy神犇：反正大家比赛的时候在friend list里看不到你

hzwer.com _ Home | http://hzwer.com

分类目录

热门文章

Myfriends

近期评论