当前位置：首页 > news >正文

10.30

news 2024/10/31 21:38:47

CF2000H Ksyusha and the Loaded Set

*2200 ds

题目要求序列中满足[x,x+k-1]都为出现的x的最小值，序列动态修改。

过道这种题，比较容易想到用数据结构维护。维护直接做即可

用1表述输出现过，0表示没出现过，然后边将题目要求的转化为求最小下表x满足以x为开头的全0序列长度至少为k。在线段树上维护区间最长全0序列，查询时进行线段树二分（~~应该是叫这个吧~~）即可。

注意到

·（1）建树键到4e6是因为题目中出现的最大值为2e6，若在1~max都找不到答案，那么一等可以在max~4e6中找到。（2）不要每做一次询问就建一次树，不然会T到飞起，用set维护出现过的数，在操作完后删除即可.

#include<bits/stdc++.h>
#define N 4000005
using namespace std;
int n,m,x,T;
char op;
set<int> s;
struct node{ int l,r,si,l0,r0,le; }t[N<<2];
int read()
{int f=0; char c=getchar(); int s=0;for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) s=(s<<1)+(s<<3)+(c^48);if(f) s=-s; return s;
}
void push_up(int rt)
{t[rt].le=max(max(t[rt<<1].le,t[rt<<1|1].le),t[rt<<1].r0+t[rt<<1|1].l0);t[rt].l0=t[rt<<1].l0; t[rt].r0=t[rt<<1|1].r0;if(t[rt].l0==t[rt<<1].si) t[rt].l0+=t[rt<<1|1].l0;if(t[rt].r0==t[rt<<1|1].si) t[rt].r0+=t[rt<<1].r0;
}
void build(int rt,int l,int r)
{t[rt].l=l,t[rt].r=r,t[rt].si=r-l+1;if(l==r) { t[rt].l0=t[rt].r0=t[rt].le=1; return; }int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r);push_up(rt);
}
void update(int rt,int x,int y)
{if(t[rt].l==t[rt].r) { t[rt].l0=t[rt].r0=t[rt].le=(y==-1); return; }int mid=(t[rt].l+t[rt].r)>>1;if(x<=mid) update(rt<<1,x,y); else update(rt<<1|1,x,y);push_up(rt);
}
int query(int rt,int x)
{if(t[rt].si==x) return t[rt].l;else if(t[rt<<1].le>=x) return query(rt<<1,x);else if(t[rt<<1].r0+t[rt<<1|1].l0>=x) return t[rt<<1].r-t[rt<<1].r0+1;else return query(rt<<1|1,x);
}
void sol()
{scanf("%d",&n);for(int i=1;i<=n;i++) x=read(),update(1,x,1),s.insert(x);scanf("%d",&m); getchar();while(m--){op=getchar(); x=read();if(op=='-') update(1,x,-1),s.erase(x);if(op=='+') update(1,x,1),s.insert(x);if(op=='?') cout<<query(1,x)<<" ";} cout<<"\n";for(auto v:s) update(1,v,-1); s.clear();
}
int main()
{build(1,1,4000000);scanf("%d",&T); while(T--) sol();return 0;
}

CF1986E Beautiful Array

*1700 math

每次可以通过操作一次使一个数+k，求最小的操作次数使得序列重排能够成回文

我们设a和b在操作以后对称，（即若a在位置i，则b在位置n-i+1），切钦定 $a\geq b$

则一定有 $a+kx=b+yk$ ，代价为x+y

然后通过移项得 $a-b=k(y-x)$

发现当且仅当 $(a-b)mod k=0$ 时才能成立，

又因为 (a-b)%k=(a%k-b%k+k)%k,所以（a-b）%k=0等价于a%k=b%k,

所以只需要将%k同余的分到一组进行即可

