Solution 1003

一:取整

题目描述

题目描述

哪门编程语言是全世界最好的编程语言? 为了解决这个世界性的难题,
你找了机房内的一些小伙伴进行调查, 在你发送调查问卷的过程中有些
小伙伴已经填好了问卷交给了你.
因此现在你手上一共有 份问卷, 有一些已经填好的问卷,有一些待发放
的问卷.
在已经填好的问卷里,你统计了一下一共有 种语言, 每种语言的支持
人数是
由于大家都最喜欢 语言, 因此 结果对你来说已经没有悬念
了, 不过这个时候你 开始对另一件事情感兴趣.
在统计每种语言的百分比的时候, 你喜欢对百分比进行四舍五入, 比如
23.33% 你最终会记成23, 99.6 你最终会写成100.
已知语言的种类是无限的,也就是剩下的每份问卷可能会得到一些新的
语言,也可能会是已经有的这些语言.
现在问你最终所有的百分比之和最大可能是多大.

数据范围

$n \le 10^5$

思路

把小数部分>=0.5的与其他数字加起来显然不会更优。

于是将已经有的语言去掉整数部分后降序,将若干个$100\times \frac{1}{n}$依次往里放。

二:路标

题目描述

题目描述

Signeld镇位于一条完全平直且无限长的道路上,从西向东延伸。沿
着这条路,有一系列S个神秘的道路标志,标志的两面都有数字。第i
个标志(从西向东依次编号)位于Signeld以东Di公里处,标志朝西
侧写有一个整数Ai,朝东侧写有一个整数Bi。
Signeld中没有人知道这些标志试图说些什么。您认为标志西侧的数
字适用于向东行驶的司机,并且它们代表到某个特定目的地的距离。
同样地,您认为标志东侧的数字适用于向西行驶的司机,并且它们代
表到某个特定目的地的距离。但是你怀疑并非所有的迹象都与这个理
论一致。
要开始测试您的理论,您算法找到符合以下规则的标志集合:
该集合是所有道路标志序列的一个连续子序列(即一段连续的区间)。
(整个序列也算作连续的子序列。) 其中M和N是(不一定是正数且
不一定是不同的)整数,对于该集合中的每个标志,至少下列之一为
真: Di + Ai = M. Di - Bi = N. 请问,有效集合中最大可能的标志数是
多少,以及有多少个不同的有效集合?

数据范围

$D_i , A_i , B_i \le 10^6$

思路

双指针(尺取法)

@517coding说:

我们发现固定一个左端点,右端点越往右越不容易满足条件,而 且肯定是连续的一段都满足条件,存在单调性.

令 $a_i=D_i+A_i, b_i=D_i-B_i$

扩展当前节点时:

  1. 区间内只有一种$a_i$或者只有一种$b_i$, 这种情况肯定是可以的
  2. 当区间内有两种或者以上的$a_i$的时候:
    1. 对于当前的ai如果选择它,那么上一个不同的ai对应的bi一定要选,如果 选择这一对数能覆盖到所有的位置就可行
    2. 对于当前的ai如果不选择,那么当前的bi一定要选,上一个不同的bi对应 的ai一定要选,如果选择这一对数能覆盖到所有的位置就可行

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
    freopen("sign.in", "r", stdin);
    freopen("sign.out", "w", stdout);
  int tt;
  //cin >> tt;
  //for (int qq = 1; qq <= tt; qq++) 
  {
    //cout << "Case #" << qq << ": ";
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
      int x, y, z;
      cin >> x >> y >> z;
      a[i] = x + y;
      b[i] = x - z;
    }
    map<int,int> ma;	//记录某个a出现了几次 
    map<int,int> mb;	//记录某个b出现了几次 
    map< pair<int,int>,int > mab;	//记录一对(a,b)出现了几次 
    int j = 0;
    int last_a = -1, last_b = -1;
    int ans = -1, ways = -1;
    for (int i = 0; i < n; i++) {
      ma[a[i]]++;
      mb[b[i]]++;
      mab[make_pair(a[i], b[i])]++;
      if (i > 0 && a[i] != a[i - 1]) {	//维护 
        last_a = i - 1;
      }
      if (i > 0 && b[i] != b[i - 1]) {	//维护 
        last_b = i - 1;
      }
      while (j <= i) {	//将左端点向右推 
        if (last_a < j || last_b < j) {
          break;
        }
        int cnt = ma[a[i]] + mb[b[last_a]] - mab[make_pair(a[i], b[last_a])];
        if (cnt == i - j + 1) {		//选当前a[i],成功 
          break;
        }
        cnt = ma[a[last_b]] + mb[b[i]] - mab[make_pair(a[last_b], b[i])];
        if (cnt == i - j + 1) {		//不选当前a[i],选当前b[i],成功
          break;
        }
        ma[a[j]]--;
        mb[b[j]]--;
        mab[make_pair(a[j], b[j])]--;	//左端点向右推 
        j++;
      }
      int len = i - j + 1;
      if (len > ans) {	//更新 
        ans = len;
        ways = 0;
      }
      if (len == ans) {
        ways++;
      }
    }
    cout << ans << " " << ways << '\n';
  }
  return 0;
}

