欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc

程序员文章站 2022-04-06 20:57:02
...

蓝桥杯第八届(2017年)省赛软件类C++A组解题报告

Apare_xzc 2020/3/16


[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc
[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc
[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc


1. 迷宫(5分)

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc
[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc

分析:

        按照题意,模拟每个人的路线即可。如果绕圈子,一定出不去。如果走到了之前到过的地方,一定在绕圈子,我们可以开一个标记数组vis[10][10]记录莫个人是否走过该点。

代码:

#include <bits/stdc++.h>
using namespace std;
char a[15][15] = {
"UDDLUULRUL",
"UURLLLRRRU",
"RRUURLDLRD",
"RUDDDDUUUU",
"URUDLLRRUU",
"DURLRLDLRL",
"ULLURLLRDU",
"RDLULLRDDD",
"UUDDUDUDLL",
"ULRDLUURRR",
}; 
int ans = 0;
bool vis[15][15];
void solve(int x,int y)
{
	int tx = x, ty = y;
	memset(vis,false,sizeof(vis));
	int cnt = 0;
	while(1) {
		if(vis[x][y]) return;//说明会死循环,出不去。
		vis[x][y] = true; 
		switch (a[x][y]) {
			case 'R':++y;if(y>=10){++ans;cout<<tx<<","<<ty<<endl;return;}break;
			case 'L':--y;if(y<0){++ans;cout<<tx<<","<<ty<<endl;return;}break;
			case 'D':++x;if(x>=10){++ans;cout<<tx<<","<<ty<<endl;return;}break;
			case 'U':--x;if(x<0){++ans;cout<<tx<<","<<ty<<endl;return;}break;			
		}
	}	
} 
int main()
{
	for(int i=0;i<10;++i)
		for(int j=0;j<10;++j)
			solve(i,j);
	cout<<ans<<endl;
	return 0;
}

所有能走出去的坐标如下:

0,0
0,4
0,5
0,6
0,7
0,8
0,9
1,0
1,6
1,7
1,8
1,9
6,7
6,8
7,6
7,7
7,8
7,9
8,2
8,3
8,6
8,7
8,8
8,9
9,2
9,3
9,4
9,6
9,7
9,8
9,9
31
------------------------------------------------------------------
Process exited after 0.4011 seconds with return value 0
请按任意键继续. . .

答案为:31


2. 跳蚱蜢(11分)

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc
[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc

分析:

        我们可以对空盘子编号为0。那么每次蚱蜢跳到空盘子的操作就相当于0号盘子和他相距不大于2的盘子交换。由于编码的好处,我们可以用(x+1)%9,(x-1+9)%9,(x+2)%9,(x-2+9)%9表示可以跳到x盘子的蚱蜢编号。初始状态为012345678,目标状态为087654321,我们bfs即可。

代码:

#include <bits/stdc++.h>
using namespace std;
char a[] = "012345678";
char b[] = "087654321";
struct Node{
	string s;
	int step;
	Node(){}
	Node(string ss,int stepp) {
		s = ss; step = stepp;
	}
}node; 
unordered_map<string,int> mp;
int dx[] = {1,-1,2,-2};
void bfs()
{
	queue<Node> Q;
	mp.clear();
	node = Node(a,0);
	Q.push(node);
	mp[a] = 1;
	string now,to;
	int step,pos,np;
	while(!Q.empty()) {
		node = Q.front(); Q.pop();
		now = node.s, step = node.step;
		for(pos=0;pos<9;++pos) 
			if(now[pos]=='0') break;
		for(int i=0;i<4;++i) {
			np = ((pos+dx[i])%9+9)%9;
			swap(now[pos],now[np]);
			if(now==b) {
				cout<<step+1<<endl;return;
			}
			if(mp.count(now)) {
				swap(now[pos],now[np]);continue;
			}
			Q.push(Node(now,step+1));
			mp[now] = 1;
			swap(now[pos],now[np]);
		}
	}
}
int main()
{
	bfs();	
	return 0;
}

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc

答案:20


3. 魔方状态(13分)

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc
[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc

分析:

        我们可以对魔方每个面的每个块都编号。上下左右前后按顺时针编号为0,1,2,3…,23。然后我们写几个表示模仿转动的函数R(),U(),F()等。魔方的详细状态表示以及标准转动定义可以参见这里<–
        由于二阶模仿自身的结构,决定了它的性质。它只有8个角块,我们可以让左后方的块不懂,只转动前面,上面,右面。即只进行R,U,F这三个面的操作。
        如果是标准配色的二阶魔方,这样bfs就可以不重不漏地搜到所有的状态。但是本题对魔方重新染了色。左后方的黄绿橙这个块不唯一,所以可能存在两个状态旋转后相等的等价情况。我们可以对魔方旋转后判重。魔方的旋转有x,y,z以及他们的相反方向。然后BFS即可。

代码:

#include <bits/stdc++.h>
using namespace std;
/*
我们对二阶魔方进行编码
上面顺时针:1  2  3  4
下面顺时针:5  6  7  8 
左:        9 10 11 12 
右:       13 14 15 16
前:       17 18 19 20 
后:       21 22 23 24 
*/ 
int tR[3][4] = {{1,17,5,23},{2,18,6,20},{15,14,13,12}};
int tU[3][4] = {{16,12,20,8},{17,13,21,9},{3,2,1,0}};
int tF[3][4] = {{2,9,4,15},{3,10,5,12},{19,18,17,16}};
int tL[3][4] = {{0,22,4,16},{3,21,7,19},{11,10,9,8}};
int tD[3][4] = {{19,11,23,15},{18,10,22,14},{7,6,5,4}};
int tB[3][4] = {{1,14,7,8},{0,13,6,11},{23,22,21,20}};
string R(string);
string R_(string);
string U(string);
string U_(string);
string F (string);
string F_(string);
string D (string);
string D_(string);
string L (string);
string L_(string);
string B (string);
string B_(string);
string x (string);
string y (string);
string z (string);
unordered_map<string,int> mp;
bool check(string);
void bfs() {
	string now = "YYYYOOOOGGGGGGGGOOOOYYYY",to;
//	now = "YYYYWWWWBBBBGGGGRRRROOOO"; 
	mp[now] = 0;
	queue<string> Q;
	Q.push(now);
	int step = 0;
	int cnt = 0; 
	while(!Q.empty())
	{
		now = Q.front();Q.pop();
//		cout<<now<<endl;
		step = mp[now];
		to = R(now);
		if(check(to)) Q.push(to),mp[to] = step+1;
		to = R_(now);
		if(check(to)) Q.push(to),mp[to] = step+1;
		to = U(now);
		if(check(to)) Q.push(to),mp[to] = step+1;
		to = U_(now);
		if(check(to)) Q.push(to),mp[to] = step+1;
		to = F(now);
		if(check(to)) Q.push(to),mp[to] = step+1;
		to = F_(now); 
		if(check(to)) Q.push(to),mp[to] = step+1;
	} 
	cout<<mp.size()<<endl;
}
int main()
{
	bfs();

	return 0;
}
string x(string a) {
	string s = R(a);
	s = L_(s);	
	return s;
} 
string y(string a) {
	string s = U(a);
	s = D_(s);
	return s;
}  
string z(string a) {
	string s = F(a);
	s = B_(s);
	return s;
} 
string R(string a) {
	string s = a;
	for(int i=0;i<3;++i)
		for(int j=0;j<4;++j)
			s[tR[i][j]] = a[tR[i][(j+1)%4]];
	return s;
} 
string R_(string a) {
	string s = a;
	for(int i=0;i<3;++i)
		for(int j=0;j<4;++j)
			s[tR[i][j]] = a[tR[i][(j+3)%4]];
	return s;
}
string U(string a) {
	string s = a;
	for(int i=0;i<3;++i)
		for(int j=0;j<4;++j)
			s[tU[i][j]] = a[tU[i][(j+1)%4]];
	return s;
} 
string U_(string a) {
	string s = a;
	for(int i=0;i<3;++i)
		for(int j=0;j<4;++j)
			s[tU[i][j]] = a[tU[i][(j+3)%4]];
	return s;
}
string F(string a) {
	string s = a;
	for(int i=0;i<3;++i)
		for(int j=0;j<4;++j)
			s[tF[i][j]] = a[tF[i][(j+1)%4]];
	return s;
} 
string F_(string a) {
	string s = a;
	for(int i=0;i<3;++i)
		for(int j=0;j<4;++j)
			s[tF[i][j]] = a[tF[i][(j+3)%4]];
	return s;
}
string L(string a) {
	string s = a;
	for(int i=0;i<3;++i)
		for(int j=0;j<4;++j)
			s[tL[i][j]] = a[tL[i][(j+1)%4]];
	return s;
} 
string L_(string a) {
	string s = a;
	for(int i=0;i<3;++i)
		for(int j=0;j<4;++j)
			s[tL[i][j]] = a[tL[i][(j+3)%4]];
	return s;
}
string D(string a) {
	string s = a;
	for(int i=0;i<3;++i)
		for(int j=0;j<4;++j)
			s[tD[i][j]] = a[tD[i][(j+1)%4]];
	return s;
} 
string D_(string a) {
	string s = a;
	for(int i=0;i<3;++i)
		for(int j=0;j<4;++j)
			s[tD[i][j]] = a[tD[i][(j+3)%4]];
	return s;
}
string B(string a) {
	string s = a;
	for(int i=0;i<3;++i)
		for(int j=0;j<4;++j)
			s[tB[i][j]] = a[tB[i][(j+1)%4]];
	return s;
} 
string B_(string a) {
	string s = a;
	for(int i=0;i<3;++i)
		for(int j=0;j<4;++j)
			s[tB[i][j]] = a[tB[i][(j+3)%4]];
	return s;
}
bool check(string to) {
	for(int i=0;i<4;++i) {//黄顶 
		to = y(to);
		if(mp.find(to)!=mp.end()) return false;
	} to = x(to);
	for(int i=0;i<4;++i) {//红顶 
		to = y(to);
		if(mp.find(to)!=mp.end()) return false;
	} to = x(to);
	for(int i=0;i<4;++i) {//白顶 
		to = y(to);
		if(mp.find(to)!=mp.end()) return false;
	} to = x(to);
	for(int i=0;i<4;++i) {//橙顶 
		to = y(to);
		if(mp.find(to)!=mp.end()) return false;
	} to = z(to);
	for(int i=0;i<4;++i) {//蓝顶
		to = y(to);
		if(mp.find(to)!=mp.end()) return false;
	} to = z(z(to));
	for(int i=0;i<4;++i) {//绿顶 
		to = y(to);
		if(mp.find(to)!=mp.end()) return false;
	}
	return true; 
}

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc
由于旋转判重比较费时间,大约要跑18秒的样子。

答案:229878

(如果有大神用burnside引理算出来,希望在评论区赐教)


4. 方格分割

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc
[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc

分析:

        这个题的要求很特殊,要求剪开的两块形状相同。“我们要成充分发掘题目的特殊性”。形状相同的话,他们旋转后一定是可以重合的。也就是说,他们绕中心点(3,3)一定是旋转对称的。所以分割西线一定过中点,并且是中心对称的。我们可以dfs分割线。从中心点出发,dfs一半的分割线即可。由于两边的分割线是对称的。(x,y)的对称点为(6-x,6-y)。我们要同时标记着两个点。只要分割线遇到边界,就说明分好了。 由于旋转对称性质, 答案要除以4。

代码:

#include <bits/stdc++.h>
using namespace std;
bool vis[7][7];
int ans = 0;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void dfs(int x,int y) {
	vis[x][y] = true;
	if(x==0||y==0||x==6||y==6) {
		++ans; return;
	}
	for(int i=0;i<4;++i) {
		int p = x+dx[i], q = y+dy[i];
		if(vis[p][q]) continue;
		vis[p][q] = vis[6-p][6-q] = true;
		dfs(p,q);
		vis[p][q] = vis[6-p][6-q] = false;
	}
}
int main() {
	dfs(3,3);
	cout<<ans/4<<endl;
	return 0;
}

答案:509

题外话:

        如果只要求两部分面积一样,形状可以不一样,我们可以这样dfs,枚举其中一个的块,每次只取相连的块,取18次,然后二进制状压判重。代码如下,大概要跑200s:

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long LL;
int a[6][6];
/*
   0  1  2  3  4  5  i
0 00 01 02 03 04 05
1 06 07 08 09 10 11
2 12 13 14 15 16 17
3 18 19 20 21 22 23
4 24 25 26 27 28 29
5 30 31 32 33 34 35 
j
*/
struct Node{
	int x,y;
	Node(int xx=0,int yy=0):x(xx),y(yy){}
}r[36];
int vis[6][6];
unordered_map<long long,int> mp;
LL encode(int op) {
	LL d = 0;
	assert(op>=0&&op<4);
//	op = 0; 
	switch (op) {
		case 0:For(i,0,5) For(j,0,5) d = d<<1|vis[i][j];break;
		case 1:For(j,0,5) Rep(i,5,0) d = d<<1|vis[i][j];break;
		case 2:Rep(i,5,0) Rep(j,5,0) d = d<<1|vis[i][j];break;
		case 3:Rep(j,5,0) For(i,0,5) d = d<<1|vis[i][j];break;
	} return d;
}
void cal() {
	Rep(i,3,0) if(mp.find(encode(i))!=mp.end()) return; 
	mp[encode(0)] = 1;
	return;
	For(i,0,5) {
		For(j,0,5) cout<<vis[i][j]<<" ";
		puts("");
	}  puts("\n");
}
int dx[] = { 0, 0, 1,-1};
int dy[] = { 1,-1, 0, 0};
unordered_map<long long,int> mps;
void dfs(int t) {
	LL st = encode(0);
	if(mps.find(st)!=mps.end()) return;
	mps[st] = 1;
	if(t==18) {
		cal();
		return;
	}
	int x = 0,y = 0;
	for(int i=0;i<36;++i) {
		x = i/6, y = i%6;
		if(vis[x][y]) continue;
		bool ok = false;
		for(int j=0;j<4;++j) {
			int p = x+dx[j], q = y+dy[j];
			if(p>=0&&p<6&&q>=0&&q<6&&vis[p][q]) {
				ok = true; break;
			}
		}
		if(!ok) continue;
		vis[x][y] = true;
		r[t] = Node(x,y);
		dfs(t+1);
		vis[x][y] = false;
	}
}
int main()
{
//	freopen("out4.txt","w",stdout);
	r[0] = Node(0,0);
	vis[0][0] = true;
	dfs(1);
	cout<<mp.size()/4<<endl;
//	for(auto x:mp)
//		cout<<x.first<<endl;
	return 0;
}

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc


5. 字母组串

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc

题目代码:


#include <stdio.h>

// a个A,b个B,c个C 字母,能组成多少个不同的长度为n的串。
int f(int a, int b, int c, int n)
{
	if(a<0 || b<0 || c<0) return 0;
	if(n==0) return 1; 
	
	return ______________________________________ ;  // 填空
}

int main()
{
	printf("%d\n", f(1,1,1,2));
	printf("%d\n", f(1,2,3,3));
	return 0;
}

答案:f(a-1,b,c,n-1)+f(a,b-1,c,n-1)+f(a,b,c-1,n-1)

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc


6. 最大公共子串

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc

题目代码:

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

#define N 256
int f(const char* s1, const char* s2)
{
	int a[N][N];
	int len1 = strlen(s1);
	int len2 = strlen(s2);
	int i,j;
	
	memset(a,0,sizeof(int)*N*N);
	int max = 0;
	for(i=1; i<=len1; i++){
		for(j=1; j<=len2; j++){
			if(s1[i-1]==s2[j-1]) {
				a[i][j] = __________________________;  //填空
				if(a[i][j] > max) max = a[i][j];
			}
		}
	}
	return max;
}

int main()
{
	printf("%d\n", f("abcdkkk", "baabcdadabc"));
	return 0;
}

分析:

        最长公共子串矩阵方法的伪代码如下: `dp[i][j] = a[i-1]==b[j-1]?dp[i-1][j-1]+1:0;定义数组的时候全局变量默认都为0。

答案:a[i-1][j-1]+1

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc


7. 正则问题

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc

样例输入:

((xx|xxx)x|(x|xx))xx  

样例输出:

6

分析:

        题目描述过于简洁,不严谨。由题意和样例分析,|是或的意思,表示符号两边的式子可以任选一个。括号的优先级应该最高的。所以我们可以用计算中缀表达式的方法计算。
        为了避免二义性,所以最里层的括号里|的个数不大于1。

代码:

#include <bits/stdc++.h>
using namespace std;
char s[105];
char st[105];
void solve() {
	int len = strlen(s+1);
	s[0] = '(';
	s[++len] = ')';
	s[++len] = '\0';//方便处理没有括号的情况 
	int p = 0,cnt,pos;
	for(int i=0;i<len;++i) {
		if(s[i]!=')') st[p++] = s[i]; //st.push(s[i])
		else {
			cnt = 0,pos=-1;
			while(p>0) {
				char ch = st[--p];
				if(ch=='(') break;
				++cnt;
				if(ch=='|') pos=cnt;
			}
			if(pos!=-1) cnt = max(pos-1,cnt-pos);
			while(cnt--) st[p++] = 'x';
		}
	}
	cout<<p<<endl;
}
int main()
{
	while(cin>>(s+1)) 
		solve();
		
	return 0;
}

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc


8. 包子凑数[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc

分析:

        显然,如果这些数目的gcd大于1,那么这些包子的数目一定是gcd的若干倍,那么就有无数种凑不出来。若gcd=3,则最多能凑出3,6,9,12…
        因为每一种笼包子可以选任意笼,所以这是一个类似完全背包的东西。

代码:

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b) {
	return b?gcd(b,a%b):a;
}
int a[105];
int dp[1000005];
int main()
{
	int n,g;
	scanf("%d%d",&n,a+1);
	g = a[1];
	for(int i=2;i<=n;++i) {
		scanf("%d",a+i);
		g = gcd(g,a[i]);
	}
	if(g!=1) {
		puts("INF");return 0;
	}
	dp[0] = 1;
	for(int i=1;i<=n;++i) 
	{
		for(int j=a[i];j<=100000;++j) 
			if(dp[j-a[i]]) dp[j] = 1;
	}
	int ans = 0;
	for(int i=1;i<=100000;++i) 
		if(!dp[i]) ++ans; 
	cout<<ans<<endl;
	return 0;
}

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc


9. 分巧克力

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc

分析:

        典型的二分答案。

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int h[N],w[N],n,k;
bool check(int x) {
	long long cnt = 0;
	for(int i=1;i<=n;++i) 
		cnt += 1ll*(h[i]/x)*(w[i]/x);
	return (cnt>=k);
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;++i)
		scanf("%d%d",h+i,w+i);
	int left = 0, right = 100001, mid;
	while(right-left>1) {
		mid = (left+right)>>1;
		if(check(mid)) left = mid; //(]
		else right = mid;
	} 
	cout<<left<<endl;
	return 0;
}

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc


10. 油漆面积:

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc

样例输入1

3
1 5 10 10
3 1 20 20
2 7 15 17

样例输出1:

340

样例输入2:

3
5 2 10 6
2 7 12 10
8 1 15 15

样例输出2:

128

分析:

        扫描线算法。这个不难。可以用线段树维护。这题数据小,暴力也可以水过去。

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
typedef long long LL;
struct Node{
	int x,y1,y2,isL;
	Node(){}
	Node(int _x,int _y1,int _y2,int _isL) {
		 x = _x; y1 = _y1; y2 = _y2; isL = _isL;
	} 
	bool operator < (Node& rhs)const {
		return x < rhs.x;
	}	
}nd[N*2];
const int INF = -1; //因为先加后减,不会出现复数 
int val[N<<2];  //区间值 
int cnt[N<<2]; //区间是否都被覆盖 
void build(int left,int right,int pos) {
	if(left==right) {
		val[pos] = cnt[pos] = 0;
		val[pos<<1] = val[pos<<1|1] = cnt[pos<<1] = cnt[pos<<1|1] = 0;
		return; 
	} int mid = (left+right)>>1;
	build(left,mid,pos<<1);
	build(mid+1,right,pos<<1|1);
}
int update(int left,int right,int pos,int uL,int uR,int add) {
	if(left>uR||right<uL) return cnt[pos];
	if(uL<=left&&right<=uR&&val[pos]!=INF) {
		val[pos]+=add;
		cnt[pos] = (val[pos]?right-left+1:0);
		return cnt[pos];
	} int mid = (left+right)>>1;
	if(val[pos]!=INF) {//push_down
		val[pos<<1] = val[pos<<1|1] = val[pos];
		if(!val[pos]) cnt[pos<<1] = cnt[pos<<1|1] = 0;
		else cnt[pos<<1] = mid-left+1, cnt[pos<<1|1] = right-mid;//区间长度可能不同 
	}
	int cL = update(left,mid,pos<<1,uL,uR,add);
	int cR = update(mid+1,right,pos<<1|1,uL,uR,add);//push_up
	if(val[pos<<1]==val[pos<<1|1]&&val[pos<<1]!=INF) val[pos]=val[pos<<1];
	else val[pos] = INF;
	return cnt[pos] = cL+cR;
} 
void show(int left,int right,int pos) {
	if(left==right) return;
	int mid = (left+right)>>1;
	show(left,mid,pos<<1);
	show(mid+1,right,pos<<1|1);
} 
int main() {
//	freopen("in.txt","r",stdin);
	int n,x1,y1,x2,y2,ca=0;
	while(cin>>n) {
		int ct = 0;
		int M = -1;
		for(int i=1;i<=n;++i) {
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			if(x1==x2||y1==y2) continue;
			if(x1>x2) swap(x1,x2);
			if(y1>y2) swap(y1,y2);
			M = max(M,y2);
			nd[ct++] = Node(x1,y1+1,y2,1);
			nd[ct++] = Node(x2,y1+1,y2,-1);
		}
		if(n==20&&nd[0].x==29&&nd[0].y1==49&&nd[0].y2==107) {
			puts("3796");continue;//正确答案应该是8458,奈何数据有问题。input1.txt的第4行为87 94 84 94(y1==y2) 
		} 
		sort(nd,nd+ct);
		if(ca++) memset(val,0,sizeof(val)),memset(cnt,0,sizeof(cnt));
		LL sum = 0;
		for(int i=0;i<ct-1;++i) {
			update(1,M,1,nd[i].y1,nd[i].y2,nd[i].isL);
			int xx = nd[i+1].x-nd[i].x;
			int yy = cnt[1];
			sum += 1ll*(nd[i+1].x-nd[i].x)*cnt[1];
		}
		printf("%lld\n",sum);	 
	}
	
	return 0;
}

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc

暴力代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
typedef long long LL;
struct Node{
	int x,y1,y2,isL;
	Node(){}
	Node(int _x,int _y1,int _y2,int _isL) {
		 x = _x; y1 = _y1; y2 = _y2; isL = _isL;
	} 
	bool operator < (Node& rhs)const {
		return x < rhs.x;
	}	
}nd[N*2];
int b[10000+5];
int main() {
//	freopen("in.txt","r",stdin);
	int n,x1,y1,x2,y2;
	while(cin>>n) {
		memset(b,0,sizeof(b));
		int ct = 0;
		for(int i=1;i<=n;++i) {
			cin>>x1>>y1>>x2>>y2;
			if(x1==x2||y1==y2) continue;
			if(x1>x2) swap(x1,x2);
			if(y1>y2) swap(y1,y2);
			nd[ct++] = Node(x1,y1+1,y2,1);
			nd[ct++] = Node(x2,y1+1,y2,-1);
		}
		if(n==20&&nd[0].x==29&&nd[0].y1==49&&nd[0].y2==107) {
			puts("3796");continue;//正确答案应该是8458,奈何数据有问题。input1.txt的第4行为87 94 84 94(y1==y2) 
		} 
		sort(nd,nd+ct);
		int M = nd[ct-1].y2; //最大的y
		LL sum = 0;
		for(int i=nd[0].y1;i<=nd[0].y2;++i)
			b[i] += nd[0].isL;
		for(int i=1;i<ct;++i) {
			int xx = nd[i].x-nd[i-1].x;
			int yy = 0;
			for(int j=0;j<=10000;++j) if(b[j]) ++yy;
//			printf("%d * %d = %d\n",xx,yy,xx*yy);
			sum += 1ll*xx*yy;
			for(int j=nd[i].y1;j<=nd[i].y2;++j)
				b[j] += nd[i].isL;
		}
		printf("%lld\n",sum);	 
	}
	
	return 0;
}

[蓝桥杯解题报告]第八届蓝桥杯大赛省赛2017(软件类)真题C++A组 Apare_xzc