2021级HAUT新生周赛（八）

A:似乎在梦里见过那样（传送门）

题目大意是求出一个凸多边形的面积。
我们根据高中知识可以得出，在面对求一个多边形面积时，如果多边形是三角形或者四边形可以直接使用公式来进行计算，那么遇见一个多边形一般是将一个多边形划分成为多个三角形.
那么我们只需要求出划分出来的三角形的面积，之后再进行求和即可。

那么我们再想一下如何划分三角形，由于题目给出了了是凸多边形，发现只要固定一个点，剩下的两个点在多边形的逆时针的点上依次选取即可，如图所示。

样例的图经过这样划分后就划分成为5个多边形，这样求出5个三角形就求出凸多边形面积了。

那么这样分为什么是正确的？如果换成凹多边形是否正确？

由于是凸多边形，那么这样划分的下一个三角形不会和上一个三角形有交集，而这样划分的三角形又可以覆盖整个多边形，所以是正确的。
但是如果是凹多边形就会出现错误，会出现重复的部分，并且会出现三角形外部的部分，如：

凹多边形的面积可以使用容斥原理，就是一些划分三角形面积记位正值，一些记位负值，这样就可以求出了。这里不过多涉及，但是标程代码可以实现求出凹多边形的面积

还有一点精度问题，这里使用叉乘的方式求出面积，就是三角形两个边的向量的叉乘结果是三角形面积两倍。

时间复杂度$O(n)O(n)$

#include <stdio.h>
#include <math.h>

typedef struct Node{  // 定义一个结构体即表示点，又表示向量
	double x,y ;
}node;

node p[110] ;  // 因为最多100个

double across(node a,node b){  // 返回两个向量的叉乘
	return a.x * b.y - a.y * b.x ;
}

double area(node a,node b,node c){  // 将三个点转化为两条边的向量
    node x,y ;
    x.x = b.x - a.x ;
    x.y = b.y - a.y ;
    y.x = c.x - a.x ;
    y.y = c.y - a.y ;
	return across(x,y) ;
}

int main()
{
	int n ;
	scanf("%d",&n) ;
	
	for(int i = 0 ; i < n ; i++){
		scanf("%lf%lf",&p[i].x,&p[i].y) ;
	}

	double ans = 0 ;
	for(int i = 1 ; i + 1 < n ; i++){ 
		ans += area(p[0],p[i],p[i+1]) ; // 划分的三角形第一个点固定为p[0],剩下的从两个点为i和i+1，这样来枚举所有三角形。
	}

	printf("%.2f\n",ans / 2) ;
    return 0;
}

// 这里不使用叉乘，使用海伦公式求出三角形面积也是可以通过的

B:那真是太令人高兴了（传送门）

题目其实就是问你那个字符串中含有problem这个序列，那么只需要暴力判断一下就行了。 那么就是暴力匹配串

代码实现

#include <stdio.h>
#include <string.h>

int n ;
char a[1100] ;
char tag[] = {"problem"} ;

int main()
{
	scanf("%d",&n);
	
	for(int i = 0 ; i < n ; i++){
		scanf("%s",a) ; // 读入字符串
		int m = strlen(a) ;
    	int flag = 0 ;
		for(int j = 0 ; j + 6 < m ; j++){
			flag = 1; 
			for(int k = 0 ;k < 7 ; k++){  // 判断从当前j位开始是否出现过problem
				if(a[j+k] != tag[k]) flag = 0 ;   // 不匹配置为0
			}
			if(flag) break ;
		}

		puts(a) ;  // 输出原来的串
		if(flag) puts("学到了") ;  // 如果flag没有置为0，则说明有problem这个串，那么输出
	}

    return 0;
}

C:已经没有什么好怕的了(传送门)

题目大意，就是找到异或值中二进制中1的个数等于询问个数的对的值。 由于数据量比较小，可以保留找。
保留枚举所有的对(由于这里说i，j和j，i是同一个对，那么你枚举的时候第二个循环就可以写成j = i + 1开始，这样保证j > i那么就保证不会重复枚举了，，，，，如果你是重复枚举的化，统计结果/2也是可以的。)

那么接下来就是如何求出当前数的二进制中1的个数 (1).可以使用位运算 x >> i & 1 ,就可以来判断x这个数第i位是不是1（不会位运算参考：博客中四右移运算符的应用，三取第k位的值） (2).可以将十进制转化位二进制，然后自然得到二进制中1的个数，oj有将十进制转化位二进制的原题传送门

时间复杂度$O(n^2)O(n^2)$

参考代码

#include <stdio.h>

int a[1100] ;

