cf #817
A
判断一个字符串是否为另一个字符串的排列(字符串中字符互不相同)
分析：看了标答发现比较tricky的方法是把这两个string排序，然后直接判断==
太简单代码就不发了
E
题意：给定n个矩形，询问q次，每次给出hs,ws,hb,wb，输出在高度在(hs+1，hb-1)，宽度在(ws+1,wb-1)的矩形面积之和。
分析：要求一定范围内的矩形面积之和，考虑二维前缀和。sum[x][y]表示从(1,1)到(x,y)的面积之和。求某个区间的话，我们只需要sum[x2][y2]+sum[x1][y1]-sum[x2][y1]-sum[x1][y2]
主要还是不熟悉二维前缀和，可以结合一维前缀和一起理解。
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
| #include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef vector<int> vi;
typedef long long ll;
const int maxn=1005;
ll a[maxn][maxn];
ll sum[maxn][maxn];
int main(){
int tt;cin >> tt;
while (tt--){
int n,m;
cin >> n >> m;
for(int i=1;i<=1000;i++){
for(int j=1;j<=1000;j++){
a[i][j]=0;
}
}
for(int i=1;i<=n;i++){
int x,y;
cin >> x >> y;
a[x][y]+=1ll*x*y;
}
for(int i=1;i<=1000;i++){
for(int j=1;j<=1000;j++){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}
}
for(int i=1;i<=m;i++){
int h1,w1,h2,w2;
cin >> h1 >> w1 >> h2 >> w2;
cout << sum[h2-1][w2-1]+sum[h1][w1]-sum[h2-1][w1]-sum[h1][w2-1] << '\n';
}
}
return 0;
}
|
这里为了便于理解用了sum[][],实际完全可以用a[][]
F
f题考场上写了超级复杂的模拟，wa6了。。。
题意：给一个n*m的图，判断是否只包含L型(2*2中取三个格子)元素并且L型块之间不相邻(包括对角线)
分析：补题的时候看的SSRS巨佬的代码。思路主要是先找到一个‘*’之后用队列(可以理解为bfs)，把与这个’*‘相通的’*‘都找出来。如果cnt>3或者max(x)-min(x)!=1或者max(y)-min(y)!=1说明这个不是L型。我们在bfs时已经保证了不会出现L型相互连通的问题(因为那样我们会把它算成一个块，然后发现它不是L型)。
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 <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef vector<int> vi;
typedef long long ll;
const int maxn=100005;
int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
void solve(){
int n,m;
bool ok = true;
cin >> n >> m;
vector<vector<char>> c(n,vector<char>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin >> c[i][j];
}
}
vector<vector<bool>> used(n,vector<bool>(m,false));
queue<pair<int,int>> q;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!used[i][j]&&c[i][j]=='*'){
used[i][j]=true;
int cnt=0,mx=-1,my=-1,mix=100000,miy=100000;
q.push(make_pair(i,j));
while (!q.empty()){
int x=q.front().first;
int y=q.front().second;
mx=max(mx,x);
my=max(my,y);
mix=min(mix,x);
miy=min(miy,y);
cnt++;
q.pop();
for(int k=0;k<8;k++){
int ii=x+dir[k][0];
int jj=y+dir[k][1];
if(ii>=0&&ii<n&&jj>=0&&jj<m&&c[ii][jj]=='*'&&!used[ii][jj]){
used[ii][jj]=true;
q.push(make_pair(ii,jj));
}
}
}
if(cnt!=3||mx-mix!=1||my-miy!=1){
ok=false;
break;
}
}
}
if(!ok){
break;
}
}
if(ok) puts("YES");
else puts("NO");
}
int main(){
int tt;
cin >> tt;
while (tt--){
solve();
}
return 0;
}
|
G
题意：造n个互不相同的数，使得奇数位置的数异或起来等于偶数位置的数异或起来
分析：我们考虑异或的一个性质：a^a=0。那么这个题即为造n个互不相同的数，使得n个数异或起来为0。
显然我们第一反应就是令第n个数为前n-1个数的异或，但是问题在于这样产生的第n个数可能与前n-1个数重复。
故我们需要考虑一下设置含高位1的数，这样便不会与前面的较小的数重合。考虑到该问题中n最大为10^5，大致估计最多也就十几位，我们可以前n-3个数为1到n-3，然后第n-2个为(1<<29)，第n-1个为(1<<30)，第n个为前n-1个的异或和。这样设计的原理是首先后三个数都含有29或30的高位，一定不会与1到n-3中的数字重复，另外第n个数同时包含29和30位，一定不会与(1<<29)和(1<<30)重复。故该造法一定有效。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef vector<int> vi;
typedef long long ll;
const int maxn=100005;
int main(){
int tt;
cin >> tt;
while (tt--){
int n;
int ans=0;
cin >> n;
for(int i=1;i<=n-3;i++){
printf("%d ",i);
ans^=i;
}
printf("%d %d %d\n",(1<<29),(1<<30),ans^(1<<29)^(1<<30));
}
return 0;
}
|
Tip
1
2
| vector<vector<char>> c(n, vector<char>(m)); //n,m的字符数组
vector<vector<bool>> used(n, vector<bool>(m, false));
|
