2019中国大学生程序设计竞赛（CCPC） - 网络选拔赛

2019中国大学生程序设计竞赛（CCPC） - 网络选拔赛

6702 &

\(1 and 1\)的话,\(c\)就必须为\(1\)。其他的贪心选\(0\).

注意c为正整数，0的话就取最低位1.

#include <iostream>

#define ll long long

using namespace std;

void solve(ll a,ll b) {

    ll c=0;

    for(ll i=31;i>=0;--i) {

        bool k1=a&(1LL<<i),k2=b&(1LL<<i);

        if(k1==1&&k2==1) c|=1LL<<i;

    } if(c) return cout<<c<<"\n",void();

    for(ll i=31;i>=0;--i) {

        bool k1=a&(1LL<<i),k2=b&(1LL<<i);

        if(k1||k2) c=1LL<<i;

	} cout<<c<<"\n";

}

int main() {

    int T;

    cin>>T;

    while(T --> 0) {

        ll a,b;

        cin>>a>>b;

        solve(a,b);

    }

    return 0;

}

6703 array

修改操作其实是删除操作。

考虑不删除的话，就是把删除的数字放入\(set\)中

最终答案就是不删除的\(ans\)和\(set\)中符合条件的取个最小值。

方法一

建立主席树维护区间和。

二分，主席树\(check\)。

复杂度\(O(nlog^2n)\)，实测\(T\)飞。

方法二

主席树上二分。

主席树不变查询区间和。然后找到第一个包含的满足条件的子区间。

条件就是\(r-l+1 < e[rt].tot\),然后再在这个区间上查一次就行了。

复杂度都是\(O(nlogn)\)

问了个当场切的老哥的代码，直接线段树，也没\(set\)直接改，我这里先\(Orz\)了。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <set>

#define ls(x) e[x].l

#define rs(x) e[x].r

#define _ 100007

using namespace std;

inline char nc() {

    static char buf[3000000], *p1 = buf, *p2 = buf;

    return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;

}

inline int read() {

    int x=0,f=1;char s=getchar();

    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

    return x*f;

}

int n,m,a[_],cnt,rt[_];

set<int> dsr;

struct node{int l,r,siz;}e[_*20];

void insert(int l,int r,int pos,int val,int x,int &y) {

    e[y=++cnt]=e[x];

    e[y].siz++;

    if(l==r) return;

    int mid=(l+r)>>1;

    if(pos<=mid) insert(l,mid,pos,val,ls(x),ls(y));

    else insert(mid+1,r,pos,val,rs(x),rs(y));

}

int lastans,flag;

int ask(int l,int r,int x) {

    if(l==r) return l;

    int mid=(l+r)>>1;

    if(e[ls(x)].siz<mid-l+1) return ask(l,mid,ls(x));

    else return ask(mid+1,r,rs(x));

}

void query(int l,int r,int L,int R,int x) {

    if(L<=l) {

        if(!flag&&e[x].siz!=r-l+1) {

            flag=1,lastans=min(lastans,ask(l,r,x));

        } return;

    }

    int mid=(l+r)>>1;

    if(L<=mid&&!flag) query(l,mid,L,R,ls(x));

    if(R>mid&&!flag) query(mid+1,r,L,R,rs(x));

}

int main() {

    int T=read();

    while(T --> 0) {

        dsr.clear(),dsr.insert(0x3f3f3f3f);

        cnt=0;

        for(int i=1;i<=n;++i) rt[i]=0;

        for(int i=1;i<=cnt;++i) e[i]={};

        n=read(),m=read();

        for(int i=1;i<=n;++i) a[i]=read(),insert(1,n+1,a[i],a[i],rt[i-1],rt[i]);

        rt[n+1]=rt[n];

        lastans=0;

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

            int opt=read();

            if(opt==1) {

                int pos=read()^lastans;

                if(!dsr.count(a[pos])) dsr.insert(a[pos]);

            } else {

                int r=read()^lastans,k=read()^lastans;

                lastans=*dsr.lower_bound(k),flag=0;

                query(1,n+1,k,n+1,rt[r]);

                printf("%d\n",lastans);

            }

        }

    }

    return 0;

}

