毒瘤模拟赛的题解

发布于 2019-08-13  506 次阅读


上午场

T1 相反数

这是一道很傻的题

首先要排序+去重

对于30%的数据,我们只需要$latex n^3$的暴力枚举就好了。代码不想写

对于70%的数据,在$latex n^2$枚举下加上二分查找就好了

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define int long long

using namespace std;

int n,a[10009];

int find(int x)
{
	int l,r,m;
	x=0-x;
	l=1;
	r=n;
	while (l<r)
	{
		if (r-l<=10)
		{
			for (int i=l;i<=r;i++)
				if (a[i]==x) return i;
			return 101000;
		}
		m=(l+r)/2;
		if (a[m]>x) r=m-1;
		else l=m;
	}
	if (a[m]==x) return m;
	return 101000;
}

signed main()
{
	int k,ans;
	cin>>k;
	while (k>0)
	{
		cin>>n;
		ans=0;
		k--;
		for (int i=1;i<=n;i++)
			cin>>a[i];
		sort(a+1,a+n+1);
		int cnt=1;
		while (cnt<n)
		{
			if (a[cnt]==a[cnt+1])
			{
				for (int i=cnt;i<n;i++)
					a[i]=a[i+1];
				n--;
			}
			cnt++;
		}
		for (int i=1;i<=n;i++)
		{
			for  (int j=i+1;j<=n;j++)
			{
				int x=find(a[i]+a[j]);
				if (x!=101000 && x>j)
				{
					ans++;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

对于100%的数据,我们发现在排序结束后枚举前两个,第三个必定在第二个之后,否则就重复了。那么我们确定了第一个点以后,只需要在他之后的数中确定头和尾,两端向中间找,就可以在$latex n^2$复杂度下找到正确解了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define N 101000

using namespace std;

int a[N],n,t;

int main()
{
	cin>>t;
	while (t--)
	{
		cin>>n;
		for (int i=1;i<=n;i++)
			cin>>a[i];
		sort(a+1,a+n+1);
		n=unique(a+1,a+n+1)-(a+1);
		int ans=0;
		for (int i=1;i<n;i++)
		{
			int l=i+1,r=n;
			while (l<r)
			{
				if (a[i]+a[l]+a[r]==0)	ans++,l++;
				if (a[i]+a[l]+a[r]>0) r--;
				if (a[i]+a[l]+a[r]<0) l++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

T2 数列

对于30%的数据,代码已经给了,虽然有点小错误(雾

#include<iostream>
#include<cstdio>
using namespace std;
int cnt[10010];
int main()
{
	long long g,a,b,c,n,p,ans;
	cin>>g>>a>>b>>c>>n>>p;
	ans=g;
	for (int i=2;i<=n;i++)
	{
		ans=a*ans*ans+b*ans+c;
		ans=ans % p;
	}
	cout<<(ans%p+p)%p<<endl;
	return 0;
}

对于100%的数据:

我们发现数列到最后的输出是由规律的,这样的原因是每次对于p取模,取到p次以后一定会在0~p-1内出现重复的数,而对于重复的数,函数的值是一样的,这样输出就会有规律了。

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int mod = 2097152;

int F(long long x,int a,int b,int c,int p)
{
	long long ans=0;
	ans=a*x%p*x%p;
	ans=(ans+b*x%p)%p;
	ans=(ans+c)%p;
	return ans;
}

int g1, a, b, c, p;
long long n;
int f[mod];
int g[mod];

int main()
{
	cin>>g1>>a>>b>>c>>n>>p;
	g1=(g1%p+p)%p;
	a=(a%p+p)%p;
	b=(b%p+p)%p;
	c=(c%p+p)%p;
	memset(g,0,sizeof(g));
	f[1]=g1,g[g1]=1;
	int point=0;
	for (int i=2;true;i++)
	{
		if (i > n) break;
		f[i]=F(f[i-1],a,b,c,p);
		if (g[f[i]])
		{
			point=i;
			break;
		}
		g[f[i]]=i;
	}
	if (!point)
		cout<<f[n]<<endl;
	else
	{
		int m=g[f[point]]-1,l=point-g[f[point]];
		n-=m;
		n%=l;
		if (n==0) n=l;
		cout<<f[m+n]<<endl;
	}
	return 0;
}

T3

对于40%的数据,只需要一个搜索就好了

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int x1,x2,y1,y2;
int map[520][520];
bool f[520][520];
bool p;

void dfs(int x,int y)
{
	if (x>x2 || y>y2) return;
	if (x==x2 && y==y2) {p=true; return;}
	if (f[x][y]) return;
	f[x][y]=true;
	if (map[x+1][y]==0 && x+1<=x2) dfs(x+1,y);
	if (map[x][y+1]==0 && y+1<=y2) dfs(x,y+1);
	return;
}
int main()
{
	int n,m,q;
	char c;
	cin>>n>>m;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			cin>>c;
			if (c=='.') map[i][j]=0;
			if (c=='#') map[i][j]=1;
		}
	cin>>q;
	for (int i=1;i<=q;i++)
	{
		cin>>x1>>y1>>x2>>y2;
		p=false;
		memset(f,false,sizeof(f));
		dfs(x1,y1);
		if (p) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

对于100%的数据:

我们希望我们一次预处理能做出多种询问,那么我们用分治的方法做:

我们可以将这个矩阵从中间劈成两瓣,那么我们的询问就会分成三种:

  • 1. 起点和终点都在上半方Q1;

  • 2.起点和终点都在下半方Q3;

  • 3.起点在上方,终点在下方或起点在下方,终点在上方Q2;

img

我们开两个数组 up [i][j][k] 表示从上半部分的点(i,j)能否走到点(mid,k)down [i][j][k] 表示从下半部分的点(i,j)能否走到点(mid,k)

对于前两种情况,我们直接在 up 或 down数组里面找就好了;

对于第三种情况,既然是从上半面某个点到下半面某个点的话,那么不管怎么走,一定是会经过分界线上的某个点,也就是说如果起点(x1,y1)到终点(x2,y2)一定会经过某个点(mid,k);换句话说我们如果(x1,y1)能够到达(x2,y2)的话,那么中间必然有一点(mid,k)满足 up[x1][y1][k]==1 && down[x2][y2][k]==1

img

流程:

void 分治()
{
	把迷宫劈成两半
	计算预处理数组up
	计算预处理数组down
	把询问分成三部分:Q1,Q2,Q3
	Q1,Q2用递归解决
	Q3用上述方法判断
}

怎么做这两个数组的预处理?

像过河卒一样,我们先看(i,j)往右走能不能走通,再看往下走能不能走通,只要有一个方向可以走通就行。

up[i][j][k]=up[i+1][j][k] | up[i][j+1][k]
down[i][j][k]=down[i-1][j][k] | down[i][j-1][k]

时间复杂度$latex O( (\frac{N^3}{64} + Q) \times log_n);$

#include <cstdio>
#include <vector>
#include <bitset>
using std::vector;
using std::bitset;
const int QUERY_SIZE = 600006;
const int MAP_SIZE = 511;

int N, M, Q;
char map[MAP_SIZE][MAP_SIZE];
int ans[QUERY_SIZE];
bitset<MAP_SIZE> up[MAP_SIZE][MAP_SIZE], down[MAP_SIZE][MAP_SIZE];
struct query {
	int x1, y1, x2, y2, id;
};

query q;
void solve(vector<query> v, int l, int r) {
	int m = (l + r) >> 1;
	if (l > r) return ;
	for (int i = m; i >= l; i--)
		for (int j = M; j >= 1; j--) {
			up[i][j] = 0;
			if (map[i][j] == '.') {
				if (i == m) up[i][j].set(j);
				else up[i][j] |= up[i + 1][j];
				if (j != M) up[i][j] |= up[i][j + 1];
			}
		}
	for (int i = m; i <= r; i++)
		for (int j = 1; j <= M; j++) {
			down[i][j] = 0;
			if (map[i][j] == '.') {
				if (i == m) down[i][j].set(j);
				else down[i][j] |= down[i - 1][j];
				if (j != 1) down[i][j] |= down[i][j - 1];
			}
		}
	vector<query> vl, vr;
	for (vector<query>::iterator it = v.begin(); it != v.end(); it++) {
		q = *it;
		if (q.x2 < m) vl.push_back(q);
		else if (q.x1 > m) vr.push_back(q);
		else ans[q.id] = (up[q.x1][q.y1] & down[q.x2][q.y2]).any();
	}
	solve(vl, l, m - 1);
	solve(vr, m + 1, r);
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++)
		scanf("%s", map[i] + 1);
	vector<query> v;
	scanf("%d", &Q);
	for (int i = 0; i < Q; i++) {
		scanf("%d %d %d %d", &q.x1, &q.y1, &q.x2, &q.y2);
		q.id = i;
		v.push_back(q);
	}
	solve(v, 1, N);
	for (int i = 0; i < Q; i++)
		puts(ans[i] ? "Yes" : "No");
	return 0;
}

img img img

下午场

T4

这个题第一个想到的思路是tarjan缩点+DAG上DP来着。。。

但是很显然我写不出来(虽然思路是对的

这道题的正解是直接搜索(没错就是这么简单

我们只需要找出从最大点走到最小点或者从最小点走到最大点就行了

假设我们已经找到了一个使得(最大值 - 最小值)最大的一条路径:

img

考虑到最大的点前面,最小的点后面再走路径的话是完全可以的,对答案是没有影响的:

img

我们要求的就是找出从最大点走到最小点或者从最小点走到最大点两种路径的答案;

所以我们可以考虑算这么一个东西:

枚举每一个点,将当前点看作是最大值的话,是不是要找能到的所有路径中的最小值?

但是不知道这个最小值是在当前点上方还是下方(如果是在上面的话,就是从最小值走到了最大值;如果在下面的话,就是从最大值走到了最小值),所以我们要向上向下各走一边找个最小值:

  • 1.每个点向后走;

  • 2.每个点向前走;

从每个点出发,能走到的所有点当中最小的是多少,以及从这个点向回走的最小值:

我们有一种暴力方法:枚举每个点作为起点或终点,直接去枚举min是哪个点。

怎么求这个点向后走的最小值,直接 bfs 就好了;期望得分80 pts

优化

这样显然会出些小问题(也有可能不会

发现对于每个点,每次都 bfs,算他正着走和反着走的答案是算法慢的原因。而先算1号点再算2号点和倒过来是一样的。所以我们直接把点权从小到大排序,然后一个点一个点去处理所有的答案。

和刚刚处理有什么区别?

这样我们 bfs 的时候就不用再去求最小值了,对每个点我们只要遇到已经算出答案的点就可以停了。

每个点只被算过一次,所以是线性时间复杂度$latex O(n+m)$

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int maxn=100010;
const int maxm=500010;

int n,m,en,result[maxn],z[maxn],y[maxn];

struct edge
{
	int s,e;
	bool rev;
	edge *next;
}*v[maxn],ed[maxm<<1];

void add_edge(int s,int e)
{
	en++;
	ed[en].next=v[s];v[s]=ed+en;v[s]->e=e;v[s]->rev=false;
	en++;
	ed[en].next=v[e];v[e]=ed+en;v[e]->e=s;v[s]->rev=true;
}

bool cmp(int a,int b)
{
	return z[a]<z[b];
}

void bfs(int p)
{
	queue<int> q;
	if (!result[p]) result[p]=z[p];
	q.push(p);
	while (q.size())
	{
		int now=q.front();
		q.pop();
		for (edge *e=v[now];e;e=e->next)
			if (!e->rev && !result[e->e])
			{
				result[e->e]=z[p];
				q.push(e->e);
			}
	}
	q.push(p);
	while (q.size())
	{
		int now=q.front();
		q.pop();
		for (edge *e=v[now];e;e=e->next)
			if (e->rev && !result[e->e])
			{
				result[e->e]=z[p];
				q.push(e->e);
			}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int a=1;a<=n;a++)
		scanf("%d",&z[a]);
	for (int a=1;a<=m;a++)
	{
		int s,e;
		scanf("%d%d",&s,&e);
		add_edge(s,e);
	}
	for (int a=1;a<=n;a++)
		y[a]=a;
	sort(y+1,y+n+1,cmp);
	for (int a=1;a<=n;a++)
		bfs(y[a]);
	int ans=0;
	for (int a=1;a<=n;a++)
	   ans=max(ans,z[a]-result[a]);	
	printf("%d\n",ans);

	return 0;
}

T5

这道题很显然是一道状压DP

只需要从数据范围里面就可以看出来

状态定义:f [ s ] ,s 所对应的人之间,能不能通过交换变得合法;

发现我们只需要排序就好了,看看相邻的两两间相差是否小于 c;

最坏的情况:n-1 次;

我们找到 c1 这把眼镜片,如果正好又拿着 c2 这个眼镜片的话就不用换了,如果不是拿着 c2 这个眼镜片,那就换过来,这样的话我们就可以通过一次操作搞定第一个人;

每次交换一定能搞定一个人;

最后一次交换能搞定两人,所以所需要的次数最多为 n-1;

那么什么时候答案小于 n-1?

如果一个人拿的眼镜本来就合法,那就不用换了;

g [ s ] 我要让 s 这一堆人合法所需要的最小步数;

如果 s 内部能够自己解决,那么 g [ s ] 最大就是 k-1;

我们需要找比 k 更小的数;

看到数据最多是 16,这告诉我们 3n 也是可行的,我们应该去枚举子集:

如果我们能将一个状态 s 分成 n/2

问题转化成:最多能将 n 个人分成多少个部分,使得他们内部都能通过换镜片来解决问题;

如果我们能将 n 分成 k 部分,答案就是 n - k;

重新定义状态:g [ s ] 我最多将 s 分成多少个部分使其能自己解决;

枚举 s 的所有子集,求出子集和剩下的部分能分成多少个部分取个max;

答案就是: n - g [ 2n - 1 ];

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#define maxn 20
#define INF 0x3f3f3f3f

using namespace std;

int n,d,z[maxn][2],y[maxn<<1],f[1<<maxn];

int main()
{
   cin>>n>>d;
   for (int i=1;i<=n;i++)
   	cin>>z[i][0]>>z[i][1];
   for (int i=0;i<(1<<n);i++)//枚举状态 
   {
   	int cnt=0;
   	for (int j=1;j<=n;j++)
   		if (i&(1<<(j-1)))
   		{
   			y[++cnt]=z[j][0];
   			y[++cnt]=z[j][1];
   		}//有这一位的就加上这个人的眼镜 
   	sort(y+1,y+cnt+1);
   	bool able=true;
   	for (int j=1;j<=cnt;j+=2)
   		if (y[j+1]-y[j]>d) able=false;
   	if (able) f[i]=1;
   	else f[i]=-INF;//判断
   }
   f[0]=0;
   for (int i=1;i<(1<<n);i++)
   	for (int j=i;j;j=(j-1)&i)
   		f[i]=max(f[i],f[i^j]+f[j]);//求最多能分成多少个部分,进行DP求最大值 
   if (f[(1<<n)-1]<0) cout<<-1<<endl;
   else cout<<n-f[(1<<n)-1]<<endl;
   return 0;
}

T6

好吧还是写一下思路

两个斐波那契数列的和仍然是个伪斐波那契数列;

打标记的时候只需要求前两个数加了多少就好了。

所以我们线段树上要记上两个东西:给第一个数加上c1,给第二个数加上c2;

这段区间的和会怎么变?

只和三个值有关:c1,c2,这段区间的长度。

#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int N = 1e5+5;
ll a[N], sum[N], fib[2 * N];
int n, Q;
void init() {
    fib[1] = fib[2] = 1; for(int i = 3; i < 2 * N; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
}
inline ll getK(ll a, ll b, int k) {
    if(k == 1) return a;
    if(k == 2) return b;
    return (a * fib[k - 2] % MOD + b * fib[k - 1] % MOD) % MOD;
}
inline ll getsum(ll a, ll b, int k){
    if(k == 1) return a;
    if(k == 2) return (a + b) % MOD;
    return (a * fib[k] % MOD + b * fib[k + 1] % MOD - b + MOD) % MOD;
}
struct Node{
    int l, r, len;
    ll a, b, sum;
} d[4*N];
void build(int rt, int l, int r) {
    d[rt].l = l; d[rt].r = r; d[rt].len = r - l + 1;
    if (l != r) {
        int mid = (l + r) / 2;
        build(2 * rt, l, mid);
        build(2 * rt + 1, mid + 1, r);
    }
}
void push_down(int rt) {
    Node &lson = d[2 * rt], &rson = d[2 * rt + 1];
    if(d[rt].a || d[rt].b) {
        lson.a = (lson.a + d[rt].a) % MOD;
        lson.b = (lson.b + d[rt].b) % MOD;
        lson.sum = (lson.sum + getsum(d[rt].a, d[rt].b, lson.len)) % MOD;
        ll ra = getK(d[rt].a, d[rt].b, lson.len + 1), rb = getK(d[rt].a, d[rt].b, lson.len + 2);
        rson.a = (rson.a + ra) % MOD;
        rson.b = (rson.b + rb) % MOD;
        rson.sum = (rson.sum + getsum(ra, rb, rson.len)) % MOD;
    	d[rt].a = d[rt].b = 0;
    }
}
void update(int rt, int L, int R, int x) {
    if (L <= d[rt].l && d[rt].r <= R) {
        d[rt].a = (d[rt].a + fib[d[rt].l - L + x]) % MOD;
        d[rt].b = (d[rt].b + fib[d[rt].l - L + 1 + x]) % MOD;
        d[rt].sum = (d[rt].sum + getsum(fib[d[rt].l - L + x], fib[d[rt].l - L + 1 + x], d[rt].len)) % MOD;
    	return ;
    }
    push_down(rt);
    int mid = (d[rt].l + d[rt].r) / 2;
    if (L <= mid) update(2 * rt, L, R, x);
    if (R > mid) update(2 * rt + 1, L, R, x);
    d[rt].sum = (d[2 * rt].sum + d[2 * rt + 1].sum) % MOD;
}
ll query(int rt, int L, int R) {
    if (L <= d[rt].l && d[rt].r <= R) return d[rt].sum;
    push_down(rt);
    int mid = (d[rt].l + d[rt].r) / 2;
    ll ans = 0;
    if (L <= mid) ans += query(2 * rt, L, R);
    if (R > mid) ans += query(2 * rt + 1, L, R);
    return ans % MOD;
}
int main(){
    scanf("%d%d", &n, &Q);
    init();
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        a[i] = (a[i - 1] + a[i]) % MOD;
    }
    build(1, 1, n);
    while(Q--) {
        int op, l, r, x;
        scanf("%d%d%d", &op, &l, &r);
        if (op == 2) {scanf("%d", &x); update(1, l, r, x);}
        else {
            ll v1 = query(1, l, r), v2 = (a[r] - a[l - 1] + MOD) % MOD;
            printf("%lld\n", (v1 + v2) % MOD);
        }
    }
    return 0;
}


最美好的事情就是和OI一起成长呢。