Preface
今天课比较少,就抽点时间补一下之前欠的 CF
这场总体来说题还算简单,E1 之前的题基本都是一眼,不过 E2 没往转化到区间不交的情况想,F 更是完全没想到 color coding,只能说太菜太菜
A. Turtle and Good Strings
不难发现只要比较开头和结尾的字符是否相同即可
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=105;
int t,n; char s[N];
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
scanf("%d%s",&n,s+1);
puts(s[1]!=s[n]?"YES":"NO");
}
return 0;
}
B. Turtle and Piggy Are Playing a Game 2
两人的策略一定是:先手干掉最小的数,后手干掉最大的数,因此最后答案为原序列的中位数,注意当序列长为偶数时中位数偏右
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int t,n,a[N];
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
scanf("%d",&n);
for (RI i=1;i<=n;++i) scanf("%d",&a[i]);
sort(a+1,a+n+1); printf("%d\n",a[n/2+1]);
}
return 0;
}
C. Turtle and Good Pairs
首先不难发现一个串不合法的充要条件为其形如 \(aaa\cdots bbb\cdots\),即由两段相同的字符构成
要最大化合法的区间,只需要最小化不合法的区间,手玩后发现贪心地交错着放最优
具体地,从前往后每次放当前出现次数最多的字符即可,总复杂度 \(O(26\times n)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,c[30]; char s[N];
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
scanf("%d%s",&n,s+1);
for (RI i=1;i<=n;++i) ++c[s[i]-'a'];
for (RI i=1;i<=n;++i)
{
int mx=-1,ch;
for (RI j=0;j<26;++j) if (c[j]>mx) mx=c[j],ch=j;
--c[ch]; putchar(ch+'a');
}
putchar('\n');
}
return 0;
}
D1. Turtle and a MEX Problem (Easy Version)
经典套路 MEX,属于是看一眼就会了
对于一个序列 \(a_1,\dots,a_{l_i}\),我们令 \(x=\operatorname{mex}(a_1,\dots,a_{l_i}),y=\operatorname{mex}(x,a_1,\dots,a_{l_i})\)
此时这个序列相当于可以将 \(x\) 变为 \(y\);同时将非 \(x\) 的所有值变为 \(x\)
不难发现将所有的 \(y\) 求出最大值 \(S\) 后,所有 \(\le S\) 的数一定都能变为 \(S\),因此就很好计算答案了
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,m,l,a[N],vis[N];
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
scanf("%d%d",&n,&m); int mx=0;
for (RI i=1;i<=n;++i)
{
scanf("%d",&l);
for (RI j=1;j<=l;++j)
{
scanf("%d",&a[j]);
if (a[j]<=l+2) vis[a[j]]=1;
}
int mex=0; while (vis[mex]) ++mex;
++mex; while (vis[mex]) ++mex;
mx=max(mx,mex);
for (RI j=1;j<=l;++j)
if (a[j]<=l+2) vis[a[j]]=0;
}
if (m<=mx) printf("%lld\n",1LL*(m+1)*mx);
else printf("%lld\n",1LL*(mx+1)*mx+1LL*(mx+1+m)*(m-mx)/2LL);
}
return 0;
}
D2. Turtle and a MEX Problem (Hard Version)
D1 我们之所以能这么做是因为一个序列可以被用多次,而这里不行
考虑对于每个序列连边 \(x\to y\),即可得到一个 DAG,很容易想到用类似拓扑排序的方法求出从每个数开始能走到的最大的数
但这样只考虑了顺着边走的情况,考虑把重置的情况加入
若某个点 \(i\) 只有一条出边,则任何数都可以变为 \(i\),对于所有这类数取 \(\max\) 用以更新贡献
若某个点 \(i\) 有超过一条出边,则任何数都可以先变为 \(i\),然后沿着 \(i\) 的有向边向后走到最大的数,对于所有这类数也取 \(\max\) 用以更新贡献
最后综合起来讨论一下即可
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,m,l,a[N],vis[N],out[N],f[N]; vector <int> v[N];
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
scanf("%d%d",&n,&m); int base=0,idx=0;
for (RI i=1;i<=n;++i)
{
scanf("%d",&l);
for (RI j=1;j<=l;++j)
{
scanf("%d",&a[j]);
if (a[j]<=l+2) vis[a[j]]=1;
}
int mex=0; while (vis[mex]) ++mex;
int smex=mex+1; while (vis[smex]) ++smex;
++out[mex]; v[smex].push_back(mex);
base=max(base,mex); idx=max(idx,smex);
for (RI j=1;j<=l;++j)
if (a[j]<=l+2) vis[a[j]]=0;
}
for (RI i=0;i<=idx;++i) f[i]=i;
for (RI i=idx;i>=0;--i)
for (auto j:v[i]) f[j]=max(f[j],f[i]);
int mx=0; for (RI i=0;i<=idx;++i)
if (out[i]>1) mx=max(mx,f[i]);
LL ans=0; for (RI i=0;i<=min(idx,m);++i) ans+=max({f[i],mx,base});
if (idx<m) ans+=1LL*(idx+1+m)*(m-idx)/2LL;
printf("%lld\n",ans);
for (RI i=0;i<=idx;++i) out[i]=0,v[i].clear();
}
return 0;
}
E1. Turtle and Inversions (Easy Version) && E2. Turtle and Inversions (Hard Version)
这两题思路差不太多,就放在一起讲了
首先要想到 E1 的做法,整体来看可以把数分为小数(用 \(0\) 表示)和大数(用 \(1\) 表示),此时每一个区间一定是由若干个 \(0\) 加上若干个 \(1\) 构成
定下一种 01 序列后考虑计算其贡献,首先所有的 01 之间都降序排列一定最优,而剩下的贡献只和该序列中 \(10\) 的对出现次数有关
考虑 DP,令 \(f_{i,j}\) 表示处理了前 \(i\) 个位置,此时前 \(i\) 个位置共有 \(j\) 个 \(1\) 时,序列中 \(10\) 的对的出现次数
转移分要求的区间以及没被 cover 的位置两种情况讨论下即可,根据定义还是非常直观的
现在的问题就是 E2 中区间不一定相离,其实也很好处理,考虑将其转化为相离的情况
若存在区间 \([l_1,r_1],[l_2,r_2](l_1\le l_2)\) 相交,则显然 \([l_1,l_2-1]\) 一定全为 \(0\),\([r_1+1,r_2]\) 一定全为 \(1\),此时只要考虑 \([l_2,r_1]\) 的情况即可
用此法可以将原来的限制转化为若干不相交的区间,以及一些以及确定了 01 的位置,再做上面的 DP 即可
总复杂度 \(O(n^2+m\log m)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=5005,INF=1e9;
int t,n,m,pos[N],tp[N],f[N][N]; pi a[N];
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
scanf("%d%d",&n,&m);
for (RI i=1;i<=m;++i) scanf("%d%d",&a[i].fi,&a[i].se);
if (!m) { printf("%d\n",n*(n-1)/2); continue; }
for (RI i=1;i<=n;++i) pos[i]=tp[i]=-1;
sort(a+1,a+m+1); int mnl,mxl,mnr,mxr;
mnl=mxl=a[1].fi; mnr=mxr=a[1].se;
bool flag=1;
for (RI i=2;i<=m+1;++i)
if (i==m+1||mxr<a[i].fi)
{
if (mnr<=mxl) { flag=0; break; }
for (RI j=mnl;j<mxl;++j) tp[j]=0;
for (RI j=mnr+1;j<=mxr;++j) tp[j]=1;
pos[mxl]=mnr;
mnl=mxl=a[i].fi; mnr=mxr=a[i].se;
} else
{
mnl=min(mnl,a[i].fi); mxl=max(mxl,a[i].fi);
mnr=min(mnr,a[i].se); mxr=max(mxr,a[i].se);
}
if (!flag) { puts("-1"); continue; }
for (RI i=0;i<=n;++i) for (RI j=0;j<=n;++j) f[i][j]=-INF;
f[0][0]=0; for (RI i=1;i<=n;++i)
if (pos[i]!=-1)
{
for (RI j=0;j<i;++j)
for (RI k=1;k<pos[i]-i+1;++k)
f[pos[i]][j+k]=max(f[pos[i]][j+k],f[i-1][j]+(pos[i]-i+1-k)*j);
i=pos[i];
} else
{
if (tp[i]==1)
{
for (RI j=1;j<=i;++j)
f[i][j]=max(f[i][j],f[i-1][j-1]);
} else if (tp[i]==0)
{
for (RI j=0;j<i;++j)
f[i][j]=max(f[i][j],f[i-1][j]+j);
} else
{
for (RI j=0;j<=i;++j)
f[i][j]=max(j>0?f[i-1][j-1]:-INF,f[i-1][j]+j);
}
}
int ans=-1;
for (RI i=0;i<=n;++i) ans=max(ans,f[n][i]+i*(i-1)/2+(n-i)*(n-i-1)/2);
printf("%d\n",ans);
}
return 0;
}
F. Turtle and Three Sequences
好经典的 color coding 啊,有人明明知道这个东西却没想到,怎么回事呢
假设 \(b_i\) 的取值范围很小,则可以进行状压 DP,令 \(f_{i,j,mask}\) 表示已经处理了前 \(i\) 个位置,上一个选的 \(a\) 的值为 \(j\),且选取的 \(b_i\) 对应的状压状态为 \(mask\) 对应的贡献最大值
不难发现在枚举 \(mask\) 的情况下这个 DP 和求 LIS 的基本一致,可以用树状数组优化
显然问题是 \(b_i\) 的取值范围太大了,但其实我们只要取 \(m\) 个数,\(m\) 的级别是很小的
因此考虑用 color coding,将每个 \([1,n]\) 的数随机映射到 \([0,m-1]\) 的一个数,映射之后再跑上面的状压 DP
考虑这样做一次得到正解的概率为 \(\frac{m!}{m^m}\),跑足够多的次数后可以得到正确性很高的算法
令 color coding 的次数为 \(T\),总复杂度 \(O(T\times 2^m\times n\log n)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=3005,T=300,INF=1e9;
int n,m,a[N],b[N],c[N],r[N];
class Tree_Array
{
private:
int bit[N];
public:
#define lowbit(x) (x&-x)
inline void clear(void)
{
for (RI i=1;i<=n+1;++i) bit[i]=-INF;
}
inline void add(RI x,CI y)
{
for (++x;x<=n+1;x+=lowbit(x)) bit[x]=max(bit[x],y);
}
inline int get(RI x,int ret=-INF)
{
for (++x;x;x-=lowbit(x)) ret=max(ret,bit[x]); return ret;
}
#undef lowbit
}BIT[1<<5];
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
srand(time(0)); scanf("%d%d",&n,&m);
for (RI i=1;i<=n;++i) scanf("%d",&a[i]);
for (RI i=1;i<=n;++i) scanf("%d",&b[i]);
for (RI i=1;i<=n;++i) scanf("%d",&c[i]);
int ans=-1; for (RI t=1;t<=T;++t)
{
for (RI i=1;i<=n;++i) r[i]=rand()%m;
for (RI i=0;i<(1<<m);++i) BIT[i].clear();
BIT[0].add(0,0);
for (RI i=1;i<=n;++i)
for (RI mask=0;mask<(1<<m);++mask)
{
int x=r[b[i]];
if (!((mask>>x)&1)) continue;
int cur=BIT[mask^(1<<x)].get(a[i])+c[i];
if (mask==(1<<m)-1)
{
ans=max(ans,cur);
}
BIT[mask].add(a[i],cur);
}
}
return printf("%d",ans),0;
}
Postscript
感觉我好像已经很久没有现场打 CF 了,真是越来越怠惰了
标签:typedef,int,968,Codeforces,long,Div,include,RI,define From: https://www.cnblogs.com/cjjsb/p/18399166