Codeforces Round #721 (Div. 2)
来源：https://codeforces.com/contest/1527
A. And Then There Were K
不妨打一个表看看有没有什么规律.
发现每个数字 $\mathrm{x}$ 的答案是 $\mathrm{x}$ 二进制展开中最高次位减一.
直接对每个数 $O( \log n) $ 扫一下即可.
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
ll calc(ll x) {
for(int i=32;i>=0;--i) {
if(x&(1ll<<i)) {
return (1ll<<i)-1;
}
}
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) {
ll n ;
scanf("%lld",&n);
printf("%lld\n",calc(n));
}
return 0;
}
B1 - Palindrome Game (easy version)
此版本的串为回文串.
假如 0 的个数为偶数，则后手可以一直模仿先手.
剩 2 个数时，先手将 $0$ 变 $1$ 后使用一次跳步，可以少取 2 次.
假如 0 的个数为奇数，且只有一个 0 则后手胜，否则先手胜.
这是因为先手可以先取中间的 0，然后转化成一个偶数的子问题.
先手在第一步吃亏一步，后面后手吃亏 2 步，先手胜.
#include <cstdio>
#include <vector>
#include <cstring>
#define N 10007
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
char str[N];
void solve() {
int n ;
scanf("%d",&n);
scanf("%s",str+1);
int cnt=0;
for(int i=1;i<=n;++i) if(str[i]==‘0‘) ++cnt;
if(cnt > 1 && (cnt % 2 == 1)) printf("ALICE\n");
else printf("BOB\n");
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
B2. Palindrome Game (hard version)
假设最开始不是回文串：
如果长度为偶数，则先手可以一直使用跳步，后手要凑成回文串.
在差一步能凑成回文串时先手走那一步，然后就变成 B1 中长度为偶数先手必败子问题了.
故 ALICE 获胜.
若长度为奇数，则要看中间位置是否为 0.
若中间位置为 1，则与偶数情况无异，ALICE 获胜.
若中间位置为 0，则先手走中间位置后又变成上面 ALICE 获胜子问题.
唯一使得 ALICE 不胜的情况就是中间位置为 0，且一共只有两个 0.
这样 ALICE 走完第一步后 BOB 走完第二步两者就打平了.
#include <cstdio>
#include <vector>
#include <cstring>
#define N 10007
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
char str[N];
void solve() {
int n ;
scanf("%d",&n);
scanf("%s",str+1);
int cnt=0;
int flag=0;
for(int i=1;i<=n;++i) {
if(str[i]==‘0‘) ++cnt;
if(str[i] != str[n-i+1]) flag=1;
}
if(!flag) {
if(cnt > 1 && (cnt % 2 == 1)) printf("ALICE\n");
else printf("BOB\n");
}
else {
if(n % 2 == 1 && str[(1+n)/2] == ‘0‘ && cnt == 2) printf("DRAW\n");
else printf("ALICE\n");
}
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
C.Sequence Pair Weight
将每一种数字单独提取出来并单独计算贡献.
枚举右端点，然后每一个左端点的贡献就是该左端点的位置.
扫一遍即可.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define N 100009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
vector<int>v[N];
int a[N],A[N],n;
void solve() {
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]), A[i]=a[i];
sort(A+1,A+1+n);
for(int i=1;i<=n;++i) {
a[i]=lower_bound(A+1,A+1+n,a[i])-A;
v[a[i]].pb(i);
}
ll ans=0ll;
for(int i=1;i<=n;++i) {
if(v[i].size() < 2) continue;
ll sum=0ll;
for(int j=0;j<v[i].size();++j) {
ans += 1ll*(n - v[i][j] + 1) * sum;
sum += v[i][j];
}
}
printf("%lld\n",ans);
for(int i=1;i<=n;++i) {
v[i].clear();
}
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
D.MEX Tree
根据 $\mathrm{mex}$ 的定义，若 $\mathrm{mex=i}$, 则路径需要包含 $1$ ~ $\mathrm{i-1}$, 且不包含 $\mathrm{i}$.
同时要求包含和不包含不好做，不妨考虑差分.
令 $\mathrm{dp[i]}$ 表示 $\mathrm{mex}$ 值至少为 $\mathrm{i}$ 的路径条数.
求解的时候维护 $1$ ~ $\mathrm{i}$ 这些点所构成的链，然后每次计算包含这条链的路径数即可.
#include <cstdio>
#include <set>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 200009
#define pb push_back
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int n ;
int size[N];
int val[N], mk[N], hd[N], fa[N],to[N<<1],nex[N<<1], edges;
ll dp[N];
void add(int u, int v) {
nex[++edges]=hd[u];
hd[u]=edges;
to[edges]=v;
}
void dfs(int x, int ff) {
fa[x]=ff;
size[x]=1;
for(int i=hd[x];i;i=nex[i]) {
int v=to[i];
if(v==ff) continue;
dfs(v, x);
size[x]+=size[v];
}
}
void solve() {
scanf("%d",&n);
for(int i=1;i<=n;++i) val[i]=i-1;
for(int i=1;i<n;++i) {
int x, y;
scanf("%d%d",&x,&y);
++x, ++y;
add(x, y);
add(y, x);
}
// 全部点对的 mex 至少为 0.
dp[0] = 1ll*n*(n-1)/2;
dfs(1, 0);
int L = 1, R = 1, son = 0;
mk[1] = 1;
ll det = 0ll;
for(int i=hd[1];i;i=nex[i])
det += 1ll*size[to[i]] * (size[to[i]] - 1) / 2;
dp[1] = dp[0] - det;
for(int i = 1; i < n; ++ i) {
int p = i + 1;
// 考虑将 p 加入进去 (val[p] = i )
// 算 mex = i + 1, 加入 i, 即 （i + 1)
if(mk[i + 1]) {
dp[i + 1] = dp[i];
continue;
}
// 没有加入 i.
int flag=0, o, lst = p;
for(o = p; ; o = fa[o]) {
if(mk[o]) {
if(o == L|| o == R ) flag=1;
break;
}
else mk[o] = 1, lst = o; // 加入这个权值.
}
if(!flag) {
// 没戏.
// mex 没办法大于等于 i+1 了.
break;
}
else {
if(o == 1) {
son = lst;
}
if(o == L) L = p;
else R = p;
// o 就是左端点.
if(L > 1 && R > 1) {
dp[i + 1] = 1ll*size[L]*size[R];
}
else {
if(L == 1) dp[i + 1] = 1ll*size[R]*(n - size[son]);
if(R == 1) dp[i + 1] = 1ll*size[L]*(n - size[son]);
}
}
}
for(int i=0;i<=n;++i) {
printf("%lld ",dp[i]-dp[i+1]);
}
printf("\n");
for(int i=0;i<=n+1;++i) {
dp[i]=0;
hd[i]=0,size[i]=fa[i]=mk[i]=val[i]=0;
}
for(int i=0;i<=edges;++i) nex[i]=to[i]=0;
edges=0;
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
E.Partition Game
考虑朴素 DP
令 $\mathrm{f[i][j]}$ 表示 DP 到 $\mathrm{i}$, 分了 $\mathrm{j}$ 段的最小值.
考虑用线段树维护这个 DP.
每次维护右端点为 $\mathrm{i}$ 时左端点的答案.
右端点向右移动时对应的就是一段区间加法，用线段树来维护即可.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 35008
#define ll long long
#define pb push_back
#define ls now<<1
#define rs now<<1|1
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const ll inf=10000000000000ll;
struct Segment_Tree {
ll lazy[N<<2],mn[N<<2];
void mark(int now, int v) {
lazy[now]+=v;
mn[now]+=v;
}
void pushdown(int now) {
if(lazy[now]) {
mark(ls, lazy[now]);
mark(rs, lazy[now]);
}
lazy[now]=0;
}
void pushup(int now) {
mn[now]=min(mn[ls],mn[rs]);
}
void modify(int l,int r,int now,int p,int v) {
if(l==r) {
mn[now]=v;
return ;
}
pushdown(now);
int mid=(l+r)>>1;
if(p<=mid) modify(l,mid,ls,p,v);
else modify(mid+1,r,rs,p,v);
pushup(now);
}
void update(int l,int r,int now,int L,int R,int v) {
if(l>r||L>R) return ;
if(l>=L&&r<=R) {
mark(now, v);
return ;
}
pushdown(now);
int mid=(l+r)>>1;
if(L<=mid) update(l,mid,ls,L,R,v);
if(R>mid) update(mid+1,r,rs,L,R,v);
pushup(now);
}
ll query(int l,int r,int now,int L, int R) {
if(l>=L&&r<=R) return mn[now];
pushdown(now);
int mid=(l+r)>>1;
if(L<=mid&&R>mid) return min(query(l,mid,ls,L,R), query(mid+1,r,rs,L,R));
else if(L<=mid) return query(l,mid,ls,L,R);
else return query(mid+1,r,rs,L,R);
}
void build(int l,int r,int now) {
mn[now]=inf;
lazy[now]=0;
if(l==r) return ;
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
}
}T;
int A[N], lst[N];
ll dp[N];
int main() {
// setIO("input");
int n,K;
scanf("%d%d",&n,&K);
for(int i=1;i<=n;++i) {
scanf("%d",&A[i]);
}
T.build(0,n,1);
T.modify(0,n,1,0,0);
// 0 -> f[0][0]=0;
for(int i=1;i<=K;++i) {
for(int j=1;j<=n;++j) lst[A[j]]=0;
for(int j=1;j<=n;++j) {
// 考虑加入 j 的影响.
int v=A[j];
if(lst[v]) {
// [lst[v]+1, i] 的左端点不变.
// [1, lst[v]] 左端点的答案 + det;
int det=j-lst[v];
// [1, lst[v]] -> 对应到 [0, lst[v]-1] 计算.
T.update(0,n,1,0,lst[v]-1,det);
}
dp[j]=T.query(0,n,1,0,j-1);
lst[v]=j;
}
T.build(0,n,1); // 将线段树清空.
for(int j=1;j<=n;++j) T.modify(0,n,1,j,dp[j]);
}
printf("%lld\n",dp[n]);
return 0;
}