2019南昌邀请赛网络赛个人记录（附官方题解）

Author： xzm2019
发布时间：April 20, 2019
9400views
No comments
5768字数
Categories：算法

> 这是一个防止代码因为账号销毁丢失而写的记录

官方题解：[南昌网络赛题解.pdf][1]

| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|:------:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|  9/13  | O | . | O | O | . | . | . | O | O | O | O | O | O |

- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet

## A. PERFECT NUMBER PROBLEM

你可以轻松通过打表找到前四个数字，这时候你可以通过OEIS和~~万能的群友~~来得到第五个答案。

当然，如果你决定让你的程序多运行一会的话，也是可以的。

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

int main()
{
    printf("6\n28\n496\n8128\n33550336\n");
    return 0;
}
```

## C. Angry FFF Party

其实你只要通过打表就可以发现，满足条件的数没有多少，只有28个，因此只要对其进行暴力分解即可。

```java
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Matrix m = new Main.Matrix();
        ArrayList<BigInteger> f3= new ArrayList<BigInteger>(),f2 = new ArrayList<BigInteger>();
        f3.add(new BigInteger("0"));
        for(int i=1;i<=30;i++){
//            System.out.println(i+": ");
            BigInteger ff = Matrix.qp(new Matrix(),new BigInteger(i+"")).f1;
//            System.out.println(ff);
            BigInteger fff = Matrix.qp(new Matrix(),ff).f1;
//            System.out.println(fff);
//            System.out.println("");
            f3.add(fff);
            f2.add(ff);
        }
        Scanner sc = new Scanner( System.in );
        int T=sc.nextInt();
        while (T!=0) {
            String w = sc.next();
            BigInteger b = new BigInteger(w);

ArrayList<Integer> ans = new ArrayList<Integer>();
            for(int i=30;i>=6;i--){
                int res = b.compareTo(f3.get(i));
                if (res>=0){
                    b=b.subtract(f3.get(i));
                    ans.add(i);
                }
                if(b.compareTo(new BigInteger("10"))<=0){
                    break;
                }
//                System.out.println(i+": "+b);
            }

if(b.compareTo(new BigInteger("0"))==0){
                for(int i=ans.size()-1;i>=0;i--){
                    if(i!=ans.size()-1){
                        System.out.print(" ");
                    }
                    System.out.print(ans.get(i)+"");
                }
                System.out.println("");
            }
            else{
                if(b.compareTo(new BigInteger("10"))<=0) {
                    if (b.compareTo(new BigInteger("10")) == 0) {
                        System.out.print("1 2 3 4 5");
                    } else if (b.compareTo(new BigInteger("9")) == 0) {
                        System.out.print("1 2 4 5");
                    } else if (b.compareTo(new BigInteger("8")) == 0) {
                        System.out.print("1 2 3 5");
                    } else if (b.compareTo(new BigInteger("7")) == 0) {
                        System.out.print("1 2 5");
                    } else if (b.compareTo(new BigInteger("6")) == 0) {
                        System.out.print("1 5");
                    } else if (b.compareTo(new BigInteger("5")) == 0) {
                        System.out.print("1 2 3 4");
                    } else if (b.compareTo(new BigInteger("4")) == 0) {
                        System.out.print("1 2 4");
                    } else if (b.compareTo(new BigInteger("3")) == 0) {
                        System.out.print("1 2 3");
                    } else if (b.compareTo(new BigInteger("2")) == 0) {
                        System.out.print("1 2");
                    } else if (b.compareTo(new BigInteger("1")) == 0) {
                        System.out.print("1");
                    }
                    for (int i = ans.size() - 1; i >= 0; i--) {
                        System.out.print(" ");
                        System.out.print(ans.get(i) + "");
                    }
                    System.out.println("");
                }

else {
                    System.out.println("-1");
                }
            }
            T--;
        }

}