三:树袋

题目描述

题目描述

有一棵树,根节点为1, 一共有 个节点,每个节点上都有一个口袋,我们称
他们为树袋,现在计算鸭准备对这棵树进行 次操作, 第i次操作会给ai
子树与bi子树的所有树袋都放进去一个编号为i的苹果,最后,对于每个
树袋,计算出有多少其他的树袋与自己至少有一个编号一样的苹果.

数据范围

$n \le 10^5$

思路

操作整棵子树,第一个想到的就是dfs序了,一棵子树对应一段区间。

继续观察,一个节点的最终答案,一定比他的父亲节点大(这是显然的),

并且答案就应该是他父亲的答案加上所有以自己为根的操作产生的答案和。

于是就dfs,将所有自己身上进行的操作对应的子树dfs序区间+1,再向下dfs,dfs完返回父亲节点之前将操作撤销(区间-1)

至于答案,显然就是dfs序1-n中>0的点的个数。

然而统计“>0”怎么实现呢?线段树似乎不好解决。

(p.s. 之前再某一道题中我就yy出过这种方法,然鹅同样卡在最后一步上。。)

解决方法还是线段树。

具体来说,就是一个不把lazy-tag下放的线段树。

先看代码:

Code
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> VI;
typedef pair<int,int> PII;
#define rep(i,n) for(int i=0;i<n;i++)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn  =  100010;
VI edge[maxn],adj[maxn];
int L[maxn] , R[maxn] , dfn;
int ans[maxn] ;
void dfs(int u,int fa)
{
     L[u] = ++dfn;
     for (auto it: edge[u]) {
        if(it!=fa) dfs(it,u);
     }
     R[u] = dfn;
}
// ~segment tree
int col[maxn<<2];
int sum[maxn<<2];
void pushup(int rt, int l, int r) 
{
    if(col[rt] > 0) {
        sum[rt] = r - l + 1;
    } else if(l == r) {
        sum[rt] = 0;
    } else {
        sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    }
}
void update(int L,int R,int val,int l,int r,int rt)
{
    if(L <= l && r <= R) {
         col[rt] += val;
        // printf("col[%d]=%d\n",rt,col[rt]);
         pushup(rt,l,r);
         return;
    }
    int m = l + r >> 1;
    if( L <= m) update(L,R,val,lson);
    if( R > m)  update(L,R,val,rson);
    pushup(rt,l,r);
}
void solve(int u,int fa) 
{
//  printf("u=%d\n",u);
    //枚举跟u 有关的 所有的操作
    for(auto it:adj[u]) {
  //    printf("%d %d\n",L[*it],R[*it]);
        update(L[it],R[it],1,1,dfn,1);
    }
    //printf("sum = %d\n",sum[1]);
    ans[u] = sum[1];
    for(auto it: edge[u]) {
        if(it!=fa) solve(it,u);
    }
    //清空与u有关的所有操作
    for(auto it:adj[u]) {
        update(L[it],R[it],-1,1,dfn,1);
    }
}
int main()
{
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    
    int n,m,u,v,a,b;
    scanf("%d%d",&n,&m);
    rep(i,n-1) scanf("%d%d",&u,&v),edge[u].push_back(v),edge[v].push_back(u);
    rep(i,m)  {
        scanf("%d%d",&a,&b);
        adj[a].push_back(a);
        adj[a].push_back(b);

        adj[b].push_back(a);
        adj[b].push_back(b);
    }
    dfs(1,-1);
   // for(int i=1;i<=n;i++) printf("%d %d\n",L[i],R[i]);
    solve(1,-1);
    rep(i,n) printf("%d ",max(1,ans[i+1])-1);
    return 0;
}

实际上,不把lazy-tag下放是正确的。

因为任何时候,没有一个位置是负数,这是显然的。

那么假设一个lazy标记“+1”的区间,再他的子区间内进行“-1”,那么这个子区间之间一定还经历过一次“+1”,算上当前的“+1”标记,这一整段还都是>0的。

正因为这样,一个lazy未下方的区间,他的子区间的sum[](>0的个数)是不一定对的,然而sum[1]是最大的“父亲”区间,是一定正确的。

其实这和扫描线求矩形面积并差不多。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注