题目

 

 

A：

 

题意：

给定一些字符串表示去年和今年的衣服型号大小( XL XXL M...... )，要求用最少的次数把去年的衣服大小改成今年需要的。每次改动只能更改字符，不能增添字符。

 

分析：

把今年和去年的型号字典序排一下。然后用挨个对上（因为题目保证合法，所以长度一样的数量必定相等）。在字符串长度是1的时候要暴力匹配一下，因为长度为1时有L S M三种东西。

 

代码：

#include 
       
        using namespace std;const int maxn=1200;string a[maxn], b[maxn], q1[maxn], q2[maxn];int vis[maxn];int main(){    int n; scanf("%d",&n);    for(int i=1;i<=n;i++) cin>>a[i];    for(int i=1;i<=n;i++) cin>>b[i];    sort(a+1,a+1+n);sort(b+1,b+1+n);    int ans=0;    for(int i=1;i<=n;i++){        if(a[i].length()==1) continue;        for(int j=0;j
       

 

 

---

 

 

 

 

 

 

 

B：

 

题意：

给定一个$ 10^18 $ 次方的数轴，在数轴上有一些点表示时间。其中有端点0和M。随着时间的推移，每到一个时间点就改变等的状态。

你可以新插入一个点（或者不插），求插入后总的灯亮的时间。

 

分析：

显然我插的点肯定是在给的点左一个或右一个·。然后前缀和优化模拟一下。

 

代码：

#include 
       
        using namespace std;typedef long long ll;const int maxn=1000005;ll A1[maxn],A2[maxn];ll M[maxn],maxans;ll sum=0;int main(){    int n;ll m;scanf("%d%I64d",&n,&m);    memset(A1,0,sizeof(A1));memset(A2,0,sizeof(A2));memset(M,0,sizeof(M));    M[1]=0;M[n+2]=m;    for(int i=2;i<=n+1;i++){        scanf("%I64d",&M[i]);    }    M[n+3]=M[n+2];    for(int i=1;i<=n+2;i+=2){        A1[i-1]=A1[i-2];        A1[i]+=A1[i-2]+M[i+1]-M[i];    }A1[n+2]=A1[n+1];    for(int i=2;i<=n+2;i+=2){        A2[i-1]=A2[i-2];        A2[i]+=A2[i-2]+M[i+1]-M[i];    }    A2[n+2]=A2[n+1];    for(int i=1;i<=n+2;i++){        ll ma1,ma2;        if(i%2==1 && M[i]!=M[i-1]+1){            ma1=A1[i-1]-1+(A2[n+2]-A2[i-1]);            ma2=A1[i]-1+(A2[n+2]-A2[i-1]);        }        else if(M[i]!=M[i+1]-1){            ma1=A1[i-1]-1+(A2[n+2]-A2[i-1]);            ma2=A1[i]-1+(A2[n+2]-A2[i-1]);        }        if(i!=1) maxans=max(maxans,max(ma1,ma2));        else maxans=ma2;    }    printf("%I64d\n",max(A1[n+2],maxans));    return 0;}
       

 

 

---

 

 

 

 

 

 

 

C：

 

题意：

线段覆盖数轴相关

 

分析：

大力算一下，如果是左端点就ans++，否则ans--

 

代码：

#include 
       
        using namespace std;typedef long long ll;const int maxn=2000000;ll sum[maxn];struct Node{    ll a;int type;    bool operator < (const Node& b) const{
     return a
       

 

 

---

 

 

 

 

 

 

D：

 

题意：

如果一个数组$ a_1.......a_k $ 且 $ a_1 = k-1$，辣么这个数组就是好数组。

一个好序列由好序列和（或）好数组组成。

给出一序列，求他有多少子序列是好序列。

 

分析：

很显然想到组合数计数一下，但不好处理子序列这个问题。

用$ dp[i] $表示以i开头的好序列的数量

然后对于每个$ a[i] $更新$ dp $

 

代码：

#include 
       
        using namespace std;typedef long long ll;const int maxn=2000l;const ll MOD=998244353;ll C[maxn][maxn], a[maxn], dp[maxn];int main(){    int n;scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%I64d",&a[i]);        for(int i=1;i<=n+5;i++)    for(int j=1;j<=n+5;j++){        if(j==1) C[i][j]=i;        else C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;    }        dp[n+1]=1;    for(int i=n-1;i>=1;i--){        if(a[i]<=0 || a[i]+i>n) continue;        for(int j=i+a[i]+1;j<=n+1;j++){            dp[i]=(dp[i]+C[j-i-1][a[i]]*dp[j])%MOD;        }    }        ll ans=0;    for(int i=1;i<=n;i++){        ans=(ans+dp[i])%MOD;     }    printf("%I64d\n",ans);    return 0;}
       

 

 

---

 

 

 

 

 

 

E：

 

题意：

求一张图桥最多的路径上桥的数量

 

分析：

缩点后求树的直径

 

代码：

#include 
       
        using namespace std;const int maxn=2000005;struct Edge{ int u,v; };vector
        
          edges; vector
         
           G[maxn], g[maxn];int n, m ;void Addedge(int a,int b){    edges.push_back((Edge){a,b}); edges.push_back((Edge){b,a});    int m=edges.size(); G[a].push_back(m-2);G[b].push_back(m-1);}int dfs_clock, low[maxn], pre[maxn], q[maxn], fron, scc_cnt, scc[maxn];int dfs(int u,int fa){    int lowu=pre[u]=++dfs_clock;    q[++fron]=u;    for(int i=0;i
          
           =pre[u]){ ok[G[u][i]]=1; ok[G[u][i]^1]=1;}        }        else{            if(pre[v]
           

que;int dis[maxn], inq[maxn];void dist(int x,int f){ dis[x]=dis[f]+1; for(int i=0;i

mx) mx=dis[i],mp=i; } memset(dis,0,sizeof(dis)); dist(mp,0); mx=0; for(int i=1;i<=scc_cnt;i++) mx=max(mx,dis[i]); printf("%d\n",mx-1); return 0;}