Puzzle: Square Jam
题目大意
给定一个的矩形，要求你将其分割成若干个正方形，使得没有一个点是四个正方形的交点、
解题思路
用辗转相减法可以完美解决，对于每个矩形，每次切割一个最大的正方形进行递归处理即可。
参考代码
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
| #include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;
bool multi=1;
struct Node{
int x,y,l;
};
vector<Node> ans;
void dfs(int x1,int y1,int x2,int y2){
if(x2-x1!=y2-y1){
if(x2-x1>y2-y1){
ans.push_back((Node){x1,y1,y2-y1+1});
dfs(x1+(y2-y1+1),y1,x2,y2);
}else{
ans.push_back((Node){x1,y1,x2-x1+1});
dfs(x1,y1+(x2-x1+1),x2,y2);
}
}else{
ans.push_back((Node){x1,y1,x2-x1+1});
}
}
void solve(){
ans.clear();
int n,m;
cin>>n>>m;
dfs(1,1,n,m);
cout<<"YES"<<'\n';
cout<<ans.size()<<'\n';
for(int i=0;i<ans.size();i++){
cout<<ans[i].x-1<<' '<<ans[i].y-1<<' '<<ans[i].l<<"\n";
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T=1;
if(multi) cin>>T;
while(T--){
solve();
}
return 0;
}
|
Non-Puzzle: Error Permutation
题目大意
给定一个长度为的全排列，计算满足以下条件的子段的数量。
条件：对于子段中的每个i，满足子段中的第i个位置不是第i小。
解题思路
（写的比较啰嗦，因为感觉表达的不清楚就想讲详细一点）
正向考虑即找到有多少个区间满足每个位置i上的数都不是第i小。
正难则反，考虑计算所有子段数量减去不符合条件的子段数量。
所有字段数量显然
重点就是对不符合条件的子段数量进行计算：
首先预处理每个数右边所有比他小的数的下标，显然可以完成。
因为我们这里是找不符合条件的子段，即这个子段中有一个位置i上的数是这个子段的第i小。
考虑计算每一个数作为区间第i小的数而导致不符合子段条件的子段数量。（这里的导致不符合字段条件就是区间第i小的数刚好位于第i位）
这句话可能有点抽象，例如{4,2,3,5,1}，当3作为区间第2小数(既然这时要不符合条件那么它一定在区间的第2个位置)，这时候不符合条件的区间有[2,3],[2,4]。也就是区间左端点为2，右端点为[3,4]这个区间。
那么我们可以枚举每个数和它作为区间第i小数而导致不符合子段条件，然后计算每个这样的情况的贡献。
但是，显然，如2作为区间第1小数而不符合子段条件的其中一个区间[2,3]和3作为区间第2小数不符合子段条件的其中一个区间[2,3]贡献的计算重复，如何避免这个问题呢？可以发现，对于每个数作为区间第i小数时的贡献，左端点固定，右端点是一个连续的区间，那么我么可以将右端点的一个连续区间存入vector[左端点]中，最后合并vector[左端点]中的所有区间，这样就能避免重复。
那么怎么找这个左右端点？首先对于一个数x，当他作为区间第i小数而导致不符合子段条件（即这个数在区间中位于第i个位置且为区间第i小数，这两个条件同时满足），那么它的左端点就是这个数左边第i-1位（第0位就是它自己），比如那个例子，{6,4,2,3,5,1}，当3作为区间第2小数且位区间第2个位置时，显然左端点就在下标为3上，这样才满足它在以3为左端点的第2个位置；那么它的右端点怎么考虑，我们可以看一下左端点到3这个数有几个小于3的数，例如这个例子上有1个也就是下表为3的数字2，记下标4右边第i个比p[4]小的数为，则它的右端点应该为一个区间，而如果是3这个数的左边没有比他小的数（左端点为下标3）例如这个例子,{2,4,6,3,5,1}，那么它的右端点就是区间。总而言之，就是要想满足一个数x在一个区间中位于第i个位置且第i小，即要满足这个数左边比它小的数的数量加上右边比它小的数的数量等于i-1，这样才能让这个数第i小。
而左边的比它小的数的数量在每次左移左区间时累加，右区间通过上述方法得到。
参考代码(带较详细的注释)
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;
bool multi=1;
const int N=5010;
int n;
int p[N];
vector<vector<pair<int,int>>> v;
int ans;
int pos[N];
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i];
pos[p[i]]=i;
}
ans=n*(n+1)/2;
vector<vector<int>> rle(n+1);
v.clear();
v.resize(n+1);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(p[j]<p[i]){
rle[i].push_back(j);
}
}
}
for(int i=1;i<=n;i++){
int cnt=0;
for(int j=i;j>=1;j--){
int totk=i-j+1;
if(p[j]<p[i]) cnt++;
int rk=totk-cnt-1;
int m=rle[i].size();
int l,r;
if(m>=rk){
if(rk-1==-1){
l=i;
}else{
l=rle[i][rk-1];
}
}else{
continue;
}
if(m>rk){
r=rle[i][rk]-1;
}else{
r=n;
}
v[j].push_back({l,r});
}
}
int ans2=0;
for(int i=1;i<=n;i++){
sort(v[i].begin(),v[i].end());
int l=-1,r=-1;
for(int j=0;j<v[i].size();j++){
if(l==-1){
l=v[i][j].first,r=v[i][j].second;
}else if(v[i][j].first<=r){
r=max(r,v[i][j].second);
}else{
ans2+=r-l+1;
l=v[i][j].first,r=v[i][j].second;
}
}
ans2+=r-l+1;
}
cout<<ans-ans2<<'\n';
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T=1;
if(multi) cin>>T;
while(T--){
solve();
}
return 0;
}
|
Non-Puzzle: Game
题目大意
黑板上有n个数字，Alice和Bob轮流玩，Alice先手，每次玩家必须在黑板上选择两个数（i，j可以相等）写在黑板上，在黑板上写数字k的人获胜。输出获胜结果，如果永远不会获胜输出平局。
解题思路
显然，如果n个数字中存在两个数（可以相同）异或等于k，则Alice获胜。直接将每个数存入桶中，然后对于每个数x找桶中是否存在。
否则，若对于任意的i,j，都存在p，使得，因为，原式可变形为①对于任意的，都存在p，使得，如果集合A表示为{序列a中每个元素异或上k的值}，那么①就相当于A集合中的元素异或上A集合中的元素仍为A集合中的元素，也就是A集合在xor意义下的形成的向量空间严格等于A，那么判断A集合的线性基能表示出的向量空间严格等于A即可。
怎么判断呢？（因为刚学，专业名词可能用的不太准确，欢迎纠正 /可怜 ）
令m为A集合不重复的数量，n为A集合的线性基数量，n个线性基能表示的向量空间的元素个数为（1LL<<(n-1))，如果A集合的线性基形成的向量空间严格等于A集合，那么n个线性基表示出的向量空间的元素个数应该于去重后的A集合相等，也就是与m相等。
所以判断是否等于即可。
参考代码
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
| #include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;
bool multi=1;
const int N=1e6+10;
int n,k;
int a[N],b[N];
void Gauss(int a[],int &n){
int i,k=1;
long long j = (long long)1<<62;
for(;j;j>>=1){
for(i=k;i<=n;i++)
if(a[i]&j) break;
if(i > n) continue;
swap(a[i],a[k]);
for(i=1;i<=n;i++)
if(i != k && a[i]&j) a[i]^=a[k];
k++;
}
n = k;
}
void solve(){
map<int,bool> mp;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
mp[a[i]]=true;
}
for(int i=1;i<=n;i++){
if(mp[a[i]^k]){
cout<<"Alice\n";
return;
}
}
for(int i=1;i<=n;i++){
b[i]=a[i]^k;
}
sort(b+1,b+n+1);
int m=unique(b+1,b+n+1)-b-1;
Gauss(b,n);
if(1LL<<(n-1)==m){
cout<<"Bob\n";
}else{
cout<<"Draw\n";
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T=1;
if(multi) cin>>T;
while(T--){
solve();
}
return 0;
}
|
