XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Khamovniki

A. Ability Draft

記憶化搜索。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() {  }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m, S, g;
int f[100][1<<10];
int p[100];
int s[100][10];

int sm, bg;
int smp, bgp;
int smk[100];
int bgk[100];
int cal(int o, int sta)
{
	if(o > g)return 0;
	if(~f[o][sta])return f[o][sta];
	int x = p[o];
	int y = p[o + 1];
	f[o][sta] = -2e9;

	int canbig = ((sta >> x & 1) == 0);
	int cansml = S - (s[o - 1][x] - (canbig == 0)); //canbig == 0 means we picked ulti

	int sgn = (x / n == y / n) ? 1 : -1;
	if(canbig)
	{
		int add = bgk[++bgp];
		f[o][sta] = max(sgn * cal(o + 1, sta | 1 << x) + add, f[o][sta]);
		--bgp;
	}
	if(cansml)
	{
		int add = smk[++smp];
		f[o][sta] = max(sgn * cal(o + 1, sta) + add, f[o][sta]);
		--smp;
	}
	return f[o][sta];
}
int main()
{
	while(~scanf("%d%d",&n, &S))
	{
		m = n * 2;
		g = m * (S + 1);
		for(int i = 1; i <= g; ++i)
		{
			scanf("%d", &p[i]); --p[i];
			for(int j = 0; j < m; ++j)
			{
				s[i][j] = s[i - 1][j] + (j == p[i]);
			}
		}
		scanf("%d", &sm);
		for(int i = 1; i <= sm; ++i)scanf("%d", &smk[i]);
		sort(smk + 1, smk + sm + 1);
		reverse(smk + 1, smk + sm + 1);
		scanf("%d", &bg);
		for(int i = 1; i <= bg; ++i)scanf("%d", &bgk[i]);
		sort(bgk + 1, bgk + bg + 1);
		reverse(bgk + 1, bgk + bg + 1);

		smp = bgp = 0;
		MS(f, -1);
		printf("%d\n", cal(1, 0)*((p[1]/n==0)?1:-1));
	}
	return 0;
}

/*
【trick&&吐槽】
1 1
1 2 2 1
2
5 3
2
7 2

1 2
2 1 1 2 2 1
4
4 8 8 9
2
6 7
(ans = 2)

2 1
1 3 4 2 2 4 3 1
6
1 4 4 8 9 11
5
14 11 10 8 5

【題意】


【分析】


【時間復雜度&&優化】


*/

B. Short Random Problem

積分DP。

C. Block, Stock and Two Smoking Galaxy Notes

枚舉領導者$S$，它需要滿足度數至少為$\frac{n}{2}$。

枚舉完領導后，將和$S$認識和不認識的分成兩組二分圖匹配即可。

時間復雜度$O(m^2)$。

#include<cstdio>
#include<cstdlib>
using namespace std;
const int N=1010,M=10010;
int n,m,i,e[M][2],g[N],v[M],nxt[M],ed,f[N],b[N],T,right[N],deg[N];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
bool find(int x){
	for(int i=g[x];i;i=nxt[i])if(b[v[i]]<T){
		b[v[i]]=T;
		if(!f[v[i]]||find(f[v[i]]))return f[v[i]]=x,1;
	}
	return 0;
}
void solve(int S){
	int i;
	for(i=1;i<=n;i++)right[i]=g[i]=0;
	ed=0;
	for(i=1;i<=m;i++){
		if(e[i][0]==S)right[e[i][1]]=1;
		if(e[i][1]==S)right[e[i][0]]=1;
	}
	for(i=1;i<=m;i++){
		if(e[i][0]!=S&&!right[e[i][0]]&&right[e[i][1]])add(e[i][0],e[i][1]);
		if(e[i][1]!=S&&!right[e[i][1]]&&right[e[i][0]])add(e[i][1],e[i][0]);
	}
	for(i=1;i<=n;i++)f[i]=b[i]=0;
	T=0;
	for(i=1;i<=n;i++){
		if(right[i]||i==S)continue;
		T++;
		if(!find(i))return;
	}
	puts("Yes");
	int cnt=0;
	for(i=1;i<=n;i++)if(right[i])cnt++;
	printf("%d %d\n",S,cnt);
	for(i=1;i<=n;i++)if(right[i]){
		printf("%d ",i);
		if(!f[i])f[i]=-1;
		printf("%d\n",f[i]);
	}
	exit(0);
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)scanf("%d%d",&e[i][0],&e[i][1]),deg[e[i][0]]++,deg[e[i][1]]++;
	for(i=1;i<=n;i++)if(deg[i]>=n/2-5)solve(i);
	puts("No");
}
/*
5 4
1 2
2 3
3 4
4 5
*/

