2019 ACM - ICPC 全國邀請賽（南昌） 題解（9 / 12）

整理的演算法模板合集： ACM模板

點我看演算法全家桶系列！！！

實際上是一個全新的精煉模板整合計劃

The 2019 ICPC China Nanchang National Invitational and International Silk-Road Programming Contest

VP地址：https://www.jisuanke.com/contest/20996/challenges

A. Attack

Solution

斯坦納樹板子 + DP即可

Code

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
const int M = 2e3 + 10;
const int N = 40;

struct Edge{
	int to,val;
	int nxt;
}edges[M];
int head[N],idx = 0;
void add(int u, int v, int c)
{
	edges[idx] = {v,c,head[u]}, head[u] = idx++;
	edges[idx] = {u,c,head[v]}, head[v] = idx++;
}

int dp[N][500];
int f[500];
map<string, int> mp;
typedef pair<int,int> pii;
priority_queue<pii, vector<pii>, greater<pii>> q;
bool vis[N];

void dij(int s)
{
	memset(vis,0,sizeof(vis));
	while(q.size()){
		int u = q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = head[u];~i;i = edges[i].nxt){
			int v = edges[i].to;
			int cost = edges[i].val;
			if(dp[v][s] > dp[u][s] + cost){
				dp[v][s] = dp[u][s] + cost;
				q.push({dp[v][s],v});
			}
		}
	}
}

bool check(int s)
{
	for(int i = 0;i < 4;++i){
		int x = s >> (i * 2) & 1;
		int y = s >> (i * 2 + 1) & 1;
		if(x ^ y) return 1;
	}
	return 0;
}

int main()
{
	memset(head,-1,sizeof(head));
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++i){
		string s;
		cin >> s;
		mp[s] = i;
	}
	for(int i = 0;i < m;++i){
		string a, b;
		int cost;
		cin >> a >> b >> cost;
		add(mp[a],mp[b],cost);
	}
	memset(dp,0x3f,sizeof(dp));
	for(int i = 0;i < 8;++i) {
		string s;
		cin>>s;
		dp[mp[s]][1 << i] = 0;
	}

	for(int s = 0; s < (1 << 8);++s){
		for(int i = 1;i <= n;++i){
			for(int subs = s & (s-1);subs;subs = s & (subs - 1)){
				dp[i][s] = min(dp[i][s], dp[i][subs] + dp[i][s ^ subs]);
			}
			if(dp[i][s] != inf) q.push({dp[i][s],i});
		}
		dij(s);
	}

	memset(f,0x3f,sizeof(f));
	for(int s = 0;s < (1 << 8);++s){
		if(check(s)) continue;
		for(int i = 1;i <= n;++i) f[s] = min(dp[i][s],f[s]);
		for(int subs = s & (s-1);subs;subs = s & (subs - 1)){
			if(check(subs)) continue;
			f[s] = min(f[subs] + f[s ^ subs], f[s]);	
		}
	}
	printf("%d\n",f[(1 << 8) - 1]);  
	return 0;
}

B. Polynomial

Solution

顯然考慮前綴和計算，我們知道若 f f f 是一個 n n n 次多項式，其前綴和 s u m sum sum 是一個 n + 1 n+1 n+1 次多項式，我們已經有了 n + 1 n+1 n+1 個點，先拉格朗日插值求出第 n + 2 n+2 n+2 個點 f ( n + 1 ) f(n+1) f(n+1)，然后用這 n + 2 n+2 n+2 個點拉格朗日插值求出 s u m ( r ) , s u m ( l ? 1 ) sum(r),sum(l-1) sum(r),sum(l?1) 即可，

Code

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int mod = 9999991, N = 5007;

int n, m;
int f[N];
int sum[N];
int fact[mod + 10], infact[mod + 10];
int inv[mod + 10];