int get_count_1(int x){  // 得到x中1的数量的函数，这里我采用位运算方式，，你也可以使用转化为二进制的方式来求
	int cnt = 0 ;
	for(int i = 0 ; i <= 15 ; i ++){  // 只需要找i到15即可，因为小于2的14次方
		if(x >> i & 1) cnt ++ ;  // 判断第i位是不是1
	}
	return cnt ;
}

int main()
{
	int n,m ; 
	scanf("%d%d",&n,&m) ;

	for(int i = 0 ; i < n ;  i++) scanf("%d",&a[i]) ;

	while(m--){
		int t ;
		scanf("%d",&t) ;
		int cnt = 0 ;
		for(int i = 0 ; i < n ; i++){
			for(int j = i + 1 ; j < n ; j ++){  // 枚举对，这里j = i + 1,开始就是为了不重复枚举
				if(get_count_1(a[i] ^ a[j]) == t) cnt ++ ;
			}
		}
		printf("%d\n",cnt) ;
	}
    return 0;
}

D:奇迹魔法都是存在的(传送门)

题目大意，得到这个集合的所有子序列的异或的和

由于这个是数据比较弱，那么n是小于等于11的，那么我们可以自然的想到枚举所有的子序列，然后暴力求出答案即可。

那么如何进行枚举所有的集合，可以使用二进制枚举的方式，或者使用dfs的方式来枚举（就是每个是选是或者否）。

二进制枚举就算由于集合中每个数只有选或者不选两种装态，发现和二进制很想，那么可以使用二进制的0代表不选，1代表选，那么任意一个子序列都可以以一个二进制数来表示，而且这个二进制数是小于$2^{n}2^n$，因为只需要把n个数在0~n-1位表示即可，那么我们就可以使用一个循环来枚举所有的子序列。

时间复杂度:$O(2^n)O(2^n)$ 参考代码

#include <stdio.h>

int a[110] ;

int main(){
	int n ;
	scanf("%d",&n) ;

	for(int i = 0 ; i < n;i++) scanf("%d",&a[i]) ;  // 读入所有的数

	int ans = 0 ;
	for(int i = 0 ; i < (1 << n) ;  i++){  // 进行二进制枚举
		int x = 0 ;
		for(int j = 0 ; j < n ; j ++){  // 枚举n位选择情况，i就代表当前的子序列选择情况
			if(i >> j & 1){ // 如果i的第j位是1代表选第j个元素
				x ^= a[j] ;
			}
		}

		ans += x;  // 统计答案即可
	}

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

	return 0 ;
}

E:怎么可能会后悔(传送门)

这道题是D的加强数据的版本，数据范围不一样，由于n的范围比较大，是$10^{5}10^5$，所以不能使用二进制枚举的方法了，那么就需要挖掘一些性质。

对于每个数我们单独考虑第i位，那么一共n个数，设第i位是的0的个数是x，是1的个数是y，那么第i为对最后答案的贡献是什么？ 简单的推理得到贡献是$2^i\ast 2^{n-1}2^i\; *\; 2\; ^\; \{n-1\}$,那么考虑所有位，就可以得出答案是所有的数进行或的值记为$t\ast 2^{n-1}t*2^\{n-1\}$
$(1+x{)}^n=(C_n^0{x}^0+C_n^1{x}^1+C_n^2{x}^2+\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}+C_n^k{x}^k+\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}+C_n^n{x}^n)(1\; +\; x)^n\; =\; (C\_\{n\}^\{0\}\; x\; ^\; 0\; +\; C\_\{n\}^\{1\}\; x\; ^\; 1\; +\; C\_\{n\}^\{2\}\; x\; ^\; 2\; +\; ....\; .+\; C\_\{n\}^\{k\}\; x\; ^\; k\; +\; ....\; +\; C\_\{n\}^\{n\}\; x\; ^\; n)$

$(1+(-1){)}^n=(C_n^0-C_n^1+C_n^2-C_n^3+\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}+C_n^k{x}^k+\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}+C_n^n{x}^n)=0(1\; +\; (-1)\; )^n\; =\; (C\_\{n\}^\{0\}\; -\; C\_\{n\}^\{1\}\; +\; C\_\{n\}^\{2\}\; -\; C\_\{n\}^\{3\}\; +\; ....\; .+\; C\_\{n\}^\{k\}\; x\; ^\; k\; +\; ....\; +\; C\_\{n\}^\{n\}\; x\; ^\; n)\; =\; 0$

$(1+1{)}^n=(C_n^0+C_n^1+C_n^2+C_n^3+\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}+C_n^k{x}^k+\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}+C_n^n{x}^n)=2^n(1\; +\; 1)\; ^\; n\; =\; (C\_\{n\}^\{0\}\; +\; C\_\{n\}^\{1\}\; +\; C\_\{n\}^\{2\}\; +\; C\_\{n\}^\{3\}\; +\; ....\; .+\; C\_\{n\}^\{k\}\; x\; ^\; k\; +\; ....\; +\; C\_\{n\}^\{n\}\; x\; ^\; n)\; =\; 2\; ^\; n$

