牛客暑期多校5简单题解_点到直线的距离公式推导

H.Nazrin the Greeeeeedy Mouse

题意：有$n$块奶酪成直线分布，第$i$块的体积为$a_i$，重量为$w_i$.现在可以拿这$n$块奶酪$m$次，每一次都有一个容积为$s{z}_i$的背包。对于$i>1$,$s{z}_i\ge s{z}_{i-1}$，总是成立的。每次拿的奶酪的总体积不能超过背包容积，每次遇到奶酪如果背包容积足够，那么可以拿取，如果不拿这个奶酪而要走到后面则对奶酪打洞，打洞的奶酪不能拿取，也可以选择回到原点。
每次拿取后一定要回到原点。
思路：如果只拿一次，那么是一个经典的背包问题，我们直接DP即可。但是它可以拿$m$次，且当前的拿取情况会对以后产生影响。
观察到$n$和$a_i$的值域只有200.可以处理出在每个区间$[l,r]$背包容积为$j$的可拿取的最大奶酪重量，记为$f_{l,r,j}$。
按照题目的要求，上一次背包的奶酪要么已经被拿走，要么已经被打洞，皆不能在被拿取。所以当前次的拿取可以从上一次的终点开始
设$g_{i,j}$为第$i$次拿取终点为$j$的最大奶酪重量。
转移的式为
$g_{i,j}=max(g_{i,j},g_{i-1,k}+f_{k+1,j,s{z}_i})$
m的值域在1e5，如果全部枚举一遍会超时。
奶酪的总数只有200个，而且背包的容积是递增的，只需要枚举后200个背包即可。最后答案对第m个背包取max即可。

//It's better to have sex than to do questions
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=205;
const ll md=1e9+7;
const ll inf=1e18;
const ll eps=1e-9;
const double E=2.718281828;
int n,m,f[N][N][N],a[N],b[N],sz[N],g[100005][N];
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
	for(int i=1;i<=m;i++){
		cin>>sz[i];
	}
	for(int be=1;be<=n;be++){
		for(int ed=be;ed<=n;ed++){
			for(int j=1;j<a[ed];j++){
				f[be][ed][j]=f[be][ed-1][j];
			}
			for(int j=a[ed];j<=200;j++){
				f[be][ed][j]=max(f[be][ed-1][j],f[be][ed-1][j-a[ed]]+b[ed]);
			}
		}
	}
	int pre=0;
	int mx=0;
	for(int i=max(1,m-200);i<=m;i++){
		for(int j=1;j<=n;j++){
			for(int k=0;k<j;k++){
				g[i][j]=max({g[i][j],g[i-1][k]+f[k+1][j][sz[i]]});
			}			
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,g[m][i]);
	}
	cout<<ans<<endl;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
}
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

D.Cirno’s Perfect Equation Class

题意：给定式子 $ka+b=c$要求b为c的因素，$gcd(a,b)\ge n$ 求满足要求的正整数对$(a,b)$数量
$1\le k,n,c\le 10^9$ 多组输入，最多100组
思路：直接枚举c的因素，判断是否满足条件即可。

//It's better to have sex than to do questions
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=0;
const ll md=1e9+7;
const ll inf=1e18;
const double eps=1e-9;
const double E=2.718281828;
struct graph{
	int cnte,hd[N];
	struct  edge{
		int v,nt;
	}e[N<<1];
	void addedge(int v,int u){
		e[++cnte].v=u;
		e[cnte].nt=hd[v];
		hd[v]=cnte;
	}
};
int k,c,n;
int gcd(int a,int b){
	if(a==0){
		return b; 
	}
	return gcd(b%a,a);
}
void solve(){
	cin>>k>>c>>n;
	vector<int>p;
	for(int i=1;i*i<=c;i++){
		if(c%i==0){
			int a=i,b=c/i;
			p.push_back(a);
			if(a!=b){
				p.push_back(b);
			}
		}
	}
	int ans=0;
	for(int b:p){
		int a=(c-b)/k;
		if((c-b)%k==0&&a>0&&gcd(a,b)>=n){
//			cout<<a<<" "<<b<<endl;
			ans++;
		}
	}
	cout<<ans<<endl;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	cin>>t;
	while(t--){
		solve();
	}

}

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

I.The Yakumo Family

