Znzryb's Blog
0%

Posted on Edited on

思路讲解

主要就是一个stl的使用，思路就是查到了直接删而不是查到了加进一个东西里

AC代码

https://atcoder.jp/contests/abc385/tasks/abc385_d

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
106
107
108
109
110
111
112
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define SZ(x) ((int)x.size())
#define all(x,size) x.begin()+1,x.begin()+size+1
#define all1(x) x.begin(),x.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(2e5)+10,MAXval=static_cast<ll>(1e18)+3;

ll N,T;
pll xy[MAXN];
struct cmpx{
	bool operator()(pll a,pll b) const{
		if(a.first!=b.first) return a.first<b.first;
		return a.second<b.second;
	}
};
struct cmpy{
	bool operator()(pll a,pll b) const{
		if(a.second!=b.second) return a.second<b.second;
		return a.first<b.first;
	}
};
set<pll,cmpx> stx;
set<pll,cmpy> sty;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	ll sx,sy;
	cin>>N>>T>>sx>>sy;
	FOR(i, 1, N){
		cin>>xy[i].first>>xy[i].second;
		stx.insert(xy[i]);
		sty.insert(xy[i]);
	}
	FOR(i, 1, T){
		char op;ll dis;
		cin>>op>>dis;
//		cout<<"Yes "<<i<<'\n';
		if(op=='U'){
			set<pll,cmpx>::iterator it=stx.lower_bound({sx,sy});
			while(it!=stx.end() && it->first== sx && it->second<=sy+dis){
				set<pll,cmpx>::iterator next_it=next(it);
				sty.erase({it->first,it->second});
				stx.erase(it);
				it=next_it;
			}
			sy+=dis;
		}else if(op=='D'){
			set<pll,cmpx>::iterator it=stx.lower_bound({sx,sy});
			if(it==stx.begin() || stx.empty()){
				sy-=dis;
				continue;
			} 
			it--;
			while(it!=stx.end() && it->first== sx && it->second>=sy-dis){
				if(it==stx.begin()){
					sty.erase({it->first,it->second});
					stx.erase(it);
					break;
				}
				set<pll,cmpx>::iterator prev_it=prev(it);
				sty.erase({it->first,it->second});
				stx.erase(it);
				it=prev_it;
			}
			sy-=dis;
		}else if(op=='R'){
			set<pll,cmpy>::iterator it=sty.lower_bound({sx,sy});
			while(it!=sty.end() && it->first<=sx+dis && it->second==sy){
				set<pll,cmpy>::iterator next_it=next(it);
				stx.erase({it->first,it->second});
				sty.erase(it);
				it=next_it;
			}
			sx+=dis;
		}else {
			set<pll,cmpy>::iterator it=sty.lower_bound({sx,sy});
			if(it==sty.begin() || sty.empty()){
				sx-=dis;
				continue;
			} 
			it--;
			while(it!=sty.end() && it->first>=sx-dis && it->second==sy){
				if(it==sty.begin()){
					stx.erase({it->first,it->second});
					sty.erase(it);
					break;
				}
				set<pll,cmpy>::iterator prev_it=prev(it);
				stx.erase({it->first,it->second});
				sty.erase(it);
				it=prev_it;
			}
			sx-=dis;
		}
	}
	cout<<sx<<' '<<sy<<' '<<N-stx.size()<<'\n';
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc385/submissions/62232268
*/

心路历程（WA，TLE，MLE……）

https://atcoder.jp/contests/abc385/submissions/62232078

RE

总的来说就是要防御性编程，能先判断的不要后判断（像我是后判断的，这不好，有些情况会RE）

然后空什么的特殊情况一定也要判断，不要嫌麻烦。

image

Posted on Edited on

思路讲解

思路其实就是组合数生成惯用套路+深度控制