static class Matrix {
        public BigInteger f0,f1,f2,f3;
        public Matrix(){
            f0= new BigInteger("1");
            f1= new BigInteger("1");
            f2= new BigInteger("1");
            f3= new BigInteger("0");
        }
        public void debug(){
            System.out.println(f0+" "+f1);
            System.out.println(f2+" "+f3);
        }
        public Matrix(BigInteger f0,BigInteger f1,BigInteger f2,BigInteger f3){
            this.f0=f0;
            this.f1=f1;
            this.f2=f2;
            this.f3=f3;
        }
        public Matrix mul(Matrix b){
            return new Matrix(
                    (this.f0.multiply(b.f0)).add(this.f1.multiply(b.f2)),
                    (this.f0.multiply(b.f1)).add(this.f1.multiply(b.f3)),
                    (this.f2.multiply(b.f0)).add(this.f3.multiply(b.f2)),
                    (this.f2.multiply(b.f1)).add(this.f3.multiply(b.f3)));
        }
        public static Matrix qp(Matrix a,BigInteger n){
            if (n.equals(new BigInteger("1"))){
                return new Matrix();
            }else{

Matrix y = qp(a,n.divide(new BigInteger("2")));

if(n.mod(new BigInteger("2")).equals(new BigInteger("1")))
                    return (y.mul(y)).mul(new Matrix());
                else
                    return y.mul(y);
            }
        }
    }

}
```

------

```python
def mul( a, b ):
	c = [[0,0],[0,0]]
	for I in range( 0, 2 ):
		for j in range( 0, 2 ):
			for k in range( 0, 2 ):
				c[I][j] += a[I][k]*b[k][j]
	# for I in range( 0, 2 ):
	# 	print( str(c[I][0]) + " " + str( c[I][1]) )
	return c
def f( x ):
	a = [[1,1],[1,0]]
	b = [[1,0],[0,0]]
	while( x ):
		if x&1:
			b = mul( b, a )
		a = mul( a, a )
		x >>= 1
	return b[0][1]
a = [0]
for I in range( 1, 29 ):
	a.append(f(f(I)))
T = int(input())
for t in range( 0, T ):
	vis = [0]*30
	b = int(input())
	I = 28
	ans = []
	while I > 0: 
		if b == 1:
			if vis[1] == 0:
				ans.append( 1 )
				b -= a[1]
				vis[1] = 1
			break
		elif b == 2:
			if vis[1] == 0:
				ans.append( 1 )
				b -= a[1]
				vis[1] = 1
			if vis[2] == 0:
				ans.append( 2 )
				b -= a[2]
				vis[2] = 1
			break
		elif b == 3:
			if vis[1] == 0:
				ans.append( 1 )
				b -= a[1]
				vis[1] = 1
			if vis[2] == 0:
				ans.append( 2 )
				b -= a[2]
				vis[2] = 1
			if vis[3] == 0:
				ans.append( 3 )
				b -= a[3]
				vis[3] = 1
			break
		elif b == 4:
			if vis[1] == 0:
				ans.append( 1 )
				b -= a[1]
				vis[1] = 1
			if vis[2] == 0:
				ans.append( 2 )
				b -= a[2]
				vis[2] = 1
			if vis[4] == 0:
				ans.append( 4 )
				b -= a[4]
				vis[4] = 1
			break
		elif b == 5:
			if vis[1] == 0:
				ans.append( 1 )
				b -= a[1]
				vis[1] = 1
			if vis[2] == 0:
				ans.append( 2 )
				b -= a[2]
				vis[2] = 1
			if vis[3] == 0:
				ans.append( 3 )
				b -= a[3]
				vis[3] = 1
			if vis[4] == 0:
				ans.append( 4 )
				b -= a[4]
				vis[4] = 1
			break
		if b >= a[I] and vis[I] == 0:
			ans.append( I )
			vis[I] = 1
			b -= a[I]
		I -= 1
	if b != 0:
		print( "-1" )
	else:
		ans.sort()
		for I in ans:
			if I != ans[0]:
				print(" ", end="")
			print( I, end="" )
		print()
