总结

又是一日爆炸

\(T1\) 不出所料报 \(0\) 了？！

题目

\(T1\)

JZOJ 4315. Prime

暴力就好了？！

考场根本没想暴力

赛后发现暴力跑得贼快

只需二分一下组数的上界

然后 \(dfs\) 判断能否能成功分完组

跑时顺便统计答案就行了

\(Code\)

#include<cstdio>

#include<iostream>

using namespace std;

const int N = 20;

int n , a[N] , vis[N][N] , d[N][N] , cnt , ans , Mx , bz;

inline int gcd(int x , int y){return y == 0 ? x : gcd(y , x % y);}

inline void dfs(int x , int mid , int Max)

{

	if (mid > ans || mid == ans && Max >= Mx) return;

	if (cnt > mid) return;

	if (x > n)

	{

		bz = 1;

		if (ans > mid) ans = mid , Mx = Max;

		else if (ans == mid && Max < Mx) Mx = Max;

		return;

	}

	for(register int i = 1; i <= cnt; i++)

	{

		int fl = 0;

		for(register int j = 1; j <= d[i][0]; j++)

		if (!vis[x][d[i][j]])

		{

			fl = 1;

			break;

		}

		if (fl) continue;

		d[i][++d[i][0]] = x;

		dfs(x + 1 , mid , max(Max , d[i][0]));

		--d[i][0];

	}

	d[++cnt][++d[cnt][0]] = x;

	dfs(x + 1 , mid , max(Max , 1));

	--d[cnt][0] , --cnt;

}

int main()

{

	freopen("prime.in" , "r" , stdin);

	freopen("prime.out" , "w" , stdout);

	scanf("%d" , &n);

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

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

		for(register int j = 1; j <= n; j++)

		if (i != j) vis[i][j] = gcd(a[i] , a[j]) == 1 ? 1 : 0;

	ans = 0x3f3f3f3f , Mx = 0x3f3f3f3f;

	int l = 1 , r = n , mid;

	while (l <= r)

	{

		mid = (l + r) >> 1;

		cnt = bz = 0;

		dfs(1 , mid , 0);

		if (bz) r = mid - 1;

		else l = mid + 1;

	}

	printf("%d %d" , ans , Mx);

}

\(T2\)

JZOJ 4316. Isfind

一眼没看出？！序列自动机？！？

去一边，暴力又能过？！！

天！！！

而我想到了非暴力的解法，幸好过了，不然亏大了

只需记录每种字母在原串出现的先后位置

然后匹配时二分找位置判断就行了

\(Code\)

#include<cstdio>

#include<cstring>

using namespace std;

const int N = 1e5 + 5;

int n , m , a[30][N] , p[30];

char s[N];

inline int binary(int t , int x)

{

	int l = 0 , r = p[t] , mid , res = -1;

	while (l <= r)

	{

		mid = (l + r) >> 1;

		if (a[t][mid] >= x) res = a[t][mid] , r = mid - 1;

		else l = mid + 1;

	}

	return res;

}

int main()

{

	freopen("isfind.in" , "r" , stdin);

	freopen("isfind.out" , "w" , stdout);

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

	int len = strlen(s) , pos , pos1 , fl;

	for(register int i = 0; i < 28; i++) p[i] = -1;

	for(register int i = 0; i < len; i++) a[s[i] - 'a'][++p[s[i] - 'a']] = i;

	while (m--)

	{

		scanf("%s" , s);

		len = strlen(s);

		pos = -1;

		fl = 0;

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

		{

			pos1 = binary(s[i] - 'a' , pos + 1);

			if (pos1 == -1)

			{

				printf("N\n");

				fl = 1;

				break;

			}

			else pos = pos1;

		}

		if (!fl) printf("Y\n");

	}

}

实际上，它是序列自动机的模板题

所以上个序列自动机的代码

\(Code\)

#include<cstdio>

#include<cstring>

using namespace std;

const int N = 1e5 + 5 , INF = 0x3f3f3f3f;

int n , m , nxt[N][30];

char s[N];

int main()

{

	freopen("isfind.in" , "r" , stdin);

	freopen("isfind.out" , "w" , stdout);

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

	int len = strlen(s);

	for(register int i = 0; i <= 26; i++) nxt[len][i] = INF;

	for(register int i = len - 1; i >= 0; i--)

	{

		for(register int j = 0; j <= 26; j++) nxt[i][j] = nxt[i + 1][j];

		nxt[i][s[i] - 'a'] = i;

	}

	for(; m; --m)

	{

		scanf("%s" , s);

		len = strlen(s);

		int pos = -1 , fl = 0;

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

		{

			pos = nxt[pos + 1][s[i] - 'a'];

			if (pos == INF)

			{

				printf("N\n") , fl = 1;

				break;

			}

		}

		if (!fl) printf("Y\n");

	}

}

\(T3\)

JZOJ 4317. Divide

很显然 \(a_i\) 有用的部分是 \(\gcd(a_i,p)\)

然后我们就发现 \(a_i \times a_j \times a_k\) 相当于 \(p\) 的因数相乘

我们只要处理出 \(p\) 的所有因数，然后 \(O(tot^3)\) 枚举三个因数相乘

用桶记下每种因数在 \(a\) 出现的次数

然后分类讨论算贡献即可

\(Code\)

#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 3e4 + 5 , M = 1e6 + 5;

LL a[N] , pr[M] , buc[M] , p , ans;

int n , tot;

inline LL gcd(LL x , LL y){return y == 0 ? x : gcd(y , x % y);}

int main()

{

	freopen("divide.in" , "r" , stdin);

	freopen("divide.out" , "w" , stdout);

	scanf("%d%lld" , &n , &p);

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

	{

		scanf("%lld" , &a[i]);

		a[i] = gcd(a[i] , p);

		++buc[(int)a[i]];

	}

	for(register int i = 1; i <= p; i++)

	if (p % i == 0) pr[++tot] = i;

	for(register int i = 1; i <= tot; i++)

	for(register int j = i; j <= tot; j++)

	for(register int k = j; k <= tot; k++)

	if (pr[i] * pr[j] % p * pr[k] % p == 0)

	{

		if (i == j && i == k) ans += buc[pr[i]] * (buc[pr[i]] - 1) * (buc[pr[i]] - 2) / 6;

		else{

			if (i == j) ans += buc[pr[i]] * (buc[pr[j]] - 1) * buc[pr[k]] / 2;

			else if (i == k) ans += buc[pr[i]] * (buc[pr[k]] - 1) * buc[pr[j]] / 2;

			else if (j == k) ans += buc[pr[j]] * (buc[pr[k]] - 1) * buc[pr[i]] / 2;

			else ans += buc[pr[i]] * buc[pr[j]] * buc[pr[k]];

		}

	}

	printf("%lld" , ans);

}

巴特西

JZOJ 2020.08.03【NOIP提高组】模拟 &&【NOIP2015模拟11.5】

总结

题目

\(T1\)

JZOJ 4315. Prime

\(Code\)

\(T2\)

JZOJ 4316. Isfind

\(Code\)

\(Code\)

\(T3\)

JZOJ 4317. Divide

\(Code\)

最新文章

热门文章