暑假集训模拟赛（1）

时间：2022-12-20 12:41:01

Problem A: 贪吃蛇

Time Limit: 2000 ms Memory Limit: 512 MB

Description

暑假集训模拟赛（1）

Input

暑假集训模拟赛（1）

Output

暑假集训模拟赛（1）

Sample Input
【样例输入1】

4 5

##...

..1#@

432#.

...#. 

【样例输出1】

4 

【样例输入2】 

4 4

#78#

.612

.543

..@. 

【样例输出2】

6 

【样例输入3】 

3 2

3@

2#

1# 

【样例输出3】

 -1

HINT

暑假集训模拟赛（1）

Solution

没什么好讲的了吧。暴力就好了。

#include<bits/stdc++.h>
using namespace std;
int mapn[16][16];
const int movex[4]={0,1,0,-1};
const int movey[4]={1,0,-1,0};
struct snake{
    int x,y;
}s[10];
int sum[16][16];
int ans=1e9;
int dx,dy;
int len=0;
void dfs(int x1,int y1,int now){
    //if(x1==dx&&y1==dy)cout<<now<<endl;
    if(now>=sum[x1][y1])return;
    sum[x1][y1]=now;
    if(x1==dx&&y1==dy){
        if(now<=ans)ans=now;
        return;
    }
    for(int i=0;i<4;++i){
        int x=x1+movex[i],y=y1+movey[i];
        //if(x==14&&y==7)cout<<mapn[x][y]<<endl;
        if(mapn[x][y]){
            snake tmp=s[len];
            for(int i=len;i>=2;--i)s[i]=s[i-1];
            s[1]={x,y};
            mapn[s[len].x][s[len].y]=1;
            mapn[x][y]=0;
            dfs(x,y,now+1);
            mapn[s[len].x][s[len].y]=0;
            mapn[x][y]=1;
            for(int i=1;i<len;++i)s[i]=s[i+1];
            s[len]=tmp;
        }
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=15;++i){
        for(int j=1;j<=15;++j)sum[i][j]=1e9;
    }
    int hx,hy;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            char ch;
            cin>>ch;
            if(ch=='@'){
                mapn[i][j]=1;
                dx=i,dy=j;
            }
            if(isdigit(ch)){
                mapn[i][j]=0;
                s[ch-'0']={i,j};
            }
            if(ch=='.'){
                mapn[i][j]=1;
            }
            if(ch=='1'){
                hx=i,hy=j;
            }
            if(isdigit(ch)&&ch-'0'>len){
                len=ch-'0';
            }
        }
    }
    mapn[s[len].x][s[len].y]=1;
    //cout<<len<<endl;
    dfs(hx,hy,0);
    //for(int i=1;i<=n;++i){
        //for(int j=1;j<=m;++j){
            //cout<<(sum[i][j]==1e9?0:sum[i][j])<<" ";
        //}
        //cout<<endl;
    //}
    printf("%d\n",ans==1e9?-1:ans);
}

Problem B: 字符串

Time Limit: 3000 ms Memory Limit: 1024 MB

Description

暑假集训模拟赛（1）

UPD:本题字符集为全体小写字母

Input

暑假集训模拟赛（1）

Output

暑假集训模拟赛（1）

Sample Input
5
1 abc
3 abcabc
0 abc 
3 aba
1 abababc
Sample Output
2

HINT

暑假集训模拟赛（1）

Solution

把所有的字符串，无论询问还是查询，丢进一个AC自动机里，跑出fail

然后建立fail树。根据fail树的性质，对于一棵以u为根节点的子树，所有子树内的节点所代表的字符串都包含u。

像树剖一样维护fail树，每插入一个就给子树全部出现次数+1 。

