xzm2019

2019南昌邀请赛网络赛 个人记录(附官方题解)
这是一个防止代码因为账号销毁丢失而写的记录官方题解:南昌网络赛题解.pdfSolvedABCDEFGHIJKLM9...
扫描右侧二维码阅读全文
20
2019/04

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

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

官方题解:南昌网络赛题解.pdf

SolvedABCDEFGHIJKLM
9/13O.OO...OOOOOO
  • 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和万能的群友来得到第五个答案。

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

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

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

C. Angry FFF Party

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

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);
            }
        }
    }

}

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$里一定没有负号

#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$。

#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表维护区间最大最小值,然后加一个单调栈即可。

#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了

#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

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

#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。
  • 切线和树枝重合算切除。

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

#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个字母方向跳即可。

#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 = 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;
}
Last modification:April 22nd, 2019 at 12:38 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment