noip 模拟赛 1 题解
目录\(\to link \leftarrow\)
A 一步之遥
构造题
手玩了一下没有什么好的想法
后来在想能不能用递推的方式处理，也就是知道 \(N\) 的答案如何推导出 \(N+1\) 的答案
容易发现，\(N\) 的排列 \(\to\) \(N+1\) 的排列只是多了一个数而已，而我把多出来的数按顺序插入原排列的缝隙里就可以得到新的 \(N+1\) 种排列
计算一下，原来总共有 \(N!\) 种，现在每个排列都有新的 \(N+1\) 种排列，共是 \((N+1)!\) 种，刚好处理完
但是有一个小细节：
在一次按从左往右顺序插入后显然被插入的到了最右侧，那么就需要改变顺序为从右往左
这样就可以完成此题
时间复杂度：$$O(\sum_{i=1}^N i!)$$
#include<bits/stdc++.h>
using namespace std;
struct node{
int A[10];
};
vector <node> p[10];
int n,a[10];
inline void print(node x){
for(int i=1;i<=n;++i) cout<<x.A[i]<<" ";
cout<<endl;
}
inline void solve(int x){
node t;
int cnt=0;
for(node y:p[x-1]){
if(!cnt){
t.A[1]=1;
for(int i=2;i<=x;++i) t.A[i]=y.A[i-1]+1;
p[x].push_back(t);
for(int i=2;i<=x;++i){
swap(t.A[i],t.A[i-1]);
p[x].push_back(t);
}
}
else{
t.A[x]=1;
for(int i=1;i<x;++i) t.A[i]=y.A[i]+1;
p[x].push_back(t);
for(int i=x-1;i;--i){
swap(t.A[i],t.A[i+1]);
p[x].push_back(t);
}
}
cnt^=1;
}
}
signed main(){
cin>>n;
for(int i=1;i<=n;++i) a[i]=i;
node x;
x.A[1]=1,x.A[2]=2;
p[2].push_back(x);
x.A[1]=2,x.A[2]=1;
p[2].push_back(x);
solve(3);
solve(4);
solve(5);
solve(6);
solve(7);
solve(8);
solve(9);
for(node x:p[n]){
print(x);
}
}
退位计划
说实话我没有怎么做过计数题，考试遇到计数题基本都无了
就是算不明白……
而且容斥原理也用不明白，这一方面有待提高
这题可以转化成一个染色问题
我们假设 \(f_i\) 表示在没有每种颜色至少出现一次的情况下使用至多 \(i\) 种颜色的方案数
那么显然根可以染 \(i\) 种颜色，其余节点不能跟父亲染的一样，只能染 \(i-1\) 种颜色
总方案数 \(f_i=i\times (i-1)^{n-1}\)
根据容斥原理得，答案：
\[ans=\sum_{i=1}^k(-1)^{k-i}\cdot {k\choose i}\cdot f_i \]时间复杂度 \(O(n+k\log n)\)
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
int n,k,ans;
int frac[N],f[N];
inline int qpow(int x,int idx){
if(!idx) return 1;
int t=qpow(x,idx>>1);
return (idx&1)?1ll*t*t%mod*x%mod:1ll*t*t%mod;
}
inline int C(int x,int y){
if(x==y) return 1;
return 1ll*frac[x]*qpow(frac[y],mod-2)%mod*qpow(frac[x-y],mod-2)%mod;
}
signed main(){
cin>>n>>k;
frac[1]=1;
for(int i=2;i<=1000000;++i) frac[i]=1ll*frac[i-1]*i%mod;
for(int i=1;i<=k;++i)
f[i]=1ll*i*qpow(i-1,n-1)%mod;
for(int i=1;i<=k;++i){
//cout<<qpow(-1,k-i)<<" "<<C(k,i)<<" "<<f[i]<<endl;
ans=((ans+1ll*qpow(-1,k-i)*C(k,i)%mod*f[i]%mod)%mod+mod)%mod;
}
cout<<ans<<endl;
}
退役以后
打了 2h，就挺恶心的。
看到最长等待（在其下单后等待了最长时间）的人最少需要等待的时间了，老二分套路了
那就二分这个时间 \(x\)
由于要按顺序送快递，快递也是按顺序准备好的，无后效性，
而且特殊的点也只有一个 \(1\) 号点 (取快递)，想到用 \(dp\)
设 \(f_{i,j,0/1}\) 表示已经送了前 \(i\) 个快递，已经拿了前 \(j\) 个快递，并且当前在 \(u_i\ /\ 1\)号点所需的最小时间
设 \(g_j=\min\{f_{i,i\sim j,1}\}\)
那么 \(dp\) 式子如下：
for(int i=2;i<=K;++i){
g[i-1]=inf;
for(int j=i;j<=K;++j){
if(f[i-1][j][0]+dis[1][a[i].u]-a[i].s<=x)
f[i][j][1]=min(f[i][j][1],f[i-1][j][0]+dis[1][a[i].u]);
if(f[i-1][j][1]+dis[a[i-1].u][a[i].u]-a[i].s<=x)
f[i][j][1]=min(f[i][j][1],f[i-1][j][1]+dis[a[i-1].u][a[i].u]);
g[j]=min(g[j-1],f[i][j][1]);
if(j>i) f[i][j][0]=min(f[i][j][0],max(g[j]+dis[a[i].u][1],1ll*a[j].t));
}
}
总时间复杂度：$$O(kNM+K^2\log 1e18)$$ (\(k\) 表示 \(SPFA\) 的常数)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N=1e3+5;
const int M=5e3+5;
const ll inf=1e18;
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
struct work{
int s,u,t;
}a[N];
struct node{
int x,v;
};
int n,m,K;
ll dis[N][N],f[N][N][2],g[N];
vector <node> G[N];
bitset <N> vis;
inline void spfa(int s){
queue <int> q;
vis.reset();
for(int i=1;i<=n;++i) dis[s][i]=inf;
dis[s][s]=0;
q.push(s);
vis[s]=1;
while(!q.empty()){
int x=q.front();
q.pop();
vis[x]=0;
for(auto y:G[x]){
if(dis[s][y.x]>dis[s][x]+y.v){
dis[s][y.x]=dis[s][x]+y.v;
if(!vis[y.x]){
vis[y.x]=1;
q.push(y.x);
}
}
}
}
}
inline bool check(ll x){
for(int i=0;i<=K;++i)
for(int j=0;j<=K;++j)
f[i][j][0]=f[i][j][1]=inf;
for(int i=1;i<=K;++i) f[0][i][0]=a[i].t;
g[0]=inf;
for(int i=1;i<=K;++i){
if(f[0][i][0]+dis[1][a[1].u]-a[1].s<=x)
f[1][i][1]=min(f[0][i][0]+dis[1][a[1].u],f[1][i][1]);
g[i]=min(g[i-1],f[1][i][1]);
//cout<<f[1][i][0]<<" "<<g[i]<<endl;
if(i>1) f[1][i][0]=min(f[1][i][0],max(g[i]+dis[a[1].u][1],1ll*a[i].t));
//cout<<1<<" "<<i<<" "<<f[1][i][1]<<" "<<f[1][i][0]<<endl;
}
for(int i=2;i<=K;++i){
g[i-1]=inf;
for(int j=i;j<=K;++j){
if(f[i-1][j][0]+dis[1][a[i].u]-a[i].s<=x)
f[i][j][1]=min(f[i][j][1],f[i-1][j][0]+dis[1][a[i].u]);
if(f[i-1][j][1]+dis[a[i-1].u][a[i].u]-a[i].s<=x)
f[i][j][1]=min(f[i][j][1],f[i-1][j][1]+dis[a[i-1].u][a[i].u]);
g[j]=min(g[j-1],f[i][j][1]);
if(j>i) f[i][j][0]=min(f[i][j][0],max(g[j]+dis[a[i].u][1],1ll*a[j].t));
}
}
//cout<<endl<<endl;
for(int i=1;i<=K;++i)
if(f[K][i][1]-a[K].t<=x)
return 1;
return 0;
}
signed main(){
n=read(),m=read();
while(m--){
int x=read(),y=read(),z=read();
G[x].push_back({y,z});
G[y].push_back({x,z});
}
for(int i=1;i<=n;++i)
spfa(i);
K=read();
for(int i=1;i<=K;++i)
a[i].s=read(),a[i].u=read(),a[i].t=read();
ll l=-1,r=1e18;
while(l<r-1){
ll mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid;
}
printf("%lld\n",r);
}