mnnu18届测试赛1

A.Jumping Buildings (单调栈)

思路

对于每个位置通过单调栈可以得出右边第一个比他高的位置。复杂度$O(n)$

代码

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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=5e5+50;

int h[maxn];
int R[maxn];

int main()
{
std::ios::sync_with_stdio(false);
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>h[i];
stack<int>st;
for(int i=n;i;i--){
while(!st.empty()&&h[i]>=h[st.top()]){
st.pop();
}
if(!st.empty())R[i]=st.top()-i-1;
else
R[i]=n-i;
st.push(i);
}
for(int i=1;i<=n;i++)cout<<min(h[i],R[i])<<" ";
return 0;
}

B.Divples (因数分解)

思路

很简单的签到了把。直接枚举a的因子判断是否是b的倍数即可 复杂度$O(sqrt(n))$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=5e5+50;

int main()
{
std::ios::sync_with_stdio(false);
ll a,b;
cin>>a>>b;
vector<ll>v;
for(ll i=1;i*i<=a;i++){
if(a%i==0){
if(i%b==0)v.push_back(i);
if((i!=a/i)&&((a/i)%b)==0)v.push_back(a/i);
}
}
sort(v.begin(),v.end());
for(auto i:v)cout<<i<<" ";
return 0;
}

C.Rectangles (离散化预处理后暴力)

思路

关键点就是中间和线上不能有点,那么我们可以考虑枚举一行的两个点,(可以知道这两个点必须是相邻的) 然后我们再在下面的几行中找是否有和这两个点可以组成矩形的点,

同时注意要保证不能矩形中间和线上出现点 复杂度$O(n^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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=5e5+50;

pair<int,int>p[maxn];

vector<int>X[maxn];

int main()
{
std::ios::sync_with_stdio(false);
int n;
cin>>n;
vector<int>v;
for(int i=1;i<=n;i++)cin>>p[i].first>>p[i].second,v.push_back(p[i].first),v.push_back(p[i].second);
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());

for(int i=1;i<=n;i++){
int x=lower_bound(v.begin(),v.end(),int(p[i].first))-v.begin()+1;
int y=lower_bound(v.begin(),v.end(),int(p[i].second))-v.begin()+1;
X[x].push_back(y);
}n=v.size();
int ans=0;
for(int i=1;i<=n;i++)sort(X[i].begin(),X[i].end());
for(int i=1;i<=n;i++){
if(X[i].size()<2)continue;
for(int j=0;j<X[i].size()-1;j++){
int a=X[i][j],b=X[i][j+1];
int flag=1;
for(int j=i+1;flag&&j<=n;j++){
if(X[j].size()==0)continue;
int k=lower_bound(X[j].begin(),X[j].end(),a)-X[j].begin();
if(k==X[j].size())continue;
if(X[j][k]>b)continue;
if(X[j][k]>a&&X[j][k]<b){
flag=0;break;
}
if(X[j].size()==1&&X[j][k]==a){
flag=0;continue;
}
if(X[j].size()==1&&X[j][k]==b){
flag=0;continue;
}
auto kk=upper_bound(X[j].begin(),X[j].end(),b)-X[j].begin();
--kk;
if(kk-k!=1){
flag=0;break;
}
if(X[j].size()<2)continue;
k=lower_bound(X[j].begin(),X[j].end(),a)-X[j].begin();
if(k<X[j].size()-1){
if(X[j][k]==a&&X[j][k+1]==b)ans++,flag=0;
else if(X[j][k]==a)flag=0;
else if(X[j][k]>=a&&X[j][k]<=b)flag=0;
}
}
}
}
cout<<ans<<endl;
return 0;
}

D.Guessing Messages (签到)

思路

直接两个指针正着做就行了 复杂度$O(max(n,m))$

代码

E Chi’s performance (简单DP)

思路

首先我们需要感性得知道放在两边的数必须是最大或者最小值(请自行证明,不难的)

但是有可能两边都方最大值会更优,所以我们就需要存储次大值。

之后我们就可以总结出,对于每一个ID 只有四个元素会有贡献,所以我们对于每一个ID只要存这四个值就行,然后我们暴力DP 每个位置前面放什么数字后面放什么数字

代码

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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1e6+50;

