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]\) 。