HR#4 题解

既然考这么差就来写题啦OTZ

T1 猜结论？猜nm！

一直到考试结束都没猜出来=。=我就好奇别人如何猜出来的

我们来说DP（from ZBK）

设\(dp[i][j]\)表示胜or负

那我们来看一下代码：

#include<bits/stdc++.h>

#define R register int

using namespace std;

const int N=1000;

bool dp[N+10][N+10];

signed main(){

    for(R i=1;i<=N;i++) dp[i][1]=!(i&1);//靠着边界走状态是可以确定的

    for(R j=1;j<=N;j++) dp[1][j]=!(j&1);

    for(R i=2;i<=N;i++) for(R j=2;j<=N;j++)

        dp[i][j]=!(dp[i][j-1]&dp[i-1][j]&dp[i-1][j-1]);//之前的存在必败态，就是必胜态

    R n,m; while(scanf("%d%d",&n,&m),n!=0&&m!=0)

		puts(dp[n][m]?"Yuri":"Chito");

    return 0;

}

/* code from ZBK */

这**不就是SG函数吗？？？

我咋就没有推DP呐？？DAG上DP呐？？

qwq

T2 1.25e9跑过1.x s

这是暴力。

但他过了(-O2)。

先二分一下答案 \(O(nlog^2n)\) ，然后暴力统计 \(O(n^2)\) 。

#include<bits/stdc++.h>

#define int ll

#define ll long long

#define R register int

using namespace std;

namespace Luitaryi {

inline int g() { R x=0;

	register char ch; while(!isdigit(ch=getchar()));

	do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x;

} const int N=50010,L=31,M=1e9+7;

int n,k,a[N],tot,lim; ll ans;

int t[N*L][2],sz[N*L];

inline void ins(int x) { R now=0;

	for(R i=lim;~i;--i) { R ch=(x>>i)&1;

		if(!t[now][ch]) t[now][ch]=++tot;

		now=t[now][ch],++sz[now];

	}

}

inline int ask(int x,int y) { R now=0,ret=0;

	for(R i=lim;~i;--i) { R ch=(x>>i)&1,c=(y>>i)&1;

		if(!c&&t[now][ch^1]) ret+=sz[t[now][ch^1]];

		if(t[now][ch^c]) now=t[now][ch^c];

		else break;

	} return ret;

}

inline bool ck(int x) { R cnt=0;

	for(R i=1;i<=n;++i) cnt+=ask(a[i],x); return cnt<k;//

}

inline void main() {

	n=g(),k=g()*2; for(R i=1;i<=n;++i) a[i]=g();

	sort(a+1,a+n+1); lim=log2(a[n]);

	for(R i=1;i<=n;++i) ins(a[i]);

	R l=0,r=(1ll<<31)-1; while(l<r) {

		R md=l+r>>1; if(ck(md)) r=md; else l=md+1;

	} k/=2;

	for(R i=1;i<=n;++i) for(R j=i+1;j<=n;++j) { R tmp=a[i]^a[j];

		if(tmp>l) ans+=tmp,--k;

	} printf("%d\n",(ans+1ll*k*l)%M);

}

} signed main() {Luitaryi::main(); return 0;}

T3 脑子是个好东西

考试时：额？\(K\leq 10\)

????

管他呢，先打暴力（还有45min）

最后获得30分的好成绩

第二天改了改暴力成功通过 \(O(n^2)\) 模拟+线段树最大值+静态区间第k大主席树拿到了 70 分。

然后看到了\(K \leq 10\)

????

!!!!

ffff%^&@#@&(*

一个线段树，每个点维护区间前十大就好了，合并时双指针，\(O(knlogn)\)

#include<bits/stdc++.h>

#define R register int

using namespace std;

namespace Luitaryi {

inline int g() { R x=0;

	register char ch; while(!isdigit(ch=getchar()));

	do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x;

} const int N=100010,K=10,SZ=40;

int n,m,tg[N<<2];

#define ls (tr<<1)

#define rs (tr<<1|1)

struct node {

