2019 USP Try-outs 练习赛

// 好久没更博客了，最近打了很多场练习赛&校内PK赛，大概自闭忙于补题吧

// 9.26 周四练习赛

A. Kolkhozy

题意

有 n 个数 \(f[i]\) ，有 q 次询问(l, r, x, m)，求 [l, r] 区间内有多少项满足 \(f[i] \%m=x\)。

思路

直接暴力的话复杂度 \(O(q\cdot n)\) ，注意到此题空间给了1024MB，如果能预处理一部分，可以\(O(q \cdot logn)\) 解决。

对于m比较大的情况，我们发现直接找[l, r]区间内等于 \(x + k*m\) 的个数即可，那么可以统计每个点值出现的位置，二分检查是否包含在 [l, r]区间，复杂度 \(O(q \cdot maxf[i]/m \cdot logn)\) ，取 m = 300 在时空复杂度上均可行。

vector牛逼就完事了！

AC代码

#include<iostream>

#include<cstdio>

#include<vector>

#include<algorithm>

typedef long long ll;

using namespace std;

vector<int> ans[310][310];

int f[50010];

int maxf;

vector<int> cnt[50010];

int n, q;

int main() {

	cin>>n>>q;

	maxf = 0;

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

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

		cnt[f[i]].push_back(i);

		maxf = max(maxf, f[i]);

	}

	for(int m=2;m<=300;m++) {

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

			ans[m][f[i]%m].push_back(i);

		}

	}

	int l, r, x, m;

	while(q--) {

		scanf("%d %d %d %d", &l, &r, &x, &m);

		if(m==1) {

			if(x==0)

				printf("%d\n", r-l+1);

			else

				printf("0\n");

			continue;

		}

		if(m<=300) {

			int L = lower_bound(ans[m][x].begin(), ans[m][x].end(), l) - ans[m][x].begin();

			int R = upper_bound(ans[m][x].begin(), ans[m][x].end(), r) - ans[m][x].begin();

			printf("%d\n", R - L);

			continue;

		}

		ll ans = 0;

		for(int v=x;v<=maxf;v+=m) {

			int L = lower_bound(cnt[v].begin(), cnt[v].end(), l) - cnt[v].begin();

			int R = upper_bound(cnt[v].begin(), cnt[v].end(), r) - cnt[v].begin();

			ans += R - L;

		}

		printf("%lld\n", ans);

	}

	return 0;

}

F. Forbechenko v Rodvsky

题意

1/3 在十进制下的小数表示为 0.33333…，在3进制下为 0.1。给定 \(A \over B\) ，求最小的进制使其表示成小数的位数是有限的。

思路

很好想，可以发现A，B约分之和，最小的进制就是B的素因子之积。

那么问题转化为质因数分解。然后一看过了那么多写了个暴力根号n的算法T了。

队友翻到了Pollard-Rho的板子，然后敲上去就A啦。

#include<cstdio>

#include<iostream>

#include<ctime>

#include<cstdlib>

#include<algorithm>

using namespace std;

typedef long long ll;

const int S= 8;

ll qmul(ll a,ll b,ll c) {

    a %= c;

    b %= c;

    ll ret = 0;

    ll tmp = a;

    while(b) {

        if(b&1) {

            ret += tmp;

            if(ret>c)ret -=c;

        }

        tmp<<=1;

        if(tmp>c)tmp -=c;

        b>>=1;

    }

    return ret;

}

ll qpow(ll a,ll n,ll mod) {

    ll ret = 1;

    ll tmp = a%mod;

    while(n) {

        if(n&1)

            ret = qmul(ret,tmp,mod);

        tmp = qmul(tmp,tmp,mod);

        n>>=1;

    }

    return ret;

}

// 判断是否是合数

bool check(ll a,ll n,ll x,ll t) {

    ll ret = qpow(a,x,n);

    ll last = ret;

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

        ret = qmul(ret,ret,n);

        if(ret==1&&last!=1&&last!=n-1)

            return true;

        last = ret;

    }

    if(ret!=1) return true;

    else return false;

}

// ****************************

// Miller_Rabin算法判断是否是素数

bool Miller_Rabin(ll n) {

    if(n<2)return 0;

    if(n==2)return 1;

    if((n&1)==0)return 0;

    ll x= n-1;

    ll t =0;

    while((x&1)==0) {

        x>>=1;

        ++t;

    }

    srand(time(NULL));

    for(int i=0;i<S;++i) {

        ll a = rand()%(n-1)+1;

        if(check(a,n,x,t))

            return 0;

    }

    return 1;

}

// ***************************

// pollard_rho算法进行质因数分解

ll factor[100];

int tol;