题意：给定一个数组，求以下公式的值，对998244353取模。
${\sum }_{1\le l1\le r1<l2\le r2<l3\le r3\le n}xor(l1,r1)\times xor(l2,r2)\times xor(l3,r3)$

思路：三个区间，可以通过维护前缀后缀得到第一个和第三个的所有区间的xor的和，但是第二个朴素暴力的想法复杂度高达$O(n^2)$，显然不行。
根据异或的特征，可以拆位考虑。独立计算每一位上面的值是0/1的情况。
首先
维护前缀，
对原数组做前缀异或和记为$s_i$，目的维护点$s_i$与右边任意一点的异或的和再加上自身。
设点$i$左边的点在第$j$位上的值为$k\in [0,1]$的个数之和为$f{p}_{i,j,k}$
设在点$i$左边的（包括点$i$）所有异或和的和为$pr{e}_i$
设$s_i$在第$j$位上的值为$x$
$pr{e}_i=pr{e}_{i-1}+f{p}_{i-1,j,x\oplus 1}\times (1<<j)$
$f{p}_{i,j,x}=f{p}_{i-1,j,x}+1$ （自身）
$f{p}_{i,j,x\oplus 1}=f{p}_{i-1,j,x\oplus 1}$
一样的
对原数组做后缀异或和记为$s_i$，目的维护点$s_i$与右边任意一点的异或的和再加上自身。
设点$i$右边的点在第$j$位上的值为$k\in [0,1]$的个数之和为$f{s}_{i,j,k}$
设在点$i$右边的（包括点$i$）所有异或和的和为$su{f}_i$
设$s_i$在第$j$位上的值为$x$
$su{f}_i=su{f}_{i+1}+f{s}_{i+1,j,x\oplus 1}\times (1<<j)$
$f{s}_{i,j,x}=f{s}_{i+1,j,x}+1$ （自身）
$f{s}_{i,j,x\oplus 1}=f{s}_{i+1,j,x\oplus 1}$

$f{p}_{0,j,0}$和$f{s}_{n+1,j,0}$均初始化为1。

枚举第二个区间的左端点$i$，继承上一步的后缀异或$s_i$，计算点$i$与右边的任意一点$j$异或与$su{f}_{j+1}$的乘积。仍是拆位，
设点i右边（包括$i$)的所有点与该点右边任意点的异或值的在第$j$位上值为$k$的和为$f{m}_{i,j,k}$
设$s_i$在第$j$位上的值为$x$
$ans=ans+pr{e}_{i-1}\times f{m}_{i+1,j,x\oplus 1}\times (1<<j)$
$f{m}_{i,j,x}=f{m}_{i+1,j,x}+su{f}_i$
$f{m}_{i,j,x\oplus 1}=f{m}_{i+1,j,x\oplus 1}$

可以发现对于$fs,fp,fm$,都是前面一位向后面一位转移，可以优化掉第一维。

//It's better to have sex than to do questions
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=2e5+5;
const ll md=998244353;
const ll inf=1e18;
const double eps=1e-9;
const double E=2.718281828;
ll n,a[N],pre[N],suf[N],s[N];
ll fp[31][2],fs[31][2],fm[31][2];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		s[i]=s[i-1]^a[i];
	}
	for(int j=0;j<31;j++){
		fp[j][0]=1;
	}
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1];
		for(int j=0;j<31;j++){
			int x=s[i]>>j&1;
			pre[i]+=fp[j][x^1]*(1<<j)%md;
			pre[i]%=md;
		}
		for(int j=0;j<31;j++){
			int x=s[i]>>j&1;
			fp[j][x]++;
		}
	}
	for(int i=n;i>=1;i--){
		s[i]=s[i+1]^a[i];
	}
	for(int j=0;j<31;j++){
		fs[j][0]=1;
	}
	for(int i=n;i>=1;i--){
		suf[i]=suf[i+1];
		for(int j=0;j<31;j++){
			int x=s[i]>>j&1;
			suf[i]+=fs[j][x^1]*(1ll<<j)%md;
			suf[i]%=md;
		}
		for(int j=0;j<31;j++){
			int x=s[i]>>j&1;
			fs[j][x]++;
		}
	}
    //中间段的每一位
	for(int j=0;j<31;j++){
		fm[j][0]=0;
	}
	ll ans=0;
	for(int i=n;i>=1;i--){
		for(int j=0;j<31;j++){
			int x=s[i]>>j&1;
			ans+=pre[i-1]*fm[j][x^1]%md*(1ll<<j)%md;
			ans%=md;
		}
		for(int j=0;j<31;j++){
			int x=s[i]>>j&1;
			fm[j][x]+=suf[i];
			fm[j][x]%=md;
		}
	}
	cout<<ans<<endl;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
}

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

