2019-10-17

T1

一道前缀和就可以暴打的题目。。没有什么可说的
就是注意因为开了$long$long $long$long输出的时候 是输出$lld$lld
我好难受啊 开了$long$long $long$long 输出错了 草

#include <cstdio>
#include <iostream>
#include <cstring>
#define int long long 
using namespace std;
const int maxn=150010;
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')	f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int n,m,sum[maxn],weight,a[maxn],ans,l,r;
signed main()
{
//	freopen("ticket.in","r",stdin);
//	freopen("ticket.out","w",stdout);
	n=read();m=read();sum[0]=0;
	for(int i=1;i<=m-1;i++)
		a[i]=read(),sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=n;i++)
	{
		l=read();r=read();weight=read();
		ans=ans+(sum[r-1]-sum[l-1])*weight;
	}
	printf("%lld",ans);
	return 0;
}

T2

哎这道题真的是，知道了结论，打最长上升序列打了好久哦。（在此疯狂批评某贪心+动规打最长上升序列的方法）这道题比较适合于用树状数组打最长上升序列
首先来分析这道题来转化 经过观察我们发现，若要保证$i=pos[i]$i=pos[i]，对于任意$i,j$i,j 必须要同时满足以下三个条件：
$1. i<j$1.i<j
$2.a[i]<a[j]$2.a[i]<a[j]
$3.a[j]-a[i]\le j-i$3.a[j]−a[i]≤j−i 这个条件是为了限制形如：$19$19这样的数连在一起的情况
然后条件3可以转化为：$i-a[i]\le j-a[j]$i−a[i]≤j−a[j]
这显然是个$nlog^2n$nlog2n的三维偏序 于是就有大佬打的cdq分治。
而像我这样的蒟蒻只顾着分析什么情况下是不满足提议的 然后分析出以上条件的反面后 我就一脸懵逼了 因为以上条件的反面是1条件必须满足 2，3条件任一满足。。。这并不是三维偏序 于是我就可怜暴力了30pts了（蒟蒻哭泣）
但是显然cdq分治一般都不是正解（形如分块，莫队。这些算法一般都是在非正解的情况下那尽量多的分，而并非正解）
所以正解是什么呢？（其实就算我现在知道了我以后遇到类似的题也不会啊)
将条件3转换一下（两边同时乘$-1$−1) 就可以得到$i-j\le a[i]-a[j]$i−j≤a[i]−a[j]
将条件2转换一下（移项）就可以得到 $a[i]-a[j]<0$a[i]−a[j]<0
结合条件2，3可以得到$i-j<0$i−j<0 然后就会惊奇的发现：这难道不就已经满足条件1了吗！（所以说出题人是怎么想到转换一下的？）
所以我们只需要满足条件$2,3$2,3就行了！
我们先以$i-val(i)$i−val(i)为关键字进行升序排序，在$i-val(i)$i−val(i)相等时，以$val(i)$val(i)为关键字进行升序排序 接下来我们所需要处理的问题就是以$val(i)$val(i)为下标的 最长严格上升子序列了

#include <bits/stdc++.h>
using namespace std;
inline int getint() {
    int x=0, c=getchar();
    for(; c<48||c>57; c=getchar());
    for(; c>47&&c<58; x=x*10+c-48, c=getchar());
    return x;
}
int c[200005], mx, n, tot;
void upd(int x, int g) {
    for(; x<=mx; x+=x&-x) {
        c[x]=max(c[x], g);
    }
}
int sum(int x) {
    int y=0;
    for(; x; x-=x&-x) {
        y=max(y, c[x]);
    }
    return y;
}
struct dat {
    int i, a;
}a[100005];
inline bool cmp(const dat &a, const dat &b) {
    return a.i==b.i?a.a<b.a:a.i<b.i;
}
int main() {
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
    n=getint();
    for(int i=1; i<=n; ++i) {
        int w=getint();
        if(i<w) {
            continue;
        }
        ++tot;
        a[tot].i=i-w;
        a[tot].a=w;
        mx=max(mx, w);
    }
    sort(a+1, a+1+tot, cmp);
    int ans=0;
    for(int i=1; i<=tot; ++i) {
        int d=1+sum(a[i].a-1);
        upd(a[i].a, d);
        ans=max(ans, d);
    }
    printf("%d\n", ans);
    return 0;
}

其实我刚刚想了一下 如果是用贪心+dp的方法进行最长严格上升子序列 好像也是可以的 因为在按照某种顺序排好序以后 本质上已经满足了一类偏序 接下来就只需要对另一类偏序进行这种进行这种算法就行了 而需要注意的就是之前所说的以$val(i)$val(i)为下标了 其实这个下标只是指在树状数组里面的下标 而非用贪心+dp方法里面的下标 贪心+dp里面的下标就是$1$1 ~ $tot$tot。

T3