然后再进行分类讨论，现将同组值按大小排序，当数量为偶数是两两匹配一定最优，当两数相同可以把两个数删掉（放在对称的位置上）。当数量为奇数时我们枚举将哪个数放在最中间的位置，两端有前缀和+后缀和优化即可，还有就是要记录一下数量为奇数的数量，若这个数量>1,则一定没有满足情况。

细节有点多，注意边界）

#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int n,k,T,t,tt,id,cnt,ans,sum,a[N],b[N],c[N];
map<int,int> ma;
vector<int> ve[N];
void sol()
{scanf("%lld%lld",&n,&k); ma.clear();for(int i=1;i<=n;i++) scanf("%lld",a+i);sort(a+1,a+1+n); t=cnt=ans=id=0; a[n+1]=0;for(int i=1;i<=n;i++) if(a[i]==a[i+1]) i++; else b[++t]=a[i],c[t]=a[i]%k;if(t<=1) { cout<<"0\n"; return; }sort(c+1,c+1+t); tt=unique(c+1,c+1+t)-c-1;for(int i=1;i<=tt;i++) ma[c[i]]=i,ve[i].clear();for(int i=1;i<=t;i++) ve[ma[b[i]%k]].push_back(b[i]);for(int i=1;i<=tt;i++){int x=ve[i].size();if(x%2) cnt++,id=i;else { for(int j=0;j<x-1;j+=2) ans+=(ve[i][j+1]-ve[i][j])/k; }}if(cnt>1) { cout<<"-1\n"; return; }if(id==0 || (int)ve[id].size()==1) { cout<<ans<<"\n"; return; }memset(b,0,sizeof b); memset(c,0,sizeof c);t=ve[id].size()-1;b[0]=(ve[id][1]-ve[id][0])/k; c[t]=(ve[id][t]-ve[id][t-1])/k;// b[t]=1e9,c[0]=1e9;for(int i=2;i<t;i+=2) b[i]=b[i-2]+(ve[id][i+1]-ve[id][i])/k;for(int i=t-2;i>0;i-=2) c[i]=c[i+2]+(ve[id][i]-ve[id][i-1])/k;sum=min(b[t-2],c[2]);for(int i=2;i<t;i+=2) sum=min(sum,b[i-2]+c[i+2]);cout<<ans+sum<<"\n";
}
signed main()
{scanf("%lld",&T);while(T--) sol();return 0;
}

CF1793E Velepin and Marketing

2600* dp ###

（被dalao同学拉去做的）

第 i 年出版 ki 本新书，同时有 n 名读者，每年会从 ki 本新书中选一本阅读。如果读者 j 发现有不低于 aj 个人（包括本身）与他阅读同一本新书，他会感到开心。求开心的读者数量最大值。

不难发现，分组越多，贡献越小，所以我们考虑枚举贡献，对于每一种贡献确定分组的上限。于是我们肯定贪心的选a更小的，这样更易满足，考虑对a排序，取一段前缀，后面的都一个人一本。

我们将一本书视为一组，设f[i]表示前i个人都开心可以有的最多书的数量，g[i]表示只取前i个且前i个都快乐的最大组数。

那么当 $a[i]>i$ 则前a[i]个数都必须一组， $f[i]=n-a[i]+1$ （n-a[i]表示剩下的人一人一本，1表是当前这组）；当 $a[i]\leqslant i$ 时 $f[i]=max(f[i-1],g[i-a[i]]+1+n-i)$ （f[i-1]表示和前一个放一组，g[i-a[i]]+1表示自己单独成一组，在这组中，因为a[i]是最大的，连a[i]都满足，则其余的一定满足），同时g[i]=g[a[i]]+1； g[i]还要前缀去max；

得到f后用指针维护，得到ans数组，询问是直接输出即可，但是注意到当 $k>n-a[1]+1$ 时答案就都为0了。

