补了一波美团2019春招的题目，据说这次美团的题目有点难QAQ，第三题的树形dp太恶心了，吃了没文化的亏。。。
蛇形矩阵
题目
传送门：https://www.acwing.com/problem/content/758/
输入两个整数n和m，输出一个n行m列的矩阵，将数字 1 到 n*m 按照回字蛇形填充至矩阵中。
具体矩阵形式可参考样例。
输入格式
输入共一行，包含两个整数n和m。
输出格式
输出满足要求的矩阵。
矩阵占n行，每行包含m个空格隔开的整数。
数据范围
1≤n,m≤1001≤n,m≤100
输入样例：
输出样例：
题解
这题是比较简单的题目，从看到AC也非常的快(毕竟练过不少迷宫题)，只要将4个方向的先后顺序搞清楚，然后对4取模达到转弯的效果即可
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
| #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int mp[150][150];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
int d=0,x=0,y=0;
memset(mp,0,sizeof(mp));
for(int i=1;i<=n*m;i++){
mp[x][y]=i;
if(i==n*m)
break;
while(x+dx[d]<0||x+dx[d]>=n||y+dy[d]<0||y+dy[d]>=m||mp[x+dx[d]][y+dy[d]]!=0)
d++,d%=4;
x+=dx[d],y+=dy[d];
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(j) printf(" ");
printf("%d",mp[i][j]);
}
printf("\n");
}
}
return 0;
}
|
修改矩阵
题目
传送门：https://www.acwing.com/problem/content/759/
我们称一个矩阵为黑白矩阵，当且仅当对于该矩阵中每一个位置如(i, j)，其上下左右四个方向的数字相等，即(i-1, j)、(i+1, j)、(i, j-1)、(i, j+1)四个位置上的数字两两相等且均不等于(i, j)位置上的数字。（超出边界的格子忽略）
现在给出一个 n*m 的矩阵，我们想通过修改其中的某些数字，使得该矩阵变成黑白矩阵，请问最少需要修改多少个数字。
输入格式
第一行包含两个整数n和m，表示矩阵的长宽。
接下来n行，每行包含m个整数，用来表示整个矩阵。
输出格式
仅包含一个整数，表示原矩阵变为黑白矩阵最少修改的数字数量。
数据范围
1≤n,m≤1051≤n,m≤105,
1≤n∗m≤1051≤n∗m≤105
输入样例1：
输出样例1：
输入样例2：
输出样例2：
题解
由于题目的性质我们可以很快得出到最后其实矩阵中只会剩下两种数字，所以我们只要将矩阵分成奇数和偶数的格子就可以，然后我们对于奇数和偶数的格子分别开一个哈希表计数。
然后我们需要对哈希表进行排序，分别选出最大的和次大的，如果恰巧两种格子的最大的数量的数字相等，那么我们就要牺牲一个最大的去选择次大的，所以我们最后需要分类讨论一下
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
| #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=(int)1e5;
typedef pair<int,int> P;
P s1[maxn],s2[maxn];
bool cmp(P a,P b){
return a.first>b.first;
}
int main(){
ios::sync_with_stdio(false);
int n,m,k,in,mx;
while(cin>>n>>m){
k=1,mx=0;
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
for(int i=0;i<n;i++){
if(m%2==0)
k=!k;
for(int j=0;j<m;j++){
cin>>in;
mx=max(mx,in);
if(k)
s1[in].first++,s1[in].second=i;
else
s2[in].first++,s2[in].second=i;
k=!k;
}
}
sort(s1,s1+mx+1,cmp);
sort(s2,s2+mx+1,cmp);
if(s1[0].second==s2[0].second)
cout << min(n*m-s1[1].first-s2[0].first,n*m-s1[0].first-s2[1].first) << endl;
else
cout << n*m-s1[0].first-s2[0].first << endl;
}
return 0;
}
|
切割树
题目
传送门：https://www.acwing.com/problem/content/760/
给你一棵含有n个结点的树，编号为0~n-1，这n个结点都被染成了黑色或白色。
显然，对于一棵树而言，我们每去掉一条边就能把树分成两部分。
现在，要求你把这棵树切开，使得每一个连通块内只有一个白色结点。
问共有多少种切开的方式满足以上条件，如果被删除的边集不同，我们则认为两种方式不同，反之，认为相同。
请输出对1000000007取模后的结果。
输入格式
第一行仅包含一个正整数n，表示树的结点数量。
第二行包含n-1个数字，第 i 个数字表示第 i 个结点的根，我们认为 0 号结点是整棵树的根，第 i 个数字不超过 i，即第 i 个结点的根一定是编号小于 i 的结点。
第三行包含n个数字，第 i 个数字表示第 i-1 个结点的颜色，0表示白色，1表示黑色。
输出格式
输出一个整数表示对1000000007取模后的结果。
数据范围
1≤n≤1051≤n≤105
输入样例1：
输出样例1：
输入样例2：
1
2
3
| 10
0 0 1 2 0 5 1 2 3
1 0 0 1 0 0 1 1 0 1
|
输出样例2：
题解
树形dp啊啊啊啊啊啊啊，还没学会嘤嘤嘤，以后再补Orz
格子染色
题目
传送门：https://www.acwing.com/problem/content/761/
在二维平面上有一个无限的网格图形，初始状态下，所有的格子都是空白的。
现在有n个操作，每个操作是选择一行或一列，并在这行或这列上选择两个端点网格，把以这两个网格为端点的区间内的所有网格染黑（包含这两个端点）。
问经过n次操作以后，共有多少个格子被染黑，重复染色同一格子只计数一次。
输入格式
第一行包含一个正整数n。
接下来n行，每行包含四个整数x1,y1,x2,y2x1,y1,x2,y2，表示一个操作的两端格子坐标。
若x1=x2x1=x2则是在一列上染色，若y1=y2y1=y2则是在一行上染色。
保证每次操作是在一行或一列上染色。
输出格式
包含一个正整数，表示被染黑的格子的数量。
数据范围
1≤n≤100001≤n≤10000,
−109≤x1,y1,x2,y2≤109−109≤x1,y1,x2,y2≤109
输入样例：
1
2
3
4
| 3
1 2 3 2
2 5 2 3
1 4 3 4
|
输出样例：
题解
这题一开始没想出来，差点都上线段树了QAQ，后来发现其实是一题区间覆盖的问题，只不过是拓展到了二维
首先所有的更新操作我们将其分类，竖的和横的排在一起，然后将会重合的更新排在一起，在重合的里面先按照左端点排序，然后再按照右端点排序，这样就可以快速地合并了，合并的时候如果发现没有公共的区间，那就直接r-l+1加到答案里，如果有公共的区间我们就一直扩展，这样我们可以保证算完之后的所有的区间都是没有公共区间的
然后我们得到了横向的和纵向的区间，再暴力O(n)去判断横向的和纵向的相互之间是否交叉，如果发现一次两两交叉，最终的答案就-1，全部都枚举完之后就是最终的答案
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn=1e4;
typedef long long ll;
int n;
struct node{
int l,r,x;
node(int l,int r,int x):l(l),r(r),x(x){}
bool operator < (const node& a) const{
if(x!=a.x) return x<a.x;
if(l!=a.l) return l<a.l;
return r<a.r;
}
};
vector<node> vx,vy;
ll merge(vector<node>& v){
ll ans=0;
vector<node> vv;
sort(v.begin(),v.end());
for(int i=0;i<v.size();){
int j=i;
while(j<v.size()&&v[i].x==v[j].x) j++;
int l=v[i].l,r=v[i].r;
for(int k=i+1;k<j;k++){
if(r<v[k].l){
ans+=r-l+1;
vv.push_back(node(l,r,v[i].x));
l=v[k].l,r=v[k].r;
}
else
r=max(r,v[k].r);
}
ans+=r-l+1;
vv.push_back(node(l,r,v[i].x));
i=j;
}
v=vv;
return ans;
}
int main(){
int x1,y1,x2,y2;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1==x2)
vy.push_back(node(min(y1,y2),max(y1,y2),x1));
else
vx.push_back(node(min(x1,x2),max(x1,x2),y1));
}
ll ans=merge(vx)+merge(vy);
for(int i=0;i<vx.size();i++){
for(int j=0;j<vy.size();j++){
if(vy[j].x>=vx[i].l&&vy[j].x<=vx[i].r&&vx[i].x>=vy[j].l&&vx[i].x<=vy[j].r)
ans--;
}
}
printf("%lld\n",ans);
return 0;
}
|