操你蛋蛋
Problem A 玩具
该题目为Codeforces 520B
小明有一个玩具,玩具初始显示一个数$n$,还有两个按钮,按一次按钮一会使数字乘以$2$,按一次按钮二会使数字减$1$,现在小明想把$n$变成$m$,他想知道最少需要按几次按钮。
代码
#include
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<
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
#include
#include
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<
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
#include
#include
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<
此处评论已关闭