2019牛客暑期多校训练营（第八场）B Beauty Values && C CDMA

B题题意：

题目

给你n个数，让你把这一个序列中的所有子区间的Beauty Values加起来，Beauty Values是子区间内有几个不同的数

题解：

肯定不会是暴力，所以我们就要在各元素的位置上下手，我们可以反过来去求有多少区间内有至少一个本元素，就把这些区间加起来就可以了

但是有可能某个区间内有几个相同的元素（只是位置不同），此时在计算这个元素出现这个区间的时候只能加一次，不能多加

这样的话我们就可以在求的时候控制他们的左边界不同（我们总是控制某个元素的左边界在上一个相同元素的位置），这样就不会出现相同元素在同一个区间加多次的情况

例如：

1 2 3 1 5 6 1 9

第一个1：左边界为0，包括他的最长子区间也包括1 2 3 1 5 6 1 9，虽然这里面有多个1，但是这并不影响

第二个1：左边界为1，此时最长子区间为2 3 1 5 6 1 9，可见这样的话，虽然里面有多个1，但是区间并没有在相同元素下多加

第三个1：左边界为4，此时最长子区间为5 6 1 9

代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<math.h>

 6 #include<stack>

 7 #include<math.h>

 8 using namespace std;

 9 typedef long long ll;

10 const int maxn=1e5+10;

11 ll v[maxn];

12 int main()

13 {

14     ll n,q;

15     ll ans=0;

16     scanf("%lld",&n);

17     for(ll i=1;i<=n;++i)

18     {

19         scanf("%lld",&q);

20         ans+=(i-v[q])*(n-i+1);  //这是一个计算包括q元素子区间的公式

21         v[q]=i;

22     }

23     printf("%lld\n",ans);

24     return 0;

25 }

C题题意：

输入一个n，让你找出来n*n阶方阵，他们任意两行的相同列的乘积之和为0，n只可能是2^k(k是1,2,...10)

题目

题解：

就是2阶方阵有

1 1 那么4阶方阵就可以把2阶方阵当作一个单位A ，即：A A A = 1 1

1 -1　　　　　　　　　　　　　　　　　　　　　　　 A -A　　　　　1 -1

具体为什么这样可以，你可以写出来任意挑选两行试试

比如四阶的第一行和第三行，前半列他们是一样的，所以就是2，但是后半列因为第三行后半列乘与一个-1，所以2就变成了-2

　　　　第一行和第四行，他们的前半列正好和2阶的一样，所以前半部分是0，后半部分乘与0*-1还是0

代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<math.h>

 6 #include<stack>

 7 #include<math.h>

 8 using namespace std;

 9 typedef long long ll;

10 const int maxn=1500;

11 int w[maxn][maxn],v[maxn][maxn];

12 int n;

13 void change(int ci,int ends)

14 {

15     if(ci==ends) return;

16     memset(v,0,sizeof(v));

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

18     {

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

20         {

21             v[i][j]=w[i][j];

22         }

23     }

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

25     {

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

27         {

28             v[i][j+n]=w[i][j];

29         }

30     }

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

32     {

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

34         {

35             v[i+n][j]=w[i][j];

36         }

37     }

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

39     {

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

41         {

42             v[i+n][j+n]=-w[i][j];

43         }

44     }

45     n*=2;

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

47     {

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

49         {

50             w[i][j]=v[i][j];

51         }

52     }

53     change(ci+1,ends);

54 }

55 void print()

56 {

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

58     {

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

60         {

61             if(j!=n)

62             printf("%d ",w[i][j]);

63             else printf("%d\n",w[i][j]);

64         }

65     }

66 }

67 int main()

68 {

69     w[1][1]=w[1][2]=w[2][1]=1;

70     w[2][2]=-1;

71     n=2;

72     int m;

73     scanf("%d",&m);

74     if(m==2)

75         print();

76     else

77     {

78         int k=0;

79         while(m!=2)

80         {

81             m/=2;

82             k++;

83         }

84         change(0,k);

85         print();

86     }

87     return 0;

88 }

巴特西

2019牛客暑期多校训练营（第八场）B Beauty Values && C CDMA

最新文章

热门文章