组合数生成其实就是从start开始，这样可以保证加入顺序都是从编号小的到编号大的，进而达到无视元素加入顺序的效果。

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int dep,int start,ull sum){
	if(dep>T){
		ans=max(ans,sum^xorSum);
		return;
	}
	FOR(i, start, N){
		if(vis[i]) continue;
		vis[i]=true;
		dfs(dep+1,i+1,sum^A[i]);
		vis[i]=false;
	}
}

当然，利用异或计算的性质，我们可以控制深度，枚举不选的，而不是枚举选的，以减少计算次数

1
2
3
4
5
if(T>N-T){
		T=N-T;
	}else{	// 正向进行不需要异或
		xorSum=0;
	}

AC代码

AC

https://atcoder.jp/contests/abc386/submissions/62216769

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
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define SZ(x) ((int)x.size())
#define all(x,size) x.begin()+1,x.begin()+size+1
#define all1(x) x.begin(),x.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(1e6)+10,MAXval=static_cast<ll>(1e18)+3;

ll N,T;
ull A[MAXN];
bool vis[MAXN];
ull ans,xorSum;

void dfs(int dep,int start,ull sum){
	if(dep>T){
		ans=max(ans,sum^xorSum);
		return;
	}
	FOR(i, start, N){
		if(vis[i]) continue;
		vis[i]=true;
		dfs(dep+1,i+1,sum^A[i]);
		vis[i]=false;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>T;
	FOR(i, 1, N){
		cin>>A[i];
		xorSum^=A[i];
	}
	if(T>N-T){
		T=N-T;
	}else{	// 正向进行不需要异或
		xorSum=0;
	}
	dfs(1,1,0);
	cout<<ans<<endl;
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc386/submissions/62216769
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

如果红色块被涂黑了，所有被红线围住的块全部也要涂黑，所以说中间不能有一个白色的块

image

形式化的来说，B（x，y），那么不能有白块 ≤ x && ≤ y。

AC代码

AC

https://atcoder.jp/contests/abc386/submissions/62215130

https://www.luogu.com.cn/record/200864278

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
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define SZ(x) ((int)x.size())
#define all(x,size) x.begin()+1,x.begin()+size+1
#define all1(x) x.begin(),x.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(2e5)+10,MAXval=static_cast<ll>(1e18)+3;

int N,T;
//ll coly[MAXN];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>T;
	vector<pll> wNode;
	// 我们要记录的是黑色最远出现位置和白色最近出现位置
	map<ll,ll> bHigh;
	FOR(i, 1, T){
		ll x,y;char c;
		cin>>x>>y>>c;
		if(c=='B'){
			bHigh[x]=bHigh.find(x)==bHigh.end()?y:max(y,bHigh[x]);
		}else{
			wNode.push_back({x,y});
		}
	}
	if(bHigh.empty()){	// 没有黑色块自然没那么多烦人事了
		cout<<"Yes\n";
		return 0;
	}
	ll maxHigh=0;
	for(map<ll,ll>::reverse_iterator it=bHigh.rbegin();it!=bHigh.rend();++it){
		it->second=max(it->second,maxHigh);
		maxHigh=it->second;
	}
	FOR(i, 0, SZ(wNode)-1){
		ll x=wNode[i].first,y=wNode[i].second;
		map<ll,ll>::iterator it=bHigh.lower_bound(x);
		if(it!=bHigh.end()){ // 确保lower_bound会搜到正确的东西
			ll yB=it->second;
			if(yB>=y){
				cout<<"No\n";
				return 0;
			}
		}
	}
	cout<<"Yes\n";
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc386/submissions/62215130
*/

心路历程（WA，TLE，MLE……）

如果出现样例结果评测机与本地结果不一致，大概率是空的情况处理有问题

还是要多防御性编程，不要相信lower_bound一定正确，避免其返回end（）的情况

Posted on Edited on

思路讲解

https://www.luogu.com.cn/article/5c0a5s3i

image

由上可知，只有让每行每列的和都为0才在所有情况下都有解。

所以说这种东西首先要确定在什么情况下是一定有解的，不能上来就做

AC代码

https://codeforces.com/contest/2055/submission/303531727

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=1010;
// 假设我们要凑的数独是0吧

ll N,M,T,maze[MAXN][MAXN];
ll rowMaze[MAXN],colMaze[MAXN];

void solve(){
	cin>>N>>M;
	string s;
	cin>>s;
	FOR(i, 1, N){
		rowMaze[i]=0;
		FOR(j, 1, M){
			cin>>maze[i][j];
			rowMaze[i]+=maze[i][j];
		}
	}
	// 
	FOR(i, 1, M){
		colMaze[i]=0;
		FOR(j, 1, N){
			colMaze[i]+=maze[j][i];
		}
	}
	int px=1,py=1;
	if(s.back()=='D'){
		maze[N][M]=-rowMaze[N];
		colMaze[M]+=maze[N][M];
	}else{
		maze[N][M]=-colMaze[M];
		rowMaze[N]+=maze[N][M];
	}
	FOR(i, 0, s.size()-1){
		// 这样子的处理唯一就是要担心最后一个块，因为最后一个块行和列都后继无人了
		if(s[i]=='D'){
			// 如果他往下走，那么他这行就后继无人了
			ll h=-rowMaze[px];
			rowMaze[px]=0;
			colMaze[py]+=h;
			maze[px][py]=h;
		}else{
			// 如果他往右走，那么他这列就后继无人了
			ll h=-colMaze[py];
			colMaze[py]=0;
			rowMaze[px]+=h;
			maze[px][py]=h;
		}
		if(s[i]=='D'){
			px+=1;
		}else{
			py+=1;
		}
	}
	
	FOR(i, 1, N){
		FOR(j, 1, M){
			cout<<maze[i][j]<<' ';
		}
		cout<<'\n';
	}
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		solve();
	}
	return 0;
}
/*
1
2 3
RRD
0 0 0
0 1 0

4
3 3
DRRD
0 2 3
0 0 0
3 1 0
4 5
DRRRRDD
0 1 0 2 3
0 0 0 0 0
-1 0 -3 -3 0
0 0 0 -1 0
2 3
RRD
0 0 0
0 1 0
5 5
DDDDRRRR
0 25 2 9 11
0 6 13 20 22
0 17 24 1 8
0 3 10 12 19
0 0 0 0 0

*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

我的总体思路就是把问题拆成3个背包，而且因为不同食物不会含有多种vitamin，所以背包之间不会有干扰。

然后枚举前两个背包的大小（第三个背包就是总背包-1-2），得出最优组合，输出答案即可

AC代码

AC

https://atcoder.jp/contests/abc390/submissions/62196209

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
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=5010,MAXval=static_cast<ll> (1e18)+3;

ll N,T,C;
struct Food{
	ll unit,ene;
};
vector<Food> food[5];
// 该容量（卡路里）下，该卡路里摄入量最多是多少？
ll dp[5][MAXN];
ll Len[5];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>C;
	FOR(i, 1, N){
		ll kind,unit,ene;
		cin>>kind>>unit>>ene;
		food[kind].push_back((Food){unit,ene});
	}
	Len[1]=food[1].size();Len[2]=food[2].size();Len[3]=food[3].size();
	// 计算三种元素的背包问题答案
	FOR(i, 1, 3){
		FOR(j, 0, Len[i]-1){	// 枚举物品种类
			ROF(k, C, food[i][j].ene){	// 枚举背包容量
				dp[i][k]=max(dp[i][k],dp[i][k-food[i][j].ene]+food[i][j].unit);
			}
		}
	}
	ll ans=0;
	FOR(i, 0, C){
		FOR(j, 0, C-i){
			ans=max(min({dp[1][i],dp[2][j],dp[3][C-i-j]}),ans);
		}
	}
	cout<<ans<<'\n';
	return 0;
}

心路历程（WA，TLE，MLE……）