[20181023][模拟赛]

题目

T1

思路

trie,AC自动机，hash都可做。良心出题人

代码

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 200000 + 100;
int a[N][30];
ll read(){
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int tot,n,len;
int bz[N * 50];
void add(char *s) {
    int now = 0;
    for(int i = 0;i < len;++i) {
        if(!a[now][s[i] - 'a']) a[now][s[i] - 'a'] = ++tot;
        now = a[now][s[i] - 'a'];
    }
    bz[now] = 1;
}
int Len;
char SS[N]; 
int find(int x) {
    int now = 0;
    for(int i = x;i <= Len;++i) {
        if(!a[now][SS[i] - 'a']) {
            return 0;
        }
        now = a[now][SS[i] - 'a'];
        if(bz[now]) return 1;
    }
    return 0;
}
char s[100];
int main() {
    freopen("monitor.in","r",stdin);
    freopen("monitor.out","w",stdout);
    Len = read();n = read();len = read();
    for(int i = 1;i <= n;++i) {
        scanf("%s",s);
        add(s);
    }
    scanf("%s",SS + 1);
    for(int i = 1;i <= Len;++i) {
        if(find(i)) {
            printf("%d",i);
            return 0;
        }
    }
    puts("no");
    return 0;
}

T2

20分思路

对于没有k = 0操作的分，可以直接利用前缀和来做，用sum[i]表示从节点i走到根节点所经过的路程。当查询x,y时，直接用sum[y] - sum[x]就是从x走到y所经过的路程

40分思路

对于只有一次k = 0操作的情况，整棵树中只有一个环。并且可以发现，因为整棵树时联通的，所以一定可以从某个位置走到这个环，走上几圈再回去。因为走过来又走回去，所以中间路程上的话费就抵消掉了。所以每次查询只要查询一下是否由x * k + w = t。k为那个环的大小，w为从x走到y的简单路径的长度，t为查询的时候所给出的t。

100分思路

其实通过40分思路已经可以发现些什么了。现在只不过是从一个环变成了n个环。那么上面那个式子就变成了,\(x_1 * k_1 + x_2 * k_2+...+x_n*k_n + w=t\)根据某某定理，这个式子有解的充要条件是\(gcd(x_1,x_2,x_3...x_n)|t-w\)。所以得出结论：这是一道数学题。

代码

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 100000 + 100,logN = 20;
ll read(){
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
struct node {
    int v,nxt;
    ll w;
}e[N * 2];
int head[N],ejs;
void add(int u,int v,int w) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w;
}
ll sum[N];
void dfs(int u,int father) {
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == father) continue;
        sum[v] = sum[u] + e[i].w;
        dfs(v,u);
    }
}
ll ab(ll x) {
    return x > 0 ? x : -x;
}
ll gcd(ll a,ll b) {
    return !b ? a : gcd(b, a % b);
}
ll g;
int main() {
    freopen("lab.in","r",stdin);
    freopen("lab.out","w",stdout);
    int n = read(),q = read();
    for(int i = 1;i < n; ++i) {
        int u = read(), v = read(),w = read();
        add(u,v,w);add(v,u,-w);
    }
    dfs(1,0);
    while(q--) {
        int bz = read(),x = read(),y = read(),w = read();
        if(bz == 0) {
            if(!g) g = ab(sum[x] - sum[y] + w);
            else g = gcd(g,ab(sum[x] - sum[y] + w)); 
        }
        else {
            if(sum[y] - sum[x] == w) puts("yes");
            else if(g == 0) puts("no");
            else if((w - (sum[y] - sum[x])) % g == 0) puts("yes");
            else puts("no");
        }
    }
    return 0;
}
/*
7 5 
1 2 1
1 3 5
2 4 3
2 5 4
3 6 8
3 7 7
0 4 5 7
0 4 6 15
0 5 6 18 
0 1 4 5
0 3 4 5
*/

T3

思路

