T1 玩游戏
解题思路
可以把序列从 k 位置掰成两个序列。
问题就变成了两个序列从开头走向末尾是否可以保证前缀和之和一直不大于 0 。
并且可以移动到两个序列的末尾，问题就变成处理前缀和。
然后在每一个序列里维护一个 next 值，表示可以跳到的较小值。
这里需要正反扫一遍，毕竟只扫一边的话会有最小值一边的 next 无法更新。
然后就是对于两个序列分别从两边扫一边。
看看是否可以跳到对应的 next 位置。
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Pass"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
const int N=1e5+10,INF=1e18;
int T,n,k,l,r,sum,s[N],nxt1[N],nxt2[N];
int a[N],b[N],cnt1,cnt2,pre1[N],pre2[N];
void solve()
{
memset(nxt1,0,sizeof(nxt1));
memset(nxt2,0,sizeof(nxt2));
n=read(); k=read();
cnt1=cnt2=0;
for(int i=1;i<=n;i++)
s[i]=read();
a[++cnt1]=0; b[++cnt2]=0;
for(int i=k+1;i<=n;i++)
a[++cnt1]=s[i];
for(int i=k;i>1;i--)
b[++cnt2]=s[i];
for(int i=1;i<=cnt1;i++)
pre1[i]=pre1[i-1]+a[i];
for(int i=1;i<=cnt2;i++)
pre2[i]=pre2[i-1]+b[i];
int pos,minn;
minn=pre1[1]; pos=1;
for(int i=2;i<=cnt1;i++)
if(minn>=pre1[i])
{
nxt1[pos]=i;
pos=i;
minn=pre1[i];
}
minn=pre1[cnt1]; pos=cnt1;
for(int i=cnt1-1;i>=1;i--)
if(minn>pre1[i])
{
nxt1[pos]=i;
pos=i;
minn=pre1[i];
}
minn=pre2[1]; pos=1;
for(int i=2;i<=cnt2;i++)
if(minn>=pre2[i])
{
nxt2[pos]=i;
pos=i;
minn=pre2[i];
}
minn=pre2[cnt2]; pos=cnt2;
for(int i=cnt2-1;i>=1;i--)
if(minn>pre2[i])
{
nxt2[pos]=i;
pos=i;
minn=pre2[i];
}
if(pre1[cnt1]+pre2[cnt2]>0)
{
printf("No\n");
return ;
}
int pos1=1,pos2=1;
bool flag=true;
while(nxt1[pos1]||nxt2[pos2])
{
flag=true;
for(int i=pos1+1;i<=nxt1[pos1];i++)
if(pre1[i]+pre2[pos2]>0)
{
flag=false;
break;
}
if(!nxt1[pos1]) flag=false;
if(flag){pos1=nxt1[pos1];continue;}
flag=true;
for(int i=pos2+1;i<=nxt2[pos2];i++)
if(pre1[pos1]+pre2[i]>0)
{
flag=false;
break;
}
if(!nxt2[pos2]) flag=false;
if(!flag) break;
pos2=nxt2[pos2];
flag=true;
}
if(!flag)
{
printf("No\n");
return ;
}
pos1=cnt1;pos2=cnt2;
while(nxt1[pos1]||nxt2[pos2])
{
flag=true;
for(int i=pos1-1;i>=nxt1[pos1];i--)
if(pre1[i]+pre2[pos2]>0)
{
flag=false;
break;
}
if(!nxt1[pos1]) flag=false;
if(flag){pos1=nxt1[pos1];continue;}
flag=true;
for(int i=pos2-1;i>=nxt2[pos2];i--)
if(pre1[pos1]+pre2[i]>0)
{
flag=false;
break;
}
if(!nxt2[pos2]) flag=false;
if(!flag) break;
pos2=nxt2[pos2];
flag=true;
}
if(!flag)
{
printf("No\n");
return ;
}
printf("Yes\n");
}
signed main()
{
T=read();
while(T--) solve();
return 0;
}
排列
解题思路
动态规划。
DP 数组 \(f_{i,j,0/1,0/1}\) 表示区间长度为 i 操作 j 次正好可以只剩下一个的方案数。
0 或者 1 分别表示左边或者右边是否有更大的或者边界。
然后就可以通过之前的状态和组合数进行转移。
分别枚举现在区间的长度，操作次数，子区间长度，以及子区间操作次数进行转移。
转移的时候就好像在两个子区间中间插进去一个更大的数，其实是和挨着边界差不多的。
但是这样显然会 TLE 因此需要前缀和优化。
转移也是差不多的，只不过省掉了一维枚举子区间的操作。
然后直接整阶乘进行组合数的计算是会被卡常的，因此需要杨辉三角处理。。
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Pass"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e3+10;
int n,m,mod,c[N][N],f[N][15][2][2];
void init()
{
c[0][0]=1;
for(int i=1;i<=n;i++)
{
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
}
signed main()
{
n=read(); m=read(); mod=read();
init();
for(int i=0;i<=m;i++)
f[0][i][0][0]=f[0][i][1][0]=f[0][i][0][1]=f[0][i][1][1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=i;k++)
{
f[i][j][0][0]=(f[i][j][0][0]+f[k-1][j][0][1]*f[i-k][j][1][0]%mod*c[i-1][k-1])%mod;
f[i][j][1][0]=(f[i][j][1][0]+f[k-1][j][1][0]*f[i-k][j-1][1][1]%mod*c[i-1][k-1])%mod;
f[i][j][0][1]=(f[i][j][0][1]+f[k-1][j][0][1]*f[i-k][j-1][1][1]%mod*c[i-1][k-1])%mod;
int tmp1=(f[k-1][j][1][1]-f[k-1][j-1][1][1]+mod)%mod;
int tmp2=(f[i-k][j][1][1]-f[i-k][j-1][1][1]+mod)%mod;
f[i][j][1][1]=(f[i][j][1][1]+(f[k-1][j][1][1]*f[i-k][j][1][1]%mod-tmp1*tmp2%mod+mod)*c[i-1][k-1])%mod;
}
printf("%lld",(f[n][m][0][0]-f[n][m-1][0][0]+mod)%mod);
return 0;
}
最短路
解题思路
考场上是想了一个假做法，先从 1 为源点跑一边，用 bitset 进行维护。
然后再第一次的 Dij 的基础上继承以后再跑一次，更新答案。
然后这个做法是 WA 了两个点，但是由于测试是 subtask 的，所以就 20pts 了。
Yubai 的思路非常的妙！！
对于每一个有的边建一条反边，跑 二维DIJ。
\(dis_{i,j}\) 表示 从 1 节点沿正边到达 i 点以及沿反边到 j 点的距离之和。
这样 \(dis_{n,n}\) 表示的就是从 1 沿正边到 n 在沿正边走回来的距离。
同样用 bitset 维护，因为这个是动态的，因此具有正确性。
二维Dij 的时候注意两步不可以同时进行要一步一步来。。
通俗来讲就是两个循环而不是两层循环。。。
code
20ptsWA两个点
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Pass"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
const int N=260,M=N*N,INF=1e18;
int n,m,ans=INF,s[N],dis[N],dis2[N];
int tot=1,head[N],nxt[M],ver[M],edge[M];
bitset<N> bit[N],bit2[N];
bool vis[N],b[M];
priority_queue<pair<int,int> > q;
void add_edge(int x,int y)
{
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void check(int x)
{
b[x]=true;
for(int i=head[x];i;i=nxt[i])
if(!b[ver[i]]&&vis[ver[i]])
check(ver[i]);
}
bool judge()
{
bool jud1,jud2;
check(1); jud1=b[n];
memset(b,false,sizeof(b));
check(n); jud2=b[1];
memset(b,false,sizeof(b));
return jud1&&jud2;
}
void Dij()
{
memset(dis,0x3f,sizeof(dis));
dis[1]=s[1]; bit[1][1]=true;
q.push(make_pair(-dis[1],1));
while(!q.empty())
{
int x=q.top().second;q.pop();
if(vis[x]) continue;
vis[x]=true;
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i],sum=0;
bitset<N> bi=bit[to]|bit[x];
for(int j=1;j<=n;j++)
if(bi[j])
sum+=s[j];
if(!bi[to])
{
bi[to]=true;
sum+=s[to];
}
if(sum<dis[to])
{
dis[to]=sum;
bit[to]=bi;
q.push(make_pair(-dis[to],to));
}
}
}
}
void Dij2()
{
memset(dis2,0x3f,sizeof(dis2));
dis2[n]=dis[n]; bit2[n]=bit[n];
q.push(make_pair(-dis2[n],n));
while(!q.empty())
{
int x=q.top().second;q.pop();
if(vis[x]) continue;
vis[x]=true;
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i],sum=0;
bitset<N> bi=bit2[to]|bit2[x];
for(int j=1;j<=n;j++)
if(bi[j])
sum+=s[j];
if(!bi[to])
{
bi[to]=true;
sum+=s[to];
}
if(sum<dis2[to])
{
dis2[to]=sum;
bit2[to]=bi;
q.push(make_pair(-dis2[to],to));
}
}
}
}
void dfs(int x,int cnt)
{
if(x==n)
{
if(judge()) ans=min(ans,cnt);
return ;
}
dfs(x+1,cnt);
vis[x]=true;
dfs(x+1,cnt+s[x]);
vis[x]=false;
}
void solve()
{
memset(vis,false,sizeof(vis));
vis[1]=vis[n]=true;
dfs(2,s[1]+s[n]);
printf("%lld",ans);
exit(0);
}
signed main()
{
n=read(); m=read();
for(int i=1;i<=n;i++)
s[i]=read();
for(int i=1,x,y;i<=m;i++)
{
x=read(); y=read();
add_edge(x,y);
}
memset(vis,true,sizeof(vis));
if(!judge())
{
printf("-1");
return 0;
}
memset(vis,false,sizeof(vis));
Dij();
memset(vis,false,sizeof(vis));
Dij2();
printf("%lld",dis2[1]);
return 0;
}
正解
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Pass"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
const int N=260,M=N*N,INF=0x3f3f3f3f3f3f3f3f;
int n,m,s[N],dis[N][N];
int tot,head[N],nxt[M],ver[M];
int tot2,head2[N],nxt2[M],ver2[M];
bool vis[N][N];
bitset<N> bit[N][N];
struct Node
{
int dat,x,y;
bool friend operator < (Node x,Node y)
{
return x.dat>y.dat;
}
};
priority_queue<Node> q;
void add_edge(int x,int y)
{
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void add_edge2(int x,int y)
{
ver2[++tot2]=y;
nxt2[tot2]=head2[x];
head2[x]=tot2;
}
void Dij()
{
memset(dis,0x3f,sizeof(dis));
dis[1][1]=s[1];
bit[1][1][1]=true;
q.push((Node){dis[1][1],1,1});
while(!q.empty())
{
int x=q.top().x,y=q.top().y;q.pop();
if(vis[x][y]) continue;
vis[x][y]=true;
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i],temp=0;
if(!bit[x][y][to]) temp=s[to];
if(dis[x][y]+temp<dis[to][y])
{
bit[to][y]=bit[x][y];
bit[to][y][to]=true;
dis[to][y]=dis[x][y]+temp;
q.push((Node){dis[to][y],to,y});
}
}
for(int i=head2[y];i;i=nxt2[i])
{
int to=ver2[i],temp=0;
if(!bit[x][y][to]) temp=s[to];
if(dis[x][y]+temp<dis[x][to])
{
bit[x][to]=bit[x][y];
bit[x][to][to]=true;
dis[x][to]=dis[x][y]+temp;
q.push((Node){dis[x][to],x,to});
}
}
}
}
signed main()
{
n=read(); m=read();
for(int i=1;i<=n;i++)
s[i]=read();
for(int i=1,x,y;i<=m;i++)
{
x=read(); y=read();
add_edge(x,y);
add_edge2(y,x);
}
Dij();
printf("%lld",dis[n][n]==INF?-1ll:dis[n][n]);
return 0;
}