题型整理（3）

拉格朗日插值法的应用

给n个点推原函数求 f(k) mod 998244353

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int maxn=2010;//n的范围
typedef long long ll;
ll mod=998244353;
ll n,k,x[maxn],y[maxn],ans,s1,s2;
ll powmod(ll a,ll x){
    ll ret=1ll,nww=a;
    while(x){
        if(x&1)ret=ret*nww%mod;
        nww=nww*nww%mod;x>>=1;
    }
    return ret;
}
ll inv(ll x){
	return powmod(x,mod-2);
}
int main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
		scanf("%lld%lld",x+i,y+i);
    for(int i=1;i<=n;i++){
        s1=y[i]%mod;s2=1ll;
        for(int j=1;j<=n;j++)if(i!=j)s1=s1*(k-x[j])%mod,s2=s2*((x[i]-x[j]%mod)%mod)%mod;
        ans+=s1*inv(s2)%mod;ans=(ans+mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

字典树的应用

子数组最大异或和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
const int M = N * 32 + 1;
int trie[M][2], idx;
void add( int x ) {
    int p = 0;
    for ( int i = 31; i >= 0; --i) {
        int u = x >> i & 1;
        int &t = trie[p][u];
        if ( !t ) t = ++idx;
        p = t;
    }
}
int query( int x ) {
    int ret = 0, p = 0;
    int u = x >> 31 & 1;
    if ( !trie[p][u] ) {
        ret |= 1 << 31;
        u ^= 1;
    }
    p = trie[p][u];
    for ( int i = 30; i >= 0; --i ) {
        u = x >> i & 1;
        int &t = trie[p][u ^ 1];
        if ( t ) {
            ret |= 1 << i;
            p = t;
        } else p = trie[p][u];
    }
    return ret;
}
int main()
{
    int n, x;
    int ret = 0, eor = 0;
    scanf("%d", &n);
    while ( n-- ) {
        scanf("%d", &x);
        eor ^= x;
        ret = max( ret, query(eor) );
        add( eor );
    }
    printf("%d\n", ret);
    return 0;
}

长度为m的子数组最大异或和（正数序列）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
const int N =( 1e5 + 10) * 31, M = 1e5 + 10;
int son[N][2],idx,arr[M], s[M],cnt[N];
void insert(int x, int val){
    int p = 0;
    for(int i = 30 ;i >= 0; i --){
        int u = x >> i & 1;
        if(!son[p][u])son[p][u] = ++idx;
        p = son[p][u];
        cnt[p] += val;
    }
}
int query(int x){
    int p = 0,res = 0;
    for(int i = 30; i >= 0; i --){
        int u = x >> i & 1;
        if(cnt[ son[p][!u] ] ){
            res += 1 << i;
            p = son[p][!u];
        }
        else p = son[p][u];
    }
    return res;
}
int main()
{
    int n,m,res = 0;
    cin>>n>>m;
    for(int i = 1; i <= n; i ++ ){
        int x;
        cin>>x;
        s[i] = s[i - 1] ^ x;
    }
    insert(s[0],1);
    for(int i = 1;i <= n; i ++ ){ 
        if(i > m )insert(s[i - m - 1], -1);
        res = max(res, query(s[i]));
        insert(s[i],1);
    }
    cout<<res;
}

最小生成树

普里姆算法的时间复杂度为O(n n)，n为顶点数，适用于稠密图；
克鲁斯卡尔算法的时间复杂度为O(e loge)，e为边数，适用于稀疏图；

Kruskal算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
int n,m,sum,cnt;
struct node{
    int start,end,power;//start为起始点，end为终止点，power为权值
}edge[5050];
int pre[5050];
int cmp(node a, node b){
    return a.power<b.power;//按照权值排序
}
int find(int x){//并查集找祖先
    if(x!=pre[x]){
        pre[x]=find(pre[x]);
    }
    return pre[x];
}
void merge(int x,int y,int n){//并查集合并函数，n是用来记录最短路中应该加入哪个点
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy){
        pre[fx]=fy;
        cnt++;
        sum+=edge[n].power;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int start,end,power;
    for(int i=1; i<=m; i++){
        scanf("%d %d %d", &start, &end, &power);
        edge[i].start=start,edge[i].end=end,edge[i].power=power;
    }
    for(int i=1; i<=m; i++){
        pre[i]=i;
    }//并查集初始化
    sort(edge+1, edge+m+1,cmp);
    for(int i=1; i <= m; i++){
        merge(edge[i].start,edge[i].end,i);
    }
    if(cnt<n-1)
    printf("?\n");
    else
    printf("%d\n",sum);
    return 0;
}

prim算法（邻接矩阵）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int prim(){
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    for (int i = 0; i < n; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        if (i && dist[t] == INF) return INF;
        if (i) res += dist[t];
        st[t] = true;
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}
int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);
    while (m -- ){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int t = prim();
    if (t == INF) puts("?");
    else printf("%d\n", t);
    return 0;
}

最大子序列和

在线处理

1
2
3
4
5
6
7
8
9
10
11
12
13
int MaxSubseqSum1(int A[], int N){
    int ThisSum, MaxSum = 0;
    int i;
    ThisSum = MaxSum=0;
    for (i = 0;i < N;i++){
        ThisSum += A[i];
        if (ThisSum > MaxSum)
            MaxSum = ThisSum;
        else if (ThisSum < 0)
            ThisSum = 0;
    }
    return MaxSum;
}