ll gcd(ll a,ll b) {

    ll t;

    while(b) {

        t = a;

        a = b;

        b = t%b;

    }

    if(a>=0)return a;

    else return -a;

}

ll pollard_pho(ll x,ll c) {

    ll i=1, k=2;

    srand(time(NULL));

    ll x0 =rand()%(x-1)+1;

    ll y = x0;

    while(1) {

        i++;

        x0 = (qmul(x0,x0,x)+c)%x;

        ll d=gcd(y-x0,x);

        if(d!=1&&d!=x) return d;

        if(y==x0) return x;

        if(i==k) {

            y=x0;

            k+=k;

        }

    }

}

void findfac(ll n,int k) {

    if(n==1)return;

    if(Miller_Rabin(n)) {

        factor[tol++] = n;

        return;

    }

    ll p =n;

    int c= k;

    while(p>=n)

        p = pollard_pho(p,c--);

    findfac(p,k);

    findfac(n/p,k);

}

int main() {

    ll a, b;

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

	b = b/gcd(a, b);

	if(b==1) {

        return 0* printf("2\n");

	}

	findfac(b, 107);

	sort(factor, factor+tol);

	tol = unique(factor, factor+tol) - factor;

    ll res = 1;

	for(int i=0;i<tol;i++) {

        res *= factor[i];

	}

	printf("%lld\n", res);

    return 0;

}

G. Hunting leshys

题意

有 n 个部落（那单词啥意思我也不知道），初始每个人是一个部落，每个人有power p[i]，有两种操作，(! i, j) ：i成为j的首领；(? i)：询问 i 到他的最终首领（根节点）之间的最小权值。

思路

一看就是并查集，然后队友演了我，写了假算法。（并不是求整条链上的最小权值所以不可以直接压缩路径），然后告诉我并查集好像做不了，需要树链剖分。。。

然后我xjb写了就A了。(路径压缩时维护当前节点到根节点之间的最小权值)

AC代码

#include<cstdio>

#include<iostream>

typedef long long ll;

using namespace std;

const int N = 1e5+10;

int arr[N];

int fa[N];

int find(int x)

{

    if(x==fa[x]) return x;

    int root = find(fa[x]);

    arr[x] = min(arr[x], arr[fa[x]]);

    return fa[x] = root;

}

int main()

{

    int n,m;

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

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

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

        fa[i] = i;

    }

    while(m--) {

        char op[3];

        scanf("%s", op);

        if(op[0]=='?') {

            int a;

            scanf("%d",&a);

            int fa = find(a);

            printf("%d\n", arr[a]);

        }

        else {

            int a, b;

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

            fa[b] = a;

        }

    }

    return 0;

}

H. Course recommendation

题意

队友写的，据说是SB题，题意没表述清楚白白浪费一小时。。。

I. Sobytiynyy Proyekt Casino

题意

看了很久，根据样例大概理解为：有 n 个玩家，每个人有一个整数对 (ai, bi)，玩家 i 离开时可以获得 \(\sum_{j=1}^{i} a_j - b_i\) 硬币，每个玩家可以在随意离开游戏。现在你可以决定玩家的顺序，求所有玩家获取的最多硬币的最小值。

思路

卡了半天，大概证明出来按照 bi 递增的顺序安排，可以使玩家收益最小。

AC代码

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

struct node {

    ll a, b;

    bool operator<(const node& n) const {

        return b<n.b;

    }

}arr[100010];

int main() {

    int n; cin>>n;

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

        scanf("%lld %lld", &arr[i].a, &arr[i].b);

    }

    sort(arr+1, arr+1+n);

    ll sum = arr[1].a, ans = arr[1].a-arr[1].b;

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

        sum += arr[i].a;

        ans = max(ans, sum-arr[i].b);

    }

    printf("%lld\n", ans);

    return 0;

}

K. Poor Folk

题意

给了一堆值，求这些值不能组成的最小整数。

思路

队友A的，稍后理解一下。

AC代码

#include<cstdio>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

ll arr[500010];

int main()

{

    int n;cin>>n;

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

        cin>>arr[i];

    sort(arr+1,arr+1+n);

    ll now = 0;

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

    {

        if(now+1<arr[i])

        {

            cout<<now+1<<endl;

            break;

        }

        else

            now+=arr[i];

        if(i==n)

            cout<<now+1<<endl;

    }

    return 0;

}

（完）

巴特西

2019 USP Try-outs 练习赛

A. Kolkhozy

题意

思路

AC代码

F. Forbechenko v Rodvsky

题意

思路

G. Hunting leshys

题意

思路

AC代码

H. Course recommendation

题意

I. Sobytiynyy Proyekt Casino

题意

思路

AC代码

K. Poor Folk

题意

思路

AC代码

最新文章

热门文章