9.18模拟赛

完美的序列(sequence)

题目描述

LYK认为一个完美的序列要满足这样的条件：对于任意两个位置上的数都不相同。然而并不是所有的序列都满足这样的条件。

于是LYK想将序列上的每一个元素都增加一些数字(当然也可以选择不增加)，使得整个序列变成美妙的序列。

具体地，LYK可以花费

输入输出格式

输入格式：

第一行一个数

接下来一行 $nn个数a_iai表示LYK得到的序列。$

输出格式：

一个数表示变成完美的序列的最小代价。

输入输出样例

输入样例#1：

4
1 1 3 2

输出样例#1：

说明

对于 $30\%30%的数据n leq 5n≤5。$

对于 $60\%60%的数据n leq 1000n≤1000。$

对于 $80\%80%的数据n leq 30000n≤30000，a_i leq 3000ai≤3000。$

对于 $100\%100%的数据n leq 100000n≤100000，1leq a_i leq 1000001≤ai≤100000。$

题解：

80分贪心..每次加到最小的没有出现的....

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int n,ans,a[100005],apper[100005];

int main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        if(apper[a[i]]==0){
            apper[a[i]]=1;
            continue;
        }   
        while(apper[a[i]]){
            ans++;a[i]++;
        }
        apper[a[i]]=1;
    }
    printf("%d
",ans);
    fclose(stdin);fclose(stdout);
    return 0;
}

正解：贪心...从小到大排序..最后的序列一定是一个递增的...每次加到刚刚好就可以

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 100006
using namespace std;
int n,a[maxn];
long long ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=2;i<=n;i++){
        if(a[i]<=a[i-1]){
            ans+=(a[i-1]-a[i]+1);
            a[i]=a[i-1]+1;
        }
    }
    cout<<ans<<endl;
    return 0;
}

LYK与实验室(lab)

题目描述

LYK在一幢大楼里，这幢大楼共有

这幢大楼有一个秘密实验室，在第

两个旅行方案不同当前仅当存在某一次按下电梯后停留的楼层不同。

输入输出格式

输入格式：

一行4个数，

输出格式：

一个数表示答案，由于答案较大，将答案对

输入输出样例

输入样例#1：

5 2 4 1

输出样例#1：

输入样例#2：

5 2 4 2

输出样例#2：

输入样例#3：

5 3 4 1

输出样例#3：

说明

对于 $20\%20%的数据n,kleq 5n,k≤5。$

对于 $40\%40%的数据n,kleq 10n,k≤10。$

对于 $60\%60%的数据n,kleq 500n,k≤500。$

对于 $90\%90%的数据n,k leq 2000n,k≤2000。$

对于 $100\%100%的数据n,k leq 5000n,k≤5000。$

题解：

40分暴力搜索

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define mod 1000000007LL
using namespace std;

long long ans;
int n,a,b,g;

void dfs(int now,int k){
    if(now==b)return;
    if(k==g){
        ans++;
        ans=ans%mod;
        return;
    }
    for(int i=now-1;i>=1;i--){
        if(abs(now-i)<abs(now-b))
        dfs(i,k+1);
        else break;
    }
    for(int i=now+1;i<=n;i++){
        if(abs(now-i)<abs(now-b))
        dfs(i,k+1);
    }
}