E.Red and Blue and Green

题意：构造一个置换，满足题目中给定区间里面的逆序对的奇偶性。给定区间保证相交即包含。

思路：给定区间满足相交即包含，那么如果满足了某个区间其子区间也得满足。将区间编号，映射到树上，从叶子节点开始向上走每一个节点检查是否满足要求。
设初始置换是1到n有序排列的，所有的区间的逆序对均是0个
在叶子节点上，区间为$[l,r]$
如果区间长度只有1，要求奇数个逆序对，无法达到
如果区间长度大于1，要求奇数个逆序对，交换$p_l,p_{l+1}$
非叶子节点，
儿子节点逆序对相加满足要求，那么就满足要求了。
如果不满足，找到区间空余的元素，取最大/最小，和儿子区间的最大/最小交换。因为每个区间满足情况后元素只是相对位置变化，没有新加的元素。这样交换，改变了当前区间的逆序对奇偶，没有改变儿子区间的逆序对奇偶。

//It's better to have sex than to do questions
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e3+5;
const ll md=1e9+7;
const ll inf=1e18;
const double eps=1e-9;
const double E=2.718281828;
struct graph{
	int cnte,hd[N];
	struct  edge{
		int v,nt;
	}e[N<<1];
	void addedge(int v,int u){
		e[++cnte].v=u;
		e[cnte].nt=hd[v];
		hd[v]=cnte;
	}
};
graph tr;
struct aa{
	int l,r,oe;
	bool operator<(const aa &x){
		if(x.l==l){
			return r>x.r;
		}
		return l<x.l;
	}
}rg[N];
int n,m,p[N],fa[N];
bool dfs(int x){
	bool res=1;
	if(tr.hd[x]==0){
		if(rg[x].l==rg[x].r&&rg[x].oe==1){
			return 0;
		}
		if(rg[x].oe==1){
			swap(p[rg[x].l],p[rg[x].l+1]);
		}
		return 1;
	}
	int oe=0,son;
	for(int i=tr.hd[x];i;i=tr.e[i].nt){
		int v=tr.e[i].v;
		son=v;
		res&=dfs(v);
		oe^=rg[v].oe;
	}
	if(!res)return res;
	if(oe!=rg[x].oe&&x!=0){
//		cout<<son<<" "<<rg[son].l<<" "<<rg[son].r<<" | "<<x<<" "<<rg[x].l<<" "<<rg[x].r<<endl;
		if(rg[son].l==rg[x].l){
			int mn=-1,mx=-1;
			for(int i=rg[son].l;i<=rg[son].r;i++){
				if(mx==-1){
					mx=i;
				}else if(p[mx]<p[i]){
					mx=i;
				}
			}
			for(int i=rg[son].r+1;i<=rg[x].r;i++){
				if(mn==-1){
					mn=i;
				}else if(p[mn]>p[i]){
					mn=i;
				}
			}
			swap(p[mx],p[mn]);
		}else{
			int mn=-1,mx=-1;
			for(int i=rg[x].l;i<rg[son].l;i++){
				if(mx==-1){
					mx=i;
				}else if(p[mx]<p[i]){
					mx=i;
				}
			}
			for(int i=rg[son].l;i<=rg[son].r;i++){
				if(mn==-1){
					mn=i;
				}else if(p[mn]>p[i]){
					mn=i;
				}
			}
			swap(p[mx],p[mn]);
		}
	}
	return res;
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		p[i]=i;
	}
	for(int i=1;i<=m;i++){
		cin>>rg[i].l>>rg[i].r>>rg[i].oe;
	}
	sort(rg+1,rg+1+m);
	int pt=0;
	for(int i=1;i<=m;i++){
		while(pt>0&&rg[pt].r<rg[i].r){
			pt=fa[pt];
		}
		tr.addedge(pt,i);
        fa[i]=pt;
		pt=i;
	}
	if(dfs(0)){
		for(int i=1;i<=n;i++){
			cout<<p[i]<<" ";
		}
		cout<<endl;
	}else{
		cout<<-1<<endl;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
}
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
133
134
135
136

