2017ccpc哈尔滨
HDU 6231
题目要求
给出数组a 把每个区间中第k大的数字放入b数组(若区间长度小于k忽略) 输出b数组中第m大的数字
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| using namespace std; int t,n,k; LL m; int a[maxn]; bool check(int x){ LL num=0; int cnt=0,p=0; for(int i=1;i<=n;i++){ while(cnt<k && p<=n){ if(a[++p]>=x) cnt++; } num+=n-p+1; if(a[i]>=x) cnt--; } return num>=m; } int main(){ // freopen("input.txt","r",stdin); scanf("%d",&t); while(t--){ scanf("%d%d%lld",&n,&k,&m); int limit=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); limit=max(limit,a[i]); } int l=1,r=limit; int ans=0; while(l<=r){ int mid=l+r>>1; if(check(mid)){ ans=mid,l=mid+1; } else r=mid-1; } printf("%d\n",ans); } return 0; }
|
思路
二分b数组中第m大的数字x 找出数组a中满足第k大为x的区间个数 若区间个数大于等于m 修改二分边界使x更大
check用了尺取法寻找区间个数
注意m要开ll 区间个数会超过int
HDU 6233
题目要求
有一颗n个点的树 边权为1 有m个结点的位置上有人 每个人单位时间移动一单位
现所有人开始往有人的方向移动 要求任意两个人的距离必须大于等于1 若等于1停止走动
问所有人停止走动时花费的时间
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| using namespace std; int t,n,m; int Max,id; int a[maxn],hashh[maxn]; vector<int>e[maxn]; void init(){ for(int i=0;i<=n;i++) e[i].clear(); Max=0,id=0; mm(hashh,0); } void dfs(int x,int fa,int dep){ for(int i=0;i<e[x].size();i++){ int next=e[x][i]; if(next==fa) continue; if(hashh[next]){ if(dep>Max) Max=dep,id=next; } dfs(next,x,dep+1); } } int main(){ // freopen("input.txt","r",stdin); scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); init(); for(int i=1;i<=m;i++){ scanf("%d",&a[i]); hashh[a[i]]++; } for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); } dfs(a[1],0,1); Max=0; dfs(id,0,1); int ans=floor(Max/2.0); printf("%d.00\n",ans); } return 0; }
|
思路
思维题
可以发现答案就是以两个人为边界的树上最长链的长度/2.0下取整
理由：所有人都是往重心方向移动 自然移动方向是以两个人为边界的树上最长链的中点位置
所以除以2下取整就是花费的时间
求最长链2边dfs即可 维护下最长链的长度
HDU 6235
题目要求
要求构造出一个序列 使得pi mod |pi−pi−2| ==0
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| using namespace std; int t,n; int a[maxn]; int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); int mid=ceil(n/2.0); int x=1; for(int i=1;i<=mid;i++) a[2*i-1]=x++; for(int i=1;i<=n-mid;i++) a[2*i]=x++; for(int i=1;i<=n;i++){ if(i==n) printf("%d\n",a[i]); else printf("%d ",a[i]); } } return 0; }
|
思路
按照奇偶性顺序交叉 可以满足差值永远是1 符合条件