int main(){
    freopen("lab.in","r",stdin);
    freopen("lab.out","w",stdout);
    scanf("%d%d%d%d",&n,&a,&b,&g);
    //n层电梯 开始在a层 实验室在b层 按g次电梯。
    dfs(a,0); 
    cout<<ans<<endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

60分O(n^3)dp

f[i][j]表示摁k次到达j的情况总数....

转移方程：f[i][j]+f[i-1][l]....l是能到达j的

#include<iostream>
#include<cstdio>
#include<cstring>
#define mod 1000000007LL
using namespace std;
int n,a,b,k;
long long ans;
int f[2001][2001];
int zs(int x){
    if(x<0)return -x;
    return x;
}
int main(){
    scanf("%d%d%d%d",&n,&a,&b,&k);
    f[0][a]=1;
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++){
            if(j==b)continue;
            for(int l=1;l<=n;l++){
                if(l==b||l==j)continue;
                if(zs(l-j)<zs(l-b)){
                    f[i][j]=f[i][j]+f[i-1][l];
                    f[i][j]%=mod;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)ans=(ans%mod+f[k][i]%mod)%mod;
    cout<<ans<<endl;
    return 0;
}

100分前缀和优化+压维

#include<cstdio>
#include<iostream>
#include<cstdlib>
#define N 5010
#define mod 1000000007
using namespace std;
int n,a,b,m,dp[2][N],s[2][N];
int main() {
    scanf("%d%d%d%d",&n,&a,&b,&m);
    dp[0][a]=1;
    for(int i=a;i<=n;i++)s[0][i]=1;
    for(int i=1;i<=m;i++)
      for(int j=1;j<=n;j++) {
          int limit;
          if(j>b)limit=j-(j-b-1)/2,
          dp[i%2][j]=((s[(i+1)%2][n]-s[(i+1)%2][j-(j-b-1)/2-1]-dp[(i+1)%2][j])%mod+mod)%mod;
          if(j<b)limit=j+(b-j-1)/2,
          dp[i%2][j]=((s[(i+1)%2][j+(b-j-1)/2]-dp[(i+1)%2][j])%mod+mod)%mod;
          s[i%2][j]=(s[i%2][j-1]+dp[i%2][j])%mod;
      }
    int ans=0;
    for(int i=1;i<=n;i++)
      ans+=dp[m%2][i],ans%=mod;
    printf("%d",ans);
    return 0;
}

旅行(travel)

题目描述

LYK想去一个国家旅行。这个国家共有

我们定义城市

我们定义整个国家的最短路为任意两个城市（

然而这个国家正处于危乱之中，极有可能一条道路会被恐怖分子炸毁。

LYK想知道，万一某条道路被炸毁了，整个国家的最短路为多少。若炸毁这条道路后整个国家不连通了，那么就输出“INF”(不加引号)。

输入输出格式

输入格式：

第一行两个数

接下来

输出格式：

输出

输入输出样例

输入样例#1：

2 2
1 2
1 2

输出样例#1：

2
2

说明

对于 $20\%20%的数据n leq 10,n leq mleq100n≤10,n≤m≤100。$

对于 $40\%40%的数据1leq n<m leq 1001≤n<m≤100。$

对于 $70\%70%的数据1leq n leq 100,n<m leq 30001≤n≤100,n<m≤3000。$

对于再另外 $10\%10%的数据对于所有节点i(1leq i < n)i(1≤i<n)，存在一条边连接 ii 与i+1i+1，且n=mn=m，n leq 100n≤100。$

对于再另外 $10\%10%的数据对于所有节点i(1leq i < n)i(1≤i<n)，存在一条边连接 ii 与i+1i+1，且n=mn=m，n leq 1000n≤1000。$

对于再另外 $10\%10%的数据对于所有节点i(1leq i < n)i(1≤i<n)，存在一条边连接 ii 与i+1i+1，且n=mn=m，n leq 100000n≤100000。$

$mn^3.....$

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n,m,ans;
int f[333][333],d[333][333];

struct WW {
    int x,y;
} e[3002];
void cut(int ii) {
    int x=e[ii].x,y=e[ii].y;
    f[x][y]--;
    f[y][x]--;
}
void huifu(int ii) {
    int x=e[ii].x,y=e[ii].y;
    f[x][y]++;
    f[y][x]++;
}

/*void debug(){
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            cout<<i<<" "<<j<<" "<<d[i][j]<<endl;
        }
    }
}*/

void floyed() {
    int flag=0;
    memset(d,0x3f,sizeof(d));
    for(int i=1; i<=n; i++) {
        d[i][i]=0;
        for(int j=i+1; j<=n; j++) {
            if(f[i][j])d[i][j]=d[j][i]=1;
        }
    }
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
//    debug();
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++)
            if(d[i][j]==0x3f3f3f3f) {
                flag=1;
                break;
            } else ans+=d[i][j];
        if(flag) {
            printf("INF
");
            break;
        }
    }
    if(flag==0) {
        printf("%d
",ans);
    }
}
int main() {
    freopen("travel.in","r",stdin);
    freopen("travel.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++) {
        scanf("%d%d",&e[i].x,&e[i].y);
        int x=e[i].x,y=e[i].y;
        f[x][y]++;
        f[y][x]++;
    }
    for(int i=1; i<=m; i++) {
        ans=0;
        cut(i);
        floyed();
        huifu(i);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

正解：先bfs计算出每个点到某个点的最短路径,然后枚举删边..如果删的这条边在

最短路上那么就重新求这个最短路...正解容斥原理..弃疗...

code 50分

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define LL long long
#define inf 100000000
#define maxn 3005
using namespace std;
queue<int>q;
int n,m,sumedge;
LL ans;
int head[maxn],dis[maxn],inq[maxn],pre[maxn][maxn],sum[maxn];

struct Edge{
    int x,y,nxt;
    Edge(int x=0,int y=0,int nxt=0):
        x(x),y(y),nxt(nxt){}
}edge[maxn<<2];

void add(int x,int y){
    edge[++sumedge]=Edge(x,y,head[x]);
    head[x]=sumedge;
}

void bfs(int st){
    while(!q.empty())q.pop();
    memset(dis,0,sizeof(dis));
    memset(inq,0,sizeof(inq));
    inq[st]=1;q.push(st); 
    while(!q.empty()){
        int now=q.front();q.pop();
        for(int i=head[now];i;i=edge[i].nxt){
            int v=edge[i].y;
            if(inq[v]==0){
                inq[v]=1;
                pre[st][v]=now;
                dis[v]=dis[now]+1;
                q.push(v); 
            }
        }
    }
    for(int i=1;i<=n;i++)sum[st]+=dis[i];
}

void spfa(int st,int cutedge){
    memset(inq,0,sizeof(inq));
    for(int i=1;i<=n;i++)dis[i]=inf;
    dis[st]=0;inq[st]=1;
    while(!q.empty())q.pop();
    q.push(st);
    while(!q.empty()){
        int now=q.front();q.pop();
        for(int i=head[now];i;i=edge[i].nxt){
            if(i==cutedge||i==cutedge+1)continue;
            int v=edge[i].y;
            if(inq[v]==0){
               dis[v]=dis[now]+1;
               inq[v]=1;
               q.push(v); 
            }
        }
    } 
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    for(int i=1;i<=n;i++)bfs(i);
    for(int i=1;i<=m*2;i+=2){
        int u=edge[i].x,v=edge[i].y;
        LL ans=0;
        for(int j=1;j<=n;j++){
            if(pre[j][u]==v||pre[j][v]==u){
                spfa(j,i);
                for(int k=1;k<=n;k++)ans+=dis[k];
            }else ans+=sum[j];
        }
        if(ans<inf){
            cout<<ans<<endl;
        }else printf("INF
");
    }
    return 0;
}