Znzryb's Blog
0%

Posted on Edited on

思路讲解

这题代码挺简单的，这个代码看起来长，实际上全部是快读模版和一些宏定义

然后我们来讲一讲，实际上就是字典树建树过程。

然后其实就是字典树每次扩充新节点++ans；最后ans就是字典树的节点数量（严格来说是不包含idx=0的节点的数量），当然此时不是答案，根据观察，所有的节点都需要被回退，只有最长的字符串不需要回退，所以答案就是

1
cout<<ans*2-maxLen<<'\n';

除了最长字符串上的节点，全部都要打一遍，然后再删除掉，故ans*2，然后最长的字符串不需要回退，-maxLen

AC代码

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

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

inline string reads()
{
	string str="";
	char ch=getchar();
	//处理空格或回车 
	while(ch==' ' || ch=='\n' || ch=='\r')
		{
			ch=getchar(); 
		}
	//读入
	while(ch!=' ' && ch!='\n' && ch!='\r')
		{
			str+=ch;
			ch=getchar();
		} 
	return str;
}
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{
			if(ch=='-')
				f=-1;
			ch=getchar();
		}
	while(ch>='0' && ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int N,T;
int idx;
int nex[MAXN*10][28]; //wei[MAXN*10];
ll ans;
int L,R;

inline void buildTree(string &s){
	int node=0;
	int len=SZ(s);
	FOR(i, 0, len-1){
		if(nex[node][s[i]-'a']==0){
			nex[node][s[i]-'a']=++idx;
			node=idx;
			// wei[idx]+=len-i;
			++ans;
		}else{
			node=nex[node][s[i]-'a'];
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	N=read(),T=read();
	int maxLen=0;
	FOR(i, 1, N){
		string s;
		s=reads();
		maxLen=max(maxLen,SZ(s));
		buildTree(s);
	}
	L=read();R=read();
	cout<<ans*2-maxLen<<'\n';
	return 0;
}
/*

*/

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

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

段错误

字典树一般要开10倍空间。

Posted on Edited on

思路讲解

image

交换速度你可以理解为这两个球想幽灵一样，直接穿过，没有碰撞（因为我们不在乎是哪个球撞的，我们只在乎碰撞次数）

套了一个树状数组查逆序对的板子

不要用unordered_map以及set用于离散化，常数有一点大。

可以用unique，sort，以及lower_bound实现离散化，常数比较小，写也不是很难写

还有要求误差小于eps可以这么写，不用直接写<eps，快一点（卡常卡常）

1
2
3
4
5
6
7
8
while (r-l>(eps*l)) {
		DB mid=(l+r)/2.0;
		if(check(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}

双指针就是可以从暴力优化，原本是双层循环，但其实第二次循环有必要从1开始吗？显然不是对吧。

然后注意notMeet可能还是需要lower_bound()一下

1
2
3
4
5
6
7
8
9
10
11
12
13
FOR(i, 1, idx){
		FOR(j,flag,idx_+1){
			if(j>=idx_+1) {flag=j;break;}
			if(pv_[j]<pv[i]) {continue;}	// 必然不会碰到
			DB curt=fabs(pv_[j]-pv[i])/2.0;
			if(curt>t){
				flag=j;
				break;
			}
		}
		int notMeet=lower_bound(&pv_[1], &pv_[idx_+1], pv[i])-&pv_[0];
		res+=flag-notMeet;
	}

AC代码

双指针肯定比树状数组稍微快一点

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

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double DB;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10;
const DB eps=1e-7;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{
			if(ch=='-')
				f=-1;
			ch=getchar();
		}
	while(ch>='0' && ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x*f;
}

ll N,K,tr[MAXN];
DB curP[MAXN];
int idx,idx_;

int pv[MAXN],pv_[MAXN];	// 正速度，负速度
inline bool check(DB t){	// 枚举时间
	ll res=0;
	//   break的那个不要，所以notMeet初始为1
	int flag=1;     // flag=1 上次在哪里停的？
	FOR(i, 1, idx){
		FOR(j,flag,idx_+1){
			if(j>=idx_+1) {flag=j;break;}
			if(pv_[j]<pv[i]) {continue;}	// 必然不会碰到
			DB curt=fabs(pv_[j]-pv[i])/2.0;
			if(curt>t){
				flag=j;
				break;
			}
		}
		int notMeet=lower_bound(&pv_[1], &pv_[idx_+1], pv[i])-&pv_[0];
		res+=flag-notMeet;
	}
	
	if(res>=K){
		return true;
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	N=read(),K=read();
	FOR(i, 1, N){
		int p=read(),v=read();
		if(v<0){
			pv_[++idx_]=p;
		}else{
			pv[++idx]=p;
		}
	}
	sort(&pv[1], &pv[idx+1]);
	sort(&pv_[1], &pv_[idx_+1]);
	DB l=0,r=1e9;
	while (r-l>(eps*l)) {
		DB mid=(l+r)/2.0;
		if(check(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	if(fabs(l-1e9)<(eps*l)){
		cout<<"No\n";
		return 0;
	}
	cout<<"Yes\n";
	cout<<setprecision(7)<<fixed<<l<<endl;
	return 0;
}
/*

4 4
1 1
2 -1
3 -1
0 1

1.5

4 1
4 1
3 -1
2 -1
1 -1

No

8 8
67 1
88 1
75 -1
43 1
23 -1
45 1
49 1
87 -1


*/

各种卡常技巧一起上，终于是过了用树状数组。

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

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double DB;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10;
const DB eps=1e-7;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{
			if(ch=='-')
				f=-1;
			ch=getchar();
		}
	while(ch>='0' && ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x*f;
}

ll N,K,tr[MAXN];
DB curP[MAXN];

struct posv{
	int p,v;
//	bool operator<(const posv &other) const{
//		return p<other.p;
//	}
};
posv pv[MAXN];
inline bool cmp(posv a, posv b){
	return a.p<b.p;
}

inline ll lowbit(ll x){
	return x&(-x);
}
inline void add(ll x) {
	while (x<=N) {
		tr[x]+=1;
		x+=lowbit(x);
	}
}
inline ll query(ll x){
	ll res=0;
	while (x>0) {
		res+=tr[x];
		x-=lowbit(x);
	}
	return res;
}
inline bool check(DB t){	// 枚举时间
	vector<DB> li(N);
//	unordered_map<DB,ll> rank;
	FOR(i, 1, N){
		curP[i]=pv[i].p*1.0+t*pv[i].v;
		li[i-1]=curP[i];
	}
	sort(li.begin(), li.end());
	vector<DB>::iterator it=unique(li.begin(), li.end());
	li.resize(it-li.begin()); // 相当于R-L+1，传进去的仍然是个数
	FOR(i, 1, N){	// 初始化rank与树状数组
		tr[i]=0;
//		rank[li[i-1]]=i;
	}
	ll res=0;
	// 就是求逆序对
	FOR(i, 1, N){
		ll rk=lower_bound(li.begin(), li.end(),curP[i])-li.begin()+1;
		res+=max(i-1-query(rk-1),0ll);
		add(rk);
	}
	if(res>=K){
		return true;
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
//	cin>>N>>K;
	N=read(),K=read();
	FOR(i, 1, N){
		pv[i].p=read();
		pv[i].v=read();
//		cin>>pv[i].p>>pv[i].v;
	}
	sort(&pv[1], &pv[N+1],cmp);
	DB l=0,r=1e9;
	while (r-l>(eps*l)) {
		DB mid=(l+r)/2.0;
		if(check(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	if(fabs(l-1e9)<(eps*l)){
		cout<<"No\n";
		return 0;
	}
	cout<<"Yes\n";
	cout<<setprecision(7)<<fixed<<l<<endl;
	return 0;
}
/*
4 4
1 1
2 -1
3 -1
0 1

3 2
0 1
2 -1
9 -1

*/

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

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

双指针有问题是因为这个

1
2
3
4
5
6
7
8
9
10
11
12
FOR(i, 1, idx){
		FOR(j,flag,idx_+1){
			if(j>=idx_+1) {flag=j;break;}
			if(pv_[j]<pv[i]) {++notMeet;continue;}	// 必然不会碰到
			DB curt=fabs(pv_[j]-pv[i])/2.0;
			if(curt>t){
				flag=j;
				break;
			}
		}
		res+=flag-notMeet;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
hack数据
8 8
67 1
88 1
75 -1
43 1
23 -1
45 1
49 1
87 -1

应该输出
22
输出
18（约）

这个程序看起来没问题，但其实有点问题，就是88理应得到0，但这个程序会给出错误判断，说明notMeet的逻辑有问题，应该使用二分查找更为保险

树状数组超时，MLE

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double DB;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10;
const DB eps=1e-6;

ll N,K,tr[MAXN];
DB curP[MAXN];

struct posv{
	ll p,v;
	bool operator<(const posv &other) const{
		return p<other.p;
	}
};
vector<posv> pv(MAXN);

inline ll lowbit(ll x){
	return x&(-x);
}
inline void add(ll x) {
	while (x<=N) {
		tr[x]+=1;
		x+=lowbit(x);
	}
}
inline ll query(ll x){
	ll res=0;
	while (x>0) {
		res+=tr[x];
		x-=lowbit(x);
	}
	return res;
}
inline bool check(DB t){	// 枚举时间
	vector<DB> li(N);
	unordered_map<DB,ll> rank;
	FOR(i, 1, N){
		curP[i]=pv[i].p*1.0+t*pv[i].v;
		li[i-1]=curP[i];
	}
	sort(li.begin(), li.end());
	vector<DB>::iterator it=unique(li.begin(), li.end());
	li.resize(it-li.begin());
	FOR(i, 1, N){	// 初始化rank与树状数组
		tr[i]=0;
		rank[li[i-1]]=i;
	}
	ll res=0;
	// 就是求逆序对
	FOR(i, 1, N){
		res+=max(i-1-query(rank[curP[i]]-1),0ll);
		add(rank[curP[i]]);
	}
	if(res>=K){
		return true;
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>K;
	FOR(i, 1, N){
		cin>>pv[i].p>>pv[i].v;
	}
	sort(pv.begin()+1, pv.begin()+N+1);
	DB l=0,r=1e9;
	while (r-l>eps) {
		DB mid=(l+r)/2.0;
		if(check(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	if(fabs(l-1e9)<eps){
		cout<<"No\n";
		return 0;
	}
	cout<<"Yes\n";
	cout<<setprecision(7)<<fixed<<l<<endl;
	return 0;
}
/*
4 4
1 1
2 -1
3 -1
0 1

3 2
0 1
2 -1
9 -1

*/

Posted on Edited on

思路讲解

想这样枚举是会超时的，我们发现其实元素加入顺序其实不重要，重要的是这个元素加入到了哪个组中

1
2
3
4
5
6
7
8
9
10
for (int i=1; i<=N; ++i) {
    if(vis[i]) continue;
    for(int j=1;j<=groups+1;++j){
        sumG[j]+=A[i];
        vis[i]=true;
        dfs(cur+1,max(groups,j));
        sumG[j]-=A[i];
        vis[i]=false;
    }
}

所以说只需要减少枚举维度就行了（不再枚举元素）

1
2
3
4
5
6
7
    for(int j=1;j<=groups+1;++j){
        sumG[j]+=A[dep];
//      vis[dep]=true;
        dfs(dep+1,max(groups,j));
        sumG[j]-=A[dep];
//      vis[dep]=false;
    }

AC代码

AC

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

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
#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>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=17;
ull N,T;
ull A[MAXN];
string s;
unordered_set<ull> st;
//bool vis[MAXN];
ull sumG[MAXN];
// dep就是指当前要计算的用掉的总数量，groups是指现在的组数
void dfs(int dep,int groups) {
    if(dep>N){
        ull res=0;
        for (int i=1; i<=groups; ++i) {
            res^=sumG[i];
        }
        st.insert(res);
        return;
    }
    for(int j=1;j<=groups+1;++j){
        sumG[j]+=A[dep];
//      vis[dep]=true;
        dfs(dep+1,max(groups,j));
        sumG[j]-=A[dep];
//      vis[dep]=false;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>N;
    for(int i=1;i<=N;++i) {
        cin>>A[i];
    }
    dfs(1,0);
    cout<<st.size()<<endl;
    
//  cout<<endl;
//  for(auto it:st) {
//      cout<<it<<endl;
//  }
    return 0;
}
/*
AC https://atcoder.jp/contests/abc390/submissions/62115363

*/

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

TLE

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

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
#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>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=17;
ull N,T;
ull A[MAXN];
string s;
unordered_set<ull> st;
bool vis[MAXN];
ull sumG[MAXN];
// cur就是指当前要计算的用掉的总数量，groups是指现在的组数
void dfs(int cur,int groups) {
    if(cur>N){
        ull res=0;
        for (int i=1; i<=groups; ++i) {
            res^=sumG[i];
        }
        st.insert(res);
        return;
    }
    for (int i=1; i<=N; ++i) {
        if(vis[i]) continue;
        for(int j=1;j<=groups+1;++j){
            sumG[j]+=A[i];
            vis[i]=true;
            dfs(cur+1,max(groups,j));
            sumG[j]-=A[i];
            vis[i]=false;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>N;
    for(int i=1;i<=N;++i) {
        cin>>A[i];
    }
    dfs(1,0);
    cout<<st.size()<<endl;
    
//  cout<<endl;
//  for(auto it:st) {
//      cout<<it<<endl;
//  }
    return 0;
}
/*

*/

Posted on Edited on

思路讲解

这句话可以好好琢磨一下

image

具体来说就是这样

我先根据题解的这句话写一写

AC代码

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

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10,mod=static_cast<ll>(1e9)+7;
ll N,T;
char maze[5][MAXN];
set<char> col[5];
ll factorial[15];
inline ll C(ll k,ll n) {
	// factorial[n]/factorial[n-k] 是排列数，组合数不要排列，所以再除factorial[k]
	ll res=factorial[n]%mod/((factorial[k]%mod)*(factorial[n-k]%mod));
	return res%mod;
}
void solve(){
	cin>>N;
	for(int i=0;i<5;++i) {
		col[i].clear();
	}
	vector<ll> vis(11,-1);
	vector<ll> cnt(4,0);
	set<ll> remele;
	for(int i=1;i<=9;++i) {
		remele.insert(i);
	}
	for(int i=1;i<=3;++i) {
		for(int j=1;j<=N;++j) {
			cin>>maze[i][j];
			col[j%3].insert(maze[i][j]);
		}
	}
	for(int i=1;i<=N;++i) {	// 排除一列中有多个重复元素的情况
		if(maze[1][i]==maze[2][i] && maze[1][i]!='?') {cout<<0<<'\n';return;}
		if(maze[1][i]==maze[3][i] && maze[1][i]!='?') {cout<<0<<'\n';return;}
		if(maze[2][i]==maze[3][i] && maze[2][i]!='?') {cout<<0<<'\n';return;}
	}
	for(int i=0;i<3;++i) {
		if(col[i].size()>=5) {cout<<"0\n";return;}
		if(col[i].size()==4 && col[i].find('?')==col[i].end()) {cout<<"0\n";return;}	// 没找到问号且包含四个元素也是无解的
		for(auto j:col[i]) {
			if(j=='?') continue;
			if(vis[j-'0']!=-1) { // 该元素已经被其他列占有
				cout<<0<<'\n';
				return;
			}
			vis[j-'0']=i;	// 该元素被该列占有
			cnt[i]+=1;	// 该列所拥有元素+1
			remele.erase(j-'0');
		}
	}
	// 列元素分配方案*问号分配方案=答案
	ll qm=1;
	// 计算问号分配方案
	for(int j=1;j<=N;++j) {
		ll qmcnt=0;	// 统计问号数量(question mark)
		for(int i=1;i<=3;++i) {
			if(maze[i][j]=='?') qmcnt+=1;
		}
		if(qmcnt==0) continue;
		if(qmcnt==2||qmcnt==1) qm=(qmcnt*qm)%mod;
		else qm=(6*qm)%mod;
	}
	qm=qm%mod;
	// 计算元素分配方案
	ll ele=1;
	ll rem=remele.size();
	for(int i=0;i<3;++i) {
		if(cnt[i]==3) continue;
		ele*=C(3-cnt[i],rem);
		rem-=3-cnt[i];
	}
	cout<<((ele%mod)*(qm%mod))%mod<<'\n';
	// cout<<"debug\n";
	// cout<<ele<<' '<<qm<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	factorial[0]=1;
	for(int i=1;i<=14;++i) {
		factorial[i]=(factorial[i-1]*i)%mod;
	}
	while (T--) {
		solve();
	}
	return 0;
}
/*

1
3
723
18?
?9?

1
3
13?
1??
2??

*/

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

1
2
3
4
5
6
1
3
13?
1??
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
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10,mod=static_cast<ll>(1e9)+7;
ll N,T;
char maze[5][MAXN];
set<char> col[5];
ll factorial[15];
inline ll C(ll k,ll n) {
	// factorial[n]/factorial[n-k] 是排列数，组合数不要排列，所以再除factorial[k]
	ll res=factorial[n]%mod/((factorial[k]%mod)*(factorial[n-k]%mod));
	return res%mod;
}
void solve(){
	cin>>N;
	for(int i=0;i<5;++i) {
		col[i].clear();
	}
	vector<ll> vis(11,-1);
	vector<ll> cnt(4,0);
	set<ll> remele;
	for(int i=1;i<=9;++i) {
		remele.insert(i);
	}
	for(int i=1;i<=3;++i) {
		for(int j=1;j<=N;++j) {
			cin>>maze[i][j];
			col[j%3].insert(maze[i][j]);
		}
	}
	for(int i=0;i<3;++i) {
		if(col[i].size()>=5) {cout<<"0\n";return;}
		if(col[i].size()==4 && col[i].find('?')==col[i].end()) {cout<<"0\n";return;}	// 没找到问号且包含四个元素也是无解的
		for(auto j:col[i]) {
			if(j=='?') continue;
			if(vis[j-'0']!=-1) { // 该元素已经被其他列占有
				cout<<0<<'\n';
				return;
			}
			vis[j-'0']=i;	// 该元素被该列占有
			cnt[i]+=1;	// 该列所拥有元素+1
			remele.erase(j-'0');
		}
	}
	// 列元素分配方案*问号分配方案=答案
	ll qm=1;
	// 计算问号分配方案
	for(int j=1;j<=N;++j) {
		ll qmcnt=0;	// 统计问号数量(question mark)
		for(int i=1;i<=3;++i) {
			if(maze[i][j]=='?') qmcnt+=1;
		}
		if(qmcnt==0) continue;
		if(qmcnt==2||qmcnt==1) qm=(qmcnt*qm)%mod;
		else qm=(6*qm)%mod;
	}
	qm=qm%mod;
	// 计算元素分配方案
	ll ele=1;
	ll rem=remele.size();
	for(int i=0;i<3;++i) {
		if(cnt[i]==3) continue;
		ele*=C(3-cnt[i],rem);
		rem-=3-cnt[i];
	}
	cout<<((ele%mod)*(qm%mod))%mod<<'\n';
	// cout<<"debug\n";
	// cout<<ele<<' '<<qm<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	factorial[0]=1;
	for(int i=1;i<=14;++i) {
		factorial[i]=(factorial[i-1]*i)%mod;
	}
	while (T--) {
		solve();
	}
	return 0;
}
/*

1
3
723
18?
?9?

1
3
13?
1??
2??

*/

Posted on Edited on

思路讲解

P2880 [USACO07JAN] Balanced Lineup G

树状数组做RMQ问题

我的思路是肯定要预处理这个东西，然后重量加减应该没那么复杂，就是加在第一块上就行
然后我们其实就是要求需要加了多少嘛
我们可以把这个问题转化为RMQ，即该区间内最大的A[i]-sumA[i-1];

query的时候这样输出就行

1
cout<<max(query(l+1,r)+sumA[l-1],0LL)<<'\n';

AC代码

AC

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

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10,MINval=static_cast<ll>(-1e18)-10;
ll N,Q,A[MAXN],sumA[MAXN],tr[MAXN];
inline ll lowbit(ll x) {
	return x&(-x);
}
// 将p位置改为x (我懒得建树，这题当然不需要在线修改)
inline void change(ll p, ll x) {
	while (p<=N) {
		tr[p]=x;  // 这个之所以可以直接赋值是因为我们这道题的change函数调用是从小区间到大区间
		// 可以模拟一下8，8-1=7  8-2=6 8-4=4 相当于把8下面的全部区间都遍历了一遍（lowbit（8）=8）
		for(int i=1;i<lowbit(p);i<<=1) {
			tr[p]=max({tr[p-i],tr[p],x});
		}
		p+=lowbit(p);
	}
}

inline ll query(ll l,ll r) {
	ll res=MINval;
	while (l<=r) {
		if(r-lowbit(r)<l) {
			res=max(A[r]-sumA[r-1],res);
			r-=1;
		}else {
			res=max(tr[r],res);
			r-=lowbit(r);
		}
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i=1;i<=N;++i) {	// 初始化树状数组
		tr[i]=MINval;
	}
	// 我的思路是肯定要预处理这个东西，然后重量加减应该没那么复杂，就是加在第一块上就行
	// 然后我们其实就是要求需要加了多少嘛
	// 我们可以把这个问题转化为RMQ，即该区间内最大的A[i]-sumA[i-1];
	for(int i=1;i<=N;++i) {
		cin>>A[i];
		sumA[i]=sumA[i-1]+A[i];
		change(i,A[i]-sumA[i-1]);
	}

	for(int i=1;i<=Q;++i) {
		ll l,r;
		cin>>l>>r;
		if(l==r) {cout<<0<<'\n';continue;}	// 特判特殊情况
		cout<<max(query(l+1,r)+sumA[l-1],0LL)<<'\n';
	}
	// cout<<"debug:\n";
	// for(int i=1;i<=N;++i) {
	// 	cout<<tr[i]<<' ';
	// }
	// cout<<'\n';
	return 0;
}
/*
6 4
1 1 4 5 1 4
1 2
1 3
2 5
1 6

15 6
5 23 56 71 13 63 24 61 2 76 28 37 46 12 43
1 15
7 8
8 9
4 7
4 11
9 10

28
37
0
0
0
74

*/

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

WA

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

1
2
3
for(int i=1;i<lowbit(p);i<<=1) {
			tr[p]=max({tr[p-i],tr[p],x});
	}

i<lowbit(p)，你想lowbit（p）就是其表示区间的长度