「CF235X」Codeforces Round #146 (Div. 1)

A. LCM Challenge

显然是在接近n数内找三个两两互质的，由于懒得推公式所以可以小范围暴力一下

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define mod 1000000007
#define inf 1000000000
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n;
ll ans;
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    n=read();
    int m=max(1,n-100);
    ans=n;
    for(int i=m;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(gcd(i,j)==1)
            for(int k=j+1;k<=n;k++)
                if(gcd(k,i)==1&&gcd(k,j)==1)
                    ans=max(ans,(ll)i*j*k);
    cout<<ans<<endl;
    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

#include<map>

#include<set>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define mod 1000000007

#define inf 1000000000

#define ll long long

using namespace std;

ll read()

{

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

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

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

return x*f;

}

int n;

ll ans;

ll gcd(ll a,ll b)

{

return b==0?a:gcd(b,a%b);

}

int main()

{

n=read();

int m=max(1,n-100);

ans=n;

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

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

if(gcd(i,j)==1)

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

if(gcd(k,i)==1&&gcd(k,j)==1)

ans=max(ans,(ll)i*j*k);

cout<<ans<<endl;

return 0;

}

B.Let’s Play Osu!

计算出到每个位置的期望连续长度

就可以得到如果该位置正确的期望得分，就可以dp辣

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define mod 1000000007
#define inf 1000000000
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n;
double d,ans;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        double x;scanf("%lf",&x);
        ans+=(2*d+1)*x;
        d=(d+1)*x;
    }

    printf("%.10lf",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

#include<map>

#include<set>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define mod 1000000007

#define inf 1000000000

#define ll long long

using namespace std;

ll read()

{

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

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

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

return x*f;

}

int n;

double d,ans;

int main()

{

n=read();

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

{

double x;scanf("%lf",&x);

ans+=(2*d+1)*x;

d=(d+1)*x;

}

printf("%.10lf",ans);

return 0;

}

C.Cyclical Quest

一道很正经的后缀自动机

建出s串的后缀自动机

把xi复制一遍接在后面，然后在s串上匹配，就可以得出后缀自动机上贡献答案的结点

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#define pa pair<int,int>
#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;
}
ll tot;
int n,l;
char ch[2000005];
int v[2000005],q[2000005];
vector<int>ans;
bool flag[2000005];
struct sam{
    int last,cnt;
    int mx[2000005],fa[2000005],num[2000005],a[2000005][26];
    sam(){
        last=++cnt;
    }
    void extend(int c){
        int p=last,np=last=++cnt;mx[np]=mx[p]+1;    
        num[np]=1;
        while(p&&!a[p][c])a[p][c]=np,p=fa[p];
        if(!p)fa[np]=1;
        else 
        {
            int q=a[p][c];
            if(mx[q]==mx[p]+1)fa[np]=q;
            else 
            {
                int nq=++cnt;mx[nq]=mx[p]+1;
                memcpy(a[nq],a[q],sizeof(a[q]));
                fa[nq]=fa[q];
                fa[np]=fa[q]=nq;
                while(a[p][c]==q)a[p][c]=nq,p=fa[p];
            }
        }
    }
    void ini(){
        for(int i=1;i<=cnt;i++)v[mx[i]]++;
        for(int i=1;i<=cnt;i++)v[i]+=v[i-1];
        for(int i=cnt;i;i--)q[v[mx[i]]--]=i;
        for(int i=cnt;i;i--)
        {
            int t=q[i];
            num[fa[t]]+=num[t];
        }
    }
    void solve(){
        int p=1,tmp=0;
        for(int i=1;i<=2*l-1;i++)
        {
            int c=ch[i]-'a';
            while(p&&!a[p][c])p=fa[p];
            if(!p)p=1,tmp=0;
            else 
            {
                tmp=min(mx[p],tmp)+1;
                p=a[p][c];
            }
            while(mx[fa[p]]>=l)p=fa[p],tmp=mx[p];
            if(!flag[p]&&tmp>=l)ans.push_back(p),flag[p]=1;
        }
        for(int i=0;i<ans.size();i++)flag[ans[i]]=0;
        for(int i=0;i<ans.size();i++)tot+=num[ans[i]];
        ans.clear();
    }
}sam;
int main()
{
    scanf("%s",ch+1);
    l=strlen(ch+1);
    for(int i=1;i<=l;i++)
        sam.extend(ch[i]-'a');
    sam.ini();
    n=read();
    for(int i=1;i<=n;i++)
    {
        scanf("%s",ch+1);
        l=strlen(ch+1);
        for(int i=1;i<l;i++)
            ch[i+l]=ch[i];
        tot=0;sam.solve();
        printf("%I64d\n",tot);
    }
    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

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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<vector>

#define pa pair<int,int>

#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;

}