int qpow(int a, int b)
{
	int res = 1;
	a %= mod;
	while(b) {
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
 
void init(int k)
{
	inv[1] = 1;
	for(int i = 2; i <= k; ++ i)
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	infact[0] = 1;
	for(int i = 1; i <= k; ++ i) {
		infact[i] = infact[i - 1] * inv[i] % mod;
	}
	//cout << infact[k] << endl; 
}  


int lagrange(int k, int *a, int n)
{
	int up = 1;
	for(int i = 0; i <= n; ++ i) {
		up = up * (k - i) % mod;
	}
	//cout << up << "up" << endl;
	int ans = 0;
	for(int i = 0; i <= n; ++ i) {
		int f;
		if((n - i) & 1) f = -1;
		else f = 1;
		int tmp = a[i] * f * infact[i] % mod * infact[n - i] % mod * (up * inv[k - i] % mod) % mod;
//		cout << infact[i] << endl;
		cout << ans << "ans" << endl;
		ans = ((ans + tmp) % mod + mod) % mod;
	}
	return ans;
}

signed main()
{
	init(mod + 7);
	int t;
	scanf("%lld", &t);
	while(t -- ) {
		scanf("%lld%lld", &n, &m);
		for(int i = 0; i <= n; ++ i) {
			scanf("%lld", &f[i]);
		}
		f[n + 1] = lagrange(n + 1, f, n);
		 
		sum[0] = f[0];
		for(int i = 1; i <= n + 1; ++ i) {
			sum[i] = (sum[i - 1] + f[i]) % mod;
		}
		while(m -- ) {
			int l, r;
			scanf("%lld%lld", &l, &r);

			if(l <= n && r <= n) {
				printf("%lld\n", (sum[r] - sum[l - 1] + mod) % mod);
			}
			else if(l <= n) {
				printf("%lld\n", (lagrange(r, sum, n + 1) - sum[l - 1] + mod) % mod);
			}
			else printf("%lld\n", (lagrange(r, sum, n + 1) - lagrange(l - 1, sum, n + 1) + mod) % mod);
		}
	}
	return 0;
}

C. Xyjj’s sequence

Solution

先歐拉降冪算出權值（數塔），然后直接DP即可，

Code

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 1e5 + 10, p = 1e5 + 3;

int v;
int aw[N], bw[N];
int n, m;
int phi[N];

int a, b;
int primes[N], cnt;
bool vis[N];

int qpow(int a, int b, int mod)
{
	int res = 1;
	a %= mod;
	while(b) {
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

void init(int n)
{
    phi[1] = 1;
    for(int i = 2; i <= n; ++ i) {
        if(vis[i] == 0) primes[ ++ cnt] = i, phi[i] = i - 1;
        for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
            vis[i * primes[j]] = true;
            if(i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }
}

int dp[2][5001][2];


int tower(int num, int p)
{
	if(p == 1) return 0;
	if(num == 1) return b % p;
	return qpow(b, tower(num - 1, phi[p]) + phi[p], p);
}

signed main()
{
	init(1e5 + 7);
	scanf("%lld%lld", &a, &b);
	scanf("%lld", &n);
	for(int i = 1; i <= n; ++ i) {
		scanf("%lld", &v);
		aw[i] = qpow(a, tower(v, phi[p]), p);
	}
	for(int i = 1; i <= n; ++ i) {
		scanf("%lld", &v);
		bw[i] = qpow(a, tower(v, phi[p]), p);
	}
	/*for(int i = 1; i <= n; ++ i)
	printf("%lld\n", aw[i]);
	for(int i = 1; i <= n; ++ i)
	printf("%lld\n", bw[i]);*/
	bw[0] = aw[0] = 0;
	for(int i = 1;i <= n;++i){
	    int idx = i&1;
		for(int j = 1;j <= n;++j){
			dp[idx][j][0] = max(dp[!idx][j][0]+(aw[i]==aw[i-1])*aw[i],dp[idx][j][0]);
			dp[idx][j][0] = max(dp[!idx][j][1]+(aw[i]==bw[j])*aw[i],dp[idx][j][0]);
			dp[idx][j][1] = max(dp[idx][j-1][0]+(aw[i]==bw[j])*bw[j],dp[idx][j][1]);
			dp[idx][j][1] = max(dp[idx][j-1][1]+(bw[j]==bw[j-1])*bw[j],dp[idx][j][1]);
		}
		memset(dp[!idx],0,sizeof(dp[!idx]));
        
	}
	cout<<max(dp[n&1][n][1],dp[n&1][n][0])<<endl;
}

F. Sequence

Solution

樹狀陣列維護即可，

Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 100006;
struct BIT
{
    ll bit[maxn];
    void modify(int n,ll val,int idx){
        for(int i = idx;i <= n;i += i&-i)bit[i] ^= val;
    }
    ll query(int x){
        ll ans = 0;
        for(int i = x;i;i -= i&-i)ans ^= bit[i];
        return ans;
    }
}odd,even;
ll a[maxn];

void solve()
{
    static int cs = 0;
    cs++;
    memset(&odd,0,sizeof(odd));
    memset(&even,0,sizeof(even));
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i = 1;i <= n;++i){
        scanf("%lld",&a[i]);
        if(i&1)odd.modify(n,a[i],i);
        else even.modify(n,a[i],i);
    }
    printf("Case #%d:\n",cs);
    while(q--){
        static int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==1){
            if((r-l+1)%2==0)printf("0\n");
            else{
                ll ans = 0;
                if(r&1){
                    ans = odd.query(r)^odd.query(l-1);
                }
                else ans = even.query(r)^even.query(l-1);
                printf("%lld\n",ans);
            }
        }
        else{
            if(l&1){
                odd.modify(n,a[l],l);
                a[l] = r;
                odd.modify(n,a[l],l);
            }
            else{
                even.modify(n,a[l],l);
                a[l] = r;
                even.modify(n,a[l],l);
            }
        }
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
}

G. Winner

Solution

考慮建圖，然后縮點即可，

Code

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
const int N = 1e5 + 10;
pii a[N],b[N],c[N];


struct Edge{
    int to;
    int nxt;
}edges[N * 4];
int head[N], idx;

void add(int u, int v)
{
    // printf("%d %d\n",u,v);
    edges[idx] = {v,head[u]};
    head[u] = idx++;
}

int dfn[N], low[N], tim;
int stk[N], tp = 0;
int ins[N];
int cnt_scc = 0;
int scc_id[N];
vector<int> scc[N];
int in[N];
unordered_map<int,int> ok;

void tarjan(int u)
{
    dfn[u] = low[u] = ++tim;
    stk[++tp] = u;
    ins[u] = 1;
    for(int i = head[u];~i;i = edges[i].nxt){
        int v = edges[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[v],low[u]);
        }
        else if(ins[v]){
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(dfn[u] == low[u]){
        cnt_scc++;
        int v;
        do{
            v = stk[tp--];
            ins[v] = 0;
            scc_id[v] = cnt_scc;
            scc[cnt_scc].push_back(v);
        }while(u != v);
    }
}

int main()
{
    memset(head,-1,sizeof(head));
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i) scanf("%d",&a[i].first),a[i].second = i;
    for(int i = 1;i <= n;++i) scanf("%d",&b[i].first),b[i].second = i;
    for(int i = 1;i <= n;++i) scanf("%d",&c[i].first),c[i].second = i;
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    sort(c+1,c+n+1);
    for(int i = 1;i < n;++i){
        add(a[i+1].second, a[i].second);
        add(b[i+1].second, b[i].second);
        add(c[i+1].second, c[i].second);
    }
    
    for(int i = 1;i <= n;++i){
        if(!dfn[i]) tarjan(i);
    }

    for(int i = 1;i <= n;++i){
        for(int j = head[i];~j;j = edges[j].nxt){
            if(scc_id[edges[j].to] != scc_id[i]){
                in[scc_id[edges[j].to]]++;
            }
        }
    }
    
    for(int i = 1;i <= cnt_scc;++i){
        if(!in[i]){
            for(auto it : scc[i]){
                ok[it] = 1;
            }
        }
    }
    // for(int i = 1;i <= cnt_scc;++i){
    //     for(auto it : scc[i]){
    //         printf("%d ",it);
    //     }
    //     puts("");
    // }
    while(m--){
        int x;
        scanf("%d",&x);
        if(ok[x]) puts("YES");
        else puts("NO");
    }
    return 0;
}

H. Another Sequence

Solution

先用FWT的或運算 O ( n l o g n ) O(nlogn) O(nlogn) 求出陣列的值，然后用樹狀陣列維護即可，

Code

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define ll long long
const int N = 5e5 + 7;
const int M = 1<<17;
const int MX = 1e5;
int n, m;
int cnta[N], cntb[N], a[N], b[N], c[N], maxx;
int cnt[N];

 void OR(ll *f, int x = 1)
{
    for(int o = 2; o <= (1 << 17); o <<= 1) {
        for(int i = 0, k = o >> 1; i < (1 << 17); i += o) {
            for(int j = 0; j < k; ++ j) {
                f[i + j + k] = (f[i + j + k] + f[i + j] * x);
            }
        }
    }
} 
int sum[N];

int bit[M+5];

void modify(int x,int n,int val){
	for(int i = x;i <= n;i += i&-i)bit[i]+=val;
}
int query(int x){
	int ans = 0;
	for(int i = x;i;i -= i&-i)ans += bit[i];
	return ans;
}




void solve()
{
	using pii = pair<int,int>;
	vector<int> a;
	vector<pii> que;
	int q;
	scanf("%lld",&q);
	for(int i = 1,x,y;i <= q;++i){
		scanf("%lld%lld",&x,&y);
		a.push_back(y);
		if(x)a.push_back(x);
		que.push_back(make_pair(x,y));
	}
	sort(a.begin(),a.end());
	a.erase(unique(a.begin(),a.end()),a.end());
	for(auto &x:que){
		if(x.first)x.first = lower_bound(a.begin(),a.end(),x.first)-a.begin()+1;
		x.second = lower_bound(a.begin(),a.end(),x.second)-a.begin()+1;
	}
	for(auto &x:que){
		if(x.first){
			modify(x.first,M,1);
			modify(x.second,M,-1);
		}
		else{
			int val = query(x.second);
			int id = a[x.second-1];
			int idx = lower_bound(sum,sum+M,id)-sum;
			while(idx > 1&&val){
				val--;
				idx = sqrt(idx);
			}
			printf("%d\n",idx);
		}
	}
}	


signed main()
{
	scanf("%lld", &n);
	for(int i = 1; i <= n; ++ i) {
		scanf("%lld", &a[i]);
		cnta[a[i]] ++ ;
		maxx = max(maxx, a[i]);
	}
	for(int i = 1; i <= n; ++ i) {
		scanf("%lld", &b[i]);
		cntb[b[i]] ++ ;
		maxx = max(maxx, b[i]);
	}

	OR(cnta);
	OR(cntb); 
	for(int i = 0; i < 1 << (17); ++ i) {
		cnt[i] = cnta[i] * cntb[i];
	}
	OR(cnt, -1);
	
	int ans = 0;
	/*for(int i = 1; i < 100; ++i){
        printf("i: %d   num: %d\n",i,cnt[i]);
    }*/
	sum[0] = cnt[0];
	for(int i = 0; i < 1 << (17); ++ i) {
		//for(int j = 1;j <= cnt[i];++j)printf("%d ",i);
		sum[i] = sum[i-1]+cnt[i];
	}
	solve();
	/*
1 1 1 2 3 3 4 5 5 5 5 6 7 7 7 8 11 12 12 12 13 14 15 15 15 	*/
	
	
}

J. Prefix

Solution

字典樹即可，

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int maxn = 2e5+5;
int val[26];

int tree[maxn][26];
int n,m,cnt[maxn];
int bit[maxn],tot;
vector<int> endpos[maxn];


void modify(int x,int val){
    for(int i = x;i;i -= i&-i)bit[i] += val;
}
int query(int x,int n){
    int ans = 0;
    for(int i = x;i <= n;i += i&-i)ans += bit[i];
    return ans;
}

void Insert(const char *s,int k)
{
    int root = 0;
    for(int i = 0;s[i];++i){
        if(!tree[root][s[i]-'a']){
            tree[root][s[i]-'a'] = ++tot;
        }
        root = tree[root][s[i]-'a'];
        cnt[root]++;
    }
    endpos[root].push_back(k);
}
char s[maxn];
int ans[maxn];


void dfs(int now,int num)
{
    if(endpos[now].size()){
        for(auto &x:endpos[now])
        ans[x] = query(num+1+1,m);
    }
    modify(num+1,cnt[now]);
    for(int i = 0;i < 26;++i){
        if(tree[now][i]){
            dfs(tree[now][i],1ll*num*val[i]%m);
        }
    }
    modify(num+1,-cnt[now]);
}


signed main()
{
    scanf("%lld%lld",&n,&m);   
    for(int i = 0;i < 26;++i)scanf("%lld",&val[i]);
    for(int i = 1;i <= n;++i){
        scanf("%s",s);
        Insert(s,i);
    }
    dfs(0,1);
    for(int i = 1;i <= n;++i)printf("%lld ",ans[i]);
    return 0;
}

K. A Good Game

Solution

顯然貪心排序即可，前綴和大的肯定乘上大的數得到的分數最多，

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int v[N];
long long sum[N];

struct node{
    int l,r;
    long long sum;
    bool operator<(const node &a)const{
        return sum < a.sum;
    }
}op[N];


int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;++i){
            scanf("%d",&v[i]);
            sum[i] = sum[i-1] + v[i];
        }
        for(int i = 1;i <= m;++i){
            scanf("%d%d",&op[i].l,&op[i].r);
            op[i].sum = sum[op[i].r] - sum[op[i].l-1];
        }
        sort(op+1,op+1+m);
        long long res = 0;
        for(int i = 1;i <= m;++i){
            //printf("%d\n",op[i].sum);
            res += 1ll * op[i].sum * i;
        }
        printf("%lld\n",res);
    } 
    return 0;
}

L

因為太簽到了所以計蒜客上沒有這道題hhh
看知乎說這道題就是輸入三個數求他們的和hhh

簽到