cf1858 做题记录
A
题面
两个人肯定会先把 \(c\) 个轮流拿掉，最后比较谁走的回合多。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
void solve(){
int a,b,c;
read(a),read(b),read(c);
a+=c/2+c%2;
b+=c/2;
if(a>b){
puts("First");
}
else{
puts("Second");
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
B
题面
比 \(c\) 难的 \(b\)。
因为删去一个关键点，影响的区间只有前一个关键点到后一个关键点的区间，不被影响的有一段前缀和一段后缀，可以预处理出每个前缀和后缀的贡献，枚举删掉哪个关键点并计算总贡献，注意特殊处理 \(1\) 和 \(m\) 即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10,inf=1e18;
int n,m,d,pos[N],nxt[N],pre[N];
void solve(){
read(n),read(m),read(d);
for(int i=1;i<=m;i++){
read(pos[i]);
}
nxt[m]=(n-pos[m])/d+1;
for(int i=m-1;i;i--){
nxt[i]=nxt[i+1]+(pos[i+1]-pos[i]-1)/d+1;
}
if(pos[1]==1){
pre[1]=1;
}
else{
pre[1]=2+(pos[1]-2)/d;
}
for(int i=2;i<=m;i++){
pre[i]=pre[i-1]+(pos[i]-pos[i-1]-1)/d+1;
}
int ans=inf,num=0;
for(int i=1,sum;i<=m;i++){
if(i==1){
sum=nxt[2]+(pos[2]-2)/d+1;
}
else if(i<m){
sum=(pos[i+1]-pos[i-1]-1)/d+pre[i-1]+nxt[i+1];
}
else{
sum=pre[m-1]+(n-pos[m-1])/d;
}
if(ans>sum){
ans=sum;
num=1;
}
else if(ans==sum){
num++;
}
}
write_space(ans),write_endl(num);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
C
题面
类似于夕阳西下几时回，选完一个数 \(x\) 之后，如果 \(2x\) 没被选，那么选择 \(2x\)，此时 \(x\) 会作为 \(gcd\) 被选择，且以该策略操作后，所有小于等于 \(n/2\) 的数都会被选，显然最大。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
int n;
void solve(){
read(n);
set<int>s;
for(int i=1;i<=n;i++){
s.insert(i);
}
while(s.size()){
int x=*(s.begin());
while(x<=n){
write_space(x);
s.erase(x);
x*=2;
}
}
putchar('\n');
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
D
题面
枚举区间 \([l,r]\) 为最长的连续 \(1\) 的区间，记其修改了 \(x\) 次，那么我们要在 \([1,l-1]\cup [r+1,n]\) 中找到修改后最长的连续 \(0\) 区间 \([l',r']\)，记其修改了 \(y\) 次，且 \(x+y\le k\)。
记 \(pre_{i,j}\) 表示前缀 \([1,i]\) 中，修改次数最多为 \(j\) 的连续 \(0\) 区间的长度的最大值，\(bac_{i,j}\) 表示后缀 \([i,n]\) 中，修改次数最多为 \(j\) 的连续 \(0\) 区间的长度的最大值。\(s_i\) 表示前缀 \([1,i]\) 中的 \(1\) 的数量，枚举区间 \([i,j]\)，\(pre_{i,sum_j-sum_i}=i-j+1\)，做一下前缀后缀 \(\max\) 即可处理得到。随后便可以得到连续 \(1\) 区间的长度为 \(x\) 时，连续 \(0\) 区间的长度的最大值 \(mx_x\)，答案可以枚举得到。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3010,inf=1e9;
int n,m,sum[N],pre[N][N],bac[N][N],mx[N];
char s[N];
void solve(){
read(n),read(m);
for(int i=1;i<=n;i++){
s[i]=getchar();
while(s[i]!='0'&&s[i]!='1'){
s[i]=getchar();
}
sum[i]=sum[i-1]+s[i]-'0';
}
for(int i=0;i<=n+1;i++){
for(int j=0;j<=n;j++){
pre[i][j]=bac[i][j]=0;
}
}
for(int i=1;i<=n;i++){
for(int j=i-1;~j;j--){
pre[i][sum[i]-sum[j]]=i-j;
}
for(int j=0;j<=n;j++){
pre[i][j]=max(pre[i][j],pre[i-1][j]);
}
for(int j=1;j<=n;j++){
pre[i][j]=max(pre[i][j],pre[i][j-1]);
}
}
for(int i=n;i;i--){
for(int j=i;j<=n;j++){
bac[i][sum[j]-sum[i-1]]=j-(i-1);
}
for(int j=0;j<=n;j++){
bac[i][j]=max(bac[i][j],bac[i+1][j]);
}
for(int j=1;j<=n;j++){
bac[i][j]=max(bac[i][j],bac[i][j-1]);
}
}
for(int i=0;i<=n;i++){
mx[i]=-inf;
}
mx[0]=pre[n][m];
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
int cnt=(j-i+1)-(sum[j]-sum[i-1]);
if(cnt>m){
continue;
}
mx[j-i+1]=max(mx[j-i+1],max(pre[i-1][m-cnt],bac[j+1][m-cnt]));
}
}
for(int i=1;i<=n;i++){
int ans=0;
for(int j=0;j<=n;j++){
ans=max(ans,i*mx[j]+j);
}
write_space(ans);
}
putchar('\n');
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
E1
题面
离线特有做法，建操作树。
假设当前在 \(p\) 位置，一次加操作，相当于该点加一个儿子，权值为 \(x\)，并移动到儿子的位置。一次减操作相当于跳到 \(p\) 的 \(x\) 级祖先，对于撤销操作，可以记录每一次操作后的位置，撤销相当于回到上一次的位置。所有询问全部离线，最后一遍dfs找答案即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e6+10,Lg=20;
int n,f[N][Lg+5],stk[N],top,idx,val[N],buc[N],ans[N],cnt;
struct node{
int opt,val;
}p[N];
vector<int>e[N];
void query(int u){
if(u!=0){
if(!buc[val[u]]){
cnt++;
}
++buc[val[u]];
}
ans[u]=cnt;
for(auto v:e[u]){
query(v);
}
if(u!=0){
--buc[val[u]];
if(!buc[val[u]]){
cnt--;
}
}
}
void solve(){
read(n);
for(int i=1;i<=n;i++){
char opt=getchar();
while(opt!='+'&&opt!='-'&&opt!='!'&&opt!='?'){
opt=getchar();
}
if(opt=='+'){
p[i].opt=1;
read(p[i].val);
}
else if(opt=='-'){
p[i].opt=2;
read(p[i].val);
}
else if(opt=='!'){
p[i].opt=3;
}
else{
p[i].opt=4;
}
}
int pos=0;
stk[++top]=pos;
for(int i=1;i<=n;i++){
if(p[i].opt==1){
idx++;
e[pos].pb(idx);
val[idx]=p[i].val;
f[idx][0]=pos;
for(int i=1;i<=Lg;i++){
f[idx][i]=f[f[idx][i-1]][i-1];
}
pos=idx;
stk[++top]=pos;
}
else if(p[i].opt==2){
for(int j=Lg;j>=0;j--){
if(p[i].val>>j&1){
pos=f[pos][j];
}
}
stk[++top]=pos;
}
else if(p[i].opt==3){
pos=stk[--top];
}
else{
p[i].val=pos;
}
}
query(0);
for(int i=1;i<=n;i++){
if(p[i].opt==4){
write_endl(ans[p[i].val]);
}
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
E2
题面
不得不说，这题有了e1之后难度直线飙升，都往优化操作树上去了。
假定没有撤回操作，考虑维护这个序列。用一个set和树状数组维护每个数第一次出现的位置。令 \(len\) 表示当前序列的长度，答案为 \(1\sim len\) 的区间中第一次出现的数的数量。带个撤回操作就记一下操作前的状态即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e6+10,mx=1e6;
int q,len,a[N],c[N];
set<int>s[N];
namespace Fenwick_Tree{
int c[N];
int lowbit(int x){
return x&(-x);
}
void add(int pos,int val){
while(pos<=mx){
c[pos]+=val;
pos+=lowbit(pos);
}
}
int query(int pos){
int ans=0;
while(pos){
ans+=c[pos];
pos-=lowbit(pos);
}
return ans;
}
}
struct node{
int opt,x;
node (int _opt=0,int _x=0){
opt=_opt,x=_x;
}
};
vector<node>stk;
void solve(){
memset(a,-1,sizeof(a));
read(q);
while(q--){
char opt=getchar();
int x;
while(opt!='+'&&opt!='-'&&opt!='?'&&opt!='!'){
opt=getchar();
}
if(opt=='+'){
read(x);
len++;
if(a[len]!=-1){
if(s[a[len]].size()){
Fenwick_Tree::add(*s[a[len]].begin(),-1);
s[a[len]].erase(len);
}
if(s[a[len]].size()){
Fenwick_Tree::add(*s[a[len]].begin(),1);
}
}
stk.pb(node(1,a[len]));
a[len]=x;
if(s[x].size()){
Fenwick_Tree::add(*s[x].begin(),-1);
}
s[x].insert(len);
Fenwick_Tree::add(*s[x].begin(),1);
}
else if(opt=='-'){
read(x);
len-=x;
stk.pb(node(0,x));
}
else if(opt=='?'){
write_endl(Fenwick_Tree::query(len));
fflush(stdout);
}
else{
node lst=stk.back();
stk.pop_back();
if(lst.opt){
if(a[len]!=-1){
if(s[a[len]].size()){
Fenwick_Tree::add(*s[a[len]].begin(),-1);
s[a[len]].erase(len);
}
if(s[a[len]].size()){
Fenwick_Tree::add(*s[a[len]].begin(),1);
}
}
x=lst.x;
a[len]=x;
if(x!=-1){
if(s[x].size()){
Fenwick_Tree::add(*s[x].begin(),-1);
}
s[x].insert(len);
Fenwick_Tree::add(*s[x].begin(),1);
}
len--;
}
else{
len+=lst.x;
}
}
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}