	int mem[K]; node() {memset(mem,0,40);}

	node operator + (const node& that) const {

		register node ret; R p1=0,p2=0; for(R i=0;i<K;++i)

			if(mem[p1]>that.mem[p2]) ret.mem[i]=mem[p1++];

			else ret.mem[i]=that.mem[p2++];

		return ret;

	}

} sum[N<<2];

#define mem(i) sum[tr].mem[i]

inline void cov(int tr,int d) {tg[tr]+=d; for(R i=0;i<K;++i) if(mem(i)) mem(i)+=d;}

inline void spread(int tr) {cov(ls,tg[tr]),cov(rs,tg[tr]),tg[tr]=0;}

inline void build(int tr,int l,int r) {

	if(l==r) {mem(0)=g(); return ;} R md=l+r>>1;

	build(ls,l,md),build(rs,md+1,r); sum[tr]=sum[ls]+sum[rs];

}

inline void change(int tr,int l,int r,int LL,int RR,int d) {

	if(LL<=l&&r<=RR) return (void) cov(tr,d); if(tg[tr]) spread(tr); R md=l+r>>1;

	if(LL<=md) change(ls,l,md,LL,RR,d); if(RR>md) change(rs,md+1,r,LL,RR,d);

	sum[tr]=sum[ls]+sum[rs];

}

inline node query(int tr,int l,int r,int LL,int RR) {

	if(LL<=l&&r<=RR) return sum[tr]; if(tg[tr]) spread(tr);

	R md=l+r>>1; register node ret;

	if(LL<=md) ret=ret+query(ls,l,md,LL,RR);

	if(RR>md) ret=ret+query(rs,md+1,r,LL,RR);

	return ret;

}

inline void main() {

	n=g(),m=g(); build(1,1,n); for(R i=1;i<=m;++i) {

		R op=g(),l=g(),r=g(),d=g();

		if(op&1) change(1,1,n,l,r,d);

		else if(r-l+1<d) puts("-1");

			else printf("%d\n",query(1,1,n,l,r).mem[d-1]);

	}

}

} signed main() {Luitaryi::main(); return 0;}

T4 爆搜

没有看T4

结束前刘队说这不是爆搜吗？

一脸懵逼.jpg

第二天

????

真实爆搜

显然对于连通块一定是一个环或者一颗树，如果是环显然只能一个点取左右两条边，ans*2；要是一棵树那么总有一个点是没有被分配边的，ans*size.

#include<bits/stdc++.h>

#define ll long long

#define R register int

using namespace std;

namespace Luitaryi {

inline int g() { R x=0,f=1;

	register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;

	do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*f;

} const int N=100010,M=1e9+7;

int n,m,size,cnt; bool flg,vis[N]; ll ans=1;

int vr[N<<1],nxt[N<<1],fir[N];

inline void add(int u,int v) {

	vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;

	vr[++cnt]=u,nxt[cnt]=fir[v],fir[v]=cnt;

}

inline void dfs(int u,int fa) { vis[u]=true,++size;

	for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];

		if(v==fa) continue; if(vis[v]) {

            flg=true; continue;

        } dfs(v,u);

	}

}

inline void main() {

	n=g(),m=g(); for(R i=1,u,v;i<=m;++i) u=g(),v=g(),add(u,v);

	for(R i=1;i<=n;++i) if(!vis[i]) {

		flg=false,size=0; dfs(i,0);

		if(flg) ans=ans*2%M; else ans=ans*size%M;

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

}

} signed main() {Luitaryi::main(); return 0;}

总结：

不要死扣，灵活点。

难以不降智。

降智时不要考试要不难受好几天=。=

巴特西

HR#4 题解

T1 猜结论？猜nm！

T2 1.25e9跑过1.x s

T3 脑子是个好东西

T4 爆搜

总结：

最新文章

热门文章