pair<ll,ll>p[maxn];
struct node{
vector<ll>vv;
void update(vector<ll> v){
if(v.size()<=4)vv=v;
else{
vv.push_back(v[0]);
vv.push_back(v[1]);
vv.push_back(v[v.size()-2]);
vv.push_back(v[v.size()-1]);
}
}
}my[maxn];
vector<ll>v[maxn];
ll dp[maxn][5]; /// 1 mi1, 2 mi2, 3 mx1 4 mx2;
int main()
{
std::ios::sync_with_stdio(false);
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i].first>>p[i].second;
}
sort(p+1,p+1+n);
ll cnt=0,mx=0;
for(int i=1;i<=n;i++){
if(p[i].first>mx){
v[++cnt].push_back(p[i].second);
mx=p[i].first;

}
else v[cnt].push_back(p[i].second);
}
for(int i=1;i<=cnt;i++)sort(v[i].begin(),v[i].end());
for(int i=1;i<=cnt;i++){
my[i].update(v[i]);
}
memset(dp,0,sizeof(dp));
// cout<<"cnt="<<cnt<<endl;
for(int i=1;i<=cnt;i++){
for(int j=0;j<my[i+1].vv.size();j++){
for(int k=0;k<my[i].vv.size();k++){
for(int kk=0;kk<my[i].vv.size();kk++){
if(k==kk&&my[i].vv.size()>1)continue;
dp[i][j]=max(dp[i][j],dp[i-1][k]+abs(my[i].vv[kk]-my[i+1].vv[j]));
// cout<<"dp["<<i<<"]["<<j<<"]="<<dp[i][j]<<endl;
}
}
}
}
ll ans=0;
for(int i=0;i<=4;i++){
ans=max(ans,dp[cnt-1][i]);
}
cout<<ans<<endl;
return 0;
}

G.Log Concave Sequences (矩阵快速幂)

思路

首先手动推一下 发现后面一个字符可以填什么只会跟最后面两个字符有关系。所以我们可以考虑存储后面两个字符的状态总共有$3*3=9$种 我们假设一个简单的方法,

$dp[n][pos] $ 表示长度为N最后面两个状态为$pos$的字符串个数 那么这个答案可以直接从$dp[n-1][pos*]$ 得来,但是题目的N有$1e18​$ 所以我们考虑矩阵快速幂,矩阵快速幂的矩阵怎么推出来代码中有,请自行理解。

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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1e6+50;

int f[3][3],a[3][3];

int go[3][3][3];
vector<pair<int,int> > v[3][3];
int b[9][9];
int bb[9][9]={
1,0,0,1,0,0,1,0,0,
1,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,
0,1,0,0,1,0,0,1,0,
0,1,0,0,1,0,0,0,0,
0,1,0,0,0,0,0,0,0,
0,0,1,0,0,1,0,0,1,
0,0,1,0,0,1,0,0,1,
0,0,1,0,0,1,0,0,1
};
map<pair<int,int>,int>mp;

int main()
{
std::ios::sync_with_stdio(false);
int cnt=0;
for(int i=0;i<=2;i++)for(int j=0;j<=2;j++){
mp[{i,j}]=cnt++;
}
for(int i=0;i<=2;i++)for(int j=0;j<=2;j++)f[i][j]=1;
for(int i=3;i<=3;i++){
for(int j=0;j<=2;j++){
for(int k=0;k<=2;k++){
for(int kk=0;kk<=2;kk++){
if(j*kk<=k*k){
v[k][kk].push_back({j,k});
}
}
}
}
}
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++){
for(auto o:v[i][j]){
cout<<o.first<<" "<<o.second<<" -> "<<i<<" "<<j<<endl;
}
}
}
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++){
for(auto o:v[i][j]){
// cout<<o.first<<" "<<o.second<<" -> "<<i<<" "<<j<<endl;
b[mp[{i,j}]][mp[{o.first,o.second}]]=1;
}
}
}
for(int i=0;i<=8;i++){
for(int j=0;j<=8;j++){
cout<<b[i][j]<<",";
}
cout<<endl;
}
return 0;
}

I.Left or Right? How about neither? (最短路 dij)

思路

题目相当于一个状态可以有三种状态转移

1.跳到左边

2.跳到右边

3.跳到相同的数字

如果就这样一直走的话复杂度会很爆炸,但是我们发现跳到相同的数字这个条件很特殊