B.Circle of Mistery

题意：给定$k$，给定一个置换1到n的所有权值$w_i$，要求构造一个置换存在一个环满足$\sum w_i\ge k$,求置换最小的逆序对个数的情况。自环也是环
思路：如果取某几个点成环，所影响的区间是这几个点最左边的点和最右边的点还有内部不选的点。
设取点$[l,r]$成环，内部不选的点的个数为$cnt$,逆序对数量为$r-l-cnt$
$1\le n\le 1000$,可以$n^2$的快乐枚举，去枚举所选择的区间$[l,r]$其中正数一定要选择，然后再满足$now\ge k$的情况下尽可能的多选择点。用优先队列贪心即可。
维护优先队列$in$表示选择的负数点，$out$表示不选择的负数点
左端点一定为正数，每次遇到一个正数就去更新一次答案。
判断out的堆顶元素与in的对顶元素交换能否对now产生正的贡献，如果能则交换。
判断out的堆顶元素能否进入in，使out的size最小
当前的逆序对就是 $j-i+out.size()$

//It's better to have sex than to do questions
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e3+5;
const ll md=1e9+7;
const ll inf=1e18;
const double eps=1e-9;
const double E=2.718281828;
int n,k,w[N];
void solve(){
	cin>>n>>k;
	bool f=0;
	for(int i=1;i<=n;i++){
		cin>>w[i];
		if(w[i]>=k){
			f=1;
		}
	}
	if(f){
		cout<<0<<endl;
		return ;
	}
	priority_queue<int>in,out;// in 升序 out 降序 
	int ans=md;
	for(int i=1;i<=n;i++){
		int now=0;
		if(w[i]<=0)continue;
        while(!in.empty())in.pop();
        while(!out.empty())out.pop();
		for(int j=i;j<=n;j++){
			if(w[j]<=0){
				out.push(w[j]);
			}else{
				now+=w[j];
				while(!in.empty()&&!out.empty()&&out.top()+in.top()>0){
					int tmpi=in.top(),tmpo=out.top();
					now=now+tmpo+tmpi;
					in.pop();
					out.pop();
					in.push(-1*tmpo);
					out.push(-1*tmpi); 
				}
				while(!out.empty()&&now+out.top()>=k){
					in.push(-1*out.top());
                    now+=out.top();
					out.pop();
				}
				if(now>=k){
//					cout<<i<<" "<<j<<endl; 
					ans=min(ans,j-i+(int)out.size());
				}
            }
		}
	}
	if(ans==md)ans=-1;
	cout<<ans<<endl;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
}
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

G.Go to Play Maimai DX

题意：给定一个长度为n数组仅包含1，2，3，4。求包含1，2，3至少1次，包含4至少k次的最短区间的长度。
思路：枚举区间左端点，维护每个点右边最近的1，2，3的距离，和最近的k个4的距离，取min即可

//It's better to have sex than to do questions
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e5+5;
const ll md=1e9+7;
const ll inf=1e18;
const double eps=1e-9;
const double E=2.718281828;
struct graph{
	int cnte,hd[N];
	struct  edge{
		int v,nt;
	}e[N<<1];
	void addedge(int v,int u){
		e[++cnte].v=u;
		e[cnte].nt=hd[v];
		hd[v]=cnte;
	}
};
int n,k,a[N],suf[N][5];
int qu[N];
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=4;i++){
		suf[n+1][i]=md;
	}
	int ans=md,cnt=0;
	for(int i=n;i>=1;i--){
		for(int j=1;j<=4;j++){
			suf[i][j]=suf[i+1][j];
		}
		if(a[i]==4){
			qu[++cnt]=i;
			if(cnt>=k){
				suf[i][a[i]]=qu[cnt-k+1];
			}
		}else{
			suf[i][a[i]]=i;
		}
//		cout<<i<<" "<<max({suf[i][1],suf[i][2],suf[i][3],suf[i][4]})<<endl;
		ans=min(ans,max({suf[i][1],suf[i][2],suf[i][3],suf[i][4]})-i+1);
	}
	cout<<ans<<endl;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}
}

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

C.Cheeeeen the Cute Cat

先研究研究竞赛图