Znzryb's Blog
0%

Posted on Edited on

题目大意

给定一个数组，通过若干次“除以 2 取整”的操作把元素压到一定范围内，要求最终能覆盖 0 到 x-1 的所有数（每个数至少出现一次），求最大的可行 x。通常用二分答案 + 贪心检查。

AC 代码 二分答案 相比于那个过了93.33%的还是修改了很多。

总体的check函数的贪心思路是 ≥x 的没用，之前就到过的（vis中有的）也没用。

没用，那怎么让他有用那？那当然是>>1才有用，不断的>>1，直到有用（注意条件，不要死循环了）。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71786526

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
#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <set>
using namespace std;
const int maxn=1e5+7,maxA=static_cast<int>(1e6)+7;
int n,t,a[maxA],A;
set<int> vis;
inline bool check(int x) {
    for(int i=n;i>=1;i--) {
        int ai=a[i];
        while(ai>=x)
            ai>>=1;
        while(vis.count(ai)!=0 && ai!=0)  // 到过以前到过的值不算有用 ai！=0防止死循环的发生
            ai>>=1;
        vis.insert(ai);
    }
    for(int i=0;i<=x-1;i++) {
        if(vis.count(i)==0)
            return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    for(int _=1;_<=t;_++) {
        cin>>n;
        for(int i=1;i<=n;i++) {
            cin>>a[i];
        }
        sort(&a[1],&a[n+1],less<int>());
        int l=0,r=n+1;  // 如果n个数连续，那么就是n
        while(l<r) {
            vis.clear();
            int mid=l+r+1>>1;
            if(check(mid)) l=mid;
            else r=mid-1;
        }
        cout<<l<<endl;
    }
    return 0;
}
// TLE https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785349
// 53.33% WA https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785676
// 93.33% WA https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785979
// AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71786526

TLE pass 2/30

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 <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=1e5+7,maxA=static_cast<int>(1e6)+7;
int n,t,a[maxA],A;
bitset<maxA> ovis,vis;
inline bool check(int x) {
    for(int i=n;i>=1;i--) {
        int ai=a[i];
        if(ai<x)
            break;
        while(ai>>=1) {
            if(!vis[ai] && ai<x) {vis[ai]=true;break;}
        }
    }
    for(int i=1;i<=x-1;i++) {
        if(!vis[i])
            return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    for(int _=1;_<=t;_++) {
        cin>>n;
        vis.reset();ovis.reset();   // 初始化
        for(int i=1;i<=n;i++) {
            cin>>a[i];A=max(A,a[i]);ovis[a[i]]=true;
        }
        sort(&a[1],&a[n+1],less<int>());
        int l=0,r=A;
        while(l<r) {
            for(int i=1;i<=A;i++)
                vis[i]=ovis[i];
            int mid=l+r+1>>1;
            if(check(mid)) l=mid;
            else r=mid-1;
        }
        cout<<l<<endl;
    }
    return 0;
}
// TLE https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785349

int l=0,r=n+1; // 如果n个数连续，那么就是n

for(int i=1;i<=n+1;i++)
vis[i]=ovis[i];

把上界换成n+1过了53.33% https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785676

但出现了WA

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 <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=1e5+7,maxA=static_cast<int>(1e6)+7;
int n,t,a[maxA],A;
bitset<maxA> ovis,vis;
inline bool check(int x) {
    for(int i=n;i>=1;i--) {
        int ai=a[i];
        if(ai<x)
            break;
        while(ai>>=1) {
            if(!vis[ai] && ai<x) {vis[ai]=true;break;}
        }
    }
    for(int i=1;i<=x-1;i++) {
        if(!vis[i])
            return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    for(int _=1;_<=t;_++) {
        cin>>n;
        vis.reset();ovis.reset();   // 初始化
        for(int i=1;i<=n;i++) {
            cin>>a[i];ovis[a[i]]=true;
        }
        sort(&a[1],&a[n+1],less<int>());
        int l=0,r=n+1;  // 如果n个数连续，那么就是n
        while(l<r) {
            for(int i=1;i<=n+1;i++)
                vis[i]=ovis[i];
            int mid=l+r+1>>1;
            if(check(mid)) l=mid;
            else r=mid-1;
        }
        cout<<l<<endl;
    }
    return 0;
}
// TLE https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785349

WA pass93.33% https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785979

应该是快了

增加了

1
2
3
4
for(int i=2;i<=n;i++) {
        if(a[i]>=x) break;
        if(a[i]==a[i-1]) vis[0]=true;break;
    }
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
#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=1e5+7,maxA=static_cast<int>(1e6)+7;
int n,t,a[maxA],A;
bitset<maxA> ovis,vis;
inline bool check(int x) {
    for(int i=2;i<=n;i++) {
        if(a[i]>=x) break;
        if(a[i]==a[i-1]) vis[0]=true;break;
    }
    for(int i=n;i>=1;i--) {
        int ai=a[i];
        if(ai<x)
            break;
        while(true) {
            ai>>=1;
            if(!vis[ai] && ai<x) {vis[ai]=true;break;}
            if(ai==0)
                break;
        }
    }
    for(int i=0;i<=x-1;i++) {
        if(!vis[i])
            return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    for(int _=1;_<=t;_++) {
        cin>>n;
        vis.reset();ovis.reset();   // 初始化
        for(int i=1;i<=n;i++) {
            cin>>a[i];ovis[a[i]]=true;
        }
        sort(&a[1],&a[n+1],less<int>());
        int l=0,r=n+1;  // 如果n个数连续，那么就是n
        while(l<r) {
            for(int i=0;i<=n+1;i++)
                vis[i]=ovis[i];
            int mid=l+r+1>>1;
            if(check(mid)) l=mid;
            else r=mid-1;
        }
        cout<<l<<endl;
    }
    return 0;
}
// TLE https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785349
// 53.33% WA https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71785676

Posted on Edited on

题目大意

给定一段字符串（或若干字符串），需要按题意进行判断/构造，输出对应结果。（该页目前为空，我先补上题意标题，具体题意可后续再补充链接或样例。）

Posted on Edited on

题目大意

给定若干根木棍长度，要求从中选出 3 根组成一个三角形，并使三角形周长最大；若无法组成任何三角形则输出 -1。

25pts，暴力dfs，TLE

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
#include <iostream>
#include <vector>
using namespace std;
const int maxn=1e4+10;
long long int T,n,aa[maxn],ans;
bool vis[maxn];

long long int summ(vector<int> tri,int c) {
    int a=tri[0],b=tri[1];
    if(a+b<=c) {
        return -1;
    }else if(a+c<=b) {
        return -1;
    }else if(b+c<=a) {
        return -1;
    }
    return a+b+c;
}

void dfs(int y,vector<int>triangle) {
    for(int i=0;i<n;i++) {
        if(!vis[i]) {
            if(y+1==3) {
                //cout<<triangle[0]<<" "<<triangle[1]<<" "<<aa[i]<<endl;
                ans=max(ans,summ(triangle,aa[i]));
                continue;
            }
            triangle.push_back(aa[i]);vis[i]=true;
            dfs(y+1,triangle);
            triangle.pop_back();vis[i]=false;
        }
    }
}

int main()
{
    cin>>T;
    while (T--) {
        fill(begin(aa),end(aa),0);
        fill(begin(vis),end(vis),false);
        ans=-1;
        cin>>n;
        for(int i=0;i<n;i++) {
            cin>>aa[i];
        }
        dfs(0,{});
        cout<<ans<<endl;
    }
    return 0;
}

参考的题解思路

https://ac.nowcoder.com/acm/discuss/blogs?tagId=271232

AC代码

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e4+7;
const ll maxLen=static_cast<ll>(1e18)+7;
ll len[maxn],n,t,ans;
int main() {
    cin>>t;
    for(int _=1;_<=t;_++) {
        cin>>n;
        for(int i=1;i<=n;i++) {
            cin>>len[i];
        }
        ans=0;
        sort(&len[1],&len[n+1],less<int>());
        for(int i=n;i>=3;i--) {
            for(int j=i-1;j>=2;j--) {
                if(len[j-1]+len[j]<=len[i])  // 别写反了，这是不满足条件的情况
                    break;
                ans=max(ans,len[j-1]+len[j]+len[i]);  // 如果这个不能，那继续往下枚举也没有意义，因为次大+次次大<大边
                break;
            }
        }
        if(ans==0) {
            cout<<-1<<endl;
        }else {
            cout<<ans<<endl;
        }
    }
}
//AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71774749

Posted on Edited on

题目大意

给定一个整数 a，需要构造两个正整数 x、y，使得 x XOR y = a，并满足题目额外的范围/特殊要求（需要对某些边界值特判）。输出一组可行的 x 与 y。

pass 7 / 10 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71053412

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int t,a,b;const int amax=1e9+10;
int main()
{
    cin>>t;
    while(t--) {
        cin>>a;
        for(int i=1;i<=amax;i++) {
            b=i^a;
            if(b>0) {
                cout<<i<<" "<<b<<endl;
                break;
            }
        }
    }
    // a=1^0;
    // std::cout << a << std::endl;
    return 0;
}
// WA https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71053412

前面一直WA，看到这个题解终于懂了。

https://ac.nowcoder.com/acm/discuss/blogs?tagId=271232

其实主要就是要特判1和1e9，这两个通过我们的算法得出的另一个数会超范围，故需要特判。

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
// https://ac.nowcoder.com/acm/contest/88392
#include <iostream>
#include <bitset>
#include <cmath>
#include <deque>
using namespace std;
int a,b,c,t;
bitset <64> numa,num3;
deque <int> a2;
typedef long long ll;
inline ll convNum3(int leng){       // 将num3转为10进制
    ll res=0;
    for(int i=0;i<leng;i++) {
        if(num3[i])
            res+=pow(2,leng-1-i);
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    for(int _=1;_<=t;_++){
        cin>>a;
        ll oa=a;
        numa.reset();num3.reset();
        while(true){
            if(a==0) break;
            a2.push_back(a%2);
            a/=2;
        }
        int leng=a2.size();         // 这种循环上限还是用一个量（前面发现调不对发现是因为<a2.size(),但a2的大小一直在变）
        for(int i=0;i<leng;i++){
            numa[i]=a2.back();
            a2.pop_back();
        }
        for(int i=0;i<leng;i++) {
            num3[i]=numa[i];
            if(i==leng-1) {
                if(num3[i]) num3[i]=false;
                else num3[i]=true;
            }
        }
        ll ans3=convNum3(leng);
        if(oa==1000000000) {
            cout<<999999999<<" "<<1023<<endl;
            continue;
        }
        if(oa==1) {
            cout<<"2 3"<<endl;
            continue;
        }
        cout<<1<<" "<<ans3<<endl;
        //cout<<"xor res: 1^"<<ans3<<"="<<(ans3^1)<<endl;
    }
}
// AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71768673

Posted on Edited on

题目大意

给定一个 n 元异或线性方程组（系数与常数均为 0/1），求其解：

  • 无解输出 “No solution”

  • 多解输出 “Multiple sets of solutions”

  • 唯一解输出每个变量的取值

时隔接近一年，重写一下这个代码。

https://cp-algorithms.com/linear_algebra/linear-system-gauss.html

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// Problem: 高斯消元解异或线性方程组
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/886/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define pb push_back
#define SZ(a) ((int) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";

using namespace std;

using  ll = long long;
constexpr ll INF=static_cast<ll>(1e17)+9;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
const double pi=acos(-1.0);
/*

*/
// 返回的是解的数量
// https://www.acwing.com/problem/content/submission/code_detail/42023476/
int gauss(vector< bitset<110> > a,ll n,ll m,bitset<110> &ans){
	vector<ll> where(m,-1);
	for(int col=0,row=0; col<m && row<m;++col){
		for(int i=row;i<n;++i){
			if(a[i][col]){	// 如果a[i][col]没有消掉，即是主元列
				swap(a[i],a[row]);
				break;
			}
		}
		if(!a[row][col]){	// 上面没找到主元列
			continue;
		}
		where[col]=row;		// 那么这一主元列对应的行
		for(int i=0;i<n;++i){
			if(i!=row && a[i][col]){
				a[i]^=a[row];
			}
		}
		++row;
	}
	for(int i=0;i<m;++i){
		if(where[i]!=-1){
			ans[i]=a[where[i]][m];
		}
	}
	// 把解带入方程
	for(int i=0;i<n;++i){
		ll sum=0;
		for(int j=0;j<m;++j){
			sum^=ans[j]*(int)a[i][j];
		}
		if(sum!=a[i][m]){	// 不符合，0个解
			return 0;
		}
	}
	for(int i=0;i<m;++i){
		if(where[i]==-1) return 2;	// 	就是指有无穷多解。
	}
	return 1;
}
inline void solve(){
	ll n;
	cin>>n;
	vector< bitset<110> > A(n+5);
	for(int i=0;i<n;++i){
		for(int j=0;j<n+1;++j){
			int a;
			cin>>a;
			A[i][j]=(bool)a;
		}
	}
	bitset<110> ans;
	int ret=gauss(A,n,n,ans);
	if(ret==2){
		cout<<"Multiple sets of solutions\n";
	}else if(ret==0){
		cout<<"No solution\n";
	}else{
		for(int i=0;i<n;++i){
			cout<<(int)ans[i]<<"\n";
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// ll lT;
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/

int opr=0; // 这个一定要写在循环内，因为每次都要重置（因为这个WA了一次）

利用了一个数异或自己变为0的特性

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
// https://www.acwing.com/problem/content/886/
#include <iostream>
using namespace std;
const int maxn=105; 
int n,m[maxn][maxn]; 
//void out(){
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n+1;j++){
//			cout<<m[i][j]<<" ";
//		}
//		cout<<endl;
//	}
//}
void gauss(){
	int r=1;
	for(int c=1;c<=n;c++){
		int opr=0;      // 这个一定要写在循环内，因为每次都要重置
		for(int i=r;i<=n;i++){
			if(m[i][c]==1){
				opr=i;break;
			}
		}
		if(opr==0) continue;
		if(opr!=r){
			for(int i=1;i<=n+1;i++){
				swap(m[opr][i],m[r][i]);
			}
		}
		for(int i=1;i<=n;i++){
			if(m[i][c]==0 || i==r) continue;
			for(int j=c;j<=n+1;j++){
				m[i][j]^=m[r][j];
			}
		}
		r++;
	}
	if(r<n+1){	// show the matrix isn't the optimal triangle; the solution is infinite or nothing 
		for(int i=r;i<=n;i++){
			if(m[i][n+1]!=0){
				cout<<"No solution"<<endl;return;
			}
		}
		cout<<"Multiple sets of solutions"<<endl;return;
	}
	for(int i=1;i<=n;i++){
		cout<<m[i][n+1]<<endl;
	}
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0); 
	cin>>n; 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n+1;j++){
			cin>>m[i][j];
		}
	} 
	gauss();
	return 0;
} 
// pass 6/12 https://www.acwing.com/problem/content/submission/code_detail/37301558/
// AC https://www.acwing.com/problem/content/submission/code_detail/37301651/