10.23NOIP模拟题

叉叉
题目描述
现在有一个字符串，每个字母出现的次数均为偶数。接下来我们把第一次出现的字母 a 和第二
次出现的 a 连一条线，第三次出现的和四次出现的字母 a 连一条线，第五次出现的和六次出现
的字母 a 连一条线...对其他 25 个字母也做同样的操作。
现在我们想知道有多少对连线交叉。交叉的定义为一个连线的端点在另外一个连线的内部，另
外一个端点在外部。
下图是一个例子，共有三对连线交叉（我们连线的时候，只能从字符串上方经过）。
输入格式
题目名称叉叉
程序文件名 cross
输入文件名 cross.in
输出文件名 cross.out
每个测试点时限 1 秒
内存限制 128MB
测试点数目 10
每个测试点分值 10
是否有部分分无
试题类型传统
一行一个字符串。保证字符串均由小写字母组成，且每个字母出现次数为偶数次。
输出格式
一个整数，表示答案。
样例输入
abaazooabz
样例输出
3
数据范围
对于 30% 的数据，字符串长度不超过 50。
对于 100% 的数据，字符串长度不超过 100,000。

/*

因为是两个相同的为一个区间，想到用栈来实现

开一个vis表示元素是否在栈中出现，开两个栈，遇到出现过的元素就把两个相同元素中间的那些倒到另一个栈中

更新答案加上两个相同元素中间元素换了几次栈

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#include<stack>

#define N 100007

using namespace std;

int n,ans;

char s[N];

map<char,bool>vis;

map<char,int>val;

stack<char>st1;

stack<char>st2;

int main()

{

    freopen("cross.in","r",stdin);

    freopen("cross.out","w",stdout);

    scanf("%s",s);n=strlen(s);

    for(int i=;i<n;i++)

    {

        if(!vis[s[i]]) val[s[i]]=;

        if(st1.empty()) st1.push(s[i]),vis[s[i]]=;

        else

        {

            if(!st1.empty() && st1.top()==s[i])

            {

                vis[s[i]]=;ans+=val[s[i]];st1.pop();continue;

            }

            else if(st1.top()!=s[i] && !vis[s[i]])

            {

                vis[s[i]]=;st1.push(s[i]);continue;

            }

            else if(vis[s[i]] && !st1.empty())

            {

                while(st1.top()!=s[i])

                {

                    int u=st1.top();st1.pop();

                    st2.push(u);val[u]++;

                }

                st1.pop();vis[s[i]]=;ans+=val[s[i]];val[s[i]]=;

                while(!st1.empty()) st2.push(st1.top()),st1.pop();

                while(!st2.empty())

                {

                    int u=st2.top();st2.pop();

                    st1.push(u);

                }

            }

        }

    }

    printf("%d\n",ans);

    fclose(stdin);fclose(stdout);

    return ;

}

跳跳虎回家
英⽂名称: move
时间限制: 1s
空间限制: 256M
题⽬描述
跳跳虎在外⾯出去玩忘了时间，现在他需要在最短的时间内赶回家。
跳跳虎所在的世界可以抽象成⼀个含有个点的图（点编号从到），跳跳虎现在在号点，跳跳虎的家在号点。
图上⼀共有条单向边，通过每条边有固定的时间花费。
同时，还存在若⼲个单向传送通道，传送通道也有其时间花费。
传送通道⼀般来说⽐普通的道路更快，但是跳跳虎最多只能使⽤次。
跳跳虎想知道他回到家的最⼩时间消耗是多少。
输⼊格式
第⼀⾏输⼊个整数（表⽰点数，表⽰普通道路的数量，表⽰传送通道的数量，表⽰跳跳虎最多使⽤次传送通道）
接下来⾏每⾏个整数，表⽰有⼀条从到，时间花费为的普通道路( )
接下来⾏每⾏个整数，表⽰有⼀条从到，时间花费为的传送通道( )
输出格式
输出⼀⾏⼀个整数表⽰最⼩时间消耗，如果没法回到家输出。
样例输⼊
5 5 2 1
1 2 1
1 3 2
2 4 2
3 4 3
4 5 4
1 4 1
2 5 1
样例输出
2
数据范围和约定
对于的数据，
对于另外的数据，
对于的数据，
n 1 n 1 n
m
k
4 n,m,q,k n m q k k
m 3 u,v,w u v w 1 ≤ u,v ≤ n,1 ≤ w ≤ 10 3
q 3 x,y,z x y z 1 ≤ x,y ≤ n,1 ≤ z ≤ 10 3
−1
30% 1 ≤ n ≤ 500,0 ≤ m,q ≤ 2000,k = 0
30% 1 ≤ n ≤ 500,0 ≤ m,q ≤ 2000,k = 1
100% 1 ≤ n ≤ 500,0 ≤ m,q ≤ 2000,0 ≤ k ≤ 10 9

/*
类似分层图最短路
堆优化dij，dis[i][j]表示到i这个点用了j次通道的最短距离
*/
#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 501

