题意
在 轴上给出 个横坐标,每个点可以变为,,,问该序列最后是否可以变为一个接续序列
解题思路
对于一段接续的点要保证其连续性，就必须将这段接续的点作为一个整体全部向左移动一格或向右移动一格
因此，在轴可以划分出若干条线段(各线段中间以空隙点将线段隔开)，并且最左侧线段最多只能右移一格，不能左移，最多能使空隙点数量减一，最右侧线段最多只能左移一格，不能右移，最多使空隙点数量减一，而移动中间线段将不改变空隙点数量
当空隙点数量为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
| #include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
int ans=0;
for(int i=1;i<n;i++){
ans+=(a[i]-a[i-1]-1);
}
if(ans<=2) puts("YES");
else puts("NO");
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 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
| #include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
void solve()
{
int n;
cin>>n;
vector<ll> a(n),b(n,0);
for(int i=0;i<n;i++)
cin>>a[i];
ll res=1e18,ans=0;
for(int pos=0;pos<n;pos++){
for(int i=0;i<n;i++) b[i]=0;
ans=0;
for(int i=pos-1;i>=0;i--){
ll d=b[i+1]-b[i];
ll k=(d+a[i])/a[i];
b[i]=k*a[i];
ans+=k;
}
for(int i=pos+1;i<n;i++){
ll d=b[i-1]-b[i];
ll k=(d+a[i])/a[i];
b[i]=k*a[i];
ans+=k;
}
res=min(res,ans);
}
cout<<res<<"\n";
}
int main()
{
solve();
return 0;
}
|
题意
给定，构造一个排列使得
解题思路
对于构造排列，排列无非就三种：递增排列，递减排列，摆动排列
思考问题一般习惯从特殊一般来考虑
假设为递增排列，那么
假设为递减排列，那么
- 考虑一般：将特殊排列中的任意几个数调换位置即变为摆动摆列
我们发现：
假设为递增排列，当每将一对调换位置，将使得减少
假设为递减排列，当每将一对调换位置，将使得增加
故要使得
我们可以先使序列为递减序列，然后在此基础上选择k对调换位置，即可使得
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <bits/stdc++.h>
using namespace std;
void solve()
{
int n,k;
cin>>n>>k;
vector<int>a(2*n);
for(int i=0;i<2*n;i++) a[i]=2*n-i;
for(int i=0;i<k;i++) swap(a[2*i],a[2*i+1]);
for(int i=0;i<2*n;i++)
cout<<a[i]<<" ";
cout<<"\n";
}
int main()
{
solve();
return 0;
}
|
题意
定义二元组是幸运的当且仅当
定义由起始长度为的幸运链，当且仅当恒成立
若给定一个二元组,求由它生成的最长幸运链的最长长度(若长度可以为，答案记为)
解题思路
假设从开始，中间均是幸运的，直到不幸运即：
利用性质可得：
易知：当时，,答案
当时，则转变求的最小值
当时，那么至少存在一个公共质因子
于是乎，上面问题可以进一步转化：对进行质因子分解(欧拉筛法(线性))，假设枚举的一个质因子为,
则：的可能取值就是满足的，即有：
对所有可能的取最小，即得到最小的的取值，由此幸运链的长度为,答案
解题代码
注意要打消iostream的输入和输出缓存，节省时间,否则会
设置如下：
std::ios::sync_with_stdio(false);
std::cin.tie(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
| #include <iostream>
#include <vector>
#include <bitset>
using namespace std;
typedef long long ll;
const int N=1e7+10;
const int INF=2e9;
int minp[N];
void euler(ll n)
{
bitset<N> vis;
vector<ll> p;
vis[0]=vis[1]=true;
minp[1]=1;
for(ll i=2;i<=n;i++){
if(!vis[i]){
p.push_back(i);
minp[i]=i;
}
for(ll j=0;i*p[j]<=n&&j<p.size();j++){
vis[i*p[j]]=true;
minp[i*p[j]]=p[j];
if(i%p[j]==0) break;
}
}
}
void solve()
{
ll x,y;
cin>>x>>y;
y-=x;
ll res=INF;
if(y==1) res=-1;
else{
while(y>1){
ll p=minp[y];
res=min(res,((-x)%p+p)%p);
while(y%p==0) y/=p;
}
}
cout<<res<<"\n";
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
euler(1e7);
int t;
cin>>t;
while(t--)
solve();
}
|
题意
给定一个01字符串 ，你需要选取
中的一个子串 ，最小化
解题思路
设：子串中的个数，:子串中的个数，:字符串中1的个数
(为子串长度)
由于求最小值，因此要将其最小化，为定值，我们需要尽可能大(子串中的数量尽可能多)，而随着增大，增大，故我们选择
由于求最小值，因此要将其最小化，我们需要尽可能小(子串中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
| #include <bits/stdc++.h>
using namespace std;
void solve()
{
string s;
cin>>s;
int len=s.size();
s='?'+s;
int sum=count(s.begin(),s.end(),'1');
vector<int> pre(len+1,0);
for(int i=1;i<=len;i++){
pre[i]=pre[i-1]+(s[i]=='0');
}
int res=sum;
for(int i=sum;i<=len;i++){
res=min(res,pre[i]-pre[i-sum]);
}
cout<<res<<"\n";
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}
|