三角
有一个三角，n层每层有n个点，第i层第j个点可以走到第i+1层第j和j+1个点。
每个点有一个权值，从第一层逐层走到第n层为1中路径，路径权值为经过的点权和。
求权值前k大的路径并输出方案。
n,k,w<=1000
题解
首先对于每个点求出从该点出发到第n层的最大路径和。
二分第k条路径的权值，因为二分的权值越小，满足条件的越多。
然后再输出即可，搜索有剪枝。
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1005;
int n,k,a[maxn][maxn];
int tot,f[maxn][maxn];
char path[maxn];
bool opt;
template<class T>inline void read(T &x){
x=0;int f=0;char ch=getchar();
while(!isdigit(ch)) {f|=(ch=='-');ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x = f ? -x : x ;
}
void dfs(int x,int y,int sum,int lim){
if(tot>=k) return ;
if(sum+f[x][y]<lim) return ;
if(x==n){
tot++;
if(opt){
for(int i=1;i<n;i++)
printf("%c",path[i]);
putchar(10);
}
return ;
}
path[x]='L';
dfs(x+1,y,sum+a[x][y],lim);
path[x]='R';
dfs(x+1,y+1,sum+a[x][y],lim);
}
int main(){
freopen("tri.in","r",stdin);
freopen("tri.out","w",stdout);
read(n);read(k);
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
read(a[i][j]);
for(int i=n;i;i--)
for(int j=1;j<=i;j++)
f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
int l=0,r=1000*1000,ans;
while(l<=r){
int mid=(l+r)>>1;
tot=0;
dfs(1,1,0,mid);
if(tot>=k) ans=mid,l=mid+1;
else r=mid-1;
}
opt=true;
tot=0;
dfs(1,1,0,ans);
}
/*
3 3
1
1 100
2 1 1
*/
tri
C++锦标赛
给出n个的得分e和打败他们消耗的rp值p，现在需要一个一个和他们比赛，可以选择打赢或者不打赢。胜者得分+1，败者得分不变。
最后按照得分排名，如果得分相同，如果那个人被打败了就排在后面，否则排在前面。初始得分为0，求最少花多少rp值可以到前k名。
T<=50,1<=n<=2333,1<=k<=n+1,1<=e,p<-2e6
题解
一开始想成了直接选人打，那样就只有自己得分加。
对于50%的数据：
暴力搜索，枚举每个人是否打赢，最后判断打赢的打标记，没打赢的得分++，然后排序（得分为第一关键字，标记为第二关键字），能够到前k名就是得分比第k名大或者（相同&&第k名被打败），然后更新答案。复杂度(T2^n nlogn)
正解：
先把无解和不用打的情况特判。对于无解就是打完所有人得分为n，但是有至少k个人得分大于n。
记按得分排序后的第k名得分为score，所以至少要得到score的分，
考虑上界是什么：当得分为score+2时，即使所有人得分+1，那么第k名也不会造成影响，所以一定是前k名。
求rp消耗：
当得分为score+2时：可以知道只要达到分数即可，不用考虑打赢谁，所以找出消耗rp最小的score+2个人即可。
当得分为score+1时：记k名及其之后得分为score的人的个数为tot，假设到达分数但是没打赢任何人，那么现在的排名为k+tot，所以要打赢tot个人，考虑有哪些人打赢有贡献：原来得分为score的，打赢之后他们就不会+1；得分为score+1的，打赢之后他们就排在同分段后面。所以过程就是先找出得分为score和score+1的人里面消耗最小的tot个，如果得分没到score+1就找消耗小的达到分数为止（当然要没打过）。
当得分为score时: 记k名及其之后得分为score的人的个数为num1,得分为score-1的人数为num2，按照上面的假设排名会是k+num1+num2，所以要打赢num1+num2个人。剩下的分析同上，在得分为score和score-1里面找即可。
考虑如果在某个方案得分达不到要求的得分有没有影响，如果达不到要求将会返回打败所有人的消耗，但是既然开始寻找方案就说明三个方案至少有一个可以，而且这一个消耗<=打完所有人的消耗，所以没有影响。时间复杂度O(Tnlogn)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn=2350;
const int inf=2000001;
int t,n,k;
int tot,score;//tot:k名之后与第k名同分的
bool ok[maxn];
struct person{
int val,w;
}a[maxn];
template<class T>inline void read(T &x){
x=0;int f=0;char ch=getchar();
while(!isdigit(ch)) {f|=(ch=='-');ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x = f ? -x : x ;
}
bool cmp(person a,person b){return a.w<b.w;}
bool cmp1(person a,person b){return a.val>b.val;}
bool no_answer(){
int cnt=0;
for(int i=1;i<=n;i++)
cnt+=a[i].val>n;//打败所有人也超不过他们
return cnt>=k;
}
ll plana(){//最后分数为score+2
//只需要达到这个分就能确保在前k
ll ret=0;
for(int i=1;i<=score+2;i++) ret+=a[i].w;
return ret;
}
ll planb(){//最后分数为score+1
//干掉tot个分为score和score+1并且达到score+1分
memset(ok+1,false,sizeof(ok));
int num=tot,cnt=score+1;
ll ret=0;
for(int i=1;i<=n&#i++)
if(a[i].val==score||a[i].val==score+1){
num--;cnt--;
ret+=a[i].w;
ok[i]=true;
}
for(int i=1;i<=n&&cnt>0;i++)
if(!ok[i]){
cnt--;
ret+=a[i].w;
ok[i]=true;
}
return ret;
}
ll planc(){//最后分数为score
memset(ok,false,sizeof(ok));
int num=tot,cnt=score;
//分数为score和score-1的人会有影响
ll ret=0;
for(int i=1;i<=n;i++)
if(a[i].val==score-1) num++;
for(int i=1;i<=n&#i++)
if(a[i].val==score||a[i].val==score-1){
num--;cnt--;
ret+=a[i].w;
ok[i]=true;
}
for(int i=1;i<=n&&cnt>0;i++)
if(!ok[i]){
cnt--;
ret+=a[i].w;
ok[i]=true;
}
return ret;
}
void solve(){
read(n);read(k);tot=0;
for(int i=1;i<=n;i++){read(a[i].val);read(a[i].w);}
if(k==n+1) {printf("0\n");return ;}
if(no_answer()) {printf("-1\n");return ;}
sort(a+1,a+n+1,cmp1);
score=a[k].val;
while(a[k].val==a[k+tot].val) tot++;
sort(a+1,a+n+1,cmp);
printf("%lld\n",min(min(plana(),planb()),planc()));
}
int main(){
freopen("tournament.in","r",stdin);
freopen("tournament.out","w",stdout);
read(t);
while(t--) solve();
}
/*
3
2 2
1 2
2 0
2 2
1 2
2 0
2 2
1 2
2 0
*/
tournament
ZGY的早餐
给出一个n个点m条边的图，q个询问，从s出发经过h到达t的最短路径长度。
对于50%的数据，n<=200,m<=250000,q<=100000,图联通
剩下的50%的数据，n<=100000,m<=250000,q<=100000,图联通无环
w<=1000000
题解
这好像是最简单的一个，对于50%的数据直接$O(n^2logn)$的Dijkstra就好了，ans=dis[h][s]+dis[h][t]
剩下的可以发现联通无环不就是树吗，所以两点距离直接$O(logn)$求就好了
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int maxo=1005;
const int maxn=100005;
const int maxm=250005;
int t,n,m,q;
int cnt,head[maxn];
int timer,vis[maxn];
ll dis[maxo][maxo];
struct node{
ll dis;
int id;
bool operator < (const node x)const {return x.dis<dis;}
};
struct edge{
int x,y,val,next;
}e[maxm<<1];
template<class T>inline void read(T &x){
x=0;int f=0;char ch=getchar();
while(!isdigit(ch)) {f|=(ch=='-');ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x = f ? -x : x ;
}
void add(int x,int y,int val){
e[++cnt]=(edge){x,y,val,head[x]};
head[x]=cnt;
}
void dijskal(int s){
++timer;
priority_queue<node> q;
while(!q.empty()) q.pop();
memset(dis[s],0x3f3f3f,sizeof(dis[s]));
dis[s][s]=0;
q.push((node){0,s});
while(!q.empty()){
int x=q.top().id;
q.pop();
if(vis[x]==timer) continue;
vis[x]=timer;
for(int i=head[x];i;i=e[i].next){
int y=e[i].y;
if(dis[s][y]>dis[s][x]+e[i].val){
dis[s][y]=dis[s][x]+e[i].val;
q.push((node){dis[s][y],y});
}
}
}
}
void plana(){
for(int i=1;i<=n;i++)
dijskal(i);
read(q);
while(q--){
int st,h,ed;
read(st);read(h);read(ed);
printf("%lld\n",dis[h][st]+dis[h][ed]);
}
}
int dep[maxn],fa[maxn][25];
ll sum[maxn];
void dfs(int x){
for(int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=e[i].next){
int y=e[i].y;
if(y==fa[x][0]) continue;
fa[y][0]=x;
dep[y]=dep[x]+1;
sum[y]=sum[x]+e[i].val;
dfs(y);
}
}
int lca(int x,int y){
if(dep[x]>dep[y]) swap(x,y);
int delt=dep[y]-dep[x];
for(int i=0;delt;i++,delt>>=1)
if(delt&1) y=fa[y][i];
if(x==y) return x;
for(int i=20;fa[x][0]!=fa[y][0];i--)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
ll query(int x,int y){
return sum[x]+sum[y]-2*sum[lca(x,y)];
}
void planb(){
dfs(1);
read(q);
while(q--){
int st,h,ed;
read(st);read(h);read(ed);
printf("%lld\n",query(st,h)+query(h,ed));
}
}
int main(){
freopen("mindis.in","r",stdin);
freopen("mindis.out","w",stdout);
read(t);read(n);read(m);
for(int i=1;i<=m;i++){
int x,y,val;
read(x);read(y);read(val);
add(x,y,val);
add(y,x,val);
}
if(t<=5) plana();
else planb();
}
/*
10 5 4
1 2 3
1 3 6
2 4 5
2 5 10
*/
mindis