首页 > 代码库 > codeforces＃266 总结
codeforces＃266 总结
我靠！写的东西总被坑爹又不稳定的博客频道吞掉，我已经无力吐槽，也无力再写了！
简单写写题意题解。
A：
题意：给出n,m,a,b，表示坐n次公交，有单程票和多程票，多程票能用m次，单程票a元，多程票b元，求最少花费。
题解：动规， f[i]表示坐i次时最小花费，转移注意点就好了。不细说了，看代码，水水的！
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1005
using namespace std;
int f[N];
int n,m,a,b;
int main()
{
int i,j,k;
scanf("%d%d%d%d",&n,&m,&a,&b);
for(i=1;i<=n;i++)
{
f[i]=f[i-1]+a;
for(j=max(0,i-m);j<i;j++)
{
f[i]=min(f[i],f[j]+b);
}
}
printf("%d\n",f[n]);
return 0;
}
B：
题意：给出n,a,b，增加a或者b中至多一个的权值，使a*b>=6*n，输出a*b的最小值，及此时的a和b（SPJ）
题解：看代码吧，我毕竟被坑没A。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
long long n,a,b,c,d;
int main()
{
cin>>n>>a>>b;
n=n*6ll;
if(n<=a*b)
{
cout<<a*b;
printf("\n");
cout<<a<<' '<<b;
printf("\n");
return 0;
}
else
{
c=n/a;
if(a*c<n)c++;
d=n/b;
if(b*d<n)d++;
if(a*c<=b*d)
{
cout<<a*c;
printf("\n");
cout<<a<<' '<<c;
printf("\n");
return 0;
}
else
{
cout<<b*d;
printf("\n");
cout<<d<<' '<<b;
printf("\n");
return 0;
}
}
return 0;
}
C：
题意：给出n个数，把它们不打乱顺序分成三份（每份都不为空），使每份权值相同，问有多少种分法。
题解：正向反向预处理出权值前缀后缀和、之前之后有多少次权值正好为总权值1/3 。然后正着枚举，若前缀和是总权值1/3，看之后有多少种分法。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define N 501000
using namespace std;
int n,a[N],ctl[N],ctr[N];
long long sum,suml[N],sumr[N];
long long ans;
int main()
{
int i,j,k;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i];
if(sum%3)
{
printf("0\n");
return 0;
}
sum/=3;
for(i=1;i<=n;i++)
{
suml[i]=suml[i-1]+a[i];
ctl[i]=ctl[i-1];
if(suml[i]==sum)ctl[i]++;
}
for(i=n;i;i--)
{
sumr[i]=sumr[i+1]+a[i];
ctr[i]=ctr[i+1];
if(sumr[i]==sum)ctr[i]++;
}
for(i=1;i<n-1;i++)
{
if(suml[i]==sum)ans+=ctr[i+2];
}
cout<<ans;
return 0;
}
D :
题意：给n个数，要把它们通过规定操作全变成m，问有多少种方案。
操作：把一个区间上每个数都权值+1，任意两次操作的左端点不能相同，任意两次操作的左端点不能相同，如[1,5],[2,5]和[1,4],[2,4]这两例都不合法。
题解： 没AC，也不会。
E：
题意：n个文员，m次操作。
操作一：输入 a,b ， 表示a的上司设定为b
操作二：输入 a ， 表示从a开始传递资料，a往其上司传，上司再往上一层传，一直到没上司为止。
操作三：输入 a,b ， 表示询问文员a是否经手过资料b。
题解：（第四个点开始TLE）（觉得我的算法是O（n））
操作一为连边，b向a。
然后边有权值，为当前传过的资料号，
dfs时离线处理每次询问的答案，若传该资料的人到文员a的若干边的权值最大值大于资料号，则“NO”。小于则“YES”。
代码：可以去看我的tarjan lca，里面有这种算法的思想（自创）。
http://blog.csdn.net/vmurder/article/details/38734663
#include <cstdio>
#include <algorithm>
#define N 5001000
using namespace std;
struct KSD
{
int v,len,next;
}e[N],eq[N];
int head[N],headq[N],cnt,cntq,dcount;
int crs[N],ans[N];
bool visit[N];
int n,m;
void add(int u,int v)
{
e[++cnt].v=v;
e[cnt].len=dcount;
e[cnt].next=head[u];
head[u]=cnt;
}
void addq(int u,int v,int len)
{
eq[++cntq].v=v;
eq[cntq].len=len;
eq[cntq].next=headq[u];
headq[u]=cntq;
}
int f[N],l[N];
inline int find(int x)
{
if(f[x]==x)return x;
int t=f[x];
f[x]=find(f[x]);
l[x]=max(l[x],l[t]);
return f[x];
}
inline void dfs(int x,int p,int ll)
{
int i;
visit[x]=1;
for(i=head[x];i;i=e[i].next)
{
dfs(e[i].v,x,e[i].len);
}
for(i=headq[x];i;i=eq[i].next)
{
if(find(eq[i].v)==x&&l[eq[i].v]<=eq[i].len)
{
ans[i]=1;
}
}
f[x]=p;
l[x]=ll;
}
int main()
{
// freopen("test.in","r",stdin);
int i,j,k;
int a,b,c;
scanf("%d%d",&n,&m);
dcount=1;
for(i=1;i<=m;i++)
{
scanf("%d",&a);
if(a==1)
{
scanf("%d%d",&b,&c);
add(c,b);
}
if(a==2)
{
scanf("%d",&b);
crs[dcount++]=b;
}
if(a==3)
{
scanf("%d%d",&b,&c);
if(c>=dcount)++cntq;
else addq(b,crs[c],c);
}
}
for(i=1;i<=n;i++)f[i]=i;
for(i=1;i<=n;i++)
{
if(!visit[i])dfs(i,i,0);
}
for(i=1;i<=cntq;i++)
{
if(ans[i])puts("YES");
else puts("NO");
}
return 0;
}
codeforces＃266 总结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。