## 1.今天考了套题。
好像没什么问题
分数300/300 AK了。
### Mumu[nim+高精]
给你n,m来博弈,每次使m乘2,4,8,16,32中的一个数，直到大于n,最后一个乘数的人输。问怎样开局才赢。
观察每一步的决策
我们设每乘了2的n次方，相当于走了一步
我们每一次决策可以走1,2,3,4,5步，所以一定到达不了6步，而两次操作是一定可以到6步的
又因为在一步的情况下，必须要走，所以在距离终点只差一步时先手必输
所以距离终点差6k+1步时，先手必输
然后对高精进行处理
因为这次n的位数只有150位以下
所以可以直接对m进行乘2操作，每乘一次2，ans++，直到m大于等于n
这时就可以得到到终点的步数，此时素素只需要维持自己走后的步数在6k+1即可
```cpp
#include<cstdio>
int st[160],len,lenm,m[160],n[160],lenn,ans,now,sum;
inline void m_in(){
char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9'){
st[++len]=ch-'0';
ch=getchar();
}
for (int i=len;i>=1;i--) m[++lenm]=st[len--];
}
inline void n_in(){
char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9'){
st[++len]=ch-'0';
ch=getchar();
}
for (int i=len;i>=1;i--) n[++lenn]=st[len--];
}
inline bool judge(){//比较此时m是否小于等于n
if (lenm<lenn) return true;
if (lenm>lenn) return false;
if (lenm==lenn){
for (int i=lenm;i>=1;i--)
if (m[i]>n[i]) return false;
else if (m[i]<n[i]) return true;
}
return true;
}
/*inline void m_write(){
for (int i=lenm;i>=1;i--) printf("%d",m[i]);
putchar('\n');
}*/
inline void m_add(){
for (int i=1;i<=lenm;i++){
m[i]=(m[i]<<1)+now;
if (m[i]>=10) m[i]-=10,now=1;
else now=0;
}
if (now){
lenm++;
m[lenm]=1;
now=0;
}
}
int main(){
freopen("Mumu.in","r",stdin);
freopen("Mumu.out","w",stdout);
m_in();
n_in();
while (judge()){
//m_write();
sum++;
m_add();
}
//m_write();
ans=(sum-1)%6;
if (ans==0) puts("0");
else if (ans==1) puts("2");
else if (ans==2) puts("4");
else if (ans==3) puts("8");
else if (ans==4) puts("16");
else if (ans==5) puts("32");
return 0;
}
```
### Susu[计算几何+DP]
素素是个好人，自从上次木木的考验后，他下定决心重新面对生活。
这回，他打算给木木买一些小礼物。礼物有点小奇葩——要用箭来射。
在一个二维平面上有许多礼物(可以视为点)，每个礼物具有两个属性，分值value和倍率mul。素素射出的箭是一条无限长的直线形区域（碉堡了。。。），可以视为两条倾斜角为α的平行线之间的区域，平行线之间的距离可以为任意值，如下图所示：
蓝色部分上下两条长边之间就是这支箭的攻击范围，在蓝色范围内的礼物(红点)属于该此被击中的礼物，如果一个礼物刚好在边界上也视为被击中。礼物击中以后就会消失，每次发射箭得到分值是该次击中礼物的分值和乘上这些礼物平均的倍率，设该次击中的礼物集合为S，则分值计算公式为:
Score = SUM{value[i] | i 属于 S} \* SUM{mul[i] | i 属于 S} / |S|
其中|S|表示S的元素个数。素素将会使用若干支箭，直到把所有礼物全部击中。任意两次攻击的范围均不重叠。最后得到的分值为每次攻击分值之和。现在请你计算出能够得到的最大分值。
首先我们对数据进行处理
发现在题目所给斜率下，有些礼物是绑定在一起必须选择的，所以我们可以将其物品数量价值倍数累加
然后我们选取时，需要将某些礼物一起选出，但是我们必须选择相连的区间
所以我们需要对其离散化
然后线性DP
dp[i]=fmax(dp[i],dp[j]+(point[j+1~i])\*(bei[j+1~i])/(num[j+1~i]));
最后求出最大值
关键是斜率的处理
当alpha=0或180时，他都是一条和x轴平行的直线
当alpha=90时，他都是一条和x轴垂直的直线
当alpha<90时，可以直接进行tan处理
当alpha>90时，可以算出180-alpha的角度，转化为锐角处理
```cpp
#include<cstdio>
#include<cmath>
#include<algorithm>
#define fmax(a,b) ((a)>(b)?(a):(b))
using namespace std;
const double EPS=1e-8;
struct node{
long long x,y;
long long point,bei;
double zero;
}e[2010];
long long n,m,a,sump[2010],sumb[2010],sums[2010],ay[2010],ap[2010],ab[2010],as[2010];
double dp[2010],az[2010];
inline long long v_in(){
char ch=getchar();
long long sum=0,f=1;
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
sum=(sum<<3)+(sum<<1)+(ch^48);
ch=getchar();
}
return sum*f;
}
bool cmp1(const node &a,const node &b){
return a.y<b.y;
}
bool cmp2(const node &a,const node &b){
return a.x<b.x;
}
bool cmp3(const node &a,const node &b){
return a.zero<b.zero;
}
int main(){
freopen("Susu.in","r",stdin);
freopen("Susu.out","w",stdout);
n=v_in();
for (register long long i=1;i<=n;i++){
e[i].x=v_in();
e[i].y=v_in();
e[i].point=v_in();
e[i].bei=v_in();
}
a=v_in();
if (a==0||a==180){
sort(e+1,e+n+1,cmp1);//按照y排序
ay[1]=e[1].y;
ap[1]=e[1].point;
ab[1]=e[1].bei;
as[1]=1;
m=1;
for (register long long i=2;i<=n;i++)
if (e[i].y==ay[m]){
ap[m]+=e[i].point;
ab[m]+=e[i].bei;
as[m]++;
}
else{
ay[++m]=e[i].y;
ap[m]=e[i].point;
ab[m]=e[i].bei;
as[m]=1;
}
}
else if (a==90){
sort(e+1,e+n+1,cmp2);//按照x排序
ay[1]=e[1].x;
ap[1]=e[1].point;
ab[1]=e[1].bei;
as[1]=1;
m=1;
for (register long long i=2;i<=n;i++)
if (e[i].x==ay[m]){
ap[m]+=e[i].point;
ab[m]+=e[i].bei;
as[m]++;
}
else{
ay[++m]=e[i].x;
ap[m]=e[i].point;
ab[m]=e[i].bei;
as[m]=1;
}
}
else{//按照倾斜直线在y轴上的位置排序
double tana=tan(((double)a/180)*3.1415926);
//printf("%lf\n",tana);
for (register long long i=1;i<=n;i++){
e[i].zero=(double)e[i].y-((double)e[i].x*tana);
//printf("%lf %lf %lf\n",e[i].zero,(double)e[i].y,(double)e[i].x*tana);
}
sort(e+1,e+n+1,cmp3);
az[1]=e[1].zero;
ap[1]=e[1].point;
ab[1]=e[1].bei;
as[1]=1;
m=1;
for (register long long i=2;i<=n;i++)
if (e[i].zero-az[m]<EPS&&e[i].zero-az[m]>-EPS){
ap[m]+=e[i].point;
ab[m]+=e[i].bei;
as[m]++;
}
else{
az[++m]=e[i].zero;
ap[m]=e[i].point;
ab[m]=e[i].bei;
as[m]=1;
}
}
for (register long long i=1;i<=m;i++){
sump[i]=sump[i-1]+ap[i];
sumb[i]=sumb[i-1]+ab[i];
sums[i]=sums[i-1]+as[i];
//printf("%lld %lld %lld\n",ap[i],ab[i],as[i]);
}
for (register long long i=1;i<=m;i++)
for (register long long j=0;j<i;j++)
dp[i]=fmax(dp[i],dp[j]+(double)((sump[i]-sump[j])*(sumb[i]-sumb[j]))/(sums[i]-sums[j]));
//for (int i=1;i<=m;i++) printf("%.3lf\n",dp[i]);
printf("%.3lf\n",dp[m]);
return 0;
}
```
### Ssjmm[SPFA+DP]
今日阳光明媚，又迎来了素素和木木的固定约会时间。
奇葩的是，他们这次选择了一个奇怪的森林，并且木木能够确定物质的密度，素素要在木木的控制下达到终点与她相见。
因为能够控制密度，所以木木能够制造白洞和黑洞，并可以随时改变它们。木木在山上设置了一些白洞或黑洞，由于引力的影响，给素素带来了很大的麻烦。于是他决定找出一条消耗体力最少的路，来方便进出。已知山上有N个路口(编号1..N)，每个路口都被木木设置了一定质量白洞或者黑洞。原本在各个路口之间有M条单向路，走过每一条路需要消耗一定量的体力以及1个单位的时间。由于白洞和黑洞的存在，走过每条路需要消耗的体力也就产生了变化，假设一条道路两端路口黑白洞的质量差为delta：
从有白洞的路口走向有黑洞的路口，消耗的体力值减少delta，若该条路径消耗的体力值变为负数的话，取为0。
从有黑洞的路口走向有白洞的路口，消耗的体力值增加delta。
如果路口两端均为白洞或黑洞，消耗的体力值无变化。
由于光是放置黑洞白洞不足以体现木木的牛逼，所以她决定每过1个单位时间，就把所有路口的白洞改成黑洞，黑洞改成白洞。当然在走的过程中你可以选择在一个路口上停留1个单位的时间，如果当前路口为白洞，则不消耗体力，否则消耗s[i]的体力。现在请你帮可怜的素素计算从路口1走到路口N最小的体力消耗。保证一定存在道路从路口1到路口N。
两边之间的距离为
fmax(0,dis[from][to]+(f[from]-f[to])\*(fmax(w[from]-w[to],w[to]-w[from])));
对没错他就是这样表示的。
然后呢，我们首先将起点的等待一个单位时间的值算出
然后算出所有相邻点的最小值
然后所有相邻点算出等待一秒的时间
当然要注意白洞等待不需要体力
然后和SPFA一样跑
```cpp
#include<cstdio>
#define MAXN 2147000000
#define fmax(a,b) ((a)>(b)?(a):(b))
#define fmin(a,b) ((a)<(b)?(a):(b))
struct edge{
long long to,val,next;
}e[30010];
long long n,m,len;
long long f[5010],w[5010],s[5010],dis[2][5010],vis[5010],q[5010],head[5010];
inline long long v_in(){
char ch=getchar();
long long sum=0;
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9'){
sum=(sum<<3)+(sum<<1)+(ch^48);
ch=getchar();
}
return sum;
}
inline void addedge(long long u,long long v,long long w){
e[++len].to=v;
e[len].val=w;
e[len].next=head[u];
head[u]=len;
}
int main(){
freopen("Ssjmm.in","r",stdin);
freopen("Ssjmm.out","w",stdout);
n=v_in();
m=v_in();
for (register long long i=1;i<=n;i++) f[i]=v_in();
for (register long long i=1;i<=n;i++) w[i]=v_in();
for (register long long i=1;i<=n;i++) s[i]=v_in();
for (register long long i=1;i<=m;i++){
long long u=v_in(),v=v_in(),w=v_in();
addedge(u,v,w);
}
dis[0][1]=0;
dis[1][1]=s[1];
for (register long long i=2;i<=n;i++) dis[0][i]=dis[1][i]=MAXN;
long long hd=0,tl=1;
vis[1]=true;
q[1]=1;
while (hd!=tl){
if (++hd>n) hd=1;
long long u=q[hd];
if (f[u]){
dis[0][u]=fmin(dis[0][u],dis[1][u]);
dis[1][u]=fmin(dis[1][u],dis[0][u]+s[u]);
}
else{
dis[0][u]=fmin(dis[0][u],dis[1][u]+s[u]);
dis[1][u]=fmin(dis[1][u],dis[0][u]);
}
for (register long long i=head[u];i!=0;i=e[i].next){
long long v=e[i].to;
long long dist1=fmax(0,e[i].val+(f[u]-f[v])*(fmax(w[u]-w[v],w[v]-w[u])));//这是没有反过来的边权
long long dist2=fmax(0,e[i].val-(f[u]-f[v])*(fmax(w[u]-w[v],w[v]-w[u])));//这是颠倒后的边权
if (dis[1][v]>dis[0][u]+dist1){
dis[1][v]=dis[0][u]+dist1;
if (!vis[v]){
vis[v]=true;
if (++tl>n) tl=1;
q[tl]=v;
}
}
if (dis[0][v]>dis[1][u]+dist2){
dis[0][v]=dis[1][u]+dist2;
if (!vis[v]){
vis[v]=true;
if (++tl>n) tl=1;
q[tl]=v;
}
}
}
vis[u]=false;
}
printf("%I64d\n",fmin(dis[0][n],dis[1][n]));
return 0;
}
```
因为是在windows系统下评测的，所以%lld都换成了%I64d。
所以今天AK了，就很皮。
### 2.然后呢要准备以下这个星期的任务
就是搜索。
我想呢，应该就是剪枝之类的需要看看。
### 3.转载了一些文章
[A\*](https://www.luogu.org/blogAdmin/article/edit/18906)
[动态树](https://www.luogu.org/blogAdmin/article/edit/18902)
[cdq分治](https://www.luogu.org/blogAdmin/article/edit/18901)
### 4.今天晚上任务
<<数学一本通>>要开始看了。争取两天内看完第一章数论吧。