CF1288

A

考虑\(x + 1 = \sqrt{d}\)时在有理域上有最优界。

那我在整数域上附近取三个点取min就行了。

// code by fhq_treap

#include<bits/stdc++.h>

#define ll long long

#define N 300005

inline ll read(){

    char C=getchar();

    ll A=0 , F=1;

    while(('0' > C || C > '9') && (C != '-')) C=getchar();

    if(C == '-') F=-1 , C=getchar();

    while('0' <= C && C <= '9') A=(A << 1)+(A << 3)+(C - 48) , C=getchar();

    return A*F;

}

template <typename T>

void write(T x)

{

    if(x < 0) {

        putchar('-');

        x = -x;

    }

    if(x > 9)

        write(x/10);

    putchar(x % 10 + '0');

    return;

}

int n,d,t;

int main(){

	scanf("%d",&t);

	while(t -- ){

		scanf("%d%d",&n,&d);

		int ans = d;

		int k = sqrt(d);

		ans = std::min(ans,(d + k - 1) / k + k - 1);

		k ++ ;

		ans = std::min(ans,(d + k - 1) / k + k - 1);

		k -= 2;

		if(k != 0)

		ans = std::min(ans,(d + k - 1)/ k + k - 1);

		puts((ans <= n) ? "Yes" : "No");

	}

}

B

考虑枚举\(b\)的位数，然后发现\(b\)一定是 \(9999\) 这类的形式，而\(a\)可以随意取。

// code by fhq_treap

#include<bits/stdc++.h>

#define ll long long

#define N 300005

inline ll read(){

    char C=getchar();

    ll A=0 , F=1;

    while(('0' > C || C > '9') && (C != '-')) C=getchar();

    if(C == '-') F=-1 , C=getchar();

    while('0' <= C && C <= '9') A=(A << 1)+(A << 3)+(C - 48) , C=getchar();

    return A*F;

}

template <typename T>

void write(T x)

{

    if(x < 0) {

        putchar('-');

        x = -x;

    }

    if(x > 9)

        write(x/10);

    putchar(x % 10 + '0');

    return;

}

int t;

int main(){

	scanf("%d",&t);

	while(t -- ){

		int a,b;

		scanf("%d%d",&a,&b);

		int k = 0,now = 9;

		while(b >= now){

            k++;

            now = now * 10 + 9;

		}

		std::cout<<1ll * k * a<<std::endl;

	}

}

C

直接暴力\(dp\),再利用前缀和优化到\(O(n^2)\)

// code by fhq_treap

#include<bits/stdc++.h>

#define ll long long

#define N 300005

#define mod ((ll)1e9 + 7)

inline ll read(){

    char C=getchar();

    ll A=0 , F=1;

    while(('0' > C || C > '9') && (C != '-')) C=getchar();

    if(C == '-') F=-1 , C=getchar();

    while('0' <= C && C <= '9') A=(A << 1)+(A << 3)+(C - 48) , C=getchar();

    return A*F;

}

template <typename T>

void write(T x)

{

    if(x < 0) {

        putchar('-');

        x = -x;

    }

    if(x > 9)

        write(x/10);

    putchar(x % 10 + '0');

    return;

}

//f[i][j][k] = \sum(f[i - 1][p][q](q <= k,p >= j,j <= k))

int f[1005][1005];

int g[1005][1005];

int n,m;

inline void got(){

	int tmp = 0;

	for(int i = 1;i <= n;++i)

	for(int j = 1;j <= n;++j)

	g[i][j] = 0;

	for(int i = 1;i <= n;++i){

		tmp = 0;

		for(int j = n;j >= 1;--j){

			tmp = (tmp + f[i][j]) % mod;

			g[i][j] = g[i - 1][j];

			g[i][j] = (g[i][j] + tmp) % mod;

		}

	}

}

int main(){

	scanf("%d%d",&n,&m);

	f[1][n] = 1;

	got();

	for(int i = 1;i <= m;++i){

		for(int j = 1;j <= n;++j){

			for(int k = j;k <= n;++k){

				f[j][k] = g[j][k];

			}

		}

		got();

	}

	std::cout<<g[n][1] % mod<<std::endl;

}

