脚本宝典收集整理的这篇文章主要介绍了Codeforces Round #721 (Div. 2)，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
来源：https://codeforces.COM/contest/1527
不妨打一个表看看有没有什么规律.
发现每个数字 $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("%lldn",calc(n)); } return 0; }
此版本的串为回文串.
假如 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("ALICEn");
else printf("BOBn");
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
假设最开始不是回文串：
如果长度为偶数，则先手可以一直使用跳步，后手要凑成回文串.
在差一步能凑成回文串时先手走那一步，然后就变成 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("ALICEn");
else printf("BOBn");
}
else {
if(n % 2 == 1 && str[(1+n)/2] == '0' && cnt == 2) printf("DRAWn");
else printf("ALICEn");
}
}
int main() {
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
将每一种数字单独提取出来并单独计算贡献.
枚举右端点，然后每一个左端点的贡献就是该左端点的位置.
扫一遍即可.
#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("%lldn",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;
}
根据 $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; }
考虑朴素 DP
令 $mathrm{f[i][j]}$ 表示 DP 到 $mathrm{i}$, 分了 $mathrm{j}$ 段的最小值.
考虑用线段树维护这个 DP.
每次维护右端点为 $mathrm{i}$ 时左端点的答案.
右端点向右移动时对应的就是一段区间加法，用线段树来维护即可.
以上是脚本宝典为你收集整理的Codeforces Round #721 (Div. 2)全部内容，希望文章能够帮你解决Codeforces Round #721 (Div. 2)所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。