#include<bits/stdc++.h>
#define N 300005
using namespace std;
int n,q,m,x,y,r,a[N],f[N],g[N],ans[N];
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",a+i); sort(a+1,a+1+n);for(int i=1;i<=n;i++){if(a[i]<=i) f[i]=g[i-a[i]]+1+n-i,g[i]=g[i-a[i]]+1;else f[i]=n-a[i]+1,g[i]=0;g[i]=max(g[i-1],g[i]);}r=n-a[1]+1;for(int i=1;i<=n;i++){if(f[i]==f[i+1]) continue;while(r>f[i+1]) ans[r--]=i;}scanf("%d",&q);while(q--) scanf("%d",&x),cout<<ans[x]<<"\n";return 0;
}

CF1991D Prime XOR Coloring

1900* ### 结论题这场被锐评为糖场

有一个 𝑛 个顶点的无向图，顶点编号从 1 到 𝑛 。两个顶点 𝑢,𝑣 之间有边当且仅当u xor v 为质数。

求出一种染色方案，使得有边相连的点不同色，求颜色数最少，输出颜色数和方案。

我们对于节点i染上 $(i-1)Mod 4+1$ 这种颜色，那么对于 $i\equiv j(mod 4)$ , $i\bigoplus j \equiv 0(mod 4)$ (将余数异或掉了），而四的倍数一定不为质数，所以满足条件。然后根据阳历，对于n<6的进行特判即可。

#include<bits/stdc++.h>
using namespace std;
int n,T;
int main()
{scanf("%d",&T);while(T--){scanf("%d",&n);if(n==1) cout<<"1\n1\n";if(n==2) cout<<"2\n1 2\n";if(n==3) cout<<"2\n1 2 2 \n";if(n==4) cout<<"3\n1 2 2 3\n";if(n==5) cout<<"3 1 2 2 3 3\n";if(n>=6) { cout<<"4\n"; for(int i=1;i<=n;i++) cout<<(i-1)%4+1<<" "; cout<<"\n"; }}return 0;
}

CF1991F Triangle Formation

2200* ### 被锐评为糖场的糖题

给定一个序列，每次询问一个区间，求出是否可以在区间中取出6个数组成2个三角形。

首先我们考虑序列若形如1,1,2,3,5,8,13....这样是不能形成三角形的，但是这样数字增长的非常快，因为a[i]<=1e9,所以当len>=45时一定存在一定三角形，同理当len>=48时一定存在2个三角形。然后我们将r-l+1>=48的进行特判，剩下的的区间长度都非常小，暴力做即可。

感性理解一下在一般情况下，取连续的3个最优，于是我们统计区间内不交的连续3个数可以构成三角形的个数，若数量大于等于2，则输出YES。否则还有一种情况例如 2 2 4 5 6 7 此时，我们应该取2 4 6 和2 5 7，在对这种情况进行判断，注意到这种情况，只会在相邻的6个数中出现，然后直接做即可。

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,m,l,r,t,fla,cnt,a[N],b[N],c[5];
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",a+i);while(m--){scanf("%d%d",&l,&r); t=fla=0;if(r-l+1>=48) { cout<<"YES\n"; continue; }for(int i=l;i<=r;i++) b[++t]=a[i];sort(b+1,b+1+t); cnt=0;for(int i=1;i+2<=t;i++)if(b[i]+b[i+1]>b[i+2]) cnt++,i+=2;if(cnt>=2) { cout<<"YES\n"; continue; }for(int i=1;i+5<=t;i++){for(int j=1;j<=5;j++)for(int k=j+1;k<=5;k++)if(b[i]+b[i+j]>b[i+k]){int x=0;for(int l=1;l<=5;l++)if(l!=k && l!=j) c[++x]=l;if(b[i+c[1]]+b[i+c[2]]>b[i+c[3]]){ fla=1; break; }}if(fla) break;}if(fla) cout<<"YES\n"; else cout<<"NO\n";}return 0;
}

查看全文

http://www.mrgr.cn/news/62744.html