6704 K-th occurrence

想了想，只会后缀数组+二分+主席树，感觉有点恐怖就没写,最后还是写了。

然后套了个后缀数组板子就过了,实现还是挺简单的一点也不恐怖。

先对串串进行一遍后缀排序。

显然符合条件的串是一个区间，用Lcp进行二分来找到边界。

边界长度不够k就是-1,否则就查询区间的第k小，用主席树维护即可。

#include <bits/stdc++.h>

using namespace std;

const int _=2e5+7;

int read() {

    int x=0,f=1;char s=getchar();

    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

    return x*f;

}

int n,Q,rt[_];

char s[_];

namespace SA {

    #define FOR(i,a,b) for(int i=a;i<=b;++i)

    #define ROF(i,a,b) for(int i=a;i>=b;--i)

    int sa[_],rk[_],c[_],x[_],height[_],st[_][21];

    void clear() {

        memset(sa,0,sizeof(sa));

        memset(rk,0,sizeof(rk));

        memset(c,0,sizeof(c));

        memset(x,0,sizeof(x));

        memset(height,0,sizeof(height));

        memset(st,0,sizeof(st));

    }

    void get_sa() {

        int m=300;

        FOR(i,1,n) ++c[rk[i]=s[i]];

        FOR(i,1,m) c[i]+=c[i-1];

        ROF(i,n,1) sa[c[rk[i]]--]=i;

        for(int k=1;k<=n;k<<=1) {

            int p=0;

            FOR(i,n-k+1,n) x[++p]=i;

            FOR(i,1,n) if(sa[i]>k) x[++p]=sa[i]-k;

            FOR(i,1,m) c[i]=0;

            FOR(i,1,n) ++c[rk[i]];

            FOR(i,1,m) c[i]+=c[i-1];

            ROF(i,n,1) sa[c[rk[x[i]]]--]=x[i],x[i]=0;

            swap(rk,x);

            rk[sa[1]]=1,p=1;

            FOR(i,2,n) rk[sa[i]]=(x[sa[i]]==x[sa[i-1]]&&x[sa[i]+k]==x[sa[i-1]+k]) ? p : ++p;

            if(p==n) break;

            m=p;

        }

    }

    void get_height() {

        FOR(i,1,n) rk[sa[i]]=i;

        int k=0;

        FOR(i,1,n) {

            k=k?k-1:0;

            int j=sa[rk[i]-1];

            while(s[i+k]==s[j+k]&&i+k<=n&&j+k<=n) k++;

            height[rk[i]]=k;

        }

        height[0]=0;

        FOR(i,1,n) st[i][0]=height[i];

        FOR(j,1,20)

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

        st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);

    }

    int LCP(int i,int j) {

        if(i-1==j) return n-sa[i-1]+1;

        int x=log2(j-i+1);

        return min(st[i][x],st[j-(1<<x)+1][x]);

    }

}

namespace TREE {

    #define ls(x) e[x].l

    #define rs(x) e[x].r

    struct node {int l,r,siz;}e[_*32];

    int cnt;

    void insert(int l,int r,int L,int x,int &y) {

        e[y=++cnt]=e[x];

        e[y].siz++;

        if(l==r) return;

        int mid=(l+r)>>1;

        if(L<=mid) insert(l,mid,L,ls(x),ls(y));

        else insert(mid+1,r,L,rs(x),rs(y));

    }

    int query(int l,int r,int k,int x,int &y) {

        if(l==r) return l;

        int mid=(l+r)>>1,w=e[ls(y)].siz-e[ls(x)].siz;

        if(k<=w) return query(l,mid,k,ls(x),ls(y));

        else return query(mid+1,r,k-w,rs(x),rs(y));

    }

}

