...

二分答案bug多成狗。。果然蒟蒻。。积分500+留念。。

改天补一波kmp

总算搞出了stl双logn的做法。。。洛谷上的数据比这要科学，这里没有重复的一开始第一问求下降子序列也对了。。。

孙杨洋的打表呢

写字符串写到怀疑自己是否学过oi…不知道调了几个小时sad

倍增写劣了啊..跳到同一深度的时候把x和y搞混了...
调试了一下午+一晚上..
中午来机房终于A了..

回复 @kZime : 大佬第二问的dp想法果然比蒟蒻的贪心不知道高到哪里去了%%%

浮点01Trie + 动态凸包 + 三分跑得很慢。。。O(64NlogN)最后两个点2.5s。。。不过代码3k 100行

两个oj上的无解输出竟然不是同样的。。。因为这个被坑了两回。。。尬

考试30分，回头看到正解感觉好简单

教你重新做人…

明明输出答案是对的 非要W 求助
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
#define road 10000+10
#define node 1000+10
struct Edge
{
int x,y,z,next;
Edge(int x=0,int y=0,int z=0,int next=0):
x(x),y(y),z(z),next(next){}
}edge[road];
struct date
{
int x,g,h;
bool operator < (const date &a) const
{
return g+h>a.g+a.h;
}
};
int nl,m,k,x,y,z,sumedge,s,e,size;
int head[node],ans[100+10],dis[node],cnt[node];
bool vis[node];
int add(int x,int y,int z)
{
edge[++sumedge]=Edge(x,y,z,head[x]);
return head[x]=sumedge;
}
void spfa()
{
queue <int> q;
memset(dis,127/3,sizeof(dis));
dis[s]=0;vis[s]=1;q.push(s);
while(!q.empty())
{
int now=q.front();q.pop();
vis[now]=0;
for(int i=head[now];i;i=edge[i].next)
{
int to=edge[i].y;
if(dis[to]>dis[now]+edge[i].z)
{
dis[to]=dis[now]+edge[i].z;
if(!vis[to])
{
vis[to]=1;
q.push(to);
}
}
}
}
}
void Astar()
{
priority_queue <date> qq;
qq.push((date){e,0,dis[e]});
while(!qq.empty())
{
date nn=qq.top();qq.pop();
++cnt[nn.x];
if(cnt[nn.x]>k)continue;
if(nn.x==s){
ans[++size]=nn.g;
}
if(cnt[s]==k){
return;
}
for(int i=head[nn.x];i;i=edge[i].next)
{
qq.push( (date){edge[i].y,nn.g+edge[i].z,dis[edge[i].y]});
}
}
return;
}
int main()
{
// freopen("cowjog.in ","r",stdin);
// freopen("cowjog.out","w",stdout);
scanf("%d%d%d",&nl,&m,&k);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
if(x<y)swap(x,y);
add(x,y,z);
}
s=1;e=nl;
spfa();
memset(ans,-1,sizeof(ans));
Astar();
for(int i=1;i<=k;i++)
printf("%d\n",ans[i]);
return 0;
}

我用了一种完全不对的树规过了9个点...可怕

回复 @MayLava :
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define N 100010
#define lowbit ( (i) & (-i) )
#define LL long long
using namespace std;
struct point{
int x,y;
void read(){scanf("%d%d",&x,&y);}
}p[N];
struct seg{
int h1,h2,h3,flag;
seg() {}
seg(int x,int y,int z,int a):h1(x),h2(y),h3(z),flag(a) {}
}s[N];
int tree[N],n,tot,sz,sub[N];
void Insert(int pos,int num){for(int i=pos;i<N;i+=lowbit)tree[i]+=num;}
int Query(int pos){int sum(0);for(int i=sum;i;i-=lowbit)sum+=tree[i];return sum;}
int find(int x){
return lower_bound(sub+1,sub+sz+1,x)-sub;
}
void link(int ff,int l,int r,int h){//0横线，//1竖线
if(!ff){
s[++tot]=seg(find(l),find(r),h,0);
}else {
int X=find(h);
s[++tot]=seg(X,X,l,1);
s[++tot]=seg(X,X,r,-1);
}
}
bool comp(const point & a,const point & b){return a.x==b.x?a.y<b.y:a.x<b.x;}
bool Comp(const point & a,const point & b){return a.y==b.y?a.x<b.x:a.y<b.y;}
bool COMP(const seg & a,const seg & b){
if(a.h3!=b.h3)return a.h3<b.h3;
return a.flag<b.flag;
}
void build(){
sort(p+1,p+n+1,comp);
for(int i=2;i<=n;++i)
if(p[i].x==p[i-1].x)
link(1,p[i-1].y,p[i].y,p[i].x);
sort(p+1,p+n+1,Comp);
for(int i=2;i<=n;++i)
if(p[i].y==p[i-1].y)
link(0,p[i-1].x,p[i].x,p[i].y);
sort(s+1,s+tot+1,COMP);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)p[i].read(),sub[++sub[0]]=p[i].x;
sort(sub+1,sub+sub[0]+1);
sz=unique(sub+1,sub+sub[0]+1)-sub-1;
build();LL Ans(0);
for(int i=1;i<=tot;++i){
if(!s[i].flag)Ans+=Query(s[i].h2)-Query(s[i].h1-1);
else {
Insert(s[i].h1,s[i].flag);
}
}cout<<Ans;
return 0;
}

w了一个点..

暴力rank1

陷入LCA的错解中……

终于过了..........

回复 @COGS再见 :
自我检讨