Contest1275 - 2017区域赛组队&&个人训练赛17
问题 B: 完美序列
时间限制: 1 Sec 内存限制: 128 MB提交: 29 解决: 18
[提交][状态][讨论版]
题目描述
已知一个长度为l的序列:b1,b2,b3,…,bl (1<=b1<=b2<=b3<=…<=bl<=n)。若这个序列满足每个元素是它后续元素的因子,换句话说就是对于任意的i (2<=i<=l)都满足bi%bi-1=0 (其中“%”代表求余),则称这个序列是完美的。你的任务是对于给定的n和l,计算出一共有多少序列是完美序列。由于答案很大,所有输出答案对1000000007取余后的结果。
输入
输入的第一行为一个正整数T (T<=1000),代表一共有T组测试数据。
每组测试数据包含两个正整数n,l (1<=n, l<=2000),分别代表序列中元素大小的最大值和序列的长度。
输出
对于每组测试数据,输出一行包含一个整数,代表答案对1000000007取余后的结果。
样例输入
33 26 42 1
样例输出
5392
提示
一道dp题,dp[i][j] 中i表示序列的长度,j表示该序列最后一位元素
状态压缩公式:dp[i][k]=(dp[i][k]+dp[i-1][j])%mod j是k的因子
代码如下:
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int N=2000+5;
const int mod=1e9+7;
int dp[N][N];
void lk()
{
memset(dp,0,sizeof(dp));
for(int i=1;i<N;i++)
dp[1][i]=1;
for(int i=1;i<N-1;i++)
for(int j=1;j<N-1;j++)
for(int k=j;k<N-1;k+=j)
dp[i+1][k]=(dp[i+1][k]%mod+dp[i][j]%mod)%mod;
}
int main()
{
int t,n,l;
lk();
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&l);
int ans=0;
for(int i=1;i<=n;i++)
ans=(ans+dp[l][i])%mod;
printf("%d\n",ans);
}
return 0;
}
问题 C: 第k大数
时间限制: 10 Sec 内存限制: 128 MB提交: 76 解决: 24
[提交][状态][讨论版]
题目描述
有两个序列a,b,它们的长度分别为n和m,那么将两个序列中的元素对应相乘后得到的n*m个元素从大到小排列后的第k个元素是什么?
输入
输入的第一行为一个正整数T (T<=10),代表一共有T组测试数据。
每组测试数据的第一行有三个正整数n,m和k(1<=n, m<=100000,1<=k<=n*m),分别代表a序列的长度,b序列的长度,以及所求元素的下标。第二行为n个正整数代表序列a。第三行为m个正整数代表序列b。序列中所有元素的大小满足[1,100000]。
输出
对于每组测试数据,输出一行包含一个整数代表第k大的元素是多少。
样例输入
33 2 31 2 31 22 2 11 11 12 2 41 11 1
样例输出
311
提示
如果直接暴力来求的话,定会超时,超内存然而该题只是求某一个值,因此用二分来优化时间和空间
首先对a,b 数组进行排序
l=a[0]*b[0] , r=a[n-1]*b[m-1] l为最小值,r 为最大值 ,进行二分处理
先去从最后的序列里找大于l和r的中值mid的个数
若个数大于等于k ,则说明该中值mid小于等于所求的数,即l要变为mid+1
否则,说明中值mid大于所求的数,即r变为mid-1
直到 l > r 结束
代码如下:
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=1e5+7;
typedef long long ll;
ll a[N],b[N];
int n,m;
ll lk(ll mid)//find > mid num
{
ll num=0;
int j=0;
for(int i=n-1;i>=0;i--)
for(;j<m;j++)
if(a[i]*b[j]>=mid)
{
num+=m-j;
break;
}
return num;
}
int main()
{
int t;
ll k,l,r,mid;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%lld",&n,&m,&k);
for(int i=0;i<n;i++)
scanf("%lld",&a[i]);
for(int i=0;i<m;i++)
scanf("%lld",&b[i]);
sort(a,a+n);
sort(b,b+m);
l=a[0]*b[0];
r=a[n-1]*b[m-1];
ll ans;
while(l<=r)
{
mid=(l+r)>>1;
ll num=lk(mid);
if(num>=k)
{
ans=mid;
l=mid+1;
}
else
r=mid-1;
}
printf("%lld\n",ans);
}
return 0;
}
问题 K: 奶酪
时间限制: 1 Sec 内存限制: 128 MB提交: 110 解决: 29
[提交][状态][讨论版]
题目描述
现在,奶酪的下表面有一只小老鼠 Jerry ,它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交,则 Jerry 可以从其中一个空洞跑到另一个空洞,特别地,如果一个空洞与下表面相切或是相交, Jerry 则可以从奶酪下表面跑进空洞;如果一个空洞与上表面相切或是相交, Jerry 则可以从空洞跑到奶酪上表面。
位于奶酪下表面的 Jerry 想知道,在不破坏奶酪的情况下,能否利用已有的空洞跑到奶酪的上表面去 ?
P1(x1,y1,z1)、P2(x_2,y_2,z_2)P2(x2,y2,z2)的距离公式如下:
输入
第一行,包含一个正整数 T,代表该输入文件中所含的数据组数。
接下来是 T 组数据,每组数据的格式如下:
第一行包含三个正整数 n,h 和 r,两个数之间以一个空格分开,分别代表奶酪中空洞的数量,奶酪的高度和空洞的半径。
接下来的 n 行,每行包含三个整数 x、y、z,两个数之间以一个空格分开,表示空洞球心坐标为(
输出
样例输入
3
2 4 1
0 0 1
0 0 3
2 5 1
0 0 1
0 0 4
2 5 2
0 0 2
2 0 4
样例输出
Yes
No
Yes
提示
分析:
首先将入口,出口进行标记,然后将互相能够连通的空洞建立边
然后以入口为起点,进行bfs搜索
也可以用并查集来做,只要确定起点和终点是否有共同的祖先
代码如下:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
typedef long long ll;
const int N=2000;
struct LK{
ll x,y,z;
}a[N];
struct Edge{
int to,next;
}edge[N*N];
bool st[N],ed[N],flag,vis[N];
int head[N],k;
void init(int n)
{
for(int i=0;i<=n;i++)
{
ed[i]=false;
st[i]=false;
head[i]=-1;
}
}
bool lk(int i,int j,ll r)
{
if((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z)<=4*r*r)
return true;
return false;
}
void add(int i,int j)
{
edge[k].to=j;
edge[k].next=head[i];
head[i]=k++;
edge[k].to=i;
edge[k].next=head[j];
head[j]=k++;
}
void bfs(int st)
{
queue<int>q;
while(!q.empty())
q.pop();
q.push(st);
vis[st]=1;
while(!q.empty())
{
int top=q.front();
for(int k=head[top];k!=-1;k=edge[k].next)
{
if(ed[edge[k].to])
{
flag=false;
return;
}
if(!vis[edge[k].to])
{
q.push(edge[k].to);
vis[edge[k].to]=1;
}
}
q.pop();
}
}
int main()
{
int t,n;
ll h,r;
scanf("%d",&t);
while(t--)
{
scanf("%d%lld%lld",&n,&h,&r);
init(n);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);
if(r+a[i].z>=h)
ed[i]=true;
if(a[i].z-r<=0)
st[i]=true;
}
k=0;
for(int i=1;i<=n;i++)
for(int j=1+i;j<=n;j++)
if(lk(i,j,r))
add(i,j);
flag=true;
for(int i=1;i<=n&&flag;i++)
if(st[i])
{
if(ed[i])
{
flag=false;
break;
}
for(int j=1;j<=n;j++)
vis[j]=0;
bfs(i);
}
if(!flag)
puts("Yes");
else
puts("No");
}
return 0;
}
上一篇: 数据结构:求解第k大(小)数
下一篇: php插入排序