「CF552X」Codeforces Round #308 (Div. 2)

A. Vanya and Table

模拟计算面积和

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long 
using namespace std;
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,ans;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x1=read(),y1=read(),x2=read(),y2=read();
        ans+=(y2-y1+1)*(x2-x1+1);
    }
    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

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

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,ans;

int main()

{

n=read();

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

{

int x1=read(),y1=read(),x2=read(),y2=read();

ans+=(y2-y1+1)*(x2-x1+1);

}

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

return 0;

}

B. Vanya and Books

枚举位数长度计算一下

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long 
using namespace std;
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 n,ans;
int main()
{
    n=read();
    ll t=9;
    for(int i=1;i<=10;i++)
    {
        ll x=min(t,n);
        n-=x;
        ans+=x*i;
        t=t*10;
    }
    cout<<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

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

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 n,ans;

int main()

{

n=read();

ll t=9;

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

{

ll x=min(t,n);

n-=x;

ans+=x*i;

t=t*10;

}

cout<<ans;

return 0;

}

C. Vanya and Scales

对于w^k，系数只能取-1，0，1

于是不断取模w什么的乱搞一下

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long 
using namespace std;
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 w,m;
int main()
{
    w=read();m=read();
    while(m)
    {
        if(m%w==1)m--;
        if(m%w==w-1)m++;
        if(m%w==0)m/=w;
        else 
        {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
    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

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

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 w,m;

int main()

{

w=read();m=read();

while(m)

{

if(m%w==1)m--;

if(m%w==w-1)m++;

if(m%w==0)m/=w;

else

{

puts("NO");

return 0;

}

puts("YES");

return 0;

}

D. Vanya and Triangles

所有情况减去三点共线

按照每个点为基点排序一下扫一遍计算共线

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long 
using namespace std;
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;
struct P{
    int x,y;
    double an;
    friend P operator-(P a,P b){
        return (P){a.x-b.x,a.y-b.y};
    }
    friend double getan(P a){
        return atan2(a.y,a.x);
    }
}a[2005],b[2005];
bool operator<(P x,P y)
{
    if(fabs(x.an-y.an)<1e-6)return x.x<y.x;
    return x.an<y.an;
}
ll ans;
void solve(int x)
{
    for(int i=1;i<=n;i++)a[i]=b[i];
    swap(a[1],a[x]);
    for(int i=2;i<=n;i++)
        a[i].an=getan(a[i]-a[1]);
    sort(a+2,a+n+1);
    for(int i=2,j;i<=n;i=j)
    {
        for(j=i+1;j<=n;j++)
        {
            if(fabs(getan(a[i]-a[1])-getan(a[j]-a[1]))>1e-6)break;
        }
        ans-=(j-i)*(j-i-1)/2;
    }
}
int main()
{
    n=read();
    if(n<=2)
    {
        puts("0");
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        a[i].x=read(),a[i].y=read();
        b[i]=a[i];
    }
    ans=(ll)n*(n-1)*(n-2)/3;
    for(int i=1;i<=n;i++)
        solve(i);
    cout<<ans/2<<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

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

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

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;

struct P{

int x,y;

double an;

friend P operator-(P a,P b){

return (P){a.x-b.x,a.y-b.y};

}

friend double getan(P a){

return atan2(a.y,a.x);

}

}a[2005],b[2005];

bool operator<(P x,P y)

{

if(fabs(x.an-y.an)<1e-6)return x.x<y.x;

return x.an<y.an;

}

ll ans;

void solve(int x)

{

for(int i=1;i<=n;i++)a[i]=b[i];

swap(a[1],a[x]);

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

a[i].an=getan(a[i]-a[1]);

sort(a+2,a+n+1);

for(int i=2,j;i<=n;i=j)

{

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

{

if(fabs(getan(a[i]-a[1])-getan(a[j]-a[1]))>1e-6)break;

}

ans-=(j-i)*(j-i-1)/2;

}

int main()

{

n=read();

if(n<=2)

{

puts("0");

return 0;

}

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

{

a[i].x=read(),a[i].y=read();

b[i]=a[i];

}

ans=(ll)n*(n-1)*(n-2)/3;

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

solve(i);

cout<<ans/2<<endl;

return 0;

}

E. Vanya and Brackets

发现左括号前面，右括号一定是乘号or字符串开头/末尾

然后就可以模拟啦QAQ

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long 
using namespace std;
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;
}
string a;
ll ans,T;
ll solve(int l,int r,ll t)
{
    ll ans=0;
    for(int i=r;i>=l;i--)
        if(a[i]=='+')ans+=t,t=0;
        else if(a[i]>='0'&&a[i]<='9')
        {
            if(a[i+1]=='+')t+=a[i]-'0';
            else t*=a[i]-'0';
        }
    T=t;
    return ans;
}
int main()
{
    cin>>a;
    a.push_back('+');
    ans=solve(0,a.size()-1,0)+T;
    for(int i=0;i<a.size()-1;i++)
        if(a[i]=='*')
        {
            ll t=solve(i+1,a.size()-1,0),p=T;
            ans=max(ans,(solve(0,i-1,1)+T)*p+t);
            t=solve(i+1,a.size()-1,0);
            ans=max(ans,solve(0,i-1,T+t)+T);
        }
    for(int i=0;i<a.size()-1;i++)
        for(int j=i+1;j<a.size()-1;j++)
            if(a[i]=='*'&&a[j]=='*')
            {
                ll t=solve(j+1,a.size()-1,0),p=T,t3=t;
                t=(solve(i+1,j-1,1)+T)*p;
                t=(solve(0,i-1,t)+T);
                ans=max(ans,t+t3);
            }
    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

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

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;

}

string a;

ll ans,T;

ll solve(int l,int r,ll t)

{

ll ans=0;

for(int i=r;i>=l;i--)

if(a[i]=='+')ans+=t,t=0;

else if(a[i]>='0'&&a[i]<='9')

{

if(a[i+1]=='+')t+=a[i]-'0';

else t*=a[i]-'0';

}

T=t;

return ans;

}

int main()

{

cin>>a;

a.push_back('+');

ans=solve(0,a.size()-1,0)+T;

for(int i=0;i<a.size()-1;i++)

if(a[i]=='*')

{

ll t=solve(i+1,a.size()-1,0),p=T;

ans=max(ans,(solve(0,i-1,1)+T)*p+t);

t=solve(i+1,a.size()-1,0);

ans=max(ans,solve(0,i-1,T+t)+T);

}

for(int i=0;i<a.size()-1;i++)

for(int j=i+1;j<a.size()-1;j++)

if(a[i]=='*'&&a[j]=='*')

{

ll t=solve(j+1,a.size()-1,0),p=T,t3=t;

t=(solve(i+1,j-1,1)+T)*p;

t=(solve(0,i-1,t)+T);

ans=max(ans,t+t3);

}

cout<<ans<<endl;

return 0;

}

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

分类目录

热门文章

Myfriends

近期评论