```

## D. Match Stick Game

其实这个题挺简单的~~（一定是榜被带歪了）~~首先预处理$f[0/1][i][j]$表示长度为$i$的$j$根火柴棒的最小/大可表示数。然后用$op$对表达式进行分块，$dp[i][j]$表示到第$i$块还剩$j$根火柴棒的时候的最大值。

注意$A_i$里一定没有负号

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

const int num[] = {6,2,5,5,4,5,6,3,7,6};
long long f[2][15][75];
inline void init()
{
    for (int i = 0 ; i < 15; i++)
        for (int j = 0; j < 75; j++)
            f[1][i][j] = - 1e10;
    memset(f[0],0x3f,sizeof(f[0]));
    f[0][0][0] = 0;
    f[1][0][0] = 0;
    for (int i = 1; i <= 10; i++)
        for (int j = 1; j <= i * 7; j++)
            for (int k = 0; k <= 9; k++)
            {
                if (j < num[k]) continue;
                f[0][i][j] = min(f[0][i][j], f[0][i - 1][j - num[k]] * 10 + k);
                f[1][i][j] = max(f[1][i][j], f[1][i - 1][j - num[k]] * 10 + k);
            }
}
long long dp[105][705];
char s[105];
int nums[105];
int main()
{
    init();
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int tot = 0;
        int n;
        scanf("%d%s",&n,s);
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n * 7; j++)
                dp[i][j] = -1e12;
        int last = -1, cnt = 0;
        for (int i = 0; s[i]; i++)
        {
            if (s[i] == '+' || s[i] == '-')
            {
                nums[cnt++] = i - last - 1;
                last = i;
            }
            if (s[i] == '+') tot += 2;
            else if (s[i] == '-') tot += 1;
            else tot += num[s[i] - '0'];
        }
        nums[cnt++] = strlen(s) - 1 - last;
        for (int i = 1; i <= min(nums[0] * 7, tot); i++)
            dp[0][tot - i] = max(dp[0][tot - i], f[1][nums[0]][i]);
        for (int i = 1; i < cnt; i++)
            for (int j = 0; j <= tot; j++)
                for (int k = 2; k <= min(nums[i] * 7 + 2, j); k++)
                {
                    dp[i][j - k] = max(dp[i][j - k], dp[i - 1][j] - f[0][nums[i]][k - 1]);
                    dp[i][j - k] = max(dp[i][j - k], dp[i - 1][j] + f[1][nums[i]][k - 2]);
                }
        printf("%lld\n",dp[cnt - 1][0]);
    }
}
```

## H. Coloring Game

我们很容易就可以找到答案的规律为$3^{n-2}*4$。

```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <complex>
#include <stack>
#define SET0(X) memset(X,0,sizeof(X));
#define SET_1(X) memset(X,-1,sizeof(X));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN = 1e5+4;
const double PI = acos(-1.0);
const double EPS = 1e-6;
const int INF = 0x3f3f3f3f;
const ll mod =1e9+7;
ll qp(ll a,ll n){
    if(n==0)
        return 1;

ll re=1;
    if(n%2)
        re=a;
    ll y=qp(a,n/2);
    return re*y%mod*y%mod;
}
int main()
{
    ll n;
    scanf("%lld",&n);
    if(n==1){
        printf("1\n");
    }else{
        printf("%lld\n",qp(3,n-2)*4%mod);
    }
    return 0;
}
```

## I. Max answer

很容易想到单调栈，但是单调栈不能处理负数的情况，考虑以下用例`-10 -10 1 -10 -10`。我们可以先用st表维护区间最大最小值，然后加一个单调栈即可。

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 500000+10;
const LL inf = 1e17;

int n;
int i,j;
LL sum[maxn],stmx[maxn][23],stmn[maxn][23];
int a[maxn],l[maxn],r[maxn];

stack<int> sta;

LL askmx(int l,int r)
{
	int k=log2(r-l+1);
	return max(stmx[l][k],stmx[r-(1<<k)+1][k]);
}

LL askmn(int l,int r)
{
	int k=log2(r-l+1);
	return min(stmn[l][k],stmn[r-(1<<k)+1][k]);
}

