hgoi#20191109
T1- 开着老爷车去 CSP
你有一辆车,每开 $k$ 公里要修理 $t$ 秒 你离目的地 $d$ 公里,你开车的速度和步行的速度分别是 $a$ 和 $b$ 你可以随时弃车步行,求到目的地的最少时间
解法
数学推导,第一段肯定是开车去 后面将开车一段和修理的时间与步行相同路程的时间做一下比较 如果步行优,行完第一段就弃车 如果开车优,还要判断最后一段是开车还是步行
ac 代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll d,k,a,b,t,ans;
int main()
{
scanf("%lld%lld%lld%lld%lld",&d,&k,&a,&b,&t);
if(d<=k)printf("%lldn",a*d),exit(0);
ll opt=ak-bk+t;
if(opt>=0)ans=ak+b(d-k);
else
{
ll x=d/k,y=d%k;
if(y)ans=min(optx+db-t,da+xt);
else ans=optx+db-t;
}
printf("%lldn",ans);
return 0;
}
T2-CSP- S 图
一幅带权有向图,每个点有且只有一个出边 求每个点走了 k 步之后经过的所有权值和最小权值
解法
因为每个点只有一个出边,所以每一步走法是唯一的 所以可以搞出一个 dp $f_{i,k}=f_{to_i,k-1}+w[i]$ $g_{i,k}=min(g_{to_i,k-1},w[i])$ 然后这玩意可以倍增优化转移
ac 代码
#include<bits/stdc++.h>
#define N 100010
#define K 35
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
int n,k,tN,sumN,minnN;
signed main()
{
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
scanf("%lld",&ti),ti++;
for(int i=1;i<=n;i++)
scanf("%lld",&sumi),minni=sumi;
for(int j=1;j<K;j++)
for(int i=1;i<=n;i++)
ti=tt[i][j-1],
sumi=sumi+sumt[i][j-1],
minni=min(minni,minnt[i][j-1]);
for(int i=1;i<=n;i++)
{
int ans1=0,ans2=inf,nw=i;
for(int j=0;j<K;j++)if(k&(1ll<<j))
ans1+=sumnw,ans2=min(ans2,minnnw),nw=tnw;
printf("%lld %lldn",ans1,ans2);
}
return 0;
}
T3- 好运
一个数如果是 7 的倍数,会带来好运气 但如果 $x\mod p_i=a_i$ 反而会带来坏运气 求区间 $[l,r]$ 内会带来好运气的数的个数
解法
用 CRT 和容斥乱搞一下 具体见代码
ac 代码
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
void ex_gcd(int a,int b,int &x,int &y)
{
if(!b)x=1,y=0;
else ex_gcd(b,a%b,y,x),y-=(a/b)*x;
}
int T,q,l,r,ans,p[20],o[20],m[20],a[20];
pii tmp;
pii china(int n)
{
int ans=0,lcm=1,x,y;
for(int i=1;i<=n;i++)lcm*=m[i];
for(int i=1;i<=n;i++)
{
int M=lcm/m[i];
ex_gcd(M,m[i],x,y);
x=(x%m[i]+m[i])%m[i];
ans=(ans+Mxa[i])%lcm;
}
return mp((ans+lcm)%lcm,lcm);
}
//CRT模板
int solve()
{
int st,ed;
if(l<=tmp.fir)st=0;
else st=(l-tmp.fir-1)/tmp.sec+1;
if(r<tmp.fir)ed=-1;
else ed=(r-tmp.fir)/tmp.sec;
return ed-st+1;
}
//solve用来求一个区间内满足要求的数的个数
void dfs(int nw,int cnt)
{
if(nw>q)
{
tmp=china(cnt);
//用CRT求出最小整数解
if(cnt&1)ans+=solve();
else ans-=solve();
//如果限制条件是奇数,就加
//如果限制条件是偶数,就减
}
else
{
dfs(nw+1,cnt);
cnt++;
m[cnt]=p[nw];
a[cnt]=o[nw];
dfs(nw+1,cnt);
}
}
signed main()
{
scanf("%lld",&T);
for(int _i=1;_i<=T;_i++)
{
memset(m,0,sizeof(m));
memset(a,0,sizeof(a));
scanf("%lld%lld%lld",&q,&l,&r);
for(int i=1;i<=q;i++)
scanf("%lld%lld",&p[i],&o[i]);
m[1]=7,a[1]=0,ans=0,dfs(1,1);
printf("Case #%lld: %lldn",_i,ans);
}
return 0;
}