20210817数论模拟赛

本文主要是介绍20210817数论模拟赛，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

数论啊！

赛时

知道考数论后很慌，这里基本停留在只能看懂题解的程度……
开题，果然发现一道题都不会QAQ

看到T1认为一定有规律。手推了\(1h\)后发现了(错误)的规律，打表并输出。

T2感觉可做，在写完T1后来想这道题。

可以确定：最佳决策点一定是经过某条线段的端点的。

于是想到\(O(n^3)\)的暴力：枚举两条线段，用斜截式\(y=kx+b\)确定此时的直线，再枚举线段判断是否有交。

期望得分:\(50\).

赛后：发现问题出在：\(y=kx+b\)不能表示与\(y\)轴平行直线！导致挂\(10pts\).

T3和T4不太会，这里见下面吧。

赛后

T1：卡特兰数。

以前并不知道这个名词。

数列大致如下：

\(1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190\cdots\)

递推式：

注意分母要求逆元。

#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f , N = 2e5+5 , mod = 1e9+7;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
	ll ret = 0 ; char ch = ' ' , c = getchar();
	while(!(c >= '0' && c <= '9')) ch = c , c = getchar();
	while(c >= '0' && c <= '9') ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar();
	return ch == '-' ? -ret : ret;
}
int n;
ll a[N],inv[N];
void init(){
	inv[1] = 1;
	for(int i = 2 ; i <= 2e5+1 ; i ++)
		inv[i] = ((mod-mod/i*inv[mod%i])%mod+mod)%mod;
	a[1] = 1;
	for(int i = 2 ; i <= 2e5 ; i ++)
		a[i] = ((a[i-1] * (4*i-2))%mod*inv[i+1]+mod)%mod;
}
void work(){
	n = read();
	printf("%d\n",a[n]);
}
signed main(){
//	fo("notitle");
	int T = read();
	init();
	while(T--)
		work();
}

T2

思路是对的，考虑优化：

寻找线段中的一个点作为基准点，处理出其他点到基准点的斜率\(k\)，为避免以上出现的问题，将斜率转化为\(\dfrac1k\)处理。

后离散化，转化为"区间修改+区间查询最大值"。

使用线段树。

注意细节。

#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f , N = 1e3+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
	ll ret = 0 ; char ch = ' ' , c = getchar();
	while(!(c >= '0' && c <= '9')) ch = c , c = getchar();
	while(c >= '0' && c <= '9') ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar();
	return ch == '-' ? -ret : ret;
}
int n;
struct node{int x1,x2,y;ll v;}a[N];
inline bool operator < (const node a,const node b){return a.y < b.y;}
ll tree[N<<4],lazy[N<<4],ans = -INF;
inline void Add(int k,int l,int r,ll v){
	lazy[k] += v;
	tree[k] += v;
}
inline void pushdown(int k,int l,int r){
	if(!lazy[k])return;
	int mid = (l + r) >> 1;
	Add(k<<1,l,mid,lazy[k]);
	Add(k<<1|1,mid+1,r,lazy[k]);
	lazy[k] = 0;
}
void modify(const int k,const int l,const int r,const int x,const int y,const ll v){
	if(x <= l && r <= y) {Add(k,l,r,v);return;}
	int mid = (l + r) >> 1;
	pushdown(k,l,r);
	if(x <= mid)modify(k<<1,l,mid,x,y,v);
	if(y > mid)modify(k<<1|1,mid+1,r,x,y,v);
	tree[k] = max(tree[k<<1],tree[k<<1|1]);
//	printf("  Tree[%d] : [%d,%d] : %lld\n",k,l,r,tree[k]);
}
ll query(const int k,const int l,const int r,const int x,const int y){
	if(x <= l && r <= y) return tree[k];
	int mid = (l + r) >> 1;
	ll ret = 0;
	pushdown(k,l,r);
	if(x <= mid) ret = max(ret,query(k<<1,l,mid,x,y));
	if(y > mid) ret = max(ret,query(k<<1|1,mid+1,r,x,y));
	return ret;
} 

