计算几何
题目描述
花花对计算几何有着浓厚的兴趣。他经常对着平面直角坐标系发呆，思考一些有趣的问题。今天，他想到了一个十分有意思的题目：
首先，花花会在$x$轴正半轴和$y$轴正半轴分别挑选$n$个点。随后，他将$x$轴的点与$y$轴的点一一连接，形成$n$条线段，并保证任意两条线段不相交。花花确定这种连接方式有且仅有一种。最后，花花会给出$m$个询问。对于每个询问，将会给定一个点$P(x_p,y_p)$，问线段$OP$（$O$ 为坐标原点）与$n$条线段会产生多少个交点？
输入第 $1$ 行包含一个正整数 $n$，表示线段的数量；
第 $2$ 行包含 $n$ 个正整数，表示花花在 $x$ 轴选取的点的横坐标；
第 $3$ 行包含 $n$ 个正整数，表示花花在 $y$ 轴选取的点的纵坐标；
第 $4$ 行包含一个正整数 $m$，表示询问数量；
随后 $m$ 行，每行包含两个正整数 $x_p$ 和 $y_p$ ，表示询问中给定的点的横、纵坐标。
样例输入
样例输出
数据范围
对于 $40 \ percent $ 的数据：$n,m ≤ 10$
另有 $20 \ percent $ 的数据：$n,m ≤ 100$
另有 $20 \ percent $ 的数据：$n,m ≤ 1000$
对于 $100 \ percent $ 的数据：$n,m ≤ 10^5,y < 2^{31}$
题解
本题考察了计算几何中较为基础的知识，根据题意，可以先将数据升序排序，然后进行二分答案。对于判定直线是否相交则可以用求零点的方法，已知每条线段的纵坐标都是大于零的，所以只需要比较当 $x=x_p$ 时的 $y_p$ 与 $y_mid$ 大小即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N =1e5+1;
int n,m,x[N],y[N];
double a[N];
typedef double db;
inline void get(int &x)
{
x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
}
int main()
{
get(n);
for(int i=1;i<=n;++i)get(x[i]);sort(x+1,x+n+1);
for(int i=1;i<=n;++i)get(y[i]);sort(y+1,y+n+1);
get(m);
for(int i=1,xx,yy;i<=m;++i)
{
get(xx);get(yy);
int l=0,r=n,mid;
while(l!=r)
{
mid=l+r+1>>1;
if(!a[mid])a[mid]=-((db)(y[mid]))/((db)(x[mid]));
double yt=a[mid]*(db)xx+y[mid];
if(yt<=(db)yy) l=mid;
else r=mid-1;
}
printf("%d\n",l);
}
}
|
花花的聚会
题目描述
花花住在 H 国。H 国有 $n$ 个城市，其中 $1$ 号城市为其首都。城市间有$n − 1$条单向道路。从任意一个城市出发，都可以沿着这些单向道路一路走到首都。事实上，从任何一个城市走到首都的路径是唯一的。
过路并不是免费的。想要通过某一条道路，你必须使用一次过路券。H 国一共有 $m$ 种过路券，每张过路券以三个整数表示：$v,k,w$：你可以在城市 $v$ 以价格 $w$ 买到一张过路券。这张券可以使用 $k$ 次。这意味着，拿着这张券通过了 $k$ 条道路之后，这张券就不能再使用了。
请注意你同一时间最多只能拥有最多一张过路券。但你可以随时撕掉手中已有的过路券，并且在所在的城市再买一张。
花花家在首都。他有 $q$ 位朋友，他希望把这些朋友们都邀请到他家做客。所以他想要知道每位朋友要花多少路费。他的朋友们都很聪明，永远都会选择一条花费最少的方式到达首都。
花花需要准备晚餐去了，所以他没有时间亲自计算出朋友们将要花费的路费。你可以帮帮他么？
输入的第一行包含两个空格隔开的整数 $n$ 和 $m$，表示 H 国的城市数量和过路券的种数。
之后的 $n − 1$ 行各自包含两个数 $a_i$ 和 $b_i$ ，代表城市 $a_i$ 到城市 $b_i$ 间有一条单向道路。
之后的 $m$ 行每行包括三个整数 $v_i$ ,$k_i$ 和 $w_i$ ，表示一种过路券。
下一行包含一个整数 $q$，表示花花朋友的数量。
之后的 $q$ 行各自包含一个整数，表示花花朋友的所在城市。
输出共 $q$ 行，每一行代表一位朋友的路费。
样例输入
7 7
3 1
2 1
7 6
6 3
5 3
4 3
7 2 3
7 1 1
2 3 5
3 6 2
4 2 4
5 3 10
6 1 20
3
5
6
7
|
样例输出
数据范围
对于 $40 \ percent$ 的数据：$n,m,q ≤ 10,w_i ≤ 10$
另有 $20 \ percent$ 的数据：$n,m,q ≤ 500,w_i ≤ 100$
另有 $20 \ percent$ 的数据：$n,m,q ≤ 5000,w_i ≤ 1000$
对于 $100 \ percent$ 的数据：$n,m,q ≤ 10^5 ,w_i ≤ 10000,1 ≤ v_i,k_i ≤ n$
题解
树形动态规划。设$f[i]$为从$i$到根节点的最小花费，则可以得到状态转移方程：
$$f[y] = min {\lbrace f[x] + w[y][i] \rbrace} ( x 为 y 祖先, dep[x] - dep[y] > = k[y][i] )$$
对于寻找$min \lbrace f[x] \rbrace $的操作，则可以通过倍增或树链剖分的方法实现。(要开 $long long$ 不然会爆)
#include<iostream>
#include<algorithm>
#include<cstdio>
const int inf =0x7fffffff;
const int N =1e5+1;
const int maxlogn =21;
using namespace std;
int deep[N],head[N],head2[N];
long long st[N][maxlogn],minn[N][maxlogn],f[N];
int tot,tot2,n,m,qu;
struct edg{int t,ne;}e[N*2];
struct edg2{int k,w,ne;}e2[N*2];
void in(int x,int y)
{
e[++tot].t=y;
e[tot].ne=head[x];
head[x]=tot;
return;
}
void in2(int x,int k,int w)
{
e2[++tot2].k=k;
e2[tot2].w=w;
e2[tot2].ne=head2[x];
head2[x]=tot2;
return;
}
void getf(int x,int pre)
{
st[x][0]=pre;minn[x][0]=f[pre];
for(int i=1;i<maxlogn;i++)
{
st[x][i]=st[st[x][i-1]][i-1];
minn[x][i]=min(minn[x][i-1],minn[st[x][i-1]][i-1]);
}
f[x]=x==1?0:inf;
for(int i=head2[x];i;i=e2[i].ne)
{
long long tmp=inf,y=x,k=e2[i].k,p=0;
while(k)
{
if(k&1)tmp=min(tmp,minn[y][p]),y=st[y][p];
p++;k>>=1;
}
f[x]=min(f[x],tmp+e2[i].w);
}
for(int i=head[x];i;i=e[i].ne)
{
int y=e[i].t;
if(y!=pre)getf(y,x);
}
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),in(x,y),in(y,x);
for(int i=1,x,k,w;i<=m;i++)scanf("%d%d%d",&x,&k,&w),in2(x,k,w);
scanf("%d",&qu);getf(1,1);
for(int i=1,x;i<=qu;i++){scanf("%d",&x);printf("%d\n",f[x]);}
}
|
文本编辑器
题目描述
九发明了一个完美的文本编辑器。这个编辑器拥有两个光标（cursor），所以九能够同时在两处地方插入和删除文本。这个编辑器除了正常的编辑功能以外，还有一些只有九才知道用处的功能，例如翻转两个光标之间的文本。某一天，九把自己的完美文本编辑器给弄丢了，但是她还有好多好多文本需要处理。于是她想请聪明又智慧的你帮她实现完美文本编辑器的一些功能。
功能列表如下：
< w
w 为一个字符，“L”或“R”，表示左光标还是右光标（下同）。
该命令将选定光标向左移动，如果已经是最左端则不移动。
命令执行成功时输出“T”，若光标已经在最左端，则输出“F”。
> w
w 同上。
与< 命令不同的是，该命令将光标向右移动。
命令执行成功时输出“T”，若光标已经在最右端，则输出“F”。
I w c
w 同上。
c 是一个可见字符(33≤ ascii 码 ≤ 126)，代表在该光标左侧插入该字符。
该命令始终输出“T”。
D w
w 同上。
代表删除该光标右侧的一个字符。
命令执行成功时输出“T”，若光标右侧没有字符输出“F”。
R
代表翻转左光标和右光标之间的字符。
该命令只有左光标在右光标左侧时才能执行。
（两光标重合时也不能执行）
命令执行成功时输出“T”，否则输“F”。
S
代表显示当前处理的文本。
该命令只输出文本，不输出“T”和“F”。
|
开始时文本编辑器中有一定内容，左光标在第一个字符左，右光标在最后一个字符右。
注意：在插入和删除操作中，没有被操作的光标与文本的相对左右位置保持不变。特别地，若两个光标重叠，操作后也仍然重叠。
输入第一行是初始时文本编辑器内容。
第二行是一个正整数 $N$，$N$ 表示操作次数。
接下来有 $N$ 行，每行有一个命令，命令格式如上方表格。
对于每个命令，按上方表格要求执行并输出。
样例输入
goodykc
11
I R u
I R l
> L
> L
> L
> L
R
D R
< R
D R
S
|
样例输出
数据范围
对于 $40 \ percent$ 的数据：$1 ≤ N$ , 初始文本长度 $≤ 100$，数据不包含翻转（Reverse）操作；
另有 $30 \ percent$ 的数据：$1 ≤ N$ , 初始文本长度 $ ≤ 10^5$ ，数据不包含翻转（Reverse）操作；
另有 $20 \ percent$ 的数据：$1 ≤ N$ , 初始文本长度 $ ≤ 10^5$ ，数据包含翻转（Reverse）操作；
对于 $100 \ percent$ 的数据：$1 ≤ N$ , 初始文本长度 $ ≤ 4 × 10^6$ ，输出文件大小 $≤ 20MB$。
题解
用链表可以模拟所有操作，对于时间复杂度较高的翻转操作，可以考虑将所有的节点前驱后驱交换一下，边界的前后驱特殊处理。但这样时间复杂度仍过高，可以考虑借鉴一下树形数据结构的LAZY_TAG思想，只有在访问到该节点时才修改并交换先后驱。
具体的实现代码十分清楚，但还有许多细节要注意，因为 $l,r$ 的相对位置可能互换，所以只能写左开右开或左闭右闭区间。
#include<iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e7+1;
int tot,m,pos[2],cnt[2],pre[N],next[N];
char opreator,ch[N],str[N];
int move(){getchar();return getchar()=='L'?0:1;}
void in(int opreator,char c)
{
++tot;
ch[tot]=c;
int u=pos[opreator],v=next[u];
pre[tot]=u;next[tot]=v;
next[u]=tot;pre[v]=tot;
if (cnt[opreator^1]>=cnt[opreator])cnt[opreator^1]++;
pos[opreator]=tot;cnt[opreator]++;
if (pos[opreator^1]==u)pos[opreator^1]=tot;
printf("T\n");
}
void ll(int opreator)
{
if (pos[opreator]==1){printf("F\n");return;}
int u=pos[opreator],v=pre[u];
if (next[v]!=u)swap(next[v],pre[v]);
pos[opreator]=v; cnt[opreator]--;
printf("T\n");
}
void rl(int opreator)
{
if (next[pos[opreator]]==2){printf("F\n");return;}
int u=next[pos[opreator]],v=next[u];
if(pre[v]!=u)swap(next[v],pre[v]);
pos[opreator]=u;cnt[opreator]++;
printf("T\n");
}
void D(int opreator)
{
if (next[pos[opreator]]== 2){printf("F\n");return;}
int u = pos[opreator], v = next[u], w = next[v];
if (pre[w]!=v) swap(next[w], pre[w]);
if (cnt[opreator^1]>cnt[opreator])cnt[opreator^1]--;
if (pos[opreator^1]==v)pos[opreator^1]=u;
next[u]= w;pre[w]=u;
printf("T\n");
}
void R()
{
if (cnt[1]-cnt[0]<=0){printf("F\n");return;}
if (cnt[1]-cnt[0]==1){printf("T\n");return;}
int now=pos[0],ne=next[now],c=pos[1],d=next[c];
swap(pre[ne], next[ne]);swap(pre[c],next[c]);
next[now]=c;pre[c]=now;next[ne]=d;pre[d]=ne;
pos[1]=ne;
printf("T\n");
}
void show()
{
int u=1;
while(true)
{
if(pre[next[u]]!= u)swap(pre[next[u]],next[next[u]]);
u=next[u];
if (u==2)break;
putchar(ch[u]);
}
printf("\n");
}
void init()
{
tot=2;
pre[1]=-1;next[1]= 2;
pre[2]=1;next[2]=-1;
pos[0]=pos[1]=cnt[0]=cnt[1]=1;
int len=strlen(str);
for(int i=0;i<len;i++)
{
++tot;
ch[tot]=str[i];
pre[tot]= i==0?1:tot-1;
next[tot]= i==len-1?2:tot+1;
}
if(len>0)
{
next[1]=3;pre[2]=tot;
pos[1]=tot;cnt[1]=len+1;
}
}
int act()
{
if(opreator=='<') ll(move());
if(opreator=='>') rl(move());
if(opreator=='I')
{
int d=move();
char c=getchar();
while (c<33||c>126)c=getchar();
in(d,c);
}
if (opreator=='D') D(move());
if (opreator=='R') R();
if (opreator=='S') show();
}
int main()
{
scanf("%s",str);
init();
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
getchar();
opreator=getchar();
while (opreator!='<'&& opreator!='>'&&!(opreator >='A'&& opreator <='Z'))opreator=getchar();
act();
}
return 0;
}
|