int main()
{
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	for (i=1;i<=n;i++) sum[i]=sum[i-1]+(LL)a[i];
	for (i=0;i<=n;i++) stmx[i][0]=stmn[i][0]=sum[i];
	for (j=1;(1<<j)<=n+1;j++)
	{
		for (i=0;i+(1<<j)-1<=n;i++)
		{
			stmx[i][j]=max(stmx[i][j-1],stmx[i+(1<<(j-1))][j-1]);
			stmn[i][j]=min(stmn[i][j-1],stmn[i+(1<<(j-1))][j-1]);
		}
	}
	for (i=1;i<=n;i++)
	{
		while (!sta.empty()&&a[i]<=a[sta.top()]) sta.pop();
		if (sta.empty()) l[i]=1; else l[i]=sta.top()+1;
		sta.push(i);
	}
	while (!sta.empty()) sta.pop();
	for (i=n;i>=1;i--)
	{
		while (!sta.empty()&&a[i]<=a[sta.top()]) sta.pop();
		if (sta.empty()) r[i]=n; else r[i]=sta.top()-1;
		sta.push(i);
	}
	LL ans=-inf;
	for (i=1;i<=n;i++)
	{
		if (a[i]<0)
		{
			LL R=askmn(i,r[i]);
			LL L=askmx(l[i]-1,i-1);
			ans=max(ans,(R-L)*(LL)a[i]);
		} else
		if (a[i]>0)
		{
			LL R=askmx(i,r[i]);
			LL L=askmn(l[i]-1,i-1);
			ans=max(ans,(R-L)*(LL)a[i]);
		} else
		{
			ans=max(ans,0ll);
		}
	}
	printf("%lld\n",ans);
	return 0;
}
```

## J. Distance on the tree

题目要求两点间距离小于$k$的边的个数，想到了树链剖分，但是不会写啊（哭

~~然后队友就看着B站视频学习了树链剖分然后写AC了~~

```cpp
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
#include <map>
#include <set>
#include <bitset>
#include <ctime>
#include <complex>

#define INF 0x3f3f3f3f
#define memset0(x) memset(x, 0, sizeof(x))
#define memsetM1(x) memset(x, -1, sizeof(x))
#define memsetINF(x) memset(x, INF, sizeof(x))

using namespace std;

const int MAXN = 2e5 + 5;
int have[MAXN];
int wt[MAXN];
struct node
{
	node *l, *r;
	int v;
	node() : l(NULL), r(NULL), v(0){}
};
node nodes[MAXN * 3];
int tot;
node* newNode()
{
	nodes[tot] = node();
	return &nodes[tot++];
}
void pushUp(node* nd)
{
	if (nd->l)
	{
		nd->v = nd->l->v + nd->r->v;
	}
}
int n, q;
node* root;
void build(node* nd = root, int l = 1, int r = n)
{
	if (l != r)
	{
		int mid = (l + r) / 2;
		nd->l = newNode();
		nd->r = newNode();
		build(nd->l, l, mid);
		build(nd->r, mid + 1, r);
		pushUp(nd);
	}
	else
	{
		nd->v = 0;
	}
}
void init()
{
	tot = 0;
	root = newNode();
	build();
}

void modify(int l, int v, node* nd = root, int cl = 1, int cr = n)
{
	if (cl == cr)
	{
		nd->v = v;
		return;
	}
	int mid = (cl + cr) / 2;
	if (l <= mid)
	{
		modify(l, v, nd->l, cl, mid);
	}
	else if (l > mid)
	{
		modify(l, v, nd->r, mid + 1, cr);
	}
	pushUp(nd);
}
int query(int l, int r, node* nd = root, int cl = 1, int cr = n)
{
	if (l == cl && r == cr)
	{
		return nd->v;
	}
	int mid = (cl + cr) / 2;
	if (r <= mid)
	{
		return query(l, r, nd->l, cl, mid);
	}
	else if (l > mid)
	{
		return query(l, r, nd->r, mid + 1, cr);
	}
	else
	{
		return query(l, mid, nd->l, cl, mid) + query(mid + 1, r, nd->r, mid + 1, cr);
	}
}

vector<int> graph[MAXN];
int dfn = 1;
int edgeCnt;
int in[MAXN], out[MAXN], son[MAXN], sz[MAXN], fa[MAXN], top[MAXN], dep[MAXN];

void dfs1(int u = 1, int pre = -1)
{
	fa[u] = pre;
	sz[u] = 1;
	son[u] = 0;
	for (int i = 0; i < graph[u].size(); i++)
	{
		int v = graph[u][i];
		if (v == pre)
		{
			continue;
		}
		dep[v] = dep[u] + 1;
		dfs1(v, u);

sz[u] += sz[v];
		if (son[u] == 0 || sz[v] > sz[son[u]])
		{
			son[u] = v;
		}
	}
}
void dfs2(int u = 1, int tp = 1)
{
	in[u] = dfn++;
	top[u] = tp;
	if (son[u])
	{
		dfs2(son[u], tp);
	}

for (int i = 0; i < graph[u].size(); i++)
	{
		int v = graph[u][i];
		if (v != fa[u] && v != son[u])
		{
			dfs2(v, v);
		}
	}
	out[u] = dfn;
}