double d[N][2],p[N<<2];
int vis[N],cnt;
void build(int u,int x){
	memset(tree,0,sizeof(tree)),memset(lazy,0,sizeof(lazy));
	cnt = 0;
//	printf("Start from (%d,%d)\n",x,a[u].y);
	for(int i = 1 ; i <= n ; i ++)
		if(i != u && a[i].y != a[u].y)
			vis[i] = u,
			d[i][0] = p[++cnt] = 1.0*(x-a[i].x1)/(a[u].y-a[i].y),
			d[i][1] = p[++cnt] = 1.0*(x-a[i].x2)/(a[u].y-a[i].y);
	sort(p+1,p+cnt+1);
	int tot = unique(p+1,p+cnt+1)-p-1;
//	printf("tot = %d\n",tot);
	for(int i = 1 ; i <= n ; i ++)
		if(i != u && vis[i] == u){
			int l = lower_bound(p+1,p+tot+1,d[i][0])-p,
				r = lower_bound(p+1,p+tot+1,d[i][1])-p;
			ll  v = a[i].v;
			if(l > r)swap(l,r),swap(d[i][0],d[i][1]);
//			printf("   (%d,%d)(%d) -> (%d->%d) as (%.2lf -> %.2lf) : %lld\n",a[i].x1,a[i].x2,a[i].y,l,r,d[i][0],d[i][1],v);
			modify(1,1,tot,l,r,v);
		}
	ans = max(ans,query(1,1,n,1,n)+a[u].v);
//	printf("  now ans = %lld\n",ans);
}
signed main(){
//	fo("oil");
	n = read();
	for(int i = 1 ; i <= n ; i ++) {
		a[i].x1 = read() , a[i].x2 = read();
		if(a[i].x1 > a[i].x2)swap(a[i].x1,a[i].x2);
		a[i].y = read() , a[i].v = a[i].x2 - a[i].x1;
	}
	sort(a+1,a+n+1); 
//	for(int i = 1 ; i <= n ; i ++)
//		printf("  %d:(%d,%d)->(%d,%d),%lld\n",i,a[i].x1,a[i].y,a[i].x2,a[i].y,a[i].v);
	
	for(int i = 1 ; i <= n ; i ++){
		build(i,a[i].x1);
		build(i,a[i].x2);
	}
	
	printf("%lld",ans);
	return 0;
}

T3

一道博弈论题。

对于\(S = \{1\}\)的情况，直接给所有同奇偶性编号的分发1即可。答案为\(\lceil\dfrac n2\rceil\).

对于其余情况：

#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f , N = 1e3+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
	ll ret = 0 ; char ch = ' ' , c = getchar();
	while(!(c >= '0' && c <= '9')) ch = c , c = getchar();
	while(c >= '0' && c <= '9') ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar();
	return ch == '-' ? -ret : ret;
}
ll n,s;
void work(){
	n = read() , s = read();
	if(s)
		printf("%d\n",(n+1)>>1);
	else{
		if(n&1)printf("%d\n",n>>1);
		else{
			n >>= 1;
			int t = 0;
			while((1<<t) <= n)
				t++;
			t--;
			n -= 1<<t;
			printf("%d\n",n);
		}
	}
}
signed main(){
//	fo("distribute");
	int T = read();
	while(T--)
		work();
}

T4

感觉推不太明白这道题，这里放上题解做法吧……

#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f , N = 1e3+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
	ll ret = 0 ; char ch = ' ' , c = getchar();
	while(!(c >= '0' && c <= '9')) ch = c , c = getchar();
	while(c >= '0' && c <= '9') ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar();
	return ch == '-' ? -ret : ret;
}
ll a,b,c;
ll ans,w[110];
int tot;
bool solve(ll fa,ll fb){
	if(!fa && !fb){ans ++;return 1;}
	if(!fa || !fb) return 0;
	
	ll v = fb % b;
	if(v)
		if(!((fa - v) % a)){
			w[++tot] = v;
			return solve((fa-v)/a,(fb-v)/b);
		}
		else return 0;
	else{
		bool flag = 0;
		int pos = ++tot;
		if(!(fa % a))
			w[pos] = 0,
			flag = solve(fa/a,fb/b);
		if(fa == b && fb == b){
			ans ++;
			if(!flag)
				w[pos] = b,
				tot = pos;
			return 1;
		}
		return flag;
	}
}
void work(){
	a = read() , b = read() , c = read();
	tot = -1;
	ans = 0;
	if(b == 1){puts(c == 1 ? a == 1 ? "-1" : "1\n0 1" : "0");return;}
	
	solve(b,c);
	printf("%lld\n",ans);
	if(!ans)return;
	if(tot == -1)
		tot = 0,w[0] = b;
	
	printf("%d ",tot);
	for(int i = tot ; i >= 0 ; i --)
		printf("%lld ",w[i]);
	puts("");
}
signed main(){
//	fo("polynomial");
	int T = read();
	while(T--)
		work();
}

集训第二阶段就剩一天了，加油QAQ

这篇关于20210817数论模拟赛的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！