CFB
思路
要想找出一个合法的子集，必须至少有一个元素漏选，可以通过枚举漏选的元素\(q\)，找到最大的符合题目要求的并集。我们可以先预处理出所有集合的并集，然后枚举\(q\)，如果当前集合包含\(q\)，那么舍去这个集合，否则就并入，这样遍历处理\(q\)，取最大值即可。
这里需要注意的几点：
- 由于是多组数据，所以需要清空数组
a和s。
- 因为集合的元素是不可重复的，所以在计算时需要考虑元素重复的情况，我们可以用一个桶来记录，当然每次处理完后也需要清空桶。
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--) solve();
}
int s[55][55];
int a[55];
int flag[55];
void solve()
{
int n; cin>>n;
memset(a,0,sizeof(a));
memset(s,0,sizeof(s));
for(int i=1;i<=n;i++)
{
int k; cin>>k;
for(int j=1;j<=k;j++)
{
int num; cin>>num;
s[i][num]=1;
a[num]=1;
}
}
int ans=0;
int cnt=0;
for(int i=1;i<=50;i++)
{
cnt=0;
if(!a[i]) continue;
memset(flag,0,sizeof(flag));
for(int j=1;j<=n;j++)
{
if(s[j][i]) continue;
for(int k=1;k<=50;k++)
{
if(!flag[k] && s[j][k])
{
cnt++;
flag[k]=1;
}
}
}
ans=max(ans,cnt);
}
cout<<ans<<"\n";
}
|
思路
我对这道题的大致理解是：一个块\((i,j)\)放置一个土豆，说明填充了第\(i\)行，第\(j\)列。
我们需要的是填充满每一个块。我们可以一行一行地填充，或者一列一列地填充。以行为例，我们只需要选出所有列的最小值，然后加上行和即可。列填充也是类似的处理方法。最后只需要从这两种处理结果取最小值即可。
代码如下：
#include <bits/stdc++.h>
const int MAXN=3e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--) solve();
}
ll a[MAXN];
ll b[MAXN];
ll sa[MAXN];
ll sb[MAXN];
void solve()
{
int n; cin>>n;
ll min_a=1e15;
for(int i=1;i<=n;i++)
{
cin>>a[i];
min_a=min(a[i],min_a);
}
ll min_b=1e15;
for(int j=1;j<=n;j++)
{
cin>>b[j];
min_b=min(b[j],min_b);
}
int cnt1=0;
for(int i=1;i<=n;i++)
{
sa[++cnt1]=min_a+b[i];
}
ll ans1=0;
for(int i=1;i<=cnt1;i++)
{
ans1+=sa[i];
}
int cnt2=0;
for(int i=1;i<=n;i++)
{
sb[++cnt2]=min_b+a[i];
}
ll ans2=0;
for(int i=1;i<=cnt2;i++)
{
ans2+=sb[i];
}
cout<<min(ans1,ans2)<<"\n";
}
|
思路
题意有点抽象，结合例子，讲人话就是，我们对串\(s\)进行修改，使得其成为回文串，然后使用另外一个串\(l\)（长度为\(n+1\)），来表示修改了多少位，使得\(s\)可以成为回文串，举个例子，如果可以修改两位使得其成为回文串，那么\(l_2=1\)。
以上是题意，下面说一下思路。
我们可以使用双指针从两端开始扫描，可以发现，如果相同，改或不改都行。如果不同，那么必须进行一次修改。分别对必须的修改和不必须的修改进行记录。再用一个数组记录即可。这里还需要注意的是，如果长度是奇数，那么另外多进行一次修改。
细节:
代码如下：
#include <bits/stdc++.h>
const int MAXN=1e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--) solve();
}
int ans[MAXN];
void solve()
{
int n; cin>>n;
string s; cin>>s;
s='@'+s;
int cnt_base=0;
int cnt_add=0;
int cnt_equil=0;
for(int i=1,j=n;i<=j;++i,--j)
{
if(i==j)
{
cnt_equil=1;
}
else
{
if(s[i]!=s[j]) ++cnt_base;
else cnt_add+=1;
}
}
ans[cnt_base]=1;
if(!cnt_equil)
{
for(int i=1;i<=cnt_add;i++)
{
cnt_base+=2;
ans[cnt_base]=1;
}
}
else
{
for(int i=1;i<=cnt_add*2+1;i++)
{
ans[cnt_base+i]=1;
}
}
for(int i=0;i<=n;i++)
{
cout<<ans[i];
ans[i]=0;
}
cout<<"\n";
}
|
思路
如果可以绕主要城市，那么肯定消耗的钱是更少的（不然要走多余的城市，花更多的钱），我们可以多走主要城市。主要有两种走法：
我们可以计算这两种情况的距离，起点到终点的距离直接计算即可。
绕过主要城市，那么肯定是越近越好，需要考虑起点或者终点本身就是主要城市的情况，这样就直接为0。我们分别处理起点到主要城市的距离、终点到主要城市的距离即可。
代码如下：
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--) solve();
}
ll x[MAXN],y[MAXN];
ll dis(int a,int b)
{
return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
void solve()
{
int n,k; cin>>n>>k;
int st,ed; cin>>st>>ed;
for(int i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
}
ll a_len=1e15,b_len=1e15;
if(st>k)
{
for(int i=1;i<=k;i++)
{
a_len=min(a_len,dis(i,st));
}
}
else a_len=0;
if(ed>k)
{
for(int i=1;i<=k;i++)
{
b_len=min(b_len,dis(i,ed));
}
}
else b_len=0;
cout<<min(a_len+b_len,dis(st,ed))<<"\n";
}
|
思路
可以发现是以0开头，以1结尾的，我们可以这样构造：两个式子的左边都是0，右边都是1。这样的构造就符合题意。（没有注意到开头和结尾，直接写\(dp\)写不出来）。
代码如下：
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--) solve();
}
bool flag[MAXN];
void solve()
{
string a,b; cin>>a>>b;
int n=a.length();
for(int i=0;i<n;i++)
{
if(a[i]=='0' && b[i]=='0' && a[i+1]=='1' && b[i+1]=='1')
{
cout<<"Yes\n";
return;
}
}
cout<<"No\n";
}
|
思路
贪心的想法：肯定是多用\(k\)值的硬币更好。可以先计算出需要的\(k\)值硬币和\(1\)元硬币，如果拥有的1元硬币比需要的多，我们可以使用多余的来凑出\(k\)值硬币，这样可以消耗的更少。最后计算需要的值和拥有的数量之差即可。
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--) solve();
}
void solve()
{
int m,k,a1,ak; cin>>m>>k>>a1>>ak;
int num_1=m%k;
int num_k=m/k;
if(a1>num_1)
{
ak+=(a1-num_1)/k;
a1=num_1;
}
if(ak>num_k) ak=num_k;
cout<<num_1-a1+num_k-ak<<"\n";
}
|
思路
不难想到，我们可以先选去每个数组中最小的元素进行去除，影响结果的只有最小值和次小值。但是还得将这些选出的最小元素塞入到其他的数组中，最好的塞法就是塞到同一个数组中，（塞入到多个数组中，肯定会使得美丽值更小），并且该数组的最小值也会被更新，我们尽量让美丽值减少的少一些即可。也就是该数组原来的次小值和最小值的差最小。
代码如下：
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--) solve();
}
ll a[MAXN];
void solve()
{
int n; cin>>n;
ll ans=0;
ll min_1=1e15,min_2=1e15;
for(int i=1;i<=n;i++)
{
int m; cin>>m;
for(int j=1;j<=m;j++)
{
cin>>a[j];
}
sort(a+1,a+1+m);
ans+=a[2];
min_1=min(min_1,a[1]);
min_2=min(min_2,a[2]);
}
cout<<ans-min_2+min_1<<"\n";
}
|
思路
我们可以将\(a\)数组全部元素减去1，再考虑将减去后为0的元素进行填补为2。进行这样的操作构造，需要注意：
- 这里需要填充的是所有值为1的元素，进行这样操作所需要的数值就是对应的个数。
- 能够提供的就是所有元素的总和减去n。
代码如下：
#include <bits/stdc++.h>
const int MAXN=1e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--) solve();
}
ll a[MAXN];
void solve()
{
int n; cin>>n;
if(n==1)
{
cin>>a[1];
cout<<"No\n";
}
else
{
ll maxn=0;
ll cnt_0=0;
ll sum=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]-=1;
if(!a[i])
{
cnt_0++;
}
sum+=a[i];
}
if(cnt_0>sum) cout<<"No\n";
else cout<<"Yes\n";
}
}
|
思路
区间中的每一个数都是\(n\)的因数，假设存在一个数\(x\)不是\(n\)的因数，那么\(x\)的倍数也不是\(n\)的因数，那么对应区间的长度的最大值也只能是\(x-1\)。
我们可以从1开始计算，直到找到第一个不是\(n\)的因数的数字即可。
代码如下：
#include <bits/stdc++.h>
const int MAXN=1e5+10;
using namespace std;
using ll=long long;
void solve();
ll a[MAXN];
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
ll n; cin>>n;
for(int i=1;i;i++)
{
if(n%i)
{
cout<<i-1<<"\n";
return;
}
}
}
|
思路
问题的关键是：只有最后一刀才是有效的，前面只是削弱怪物的血量。我们先进行取模运算，为0的肯定是最先被杀死的，剩下的怪物按照血量从大到小排序，即可得到全部的顺序。
#include <bits/stdc++.h>
const int MAXN=3e5+10;
using namespace std;
using ll=long long;
void solve();;
ll ans[MAXN];
struct node
{
int id;
ll val;
}a[MAXN];
bool cmp(node a,node b)
{
if(a.val==b.val)
{
return a.id<b.id;
}
return a.val>b.val;
}
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
int n,k; cin>>n>>k;
int cnt=0;
for(int i=1;i<=n;i++)
{
cin>>a[i].val;
a[i].val%=k;
a[i].id=i;
if(!a[i].val)
{
ans[++cnt]=i;
}
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
if(a[i].val==0) break;
else
{
ans[++cnt]=a[i].id;
}
}
for(int i=1;i<=cnt;i++)
{
cout<<ans[i]<<" ";
}
cout<<"\n";
}
|
思路
我们尝试找一下规律: \[
a_3=a_2+a_1
\]
\[
a_4=a_3+a_2=2a_2+a_1
\]
而\(a_5=a_4+a_3\)，分别计算\(a_1\)和\(a_2\)的系数，这里其实也是利用斐波那契数列的递推关系。我们可以得到\(a_n\)是由多少个\(a_1\)和\(a_2\)组成的。我们再枚举\(a_1\)可能的值，从而推导出\(a_2\)可能的值即可。需要注意的是：
- \(k\)的范围太大，而\(n\)最大是2e5，所以当\(30 \leq
k\)时，无解，直接输出0即可。不然直接处理会TLE。
- \(a_1 \leq
a_2\)这个是一个潜在的条件。
代码如下：
#include <bits/stdc++.h>
const int MAXN=3e5+10;
using namespace std;
using ll=long long;
void solve();;
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
}
ll a1[MAXN],a2[MAXN];
void solve()
{
int n,k; cin>>n>>k;
if(k>=30)
{
cout<<0<<"\n";
return;
}
a1[3]=1,a2[3]=1;
a1[4]=2,a2[4]=1;
for(int i=5;i<=k;i++)
{
a1[i]=a1[i-1]+a1[i-2];
a2[i]=a2[i-1]+a2[i-2];
}
int ans=0;
for(int i=0;i<=n;i++)
{
int num=n-a2[k]*i;
if(num>0 && num%a1[k]==0 && num/a1[k]>=i)
{
ans++;
}
}
cout<<ans<<"\n";
}
|
思路
一个大致的思路是：我们对每一种颜色单独处理。我们只能修改一块的颜色，使得需要跨越的距离变小。不难想到对最大值\(p\)进行处理（进行折半），得到\(\lfloor \frac{p}{2}
\rfloor\)，然后再与次小值\(q\)进行比较，取两者的最大值，最后遍历所有的颜色取最小值即可。
代码如下：
#include <bits/stdc++.h>
const int MAXN=3e5+10;
using namespace std;
using ll=long long;
void solve();;
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
}
ll c[MAXN];
ll nxt[MAXN];
ll head[MAXN];
void solve()
{
int n,k; cin>>n>>k;
ll ans=1e15;
for(int i=1;i<=n;i++)
{
head[i]=nxt[i]=0;
}
for(int i=1;i<=n;i++)
{
cin>>c[i];
nxt[i]=head[c[i]];
head[c[i]]=i;
}
for(int p=1;p<=k;p++)
{
ll max_1=n-head[p],max_2=0;
ll num=0;
for(int i=head[p];i;i=nxt[i])
{
num=i-nxt[i]-1;
if(num>max_1)
{
max_2=max_1;
max_1=num;
}
else if(num>max_2)
{
max_2=num;
}
}
ans=min(ans,max(max_1>>1,max_2));
}
cout<<ans<<"\n";
}
|
思路对了，但是写挂了。
后面再补一下。
思路
与运算的结果只会越来越小，我们可以尽量进行与运算，使得结果为0，这样就可以砍一刀，得到一个分组。需要注意的是：
- 如果全部与运算后不为0（这是最小的结果），那么只能直接划分为1组。
- 如果中间部分存在结果为0，我们就砍一刀。如果最后的部分不为0，我们直接并入前面的即可。
代码如下：
#include <bits/stdc++.h>
const int MAXN=3e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
}
ll a[MAXN];
void solve()
{
int n; cin>>n;
ll cnt=0;
ll sum=-1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum=sum&a[i];
}
if(sum)
{
cout<<1<<"\n";
return;
}
sum=-1;
for(int i=1;i<=n;i++)
{
if(sum==-1)
{
sum&=a[i];
}
sum=sum&a[i];
if(sum==0)
{
sum=-1;
cnt++;
}
}
cout<<cnt<<"\n";
}
|
思路
分成\(x\)和\(y\)分别计算，注意到\(x_a(y_a)\)只能是最小或者最大的情况。再与\(x_b(y_b)、x_c(y_c)\)中的最近点计算即可。
需要注意的是：
代码如下：
#include <bits/stdc++.h>
const int MAXN=3e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
}
ll x[4],y[4];
void solve()
{
for(int i=1;i<4;i++)
{
cin>>x[i]>>y[i];
}
ll ans=1;
if(x[1]<=x[2] && x[1]<=x[3])
{
ans+=min(x[2],x[3])-x[1];
}
else if(x[1]>x[2] && x[1]>x[3])
{
ans+=x[1]-max(x[2],x[3]);
}
if(y[1]<=y[2] && y[1]<=y[3])
{
ans+=min(y[2],y[3])-y[1];
}
else if(y[1]>y[2] && y[1]>y[3])
{
ans+=y[1]-max(y[2],y[3]);
}
cout<<ans<<"\n";
}
|
思路
发现数据范围很大，所以想到拆位处理。看样例不难发现，当\(r\)和\(l\)存在从某一位开始不同时，也就是\(r_x-l_x>0\)时，后面的位肯定可以构造成\(|0-9|\)或者\(|9-0|\)。所以我们逐位查找计算。如果相等就跳过，如果不等就计入ans，并且从此后开始构造出\(|0-9|\)或者\(|9-0|\)的形式。
需要注意的是：
- 两者相等的情况：直接输出0即可。
- 位数不同，那么\(l\)需要添加前导0。
#include <bits/stdc++.h>
const int MAXN=3e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
string l,r; cin>>l>>r;
if(l==r)
{
cout<<0<<"\n";
return;
}
if(l.length()<r.length())
{
string tmp=l;
l=r;
for(int i=0;i<r.length();i++)
{
if(i<r.length()-tmp.length()) l[i]='0';
else l[i]=tmp[i-r.length()+tmp.length()];
}
}
ll ans=0;
ll n=l.length();
ll flag=0;
for(int i=0;i<n;i++)
{
if(l[i]==r[i]) continue;
else
{
ans+=r[i]-l[i];
flag=i;
break;
}
}
ans+=(n-flag-1)*9;
cout<<ans<<"\n";
}
|
细节还是写挂了。。。
思路
我们按照题目的描述进行构造，分为四种情况
- \(a_i\)直接接入末尾，此时还是一个单增序列。\(a_{i-1}\leq a_{i}\)。
- \(a_i<a_{i-1}\)，但是比\(a_1\)大，所以可以接入末尾，这样将前面的单增部分往后补充即可。需要使用一个\(flag\)作为记号。
- \(flag\)存在，且\(a_i\leq
a_1\)，这样才可以继续往后补充。这个需要特别注意。
- 否则不能补充。
代码如下：
#include <bits/stdc++.h>
const int MAXN=3e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
}
ll a[MAXN];
void solve()
{
int n; cin>>n;
cin>>a[1];
cout<<1;
ll flag=0,last=a[1];
for(int i=2;i<=n;i++)
{
cin>>a[i];
if(a[i]>=last && flag==0)
{
cout<<1;
last=a[i];
}
else if(a[i]<=a[1] && flag==0)
{
cout<<1;
last=a[i];
flag=1;
}
else if(a[i]<=a[1] && flag && a[i]>=last)
{
cout<<1;
last=a[i];
}
else cout<<0;
}
cout<<"\n";
}
|
思路
不难想到让1和2这两个元素的距离越远越好，这样得到的排列数目是最少的。
但是如果只是简单地放在左右两边（1左2右），可能不是最好的效果，而且题目要求只能交换一次。
可以这样构造：只要最大数\(n\)位于1和2中间，这样如果要得到满足题意的排列，那么必须长度大于等于\(n\)，比这长度小的肯定会缺少一些关键的元素，无法构成排列。
所以构造时：1左2右，\(n\)中间。这是三者的相对顺序。
代码如下：
#include <bits/stdc++.h>
const int MAXN=3e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
}
ll a[MAXN];
void solve()
{
int n; cin>>n;
int pos_1=0;
int pos_2=0;
int pos_n=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]==1)
{
pos_1=i;
}
if(a[i]==2)
{
pos_2=i;
}
if(a[i]==n)
{
pos_n=i;
}
}
if(pos_1>pos_2) swap(pos_1,pos_2);
if(pos_1>pos_n) cout<<pos_1<<" "<<pos_n;
else if(pos_2<pos_n) cout<<pos_2<<" "<<pos_n;
else cout<<pos_1<<" "<<pos_1;
cout<<"\n";
}
|
思路对了，脑子一抽自己全推翻了。
思路
不难想到从\(a\)和\(b\)两个数组中，各自寻找同一个元素的最长连续段。然后把他们拼接起来，然后枚举元素值，得到的就是最长的。
证明：我们以数字2为例子，其余元素不关心。
- ------222222------
- ---222-------------
我们只需要把前面的无关部分先取出，然后再拼接起来即可。
需要注意的细节：
- 计算连续最长的段时，最后的一段需要特别处理，具体看代码。
- 不要使用memset，会TLE。
- 最后枚举元素时，需要分别枚举\(a\)和\(b\)中的元素，因为元素类型可能是不同的。
代码如下：
#include <bits/stdc++.h>
const int MAXN=4e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
}
ll a[MAXN];
ll b[MAXN];
ll a_length[MAXN];
ll b_length[MAXN];
void solve()
{
int n; cin>>n;
ll cnt_a=1,cnt_b=1;
for(int i=1;i<=2*n;i++)
{
a_length[i]=b_length[i]=0;
}
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
}
for(int i=2;i<=n;i++)
{
if(a[i]==a[i-1])
{
cnt_a++;
}
else
{
a_length[a[i-1]]=max(cnt_a,a_length[a[i-1]]);
cnt_a=1;
}
if(b[i]==b[i-1])
{
cnt_b++;
}
else
{
b_length[b[i-1]]=max(cnt_b,b_length[b[i-1]]);
cnt_b=1;
}
}
a_length[a[n]]=max(a_length[a[n]],cnt_a);
b_length[b[n]]=max(b_length[b[n]],cnt_b);
ll ans=1;
for(int i=1;i<=n;i++)
{
ans=max({ans,a_length[a[i]]+b_length[a[i]],a_length[b[i]]+b_length[b[i]]});
}
cout<<ans<<"\n";
}
|
思路
构造题，不难发现可以使用连续的整数进行构造：12345······，那么关键的就是找到一段最长连续<(>)的子段的长度，答案就是再此基础上+1。
代码如下：
#include <bits/stdc++.h>
const int MAXN=4e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
int n; cin>>n;
string s; cin>>s;
ll cnt=1;
ll maxn=0;
for(int i=1;i<n;i++)
{
if(s[i]==s[i-1])
{
cnt++;
}
else
{
maxn=max(maxn,cnt);
cnt=1;
}
}
maxn=max(maxn,cnt);
cout<<maxn+1<<"\n";
}
|
思路
看一下样例，首先直觉猜测跟排序和当前的位置有关，我们先对其进行一次排序。计算得出如果交换位置的差值。猜测可能是取所有需要交换差值的最小公约数（可以打个表试一下）。
需要注意的是：
- 差值可能为0，需要特判一下。
- 输入的时候\(a_1\)先处理一下，作为\(ans\)。
代码如下：
#include <bits/stdc++.h>
const int MAXN=4e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
}
struct node
{
ll val;
int id;
}a[MAXN];
ll b[MAXN];
bool cmp(node a,node b)
{
return a.val<b.val;
}
void solve()
{
int n; cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].val;
a[i].id=i;
}
sort(a+1,a+1+n,cmp);
ll ans=abs(1-a[1].id);
for(int i=2;i<=n;i++)
{
b[i]=abs(i-a[i].id);
if(b[i]==0) continue;
else
{
ans=__gcd(ans,b[i]);
}
}
cout<<ans<<"\n";
}
|
以为是贪心，发现不对，写了个类似dp的东西，还是不对。。。
思路
不难想到先进行排序，如果直接贪心处理（每一次一直从两端取最大的元素或者两个最小的元素），发现有一个不符合样例（样例5）。所以贪心的方法是错误的。
再发现，我们取完\(k\)次后是一段连续的区间。也就是去掉两头，那么我们可以枚举去掉的两头的元素，这里使用前缀和进行处理。得到的最后结果就是\(sum_{n-k+i}-sum_{2*i}\)。我们只需要枚举\(i\)，取最大值即可。
代码如下：
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
}
ll a[MAXN];
ll sum[MAXN];
void solve()
{
memset(a,0,sizeof(a));
int n; cin>>n;
int k; cin>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
}
ll ans=0;
for(int i=0;i<=k;i++)
{
ans=max(ans,sum[n-k+i]-sum[2*i]);
}
cout<<ans<<"\n";
}
|
思路
构造题。
一开始我的想法是：左上角放最大的元素，然后对角线放最小的元素，另外的第一行和第一列（及位置(2,1)和(1,2)）特别处理，但是发现不对。
更合理的构造方法是：把最小的元素放在(2,1)，次小的元素放在(1,2)，这样得到的结果更大。不过也可能位置反过来，因为\(n\)和\(m\)的大小关系。我们的想法是尽可能大一些，所以如果\(n>m\)就放在(2,1)，反之同理。
还需要注意的是：
- 可以在左上角放最小值，(2,1)和(1,2)放最大值。
- 最终答案取max即可。
代码如下：
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t; cin>>t;
while(t--)
{
solve();
}
}
ll a[MAXN];
ll b[4];
bool cmp(ll a,ll b)
{
return a>b;
}
void solve()
{
int n,m; cin>>n>>m;
for(int i=1;i<=n*m;i++)
{
cin>>a[i];
}
int k=n*m;
ll ans_1=0;
ll ans_2=0;
sort(a+1,a+1+k);
if(n>m)
{
ans_1=(n-1)*m*(a[k]-a[1])+(m-1)*(a[k]-a[2]);
}
else
{
swap(n,m);
ans_1=(n-1)*m*(a[k]-a[1])+(m-1)*(a[k]-a[2]);
}
sort(a+1,a+1+k,cmp);
if(n>m)
{
ans_2=(n-1)*m*(a[1]-a[k])+(m-1)*(a[2]-a[k]);
}
else
{
swap(n,m);
ans_2=(n-1)*m*(a[1]-a[k])+(m-1)*(a[2]-a[k]);
}
cout<<max(ans_1,ans_2)<<"\n";
}
|
思路
不难发现，对称位置的元素取模\(x\)后是相等的，并且他们的差值一定是\(x\)的倍数，要求最大的\(x\)，只需要逐个计算对称位置的差值，取他们的最小公约数就是答案。
需要注意的是：
- 无限大的情况，这里只需要特判一个元素的情况即可，即输出0。
代码如下：
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
ll a[MAXN];
ll b[MAXN];
void solve()
{
int n; cin>>n;
int cnt=0;
for(int i=1;i<=n;i++) cin>>a[i];
if(n==1)
{
cout<<0<<"\n";
return;
}
for(int i=0;i<n/2;i++)
{
b[++cnt]=abs(a[n-i]-a[1+i]);
}
ll ans=b[1];
for(int i=2;i<=cnt;i++)
{
ans=__gcd(ans,b[i]);
}
cout<<ans<<"\n";
}
|
思路
构造题，还是不会。
CF1818B 题解 -
洛谷专栏 (luogu.com.cn)
代码如下：
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
int n; cin>>n;
if(n==1) cout<<1;
else if(n&1) cout<<-1;
else
for(int i=1;i<=n;i++)
{
if(i&1) cout<<i+1<<" ";
else cout<<i-1<<" ";
}
cout<<"\n";
}
|
侥幸猜过去的。。。以后还是得找一下正确解法。
思路
跟之前一道题类似，只不过这里可以进行一次额外的操作。要想使得交换的距离
为\(k\)的倍数，且额外操作的次数最多为1。
我们先排序，计算各个位置的数需要的交换距离。讨论其中不是\(k\)的倍数的个数的情况：
- 大于3，肯定不行，输出-1。
- 等于0，不用额外操作，输出0。
- 等于1，感觉不行（不知道怎么证明），输出-1。
- 等于2，感觉可以（看样例），输出1。
代码如下：
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
struct node
{
int id;
int val;
}a[MAXN];
bool cmp(node a,node b)
{
return a.val<b.val;
}
int b[MAXN];
void solve()
{
int n; cin>>n;
int k; cin>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i].val;
a[i].id=i;
}
sort(a+1,a+1+n,cmp);
int cnt=0;
for(int i=1;i<=n;i++)
{
b[i]=abs(i-a[i].id);
if(b[i]%k)
{
cnt++;
}
}
if(cnt>2)
{
cout<<-1;
}
else if(cnt==0)
{
cout<<0;
}
else if(cnt==2)
{
cout<<1;
}
else
{
cout<<-1;
}
cout<<"\n";
}
|
思路
不难想到，先找出两个数组中从左右两端开始不同的数字，这是最小的长度。还可以往两端进行扩展：
- 往左一直找比\(b_{st}\)更小的，往右一直找比\(b_ed\)更大的。
代码如下：
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
int a[MAXN];
int b[MAXN];
void solve()
{
int n; cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
}
int st=0;
int ed=0;
for(int i=1;i<=n;i++)
{
if(a[i]!=b[i])
{
if(!st)
{
st=i;
}
}
if(a[n-i+1]!=b[n-i+1])
{
if(!ed)
{
ed=n-i+1;
}
}
}
for(int i=st-1;i>=1;i--)
{
if(b[i]<=b[st]) st--;
else break;
}
for(int i=ed+1;i<=n;i++)
{
if(b[i]>=b[ed]) ed++;
else break;
}
cout<<st<<" "<<ed<<"\n";
}
|
思路对了，不会一些小技巧。。。
思路
不难想到规律：
1111 11111 111111 1111111
1111 11111 111111 1111111
1111 11111 111111 1111111
1111 11111 111111 1111111
11111 111111 1111111
111111 1111111
1111111
|
要使得面积最大，且$x+y=n+\(1，利用基本不等式，要使得\)xy\(最大，\)x\(和\)y\(应该尽可能接近。注意这里的\)n$是1串的最大长度。
可以发现 \(n\)为偶数时，面积是\(\frac{n×(n+2)}{4}\)，\(n\)为奇数时为\(\frac{(n+1)×(n+1)}{4}\)。
把这两种情况合起来就是\(\frac{n+2}{2}×\frac{n+1}{2}\)。
需要注意的是：
- \(s\)全1时需要特判一下。
- 一定要按照上面的式子计算，因为是利用了计算机向下取整的性质。
- 注意开$long long $。
- 首尾相接的情况：可以使用拼接进行处理。
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
string s; cin>>s;
s=s+s;
ll n=s.length();
ll maxn=0;
ll cnt=0;
for(int i=0;i<n;i++)
{
if(s[i]=='0')
{
maxn=max(maxn,cnt);
cnt=0;
}
else cnt++;
}
maxn=max(maxn,cnt);
if(maxn==n) cout<<n/2*n/2;
else cout<<(maxn+2)/2*((maxn+1)/2);
cout<<"\n";
}
|
思路
还是构造题，不难想到对图进行旋转，然后暴力查找不同的地方并记录。
修改一个不同的地方，对应的两幅图是有两个位置的方块是不同的。这里分类讨论一下：
- 如果修改完不同的地方后，剩下的次数是偶数（因为修改相同的地方话，要修改两次），输出YES.
- 如果不是偶数，那么看\(n\)是不是奇数，如果是奇数，剩下的\(k\)是奇数就没有问题。如果不是奇数，则输出NO。
- 如果\(k\)不够，那么输出NO。
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
int a[1010][1010];
int b[1010][1010];
void solve()
{
int n,k; cin>>n>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
b[i][j]=a[i][j];
}
}
for(int i=1;i<=n;i++)
{
reverse(b[i]+1,b[i]+1+n);
}
int cnt=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]!=b[n-i+1][j])
{
cnt++;
}
}
}
if(cnt/2<=k)
{
if((k-cnt/2)%2==0) cout<<"YES\n";
else
{
if(n%2) cout<<"YES\n";
else cout<<"NO\n";
}
}
else cout<<"NO\n";
}
|
思路
构造题，观察几个样例，可以发现：左上角和右下角是必须经过的，而且他们对答案的贡献是只增不减的，所以把两个最大的数字放在左上角和右下角。
剩下的构造：（把左上角和右下角剔除不考虑）。可以发现：上面的奇数位置是-，偶数位置是+，下面的奇数位是-，偶数位是正的。+代表可以使得答案变大，-代表可以使得答案变小。
并且贪心的想：肯定是位置越小的格子越容易走到。
综上可以这样构造：以\(n=5\)为例子。
上面的是: 2 8 4 6 下面的是:1 7 3 5。这样交错的构造。
即上面的是：偶数位是从大到小递减，奇数位是从小到大递增。下面的也是同理。
代码如下：
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
int n; cin>>n;
int m=2*n;
cout<<m<<" ";
for(int i=1;i<n;i++)
{
if(i&1)
{
cout<<2*(i/2+1)<<" ";
}
else
{
cout<<m-i<<" ";
}
}
cout<<"\n";
for(int i=1;i<n;i++)
{
if(i&1)
{
cout<<i<<" ";
}
else
{
cout<<m-1-i<<" ";
}
}
cout<<m-1<<"\n";
}
|
数学题，不会。。。
思路
先贪心地想：肯定是先让\(leg\)长度变长越好，这样后续的操作才更少。所以我们先进行变长的操作，再进行移动。
假设长度为\(m\),那么向上的操作和向右的操作是\(\lceil \frac{a}{m} \rceil\)和\(\lceil \frac{b}{m}
\rceil\)，变长的操作就是\(m-1\)，因为最初的长度是1。那么总共的操作次数：\(m-1+\lceil \frac{a}{m} \rceil + \lceil \frac{b}{m}
\rceil\)。
但是如果直接暴力枚举\(m\)肯定会TLE。这个再观察一下可以发现，类似基本不等式：\(m+\frac{a+b}{m}\)，所以\(m\)的近似值为\(\sqrt{a+b}\)。我们估计一下范围就是1~5e5之间。直接暴力枚举即可。
不过这个向上取整比较奇怪：我原来的写法是(a+0.5)/i，但是WA了。
\((a+i-1)/i\)这种写法比较好，作为一个\(trick\)。
代码如下：
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
ll ans=1e15;
ll a,b; cin>>a>>b;
for(int i=1;i<=5e5;i++)
{
ans=min(ans,(a+i-1)/i+(b+i-1)/i+i-1);
}
cout<<ans<<"\n";
}
|
忘记清空map了，WA了一发。。。
思路
不难想到，直接从原序列中找到最小的字母拼接在前面。
需要注意的是：如果有多个，我们选择排在后面的最小字母。
以abaca为例子：可以变为aabca（前）、aabac（后），不难发现取后面的更小。
注意：
- 需要清空map，否则会WA。（样例没WA纯属侥幸）。
代码如下：
#include <bits/stdc++.h>
const int MAXN=2e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
map<int,int> mp;
int pos[MAXN];
void solve()
{
int n; cin>>n;
string s; cin>>s;
for(int i=0;i<26;i++)
{
mp[i]=0;
}
for(int i=0;i<n;i++)
{
mp[s[i]-'a']++;
pos[s[i]-'a']=i;
}
int flag=0;
for(int i=0;i<26;i++)
{
if(mp[i])
{
flag=i;
break;
}
}
cout<<char('a'+flag-0);
for(int i=0;i<n;i++)
{
if(i==pos[flag]) continue;
else cout<<s[i];
}
cout<<"\n";
}
|
思路大致对了，但是没写完。。。
仔细一想，这个系数求解确实不难。。。
思路
较为入门的解决方案 -
洛谷专栏 (luogu.com.cn)
如果直接暴力肯定会TLE，所以改变策略，我们取一列观察，改变顺序对结果没有影响，所以不难想到排个序，列一下例子查看系数的关系，具体看上面的链接。（这个东西的求法好像也是一个套路？）。
另外的写法：CF1808B Playing in a
Casino 题解 - 洛谷专栏 (luogu.com.cn)
需要注意的细节：
- 这里用的是vector，不然会MLE。
- 需要开long long，不然WA。
代码如下：
#include <bits/stdc++.h>
const int MAXN=3e5+10;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
ll b[MAXN];
void solve()
{
int n; cin>>n;
int m; cin>>m;
vector<vector<ll>> a(n+1,vector<ll>(m+1,0));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
ll ans=0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
b[j]=a[j][i];
}
sort(b+1,b+1+n);
for(int j=1;j<=n;j++)
{
ans+=(2*j-n-1)*b[j];
}
}
cout<<ans<<"\n";
}
|