思路其实并不难，进行两边dfs，分别处理一些东西。考场上写完这道题就再也不想讲思路了。看代码理解吧

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
ll read(){
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
ll ans[N][2];
int n,Q;
struct node {
    int u,v,nxt,w;
}e[N * 2];
int head[N],ejs;
void add(int u,int v,int w) {
    e[++ejs].v = v;e[ejs].w = w;e[ejs].nxt = head[u];head[u] = ejs;
}
queue<int>q;
ll dis[N];
void bfs(int U) {
    while(!q.empty()) q.pop();
    memset(dis,-1,sizeof(dis));
    q.push(U);
    dis[U] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u];i;i = e[i].nxt) {
            int v = e[i].v;
            if(dis[v] != -1) continue;
            dis[v] = dis[u] + e[i].w;
            if(dis[v] & 1) ans[U][1] += dis[v];
            else ans[U][0] += dis[v];
            q.push(v);
        }
    }
    return;
}
void BF1() {
    for(int i = 1;i < n;++i) {
        int u = read(),v = read(),w = read();
        add(u,v,w);
        add(v,u,w);
    }
    for(int i = 1;i <= n;++i) bfs(i);
    while(Q--) {
        int x = read();
        printf("%lld %lld\n",ans[x][1],ans[x][0]);
    }
    return;
}
ll num[N][2];//到每个节点为奇数偶数的点得个数。
ll nnum[N][2];
ll f[N][2];//在当前子树中到当前点为偶数奇数得大小
//ans[N][2]为真正答案 
void dfs1(int u,int father) {
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == father) continue;
        dfs1(v,u);
        int w = e[i].w;
        if(w & 1) {
            num[u][0] += num[v][1];
            num[u][1] += num[v][0] + 1 ;
            f[u][0] += num[v][1] * w + f[v][1];
            f[u][1] += (num[v][0] + 1) * w + f[v][0];
        }
        else {
            num[u][0] += num[v][0] + 1;
            num[u][1] += num[v][1];
            f[u][0] += (num[v][0] + 1) * w + f[v][0];
            f[u][1] += num[v][1] * w + f[v][1];
        }
    }
}
void dfs2(int u,int father) {
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == father) continue;
        ll w = e[i].w;
        if(w & 1) {
            nnum[v][1] = num[v][1] + nnum[u][0] - num[v][1] + 1;
            nnum[v][0] = num[v][0] + nnum[u][1] - num[v][0] - 1;
            ans[v][1] = f[v][1] + (ans[u][0] - (num[v][1] * w + f[v][1])) + (nnum[v][1] - num[v][1]) * w;
            ans[v][0] = f[v][0] + (ans[u][1] - ((num[v][0] + 1) * w + f[v][0])) + (nnum[v][0] - num[v][0]) * w;
        }
        else {
            nnum[v][1] = num[v][1] + nnum[u][1] - num[v][1];
            nnum[v][0] = num[v][0] + nnum[u][0] - num[v][0] - 1 + 1;
            ans[v][1] = f[v][1] + (ans[u][1] - (num[v][1] * w +f[v][1])) + (nnum[v][1] - num[v][1]) * w;
            ans[v][0] = f[v][0] + (ans[u][0] - ((num[v][0] + 1) * w + f[v][0])) + (nnum[v][0] - num[v][0]) * w;
        }
        dfs2(v,u);
    }
}
void BF2() {
    for(int i = 1;i < n; ++i) {
        int u = read(),v = read(),w = read();
        add(u,v,w);add(v,u,w);
    }
    dfs1(1,0);
    nnum[1][1] = num[1][1];
    nnum[1][0] = num[1][0];
    ans[1][1] = f[1][1];
    ans[1][0] = f[1][0];
    dfs2(1,0);
    while(Q--) {
        int x = read();
        printf("%lld %lld\n",ans[x][1],ans[x][0]);
    }
}
int main() {
    freopen("civilization.in","r",stdin);
    freopen("civilization.out","w",stdout);
    n = read(),Q = read();
    if(n <= 2000) {
        BF1();
        return 0;
    }
    BF2();
    return 0;
}
/*
4 4
1 2 1
2 3 2
2 4 3
1 2 3 4
*/