$2^n-0=2\ast (C_n^1+C_n^3+\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}+C_n^k{x}^k)=2^{n}2\; ^\; n\; -\; 0\; =\; 2\; *(\; C\_\{n\}^\{1\}\; +\; C\_\{n\}^\{3\}\; +\; ....\; .+\; C\_\{n\}^\{k\}\; x\; ^\; k\; )\; =\; 2\; ^\; n$

$C_n^1+C_n^3+\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}+C_n^k{x}^k=2^{n-1}C\_\{n\}^\{1\}\; +\; C\_\{n\}^\{3\}\; +\; ....\; .+\; C\_\{n\}^\{k\}\; x\; ^\; k\; =\; 2\; ^\; \{n-1\}$

$2^x\ast 2^{y-1}\ast 2^b=2^{x+y-1+b}=2^{n+b-1}=2^{n-1}\ast 2^{b}2^x\; *2^\{y-1\}\; *\; 2^b\; =\; 2\; ^\; \{x\; +\; y\; -\; 1\; +b\}\; =\; 2\; ^\{n\; +\; b\; -\; 1\}\; =\; 2\; ^\{n-1\}\; *\; 2\; ^b$

$x(101010)=2^{n-1}(1\ast 2^5+0\ast 2^4+1\ast 2^3+0\ast 2^2+1\ast 2^1+0\ast 2^0)x(101010)\; =\; 2\; ^\; \{n-1\}\; (1\; *\; 2^5\; +\; 0\; *\; 2^4\; +\; 1\; *\; 2\; ^3\; +\; 0\; *\; 2\; ^2\; +\; 1\; *\; 2^1+\; 0\; *\; 2^0)$

时间复杂度：$O(n)O(n)$

参考代码：

#include <stdio.h>

typedef long long ll ;  // def一下long long

const ll mod = 998244353 ;  // 模数

ll fast_pow(ll a,ll n,ll mod){  // 快速幂
	ll ans = 1 ;
	while(n){
		if(n&1) ans = ans * a % mod ;
		a = a * a % mod ;
		n >>= 1 ;
	}
	return ans ;
}

int main(){
	int n ;
	scanf("%d",&n) ;

	ll ans = 0 ;
	for(int i = 0 ; i < n ; i++){
		ll x ;
		scanf("%lld",&x) ;
		ans |= x ;
	}

	printf("%lld\n",ans * fast_pow(2,n-1,mod)%mod) ;
	return 0;
}

F:这种事绝对很奇怪啊(传送门)

题目大意是修建隧道可以使两两到达，任意两座城市间的修建费用是坐标距离。

显然如果x到y中间有其他的城市z，那么先修建x到z，再修建z到y的费用想等或者更低。

那么其实就是求出最右端点和最左端点的差值。（注意肯会超过int范围，所以使用long long）

时间复杂度：$O(n)O(n)$

参考代码：

#include <stdio.h>

typedef long long ll ;

int main()
{
    ll n ;
	scanf("%lld",&n) ;
	
	ll l,r ;   // l记录最左端，r记录最右端
	for(int i = 0 ; i < n ; i++){
		int x ;
		scanf("%d",&x) ;
		if(!i) l = x,r =x ;
		else{
			if(x < l) l = x; 
			if(x > r) r = x;
		}
	}
	
	printf("%lld",r - l) ;

    return 0;
}

G:你能面对真正的内心吗(传送门)

题目大意：小圆会按照顺序交题，那么用一个数来记录当前交到了第几题，那么进行一次循环即可。

时间复杂度:$O(n)O(n)$

参考代码：

#include <stdio.h>

int main()
{
	int n,m ;
	scanf("%d%d",&n,&m) ;

	int cnt = 0 ; // 记录当前做到第几题了
	for(int i = 1; i <= m; i ++){
		int x ;
		scanf("%d",&x) ;
		if(x == cnt + 1) cnt ++ ; // 判断x 是否是正确的题目号，当前做完的下一道
	}

	printf("%d\n",cnt) ;
    return 0;
}

H：我，真是个笨蛋(传送门)

题目大意：选出m个数，将选出的数或起来，得到或的最大值，那么由于一个数或上一个数会使原先的更大，那么由于m没有限制，那么将所有的数全部或起来就是最大值。 所以输出所有数或起来的最大值。

时间复杂度：$O(n)O(n)$

参考代码：

#include <stdio.h>

int main()
{
	int n ;
	scanf("%d",&n) ;
	
	int ans = 0 ;
	for(int i = 0 ; i < n ; i++){
		int x ;
		scanf("%d",&x) ;
		ans |= x ;
	}

	printf("%d\n",ans) ;
    return 0;
}