70 C

题意

求两个数 \(x,y\) ，使得在一个 \(x×y\) 的矩阵中，对于任意一个元素 \(a_{ij}\) ，有 \(i*j=rev(i)*rev(j)\) 。 \(rev(x)\) 指将 \(x\) 各位翻转得到的数。要求这样的数在该矩阵中至少有 \(w\) 个，且 \(x\le maxx,y\le maxy\) 。最小化 \(x×y\) 。
\((x,y\le 10^5,w\le 10^7)\)

Examples

Input
2 2 1
Output
1 1
Input
132 10 35
Output
7 5
Input
5 18 1000
Output
-1
Input
48 132 235
Output
22 111

解

明确： \(i*j=rev(i)*rev(j)?\frac{i}{rev(i)}=\frac{rev(j)}{j}\)
首先预处理出 \(\frac{i}{rev(i)}\) 。
然后用two-pointers算法，定义 \(i\) 从 \(1\) 扫到 \(maxx\) ， \(j\) 从 \(maxy\) 扫到 \(1\) 。
同时定义两个map \(mp1,mp2\) ，分别表示 \(1-i\) 中每个 \(i/rev(i)\) 出现了几次、 \(1-j\) 中每个 \(j/rev(j)\) 出现了几次。
当 \(i*j<w\) 时，答案不够大， \(i++\) ；
否则， \(j--\) 。
指针每移动一步，都要更新答案和 \(mp1,mp2\) 。
注意精度问题。

70 D

你要维护一个凸包，给你 \(Q\) 个询问，形如：

• 将一个点加到凸包内；

• 询问一个点是否在凸包内。
  \((Q\le 10^5)\)

  Examples

  Input
  8
  1 0 0
  1 2 0
  1 2 2
  2 1 0
  1 0 2
  2 1 1
  2 2 1
  2 20 -1
  Output
  YES
  YES
  YES
  NO

  解

  由于每个横坐标一定最多对应一个纵坐标，所以用两个map<int,int>（水平序）维护上、下凸包，查询时用叉积判断。
  可以证明总时间复杂度为 \(O(n\log n)\) 。
  有一种方法可以大大减少代码长度，就是将下凸包中每个点的纵坐标取相反数。
  将会涉及到一大堆map迭代器map<int,int>::iterator的操作，细节非常多，具体请看代码
  要有耐心

  Code

#include<bits/stdc++.h>
#define maxn 100003
#define INF 1050000000
using namespace std;
template<typename T>
void read(T& x){
    x=0;
    char c=getchar();
    bool sgn=0;
    while((c<'0'||c>'9')&&c!='-')c=getchar();
    if(c=='-')sgn=1,c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
    if(sgn)x=-x;
}

typedef long long tp;
struct point{
    tp x,y;
    point(){}
    point(tp _x,tp _y):x(_x),y(_y){}
    point(const pair<tp,tp>& p):x(p.first),y(p.second){}
    bool operator <(const point& p)const{return x==p.x?y<p.y:x<p.x;}
    bool operator ==(const point& p)const{return x==p.x&&y==p.y;}
    bool operator >(const point& p)const{return x==p.x?y>p.y:x>p.x;}
    point operator +(const point& p)const{return point(x+p.x,y+p.y);}
    point operator -(const point& p)const{return point(x-p.x,y-p.y);}
    point operator *(tp k)const{return point(x*k,y*k);}
};
typedef point Vec;
tp cross(const Vec& u,const Vec& v){return u.x*v.y-v.x*u.y;}

typedef map<tp,tp>::iterator iter;
iter i,j,k,l,o;
map<tp,tp> up,down;
bool check(map<tp,tp>& mp,const point& p){
    if(mp.empty())return 1;
    if(mp.count(p.x))return p.y>mp[p.x];
    if(p.x<mp.begin()->first||p.x>(--mp.end())->first)return 1;
    i=mp.lower_bound(p.x);
    j=i,j--;
    return cross(point(*i)-point(*j),p-point(*j))>0;
}
void insert(map<tp,tp>& mp,const point& p){
    if(!check(mp,p))return;
    mp[p.x]=p.y;
    k=mp.upper_bound(p.x);
    l=k,l--;
    if(k!=mp.end()){
        for(j=i=k,j++;j!=mp.end()&&cross(point(*j)-point(*i),p-point(*i))>0;i=j,j++){
            mp.erase(i);
        }
    }
    if(l!=mp.begin()){
        l--;
        if(l!=mp.begin()){
            for(o=l,o--;l!=mp.begin()&&cross(point(*o)-point(*l),p-point(*l))<0;l=o,o--){
                mp.erase(l);
            }
        }
    }
}
int main(){
    int Q;
    read(Q);
    while(Q--){
        int mo;
        point p;
        read(mo),read(p.x),read(p.y);
        if(mo==1){
            insert(up,p);
            insert(down,point(p.x,-p.y));
        }
        else{
            puts(check(up,p)||check(down,point(p.x,-p.y))?"NO":"YES");
        }
    }
    return 0;
}

70 E

一棵树，在上面建造若干个站点，建造一个站点的代价为 \(k\) ，每个节点 \(u\) 的代价为 \(d[\min(dis(u,i))]\) （ \(i\) 为任意建造了站点的节点，\(k\) 、 \(d\) 数组在输入中给出）
问怎么建造能使得总代价最小，并输出每个节点的代价（任意一解）
\((1\le n\le 180)\)

Examples

Input
8 10
2 5 9 11 15 19 20
1 4
1 3
1 7
4 6
2 8
2 3
3 5
Output
38
3 3 3 4 3 4 3 3

解

本题虽然数据只有180，但其实 \(n^2\) 就可过了 为什么还要 \(n^3\) 地跑floyd+邻接矩阵存边……
dp思路不同于一般的树形dp，有必要记一记
设 \(dp[i][j]\) 表示节点 \(i\) 依赖周围的某一个站点 \(j\) ，\(i\) 及其子树的总代价
初始值： \(dp[u][i]=d[dis(u,i)]+k\)
转移方程： \(dp[u][i]+=\min(dp[v][i]-k,dp[v][j])\) （ \(j\) 使得 \(dp[v][j]\) 最小）
统计答案时，dfs，判断 \(dp[v][i]-k<dp[v][j]\) 。

Codeforces 70

原文：https://www.cnblogs.com/BlogOfchc1234567890/p/10502812.html