int queryV(int u, int v)
{
	int res = 0;
	while (top[u] != top[v])
	{
		if (dep[top[u]] < dep[top[v]])
		{
			swap(u, v);
		}
		// u
		res += query(in[top[u]], in[u]);
		u = fa[top[u]];
		if (u == -1)
		{
			break;
		}
	}
	if (u == -1)
	{
		while (top[v] != 1)
		{
			res += query(in[top[v]], in[v]);
			v = fa[top[v]];
		}
	}
	else
	{
		if (dep[u] < dep[v])
		{
			swap(u, v);
		}
		// u
		res += query(in[v], in[u]);
	}

return res;
}

struct qry
{
	int u, v, w, ans, id;
	void input()
	{
		scanf("%d%d%d", &u, &v, &w);
	}
	bool operator<(const qry& b) const
	{
		return w < b.w;
	}
};
bool cmp(const qry& a, const qry& b)
{
	return a.id < b.id;
}
qry qs[MAXN];
pair<int, int> wts[MAXN];

int main()
{
#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	int startTime = clock();
#endif

scanf("%d%d", &n, &q);
	edgeCnt = n + 1;
	for (int i = 0; i < n - 1; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		graph[u].push_back(edgeCnt);
		graph[v].push_back(edgeCnt);
		graph[edgeCnt].push_back(v);
		graph[edgeCnt].push_back(u);
		have[edgeCnt] = 1;
		wt[u] = wt[v] = INF;
		wt[edgeCnt] = w;
		edgeCnt++;
	}
	for (int i = 1; i < edgeCnt; i++)
	{
		wts[i] = { wt[i], i };
	}
	sort(wts + 1, wts + edgeCnt);
	n = 2 * n - 1;
	init();
	dfs1();
	dfs2();

for (int i = 0; i < q; i++)
	{
		qs[i].input();
		qs[i].id = i;
	}
	sort(qs, qs + q);
	int cIndex = 1;
	for (int i = 0; i < q; i++)
	{
		if (i == 0 || qs[i].w != qs[i - 1].w)
		{
			for (; cIndex < edgeCnt; cIndex++)
			{
				if (wts[cIndex].first <= qs[i].w)
				{
					modify(in[wts[cIndex].second], 1);
				}
				else
				{
					break;
				}
			}
		}
		qs[i].ans =  queryV(qs[i].u, qs[i].v);
	}
	sort(qs, qs + q, cmp);
	for (int i = 0; i < q; i++)
	{
		printf("%d\n", qs[i].ans);
	}

#ifndef ONLINE_JUDGE
	printf("Time = %dms\n", clock() - startTime);
#endif
	return 0;
}
```

## K. MORE XOR

我们通过打表很容易发现答案的分布规律和数字贡献的关系。

- mod 4 = 1时，把mod 4 = 1的位置异或起来
- mod 4 = 2时，把mod 4 = 1和2的位置异或
- mod 4 = 3时，mod  4 = 2的位置异或
- mod 4 = 0时，答案为0

用前缀异或和维护一下就好啦~

```cpp
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
#define PI acos(-1)
#define eps 1e-9
#define mp(x,y) make_pair(x,y)
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
#define LOCAL

const int MAXN = 100000+10;
int n;
int a[MAXN];

void solve()
{
	int q;
	scanf("%d", &q);
	int l, r;
	while( q-- ){
		scanf("%d %d", &l, &r);
		int all = r-l+1;
		int ans;
		if( all%4 == 0 ){
			ans = 0;
		}else if( all%4 == 1 ){
			if( l >= 4 ) ans = a[r]^a[l-4];
			else ans = a[r];
		}else if( all%4 == 2 ){
			if( l >= 3 ) ans = a[r]^a[l-3];
			else ans = a[r];
			if( l >= 4 ) ans ^= a[r-1]^a[l-4];
			else ans ^= a[r-1];
		}else{
			if( l >= 3 ) ans = a[r-1]^a[l-3];
			else ans = a[r-1];
		}
		printf("%d\n", ans);
	}
}

