2019 CCPC 网络赛 部分题解

传送门

6702 ^&^

签到,注意特判答案为 0 的情况

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int q[50], w[50];
int main()
{
    int T;
    sc("%d", &T);
    while (T--)
    {
        ll a, b;
        sc("%lld%lld", &a, &b);
        for (int i = 0; i < 40; i++)
        {
            if (a & (1LL << i))
                q[i] = 1;
            else
                q[i] = 0;
        }
        for (int i = 0; i < 40; i++)
        {
            if (b & (1LL << i))
                w[i] = 1;
            else
                w[i] = 0;
        }
        ll ans = 0;
        for (int i = 0; i < 40; i++)
        {
            if (q[i] == 1 && w[i] == 1)
            {
                ans += (1LL << i);
            }
        }
        if (ans == 0)
        {
            for (int i = 0; i < 40; i++)
            {
                if ((q[i] == 0 && w[i] == 1) || (q[i] == 1 && w[i] == 0))
                {
                    ans = (1LL << i);
                    break;
                }
            }
        }
        printf("%lld\n", ans);
    }
}

6703 array

有一个 的全排列,两种操作,第一个操作,让一个数字加上  ,第二种操作,求一个最小的数字,满足大于等于给定的数字K,并且不等于区间的数字。

1、由于区间是一个全排列,所以对于每一个操作2,我们可以用线段树 or 主席树找出一个区间内大于等于 val 的最小数字

2、对于操作1,因为数列长度和操作次数都是  ,所以所求的答案不可能大于  ,所以相当于让这个数字消失,将所有消失的数字存入一个set,每次二操作求完之后,再到set里面找一次大于等于 val 的最小值来更新答案。

3、怎么使用线段树来求一个区间大于等于 val 的最小值呢。

能否直接对原数组建一颗线段树来暴力扫左右子树呢,显然是不行的,在最差的情况下,每次复杂度都是 ,显然是会 T 的。

考虑维护下标是值,并且值是下标的线段树,那么原询问:求出区间  里面大于等于 val 的最小值,就变成了:求出下标大于等于  的第一个   值大于  的    下标的值。

然后对于每个询问,我们只需要在线段树上dfs找一下,加个剪枝,如果在左子树找到了就不在右子树找了,就可以AC。

AC代码