查询就是trie树上每个节点的出现次数加起来就好了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct qwq{
    int v;
    int nxt;
}edge[2000001];
int head[2000001];
int cnt=-1;
void add(int u,int v){
    edge[++cnt].nxt=head[u];
    edge[cnt].v=v;
    head[u]=cnt;
}
struct trie{
    int ch[26];
    int fail;
}t[2000001];
int tot;
int num[2000001];
void insert(char s[],int id){
    int len=strlen(s+1);
    int x=0;
    for(int i=1;i<=len;++i){
        int c=s[i]-'a';
        //cout<<c<<endl;
        if(!t[x].ch[c]){
            t[x].ch[c]=++tot;
        }
        x=t[x].ch[c];
    }
    num[id]=x;
}
void getfail(){
    queue<int> q;
    for(int i=0;i<26;++i){
        if(t[0].ch[i]){
            t[t[0].ch[i]].fail=0;
            q.push(t[0].ch[i]); 
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;++i){
            if(t[u].ch[i]){
                //cout<<t[u].fail<<" "<<t[t[u].fail].ch[i]<<endl;
                t[t[u].ch[i]].fail=t[t[u].fail].ch[i];
                q.push(t[u].ch[i]);
            }
            else {
                t[u].ch[i]=t[t[u].fail].ch[i];
            }
        }
    }
    for(int i=1;i<=tot;++i){
        //cout<<t[i].fail<<" ";
        add(t[i].fail,i);
    }
    //cout<<endl;
}
int dfn[2000001];
int siz[2000001];
int ind;
void dfs(int u){
    dfn[u]=++ind;
    siz[u]=1;
    for(int i=head[u];~i;i=edge[i].nxt){
        int v=edge[i].v;
        dfs(v);
        siz[u]+=siz[v];
    }
}
ll c[2000001];
#define lowbit(x) x&-x
void upd(int x,int v){
    while(x<=ind){
        //cout<<x<<" ";
        c[x]+=v;
        x+=lowbit(x);
    }
}
int query(int x){
    int ans=0;
    while(x){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
void update(int u,int i){
    //cout<<dfn[u]<<" "<<siz[u]<<endl;
    upd(dfn[u],i);
    upd(dfn[u]+siz[u],-i);
}
int tott;
char s[2000001];
ll solve(int l,int r){
    ll ans=0;
    int x=0;
    for(int i=l;i<=r;++i){
        int c=s[i]-'a';
        x=t[x].ch[c];
        //cout<<x<<" ";
        //cout<<dfn[x]<<endl;
        ans+=query(dfn[x]);
    }
    return ans;
}
char a[2000001];
ll opt[2000001];
int st[2000001];
int len[2000001];
int main(){
    memset(head,-1,sizeof(head));
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;++i){
        scanf("%lld%s",&opt[i],a+1);
        insert(a,i);
        len[i]=strlen(a+1);
        st[i]=tott+1;
        for(int j=1;j<=len[i];++j){
            s[++tott]=a[j];
        }
    }
    getfail();
    dfs(0);
    //for(int i=1;i<=tot;++i)cout<<siz[i]<<" ";
    ll mask=0;
    for(int i=1;i<=m;++i){
        opt[i]^=mask;
        if(opt[i]==1){
            //cout<<num[i]<<endl;
            update(num[i],1);
        }
        if(opt[i]==2){
            update(num[i],-1);
        }
        if(opt[i]==3){
            ll tmp;
            //cout<<i<<endl;
            printf("%lld\n",tmp=solve(st[i],st[i]+len[i]-1));
            mask^=abs(tmp);
        }
    }
}

Problem C: 都城

Time Limit: 1000 ms Memory Limit: 512 MB

Description

暑假集训模拟赛（1）

Input

暑假集训模拟赛（1）

Output

暑假集训模拟赛（1）

Sample Input
4
1 4
2 4
3 4
Sample Output
2
2
2
3

HINT

暑假集训模拟赛（1）

Solution

先随意选择一个点，算出这个点如果让它当首都需要改几条边。

然后遍历它的后继，对于这个后继，只需要修改原点到这个后继的这条边就可以满足题目需求了。

然后遍历后继的后继，以此类推就可以了。

用一个vis记录一下每条边的状态就可以知道这条边有没有改了。

#include<bits/stdc++.h>
using namespace std;
int read(){
    char ch;
    int num=0;
    int f=1;
    ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();   
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num*f;
}
void out(int num){
    if(num>9)out(num/10);
    putchar(num%10+'0');
}
struct qwq{
    int u1,v1;
    int v;
    int nxt;
}edge[4000001];
int head[2000001];
int cnt=-1;
void add(int u,int v,int u1,int v1){
    edge[++cnt].nxt=head[u];
    edge[cnt].v=v;
    edge[cnt].u1=u1,edge[cnt].v1=v1;
    head[u]=cnt;
}
bool vis[2000001];
int ans[2000001];
void dfs(int u,int fa){
    for(int i=head[u];~i;i=edge[i].nxt){
        int v=edge[i].v,v1=edge[i].v1;
        if(v==fa)continue;
        if(v1!=v)vis[i]=true,ans[1]++;
        dfs(v,u);
    }
}
void solve(int u,int fa){
    for(int i=head[u];~i;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==fa)continue;
        if(!vis[i])ans[v]=ans[u]+1;
        else ans[v]=ans[u]-1;
        solve(v,u);
    }
}
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
    memset(head,-1,sizeof(head));
    int n;
    n=read();
    for(int i=1;i<n;++i){
        int u,v;
        u=read(),v=read();
        add(u,v,u,v);
        add(v,u,u,v);
    }
    dfs(1,-1);
    solve(1,-1);
    for(int i=1;i<=n;++i){
        out(ans[i]);
        putchar('\n');
    }
}
标签：

相关文章