成都外国语学校信息学集训课阶段测试

操你蛋蛋

Problem A 玩具

该题目为Codeforces 520B

小明有一个玩具,玩具初始显示一个数$n$,还有两个按钮,按一次按钮一会使数字乘以$2$,按一次按钮二会使数字减$1$,现在小明想把$n$变成$m$,他想知道最少需要按几次按钮。

代码

#include <iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    long long n,m,ans=0;
    cin>>n>>m;
    while(m>n)
    {
        if(m&1){
            m++;
            ans++;
        }
        while(m>n&&!(m&1)){
            m>>=1;
            ans++;
        }
    }
    ans+=n-m;
    cout<<ans<<endl;
    return 0;
}

Problem B

题面

小明的班级一共有$k$个同学,毕业后,他们各奔东西,分别住在$n$个城市里,$n$个城市之间存在$m$条单向的道路。小明想组织一次同学会,那么选定一个大家都能到达的城市作为聚会地点就很有必要,请你帮助小明计算出有多少个城市能作为聚会的地点。

输入格式

第一行一个正整数$T$,表示有$T$组测试数据,每组数据第一行$3$个正整数,$k,n,m$,第二行$k$个正整数$x_i$表示第$i$个人住在$x_i$号城市,接下来$m$行,每行两个正整数$a,b$,城市$a$到$b$有一条路。

输出格式

对于每组测试数据输出一个答案,表示能作为聚会地点的城市数量。

输入输出样例

样例 1
输入
1
2 4 4
2 3
1 2
1 4
2 3
3 4
输出
2

样例解释

$3,4$号城市都能作为聚会地点。

数据范围

  • 对于$30\%$的数据,$1 \leq k,n \leq 10,1 \leq m \leq 20$
  • 对于$60\%$的数据,$1 \leq k \leq 50,1 \leq n \leq 500,1 \leq m \leq 500$
  • 对于$100\%$的数据,$1 \leq k \leq 100,1 \leq n \leq 1000,1 \leq m \leq 10000,1 \leq T \leq 10$

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=10005;
const int MAXM=100005;
struct point{
    int v;
    int next;
}e[MAXM<<1]; 
int head[MAXN],city[MAXN],tcount[MAXN];
int tot=0;
bool vis[MAXN];
inline void addedge(int u,int v){
    tot++;
    e[tot].v=v;
    e[tot].next=head[u];
    head[u]=tot;
} 
void dfs(int now){
    tcount[now]++;
    vis[now]=true;
    for(int i=head[now];i;i=e[i].next){
        if(!vis[e[i].v]){
            dfs(e[i].v);
        }
    }
}
int main(){
    int t;
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        int ans=0,m,n,k;
        memset(head,0,sizeof(head));
        memset(tcount,0,sizeof(tcount));
        cin>>k>>n>>m;
        for(int i=1;i<=k;i++){
            cin>>city[i]; 
        }
        for(int i=1;i<=m;i++){
            int u,v;
            cin>>u>>v;
            addedge(u,v);
        }
        for(int i=1;i<=k;i++){
            memset(vis,false,sizeof(vis)) ;
            dfs(city[i]);
        }
        for(int i=1;i<=n;i++){
            if(tcount[i]==k)
                ans++; 
        }
        cout<<ans<<endl;
    }
    return 0;
}

Problem C 神奇的序列

祝老说:注意,这套美妙无比精妙绝伦的题并不保证题目难度不递增,请仔细斟酌小心思考后再尝试作答此题,因为它可能是最难的…

题目描述

Z特别喜欢数列。有一天M送给了Z一个有趣的排列$a$Z很高兴。可是有一天,L出现了,LZ很不爽,于是准备对Z喜欢的数列搞一些操作。具体地说,一次操作就是选定一个区间$[l,r]$,并将$a[l \dots r]$循环后移一格$k$次。换言之,循环后移一次即为$a[l] = a[r],a[l + 1] = a[l],a[l + 2] = a[l + 1] \dots $。Z认为一个排列是优美的,当且仅当这个排列的逆序对对数为奇数。请帮Z算一算,每次操作之后排列是否优美。

输入格式

  • 第一行一个整数$n$,表示排列的长度。
  • 接下来一行$n$个整数,第$i$个整数表示$a[i]$。接下来一行一个整数$q$,表示L执行了$q$次操作。
    接下来$q$行一行三个整数,表示L的操作,以$l,r,k$表示,$l,r,k$的意义如题面所述。

输出格式

  • 为了验证您使用在线算法求逆序对,第一行请输出$n$个整数。
  • 第$i$个表示截至$a[i]$的逆序对个数。接下来$q$行$q$个整数,$0$表示不优美,$1$表示优美。

提示

因为输入文件可能很大,推荐您使用如下方式进行读入:

inline 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;
}

使用方法:若您需要读入n,则写作n = read();即可。

输入输出样例

样例输入

4
4 3 2 1
2
1 2 1
1 3 2

样例输出

0 1 3 6
1
1

样例解释

  • 操作前,逆序对的个数为$3 + 2 + 1 = 6$
  • 第一次操作后,序列成为$3,4,2,1$,逆序对个数为$ 2 + 2 + 1 = 5$
  • 第二次操作后,序列成为$4,2,3,1$,逆序对个数为$3 + 1 + 1 = 5$

数据范围

  • 对于$10\%$的数据,$n \leq 10$,$q \leq 1000$
  • 对于$30\%$的数据,$n \leq 1000$,$q \leq 1000,k=1$
  • 对于另外$20\%$的数据,$n \leq 100000$,$q \leq 10$
  • 对于另外$20\%的数据,$n leq 100000$,$q leq 100000$
  • 对于$100\%$的数据,$1 \leq n \leq 1000000,1 \leq q \leq 1000000,1 \leq m \leq 10000,1 \leq T \leq 10^9$

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=10005;
const int MAXM=100005;
struct point{
    int v;
    int next;
}e[MAXM<<1]; 
int head[MAXN],city[MAXN],tcount[MAXN];
int tot=0;
bool vis[MAXN];
inline void addedge(int u,int v){
    tot++;
    e[tot].v=v;
    e[tot].next=head[u];
    head[u]=tot;
} 
void dfs(int now){
    tcount[now]++;
    vis[now]=true;
    for(int i=head[now];i;i=e[i].next){
        if(!vis[e[i].v]){
            dfs(e[i].v);
        }
    }
}
int main(){
    int t;
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        int ans=0,m,n,k;
        memset(head,0,sizeof(head));
        memset(tcount,0,sizeof(tcount));
        cin>>k>>n>>m;
        for(int i=1;i<=k;i++){
            cin>>city[i]; 
        }
        for(int i=1;i<=m;i++){
            int u,v;
            cin>>u>>v;
            addedge(u,v);
        }
        for(int i=1;i<=k;i++){
            memset(vis,false,sizeof(vis)) ;
            dfs(city[i]);
        }
        for(int i=1;i<=n;i++){
            if(tcount[i]==k)
                ans++; 
        }
        cout<<ans<<endl;
    }
    return 0;
}
Last modification:July 11th, 2019 at 07:38 pm
如果您觉得我的文章有用,请赏一颗糖糖。

Leave a Comment