因为放在的是T3的位置 所以我有必要分析一下其暴力算法！（70也是很客观的分数）
考虑第$5tps$5tps的数据 $x_i==y_i$xi​==yi​ 显然答案为$x_n-x_1$xn​−x1​
考虑第$30pts$30pts的数据 对于每个点都与其他点暴力建边 边权为$min(|x_i-x_j|,|y_i-y_j|)$min(∣xi​−xj​∣,∣yi​−yj​∣) 然后跑一边dijkstra
考虑另外$35pts$35pts的数据 $x_i,y_i$xi​,yi​均单调不减。 对于一队单调不降的点对来说 任意$i,k$i,k两点之间若有一点$j$j存在，那么$i$i到$k$k的$x$x或者$y$y路径必定可以中途经过点$j$j，且经过该点不会使得走的路径更长 因此选了$j$j只有可能使得走过的路径更优
因此对于该$30pts$30pts的分来说 贪心策略就是所有点都选。
（可怜蒟蒻以为贪心策略是只选$1,n$1,n点，发现不对就果断放弃了）
至此 已经可以拿$70tps$70tps了。。
（所以辛辛苦苦想正解就只是为了那剩下的$30pts$30pts罢了）
首先分析 如果每个点都向其余点连边 边的数量为$n*(n-1)$n∗(n−1)，显然爆空间
于是考虑如何玄学建图。 因为这些点都是在平面直角坐标系上 所以按照升序或者降序排列$x$x和$y$y，然后只连接$x_i,x_{i+1}$xi​,xi+1​和$y_i,y_{i+1}$yi​,yi+1​ 你就会发现 所有点之间的横纵坐标距离 都可以被我们连的这些边代替 如下图：

$x_3-x_1=(x_2-x_1)+(x_3-x_2)$x3​−x1​=(x2​−x1​)+(x3​−x2​) 因此我们没有必要连接$1,3$1,3号点 他们可以由（类似于最小单位的距离）代替
这样建边我们就省了很多空间了！
现在来解决$min(|x_i−x_j|,|y_i−y_j|)$min(∣xi​−xj​∣,∣yi​−yj​∣)的问题 我们需要求1到n号点最短距离， 而$min(|x_i−x_j|,|y_i−y_j|)$min(∣xi​−xj​∣,∣yi​−yj​∣)实际上求的也是从i号点到j号点更近的走法,符合最短路算法的走法。所以我们可以把因此我们可以将i，j号点他们的x，y分别连边（如果他们的x，y在排序后是相邻的）
总而言之，将x升序排列，y升序排列 然后相邻$x,y$x,y建边，直接跑一边dij就可以ac此题了。其实这一点很好分析吧。

#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#define int long long
using namespace std;
const int maxn=200010;
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
struct node{
	int id,x;
}heng[maxn];
struct node1{
	int id,y;
}zong[maxn];
struct nodee
{
    int dis;
    int pos;
    bool operator <( const nodee &x )const
    {
        return x.dis < dis;
    }
};
priority_queue<nodee> q;
int first[maxn<<2],next[maxn<<2],to[maxn<<2],val[maxn<<2];
int n,a,b,tot,dis[maxn<<2],inque[maxn<<2];

void dij()
{
	int rp,des;
	dis[1]=0;
	q.push( ( nodee ){0, 1} );
	while(!q.empty())
	{
		nodee tmp=q.top();
		q.pop();
		int x=tmp.pos;int y=tmp.dis;
		if(inque[x])	continue;
		inque[x]=true;
		for(rp=first[x];rp;rp=next[rp])
		{
			des=to[rp];
			if(dis[des]>y+val[rp])
				dis[des]=y+val[rp];
			if(inque[des]==false)
			{
				q.push( ( nodee ){dis[des], des} );
			}
		}
	}
}

void add(int x,int y,int z)
{
	tot++;
	next[tot]=first[x];
	first[x]=tot;
	to[tot]=y;
	val[tot]=z;
}

inline bool cmp(node cxk,node qbl) 
{
	return cxk.x<qbl.x || (cxk.x==qbl.x && cxk.id<qbl.id);
}
inline bool cmpl(node1 cxk,node1 qbl) 
{
	return cxk.y<qbl.y || (cxk.y==qbl.y && cxk.id<qbl.id);
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++)
		dis[i]=0x7fffffff;
	for(int i=1;i<=n;i++)
	{
		a=read();b=read();
		heng[i].x=a;heng[i].id=i;zong[i].y=b;zong[i].id=i;		
	}
	sort(zong+1,zong+1+n,cmpl);
	sort(heng+1,heng+1+n,cmp);
	for(int i=2;i<=n;i++)
	{
		add(zong[i-1].id,zong[i].id,zong[i].y-zong[i-1].y);
		add(zong[i].id,zong[i-1].id,zong[i].y-zong[i-1].y);
		add(heng[i-1].id,heng[i].id,heng[i].x-heng[i-1].x);
		add(heng[i].id,heng[i-1].id,heng[i].x-heng[i-1].x);
	}
	dij();
	return printf("%lld",dis[n]), 0;
}

总结

今天的考试不是很难（对于本蒟蒻来说太难了） T2 T3 都属于想到了思路 就很好做的题 但是如果想不出来 暴力也可以获得可观的分数！