之前落下的每一场比赛都是要补回来的。。。
G Go to Play Maimai DX
题解的想法比较简单,由于找到满足1,2,3出现至少一次,4出现至少k次的最短区间,所以可以双指针,双指针用于这种长度最短,长度越长越容易满足条件的题就很恰当。
我没想到双指针,就写的比较麻烦,预处理每个数后一个1,2,3的位置,以及4的特殊处理,每次枚举左端点,计算右端点即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define db double
#define endl '\n'
#define rep(x,y,z) for(int x=y;x<=z;++x)
#define fep(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
const int N=1e5+10;
int n,k,a[N],nex[N][5],pl[5],p[N],ct[N],tot;
int main()
{
// freopen("1.in","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
rep(i,1,n) cin>>a[i];
rep(i,1,3) pl[i]=n+1;
fep(i,n,1)
{
rep(j,1,3) nex[i][j]=pl[j];
pl[a[i]]=i;
ct[i]=tot;
if(a[i]==4)
{
p[++tot]=i;
ct[i]=tot;
}
}
int ans=n;
rep(i,1,n)
{
int mx1=max(max(nex[i][1],nex[i][2]),nex[i][3]);
if(mx1==n+1) continue;
if(ct[i]<k) continue;
mx1=max(mx1,p[ct[i]-k+1]);
ans=min(ans,mx1-i+1);
}
cout<<ans<<endl;
return 0;
}
D Cirno's Perfect Equation Class
没啥难度,按照题意模拟,暴力枚举c的所有因子即可。
C Cheeeeen the Cute Cat
有意思的题目,题目让你明求最大匹配,那么说明正解要么和二分图没关系(大概率),要么就是二分图匹配算法上做一些优化。
其实题目已经提示的很明显了,当提到i和i+n无边,i和i+n,j和j+n之间只能存在一条边时,这就提示我们要将i和i+n合并看,而且题目规定边数为n*(n-1)/2,这个数字也很特殊,不就是完全图吗?合并的时候就有一个问题,考虑方向吗?这个时候我们就要观察二分图的匹配在合并时的特点,发现如果合并时按照无向边合并,则无法有效区分是i到j+n的连边还是j到i+n的连边,所以为了区分,按照有向的合并,i到j+n表示i到j有边,这个时候合并起来的图就是一个竞赛图,之后继续考虑匹配在合并后的图上的体现,简单手玩之后可以发现,一系列的匹配在合并后的图上体现为一些路径,也就是说我们要在新图上选择若干条互不相交的路径,这个时候就需要用到一些性质了。竞赛图必有哈密顿路径,所以答案至少为n-1,接下来只需要考虑答案什么时候是n,即存在哈密顿回路。对于有向图的一个点数大于等于3的强连通分量,肯定存在哈密顿环,(图中不存在强连通分量个数为2的)。即只需要判掉个数为1的强连通分量即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define db double
#define endl '\n'
#define rep(x,y,z) for(int x=y;x<=z;++x)
#define fep(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
const int N=3010;
int n,du[N];
inline bool check()
{
rep(i,1,n) rep(j,1,n)
{
if(i!=j&&du[i]+du[j]<n) return false;
}
return true;
}
int main()
{
// freopen("1.in","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
rep(i,1,n) rep(j,1,n)
{
int x;cin>>x;
du[i]+=x;
}
sort(du+1,du+n+1);
int j=0,s=0;
rep(i,1,n)
{
s+=du[i];
if(s==i*(i-1)/2)
{
if(i-j<3)
{
cout<<n-1<<endl;
return 0;
}
j=i;
}
}
cout<<n<<endl;
return 0;
}