• 周六. 10月 8th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

2021牛客暑期多校训练营1

admin

11月 28, 2021

2021牛客暑期多校训练营1

A Alice and Bob

题目大意
两人博弈,每次一个人从一堆中拿 k 个,同时从另一堆拿 k * s(s >= 0) 个,问谁先不能拿。
10000 组数据,N <= 5000

考虑到N十分小,使用SG函数解决。

使用记忆化搜索时,因为一个状态的SG函数的判断需要(NlogN)个状态。所以总复杂度是(O(N^3logN))

考虑SG函数的构造过程:如果一个状态可以由必败状态转移过来那么这个状态必胜,否者必败。

我们只需要考虑这个状态是否可以由必败状态转移过来。通过打表简单的推理必败态数量只有N的数量级。

考虑反向(与记忆化搜索)递推,用每一个必败态筛出所有必胜态,留下的就是必败态。时间复杂度(O(N^2logN))

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 5010
bool ans[N][N],book[N]; 
int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return sum*f;
}
void pre_work(){
	ans[0][0]=0;
	for(int i=0;i<=5000;i++){
		for(int j=0;j<=5000;j++){
			if(ans[i][j]==1)continue;
			for(int k=1;k+i<=5000;k++)
				for(int l=0;l*k+j<=5000;l++)
					ans[k+i][l*k+j]=1;
				
			for(int k=1;k+j<=5000;k++)
				for(int l=0;l*k+i<=5000;l++)
					ans[l*k+i][k+j]=1;
		}
	}
}
int main(){
	pre_work();
	int T=read();
	while(T--){
		int x=read(),y=read();
		if(ans[x][y])printf("Alice
");
		else printf("Bob
");
	} 
	return 0;
}

B Ball Dropping

题目大意
一个球卡在一个直角等腰梯形内部,求卡着的高度。

初中数学题。重读一边初中。

#include <bits/stdc++.h>
#define ll long long
#define int ll 
#define mod 100000000
#define N 100010
#define long_long_MAX 9187201950435737471
#define long_long_MIN -9187201950435737472
#define int_MAX 2139062143
#define int_MIN -2139062144
#define jh(x, y) (x ^= y ^= x ^= y)
#define loc(x, y) ((x - 1) * m + y)
#define lowbit(x) (x & -x)
using namespace std;

ll max(ll x,ll y){return x > y ? x : y;}

ll min(ll x,ll y){return x > y ? y : x;}

inline ll read()
{
    ll a=0;ll f=0;char p=getchar();
	while(!isdigit(p)){f|=p=='-';p=getchar();}
	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
	return f?-a:a;
}

inline void print(ll x)
{
    if(!x) return;
    if(x) print(x/10);
    putchar(x%10+'0');
}

double r,a,b,h;

signed main()
{
    r = read(),a = read(),b = read(),h = read();
    if(r <= b / 2.0) printf("Drop
");
    else
    {
        printf("Stuck
");
        double aa = a / 2.0;
        double bb = b / 2.0;
        double cc = aa - bb;
        double dd = sqrt(h * h + cc * cc);
        double x = cc / dd;
        double h1 = x * r;
        double ee = sqrt(1 - x * x) * r;
        double h2 = h * (ee - bb) / (aa - bb);
        printf("%lf
",h1 + h2);
    }
    system("pause");
    return 0;
}

C Cut the Tree

题目大意
给一个带点权的树,你可以删去树上一个点,最小化所有子树最长上升子序列的长度最大值
N <= 100000

  1. 先在原树上求出最长链,要想答案更优,删除的点必须是链上的点,因此可以尝试删除链的中点,再求一条最长链。
  2. 要想答案比之前都更优,则删除的点必须在之前所有答案链的交集内。
    因为若干条链的交集一定还是一条链,所以可以继续尝试删除链的中点,再求一条最长链。重复此操作直到所有答案链的交集为空,最多需要求 O(log N) 次,时间复杂度 O(N log^2 N) 。

D Determine the Photo Position

题目大意
给出一个 nn 的 01 矩阵,要用一个 1m 的矩阵去覆盖一段 0,问方案数。

签到题。

#include <bits/stdc++.h>
#define ll long long
#define int ll 
#define mod 100000000
#define N 20010
#define long_long_MAX 9187201950435737471
#define long_long_MIN -9187201950435737472
#define int_MAX 2139062143
#define int_MIN -2139062144
#define jh(x, y) (x ^= y ^= x ^= y)
#define loc(x, y) ((x - 1) * m + y)
#define lowbit(x) (x & -x)
using namespace std;

ll max(ll x,ll y){return x > y ? x : y;}

ll min(ll x,ll y){return x > y ? y : x;}

inline ll read()
{
    ll a=0;ll f=0;char p=getchar();
	while(!isdigit(p)){f|=p=='-';p=getchar();}
	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
	return f?-a:a;
}

inline void print(ll x)
{
    if(!x) return;
    if(x) print(x/10);
    putchar(x%10+'0');
}

int n,m;
char t[N][N];

signed main()
{
    n = read(),m = read();
    for(int i = 1;i <= n;++i) scanf("%s",t[i] + 1);
    scanf("%s",t[n + 1] + 1);
    int ans = 0;
    for(int i = 1;i <= n;++i)
    {
        for(int j = 1;j <= n;++j)
        {
            if(t[i][j] == '1') continue;
            int st = j,en = j;
            while(t[i][en] == '0')
            {
                en++;
            }
            en--;
            if(en - st + 1 >= m) ans += en - st + 2 - m;
            j = en;
        }
    }
    printf("%d
",ans);
    //system("pause");
    return 0;
}

E: Escape along Water Pipes

题目大意
给出一个 n*m 的水管图,要从 (1,1) 顶部走到 (n,m) 底部。每走一步前,可以选择一个管道集合旋转相同的角度。要求在 20nm 步前走到终点或者输出无解。

整个图可视为无状态的
虽然每个格子有当前的角度,但是旋转操作的任意性使得你无须关注每个格子当前的状态(当然输出答案的时候需要继承状态的)。
既然是无状态的,总情况从指数级降低成 O(N^2)。

一些碎碎念
集合选取没有意义,每次只要旋转下一个要去的格子就行了。
理论经过的格子数是 4nm,操作数是 8nm,因为到达每个格子时有四种方向。
对所有状态进行记忆化搜索/宽搜。输出方案的时候需要模拟一下方向。

F Find 3-friendly Numbers

题目大意
定义一个自然数是 3-friendly 的,如果它存在一个子串(允许前导0)是 3 的倍数。多组数据,求 L~R 中 3-friendly 的数的个数。

题目读起来就是数位DP。
但是仔细想想,一个三位数必然满足条件。
然后对于小于100的数暴力就行了。

#include <bits/stdc++.h>
#define ll long long
#define int ll 
#define mod 100000000
#define N 100010
#define long_long_MAX 9187201950435737471
#define long_long_MIN -9187201950435737472
#define int_MAX 2139062143
#define int_MIN -2139062144
#define jh(x, y) (x ^= y ^= x ^= y)
#define loc(x, y) ((x - 1) * m + y)
#define lowbit(x) (x & -x)
using namespace std;

ll max(ll x,ll y){return x > y ? x : y;}

ll min(ll x,ll y){return x > y ? y : x;}

inline ll read()
{
    ll a=0;ll f=0;char p=getchar();
	while(!isdigit(p)){f|=p=='-';p=getchar();}
	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=getchar();}
	return f?-a:a;
}

inline void print(ll x)
{
    if(!x) return;
    if(x) print(x/10);
    putchar(x%10+'0');
}

inline bool check(int num)
{
    int len = 1;
    for(len = 1;;++len)
    {
        int data = pow(10,len);
        if(num / data == 0) break;
    }
    //printf("len:%d
",len);
    for(int i = len;i >= 1;--i)
        for(int st = len;st - i + 1 >= 1;--st)
        {
            int en = st - i + 1;
            int a1 = pow(10,st);
            int a2 = pow(10,en - 1);
            int x = num % a1;
            x /= a2;
            if(!(x % 3)) return true;
        }
    return false;
}

int no[N],t;

signed main()
{
    for(int i = 1;i <= 1e4;++i)
    {
        if(!check(i)) no[i] = 1;
    }
    t = read();
    while(t--)
    {
        int ans = 0;
        int l = read(),r = read();
        if(l < 100)
        {
            if(r < 100)
            {
                for(int i = l;i <= r;++i) if(no[i]) ans--;
                ans += r - l + 1;
            }
            else
            {
                for(int i = l;i <= 100;++i) if(no[i]) ans--;
                ans += r - l + 1;
            }
        }
        else ans = r - l + 1;
        printf("%lld
",ans);
    }
    //system("pause");
    return 0;
}

G: Game of Swapping Numbers

题目大意
给定序列 A,B,需要交换恰好 k 次 A 中两个不同的数,使得 A,B 每个位置的绝对差值和最大。
N <= 100000

要求的东西似乎很难求,试着转换模型。

其实要求的东西是(ans=sum_{i=1}^n[max(a[i],b[i])-min(a[i],b[i])]=sum_{i=1}^nmax(a[i],b[i])-sum_{i=1}^nmin(a[i],b[i]))

(a[i])(b[i])放在一起排序,最小的n个打上一个“小”标记,最大的n个打上一个“大”的标记。
a,b序列可以表示成:
(|小|小|大|大|小|)
(|小|大|大|小|大|)

根据上边的式子(ans)最大的情况一定是(a[i],b[i])一个是大一个是小。

交换同一行的两个小或者两个大是没有意义的。

为使答案变优必须交换(a[i]b[i])都是小的(a[i])(a[j]b[j])都是大的(a[j])
如上边的例子中交换(a[1])(a[3])答案变为最优。

考虑一次交换对答案变化的贡献:
(Delta ans=(b[j]-a[i]+a[j]-b[i])-[abs(b[j]-a[j])+abs(a[i]-b[i])])
(b[j]a[j])(a[i]b[i])的相对大小进行讨论可以得到:
(Delta ans=2*[min(b[j],a[j])-max(a[i],b[i])])

所以对(a[j]b[j])都是大的(j)(e[m]=min(a[j],b[j]))并把(e[m])从大到小排序,对(a[i]b[i])都是小的(i)(f[n]=max(a[i],b[i]))并把(f[n])从小到大排序。
一次最优的交换就是把答案加上(2*[e[k]-f[k]])

(e)数组长度和(f)数组长度一定相等。

(n>2)根据鸽巢原理,一个最优解可以通过交换维持为最优解。

所以交换(min(k,sizeof(e)))次就得到了最优解。

n=2时没有一个最优解可以通过交换维持为最优解的性质,所以要特判。

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 501000
int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return sum*f;
}
int a[N],b[N],col[2][N],e[N],f[N];
struct node{
	int w,type,pos; 
}c[N*2];
bool cmp(int x,int y){
	return x>y;
}
bool operator < (node a,node b){
	return a.w<b.w;
}
signed main(){
	int n=read(),k=read();
	if(n==2){
		a[1]=read(),a[2]=read();
		b[1]=read(),b[2]=read();
		int ans1=abs(a[1]-b[1])+abs(a[2]-b[2]);
		int ans2=abs(a[1]-b[2])+abs(a[2]-b[1]);
		if(k&1==1)printf("%d",ans2);
		else printf("%d",ans1);
		return 0;
	}
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	long long ans=0;
	for(int i=1;i<=n;i++)ans+=abs(a[i]-b[i]);
	for(int i=1;i<=n;i++){
		c[i*2-1].w=a[i];
		c[i*2-1].type=0;
		c[i*2-1].pos=i;
		c[i*2].w=b[i];
		c[i*2].type=1;
		c[i*2].pos=i;
	}
	sort(c+1,c+1+2*n);
	for(int i=1;i<=n*2;i++){
		if(i<=n)col[c[i].type][c[i].pos]=0;
		else col[c[i].type][c[i].pos]=1;
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(col[0][i]==1&&col[1][i]==1)e[++cnt]=min(a[i],b[i]);
	cnt=0;
	for(int i=1;i<=n;i++)
		if(col[0][i]==0&&col[1][i]==0)f[++cnt]=max(a[i],b[i]);
	sort(e+1,e+1+cnt,cmp);
	sort(f+1,f+1+cnt);
	k=min(k,cnt);
	for(int i=1;i<=k;i++)ans+=2ll*(e[i]-f[i]);
	printf("%lld",ans);
	return 0; 
} 

H: Hash Function

题目大意
给定 n 个互不相同的数,找一个最小的模域,使得它们在这个模域下互不相同。
n 500000。
解法
考虑两个数 a 与 b, a 与 b 模 m 余数相同,当且仅当 |a-b| 能被 m 整除。
问题转化为找到最小的 m,其不是任意一个|(a_i)(a_j)|的约数。
由于(1 <= |a_i – a_j| <= 500000), 如果我们知道每一种差值是否存在,只需要直接枚举每个 m 以及其倍数即可在 O(Nlog N) 的时间寻找最优解。
(P_i) 为数值 $i $是否存在,将 ${P_0,P_1,…,P_{500000}} $ 与 ${P_{500000−0},P_{500000−1},…,P_0} $卷积,判断对应位置是否大于 0 以确认每一种差值是否存在。
利用 (FFT/NTT) 加速上述过程。总复杂度 (O(Nlog N))

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1100000;
const double Pi=acos(-1.0);
int n,m,r[N];
int c[N];
struct complex{
	double x,y;
	complex(double xx=0,double yy=0){
		x=xx;y=yy;
	}
}a[N],b[N];
complex operator +(complex a,complex b){
	return complex(a.x+b.x,a.y+b.y);
}
complex operator -(complex a,complex b){
	return complex(a.x-b.x,a.y-b.y);
}
complex operator *(complex a,complex b){
	return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
void FFT(complex *A,int limit,int type){
	for(int i=0;i<limit;i++)if(i<=r[i])swap(A[i],A[r[i]]);
	for(int k=1;k<limit;k<<=1){
		complex Wn(cos(Pi/k),type*sin(Pi/k));
		for(int i=0;i<limit;i+=(k<<1)){
			complex w(1,0);
			for(int j=0;j<k;j++,w=w*Wn){
				complex x=A[i+j],y=A[i+j+k]*w;
				A[i+j]=x+y;A[i+j+k]=x-y;
			}
		}
	}
}
int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return sum*f;
}
int main(){
	int n=read();
	for(int i=1;i<=n;i++)a[read()].x=1;
	for(int i=0;i<=500000;i++)b[i].x=a[500000-i].x;
	n=m=500000;
	int limit=1,l=0;
	while(limit<=(n+m))limit<<=1,l++;
	for(int i=0;i<limit;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	FFT(a,limit,1);FFT(b,limit,1);
	for(int i=0;i<limit;i++)a[i]=a[i]*b[i];
	FFT(a,limit,-1);
	for(int i=500001;i<=1000000;i++)c[i-500000]=(int)(a[i].x/limit+0.5);
	for(int i=1;i<=500001;i++){ 
		int flag=0; 
		for(int j=1;j*i<=500000;j++)if(c[j*i])flag=1;
		if(flag==0){
			printf("%d",i);
			break;
		}
	} 
	return 0;
}

I: Increasing Subsequence

题目大意
给出排列P,两个人轮流取数,每次取的数需要在之前该人取数的右边,且比当前取出来所有的数都要大。所有当前可选的数都将等概率随机的被当前决策人选中。问两个人期望取数的轮数。
N <= 5000

J: Journey of Railway Stations

题目大意
一段路上有 N 个点,每个点有一个合法时间段 [u_i, v_i],相邻两个点有一个长度。每次问,在 u_i 的时间从 i 出发后,能否依次经过 i+1~j 的所有点,使得到达时间满足每个点的合法区间(如果提前到可以等待,迟到了失败了)。同时还可能修改一段路的长度,或者修改一个点的合法时间段。
N, Q <= 1000000

K: Knowledge Test about Match

题目大意
随机生成一个权值范围为 0~n-1 的序列,你要用 0~n-1 去和它匹配,匹配函数是 sqrt。
要求平均情况下和标准值偏差不能超过 4%。

发表回复

您的电子邮箱地址不会被公开。