Codeforces Round #569 (Div. 1)

川长思鸟来 2021-12-24 08:39 206阅读 0赞

[Codeforces Round \#569 (Div. 1)][Codeforces Round _569 _Div. 1]

## A Valeriy and Deque ##

考虑先走n-1步，那么走完了n-1步后最大的数一定就在最前面了，接下来的操作会让后面的n-1个数进入循环，那么对于一个询问\\(m\_i\\)，如果\\(m\_i<n-1\\)，那么直接回答即可，否则将\\(m\_i\\)对n-1取模，然后回答。

## B Tolik and His Uncle ##

构造题。

\\((1,1)\\rightarrow(n,m)\\rightarrow(1,2)\\rightarrow(n,m-1)\\rightarrow\\cdots\\rightarrow(n,1)\\rightarrow(2,1)\\rightarrow(n-1,m)\\rightarrow\\cdots\\)

## C Serge and Dining Room ##

考虑要求的实际上就是最大的x，满足价格大于x的菜的数目大于钱数大于x的人数。

那么这个问题就是单点修改，然后查询后缀和，这样很不好搞，于是变成前缀修改，单点查询，然后就可以在线段树上二分了。

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cctype> #define qmin(x,y) (x=min(x,y)) #define qmax(x,y) (x=max(x,y)) #define vic vector<int> #define vit vic::iterator #define pir pair<int,int> #define fr first #define sc second #define mp(x,y) make_pair(x,y) #define rsort(x,y) sort(x,y),reverse(x,y) using namespace std; inline char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; return getchar(); } template<class T> int read(T &ans) { ans=0;char ch=gc();T f=1; while(!isdigit(ch)) { if(ch==EOF) return -1; if(ch=='-') f=-1; ch=gc(); } while(isdigit(ch)) ans=ans*10+ch-'0',ch=gc(); ans*=f;return 1; } template<class T1,class T2> int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF; } template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF; } typedef long long ll; const int Maxn=1100000; const int inf=0x3f3f3f3f; int tl[Maxn<<2],tr[Maxn<<2],tn[Maxn<<2],bj[Maxn<<2]; int n,m,a[Maxn],b[Maxn],q,opt,x,y; #define lch (root<<1) #define rch (root<<1|1) void build(int root,int l,int r) { tl[root]=l,tr[root]=r; if(l==r) return ; int mid=l+r>>1; build(lch,l,mid); build(rch,mid+1,r); } inline void update(int root) { tn[root]=max(tn[lch],tn[rch]); } inline void abj(int root,int x) { tn[root]+=x; bj[root]+=x; } void pushdown(int root) { if(bj[root]) { abj(lch,bj[root]); abj(rch,bj[root]); bj[root]=0; } } void chang(int root,int x,int y) { int l=tl[root],r=tr[root],mid=l+r>>1; if(l==r) { tn[root]+=y; return ; } pushdown(root); if(x<=mid) { chang(lch,x,y); update(root); return ; } abj(lch,y); chang(rch,x,y); update(root); } int work(int root) { if(tl[root]==tr[root]) return tl[root]; pushdown(root); return work(tn[rch]>=1?rch:lch); } signed main() { // freopen("test.in","r",stdin); read(n,m); build(1,1,1000000); for(int i=1;i<=n;i++) { read(a[i]); chang(1,a[i],1); } for(int i=1;i<=m;i++) { read(b[i]); chang(1,b[i],-1); } read(q); for(int i=1;i<=q;i++) { read(opt,x,y); if(opt==1) { chang(1,a[x],-1); a[x]=y; chang(1,a[x],1); } else { chang(1,b[x],1); b[x]=y; chang(1,b[x],-1); } if(tn[1]>=1) printf("%d\n",work(1)); else puts("-1"); } return 0; }

## D Fedor Runs for President ##

考虑加上一条边会增加多少条简单路径，那么把这条边连接的两个点之间的链拎出来，树的形态就变成了一条链上每个点上挂着一颗树，那么答案就等于\\(n^2-\\sum\_isize\[i\]^2\\)。显然选的两个点一定是两个叶子，因为如果不是两个叶子，那么再继续往下走一定会更优。

考虑枚举选的两个点的lca，设\\(i\\)为当前枚举的lca的一个儿子，\\(f\_i\\)为\\(i\\)这个子树中叶子到\\(i\\)的链上的点除了链上的子树外的点的数目的平方的和的最小值。转移为\\(f\_\{root\}=\\min\_i \\\{f\_i+(size\[root\]-size\[i\])^2\\\}\\)。

现在来考虑统计答案，那么对于当前点的两个儿子\\(i,j\\)，其答案除了\\(f\_i+f\_j\\)外还有当前点的大小之和，即\\(f\_i+f\_j+(n-size\[i\]-size\[j\])^2\\)，展开一下有\\(n^2+(f\_i+size\[i\]^2-2\\cdot n\\cdot size\[i\])+(f\_j+size\[j\]^2-2\\cdot n\\cdot size\[j\])+2\\cdot size\[i\]\\cdot size\[j\]\\)，那么按照\\(size\\)排序后用单调栈处理即可。

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cctype> #define qmin(x,y) (x=min(x,y)) #define qmax(x,y) (x=max(x,y)) #define vic vector<int> #define vit vic::iterator #define pir pair<int,int> #define fr first #define sc second #define mp(x,y) make_pair(x,y) #define rsort(x,y) sort(x,y),reverse(x,y) using namespace std; inline char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; return getchar(); } template<class T> int read(T &ans) { ans=0;char ch=gc();T f=1; while(!isdigit(ch)) { if(ch==EOF) return -1; if(ch=='-') f=-1; ch=gc(); } while(isdigit(ch)) ans=ans*10+ch-'0',ch=gc(); ans*=f;return 1; } template<class T1,class T2> int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF; } template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF; } typedef long long ll; const int Maxn=1100000; const int inf=0x3f3f3f3f; int to[Maxn],nxt[Maxn],first[Maxn],tot=1; int n,m,u,v,d[Maxn],siz[Maxn]; ll f[Maxn],res; pair<ll,ll> q[Maxn],a[Maxn]; inline void add(int u,int v) { to[tot]=v; nxt[tot]=first[u]; first[u]=tot++; to[tot]=u; nxt[tot]=first[v]; first[v]=tot++; } inline ll sqr(ll x) { return x*x; } ll cal(pair<ll,ll> x,ll y) { return y*x.fr+x.sc; } void work(int root,int fa) { siz[root]=1,f[root]=1ll*n*n; for(int i=first[root];i;i=nxt[i]) if(to[i]!=fa) work(to[i],root),siz[root]+=siz[to[i]]; for(int i=first[root];i;i=nxt[i]) if(to[i]!=fa) qmin(f[root],f[to[i]]+sqr(siz[root]-siz[to[i]])); int tot=0; for(int i=first[root];i;i=nxt[i]) if(to[i]!=fa) a[++tot]=mp(siz[to[i]],to[i]); if(!tot) { f[root]=1; return ; } sort(a+1,a+tot+1); int top=0; q[++top]=mp(2ll*siz[a[1].sc],f[a[1].sc]+sqr(siz[a[1].sc])-2ll*n*siz[a[1].sc]); for(int i=2;i<=tot;i++) { while(top&&cal(q[top-1],a[i].fr)<cal(q[top],a[i].fr)) top--; qmin(res,cal(q[top],a[i].fr)+f[a[i].sc]+sqr(siz[a[i].sc])-2ll*n*siz[a[i].sc]+1ll*n*n); pair<ll,ll> temp=mp(2ll*siz[a[i].sc],f[a[i].sc]+sqr(siz[a[i].sc])-2ll*n*siz[a[i].sc]); q[++top]=temp; } } signed main() { // freopen("test.in","r",stdin); read(n); if(n==2) { puts("2"); return 0; } for(int i=1;i<n;i++) { read(u,v); d[u]++,d[v]++; add(u,v); } int rt; for(int i=1;i<=n;i++) if(d[i]>1) { rt=i; break; } res=1ll*n*n; work(rt,rt); ll ans=1ll*n*(n-1); ans+=1ll*n*n-res; printf("%I64d\n",ans/2); return 0; }

## E Alesya and Discrete Math ##

看到了题目，满脸的不可做，（于是我们看一下题解。所以我就把题解翻译一下就好了。

考虑朴素做法，不失一般性，我们设n为偶数，那么显然我们可以用二分找到使得\\(f\_i(x\_i)=\\frac\{L\}\{2\}\\)的\\(x\_i\\)，那么按照\\(x\_i\\)从大到小排序并重新编号，可以发现这个一定是对的。同时这个问题也被分成了两个规模为\\(\\frac\{n\}\{2\}\\)的子问题，那么复杂度\\(T(n)=2T(\\frac\{n\}\{2\})+O(n\\log w)\\ ,\\ T(n)=O(n\\log n\\log w)\\)，这个是过不了的，所以考虑优化这个过程。

我们要把它分成两个子问题，所以可以随机一个选一个函数\\(f\_i\\)，二分出上面的\\(x\_i\\)，那么把\\(f\_j(x\_i)>\\frac\{L\}\{2\}\\)的函数放在左边，反之放在右边，如果等于的话就先单独记出来，能填到左边就填到左边，直到左边放到\\(\\frac\{n\}\{2\}\\)个数，然后剩下的丢到右边。这时如果左边恰有\\(\\frac\{n\}\{2\}\\)个数，那么完成，否则如果少于，就向右边找，否则向左边找。这个复杂度是\\(O(n\\log n+n\\log w)\\)。

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cctype> #define qmin(x,y) (x=min(x,y)) #define qmax(x,y) (x=max(x,y)) #define vic vector<int> #define vit vic::iterator #define pir pair<int,int> #define fr first #define sc second #define mp(x,y) make_pair(x,y) #define rsort(x,y) sort(x,y),reverse(x,y) using namespace std; inline char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; return getchar(); } template<class T> int read(T &ans) { ans=0;char ch=gc();T f=1; while(!isdigit(ch)) { if(ch==EOF) return -1; if(ch=='-') f=-1; ch=gc(); } while(isdigit(ch)) ans=ans*10+ch-'0',ch=gc(); ans*=f;return 1; } template<class T1,class T2> int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF; } template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF; } typedef long long ll; const int Maxn=1100; const int inf=0x3f3f3f3f; int a[Maxn],b[Maxn],c[Maxn],tims; ll n,L,v; pair<ll,ll> ans[Maxn]; ll query(ll a,ll b) { printf("? %I64d %I64d\n",a,b); fflush(stdout); ll ans; read(ans); // ans=b; // tims++; return ans; } ll find(int x,ll k,ll l,ll r) { ll mid=l+r>>1; while(1) { ll y=query(x,mid); if(y==k) return mid; if(y<k) l=mid+1; else r=mid-1; mid=l+r>>1; } } void kth(int l,int r,int k,ll ql,ll qr) { if(l==r) return ; int x=rand()%(r-l+1)+l; ll y=find(a[x],(L/n)*k,ql,qr); int mid=k-l+1; int l1=l-1,l2=r+1,l3=0; c[++l3]=a[x]; for(int i=l;i<=r;i++) { if(i==x) continue; ll sxz=query(a[i],y); if(sxz<(L/n)*k) b[--l2]=a[i]; if(sxz==(L/n)*k) c[++l3]=a[i]; if(sxz>(L/n)*k) b[++l1]=a[i]; } while(l1<k&&l3) b[++l1]=c[l3--]; if(l1==k) { v=y; while(l3) b[--l2]=c[l3--]; for(int i=l;i<=r;i++) a[i]=b[i]; return ; } if(l1<k) { for(int i=l;i<=r;i++) a[i]=b[i]; kth(l1+1,r,k,ql,qr); return ; } while(l3) b[--l2]=c[l3--]; for(int i=l;i<=r;i++) a[i]=b[i]; kth(l,l1,k,ql,qr); } void solve(int l,int r,ll ql,ll qr) { if(l==r) { ans[a[l]]=mp(ql,qr); return ; } int mid=l+r>>1; kth(l,r,mid,ql,qr); ll x=v; solve(l,mid,ql,x); solve(mid+1,r,x,qr); } signed main() { // freopen("test.in","r",stdin); // freopen("out","w",stdout); read(n,L); for(int i=1;i<=n;i++) a[i]=i; solve(1,n,0,1000000000000000000ll); puts("!"); for(int i=1;i<=n;i++) printf("%I64d %I64d\n",ans[i].fr,ans[i].sc); fflush(stdout); // printf("%d\n",tims); return 0; }

转载于:https://www.cnblogs.com/shanxieng/p/11077328.html

[Codeforces Round _569 _Div. 1]: http://codeforces.com/contest/1179