D. Lunch Queue

用一棵平衡樹$S$維護整個隊列，再對每個隊伍用一棵平衡樹$T_i$維護。

那么對于新來的一個人，先在$S$中找出滿足距離限制最緊的那個點$x$，再在$T_{c_i}$中查找$x$之后最靠前的點作為插隊位置。

瓶頸在于最后一步比較兩個人在$S$中的前后關系，將$S$用替罪羊樹維護，同時維護動態標號即可$O(1)$比較。

時間復雜度$O(n\log n)$。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=400010;
typedef unsigned long long ll;
const ll inf=1ULL<<63;
const double A=0.8;
ll tl[N],tr[N],tm[N];
int size[N],son[N][2],f[N],tot,root;
int id[N],cnt;
int n,i,a[N];
void dfs(int x){
  if(son[x][0])dfs(son[x][0]);
  id[++cnt]=x;
  if(son[x][1])dfs(son[x][1]);
}
int build(int fa,int l,int r,ll a,ll b){
  int mid=(l+r)>>1,x=id[mid];
  f[x]=fa;son[x][0]=son[x][1]=0;size[x]=1;tl[x]=a;tr[x]=b;tm[x]=(a+b)>>1;
  if(l==r)return x;
  if(l<mid)size[x]+=size[son[x][0]=build(x,l,mid-1,a,tm[x])];
  if(r>mid)size[x]+=size[son[x][1]=build(x,mid+1,r,tm[x],b)];
  return x;
}
inline int kth(int k){
  if(k<1)return 0;
  int x=root,rank;
  while(1){
    rank=size[son[x][0]]+1;
    if(k==rank)return x;
    if(k<rank)x=son[x][0];else k-=rank,x=son[x][1];
  }
}
inline int rebuild(int x){
  cnt=0;
  dfs(x);
  return build(f[x],1,cnt,tl[x],tr[x]);
}
inline void fix(int x){
  int deep=1,z=x;
  size[x]++;
  while(f[z])size[z=f[z]]++,deep++;
  if(deep<log(tot)/log(1/A))return;
  while((double)size[son[x][0]]<A*size[x]&&(double)size[son[x][1]]<A*size[x])x=f[x];
  if(!x)return;
  if(x==root){root=rebuild(x);return;}
  int y=f[x],b=son[y][1]==x,now=rebuild(x);
  son[y][b]=now;
}
inline void ins(int A,int B,int x){
  if(!root){
    root=size[1]=1;
    tr[1]=inf;
    tm[1]=inf>>1;
    return;
  }
  while(1){
    if(!son[A][B]){
      son[A][B]=x;
      f[x]=A;
      if(!B){
        tl[x]=tl[A];
        tr[x]=tm[A];
      }else{
        tl[x]=tm[A];
        tr[x]=tr[A];
      }
      tm[x]=(tl[x]+tr[x])>>1;
      break;
    }
    A=son[A][B];
  }
  fix(x);
}
inline void insd(int A,int B,int x){
  if(!son[A][B]){
    son[A][B]=x;
    f[x]=A;
    if(!B){
      tl[x]=tl[A];
      tr[x]=tm[A];
    }else{
      tl[x]=tm[A];
      tr[x]=tr[A];
    }
    tm[x]=(tl[x]+tr[x])>>1;
    fix(x);
    return;
  }
  ins(son[A][B],B^1,x);
}
void show(int x){
  if(son[x][0])show(son[x][0]);
  printf("%d ",x);
  if(son[x][1])show(son[x][1]);
}
namespace DS{
int root[N],son[N][2],f[N];
inline void rotate(int x){
  int y=f[x],w=son[y][1]==x;
  son[y][w]=son[x][w^1];
  if(son[x][w^1])f[son[x][w^1]]=y;
  if(f[y]){
    int z=f[y];
    if(son[z][0]==y)son[z][0]=x;
    else if(son[z][1]==y)son[z][1]=x;
  }
  f[x]=f[y];son[x][w^1]=y;f[y]=x;
}
inline void splay(int x){
  while(f[x]){
    int y=f[x];
    if(f[y]){if((son[f[y]][0]==y)^(son[y][0]==x))rotate(x);else rotate(y);}
    rotate(x);
  }
}
inline void insert(int&x,int y){
  if(!x){x=y;return;}
  int z=x;
  while(1){
    int b=tm[y]>tm[z];
    if(son[z][b])z=son[z][b];
    else{
      son[z][b]=y;
      f[y]=z;
      break;
    }
  }
  splay(x=y);
}
int ask(int&o,int y){
  int t=0,z=0,x=o;
  while(x){
    z=x;
    if(tm[x]>tm[y]){
      t=x;
      x=son[x][0];
    }else{
      x=son[x][1];
    }
  }
  if(z)splay(o=z);
  return t;
}
}
int main(){
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    int x,dis;
    scanf("%d%d",&x,&dis);
    a[i]=x;
    if(i==1)ins(0,0,i);
    else{
      int y=kth(i-dis-1);
      if(a[y]==x)insd(y,1,i);
      else{
        int z=DS::ask(DS::root[x],y);
        if(z)insd(z,0,i);
        else ins(root,1,i);
      }
    }
    DS::insert(DS::root[x],i);
  }
  show(root);
}

