操你蛋蛋
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出现了，L看Z很不爽，于是准备对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;
}版权声明：本文是原创文章，版权归 星雾月雨 所有。
本文链接：https://www.ariels.xyz/archives/363.html
本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。