void solve(int S,int T,int k) {

    int L,R,l,r;

    l=1,r=SA::rk[S];

    while(l<=r) {

        int mid=(l+r)>>1;

        if(SA::LCP(mid+1,SA::rk[S])>=T-S+1) L=mid,r=mid-1;

        else l=mid+1;

    }

    l=SA::rk[S],r=n;

    while(l<=r) {

        int mid=(l+r)>>1;

        if(SA::LCP(SA::rk[S]+1,mid)>=T-S+1) R=mid,l=mid+1;

        else r=mid-1;

    }

    // cout<<SA::rk[S]<<"\n";

    // cout<<L<<" "<<R<<"\n";

    if(R-L+1<k) return puts("-1"),void();

    printf("%d\n",TREE::query(1,n,k,rt[L-1],rt[R]));

}

int main() {

    int T=read();

    while(T --> 0) {

        //clear

        memset(rt,0,sizeof(rt));

        memset(TREE::e,0,sizeof(TREE::e));

        TREE::cnt=0;

        SA::clear();

        //init

        n=read(),Q=read();

        scanf("%s",s+1);

        n=strlen(s+1);

        SA::get_sa();

        SA::get_height();

        for(int i=1;i<=n;++i) TREE::insert(1,n,SA::sa[i],rt[i-1],rt[i]);

        //debug

        // puts("sa : ");

        // for(int i=1;i<=n;++i) cout<<SA::sa[i]<<" ";

        // puts("\nrk : ");

        // for(int i=1;i<=n;++i) cout<<SA::rk[i]<<" ";

        // cout<<"\n";

        // puts("LCP");

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

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

        //         if(i>j) printf("0 ");

        //         else printf("%d ",SA::LCP(i+1,j));

        //     }

        //     printf("\n");

        // }

        //query

        while(Q --> 0) {

            int l=read(),r=read(),k=read();

            solve(l,r,k);

        }

    }

    return 0;

}

6705 path

类似于NOI2010超级钢琴和十二省联考的异或粽子。

往这里思考过，不知道咋的\(3s\)后就放弃了，也许是当时觉得不对？

现在一看很对啊。

首先我们每个点连出的边按照权值排序。

用一个优先队列维护每个点为起始点的没被选中的最短路径，每次堆上找到最小的，然后删掉。

之后我们要加入两条要成为最短的可能路径。

1.\(t\)之后找一条最小的边接上。

2.若与\(t\)相连的上一个点为\(s，<s,t>\)这条边为第k大，则起点\(->s+k+1\)大边。

路径权值\(w\)对应着加加减减。

这里初始点不用记录，只记录\(s,t,k,w\)就行了。

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int _=5e4+7;

int read() {

	int x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

	return x*f;

}

int ask[_];ll ans[_];

struct node{

 	int s,t,k;ll w;

	node(int a,int b,int c,ll x) {s=a,t=b,k=c,w=x;}

};

bool operator < (node a,node b) {

	return a.w>b.w;

}

priority_queue<node> q;

vector< pair<ll, int> > G[_];

int main() {

	int T=read();

	while(T --> 0) {

		int n=read(),m=read(),Q=read(),cnt=0,limit=0;

		while(!q.empty()) q.pop();

		for(int i=1;i<=n;++i)  G[i].clear();

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

			int u=read(),v=read(),w=read();

			G[u].push_back(make_pair(w,v));

		}

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

			sort(G[i].begin(),G[i].end());

			if(G[i].size()) q.push(node(i,G[i][0].second,0,G[i][0].first));

		}

		for(int i=1;i<=Q;++i) ask[i]=read(),limit=max(limit,ask[i]);

		while(!q.empty()&&cnt<limit) {

			node u=q.top();q.pop();

			ans[++cnt]=u.w;

			if(u.k+1<(int)G[u.s].size())

				q.push(node(u.s,G[u.s][u.k+1].second,u.k+1,u.w-G[u.s][u.k].first+G[u.s][u.k+1].first));

			if(G[u.t].size()>0)

				q.push(node(u.t,G[u.t][0].second,0,u.w+G[u.t][0].first));

		}

		for(int i=1;i<=Q;++i) printf("%lld\n",ans[ask[i]]);

	}

	return 0;

}