可以猜到相同的数字只会跳一次,比如你现在是数字3你跳到相同的数字3的位置,那么你以后都不会再跳,因为答案不可能更优。所以我们这样复杂度就降下来了。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
const int oo=1e5+20;
map<int,int>mp;

vector<int>V[maxn];
int cnt;
bool vis[maxn];
ll value[maxn];
int a[maxn];
struct node{
int id;
ll value;
bool operator<(const node &o)const{
return value>o.value;
}
};
int main()
{
ll n,L,R,C;
cin>>n>>L>>R>>C;
int u,v;cin>>u>>v;
for(int i=1;i<=n;i++){
cin>>a[i];
if(mp.count(a[i])==0)mp[a[i]]=++cnt;
V[mp[a[i]]].push_back(i);
}
priority_queue<node>Q;
fill(value,value+oo,1000000000000000000LL);
value[u]=0;
Q.push({u,0});
while(!Q.empty()){
node now=Q.top();
Q.pop();
int id=now.id;
ll v=now.value;
if(id-1>=1&&value[id-1]>v+L){
value[id-1]=v+L;
Q.push({id-1,v+L});
}
if(id+1<=n&&value[id+1]>v+R){
value[id+1]=v+R;
Q.push({id+1,v+R});
}
if(vis[mp[a[id]]]==false){
vis[mp[a[id]]]=true;
int who=mp[a[id]];
for(auto o:V[who]){
if(value[o]>v+C){
value[o]=v+C;
Q.push({o,v+C});
}
}
}
}
cout<<value[v]<<endl;
return 0;
}

J.Houston, Are You There? (优雅暴力)

思路

看到这题n只有8所以脑子里应该要有点冲动的想法把。

我们考虑暴力出所有的状态。首先每个牌都可以翻转是把?所以我们现在有总共有

$2^8$种状态,这里可以考虑用二进制状压来遍历记录。

其次每个牌都可以对调位置是把?是不是有$A_{n}^{n}$ 种情况,这里我们用全排列来记录

所以总状态数为$2^8 ×8!$ 种情况 自己用电脑算算复杂度会不会超。然后我们还需要$O(n)$的时间来判断是否合法

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
const int oo=1e5+20;

int a[maxn],b[maxn];

int tmp[maxn],vis[maxn];

int main()
{
std::ios::sync_with_stdio(false);
int n;
// int tmp=1;
// for(int i=1;i<=8;i++)tmp*=i;
// cout<<(tmp*(1<<8))<<endl;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
}
for(int i=0;i<(1<<n);i++){
for(int j=0;j<n;j++)if(i&(1<<j))swap(a[j],b[j]);
vector<int>v;
for(int j=0;j<n;j++)v.push_back(j);
do{
int flag=1;
for(int j=1;j<n;j++){
if(b[v[j-1]]!=a[v[j]]){
flag=0;break;
}
}
if(flag){
for(int j=0;j<n;j++){
tmp[j]=v[j]+1;
if((1<<(v[j]))&i)vis[j]=1;
}
for(int j=0;j<n;j++){
cout<<tmp[j]<<" "<<char(vis[j]?'b':'a')<<endl;
}
return 0;
}
}while(next_permutation(v.begin(),v.end()));
for(int j=0;j<n;j++)if(i&(1<<j))swap(a[j],b[j]);
}
return 0;
}

K.Dahlia The Champion (gcd)

思路

首先会不会被盖住是不是说明他们的角度(叉积)不同,但是这个叉积是double类型的会有误差很难存是把, 所以我们可以考虑用$gcd$ 来缩小范围,比如点$(4,6)$ 和点$(2,3)$ 他们肯定会被盖住是把。那么点$(4,6)$ 其实可以变成点$(2,3)$ ….想想。

于是我们就可以把压缩后的点存起来,注意四个向量怎么区别。

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
const int oo=1e5+20;


int main()
{
std::ios::sync_with_stdio(false);
ll x0,y0,R,N;
cin>>x0>>y0>>R>>N;
set<pair<int,int> >st,st2,st3,st4;
while(N--){
ll x,y;
cin>>x>>y;
int tmp1=x,tmp2=y;
x-=x0;y-=y0;
if(sqrt(x*x+y*y)>R)continue;
int gc=__gcd(abs(x),abs(y));x/=gc;y/=gc;
st.insert({x,y});
}
cout<<st.size()<<endl;
return 0;
}