10.23模拟赛

  

叉叉

题目描述

现在有一个字符串，每个字母出现的次数均为偶数。接下来我们把第一次出现的字母a和第二次出现的a连一条线，第三次出现的和四次出现的字母a连一条线，第五次出现的和六次出现的字母a连一条线...对其他25个字母也做同样的操作。

现在我们想知道有多少对连线交叉。交叉的定义为一个连线的端点在另外一个连线的内部，另外一个端点在外部。

下图是一个例子，共有三对连线交叉（我们连线的时候，只能从字符串上方经过）。

输入格式

一行一个字符串。保证字符串均由小写字母组成，且每个字母出现次数为偶数次。

输出格式

一个整数，表示答案。

样例输入

abaazooabz

样例输出

3

数据范围

对于30% 的数据，字符串长度不超过50。

对于100% 的数据，字符串长度不超过100,000。

 法一：（n/2*n/2）/2  （不到）的做法。

我们现将字母两两配对，然后用结构体记录一下这两个相同的字母的位置，当然这两个字母一定是挨着的且为奇偶交叉的。我们记录一下这个区间的信息，l为奇数位字母的位置，r为偶数位字母的位置，然后我们讲这样的每个区间按l排序。然后枚举每一个区间，判断那条线段在这个区间里，在这个区间的条件为a.l<now.r&&a.r>now.l，now为我们当前枚举到的区间，a为我们枚举的这个区间内的线段