#include <bits/stdc++.h>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
#define sc scanf
#define pr printf
using namespace std;
int n, m, ql, qr, val;
const int MAXN = 1e5 + 5;
struct Segment_tree
{
    int l;
    int r;
    int maxn;
}que[MAXN * 4];
int a[MAXN], in[MAXN];
int ans;
void up(int k)
{
    que[k].maxn = max(que[k << 1].maxn, que[k << 1 | 1].maxn);
}
void build(int left = 1, int right = n, int k = 1)
{
    que[k].l = left;
    que[k].r = right;
    if (left == right)
    {
        que[k].maxn = a[left];
        return;
    }
    imid;
    build(lson);
    build(rson);
    up(k);
}
void update(int left = 1, int right = n, int k = 1)
{
    if (qr < left || right < ql)
        return;
    if (ql <= left && right <= qr)
    {
        que[k].maxn = 0;
        return;
    }
    imid;
    update(lson);
    update(rson);
    up(k);
}
//求区间[ql,qr]第一个大于等于val的值
//使用线段树将区间外的点分开,然后判一段合法区间最大值是否大于等于val
//因为这里不是求整个区间,所以需要将区间外的点分开,不然会影响区间的最大值
bool query(int left = 1, int right = n, int k = 1)
{
    if (que[k].maxn < val)
        return false;
    if (left == right)
    {
        if (que[k].maxn > val)
        {
            ans = min(ans, left);
            return true;
        }
        else
            return false;
    }
    imid;
    if (ql <= mid)
    {
        if (query(lson))
            return true;
        else
            return query(rson);
    }
    else
        query(rson);
}
int main()
{
    int T, op, t;
    sc("%d", &T);
    while (T--)
    {
        sc("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
        {
            sc("%d", &in[i]);
            a[in[i]] = i;
        }
        build();
        set<int>s;
        int pre = 0;
        while (m--)
        {
            sc("%d", &op);
            if (op == 1)
            {
                sc("%d", &val);
                val ^= pre;
                s.insert(in[val]);
                ql = qr = in[val];
                update();
            }
            else
            {
                sc("%d%d", &val, &ql);
                val ^= pre;
                ql ^= pre;
                qr = n;
                ans = n + 1;
                query();
                auto it = s.lower_bound(ql);
                if (it != s.end())
                    ans = min(ans, *it);
                printf("%d\n", ans);
                pre = ans;
            }
        }
    }
}

TLE代码

#include <bits/stdc++.h>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
#define sc scanf
#define pr printf
using namespace std;
int n, m, ql, qr, val;
const int MAXN = 1e5 + 5;
struct Segment_tree
{
    int l;
    int r;
    int maxn;
}que[MAXN * 4];
int a[MAXN];
int ans;
void up(int k)
{
    que[k].maxn = max(que[k << 1].maxn, que[k << 1 | 1].maxn);
}
void build(int left = 1, int right = n, int k = 1)
{
    que[k].l = left;
    que[k].r = right;
    if (left == right)
    {
        que[k].maxn = a[left];
        return;
    }
    imid;
    build(lson);
    build(rson);
    up(k);
}
void update(int left = 1, int right = n, int k = 1)
{
    if (qr < left || right < ql)
        return;
    if (ql <= left && right <= qr)
    {
        que[k].maxn = -1;
        return;
    }
    imid;
    update(lson);
    update(rson);
    up(k);
}
//求区间[ql,qr]大于val的最小权值
void query(int left = 1, int right = n, int k = 1)
{
    if (qr < left || right < ql)
        return;
    if (ql <= left && right <= qr)
    {
        imid;
        if (left == right)
        {
            if (que[k].maxn >= val)
                ans = min(ans, que[k].maxn);
            return;
        }
        if (que[k << 1].maxn >= val)
            query(lson);    
        if (que[k << 1 | 1].maxn >= val)
            query(rson);
    }
    imid;
    query(lson);
    query(rson);
}
int main()
{
    int T, op;
    sc("%d", &T);
    while (T--)
    {
        sc("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            sc("%d", &a[i]);
        build();
        set<int>s;
        int pre = 0;
        while (m--)
        {
            sc("%d", &op);
            if (op == 1)
            {
                sc("%d", &val);
                val ^= pre;
                s.insert(a[val]);
                ql = qr = val;
                update();
            }
            else
            {
                sc("%d%d", &ql, &val);
                ql ^= pre;
                val ^= pre;
                ql++;
                qr = n;
                ans = n + 1;
                query();
                auto it = s.lower_bound(val);
                if (it != s.end())
                    ans = min(ans, *it);
                printf("%d\n", ans);
                pre = ans;
            }
        }
    }
}

6704 K-th occurrence

多次询问,对于一个给定的串的子串,求出这个子串第K次出现的位置,不存在输出-1。

大概就是 后缀数组,套个主席树,再套个二分求区间左右端点,

(队友不会主席树,赛时也不跟我说要用主席树,然后每次sort 直接输出,T飞。)(甩锅)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define M(x) memset(x,0,sizeof(x))
#define ll long long
#define rep(i,a,b) for(int i = a;i<=b;i++)
#define dec(i,a,b) for(int i = a;i>=b;i--)
#define imid int mid=(left+right)/2;
const int MAXN = 100005;
const int logMAXN = 20;
struct node
{
    int l;
    int r;
    ll cnt;
    ll sum;
}tree[MAXN * logMAXN];
int root[MAXN], a[MAXN], cnt;
void init()
{
    root[0] = 0;
    tree[0].l = tree[0].r = tree[0].cnt = 0;
    cnt = 1;
}
void build(int num, int& rot, int left, int right)
{
    tree[cnt++] = tree[rot];
    rot = cnt - 1;
    tree[rot].cnt++;
    tree[rot].sum += num;
    if (left == right)
        return;
    imid;
    if (num <= mid)
        build(num, tree[rot].l, left, mid);
    else
        build(num, tree[rot].r, mid + 1, right);
}
//查询区间[ql, qr]里面的第K小的数字
//query(root[ql - 1], root[qr], k, 1, n);
int query(int pre, int nex, int num, int left, int right)
{
    int s = tree[tree[nex].l].cnt - tree[tree[pre].l].cnt;
    if (left == right)
        return left;
    imid;
    if (num <= s)
        return query(tree[pre].l, tree[nex].l, num, left, mid);
    else
        return query(tree[pre].r, tree[nex].r, num - s, mid + 1, right);
}
struct SufArray {
    int sa[N], c[N], x[N], y[N], height[N], rk[N], f[N][22], n;
    char s[N];
    void clear()
    {
        M(sa); M(c); M(x); M(y); M(height); M(rk); M(f); M(s);
    }

    void build_sa()
    {
        int m = 128;
        for (int i = 0; i <= m; i++) c[i] = 0;
        for (int i = 1; i <= n; ++i) ++c[x[i] = s[i]];
        for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
        for (int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
        for (int k = 1; k <= n; k <<= 1) {
            int num = 0;
            for (int i = n - k + 1; i <= n; ++i) y[++num] = i;
            for (int i = 1; i <= n; ++i) if (sa[i] > k) y[++num] = sa[i] - k;
            for (int i = 1; i <= m; ++i) c[i] = 0;
            for (int i = 1; i <= n; ++i) ++c[x[i]];
            for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
            for (int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
            swap(x, y);
            x[sa[1]] = 1;
            num = 1;
            for (int i = 2; i <= n; ++i)
                x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
            if (num == n) break;
            m = num;
        }
    }
    void build_height()
    {
        int k = 0;
        for (int i = 1; i <= n; i++) rk[sa[i]] = i;
        for (int i = 1; i <= n; i++)
        {
            if (rk[i] == 1)
                continue;
            if (k) k--;
            int j = sa[rk[i] - 1];
            while (j + k <= n && i + k <= n && s[j + k] == s[i + k]) k++;
            height[rk[i]] = k;
        }
    }
    void build_st()
    {
        build_height();
        for (int i = 1; i <= n; i++) f[i][0] = height[i];
        for (int k = 1; (1 << k) <= n; k++)
            for (int i = 1; i + (1 << k) - 1 <= n; i++)
                 f[i][k] = min(f[i][k - 1], f[i + (1 << (k - 1))][k - 1]);
    }
    int lcp(int u, int v)
    {
        int l = rk[u], r = rk[v];
        if (l > r) swap(l, r);
        if (l == r) return n - sa[l];
        l++;
        int k = 0;
        while ((1 << (1 + k)) <= r - l + 1) k++;
        return min(f[l][k], f[r - (1 << k) + 1][k]);
    }//rmq  
    void solve(int l, int r, int k)
    {
        int len = (r - l + 1);
        int t = rk[l];
        int L = 1, R = t;
        int ql, qr;
        while (L + 1 < R)
        {
            int mid = (L + R) >> 1;
            if (lcp(sa[mid], l) >= len)
                R = mid;
            else
                L = mid;
        }
        ql = R;
        if (lcp(sa[L], l) >= len)
            ql = L;
        L = t, R = n;
        while (L + 1 < R)
        {
            int mid = (L + R) >> 1;
            if (lcp(sa[mid], l) >= len)
                L = mid;
            else
                R = mid;
        }
        qr = L;
        if (lcp(sa[R], l) >= len)
            qr = R;
        if (qr - ql + 1 >= k)
            printf("%d\n", query(root[ql - 1], root[qr], k, 1, n));
        else
            printf("-1\n");
    }
}sa;
int main()
{
    int T, K;
    scanf("%d", &T);
    while (T--)
    {
        sa.clear();
        scanf("%d %d", &sa.n, &K);
        scanf("%s", sa.s + 1);

        sa.build_sa();
        sa.build_st();
        init();
        for (int i = 1; i <= sa.n; i++)
        {
            a[i] = sa.sa[i];
            root[i] = root[i - 1];
            build(a[i], root[i], 1, sa.n);
        }
        for (int i = 1; i <= K; i++)
        {
            int l, r, k;
            scanf("%d %d %d", &l, &r, &k);
            sa.solve(l, r, k);
        }
    }
}

6706 huntian oy

//update 2019/10/14

杜教筛模板题,但。首先要知道

(考虑欧拉函数  中与  互质的数字是首尾相加等于 ,即可推导出上面的式子,最后加上 j 为 1 的值)

考虑杜教筛

#include <bits/stdc++.h>
#include <unordered_map>
#define ll long long //T了就换int 试试
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 5000005;//用板子前先改范围
const ll mod = 1e9 + 7;

bool check[MAXN + 10];//值为 false 表示素数,值为 true 表示非素数
ll phi[MAXN + 10];//欧拉函数表
//ll mu[MAXN + 10];//莫比乌斯函数
int prime[MAXN + 10];//连续素数表
int tot;//素数的个数(从0开始
void jzk()
{
	//memset(check, false, sizeof(check));
	phi[1] = 1;
	//mu[1] = 1;
	check[1] = true;//额外要加上的
	tot = 0;
	for (int i = 2; i < MAXN; i++)
	{
		if (!check[i])
		{
			prime[tot++] = i;
			phi[i] = i - 1;
			//mu[i] = -1;
		}
		for (int j = 0; j < tot; j++)
		{
			if (i * prime[j] >= MAXN)
				break;
			check[i * prime[j]] = true;
			if (i % prime[j] == 0)
			{
				phi[i * prime[j]] = phi[i] * prime[j];
				//mu[i * prime[j]] = 0;
				break;
			}
			else
			{
				phi[i * prime[j]] = phi[i] * (prime[j] - 1);
				//mu[i * prime[j]] = -mu[i];
			}
		}
	}
	for (int i = 1; i < MAXN; i++) {
		//mu[i] = (mu[i] + mu[i - 1]);
		phi[i] = (phi[i] * i + phi[i - 1]) % mod;
	}
}
unordered_map<ll, ll>mp;
ll inv2 = (mod + 1) / 2;
ll inv6 = (mod + 1) / 6;
ll calc(ll a, ll b)
{
	ll ans = (b - a + 1) % mod * ((b + a) % mod) % mod * inv2 % mod; 
	return ans;
}
ll calcs(ll n)
{
	ll ans = n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod;
	return ans;
}
ll djs1(ll n)// i * \phi i
{
	if (n < MAXN)
		return phi[n];
	if (mp.count(n))
		return mp[n];
	ll ans = 0, j;
	for (ll i = 2; i <= n; i = j + 1)
	{
		j = n / (n / i);
		ans = (ans + calc(i, j) * djs1(n / i)) % mod;
	}
	ans = calcs(n) - ans;
	return mp[n] = ans;
}
int main()
{
	jzk();
	int T;
	sc("%d", &T);
	while(T--)
	{
		ll n;
		sc("%lld%*d%*d", &n);
		ll ans = djs1(n);
		ans = (ans - 1 + mod) * inv2 % mod;
		pr("%lld\n", ans);
	}
}

6707 Shuffle Card

签到。反过来扫一遍

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int a[100005];
int qq[100005];
vector<int>ans;
bool vis[100005];
int main()
{
    int n, m;
    sc("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        sc("%d", &a[i]);
    for (int i = 1; i <= m; i++)
        sc("%d", &qq[i]);
    for (int i = m; i >= 1; i--)
    {
        int t = qq[i];
        if (vis[t] == true)
            continue;
        else
        {
            ans.push_back(t);
            vis[t] = true;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (vis[a[i]] == false)
            ans.push_back(a[i]);
    }
    for (int i = 0; i < n; i++)
        printf("%d ", ans[i]);
}

6708 Windows Of CCPC

签到,递归秒

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int s[1025][1025];
void dfs(int x, int y, int len, int op)
{
    if (len == 1)
    {
        if (op == 0)
        {
            s[x][y] = 'C';
            s[x][y + 1] = 'C';
            s[x + 1][y] = 'P';
            s[x + 1][y + 1] = 'C';
            return;
        }
        else
        {
            s[x][y] = 'P';
            s[x][y + 1] = 'P';
            s[x + 1][y] = 'C';
            s[x + 1][y + 1] = 'P';
            return;
        }
    }
    dfs(x, y, len - 1, op);
    dfs(x + (1 << (len - 1)), y, len - 1, op ^ 1);
    dfs(x, y + (1 << (len - 1)), len - 1, op);
    dfs(x + (1 << (len - 1)), y + (1 << (len - 1)), len - 1, op);
}
int main()
{
    int T;
    sc("%d", &T);
    while (T--)
    {
        int n;
        sc("%d", &n);
        int len = (1 << n);
        for (int i = 1; i <= len; i++)
            for (int j = 1; j <= len; j++)
                s[i][j] = 0;
        dfs(1, 1, n, 0);
        for (int i = 1; i <= len; i++)
        {
            for (int j = 1; j <= len; j++)
                printf("%c", s[i][j]);
            printf("\n");
        }
    }
}

6709 Fishing Master

假设我们煮鱼的时候如果时间不够就不浪费时间去抓鱼,那么就不抓鱼,那么我们可以知道在不浪费时间的前提下最多能抓多少鱼,然后浪费时间的前提下抓的鱼就是总的鱼减去不浪费时间抓的鱼,,然后将所有煮鱼的时间膜上抓鱼的时间,这个时候我们肯定希望抓浪费时间的鱼最小,所以将煮的时间排个序,煮鱼时间越长说明浪费的时间越少。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll a[100005];
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		int n, k;
		sc("%d%d", &n, &k);
		for (int i = 0; i < n; i++)
			sc("%lld", &a[i]);
		sort(a, a + n, [](int q, int w) {
			return q > w;
			});
		ll time = 0;
		ll num = n;
		for (int i = 0; i < n; i++)
		{
			ll can = a[i] / k;
			can = min(can, num);

			num -= can;
			time += can * k;
			a[i] = a[i] - can * k;
		}
		sort(a, a + n, [](int q, int w) {
			return q > w;
			});
		for (int i = 0; i < num; i++)
			time += k;
		for (int i = num; i < n; i++)
			time += a[i];
		printf("%lld\n", time);
	}
}

 

全部评论

相关推荐

一名愚蠢的人类:多少games小鬼留下了羡慕的泪水
投递荣耀等公司10个岗位
点赞 评论 收藏
分享
10-05 23:02
东北大学 Java
我说句实话啊:那时候看三个月培训班视频,随便做个项目背点八股,都能说3 40w是侮辱价
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务