E. Oneness

$ans=\lfloor\frac{n}{11}\rfloor+\lfloor\frac{n}{111}\rfloor+\lfloor\frac{n}{1111}\rfloor+...$。

令$N=9n$，則$ans=\lfloor\frac{N}{99}\rfloor+\lfloor\frac{N}{999}\rfloor+\lfloor\frac{N}{9999}\rfloor+...$。

對于整數部分FFT計算答案，對于小數部分用實數近似計算即可。

時間復雜度$O(|n|\log |n|)$。

F. Shuffle

對于置換中的每個循環，通過KMP求出所有可能的匹配位置，它們必然是一個等差數列。

那么對于所有循環分別列同余方程，然后擴展歐幾里得求解即可。

時間復雜度$O(n)$。

#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef int ll;
const int N=1000010;
int n,i,j,p[N],vis[N],q[N];
char a[N],b[N],c[N],S[N],T[N];
int nxt[N],w[N*4];
int ans=1;
int _a[N],_b[N],tot;
namespace NT{
int flag=1;
ll k=1,m,a,r,d,x,y;
ll exgcd(ll a,ll b,ll&x,ll&y){
	if(!b)return x=1,y=0,a;
	ll d=exgcd(b,a%b,x,y),t=x;
	return x=y,y=t-a/b*y,d;
}
inline void add(ll a,ll r){
	if(r>=a)while(1);
	r%=a;
	if(!flag)return;
	d=exgcd(k,a,x,y);
	if((r-m)%d){flag=0;return;}
	x=(x*(r-m)/d+a/d)%(a/d),y=k/d*a,m=((x*k+m)%y)%y;
	if(m<0)m+=y;
	k=y;
}
void write(ll x){
	if(x>=10)write(x/10);
	int t=x%10;
	printf("%d",t);
}
void show(){
	if(flag)write(m);
	else puts("-1");
}
}
inline void solve(int len){
	int i,j,k,cnt=0;
	for(i=1;i<=len;i++)T[i]=b[q[i]],S[i]=a[q[i]];
	//printf("len=%d\n",len);
	//for(i=1;i<=len;i++)putchar(T[i]);puts("");
	//for(i=1;i<=len;i++)putchar(S[i]);puts("");
	for(nxt[1]=j=0,i=2;i<=len;nxt[i++]=j){
		while(j&&S[j+1]!=S[i])j=nxt[j];
		if(S[j+1]==S[i])j++;
	}
	//for(i=1;i<=len;i++)printf("nxt[%d]=%d\n",i,nxt[i]);
	for(i=1,j=0,k=1;i<=len*4;i++){
		while(j&&S[j+1]!=T[k])j=nxt[j];
		if(S[j+1]==T[k]){
			j++;
			if(j==len){
				w[++cnt]=i-len;
				j=nxt[j];
				//printf("find %d\n",i);
			}
		}
		k++;
		if(k>len)k=1;
	}
	if(!cnt){
		puts("-1");
		exit(0);
	}
	if(cnt<2)while(1);
	for(i=2;i<=cnt;i++)if(w[i]-w[i-1]!=w[2]-w[1])while(1);
	//printf("per=%d occ=%d\n",w[2]-w[1],w[1]);
	NT::add(w[2]-w[1],w[1]);
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main(){
	scanf("%s%s",a+1,b+1);
	n=strlen(a+1);
	for(i=1;i<=n;i++){
		int x;
		if(i<=n/2)x=i*2-1;
		else x=i*2-n;
		//printf("! %d %d\n",i,x);
		p[x]=i;
	}
	for(i=1;i<=n;i++)if(!vis[i]){
		int cnt=0;
		for(j=i;!vis[j];j=p[j])vis[j]=1,q[++cnt]=j;
		//for(j=1;j<=cnt;j++)printf("%d ",q[j]);puts("");
		solve(cnt);
	}
	NT::show();
}
/*
aaababbbbbbabbbbab
aabbabbababbbabbbb


babaaabbaa
bbaaaababa
*/

G. Piecewise Linearity

按題意反解出每個函數即可，精度可以取模控制，不過使用__float128也可以通過全部數據。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() {  }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n;
double xx[N], yy[N];
__float128 x[N], y[N], v[N], k[N];
const double EPS = 1e-9;
__float128 fabs(__float128 x)
{
	return x >= 0 ? x : -x;
}
bool same(__float128 x, __float128 y)
{
	x -= y;
	return x <= EPS && x >= -EPS;
}
int main()
{
	while(~scanf("%d",&n))
	{
		for(int i = 1; i <= n + 1; ++i)
		{
			scanf("%lf%lf", &xx[i], &yy[i]);
			x[i] = xx[i];
			y[i] = yy[i];
		}
		__float128 sum = 0;
		__float128 yy = 0;
		for(int i = 1; i <= n; ++i)
		{
			k[i] = (y[i + 1] - y[i]) / (x[i + 1] - x[i]);
			if(i >= 2)
			{
				v[i] = (k[i] - k[i - 1]) / 2;
				sum += v[i];
				yy += v[i] * fabs(x[1] - x[i]);
			}
		}
		if(!same(sum, k[n]) || !same(-sum, k[1]) || !same(yy, y[1]))
		{
			puts("No");
		}
		else 
		{
			puts("Yes");
		}
	}
	return 0;
}

/*
【trick&&吐槽】
2
-1 2
1 0
2 1

3
-3 -1
-1 -1
1 1
4 1

3
-3 1
-2 0
0 1
1 1

【題意】


【分析】


【時間復雜度&&優化】


*/

H. Sketch

貪心將原序列復制下來，然后構造遞減數列，注意特判原序列非法的情況。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() {  }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 3e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m, k;
int a[N], b[N];

int main()
{
	while(~scanf("%d%d%d", &k, &n, &m)){
        a[0] = 1;
        for(int i = 1; i <= k; i ++) {
            scanf("%d", &a[i]);
            if(a[i] == -1){
                a[i] = a[i - 1];
            }
        }
        int flag = 1;
        for(int i = 2; i <= k; i ++){
            if(a[i] < a[i - 1]) flag = 0;
        }
        if(k > n || !flag){
            puts("-1");
            continue;
        }
        int rst = n - k, o = 0;
        for(int i = 1; i <= k; i ++){
            int x = m;
            while(rst > 0){
                if(x == a[i]) break;
                b[++ o] = x --;
                rst --;
            }
            b[++ o] = a[i];
        }
        /*
        if(rst){
            int x = b[o] - 1;
            while(rst > 0){
                if(x == 0) break;
                b[++ o] = x --;
                rst --;
            }
        }
        */
        if(rst){
            puts("-1");
        }
        else{
            for(int i = 1; i <= n; i ++) printf("%d ", b[i]);
            puts("");
        }
	}
	return 0;
}

/*
【trick&&吐槽】


【題意】


【分析】


【時間復雜度&&優化】


*/

I. $\leq$ or $\geq$

最優策略：將元素個數為$k$的棧的棧頂元素的權重設置為$2^{k-1}$，然后取加權中位數。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() {  }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;

int n, k, x;
int a[N], b[N];
char s[10];
int rst[N];
int w[20];
typedef pair<int,int>P;
P q[N];
LL pre[N][2],suf[N][2];
int main()
{
    w[1]=1;
    w[2]=2;
    w[3]=4;
    w[4]=8;
    w[5]=16;
    w[6]=32;
    w[7]=64;
    w[8]=128;
    w[9]=256;
    w[10]=512;
	while(~scanf("%d%d",&n, &k))
	{
	    for(int i = 1; i <= n; i ++) rst[i] = k;
	    while(1){
            int num = 0;
            int mx=0;
            for(int i=1;i<=n;i++)mx=max(mx,rst[i]);
            for(int i = 1; i <= n; i ++){
                scanf("%d", &b[i]);
                if(b[i])q[++num]=P(b[i],w[rst[i]]);
            }
            sort(q + 1, q + num + 1);
            LL best=~0ULL>>1;
            int pos=1;
            for(int i=1;i<=num;i++){
            	pre[i][0]=pre[i-1][0]+1LL*q[i].first*q[i].second;
            	pre[i][1]=pre[i-1][1]+q[i].second;
			}
			suf[num+1][0]=suf[num+1][1]=0;
			for(int i=num;i;i--){
            	suf[i][0]=suf[i+1][0]+1LL*q[i].first*q[i].second;
            	suf[i][1]=suf[i+1][1]+q[i].second;
			}
			for(int i=1;i<=num;i++){
				LL now=1LL*q[i].first*pre[i][1]-pre[i][0];
				now+=suf[i][0]-1LL*q[i].first*suf[i][1];
				if(now<best)best=now,pos=i;
			}
			int y=q[pos].first;
            printf("%d\n", y);
            fflush(stdout);
            scanf("%s", s);
            if(s[0] == 'E'){
                return 0;
            }
            else{
                for(int i = 1; i <= n; i ++){
                    if(s[0] == '<' && b[i] <= y){
                        rst[i] --;
                    }
                    else if(s[0] == '>' && b[i] >= y){
                        rst[i] --;
                    }
                }
            }
	    }
	}
	return 0;
}

/*
【trick&&吐槽】


【題意】


【分析】


【時間復雜度&&優化】


*/

J. Stairways

設$pre[i]=\max(a[1..i])$，則對于任意一個前綴$i$來說，兩個子序列必有一個的最大值為$pre[i]$，設$f[i][j]$表示考慮前綴$i$，除了$pre[i]$之外另一個子序列最大值為$j$時的最小代價，考慮如何從$f[i-1][]$轉移到$f[i][]$。

若$a[i]=pre[i]$，那么顯然將它歸到較大一側最優，故$f[i][j]=f[i-1][j]+a[i]$，只需要把答案加上$a[i]$即可。

否則$a[i]<pre[i]$，那么假設它不作為最大值，則對于$[a[i],pre[i]]$的$j$，有$f[i][j]=f[i-1][j]+j$，對于$[0,a[i])$的$j$，有$f[i][j]=f[i-1][j]+pre[i]$。

而如果它作為最大值，則有$f[i][a[i]]=\min(f[i-1][0..a[i]])+a[i]$。

故需要一個數據結構維護$f[j]$，支持區間加上一個數，區間每個位置$j$加上$j$，以及區間查詢最小值，單點修改。

將$f$分塊，每塊維護凸殼和標記即可，因為查詢橫坐標遞增，故不斷將凸殼的隊首彈出即可均攤$O(\sqrt{n})$每次查詢。

時間復雜度$O(n\sqrt{n})$。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010,K=330;
const ll inf=1000000000000010LL;
int n,m,lim,i,a[N],b[N],pre[N],pos[N],st[K],en[K],tx[K],q[N],head[K],tail[K];
ll base,f[N],tb[K];
inline void up(ll&a,ll b){a>b?(a=b):0;}
inline double slope(int x,int y){return 1.0*(f[x]-f[y])/(b[y]-b[x]);}
inline void build(int x){
  int&h=head[x],&t=tail[x],l=st[x],r=en[x];
  h=l,t=h-1;
  for(int i=r;i>=l;q[++t]=i--)while(h<t&&slope(q[t-1],q[t])>slope(q[t],i))t--;
}
inline void addx(int l){
  int L=pos[l];
  for(int i=l;i<=en[L];i++)f[i]+=b[i];
  for(int i=pos[m];i>L;i--)tx[i]++;
}
inline void addf(int r,int p){
  int R=pos[r];
  for(int i=st[R];i<=r;i++)f[i]+=p;
  build(R);
  for(int i=0;i<R;i++)tb[i]+=p;
}
inline ll cal(int x,int y){return f[x]+1LL*y*b[x];}
inline ll ask(int x){
  int&h=head[x],t=tail[x],o=tx[x];
  while(h<t&&cal(q[h],o)>cal(q[h+1],o))h++;
  return cal(q[h],o);
}
inline ll query(int r){
  ll ret=inf;
  int R=pos[r];
  for(int i=st[R];i<=r;i++)up(ret,f[i]+1LL*tx[R]*b[i]+tb[R]);
  for(int i=0;i<R;i++)up(ret,ask(i)+tb[i]);
  return ret;
}
int main(){
  scanf("%d",&n);
  for(i=1;i<=n;i++)scanf("%d",&a[i]),base-=a[i],b[i]=a[i];
  sort(b+1,b+n+1);
  for(i=1;i<=n;i++)if(b[i]!=b[i-1])b[++m]=b[i];
  for(lim=1;lim*lim<=m;lim++);
  for(i=1;i<=n;i++)pre[i]=max(pre[i-1],a[i]);
  for(i=0;i<=m;i++)pos[i]=i/lim;
  for(i=0;i<=m;i++)en[pos[i]]=i;
  for(i=m;~i;i--)st[pos[i]]=i;
  for(i=0;i<=pos[m];i++)build(i);
  for(i=1;i<=n;i++){
    if(pre[i]==a[i]){
      base+=a[i];
      continue;
    }
    int x=lower_bound(b,b+m+1,a[i])-b;
    ll t=query(x)+a[i];
    addx(x);
    addf(x-1,pre[i]);
    up(f[x],t-tb[pos[x]]-1LL*tx[pos[x]]*b[x]);
    build(pos[x]);
  }
  printf("%lld",query(m)+base);
}

K. Hiding a Tree

將所有可以修改編號的點的編號隨機設置，然后再挑選一個影響答案的點修正異或值。

若當前方案不合法，則在有解的情況下是小概率事件，多輪隨機即可。

注意生成隨機編號的時候要避免與之前編號相同，因為根據生日悖論，在$10^9$內取$10^5$個隨機數中有重復元素的概率超過$50\%$，會導致這一輪隨機作廢。

#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<set>
using namespace std;
const int N=100010;
int n,i,a[N],e[N][2],b[N],c[N],q[N],m,v[N];
int used[N];
set<int>T;
inline int ask(){
	while(1){
		int x=rand()%1000000000+1;
		if(x<N&&used[x])continue;
		if(T.find(x)!=T.end())continue;
		T.insert(x);
		return x;
	}
}
void solve(){
	T.clear();
	for(i=1;i<=n;i++){
		if(a[i])b[i]=ask();
		else b[i]=i;
	}
	int ret=n;
	for(i=1;i<=n;i++)if(v[i])ret^=b[i];
	if(ret){
		if(!m)return;
		int x=rand()%m+1;
		b[q[x]]^=ret;
	}
	for(i=1;i<=n;i++){
		if(b[i]<1||b[i]>1000000000)return;
		c[i]=b[i];
	}
	sort(c+1,c+n+1);
	for(i=1;i<n;i++)if(c[i]==c[i+1])return;
	printf("%d\n",n);
	for(i=1;i<n;i++)printf("%d %d\n",b[e[i][0]],b[e[i][1]]);
	exit(0);
}
int main(){
	srand(time(NULL));
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(!a[i])used[i]=1;
	}
	for(i=1;i<n;i++){
		scanf("%d%d",&e[i][0],&e[i][1]);
		v[e[i][0]]^=1;
		v[e[i][1]]^=1;
	}
	for(i=1;i<=n;i++)if(a[i]&&v[i])q[++m]=i;
	for(int _=100;_;_--)solve();
	puts("-1");
}

posted @ 2018-04-01 23:59 Claris 閱讀(1506) 評論(1) 收藏舉報

刷新頁面返回頂部

Claris' Blog

XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Khamovniki

公告