int main(int argc, char * argv[]) 
{
    #ifdef LOCAL
    //freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stdout);
    #endif
	int t;
	scanf("%d", &t);
	while( t-- ){
		scanf("%d", &n);
		for(int i = 1; i <= n; i++ ){
			scanf("%d", &a[i]);
			if( i >= 4 ){
				a[i] ^= a[i-4];
			}
		}
		solve();
	}
    return 0;
}
```

## L. qiqi'tree

计算几何，挺裸的，直接模拟树的生长，边长边切。

- 如果切了根就输出0。
- 切线和树枝重合算切除。

维护一下这一轮没被切断的树枝，下一轮接着长。

```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <complex>
#include <stack>
#define SET0(X) memset(X,0,sizeof(X));
#define SET_1(X) memset(X,-1,sizeof(X));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN = 1e5+4;
const double PI = acos(-1.0);
const double EPS = 1e-8;
const int INF = 0x3f3f3f3f;
int L,n;
double x,y,k;

int online(double a,double b){
    double bb=k*(a-x)+y;
    if(abs(bb-b)<EPS){
        return 0;
    }else{
        if(b>bb)
            return 1;
        else
            return -1;
    }
}
double dir[6][2]={{0,1},{0.5*sqrt(3),0.5},{0.5*sqrt(3),-0.5},{0,-1},{-0.5*sqrt(3),-0.5},{-0.5*sqrt(3),0.5}};
double dfs(double a,double b,int d,double len,int dep){
    if(online(a,b)==0||dep==n){
        return 0;
    }else{
        double t = -(k*(a-x)+y-b)/(k*dir[d][0]-dir[d][1]);
//        printf("a:%lf b:%lf len:%lf t:%lf\n",a,b,len,t);
        if(t>=0&&t<=len){
            return t;
        }else{
            double na=a+len*dir[d][0];
            double nb=b+len*dir[d][1];
            double nlen = len/4;
            return len+dfs(na,nb,((d-1)%6+6)%6,nlen,dep+1)+dfs(na,nb,d,nlen,dep+1)+dfs(na,nb,(d+1)%6,nlen,dep+1);
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d%lf%lf%lf",&L,&n,&x,&y,&k);
        printf("%.6lf\n",dfs(0,0,0,L,0));
    }
    return 0;
}
```

## M. Subsequence

直接建立一个next数组，然后每个节点尝试往26个字母方向跳即可。

#define INF 0x3f3f3f3f
#define memset0(x) memset(x, 0, sizeof(x))
#define memsetM1(x) memset(x, -1, sizeof(x))
#define memsetINF(x) memset(x, INF, sizeof(x))

using namespace std;

const int MAXN = 1e5 + 5;
char str[MAXN];
int nxt[MAXN][26];
char str2[MAXN];
int lst[26];

int main()
{
#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	int startTime = clock();
#endif
	scanf("%s", str + 1);
	int n = strlen(str + 1);
	for (int i = 1; i <= n; i++)
	{
		int id = str[i] - 'a';
		for (int j = i - 1; j >= lst[id]; j--)
		{
			nxt[j][id] = i;
		}
		lst[id] = i;
	}
	int t;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%s", str2);
		int loc = 0;
		bool yes = true;
		for (int i = 0; str2[i]; i++)
		{
			int id = str2[i] - 'a';
			if (nxt[loc][id])
			{
				loc = nxt[loc][id];
			}
			else
			{
				yes = false;
				break;
			}
		}
		if (yes)
		{
			puts("YES");
		}
		else
		{
			puts("NO");
		}
	}

#ifndef ONLINE_JUDGE
	printf("Time = %dms\n", clock() - startTime);
#endif
	return 0;
}
```
  [1]: http://xzm2001.cn/usr/uploads/2019/04/4177443737.pdf

Last modification：April 22nd, 2019 at 12:38 am

If you think my article is useful to you, please feel free to appreciate

Comment *

私密评论

Name *

Email *

Site

2019南昌邀请赛网络赛个人记录（附官方题解）

Leave a Comment

2019南昌邀请赛网络赛个人记录（附官方题解）

北京理工大学第七届程序设计新生赛题解（unofficial）

第 43 届 ACM/ICPC 亚洲区域赛（南京）总结

北京理工大学第八届程序设计新生赛题解

Beijing Institute of Technology 2019.6 Monthly Contest 题解

北京理工大学第八届程序设计新生赛题解

OI~XCPC流水账

欢迎使用来到xzm's blog

Codeforces Round #539 (1113,1109) 个人题解

第 4 届中国大学生程序设计竞赛总决赛总结

2019南昌邀请赛网络赛个人记录（附官方题解）

Leave a Comment

2019南昌邀请赛网络赛 个人记录（附官方题解）

2019南昌邀请赛网络赛个人记录（附官方题解）