联考(Oct28)赛后分析总结

· · 个人记录

0x00 比赛记录

Oct 28 Windy

正式集训第一天。晚上照常联考，但是这次加了挡板。

终于不用担心别人听我自言自语时突然听到正解了

T1看了半小时，想到了染色tarjan的离线查询。正巧我还没写过，于是就去尝试了一次。时间复杂度估计O(N+QlogQ)。2s时限大抵能过。

T2字符串，回想起某老师讲过的Hash可以加快搜索进度。于是暴力地写了Hash，查询O(1)，但是枚举字符串长度什么的让时间复杂度降到了O(nm)。估计药丸。

T3是背包问题，但是一看数据量的大小，直接暴毙。掐着时间写了个假的dfs交了上去。

结束后大家都在说T2正解是KMP。而我压根就不会KMP。然后又知道背包问题竟然真是用背包。到了现在我都还没搞懂。

最后拿了150。T2竟然暴毙了，数组没开大。T3后来乱调dfs竟然调到了90。但是直到现在我也不会写T2、T3正解。

0x01 Tree

题意

输入一棵n个点的树和n-1条边，之后给出Q个(x,y,z)的查询。如果将第z条输入的边删掉再连上点x和点y不能使整棵树仍然连通，输出YES。否则输出NO。 n≤200000,Q≤2000000。

输入格式

第一行一个正整数 n，表示节点个数。

接下来 n-1 行，每行两个正整数 x，y，表示原来树上存在一条连接编号为 x 的节点和编号为 y 的节点的边。

第 n+1 行一个正整数 Q，表示询问次数。

接下来 Q 行，每行三个正整数 x，y，z，表示一个询问（含义如题所示）。

输出格式

输出共 Q 行。

对于每一个询问，如果不连通输出 YES，否则输出 NO。

样例输入

5
1 2 
2 3 
2 4 
4 5 
3
2 5 3 
2 3 1 
1 5 2

样例输出

NO
YES
YES

分析

虽然我最后发现一个时间戳就能解决不少麻烦，但是我还是先讲讲我的那个麻烦的做法。

首先对查询进行处理，按照查询中的z从小到大排序(sort)。手写一个二分查询起到lower_bound的作用,方便快速找到关于第x条边的首个查询在数组中的位置。

每搜到新的点记录并更新color（事实上是时间戳），每一条边搜完之后立即进行查询，如果某点数值在到达该点时记录的颜色数值与当前颜色数值之间，说明该点在这条边所连的子树上，否则在含根节点的主树上。那么如果两个点在相同子树上就不连通，反之则连通。

这条边是连接这两个连通块的充要条件就是这条边有且仅有一个点在被割开的子树内

时间复杂度O(N+QlogQ)。用时间戳(DFS序)会更快，运用的也以上的理论，但不用离线查询，时间复杂度O(N+Q)。

注意要进行快读，要不然会超时间。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int head[201000],nxt[401000],rdc[401000],num[401000];
int visited[201000],color=0;
struct ques{
    int x,y;int z;int loc;
}q[2010000];
int n,Q;
bool ans[2010000];
inline int read()
{
    int res=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res;
}
bool cmp(ques a,ques b){
    return a.z<b.z;
}
int tnt=0;
void add(int u,int v,int z){
    nxt[++tnt]=head[u];
    head[u]=tnt;
    rdc[tnt]=v;
    num[tnt]=z;
}
bool check(int x,int color)
{
    return visited[x]<=color;
}
int search(int z){
    int l=0,r=Q;
    while(l<r){
        int mid=(l+r)>>1;
        if(q[mid].z>=z)
            r=mid;
        else
            l=mid+1;
    }
    return l;
}
void questioner(int z,int color)
{
    int i=search(z);
    for(;z==q[i].z;i++)
        if(check(q[i].x,color)==check(q[i].y,color))
            ans[q[i].loc]=true;
        else;
}
void dfs(int p){
    visited[p]=++color;
    for(int i=head[p];i;i=nxt[i])
        if(!visited[rdc[i]]){
            dfs(rdc[i]);
            questioner(num[i],visited[p]);
            visited[p]=color;
        }
    return;
}
int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    n=read();
    int u,v;
    for(int i=1;i<=n-1;i++){
        u=read();v=read();
        add(u,v,i);
        add(v,u,i);
    }
    Q=read();
    for(int i=0;i<Q;i++){
        q[i].x=read();
        q[i].y=read();
        q[i].z=read();
        q[i].loc=i;
    }
    sort(q,q+Q,cmp);
    dfs(1);
    for(int i=0;i<Q;i++)
        if(ans[i])
            puts("YES");
        else
            puts("NO");
    return 0;
}