6706 huntian oy

\(gcd(i^a-j^a,i^b-j^b)=i-j(a,b互质)\)

求\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}(i-j)[(i,j)=1]\)

\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}i-\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}j([(i,j)=1])\)

与他互质的和为\(\frac{n*\phi(n)}{2}，因为i\)对应\(n-i\)

\(\sum\limits_{i=1}^{n}i*\phi(i)-\sum\limits_{i=1}^{n}(\frac{i*\phi(i)}{2}+[i==1])\)

\(\frac{(\sum\limits_{i=1}^{n}i*\phi(i))-1}{2}\)

用杜教筛来求\(i*\phi(i)\)的前缀和就行了。

\(f(x)=x*\phi(x)\)

\((f*g)(n)=\sum\limits_{d|n}g(d)*\phi(\frac{n}{d})*\frac{n}{d}\)

显然\(g(i)为id(i)\)最合适。

\((f*g)(n)=n*\sum\limits_{d|n}\phi(\frac{n}{d})=n^2\)

\(g(1)S(n)=\sum\limits_{i=1}^{n}g(i)S(\frac{n}{i})-\sum\limits_{i=2}^{n}g(i)S(\frac{n}{i})\)

\(S(n)=\sum\limits_{i=1}^{n}i^2-\sum\limits_{i=2}^{n}iS(\frac{n}{i})\)

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int _=5e6+7,mod=1e9+7,limit=5000000;

int read() {

	int x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

	return x*f;

}

int inv_2,inv_6,vis[_],pri[_],cnt;

ll phi[_];

int q_pow(int a,int b) {

	int ans=1;

	while(b) {

		if(b&1) ans=1LL*ans*a%mod;

		a=1LL*a*a%mod,b>>=1;

	} return ans;

}

void Euler() {

	vis[1]=phi[1]=1;

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

		if(!vis[i]) pri[++cnt]=i,phi[i]=i-1;

		for(int j=1;j<=cnt&&pri[j]*i<=limit;++j) {

			vis[pri[j]*i]=1;

			if(i%pri[j]==0) {

				phi[i*pri[j]]=phi[i]*pri[j];

				break;

			} else phi[i*pri[j]]=phi[i]*(pri[j]-1);

		}

	}

	for(int i=2;i<=limit;++i) phi[i]=(phi[i-1]+1LL*phi[i]*i%mod)%mod;

}

unordered_map<int,int> ans_phi;

int get(int n) {return 1LL*n*(n+1)/2%mod;}

int solve_phi(int n) {

	if(n<=limit) return phi[n];

	if(ans_phi[n]) return ans_phi[n];

	ll tmp=1LL*n*(n+1)%mod*(2*n+1)%mod*inv_6%mod;

	for(int l=2,r;l<=n;l=r+1) {

		r=n/(n/l),

		tmp-=1LL*(get(r)-get(l-1))*solve_phi(n/l)%mod,

		tmp=(tmp%mod+mod)%mod;

	} return ans_phi[n]=tmp;

}

int main() {

	inv_2=q_pow(2,mod-2),inv_6=q_pow(6,mod-2);

	Euler();

	int T=read();

	while(T --> 0) {

		int N=read();

		int ans=1LL*(solve_phi(N)-1)*inv_2%mod;

		ans=(ans%mod+mod)%mod;

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

		N=read(),N=read();

	}

	return 0;

}

6707 Shuffle Card

想了半天也不会啊，平衡树还很麻烦，不想写。

其实倒着做就行了，用\(stack\)其实本质也是倒着做。

#include <bits/stdc++.h>

using namespace std;

const int _=2e5+7;

int n,m,a[_],b[_],vis[_];

vector<int> ans;