#define M 2001

using namespace std;

int n,m,g,k;

int front[N],to[M<<],nxt[M<<],val[M<<],tot;

bool fly[M<<];

int DIS[N][];

struct node

{

    int tim,dis,num;

    bool operator < (node p) const{

        return dis>p.dis;

    }

}cur,nt;

priority_queue<node>q;

void read(int &x)

{

    x=;

    char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)){x=x*+c-'';c=getchar();}

}

void add(int u,int v,int w,bool fl)

{

    to[++tot]=v;

    nxt[tot]=front[u];

    front[u]=tot;

    val[tot]=w;

    fly[tot]=fl;

}

inline void init()

{

    read(n);read(m);read(g);read(k);

    int u,v,w;k=min(g,k);

    while(m--)

    {

        read(u);read(v);read(w);add(u,v,w,);

    }

    while(g--)

    {

        read(u);read(v);read(w);add(u,v,w,);

    }

}

void dijkstra()

{

    memset(DIS,,sizeof(DIS));

    cur.dis=;cur.num=;cur.tim=;

    DIS[][]=;q.push(cur);

    while(!q.empty())

    {

        cur=q.top();q.pop();

        if(cur.num==n)

        {

            printf("%d",cur.dis);return;

        }

        if(DIS[cur.num][cur.tim]!=cur.dis) continue;

        for(int i=front[cur.num]; i; i=nxt[i])

        {

            if(DIS[to[i]][cur.tim+fly[i]]<cur.dis+val[i]) continue;

            if(cur.tim+fly[i]>k) continue;

            DIS[to[i]][cur.tim+fly[i]]=cur.dis+val[i];

            nt.dis=cur.dis+val[i];nt.tim=cur.tim+fly[i];nt.num=to[i];

            q.push(nt);

        }

    }

    printf("-1");

}

int main()

{

    freopen("move.in","r",stdin);

    freopen("move.out","w",stdout);

    init();dijkstra();

    return ;

}

/*

51nod 算法马拉松3 Tree

树形dp f[i][j]表示以i为根，根所在联通快为j的方案数

转移的时候把i的子树一颗一颗加到i中，n^3

枚举时常数优化，降至n^2

*/

#include<cstdio>

#include<cstdlib>

#define N 5555

#define M 786433

using namespace std;

typedef long long LL;

struct edge

{

    int t,n;

}e[N*];

LL h[N],size[N],f[N][N],g[N],cnt[N];

int n,K,tote;

void add(int u,int v)

{

    e[++tote].t=v;

    e[tote].n=h[u];

    h[u]=tote;

    return ;

}

void dfs(int u,int fa)

{

    size[u]++; f[u][]=;

    for (int i=h[u];i;i=e[i].n)

    {

        int v=e[i].t;

        if (v==fa) continue;

        dfs(v,u);

        for (int j=;j<=size[u]+size[v];j++) g[j]=;

        for (int j=;j<=size[u];j++) g[j]=cnt[v]*f[u][j]%M;

        for (int j=;j<=size[u];j++)

          for (int k=;k<=size[v];k++)

            g[j+k]=(g[j+k]+f[u][j]*f[v][k]%M)%M;

        for (int j=;j<=size[u]+size[v];j++) f[u][j]=g[j];

        size[u]+=size[v];

    }

    for (int i=K;i<=size[u];i++) cnt[u]=(cnt[u]+f[u][i])%M;

    return ;

}

int main()

{

    freopen("cut.in","r",stdin);

    freopen("cut.out","w",stdout);

    scanf("%d %d",&n,&K);

    for (int i=;i<n;i++)

    {

        int u,v;

        scanf("%d%d",&u,&v);

        add(u,v);add(v,u);

    }

    dfs(,);

    printf("%d\n",cnt[]);

    fclose(stdin);

    fclose(stdout);

    return ;

}

巴特西

10.23NOIP模拟题

最新文章

热门文章