#include
      
       #include
       
        #include
        
         #include
         
          #define N 100010using namespace std;char ch[N];int ans,sum;struct Node{    int l,r;}node[N];int cmp(Node a,Node b){
    return a.l
          
           >ch+1;sum=1;    int l=strlen(ch+1),r,n=0;    for(int a=1;a<=26;a++)      for(int i=1;i<=l;i++)        if(a==ch[i]-'a'+1)        {            if(node[sum].r) node[++sum].l=i;            else             if(!node[sum].l) node[sum].l=i;             else node[sum].r=i;        }    sort(node+1,node+1+sum,cmp);    for(int i=1;i<=sum;i++)     for(int j=i+1;j<=sum;j++)     {         if(node[i].r
          
         
        
       
      

 

法二：26*26*sum[i]的做法

对于读入的字符串我们用一个数组d[i][sum[i]]记录一下当前字母的位置，sum[i]记录当前字母的个数，s[j][i]记录到当前位置每个字母的个数。然后我们第一个for循环枚举26个字母，第二个for循环枚举当前字母的个数，第三个for循环枚举在两个相邻的字母之间的字母。

然后我们判断在我们第一个枚举的字母a两个相邻之间的这段区间所含的一个字母的个数是否为奇数，如果是奇数的话，这两条线断一定是相交的，但是如果是偶数的话，我们还要判断一下第一个字母与最后一个字母（这两个字母是相同的）是否是成对的，如果是的话就不管他，如果不是就说明这两个字母组成的两条线断都与当前区间相交，ans+=2，最后输出答案、

 

#include
      
       #include
       
        #include
        
         #include
         
          #define N 100010using namespace std;char ch[N];int ans,sum[30],d[30][N],s[30][N];int main(){    freopen("cross.in","r",stdin);    freopen("cross.out","w",stdout);    cin>>ch+1;    int l=strlen(ch+1),r,n=0;    for(int i=1,a;i<=l;i++)    {        a=ch[i]-'a'+1;        if(a>n) n=a;        d[a][++sum[a]]=i;        for(int j=1;j<=26;j++)         if(a==j) s[j][i]=s[j][i-1]+1;         else s[j][i]=s[j][i-1];    }    for(int a=1;a<=n;a++)     for(int i=1;i
         
        
       
      

 

 

 

 

 

 

　　　　　　　　　　　　　　　　跳跳虎回家

英⽂名称: 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

 

这道题的暴力分给的特别足，我们先来看30%的数据，k是等于零的，也就是说这30分是一个求最短路的模板，我们直接跑一遍spfa就好了。然后再来看60%的数据，k=1，也就是说只修改一条边来使这个路径最短，对于这种问题我们一般都有一个套路即为建反向边，然后正着倒着各跑一遍spfa，然后我们枚举一下修改那一条边，ans=dis1[x]+dis2[y]+s[x][y]，取一个min就好了。然后我们再来看100%的数据，k是小于等于10^9的，并且n小于等于500，也就是说一定有一部分数据是k大于n的，对于这种情况我们直接将所有的边都建出，然后跑一遍spfa就好了。本以为这样最多能拿到90分，可是这样分类讨论竟然可以A掉这道题，至于为什么，问出题人去吧、

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 510#define maxn 99999999using namespace std;queue
           
            q;bool vis[N];int n,m,p,k,x,y,z,ans,tot1,tot2;int dis1[N],dis2[N],head1[N*4],head2[N*4];int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='0')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f;}struct Edge{ int to,dis,next;}edge1[N*4],edge2[N*4];struct Node { int x,y,z;}node[N*4];int add1(int x,int y,int z){ tot1++; edge1[tot1].to=y; edge1[tot1].dis=z; edge1[tot1].next=head1[x]; head1[x]=tot1;}int add2(int x,int y,int z){ tot2++; edge2[tot2].to=y; edge2[tot2].dis=z; edge2[tot2].next=head2[x]; head2[x]=tot2;}int spfa1(){ for(int i=1;i<=n;i++) dis1[i]=maxn,vis[i]=0; dis1[1]=0,vis[1]=true,q.push(1); while(!q.empty()) { x=q.front(),q.pop(),vis[x]=false; for(int i=head1[x];i;i=edge1[i].next) { int t=edge1[i].to; if(dis1[t]
            
             =maxn) ans=-1; else ans=dis1[n]; printf("%d",ans);}void work2(){ spfa1(),spfa2();ans=dis1[n]; for(int i=1;i<=p;i++) { x=node[i].x,y=node[i].y,z=node[i].z; if(ans>dis1[x]+dis2[y]+z) ans=dis1[x]+dis2[y]+z; } if(ans>=maxn) ans=-1; printf("%d",ans);}void work3(){ for(int i=1;i<=p;i++) { x=node[i].x,y=node[i].y,z=node[i].z; add1(x,y,z); } spfa1();ans=dis1[n]; if(ans>=maxn) ans=-1; printf("%d",ans);}int main(){ freopen("move.in","r",stdin); freopen("move.out","w",stdout); n=read(),m=read(),p=read(),k=read(); memset(dis1,0x3f3f3f3f,sizeof(dis1)); for(int i=1;i<=m;i++) { x=read(),y=read(),z=read(); add1(x,y,z),add2(y,x,z); } for(int i=1;i<=p;i++) { node[i].x=read(); node[i].y=read(); node[i].z=read(); } if(k==0) work1(); else if(k==1) work2(); else work3(); return 0;}
            
           
          
         
        
       
      

 

 

　　　　　　　　　　　　　　秀秀 和哺 噜国 （ cut ）

时间限制：1s

空间限制：512MB

【问题描述】

哺噜国里有!个城市，有的城市之间有高速公路相连。在最开始时，哺噜国里有! − 1条高

速公路，且任意两座城市之间都存在一条由高速公路组成的通路。

由于高速公路的维护成本很高， 为了减少哺噜国的财政支出， 将更多的钱用来哺育小哺噜，

秀秀女王决定关闭一些高速公路。 但是为了保证哺噜国居民的正常生活， 不能关闭太多的高速

公路，要保证每个城市可以通过高速公路与至少$个城市（包括自己）相连。

在得到了秀秀女王的指令后，交通部长华华决定先进行预调研。华华想知道在满足每个城

市都可以与至少$个城市相连的前提下，有多少种关闭高速公路的方案（可以一条也不关） 。两

种方案不同， 当且仅当存在一条高速公路在一个方案中被关闭， 而在另外一个方案中没有被关

闭。

由于方案数可能很大， 你只需输出不同方案数对786433取模后的结果即可。 其中786433 =

6×2 -. + 1。

【输入格式】

从文件 cut.in 中读入数据。

输入第一行，包含两个正整数!,$。

接下来的! − 1行，每行包含两个正整数1和2，表示城市1和城市2之间有一条高速公路相

连。

【输出格式】

输出文件到 cut.out 中。

输出一个非负整数，表示所求方案数对 786433 取模后的结果。

【样例 1 输入】

5 2

1 2

2 3

3 4

4 5

【样例 1 输出】

3

【样例 1 解释】

三种方案分别为：

一条高速公路也不关闭；

关闭城市 2 和城市 3 之间的高速公路；

关闭城市 3 和城市 4 之间的高速公路。

【样例 2 输入】

10 2

1 2

1 3

2 4

2 5

3 6

3 7

3 10

5 8

6 9

【样例 2 输出】

12

【子任务】

对于20%的数据：! ≤ 20;

另有30%的数据：! ≤ 100;

另有10%的数据：$ ≤ 100;

另有20%的数据：! ≤ 1000;

对于100%的数据：! ≤ 5000,$ ≤ !。

 

树形背包

我们用dp[i][j]表示以i为根的块的大小为j的方案数，g[j]表示大小为j的方案数，cnt[x]表示以x为根的块并且大小大于m的方案数。

我们这个地方有两种情况，我们当前有两棵树，我们可以将它们合并起来，也可以不把他们合并起来，当以i为根的块的大小已经比m大了，那么我们可以选择不合并，那么他的方案数为g[j]=1ll*cnt[t]*dp[x][j]，（我们以t为根c的节点数大于等于k方案数*以i为根的块的方案数），因为这个时候t这棵子树与以i为根的这棵树是两个独立的块，这两个块是相互独立互不影响的，这样总的方案数就是这两块的方案数的乘积。或者是我们要将这两棵子树合并起来，我们设j为第一个子树（以x为跟）的大小，k为第二棵子树（以t为根）的大小，

那么g[k+j]+=dp[x][j]*dp[t][k]。最终答案为所有的满足条件的以1为根节点的块的大小大于j的方案数的和

#include
      
       #include
       
        #include
        
         #include
         
          #define N  5010*2#define mod 786433using namespace std;int n,m,x,y,tot,g[N],cnt[N],size[N],dp[N][N],head[N];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    return x*f;}struct Edge{    int to,next;}edge[N*4];int add(int x,int y){    tot++;    edge[tot].to=y;    edge[tot].next=head[x];    head[x]=tot;}int dfs(int x,int fa){    size[x]=1,dp[x][1]=1;    for(int i=head[x];i;i=edge[i].next)     if(edge[i].to!=fa)     {         int t=edge[i].to;         dfs(t,x);         for(int j=1;j<=size[x]+size[t];j++) g[j]=0;         for(int j=1;j<=size[x];j++) g[j]=1ll*cnt[t]*dp[x][j]%mod;         for(int j=1;j<=size[x];j++)          for(int k=1;k<=size[t];k++)           g[j+k]=(g[j+k]+1ll*dp[x][j]*dp[t][k]%mod)%mod;         for(int j=1;j<=size[x]+size[t];j++) dp[x][j]=g[j];         size[x]+=size[t];     }    for(int i=m;i<=size[x];i++) cnt[x]+=dp[x][i],cnt[x]%=mod;}int main(){    freopen("cut.in","r",stdin);    freopen("cut.out","w",stdout);    n=read(),m=read();    for(int i=1;i
         
        
       
      

 

 

 

 　　　　　　　　　　　　　　

 

 

 

　　　　　　　　　　　　　　　　　　　　　　距 NOIp2017 还剩 18 天

 

 　　                             你可以做的事情还有很多，即使到最后一秒也不要放弃，因为不到结束的那一刻谁也不知道结果会怎样