省选模拟测试10

期望得分:(100+50+20 = 170)

实际得分:(0+10+10=20)

wdnmd,挂了 (150) 多分,就nm离谱。

(T1) 原题,毒瘤出题人空间只给了 ( 256MB) ,全开 ( long long) 炸空间了。

(T2) 本来打了个 (O(n^2)) 的暴力,但没写过哈希判回文串,这次第一次写就写出锅了,难受。

(T3) 考试的时候推出来了个柿子,但写着写着发现神 (tm) 没有逆元,然后就不会做了。

T1 没睡醒

题意描述

(n)座城市,(m)个民族。这些城市之间由(n-1)条有边权道路连接形成了以城市(1)为根的有根树。

每个城市都是某一民族的聚居地,(Winniechen)知道第(i)个城市的民族是(A_i),人数是(1)

我们定义一个民族(x)的来往程度(f(x))为民族为(x)的点两两之间的距离之和,距离定义为树上两点间最短路距离。

他想知道以(i)为根的子树内来往程度最大的民族(x)是多少,如果有多个,求编号最小。

以及对于给定的(k_i),求(i)子树内编号的(k_i)小民族(y)(f(y))

但是(Winniechen)昨天打了(CF)现在还没睡醒, 就将这个问题就丢给了你。

数据范围:(nleq 10^5)

solution

