2017 清北国庆刷题 day7afternoon
A 同花顺
文件名 输入文件 输出文件 时间限制 空间限制
card.cpp/c/pas card.in card.out 1s 512MB
题目描述
所谓同花顺，就是指一些扑克牌，它们花色相同，并且数字连续。
现在我手里有 n 张扑克牌，但它们可能并不能凑成同花顺。我现在想知道，最
少更换其中的多少张牌，我能让这 n 张牌凑成一个同花顺？
输入格式
第一行一个整数 n，表示扑克牌的张数。
接下来 n 行，每行两个整数 a i 和 b i 。其中 a i 表示第 i 张牌的花色，b i 表示第
i 张牌的数字。
（注意： 这里的牌上的数字不像真实的扑克牌一样是 1 到 13， 具体见数据范围）
输出格式
一行一个整数，表示最少更换多少张牌可以达到目标。
样例输入 1
5
1 1
1 2
1 3
1 4
1 5
样例输出 1
0
2
样例输入 2
5
1 9
1 10
2 11
2 12
2 13
样例输出 2
2
数据范围
对于 30% 的数据，n ≤ 10。
对于 60% 的数据，n ≤ 10 5 ，1 ≤ a i ≤ 10 5 ，1 ≤ b i ≤ n。
对于 100% 的数据，n ≤ 10 5 ，1 ≤ a i ,b i ≤ 10 9 。
/*
数据量比较大，需要我们进行离散化，去除相同的牌。
一个显然的贪心就是找到花色出现次数最多的花色，则其他的花色的牌一定要换掉。
做到这里，应该能拿60.
100分做法：枚举在已有的同花顺序列上的最后一张牌，去寻找可能的第一张牌。
我们令last为当前牌作为同花顺序列的最后一张牌时，可能的第一张牌。如果当前牌的点数是a，last牌的点数是b，则必须要满足a-b+1≤n。
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define N 100007
using namespace std;
int n;
struct card
{
int color, value;
bool operator < (const card &x) const{
return color<x.color || (color==x.color && value<x.value);
}
bool operator == (const card &x) const{
return color==x.color && value==x.value;
}
} a[N];
inline int read()
{
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main()
{
freopen("card.in","r",stdin);
freopen("card.out","w",stdout);
n=read();
for(int i=1;i<=n;i++) a[i].color=read(),a[i].value=read();
sort(a+1,a+n+1);
int m=n;
n=unique(a+1,a+1+n)-(a+1);
int last=1;
int maxx=1;
for(int i=1;i<=n;i++)
{
if (i==1 || a[i].color!=a[i-1].color) last=i;
while (a[i].value-a[last].value+1>m) last++;
maxx=max(maxx,i-last+1);
}
printf("%d
",m-maxx);
return 0;
}
B 做实验
文件名 输入文件 输出文件 时间限制 空间限制
test.pas/c/cpp test.in test.out 1s 128MB
题目描述
有一天，你实验室的老板给你布置的这样一个实验。
首先他拿出了两个长度为 n 的数列 a 和 b，其中每个 a i 以二进制表示一个集
合。例如数字 5 = (101) 2 表示集合 {1,3}。第 i 次实验会准备一个小盒子，里面装
着集合 a i 所有非空子集的纸条。老板要求你从中摸出一张纸条，如果满足你摸出的
纸条是 a i 的子集而不是 a i−b i ，a i−b i +1 ，...，a i−1 任意一个的子集，那么你就要 ***；
反之，你就逃过一劫。
令你和老板都没有想到的是，你竟然每次都逃过一劫。在庆幸之余，为了知道
这件事发生的概率，你想要算出每次实验有多少纸条能使你 ***
输入格式
第一行一个数字 n。
接下来 n 行，每行两个整数，分别表示 a i 和 b i 。
输出格式
n 行，每行一个数字，表示第 i 次实验能使你 *** 的纸条数。
样例输入 1
3
7 0
15 1
3 1
样例输出 1
7
8
0
4
数据范围
对于 30% 的数据，n,a i ,b i ≤ 100
对于 70% 的数据，n,a i ,b i ≤ 60000
对于 100% 的数据，n,a i ,b i ≤ 10 5
保证所有的 a i 不重复，b i < i
/*
记录所有子集的最后出现位置
对于每个ai，枚举ai的子集，若最后出现位置<i-bi,ans++
枚举子集复杂度：
for(int s=1;s<(1<<n);s++)
for(int i=s;i;i=(i-1)&s)
这两个循环的复杂度为3^n
因为对于n个二进制位，要么属于s不属于i，要么属于s属于i，要么不属于i
*/
#include<cstdio>
#include<iostream>
#define N 100001
using namespace std;
void read(int &x)
{
x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}
int pos[N];
int main()
{
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
int n,a,b,ans;
read(n);
for(int i=1;i<=n;i++)
{
ans=0;
read(a); read(b);
for(int j=a;j;j=(j-1)&a)
{
if(pos[j]<i-b) ans++;
pos[j]=i;
}
printf("%d
",ans);
}
}
C 拯救世界
文件名 输入文件 输出文件 时间限制 空间限制
save.cpp/c/pas save.in save.out 1s 512MB
题目描述
C 城所有的道路都是单向的。不同道路之间有路口，每个路口都有一个大楼。
有一天， 城市里的所有大楼因为不明原因， 突然着火了。 作为超人的你要去拯救
这些大楼。初始的时候你在 S 号楼，最后你必须到达某个有补给站的大楼，你可以
沿着单向道路行驶。你可以经过某条道路或者某个大楼若干次，经过一个大楼你就
可以消灭一个大楼的大火。每个大楼都有一个重要程度，最后这个任务的评价分数
就是你经过的所有大楼的重要度之和（若重复经过某个大楼多次，则不重复算分） 。
你是一个聪明的超人，你想知道，通过合理的规划路线，你这次任务能得到的
最高得分是多少。
注意，该城市的道路可能有重边或自环。
输入格式
第一行包括两个整数 n，m，n 表示路口的个数（即大楼的个数） ，m 表示道路
的条数。
接下来 m 行，每行两个整数 x,y，表示 x 到 y 之间有一条单向道路。
接下来 n 行，每行一个整数，按顺序表示每个大楼的重要度。
接下来一行包含两个整数 S 和 P，S 是出发的路口（大楼）的编号，P 是有补
给站的大楼的数量。
接下来一行 P 个整数，表示有补给站的大楼的编号。
输出格式
输出一行一个整数，表示你得分的最大值。
样例输入 1
6 7
1 2
2 3
3 5
6
2 4
4 1
2 6
6 5
10
12
8
16
1
5
1 4
4 3 5 6
样例输出 1
47
数据范围
对于 1、2、3 测试点，N,M ≤ 300
对于 4、5、6、7、8、9、10 测试点，N,M ≤ 3000
对于 11、12、13、14、15 测试点，N,M ≤ 500000。每个大楼的重要度均为非
负数且不超过 4000。
输入数据保证你可以从起点沿着单向道路到达其中的至少一个有补给站的大
楼。
注意，输入数据中存在树和链的特殊情况
/*
一个强连通分量里的点都能到达，所以先缩点。
要求多个终点的最大值，所以要处理出到所有终点的最大距离
所以采取dp记录最长路。为了dp无后效性，把新建图拓扑排序。
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 500001
using namespace std;
int n,m,S,tot,cnt,tot2;
int val[N],front[N],to[N],nxt[N],from[N];
int dfn[N],low[N],st[N],top,id[N],sum[N];
int nxt2[N],front2[N],to2[N],q[N],in[N],dp[N];
bool ins[N];
inline int read()
{
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
void add(int u,int v)
{
if(u==v) return;
for(int i=front[u];i;i=nxt[i])
if(to[i]==v) continue;
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u;
}
void init()
{
n=read();m=read();
int u,v;
for(int i=1;i<=m;i++) { u=read(); v=read(); add(u,v); }
for(int i=1;i<=n;i++) val[i]=read();
S=read();
}
void tarjan(int x)
{
dfn[x]=low[x]=++tot;
st[++top]=x; ins[x]=true;
for(int i=front[x];i;i=nxt[i])
{
if(!dfn[to[i]])
tarjan(to[i]),low[x]=min(low[x],low[to[i]]);
else if(ins[to[i]])
low[x]=min(low[x],dfn[to[i]]);
}
if(low[x]==dfn[x])
{
id[x]=++cnt; sum[cnt]+=val[x];
while(top && st[top]!=x)
{
id[st[top]]=cnt;
sum[cnt]+=val[st[top]];
ins[st[top--]]=false;
}
ins[st[top--]]=false;
}
}
void add2(int u,int v)
{
to2[++tot2]=v; nxt2[tot2]=front2[u]; front2[u]=tot2; in[v]++;
}
void rebuild()
{
for(int i=1;i<=m;i++)
if(id[from[i]]!=id[to[i]]) add2(id[from[i]],id[to[i]]);
}
void pre()
{
memset(ins,false,sizeof(ins));
int h=0,t=1;
q[++h]=id[S]; ins[id[S]]=true;
int now;
while(h<=t)
{
now=q[h++];
for(int i=front2[now];i;i=nxt2[i])
if(!ins[to2[i]]) ins[to2[i]]=true,q[++t]=to2[i];
}
for(int i=1;i<=cnt;i++)
if(!ins[i])
for(int j=front2[i];j;j=nxt2[j]) in[to2[j]]--;
}
void topsort()
{
st[top=1]=id[S]; dp[id[S]]=sum[id[S]];
int now;
while(top)
{
now=st[top--];
for(int i=front2[now];i;i=nxt2[i])
{
dp[to2[i]]=max(dp[to2[i]],dp[now]+sum[to2[i]]);
in[to2[i]]--;
if(!in[to2[i]]) st[++top]=to2[i];
}
}
}
void answer()
{
int ans=0,k,x;
k=read();
for(int i=1;i<=k;i++)
{
x=read();
ans=max(ans,dp[id[x]]);
}
printf("%d
",ans);
}
int main()
{
freopen("save.in","r",stdin);
freopen("save.out","w",stdout);
init();
tot=0;
for(int i=1;i<=n;i++)
if(!dfn[i]) top=0,tarjan(i);
rebuild();pre();
topsort();answer();
return 0;
}