[BZOJ 2763]飞行路线
分层图最短路处女作TAT
很明显要求你求一个分层图上的最短路。不过没必要把分层图构出来，手写转移即可。还有卡SPFA是怎么回事？出题人你粗来我保证不打死你……
然而沉迷pb_ds，不能自拔。
代码：
/**************************************************************
Problem: 2763
User: danihao123
Language: C++
Result: Accepted
Time:268 ms
Memory:3136 kb
****************************************************************/
#include <cstdio>
#include <queue>
#include <algorithm>
#include <utility>
#include <cstring>
#include <cctype>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
const int maxn=10001,maxm=100001,maxk=11;
typedef pair<int,int> pii;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int graph_cnt=0;
inline void Add_Edge(int u,int v,int d){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
dist[graph_cnt]=d;
}
struct Node{
pii pnt;
int d;
bool operator <(const Node& x) const{
return d<x.d;
}
bool operator >(const Node& x) const{
return d>x.d;
}
};
typedef __gnu_pbds::priority_queue<Node,greater<Node> > Heap;
Heap::point_iterator ite[maxn][maxk];
Heap Q;
int n,k;
bool vis[maxn][maxk];
int d[maxn][maxk];
inline void relax(int u,int v,int di){
d[u][v]=di;
if(ite[u][v]!=0)
Q.modify(ite[u][v],(Node){make_pair(u,v),di});
else
ite[u][v]=Q.push((Node){make_pair(u,v),di});
}
int Dijkstra(int s,int t){
register int i,u,v;
pii temp;
memset(d,0x7f,sizeof(d));
d[s][0]=0;
ite[s][0]=Q.push((Node){make_pair(s,0),0});
while(!Q.empty()){
temp=Q.top().pnt;
Q.pop();
u=temp.first;
v=temp.second;
if(vis[u][v])
continue;
vis[u][v]=true;
for(i=first[u];i;i=next[i]){
if(v<k){
if(d[u][v]<d[to[i]][v+1]){
relax(to[i],v+1,d[u][v]);
}
}
if(d[u][v]+dist[i]<d[to[i]][v]){
relax(to[i],v,d[u][v]+dist[i]);
}
}
}
register int ans=0x7f7f7f7f;
for(i=0;i<=k;i++)
ans=min(ans,d[t][i]);
return ans;
}
int main(){
int m,s,t,u,v,d;
register int i;
scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
for(i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&d);
Add_Edge(u,v,d);
Add_Edge(v,u,d);
}
printf("%d\n",Dijkstra(s,t));
return 0;
}
[BZOJ 1878]HH的项链
扫描线处女作TAT
直接离线，按左端点排序扫描。每个点要保存后继相同节点，每种元素第一次出现的位置都加1。然后扫描的时候有后继就给后继加。之后求区间和即可。
代码：
/**************************************************************
Problem: 1878
User: danihao123
Language: C++
Result: Accepted
Time:1344 ms
Memory:8444 kb
****************************************************************/
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=50001,maxm=200001;
int T[maxn];
int n;
inline int lowbit(int x){
return x&(-x);
}
inline void update(int p,int v){
while(p<=n){
T[p]+=v;
p+=lowbit(p);
}
}
inline int query(int p){
register int ans=0;
while(p>0){
ans+=T[p];
p-=lowbit(p);
}
return ans;
}
struct Query{
int l,r;
int id;
int ans;
bool operator <(const Query& x) const{
return l==x.l?r<x.r:l<x.l;
}
};
Query Q[maxm];
bool cmp2(const Query& a,const Query& b){
return a.id<b.id;
}
// I/O优化
inline int readint(){
char c=getchar();
register int x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x;
}
int bf[10];
inline void writeint(int x){
register int p=0;
if(x==0){
bf[p++]=0;
}else{
while(x){
bf[p++]=x%10;
x/=10;
}
}
for(register int i=p-1;i>=0;i--)
putchar('0'+bf[i]);
}
int next[maxn];
int A[maxn];
int pos[1000001];
int main(){
int m,maxA=0;
register int i,j;
n=readint();
for(i=1;i<=n;i++){
A[i]=readint();
maxA=max(maxA,A[i]);
}
for(i=n;i;i--){
next[i]=pos[A[i]];
pos[A[i]]=i;
}
for(i=1;i<=maxA;i++)
if(pos[i])
update(pos[i],1);
m=readint();
for(i=1;i<=m;i++){
Q[i].l=readint();
Q[i].r=readint();
Q[i].id=i;
}
sort(Q+1,Q+1+m);
register int tot=1;
for(i=1;i<=m;i++){
while(tot<Q[i].l){
if(next[tot])
update(next[tot],1);
tot++;
}
Q[i].ans=query(Q[i].r)-query(Q[i].l-1);
}
sort(Q+1,Q+1+m,cmp2);
for(i=1;i<=m;i++){
writeint(Q[i].ans);
putchar('\n');
}
return 0;
}
[BZOJ 1441]Min
这个问题看似无从下手。
我们可以先取[tex]n=2[/tex]，然后你就发现你似乎要解[tex]A_{1}X_{1}+A_{2}X_{2}>0[/tex]，而且还要求[tex]S[/tex]最小？你想到了什么？扩展欧几里得？对头！
由扩欧推广可得答案就是所有数的最大公约数。
代码：
/**************************************************************
Problem: 1441
User: danihao123
Language: C++
Result: Accepted
Time:0 ms
Memory:820 kb
****************************************************************/
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int main(){
register int ans,i;
int n,temp;
scanf("%d",&n);
scanf("%d",&temp);
ans=abs(temp);
for(i=2;i<=n;i++){
scanf("%d",&temp);
ans=gcd(ans,abs(temp));
}
printf("%d\n",ans);
return 0;
}
[POJ 2388]Who's in the Middle
这题题面长得挺吓人的（英文……），不过就是让你求中位数……
我怀疑会有卡快排的数据，不过我用的是STL的sort（sort好像用的不是普通的快排）
代码：
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=10000;
int A[maxn];
int main(){
register int i;
int n;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&A[i]);
sort(A,A+n);
printf("%d\n",A[n>>1]);
return 0;
}
[CF 371B]Fox Dividing Cheese
狐狸的三种操作的实质是除二，除三，除五。由此我们可以猜想在最优策略下，两块蛋糕最后的重量应该是[tex]gcd(a,b)[/tex]。然后试除即可。
（大胆猜想，不用证明）
代码：
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a,int b){
if(!b)
return a;
else
return gcd(b,a%b);
}
static int P[3]={2,3,5};
inline int min_fj(int source,int direction){
register int i,ans=0;
source/=direction;
if(source==1)
return 0;
for(i=2;i>=0;i--){
while(source%P[i]==0){
source/=P[i];
ans++;
}
}
if(source==1)
return ans;
else
return -1;
}
int main(){
register int direction,t1,t2;
int a,b;
cin>>a>>b;
if(a==b){
cout<<0<<endl;
return 0;
}
direction=gcd(a,b);
t1=min_fj(a,direction);
if(t1==-1){
cout<<-1<<endl;
return 0;
}
t2=min_fj(b,direction);
if(t2==-1){
cout<<-1<<endl;
return 0;
}
cout<<t1+t2<<endl;
return 0;
}
[BZOJ 1050]旅行/[CodeVS 1001]舒适的路线
这两个题是一样的啊……
让路径上最大值最小当然要玩瓶颈路，瓶颈路需要MST，然后Kruskal求MST时最小边不是不可控的！也就是说我们可以控制最小边，从而求出符合要求的生成树，然后凿出瓶颈路。
所以我们可以直接枚举最小边，然后Kruskal求生成树，之后求瓶颈路。至于是否有解，第一遍Kruskal（第一遍求的其实是MST）之后看看是否联通即可。
不过这个题求瓶颈路个人建议用BFS而不是DFS，且不谈BFS效率高还不易炸堆栈段（尽管这个题没有炸堆栈段的隐患），DFS本身细节就很多，容易错。
代码：
/**************************************************************
Problem: 1050
User: danihao123
Language: C++
Result: Accepted
Time:3588 ms
Memory:1172 kb
****************************************************************/
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <bitset>
#include <vector>
#include <queue>
using namespace std;
const int maxn=501,maxm=10001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REPB(i,n) for(i=1;i<=(n);i++)
#define CUS_REP(i,u,v) for(i=(u);i<(v);i++)
#define REP_G(i,u) for(i=first[u];i;i=next[i])
#define CL_ARR(x,v) memset(x,v,sizeof(x))
typedef pair<int,int> pii;
int n;
int S,T;
// Graph
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int G_cnt=0;
inline void Add_Edge(int u,int v,int d){
G_cnt++;
next[G_cnt]=first[u];
first[u]=G_cnt;
to[G_cnt]=v;
dist[G_cnt]=d;
}
inline void Clear_Graph(){
CL_ARR(first,0);
CL_ARR(next,0);
CL_ARR(to,0);
CL_ARR(dist,0);
G_cnt=0;
}
// BFS
bitset<maxn> vis;
struct Node{
int x,maxv,minv;
};
pii BFS(){
register int a,b,i;
queue<Node> Q;
Node tt;
Q.push((Node){S,-1,0x7fffffff});
vis[S]=true;
while(!Q.empty()){
tt=Q.front();
Q.pop();
if(tt.x==T)
return make_pair(tt.maxv,tt.minv);
REP_G(i,tt.x){
if(!vis[to[i]]){
vis[to[i]]=true;
Q.push((Node){to[i],max(tt.maxv,dist[i]),min(tt.minv,dist[i])});
}
}
}
}
// BINGCHA Set
int p[maxn],rank[maxn];
int find_set(int x){
if(p[x]==x)
return x;
else
return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
if(rank[x]>rank[y]){
p[y]=x;
}else{
p[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
inline void union_set(int x,int y){
link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
return find_set(x)==find_set(y);
}
inline void init_set(){
register int i;
for(i=1;i<=n;i++)
p[i]=i;
CL_ARR(rank,0);
}
// MST
struct Edge{
int u,v,d;
bool operator <(const Edge& x) const{
return d<x.d;
}
};
vector<Edge> E;
bool OK=false;
pii ans;
void MST(int x){
register int i,a,b,cnt=0;
pii que;
register double jia,yi;
Clear_Graph();
init_set();
CUS_REP(i,x,E.size()){
if(!is_same(E[i].u,E[i].v)){
Add_Edge(E[i].u,E[i].v,E[i].d);
Add_Edge(E[i].v,E[i].u,E[i].d);
cnt++;
union_set(E[i].u,E[i].v);
if(cnt==n-1)
break;
}
}
if(is_same(S,T)){
OK=true;
}else{
return;
}
vis.reset();
que=BFS();
a=que.first;
b=que.second;
jia=((double)a)/((double)b);
yi=(double(ans.first))/(double(ans.second));
if(jia<yi){
ans.first=a;
ans.second=b;
}
}
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
// I/O优化
inline int readint(){
char c=getchar();
register int x=0;
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return x;
}
int main(){
int m;
register int i,u,v,d;
n=readint();
m=readint();
REP(i,m){
u=readint();
v=readint();
d=readint();
E.push_back((Edge){u,v,d});
}
S=readint();
T=readint();
sort(E.begin(),E.end());
ans.first=0x7fffffff;
ans.second=1;
REP(i,m){
MST(i);
if(!OK){
if(!i){
puts("IMPOSSIBLE");
return 0;
}else{
break;
}
}
}
d=gcd(ans.first,ans.second);
ans.first/=d;
ans.second/=d;
if(ans.second==1)
printf("%d\n",ans.first);
else
printf("%d/%d\n",ans.first,ans.second);
return 0;
}
[CodeVS 3269]混合背包
哎……现在才敢说真正会背包DP……
这个题可以分成三类问题分别处理，然后用一个一维数组一起递推。
0-1背包和完全背包都很简单。多重背包直接递推的话复杂度很高，可以考虑单调队列优化……然而窝太弱……不过还是用了
代码：
#include <cstdio>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxn=201,maxv=200001;
struct DQueue{
deque<int> D;
queue<int> Q;
void push(int x){
Q.push(x);
while(!D.empty() && x>D.back())
D.pop_back();
D.push_back(x);
}
int top(){
return D.front();
}
void pop(){
if(D.front()==Q.front())
D.pop_front();
Q.pop();
}
int size(){
return Q.size();
}
void clear(){
while(!Q.empty())
Q.pop();
D.clear();
}
};
int d[maxv];
int v;
void pack(int V,int W,int c){
register int i,j,m;
if(c==1){
for(i=v;i>=V;i--)
d[i]=max(d[i],d[i-V]+W);
}else{
if(c==-1){
for(i=V;i<=v;i++)
d[i]=max(d[i],d[i-V]+W);
}else{
c=min(c,v/V);
for(i=0;i<V;i++){
m=(v-i)/V;
DQueue Q;
for(j=0;j<=m;j++){
if(Q.size()==c+1)
Q.pop();
Q.push(d[j*V+i]-j*W);
d[j*V+i]=Q.top()+j*W;
}
}
}
}
}
int main(){
register int i;
int n,x,y,z;
scanf("%d%d",&n,&v);
for(i=1;i<=n;i++){
scanf("%d%d%d",&x,&y,&z);
pack(x,y,z);
}
printf("%d\n",d[v]);
return 0;
}
[CodeVS 1044]拦截导弹
第一问很显然是最长不升子序列，直接DP即可。
第二问咋整？暴力？网络流？
其实就是最长不降子序列。具体证明嘛……自己找吧。
代码：
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=22;
int d[maxn],f[maxn];
int A[maxn];
int main(){
int n;
register int i,j,ans=0;
for(n=1;;n++)
if(scanf("%d",&A[n])!=1)
break;
n--;
for(i=1;i<=n;i++){
d[i]=1;
for(j=i-1;j>=1;j--)
if(A[j]>=A[i])
d[i]=max(d[i],d[j]+1);
ans=max(ans,d[i]);
}
printf("%d\n",ans);
ans=0;
for(i=1;i<=n;i++){
f[i]=1;
for(j=i-1;j>=1;j--)
if(A[j]<=A[i])
f[i]=max(f[i],f[j]+1);
ans=max(ans,f[i]);
}
printf("%d\n",ans);
return 0;
}
[BZOJ 3831]Little Bird
单调队列水体……然而我这蒟蒻仍然WA一墙
这个题本质是一个动态规划，然后我们发现取区间递推最小值这个任务可以交给单调队列君来做~不过优先级似乎是一个问题……
优先级直接按照递推值来搞即可，递推值一样的话才按照高度比。因为就算递推值比较小但高度会带来额外影响，也不过是1，这样撑死也不会使答案更差
但凡是单调队列的题，都会有神秘细节，这题也不例外……顺便说一下这题不要傻乎乎的用pair
代码：
/**************************************************************
Problem: 3831
User: danihao123
Language: C++
Result: Accepted
Time:11596 ms
Memory:16228 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxn=1e6+1;
int D[maxn],f[maxn];
bool d_cmp(int x,int y){
if(f[x]==f[y])
return D[x]<D[y];
else
return f[x]>f[y];
}
struct DQueue{
deque<int> D;
queue<int> Q;
void push(int x){
Q.push(x);
while(!D.empty() && d_cmp(D.back(),x))
D.pop_back();
D.push_back(x);
}
int top(){
return D.front();
}
void pop(){
if(D.front()==Q.front())
D.pop_front();
Q.pop();
}
int size(){
return Q.size();
}
void clear(){
while(!Q.empty())
Q.pop();
D.clear();
}
};
DQueue hhh;
int main(){
register int i,temp,ans;
int n,Q,k;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&D[i]);
scanf("%d",&Q);
while(Q--){
scanf("%d",&k);
hhh.push(1);
f[1]=0;
for(i=2;i<=n;i++){
while(hhh.size()>k)
hhh.pop();
temp=hhh.top();
f[i]=f[temp]+(D[temp]<=D[i]);
hhh.push(i);
}
printf("%d\n",f[n]);
hhh.clear();
}
return 0;
}
[洛谷 P2679]子串
DP神题……
第一眼都能看出来是DP，然后大约构思就出来了，但细节很复杂啊……
看完第一眼后大家大约都能想出来[tex]d[i][j][k][/tex]这样的状态，但是注意[tex]A[i]=B[j][/tex]（字符数组细节此处未予考虑）的情况和整体情况要独立对待，否则这题只能233
然后下面就不难想了。但是注意直接开数组会233，要开滚动数组防MLE。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1001,maxm=201,maxk=201;
const int MOD=1e9+7;
int d[2][maxm][maxk][2];
char A[maxn];
char B[maxm];
int main(){
register int i,j,p,now,pre;
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
scanf("%s%s",A,B);
d[0][0][0][1]=1;
for(i=1;i<=n;i++){
now=i%2;
pre=1-now;
d[now][0][0][1]=1;
for(j=1;j<=m;j++){
if(A[i-1]==B[j-1])
for(p=1;p<=min(k,j);p++){
d[now][j][p][0]=(d[pre][j-1][p][0]+d[pre][j-1][p-1][1])%MOD;
d[now][j][p][1]=(d[pre][j][p][1]+d[now][j][p][0])%MOD;
}
else
for(p=1;p<=min(k,j);p++){
d[now][j][p][0]=0;
d[now][j][p][1]=d[pre][j][p][1];
}
}
}
printf("%d\n",d[n%2][m][k][1]);
return 0;
}