ll tot;

int n,l;

char ch[2000005];

int v[2000005],q[2000005];

vector<int>ans;

bool flag[2000005];

struct sam{

int last,cnt;

int mx[2000005],fa[2000005],num[2000005],a[2000005][26];

sam(){

last=++cnt;

}

void extend(int c){

int p=last,np=last=++cnt;mx[np]=mx[p]+1;

num[np]=1;

while(p&&!a[p][c])a[p][c]=np,p=fa[p];

if(!p)fa[np]=1;

else

{

int q=a[p][c];

if(mx[q]==mx[p]+1)fa[np]=q;

else

{

int nq=++cnt;mx[nq]=mx[p]+1;

memcpy(a[nq],a[q],sizeof(a[q]));

fa[nq]=fa[q];

fa[np]=fa[q]=nq;

while(a[p][c]==q)a[p][c]=nq,p=fa[p];

}

void ini(){

for(int i=1;i<=cnt;i++)v[mx[i]]++;

for(int i=1;i<=cnt;i++)v[i]+=v[i-1];

for(int i=cnt;i;i--)q[v[mx[i]]--]=i;

for(int i=cnt;i;i--)

{

int t=q[i];

num[fa[t]]+=num[t];

}

void solve(){

int p=1,tmp=0;

for(int i=1;i<=2*l-1;i++)

{

int c=ch[i]-'a';

while(p&&!a[p][c])p=fa[p];

if(!p)p=1,tmp=0;

else

{

tmp=min(mx[p],tmp)+1;

p=a[p][c];

}

while(mx[fa[p]]>=l)p=fa[p],tmp=mx[p];

if(!flag[p]&&tmp>=l)ans.push_back(p),flag[p]=1;

}

for(int i=0;i<ans.size();i++)flag[ans[i]]=0;

for(int i=0;i<ans.size();i++)tot+=num[ans[i]];

ans.clear();

}

}sam;

int main()

{

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

l=strlen(ch+1);

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

sam.extend(ch[i]-'a');

sam.ini();

n=read();

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

{

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

l=strlen(ch+1);

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

ch[i+l]=ch[i];

tot=0;sam.solve();

printf("%I64d\n",tot);

}

return 0;

}

D. Graph Game

不经过环的路径x，y贡献是1/dis(x,y)

经过环的要扣除两段路径并的贡献

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#define pa pair<int,int>
#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;
}
double ans;
int n,cnt,C;
int head,tail;
int q[3005],d[3005],d2[3005];
bool vis[3005];
vector<int>e[3005];
void dfs(int x)
{
    vis[x]=1;
    for(int i=0;i<e[x].size();i++)
        if(!vis[e[x][i]])
        {
            d2[e[x][i]]=d2[x]+1;
            if(!d[e[x][i]])
            {
                d[e[x][i]]=d[x]+1;
                ans+=1.0/d[e[x][i]];
            }
            else ans=ans+1.0/d2[e[x][i]]-2.0/(d[e[x][i]]+d2[e[x][i]]+C-2);
            dfs(e[x][i]);
        }
    vis[x]=0;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int u=read(),v=read();
        u++;v++;
        e[u].push_back(v);
        e[v].push_back(u);
        d[u]++;d[v]++;
    }
    for(int i=1;i<=n;i++)
        if(d[i]==1)q[tail++]=i;
    while(head!=tail)
    {
        int now=q[head];head++;
        for(int i=0;i<e[now].size();i++)
        {
            d[e[now][i]]--;
            if(d[e[now][i]]==1)q[tail++]=e[now][i];
        }
    }
    C=n-tail;
    for(int i=1;i<=n;i++)
    {
        memset(d,0,sizeof(d));
        memset(d2,0,sizeof(d2));
        d[i]=d2[i]=1;
        dfs(i);
    }
    printf("%.10lf\n",ans+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

70

71

72

73

74

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<vector>

#define pa pair<int,int>

#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;

}

double ans;

int n,cnt,C;

int head,tail;

int q[3005],d[3005],d2[3005];

bool vis[3005];

vector<int>e[3005];

void dfs(int x)

{

vis[x]=1;

for(int i=0;i<e[x].size();i++)

if(!vis[e[x][i]])

{

d2[e[x][i]]=d2[x]+1;

if(!d[e[x][i]])

{

d[e[x][i]]=d[x]+1;

ans+=1.0/d[e[x][i]];

}

else ans=ans+1.0/d2[e[x][i]]-2.0/(d[e[x][i]]+d2[e[x][i]]+C-2);

dfs(e[x][i]);

}

vis[x]=0;

}

int main()

{

n=read();

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

{

int u=read(),v=read();

u++;v++;

e[u].push_back(v);

e[v].push_back(u);

d[u]++;d[v]++;

}

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

if(d[i]==1)q[tail++]=i;

while(head!=tail)

{

int now=q[head];head++;

for(int i=0;i<e[now].size();i++)

{

d[e[now][i]]--;

if(d[e[now][i]]==1)q[tail++]=e[now][i];

}

C=n-tail;

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

{

memset(d,0,sizeof(d));

memset(d2,0,sizeof(d2));

d[i]=d2[i]=1;

dfs(i);

}

printf("%.10lf\n",ans+n);

return 0;

}

E. Number Challenge

http://gaotianyu1350.gitcafe.io/2015/04/21/CF235E/

懒得写公式了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#define pa pair<int,int>
#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 a,b,c,cnt;
int pri[2005],mu[2005];
bool mark[2005];
ll ans;
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
void pre()
{
    mu[1]=1;
	for(int i=2;i<=2000;i++)
	{
		if(!mark[i])mu[i]=-1,pri[++cnt]=i;
		for(int j=1;j<=cnt&&pri[j]*i<=2000;j++)
		{
			mark[pri[j]*i]=1;mu[pri[j]*i]=-mu[i];
			if(i%pri[j]==0){mu[pri[j]*i]=0;break;}
		}
	}
}
int f(int d,int x)
{
	int sum=0;
	for(int i=1;i<=d;i++)
		if(gcd(i,x)==1)sum+=d/i;
	return sum;
}
int main()
{
	pre();
	a=read();b=read();c=read();
	for(int i=1;i<=a;i++)
		for(int j=1;j<=min(b,c);j++)
			if(gcd(i,j)==1)
				ans+=mu[j]*(a/i)*f(b/j,i)*f(c/j,i);
	cout<<ans%1073741824;
	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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<vector>

#define pa pair<int,int>

#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 a,b,c,cnt;

int pri[2005],mu[2005];

bool mark[2005];

ll ans;

int gcd(int a,int b)

{

return b==0?a:gcd(b,a%b);

}

void pre()

{

mu[1]=1;

for(int i=2;i<=2000;i++)

{

if(!mark[i])mu[i]=-1,pri[++cnt]=i;

for(int j=1;j<=cnt&&pri[j]*i<=2000;j++)

{

mark[pri[j]*i]=1;mu[pri[j]*i]=-mu[i];

if(i%pri[j]==0){mu[pri[j]*i]=0;break;}

}

int f(int d,int x)

{

int sum=0;

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

if(gcd(i,x)==1)sum+=d/i;

return sum;

}

int main()

{

pre();

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

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

for(int j=1;j<=min(b,c);j++)

if(gcd(i,j)==1)

ans+=mu[j]*(a/i)*f(b/j,i)*f(c/j,i);

cout<<ans%1073741824;

return 0;

}

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

分类目录

热门文章

Myfriends

近期评论