完美的序列(sequence)
Time Limit:1000ms Memory Limit:64MB
题目描述
LYK 认为一个完美的序列要满足这样的条件:对于任意两个位置上的数都不相同。然而
并不是所有的序列都满足这样的条件。
于是 LYK 想将序列上的每一个元素都增加一些数字(当然也可以选择不增加),使得整个
序列变成美妙的序列。
具体地, LYK 可以花费 1 点代价将第 i 个位置上的数增加 1,现在 LYK 想花费最小的代价
使得将这个序列变成完美的序列。
输入格式(sequence.in)
第一行一个数 n,表示数字个数。
接下来一行 n 个数 ai 表示 LYK 得到的序列。
输出格式(sequence.out)
一个数表示变成完美的序列的最小代价。
输入样例
4
1 1 3 2
输出样例
3
数据范围
对于 30%的数据 n<=5。
对于 60%的数据 n<=1000。
对于 80%的数据 n<=30000, ai<=3000。
对于 100%的数据 n<=100000, 1<=ai<=100000。
/*简单的贪心*/ #include<cstdio> #include<iostream> #include<algorithm> #include<cstdlib> #define N 100010 #define ll long long using namespace std; ll a[N],n; ll read() { ll num=0,flag=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();} while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();} return num*flag; } int main() { freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); n=read(); for(ll i=1;i<=n;i++) a[i]=read(); sort(a+1,a+n+1); ll tot=0; for(ll i=2;i<=n;i++) { if(a[i]<=a[i-1]) { tot+=a[i-1]+1-a[i]; a[i]=a[i-1]+1; } } cout<<tot; return 0; }
LYK 与实验室(lab)
Time Limit:5000ms Memory Limit:64MB
题目描述
LYK 在一幢大楼里,这幢大楼共有 n 层, LYK 初始时在第 a 层上。
这幢大楼有一个秘密实验室,在第 b 层,这个实验室非常特别,对 LYK 具有约束作用,
即若 LYK 当前处于 x 层,当它下一步想到达 y 层时,必须满足|x-y|<|x-b|,而且由于实验室
是不对外开放的,电梯无法停留在第 b 层。
LYK 想做一次旅行,即它想按 k 次电梯,它想知道不同的旅行方案个数有多少个。
两个旅行方案不同当前仅当存在某一次按下电梯后停留的楼层不同。
输入格式(lab.in)
一行 4 个数, n,a,b,k。
输出格式(lab.out)
一个数表示答案,由于答案较大,将答案对 1000000007 取模后输出。
输入样例 1
5 2 4 1
输出样例 1
2
输入样例 2
5 2 4 2
输出样例 2
2
输入样例 3
5 3 4 1
输出样例 3
0
数据范围
对于 20%的数据 n,k<=5。
对于 40%的数据 n,k<=10。
对于 60%的数据 n,k<=500。
对于 90%的数据 n,k<=2000。
对于 100%的数据 n,k<=5000。
/* O(mn^2)的dp方程是很好想的,我们可以在这基础上进行优化 因为每次更新的都是一段连续的序列,所以可以用前缀和优化,空间用滚动数组。 */ #include<cstdio> #include<iostream> #include<cstdlib> #define N 5010 #define mod 1000000007 using namespace std; int n,a,b,m,f[2][N],s[2][N]; int main() { //freopen("lab.in","r",stdin); //freopen("lab.out","w",stdout); scanf("%d%d%d%d",&n,&a,&b,&m); f[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,f[i%2][j]=((s[(i+1)%2][n]-s[(i+1)%2][j-(j-b-1)/2-1]-f[(i+1)%2][j])%mod+mod)%mod; if(j<b)limit=j+(b-j-1)/2,f[i%2][j]=((s[(i+1)%2][j+(b-j-1)/2]-f[(i+1)%2][j])%mod+mod)%mod; s[i%2][j]=(s[i%2][j-1]+f[i%2][j])%mod; } int ans=0; for(int i=1;i<=n;i++) ans+=f[m%2][i],ans%=mod; printf("%d",ans); return 0; }
旅行(travel)
Time Limit:1000ms Memory Limit:64MB
题目描述
LYK 想去一个国家旅行。这个国家共有 n 个城市,有些城市之间存在道路,我们假定这
些道路长度都是 1 的,更准确的说,共有 m 条道路。
我们定义城市 A 与城市 B 的最短路为 A 到 B 的所有路径中,经过的道路最少的那条道
路。最短路的长度为这条道路的所有道路长度之和,由于所有道路长度都为 1,因此假如 A
到 B 之间最短路的道路条数为 k,则 A 到 B 的最短路长度为 k。
我们定义整个国家的最短路为任意两个城市( A,B 与 B,A 算作不同的点对)之间的最短
路长度的和。
然而这个国家正处于危乱之中,极有可能一条道路会被恐怖分子炸毁。
LYK 想知道,万一某条道路被炸毁了,整个国家的最短路为多少。若炸毁这条道路后整
个国家不连通了,那么就输出“ INF” (不加引号)。
输入格式(travel.in)
第一行两个数 n,m。
接下来 m 行,每行两个数 u,v,表示存在一条道路连接 u,v(数据保证不存在自环)。
输出格式(travel.out)
输出 m 行,第 i 行的值表示当第 i 条道路被炸毁时,整个国家的最短路是多少,若图不
连通,则输出“ INF”。
输入样例
2 2
1 2
1 2
输出样例
2 2
数据范围
对于 20%的数据 n<=10,n<m<=100。
对于 40%的数据 1<=n<m<=100。
对于 70%的数据 1<=n<=100,n<m<=3000。
对于再另外 10%的数据对于所有节点( i 1<=i<n),存在一条边连接 i与 i+1,且 n=m,n<=100。
对于再再另外 10%的数据对于所有节点 i( 1<=i<n),存在一条边连接 i 与 i+1,且 n=m,
n<=1000。
对于再再再另外 10%的数据对于所有节点( i 1<=i<n),存在一条边连接 i 与 i+1,且 n=m,
n<=100000。
/* 只做了前70分,用最短路树,后30分用容斥原理,不会做。 前70分:我们可以先找一遍最短路,然后记下f[i]表示i到其他个点的距离总和,记下zd[i][j]表示以i为起点的最短路树中有没有j这条边。当我们删边时,如果这条边没在以i为起点最短路树中,直接加上f[i],否则,再宽搜一遍,这样可以保证,对于每个起点,删边时,最多宽搜n-1边,时间复杂度变成了O(mn^2)。 */ #include<cstdio> #include<Cstring> #include<iostream> #include<queue> #define N 110 #define M 3010 #define INF 1000000000 using namespace std; int head[N],dis[N],vis[N],f[N],zd[N][M*2],n,m; struct node { int v,pre,fl; };node e[M*2]; void add(int i,int x,int y) { e[i].v=y; e[i].pre=head[x]; head[x]=i; } void bfs(int s) { memset(vis,0,sizeof(vis)); memset(dis,0x3f3f3f3f,sizeof(dis)); queue<int> q; q.push(s);vis[s]=1;dis[s]=0; while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].pre) if(!vis[e[i].v]) { zd[s][i]=1; dis[e[i].v]=dis[u]+1; vis[e[i].v]=1; q.push(e[i].v); } } for(int i=1;i<=n;i++) { f[s]+=dis[i]; if(f[s]>=INF){f[s]=INF;break;} } } int bfs2(int s) { memset(vis,0,sizeof(vis)); memset(dis,0x3f3f3f3f,sizeof(dis)); queue<int> q; q.push(s);vis[s]=1;dis[s]=0; while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].pre) if(!vis[e[i].v]&&!e[i].fl) { dis[e[i].v]=dis[u]+1; vis[e[i].v]=1; q.push(e[i].v); } } int tot=0,flag=0; for(int i=1;i<=n;i++) { tot+=dis[i]; if(tot>=INF)flag=1; } if(flag)return INF; return tot; } int main() { freopen("jh.in","r",stdin); //freopen("travel.in","r",stdin); //freopen("travel.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y;scanf("%d%d",&x,&y); add(i*2-1,x,y);add(i*2,y,x); } for(int i=1;i<=n;i++) bfs(i); for(int i=1;i<=m;i++) { int tot=0,flag=0; for(int j=1;j<=n;j++) { if(zd[j][i*2-1]||zd[j][i*2]) { e[i*2-1].fl=e[i*2].fl=1; tot+=bfs2(j); e[i*2-1].fl=e[i*2].fl=0; } else tot+=f[j]; if(tot>=INF) { printf("INF ");flag=1;break; } } if(!flag)printf("%d ",tot); } return 0; }