0x02 Memory

题意

输入一个字符串，求这段字符串里最长的既是前缀又是后缀还在中间某个地方出现过（非前缀非后缀的出现）的最长的子串是什么。

输入格式

一行给出一个由小写字母组成的字符串。字符串长度<=100000。

输出格式

输出满足题目要求的非空子串，如果不存在这样的非空子串输出“CD can't remember anything.”（不含双引号）

样例输入

fixprefixsuffix

样例输出

fix

分析

预处理一个Hash数组和一个存储27^i的数组。搜索时按长度从大到小搜索，如果首尾Hash值再寻找中间是否有情况满足。

怎么用Hash前缀数组求？运用Hash的性质！（Tips:为什么要存27^i？）

KMP不会写。直接跳过。事实上Hash只跑了40ms左右。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define mod 1000000009
using namespace std;
string s;
int len;
long long hash[1010000];
long long pluser[1010000],crosser[1010000];
bool pos=0,poslen=0;
void reset()
{
    crosser[0]=1;
    for(int i=1;i<=len;i++){
        hash[i]=(hash[i-1]*27+s[i-1]-'a'+1)%mod;
        crosser[i]=crosser[i-1]*27%mod;
    }
}
long long pick(int loc,int l){
    return (hash[loc+l]-(hash[loc]*crosser[l])%mod+mod)%mod;
}
bool check(int l){
    for(int i=1;i+l<len;i++)
        if(pick(i,l)==hash[l])
            return true;
    return false;
}
int main()
{
    cin>>s;
    len=s.length();
    reset();
    for(int i=len-2;i>=1;i--){
        if(hash[i]==pick(len-i,i))
            if(check(i)){
                for(int j=0;j<i;j++)
                    cout<<s[j];
                return 0;
            }
    }
    puts("CD can't remember anything.");
    return 0;
}

0x03 Gold

题意

话说某一天，CD 在爬树的时候发现了一个神奇的山洞，那里有许许多多体 积价值都不同的金块，而且每当他拿走一块金块，原地又会出现一个一模一样的 金块，也就是说金块是源源不断地出现的(当然，他不会把这样的好事告诉 moreD)。CD 这次想，终于可以赚够足够的钱来摆脱 moreD 的奴役了。于是就 在第二天悄悄地搬来了 S 个，体积都为 Y 的袋子，准备把价值尽量多的金子搬 回去卖掉，然后摆脱 moreD 的奴役甚至是把 moreD 变成他的宠物。

山洞里原来共有 n 块不可切割的金块，第 i 块金块的体积是 Vi，价值是 Wi。 不得不说的是，moreD 曾经教过 CD 一个神奇的魔法，可以把两个袋子合成一 个袋子，但是驱动这样的魔法有 C 的代价。你要告诉 CD，这一次他最多能获利 多少（能带走的金块价值扣除驱动魔法的代价）。

输入格式

第一行四个正整数 n，S，Y，C。分别表示金块的个数、袋子个数、袋子的 容积、把两个袋子合成一个的代价。 接下来 n 行，每行两个整数 Wi，Vi。

数据满足 1≤S ≤1000 ，1≤ Y≤1000000000，1≤N ≤ 1000，1≤C≤10000，1≤Wi≤100，1≤Vi≤18。

输出格式

输出一个整数表示 CD 的最大获利。

样例输入

2 5 3 1
1 2 
5 7

样例输出

6

分析

虽然用了DFS，但是后来魔改始终搜不出某点的正解。因而代码就不放在这里。（在分析里的代码应该都是能AC的。）

（下面是官方正解）

CD: 背包太大了，把背包全部预处理出来是不科学的。然而我们可以采用部分贪心的思想。可以想到，当体积大到一定程度的时候，我们只需要用性价比最高的金块填充就可以了，于是我们先选出性价比最高的物品，假设它的体积为 v，重量为 w，如果 DP 到某个 i 时，对于所有 i-w<k<=i，满足 g(k-v)+w = g(k)，就可以停止 DP 了，因为后面的都会满足 g(i)+w=g(i+v)，这样我们就可以得到所有的 g 值了，并且可以证明需要预处理的状态 数不超过 v3。

另外其实可以观察到，对于 v 相同的情况，只有 w 最大的金块是有用的，于是其实真 正有用的金块个数不超过 18。