原题,不说了。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
const int N = 1e5+10;
int n,m,tot,u,v,w,cnt,maxn;
int head[N],a[N],k[N],rt[N];
LL dep[N],ans1[N],ans2[N];
struct node
{
    int to,net,w;
}e[N<<1];
struct Tree
{
    int lc,rc,id;
    int siz,tag;
    LL sum,w;
}tr[10000010];
inline int read()
{
    int s = 0,w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
    return s * w;
}
void add(int x,int y,int w)
{
    e[++tot].to = y;
    e[tot].w = w;
    e[tot].net = head[x];
    head[x] = tot;
}
void up(int o)
{
    tr[o].tag = tr[tr[o].lc].tag + tr[tr[o].rc].tag;
    tr[o].sum = max(tr[tr[o].lc].sum,tr[tr[o].rc].sum);
    if(tr[o].sum == 0)
    {
        if(tr[tr[o].lc].id) tr[o].id = tr[tr[o].lc].id;
        else tr[o].id = tr[tr[o].rc].id;
    }
    else tr[o].id = tr[o].sum == tr[tr[o].lc].sum ? tr[tr[o].lc].id : tr[tr[o].rc].id;
}
void insert(int &o,int l,int r,int x,int val)
{
    if(!o) o = ++cnt;
    if(l == r)
    {
        tr[o].siz++;
        tr[o].w += val;
        tr[o].tag |= 1;
        tr[o].id = l;
        return;
    }
    int mid = (l + r)>>1;
    if(x <= mid) insert(tr[o].lc,l,mid,x,val);
    if(x > mid) insert(tr[o].rc,mid+1,r,x,val);
    up(o);
}
void merage(int &x,int y,int l,int r,int Lca)
{
    if(!x){x = y; return;}
    if(!y) return;
    if(l == r)
    {
        tr[x].sum = 1LL * (tr[x].sum + tr[y].sum + tr[x].siz * tr[y].w + tr[y].siz * tr[x].w - 2 * tr[x].siz * tr[y].siz * dep[Lca]);
        tr[x].siz += tr[y].siz;
        tr[x].w += tr[y].w;
        tr[x].tag |= tr[y].tag;
        if(tr[x].tag == 1) tr[x].id = l;
        else tr[x].id = 0;
        return;
    }
    int mid = (l + r)>>1;
    merage(tr[x].lc,tr[y].lc,l,mid,Lca);
    merage(tr[x].rc,tr[y].rc,mid+1,r,Lca);
    up(x);
}
LL query(int o,int l,int r,int k)
{
    if(l == r) return tr[o].sum;
    int mid = (l + r)>>1;
    int num = tr[tr[o].lc].tag;
    if(k <= num) return query(tr[o].lc,l,mid,k);
    else return query(tr[o].rc,mid+1,r,k-num);
}
void dfs1(int x,int fa)
{
    for(int i = head[x]; i; i = e[i].net)
    {
        int to = e[i].to;
        if(to == fa) continue;
        dep[to] = dep[x] + e[i].w;
        dfs1(to,x);
    }
}
void dfs2(int x,int fa)
{
    insert(rt[x],1,maxn,a[x],dep[x]);
    for(int i = head[x]; i; i = e[i].net)
    {
        int to = e[i].to;
        if(to == fa) continue;
        dfs2(to,x);
        merage(rt[x],rt[to],1,maxn,x);
    }
    ans1[x] = tr[rt[x]].id;
    if(tr[rt[x]].tag < k[x]) ans2[x] = -1;
    else ans2[x] = query(rt[x],1,maxn,k[x]);
}
signed main()
{
    freopen("city.in","r",stdin);
    freopen("city.out","w",stdout);
    n = read();
    for(int i = 1; i <= n-1; i++)
    {
        u = read(); v = read(); w = read();
        add(u,v,w); add(v,u,w);
    }
    for(int i = 1; i <= n; i++) a[i] = read(), maxn = max(maxn,a[i]);
    for(int i = 1; i <= n; i++) k[i] = read();
    dfs1(1,0); dfs2(1,0);
    for(int i = 1; i <= n; i++) printf("%lld %lld
",ans1[i],ans2[i]);
    fclose(stdin); fclose(stdout);
    return 0;
}

T2 调不出来

题意描述

(lizhenhao)点开了一道题:

给一个长度为(n)的字符串(S),有(n-2)次修改操作,第(i)次操作会将第(i+1)个字符变成(w_i)

你需要在每次操作之后(包括未操作时)输出这个字符串的最长回文子串,即修改对后续有影响。

(lizhenhao)马上会了(ziptree)维护回文仙人掌的做法,但是他调不出来了,于是丢给了你。

对于你来说,只需要输出一个(ans),表示每次操作之后的答案的最大值就可以了。

数据范围:(nleq 10^5)

solution

(O(n^2)) 的暴力想必都会写吧,全机房就我一个写炸了。

我们记原串 (S)(A), 修改后的字符串 (S)(B)

那样例举例就是:

字符串 A: ABAECB
字符串 B: ABCDEB

(pre(i,j)) 表示字符串 (A) 的第 (i) 个字符到第 (j) 个字符所组成的字符串。

(suf(i,j)) 为字符串 (B) 的第 (i) 个字符到到第 (j) 个字符所组成的字符串。

不难发现每次操作后所形成的字符串实际上是由 (pre(1,i) + suf(i+1,n)) 拼起来的。

然后我们要求的就是 (pre(1,i)+suf(i+1,n)) 的最长回文子串。

假设最长的回文子串为 (pre(i,j) + suf(j+1,k))

(len = k-j), 不难发现整个字符串可以分为三部分 (pre(i,i+len-1) + pre(i+len,j) + suf(j+1,k))

结合图理解一下(画的图好丑):

图中的 ①②③分别表示 (pre(i,i+len-1))(pre(i+len,j))(suf(j+1,k)) 三部分。

显然 (pre(i,i+len-1))(suf(j+1,k)) 互为反串,(pre(i+len,j)) 为回文串。

我们可以对 (A)(manacher) 求出回文半径 (R[i]), (pre(i-R[i]+1,i+R[i]-1)) 构成了中间的回文串,之后二分出 (len) 即可。

判断两个串是否为反串可以用 (Hash) 来判断。

同理中间的回文串也可以是 (B) 的一部分,在对 (B) 跑一边上述过程即可。

时间复杂度:(O(nlogn))

代码实现起来比较恶心,各种边界问题恶心的要死,我调代码的时候,和 (std) 的代码瞅了半天。

code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ull unsigned long long
const int base = 321;
const int N = 5e5+10;
int n,ans,len1,len2,R[N];
ull pre[N],suf[N],mi[N];
char a[N],b[N],s1[N],s2[N],s[N];
ull get_pre(int l,int r)
{
    return pre[r] - pre[l-1] * mi[r-l+1];
}
ull get_suf(int l,int r)
{
    return suf[l] - suf[r+1] * mi[r-l+1];
}
int main()
{
//	freopen("str.in","r",stdin);
//	freopen("str.out","w",stdout);
    scanf("%d%s",&n,s+1); n--;
    mi[0] = 1; a[1] = s[1];
    for(int i = 1; i <= n; i++) b[i] = s[i+1];
    for(int i = 2; i <= n; i++)
    {
        char ch; cin>>ch;
        a[i] = ch;
    }
    for(int i = 1; i <= 2*n; i++) mi[i] = mi[i-1] * base;
    s1[++len1] = '#';
    for(int i = 1; i <= n; i++)
    {
        s1[++len1] = a[i];
        s1[++len1] = '#';
    }
    s2[++len2] = '#';
    for(int i = 1; i <= n; i++)
    {
        s2[++len2] = b[i];
        s2[++len2] = '#';
    }
    for(int i = 1; i <= n; i++) pre[i] = pre[i-1] * base + a[i];
    for(int i = n; i >= 1; i--) suf[i] = suf[i+1] * base + b[i];
    int p = 1, mx = 1;
    for(int i = 1; i <= len1; i++)
    {
        R[i] = i < mx ? min(mx-i,R[2*p-i]) : 1;
        while(s1[i-R[i]] == s1[i+R[i]]) R[i]++;
        if(i+R[i]-1 > mx)
        {
            mx = i+R[i]-1;
            p = i;
        }
        ans = max(ans,R[i]-1);
        int u = ((i-R[i]+1)>>1)+1, v = (i+R[i]-1)>>1;
        int l = 1, r = min(u-1,n-v+1)+1, res = 0;
        while(l < r)
        {
            int mid = (l+r)>>1;
            if(get_pre(u-mid,u-1) == get_suf(v,v+mid-1))
            {
                l = mid + 1;
                res = mid;
            }
            else r = mid - 1;
        }
        ans = max(ans,v-u+1+2*res);
    }
    memset(R,0,sizeof(R));
    p = 1, mx = 1;
    for(int i = 1; i <= len1; i++)
    {
        R[i] = i < mx ? min(mx-i,R[2*p-i]) : 1;
        while(s2[i-R[i]] == s2[i+R[i]]) R[i]++;
        if(i+R[i]-1 > mx)
        {
            mx = i+R[i]-1;
            p = i;
        }
        ans = max(ans,R[i]-1);
        int u = ((i-R[i]+1)>>1)+1, v = (i+R[i]-1)>>1;
        int l = 1, r = min(u,n-v)+1, res = 0;
        while(l <= r)
        {
            int mid = (l+r)>>1;
            if(get_pre(u-mid+1,u) == get_suf(v+1,v+mid))
            {
                l = mid + 1;
                res = mid;
            }
            else r = mid - 1;
        }
        ans = max(ans,v-u+1+2*res);
    }
    printf("%d
",ans);
    fclose(stdin); fclose(stdout);
    return 0;
}

T3 数不过来

题意描述

称一个的无向图是好的,满足:

  • 任意一个子连通图的点数都相等,且都为完全图。

我们将所有(n)个点的好无向图拿出来,产生一个集合,每个好无向图是一个元素。

现在有(m)种颜色,求染色方案数,模(999999599)

两种方案数不同当且仅当存在一个元素的颜色不同。

数据范围:(n,mleq 10^9, Tleq 50)

solution

(ans) 为集合中元素的个数。

不难发现我们要求的其实是 (m^{ans} pmod {999999599})

根据欧拉公式可得,答案为 (m^{anspmod {varphi(999999599)}} pmod {99999599})

(999999599) 这个数我们不太熟悉,把他分解一下,发现他是个质数。

然后我们的问题就转化为求 (anspmod {999999598})

(f(i,j)) 表示把 (n) 个元素分到 (j) 个相同的集合中,每个集合元素的个数都为 (i) 的方案数。

我们可以枚举每个子连通图的点数 (d) , 则有:(ans = displaystylesum_{dmid n} f(d,{nover d}))

考虑怎么求 (f(d,{nover d})) ,可以列出来这么一个柿子:

(f(d,{nover d}) = {nchoose d} imes {n-dchoose d} imes {n-2dchoose d} imes {n-3dchoose d} imes.... imes {dchoose d})

这个柿子实际上是考虑了每个子连通图的顺序的,但我们考虑顺序的话就会把 {1-2-3,4-5-6} 和 {4-5-6,1-2-3} 算成两种方案,实际上这两个是同一种方案,所以最后还要除以 ({nover d}!)

化简一下可得:(Large{f(d,{nover d}) = {n!over {(d!)^{nover d} imes {nover d}!}}})

考虑怎么求这个柿子,因为 (999999598) 不存在逆元,所以不能直接算。

考虑用类似于拓展卢卡斯的方法求解。

先对 (999999598) 质因数分解可得: (999999598 = 2 imes 13 imes 5281 imes 7283)

算出 (f(n{nover d}) pmod {2/13/5284/7283}) ,然后用 中国剩余定理 合并即可。

快速算阶乘的话可以用拓展卢卡斯的方法去求,这里不在详细介绍。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long
const int N = 1e6+10;
const int p = 999999599;
const int pmod = 999999598;
int T,n,m,cnt,flag;
int a[5] = {2,13,5281,7283};
inline int read()
{
    int s = 0,w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
    return s * w;
}
int ksm(int a,int b,int p)
{
    int res = 1;
    for(; b; b >>= 1)
    {
        if(b & 1) res = res * a % p;
        a = a * a % p;
    }
    return res;
}
void exgcd(int a,int b,int &x,int &y)
{
	if(b == 0)
	{
		x = 1;
		y = 0;
		return;
	}
	exgcd(b,a%b,y,x);
	y -= a/b*x;
}
int Inv(int a,int b)
{
	int x = 0, y = 0;
	exgcd(a,b,x,y);
	return (x % b + b) % b;
}
int fac(int n,int pi,int pk)
{
	if(n == 1 || n == 0) return 1;
	int tmp1 = 1, tmp2 = 1;
	for(int i = 1; i <= pk; i++)
	{
		if(i % pi) tmp1 = tmp1 * i % pk;
	}
	for(int i = 1; i <= n%pk; i++)
	{
		if(i % pi) tmp2 = tmp2 * i % pk;
	}
	return fac(n/pi,pi,pk) * ksm(tmp1,n/pk,pk) % pk * tmp2 % pk;
}
int calc(int d,int n,int pi,int pk)
{
	int n1 = fac(n,pi,pk), m1 = fac(d,pi,pk), m2 = fac(n/d,pi,pk);
	int x = 0, y = 0, z = 0;
	for(int i = n; i; i /= pi) x += i/pi;
	for(int i = d; i; i /= pi) y += i/pi;
	for(int i = n/d; i; i /= pi) z += i/pi;
	return n1 * Inv(ksm(m1,n/d,pk),pk) % pk * Inv(m2,pk) % pk * ksm(pi,x-y*(n/d)-z,pk) % pk;
}
int CRT(int d,int n)
{
	int res = 0;
	for(int i = 0; i < 4; i++)
	{
		int tmp = calc(d,n,a[i],a[i]); 
		int M = pmod / a[i];
		res = (res + tmp % pmod * M % pmod * Inv(M,a[i])) % pmod;
	}
	return res;
}
int slove(int n)
{
	int res = 0;
	for(int i = 1; i <= sqrt(n); i++)
	{
		if(i * i == n) res = (res + CRT(i,n)) % pmod;
		else if(n % i == 0)
		{
			res = (res + CRT(i,n)) % pmod;
			res = (res + CRT(n/i,n)) % pmod;
		}
	}
	return res;
}
signed main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    T = read();
    while(T--)
    {
        n = read(); m = read();
        printf("%lld
",ksm(m,slove(n),p));
    }
    fclose(stdin); fclose(stdout);
    return 0;
}
原文地址:https://www.cnblogs.com/genshy/p/14515456.html