A 直接线段树过的 两遍 貌似大多是标记过的。。注意long long
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define N 100100
LL s[N<<],lz[N<<],st[N<<],lzt[N<<];
LL a[N];
struct node
{
int l,r;
LL d;
}p[N];
void build(int l,int r,int w)
{
if(l==r)
{
st[w] = a[l];
return;
}
int m = (l+r)>>;
build(l,m,w<<);
build(m+,r,w<<|);
}
void down(int w,int m,int f)
{
if(f)
{
if(lz[w])
{
s[w<<]+=lz[w]*(m-m/);
s[w<<|]+=lz[w]*(m/);
lz[w<<] +=lz[w];
lz[w<<|]+=lz[w];
lz[w] = ;
}
}
else
{
if(lzt[w])
{
st[w<<]+=lzt[w]*(m-m/);
st[w<<|]+=lzt[w]*(m/);
lzt[w<<] += lzt[w];
lzt[w<<|] += lzt[w];
lzt[w] = ;
}
}
}
void update(int a,int b,LL d,int l,int r,int w,int f)
{
if(a<=l&&b>=r)
{
if(f)
{
s[w]+=(r-l+);
lz[w]++;
}
else
{
st[w]+=(r-l+)*d;
lzt[w]+=d;
}
return ;
}
down(w,r-l+,f);
int m = (l+r)>>;
if(a<=m)
update(a,b,d,l,m,w<<,f);
if(b>m)
update(a,b,d,m+,r,w<<|,f);
}
LL query(int p,int l,int r,int w,int f)
{
if(l==r)
{
if(f)
return s[w];
else return st[w];
}
down(w,r-l+,f);
int m = (l+r)>>;
if(p<=m)
return query(p,l,m,w<<,f);
else return query(p,m+,r,w<<|,f);
}
int main()
{
int i,k,n,m;
cin>>n>>m>>k;
for(i = ; i <= n ;i++)
cin>>a[i];
build(,n,);
for(i = ; i <= m ;i++)
cin>>p[i].l>>p[i].r>>p[i].d;
while(k--)
{
int x,y;
cin>>x>>y;
update(x,y,,,m,,);
}
for(i = ; i <= m ; i++)
{
p[i].d = query(i,,m,,)*p[i].d;
if(p[i].d)
{
update(p[i].l,p[i].r,p[i].d,,n,,);
}
}
for(i = ; i < n ;i++)
{
cout<<query(i,,n,,)<<" ";
}
cout<<query(n,,n,,)<<endl;
return ;
}
B floyd的变形 倒着更新 每次加一个节点 然后利用floyd的dp性质对所有的点对距离进行更新
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define N 510
#define LL long long
int a[N][N],b[N],q[N];
LL w[N][N],s[N];
int main()
{
int i,j,n,e;
cin>>n;
for(i = ; i <= n ;i++)
{
for(j = ; j <= n ;j++)
{
cin>>a[i][j];
w[i][j] = a[i][j];
}
}
for(i = ; i <= n ;i++)
{
cin>>b[i];
}
int g = ;
for(i = n ; i>= ; i--)
{
LL ans=;
g++;
q[g] = b[i];
for(j = ; j <= n ;j++)
for(e = ; e <= n ;e++)
w[j][e] = min(w[j][b[i]]+w[b[i]][e],w[j][e]);
for(j = ; j <= g ; j++)
for(e = ; e <= g ; e++)
{
//w[q[j]][q[e]] = min(w[q[j]][b[i]]+w[b[i]][q[e]],w[q[j]][q[e]]);
ans+=w[q[j]][q[e]];
}
s[i] = ans;
}
for(i = ; i <= n ; i++)
cout<<s[i]<<" ";
return ;
}
C 搜索+dp
刚开始只往 dp方向 想了 想着先dp出最短的 再倒 回去符合情况的状态保存下来 找次数 貌似时间复杂度 以及代码难写度都很高 正确性也不能保证。。果断没写
看了题解说是搜索+dp 想到用bfs保存状态求次数最小 貌似遇到组合就会卡 组合求 次数的地方一直没写对 之后参考别人的 应该是每次符合情况的都要加上而不只是入队的那颗加 挺好的一题
#include <iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
#define LL long long
#define mod 1000000007
#define INF 0xfffffff
LL c[][];
int vis[][][];
LL dp[][][];
struct node
{
int num,a,b,d;
};
int n,k;
void init()
{
int i,j;
for(i = ; i <= n ;i++)
{
c[i][] = ;
}
for(i = ; i <= n; i++)
{
for(j = ; j <= i ; j++)
{
c[i][j] = (c[i-][j]+c[i-][j-])%mod;
}
}
}
void bfs(int c1,int c2)
{
int i,j;
queue<node>q;
node tt;
memset(vis,-,sizeof(vis));
tt.num = ;tt.d = ;
tt.a = c1;tt.b = c2;
vis[][c1][c2] = ;
dp[][c1][c2] = ;
q.push(tt);
int minz = INF;
while(!q.empty())
{
node st = q.front();q.pop();
if(st.a==c1&&st.b==c2&&st.d==) minz = min(minz,st.num);
for(i = ; i <= st.a ; i++)
for(j = ; j <= st.b ; j++)
{
int a1 = c1-st.a+i;
int b1 = c2-st.b+j;
if(i+j>=&&i*+j*<=k)
{
if(vis[st.d^][a1][b1]==-)
{
vis[st.d^][a1][b1] = vis[st.d][st.a][st.b]+;
tt.num = st.num+;
tt.a = a1;tt.b = b1;
tt.d = st.d^;
q.push(tt);
dp[st.d^][a1][b1] = (dp[st.d^][a1][b1]+((dp[st.d][st.a][st.b]*c[st.a][i])%mod*c[st.b][j])%mod)%mod;
}
else if(vis[st.d^][a1][b1]==vis[st.d][st.a][st.b]+)
dp[st.d^][a1][b1] = (dp[st.d^][a1][b1]+((dp[st.d][st.a][st.b]*c[st.a][i])%mod*c[st.b][j])%mod)%mod;
}
}
}
if(minz!=INF)
cout<<minz<<"\n"<<dp[][c1][c2]<<endl;
else
printf("-1\n0\n");
}
int main()
{
int i;
cin>>n>>k;init();
int c1=,c2=;
for(i = ; i <= n ;i++)
{
int a;
cin>>a;
if(a==)
c1++;
else c2++;
}
bfs(c1,c2);
return ;
}