191017

191017

T1:补票

企鹅国最近开通了高铁，高铁一共有M站（站台编号从1到M），第i站和第i+1站之间的距离是Ai。
由于正值暑假有不少企鹅购票乘坐高铁，但是也有一些没有买票的企鹅也溜上了列车。在一轮查票之后，找出了N只没有购票的企鹅，第i只企鹅在Si站上车，Ti站下车，体重为Wi。
企鹅国的高铁票价机制为，对于一只需要乘坐距离L，体重W的企鹅，高铁票价为L×W。 现在你需要计算出这N只企鹅一共需要花多少钱补票？

其实就是一道氵题，但需要注意开long long不然就只有70分了。

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
ll read()
{ll x=0,f=1;char ch;while(ch>'9'||ch<'0'){if(ch=='-')	f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return f*x;
}
ll s[N],ans,str,end,w,n,m;
int main()
{//freopen("ticket.in","r",stdin);//freopen("ticket.out","w",stdout);n=read();m=read();for(ll i=1;i<m;i++)	s[i]=read()+s[i-1];for(ll i=1;i<=n;i++){str=read();end=read();w=read();ans+=(s[end-1]-s[str-1])*w;}printf("%lld",ans);return 0;
}

T2：删数字

企鹅豆豆拿到一列数字（我也不知道他怎么拿到的），这些数字很乱，他看着很不爽，于是他准备删掉一些数字，使得剩下的数字尽可能多的数字满足从左往右第i 个数字的值是i。
你需要告诉他最多能有多少个数字满足如上条件？

考试时，我连暴力都没想到，就用了个rand随机输出，没想到还贪了10分

暴力:直接枚举每一种删数的情况，能得30pts，也是很可观的分数。

正解：满足题目所给要求，存在于最后的序列中的数必定满足i<j,a[i]<a[j],a[i]-i>=a[j]-j，然后由a[i]-i>=a[j]-j可得a[i]-a[j]>=i-j，再由a[i]<a[j]，所以i<j。把a[i]看作新的下标，这就是个最长不严格上升子序列问题。可以用树状数组来储存和查询。

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
int read()
{int x=0,f=1;char ch;while(ch>'9'||ch<'0'){if(ch=='-')	f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return f*x;
}
vector<int>v[N];
int f[N],n,x,tot,id,num,tree[N];
int lowbit(int i)
{return i&(-i);
}
void add(int x,int v)
{while(x<=n){tree[x]=max(tree[x],v);//x+=lowbit(x);}
}
int query(int n)
{int ans=0;while(n){ans=max(ans,tree[n]);///n-=lowbit(n);}return ans;
}
int main()
{n=read();for(int i=1;i<=n;i++){x=read();if(x>i)	continue;v[x].push_back(i-x+1);	/}for(int i=1;i<=n;i++){id=num;for(int j=0;j<v[i].size();j++)	f[++id]=query(v[i][j])+1;id=num;for(int j=0;j<v[i].size();j++)	add(v[i][j],f[++id]);num=id;}int ans=0;for(int i=1;i<=num;i++)	ans=max(ans,f[i]);printf("%d",ans);return 0;
}

T3：滑冰

传送门

这是一道最短路构图问题，由于两点间距离总是取x距离或y距离，则第i个点与第i+2个点连边等效于，第i个点连第i+1个点再连第i+2个点，因此，我们可以避免n²的建边，把大边都拆成小边，再把x和y两种情况分开建边，最后跑一次迪杰斯特拉即可。

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 200005
using namespace std;
int read()
{int x=0,f=1;char ch;while(ch>'9'||ch<'0'){if(ch=='-')	f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return f*x;
}
struct node
{int x,y,id;	
}d[N];
ll dis[10*N],ans;
int n,first[N],net[10*N],to[10*N],w[10*N],tot;
void add(int x,int y,int z)
{net[++tot]=first[x];first[x]=tot;to[tot]=y;w[tot]=z;
}
bool cmp1(const node &a,const node &b)
{return a.x<b.x;
}
bool cmp2(const node &a,const node &b)
{return a.y<b.y;
}
priority_queue<pair<int,int> >q;
int main()
{n=read();for(int i=1;i<=n;i++)	d[i].x=read(),d[i].y=read(),d[i].id=i;sort(d+1,d+1+n,cmp1);for(int i=1;i<n;i++){add(d[i].id,d[i+1].id,d[i+1].x-d[i].x);add(d[i+1].id,d[i].id,d[i+1].x-d[i].x);}sort(d+1,d+1+n,cmp2);for(int i=1;i<n;i++){add(d[i].id,d[i+1].id,d[i+1].y-d[i].y);add(d[i+1].id,d[i].id,d[i+1].y-d[i].y);}memset(dis,127,sizeof(dis));dis[1]=0;q.push(make_pair(0,1));while(!q.empty()){int u=q.top().second;q.pop();for(int e=first[u];e;e=net[e]){int v=to[e];if(dis[v]>dis[u]+w[e]){dis[v]=dis[u]+w[e];q.push(make_pair(-dis[v],v));}}}printf("%lld",dis[n]);return 0;
}