D

二分答案，将一个长度为 \(m\) 的数字序列转换为 \(01\) 序列。

可以获得这个答案则有两个\(01\)串或起来为全1串。

可以\(O({2^m}^2)\)做。

// code by fhq_treap

#include<bits/stdc++.h>

#define ll long long

#define N 300005

inline ll read(){

    char C=getchar();

    ll A=0 , F=1;

    while(('0' > C || C > '9') && (C != '-')) C=getchar();

    if(C == '-') F=-1 , C=getchar();

    while('0' <= C && C <= '9') A=(A << 1)+(A << 3)+(C - 48) , C=getchar();

    return A*F;

}

template <typename T>

void write(T x)

{

    if(x < 0) {

        putchar('-');

        x = -x;

    }

    if(x > 9)

        write(x/10);

    putchar(x % 10 + '0');

    return;

}

int n,m;

int a[300005][8];

int ansx = 1,ansy  = 1;

int t[(1 << 9)];

inline bool check(int lim){

	for(int i = 0;i < (1ll << m);++i)

	t[i] = 0;

	for(int i = 1;i <= n;++i){

		int tmp = 0;

		for(int j = 1;j <= m;++j){

			if(a[i][j] >= lim)

			tmp = tmp | (1ll << (j - 1));

		}

		t[tmp] = i;

	}

	for(int i = 0;i < (1ll << m);++i)

	for(int j = 0;j < (1ll << m);++j){

		if(((i | j) == ((1ll << m) - 1)) && (t[i]) && t[j]){

			ansx = t[i];

			ansy = t[j];

			return 1;

		}

	}

	return 0;

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

	for(int j = 1;j <= m;++j){

		scanf("%d",&a[i][j]);

	}

	int l = -1,r = 1e9;

	#define mid ((l + r) >> 1)

	while(l <= r){

		if(check(mid))

		l = mid + 1;

		else

		r = mid - 1;

	}

	l --;

	while(check(l + 1))

	l ++ ;

	std::cout<<ansx<<" "<<ansy<<std::endl;

}

E

经典套路，前面留\(m\)个位置，用树状数组维护排名。

// code by fhq_treap

#include<bits/stdc++.h>

#define ll long long

#define N 300005

inline ll read(){

    char C=getchar();

    ll A=0 , F=1;

    while(('0' > C || C > '9') && (C != '-')) C=getchar();

    if(C == '-') F=-1 , C=getchar();

    while('0' <= C && C <= '9') A=(A << 1)+(A << 3)+(C - 48) , C=getchar();

    return A*F;

}

template <typename T>

void write(T x)

{

    if(x < 0) {

        putchar('-');

        x = -x;

    }

    if(x > 9)

        write(x/10);

    putchar(x % 10 + '0');

    return;

}

int n;

int a[N];

int minn[N],maxx[N];

int T[N << 2];

#define lowbit(x) (x & -x)

inline void add(int x,int p){

	for(int i = x;i <= N << 2;i += lowbit(i))

	T[i] += p;

}

inline int find(int x){

	int ans = 0;

	for(int i = x;i;i -= lowbit(i))

	ans += T[i];

	return ans;

}

int m,pos[N];

int main(){

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

	minn[i] = maxx[i] = i,pos[i] = m + i,add(pos[i],1);

	int now = m;

	for(int i = 1;i <= m;++i){

		int k;

		scanf("%d",&k);

		minn[k] = 1;

		maxx[k] = std::max(maxx[k],find(pos[k]));

		add(pos[k],-1);

		pos[k] = now -- ;

		add(pos[k],1);

	}

	for(int i = 1;i <= n;++i){

		maxx[i] = std::max(maxx[i],find(pos[i]));

		std::cout<<minn[i]<<" "<<maxx[i]<<std::endl;

	}

}

巴特西

CF1288

A

B

C

D

E

最新文章

热门文章