int main() {

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

    for(int i=1;i<=n;++i) scanf("%d",&a[i]);

    for(int i=1;i<=m;++i) scanf("%d",&b[i]);

    for(int i=m;i>=1;--i) {

        if(vis[b[i]]) continue;

        vis[b[i]]=1;

        ans.push_back(b[i]);

    }

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

        if(vis[a[i]]) continue;

        ans.push_back(a[i]);

    }

    for(int i=0;i<n;++i) cout<<ans[i]<<" ";

    return 0;

}

6708 Windows Of CCPC

这是\(yjg\)外出模拟赛的\(luogu\)原题啊，\(axm\)还拉我做过，把\(0,1\)改成了\(C,P\)了而已。

递归即可。

分成四块，先递归第一块，剩下的三块复制第一块的内容，然后第四块取反。

#include <bits/stdc++.h>

using namespace std;

const int _=1207;

int n,A[_][_];

void copp(int x,int y,int len) {

    for(int i=0;i<len;++i)

        for(int j=0;j<len;++j)

            A[x+i][y+j]=A[i][j];

}

void print(int x) {

    for(int i=0;i<(1<<x);++i) {

        for(int j=0;j<(1<<x);++j)

            printf("%c",A[i][j]?'C':'P');

        printf("\n");

    }

}

void calc(int n) {

    if(n==0) return A[0][0]=1,void();

    calc(n-1);

    int len=1<<(n-1);

    copp(0,len,len);

    copp(len,len,len);

    for(int i=0;i<len;++i)

        for(int j=0;j<len;++j)

            A[len+i][j]=A[i][j]^1;

}

int main() {

    int T;

    cin>>T;

    while(T-->0) {

        int x;cin>>x;

        calc(x);

        print(x);

    }

}

6709 Fishing Master

补充：看到zhihu好多全局钓鱼的，其实不难吧。

考虑dp，不会。贪心。

首先一开始肯定要先捉一次鱼。

发现捉鱼分两种种。

1.煮鱼的时间内能去捉鱼并且在锅里鱼没熟之前回来。

2.煮鱼的时间内能去捉鱼并且在锅里鱼熟之后时候回来。

显然1这种情况能干就干，相当于一开始就捉到了这些条。

剩下的捕鱼就得是情况2了，因为剩下的煮鱼时间都是小于捕鱼时间的，当然是贪心的从煮鱼时间大的开始捉。

发现这样一定能安排上(先捉情况2，然后过程中能捉1就捉1)。

然后就做完了。

#include <iostream>

#include <algorithm>

#define ll long long

using namespace std;

const int _=2e5+7;

ll n,m,t[_];

int main() {

    std::ios::sync_with_stdio(false);

    ll T;

    cin>>T;

    while(T --> 0) {

        cin>>n>>m;

        for(ll i=1;i<=n;++i) cin>>t[i];

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

        ll ma=0,ans=0;

        for(ll i=1;i<=n;++i) ma+=t[i]/m;

        for(ll i=1;i<=n;++i) ans+=t[i];

        ans+=m;

        if(ma>=n-1) {

            cout<<ans<<"\n";

        } else {

            ll need=n-1-ma;

            for(ll i=1;i<=n;++i) t[i]-=t[i]/m*m;

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

            for(ll i=n;i>=1;--i) {

                need--;

                ans+=m-t[i];

                if(!need) break;

            }

            cout<<ans<<"\n";

        }

    }

}

巴特西

2019CCPC网络预选赛八道签到题题解

2019中国大学生程序设计竞赛（CCPC） - 网络选拔赛

6702 &

6703 array

6704 K-th occurrence

6705 path

6706 huntian oy

6707 Shuffle Card

6708 Windows Of CCPC

6709 Fishing Master

最新文章

热门文章

巴特西

2019CCPC网络预选赛 八道签到题题解

2019中国大学生程序设计竞赛（CCPC） - 网络选拔赛

6702 &

6703 array

6704 K-th occurrence

6705 path

6706 huntian oy

6707 Shuffle Card

6708 Windows Of CCPC

6709 Fishing Master

最新文章

热门文章

2019CCPC网络预选赛八道签到题题解