CSP11
T1
暴力
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define ull unsigned long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
//#define int long long
#define pb push_back
// #pragma comment(linker, ¡°/STACK:512000000,512000000¡±)
using namespace std;
const int N = 2e5+5,mod=1e9+7,inf=1e9;
int n,m,dis[N];bool vis[N];
vector <int> edge[N];
struct Node
{
int dis,u;
bool operator < (const Node& A)const
{
return dis>A.dis;
}
};
int st,en;
void dij(int st)
{
for(int i=1;i<=n;i++)dis[i]=1e9;
priority_queue <Node> q;
q.push({0,st});
dis[st]=0;
while(q.size())
{
int u=q.top().u;q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto to:edge[u])
{
if(vis[to])continue;
if(dis[to]>dis[u]+1)
{
dis[to]=dis[u]+1;
q.push({dis[to],to});
}
}
}
}
inline ll dfs(const int u,const int step,const int tg)
{
if(step>tg||(step==tg&&u!=en))return 0;//这两个特判优化不少
if(u==en)return step==tg;
vis[u]=1;
ll res=0;
for(auto to:edge[u])
{
if(vis[to])continue;
res=(dfs(to,step+1,tg)+res)%mod;
}
vis[u]=0;
return res;
}
int main()
{
speed();
// freopen("Fate1.in","r",stdin);
// freopen("Fate9.in","r",stdin);
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
cin>>n>>m;
cin>>st>>en;
// cout<<"**********"<<endl;
int u,v;
for(int i=1;i<=m;i++)
{
cin>>u>>v;
edge[u].pb(v);edge[v].pb(u);
}
dij(st);
memset(vis,0,sizeof vis);
int tg=dis[en]+1;
cout<<dfs(st,0,tg);
return 0;
}
我们其实没必要\(dfs\)找一遍,其实可以直接\(BFS\),从起点开始,\(f\)表示最短路径的数量，\(g\)表示最短路径+1的数量
如何转移?,设当前为\(u->to\),\(dis_u==dis_{to}则g_{u}+=f_{to}\)\(dis_{to}=dis_u+1,则g_{to}+=g_u,f_{to}+=f_u\)
注意顺序一定不能换,否则\(g_u\)不上
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define ull unsigned long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
//#define int long long
#define pb push_back
#define pii pair<int,int>
// #pragma comment(linker, ¡°/STACK:512000000,512000000¡±)
using namespace std;
const int N = 2e5+5,mod=1e9+7,inf=1e9;
int n,m,dis[N],g[N],f[N],id[N];bool vis[N];
vector <int> edge[N];
vector <pii> G;
struct Node
{
int dis,u;
bool operator < (const Node& A)const
{
return dis>A.dis;
}
};
int st,en;
void dij(int st)
{
for(int i=1;i<=n;i++)dis[i]=1e9;
priority_queue <Node> q;
q.push({0,st});
dis[st]=0;
while(q.size())
{
int u=q.top().u;q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto to:edge[u])
{
if(vis[to])continue;
if(dis[to]>dis[u]+1)
{
dis[to]=dis[u]+1;
q.push({dis[to],to});
}
}
}
}
// unordered_map <int,map<int,int>> dp;
// inline ll dfs(const int u,const int step,const int tg)
// {
// if(step>tg||(step==tg&&u!=en))return 0;
// if(u==en)return step==tg;
// if(dp[u][step])return dp[u][step];
// // cout<<step<<endl;
// vis[u]=1;
// ll res=0;
// for(auto to:edge[u])
// {
// if(vis[to])continue;
// res=(dfs(to,step+1,tg)+res)%mod;
// }
// vis[u]=0;
// return dp[u][step]=res;
// }
int main()
{
speed();
// freopen("Fate1.in","r",stdin);
// freopen("Fate9.in","r",stdin);
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
cin>>n>>m;
cin>>st>>en;
// cout<<"**********"<<endl;
int u,v;G.pb({0,0});
for(int i=1;i<=m;i++)
{
cin>>u>>v;
G.pb({u,v});
edge[u].pb(v);edge[v].pb(u);
}
dij(st);
memset(vis,0,sizeof vis);
auto ans=[&](int st,int en)
{
queue <int> q;
q.push(st);
f[st]=1;
// vis[st]=1;
while(q.size())
{
int u=q.front();q.pop();
// if(vis[u])continue;
// vis[u]=1;
for(auto to:edge[u])
{
if(dis[u]==dis[to])
{
g[u]+=f[to];g[u]%=mod;
// q.push(to);
}
}
for(auto to:edge[u])
{
if(dis[to]==dis[u]+1)
{
g[to]+=g[u];
f[to]+=f[u];
g[to]%=mod;f[to]%=mod;
if(!vis[to])vis[to]=1,q.push(to);
}
}
}
return g[en];
};
ll p=ans(st,en);
cout<<p<<endl;
return 0;
}
T2
暴力
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
int sum[N];
int n,a;
struct Fs
{
int x,w,v;
double dis;
}f[N];
bool cmp(Fs a,Fs b)
{
return a.x<b.x;
}
bool cmpdis(Fs a,Fs b)
{
return a.dis<b.dis;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen("EVA1.in","r",stdin);
cin>>n>>a;
bool ev=1;
for(int i=1;i<=n;i++)
{
cin>>f[i].w>>f[i].x>>f[i].v;
if(i>1&&f[i].v!=f[1].v)ev=0;
}
if(ev)
{
// cout<<"****"<<endl;
sort(f+1,f+1+n,cmp);
for(int i=1;i<=n;i++)sum[f[i].x]+=f[i].w;
for(int i=1;i<=f[n].x;i++)sum[i]+=sum[i-1];
int ans=0;
for(int i=1;i<=f[n].x;i++)
{
ans=max(ans,sum[min(i+a,f[n].x)]-sum[i-1]);
}
cout<<ans<<endl;
return 0;
}
// for(int i=1;i<=n;i++)
// cout<<"****"<<endl;
int ans=0;
for(double t=0.0001;t<=1;t+=0.0001)
{
for(int i=1;i<=n;i++)
{
f[i].dis=f[i].x+f[i].v*t;
}
sort(f+1,f+1+n,cmpdis);
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+f[i].w;
int st=1;
for(int i=1;i<=n;i=-~i)
{
while(f[i].dis-a>f[st].dis)st++;
ans=max(ans,sum[i]-sum[st-1]);
}
}
for(double t=0.001;t<=10;t+=0.02)
{
for(int i=1;i<=n;i++)
{
f[i].dis=f[i].x+f[i].v*t;
}
sort(f+1,f+1+n,cmpdis);
for(int i=1;i<=n;i=-~i)sum[i]=sum[i-1]+f[i].w;
int st=1;
for(int i=1;i<=n;i=-~i)
{
while(f[i].dis-a>f[st].dis)st++;
ans=max(ans,sum[i]-sum[st-1]);
}
}
cout<<ans;
return 0;
}
/*
3 10
1 15 55
10 20 55
100 25 55
*/
正解是枚举每一条鱼,设为\(i\)作为左端点(一定是最优的)，通过相对速度，算出每一条鱼对它的贡献\(l_t,r_t\),进行差分即可
一些细节问题，
精度问题
还有判断\(r\)是负数的情况不能要
速度相等的情况要注意
由于精度问题\(l,r\)可能要互换位置,先要换位置，再判断是否\(r<0\)
关于差分时，右端点\(r\)要加上一个\(eps\),就是为了先让鱼进来，再让鱼出去，以满足答案最优
点击查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4+5;
const double eps=1e-9;
int sum[N];
int n,a,cnt[N],jcnt[N];
struct Fs
{
int x,w,v;
}f[N];
bool cmp(Fs a,Fs b)
{
return a.x<b.x;
}
map <double,int> tmm;
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
// freopen("EVA1.in","r",stdin);
cin>>n>>a;
for(int i=1;i<=n;i++)
{
cin>>f[i].w>>f[i].x>>f[i].v;
}
sort(f+1,f+1+n,cmp);ll ans=0;
for(int i=1;i<=n;i++)
{
tmm.clear();
ll res=f[i].w;
for(int j=1;j<=n;j++)
{
if(i==j)continue;
if(f[j].v==f[i].v)
{
if(f[j].x>=f[i].x&&f[j].x-f[i].x<=a)res+=f[j].w;
// cout<<res<<endl;
continue;
}
// if(f[j].x<f[i].x&&f[j].v<=f[i].v)continue;
double l=1.0*(f[i].x-f[j].x)/(f[j].v-f[i].v);
double r=1.0*(f[i].x-f[j].x+a)/(f[j].v-f[i].v);
// cout<<t<<" "<<r<<rdl;
// if(t<0)continue;
if(l>r-eps)swap(l,r);//先要换位置，再判断是否r<0
if(r<0)continue;
l=max(l,0.0000);
tmm[l]+=f[j].w;
tmm[r+eps]-=f[j].w;
// if(f[j].x>f[i].x&&f[j].v>=f[i].v&&f[j].x-f[i].x>a)continue;
}
ans=max(ans,res);
for(auto it:tmm)
{
res+=(it.second);
ans=max(ans,res);
}
}
cout<<ans;
return 0;
}
/*
3 10
1 15 55
10 20 55
100 25 55
*/
T3
计数题
做法一：
排序\(a\)数组,然后,我们初始左右指针\(l=1,r=n\),在满足\(l<r企鹅a[l]+a[r]>=k\)的情况下不断让\(r\)指针右移,这样,一定会有一个边界，使得左端点\(a_l\)只能与\([r,n]\)的\(a\)匹配,我们把他们加入到数列中，用\(ans\)乘上贡献,类似插空的思想，当前未放入\(a_l,a_r\),
数列中已经包含\([1,l-1],[r+1,n]\),这样就有\(n-r+l-1+1\)个空，再减去有\([1,l-1]\)元素周围不能放\(a_r,a_l\)所以,贡献为\(n-r+l-2\times (l-1)\),但是要注意最后还用相同数的情况，所以乘上相同数阶乘的逆元即可
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define ull unsigned long long
#define lid (rt<<1)
#define rid (rt<<1|1)
#define endl '\n'
//#define int long long
#define pb push_back
// #pragma comment(linker, ¡°/STACK:512000000,512000000¡±)
using namespace std;
const int N = 2e5+5,mod=998244353,inf=1e9;
ll n,k,a[N],jie[N];
ll qpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
ll calc(ll l,ll r)
{
return (n-l-r+2);
}
int main()
{
speed();
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
jie[0]=1;
for(ll i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
sort(a+1,a+1+n);
ll l=1,r=n;
ll ans=1;
while(l<=r)
{
while(l<r&&a[r]+a[l]>=k)
{
ans=ans*calc(l,r)%mod;
r--;
}
ans=ans*calc(l,r)%mod;
l++;
}
ll cnt=1;
a[n+1]=inf;
for(int i=2;i<=n+1;i++)
{
if(a[i]==a[i-1])cnt++;
else
{
ans=ans*qpow(jie[cnt],mod-2)%mod;
cnt=1;
}
}
cout<<ans<<endl;
// for()
return 0;
}