LFYZ2018May题解

t1

对于两头牛 $(T_A, D_A),(T_B, D_B)$ ，先送哪一头？

先送A，啃掉的花为 $T_A*D_B$

先送B，啃掉的花为 $T_B*D_A$

很明显，要选择两者中小的一个，这个是一个贪心选择，按照 $T_i*D_i$ 排序即可。

#include<bits/stdc++.h>  
#define ll long long  
#define maxn 100050  
using namespace std;  
struct cow  
{  
  ll d, t;  
  bool operator<(cow x)const{return t*x.d<d*x.t;}  
}c[maxn];
ll N, ans;  
int main()  
{  
  freopen("flower.in","r",stdin);  
  freopen("flower.out","w",stdout);  
  ll i, j, t;  
  scanf("%I64d",&N);  
  for(i=1;i<=N;i++)scanf("%I64d%I64d",&c[i].t,&c[i].d),c[i].t<<=1;  
  sort(c+1,c+N+1);  
  for(t=0,i=1;i<=N;i++)  
  {  
    ans+=t*c[i].d;  
    t+=c[i].t;  
  }  
  printf("%I64d\n",ans);  
  return 0;  
}

t2

很容易推导出 $a^3-b^3=(a-b)(a^2+b^2+ab)=p$

因p是素数，可以确定 $a=b+1, a^2+b^2+ab=p$

消元得到：$3b^2+3b+(1-p)=0$，问题转为求解一元二次方程

接下来可以有三种方法：

可以确定 $a$ 的范围不会超过 $\sqrt p$，因为 $T$ 在100以内，枚举所有可能的 $a$ 即可。$O(N)$
使用求根公式计算 $a$，不过要进行精度验证。$O(1)$
可以确定 $a$ 的范围是 $(0, \sqrt p]$，因函数在这个区间内是单调递增的，可以使用二分法。$O(logN)$

//参考代码使用了枚举法
#include<bits/stdc++.h>
using namespace std;
int main()
{
    freopen("cubicp.in","r",stdin);
    freopen("cubicp.out","w",stdout);
    int t,flag;
    scanf("%d",&t);
    long long p;
    while(t--)
    {
        flag=0;
        scanf("%I64d",&p);
        for(int i=1;i<=1e6+10;i++)
        {
            if(3ll*i*i+3*i+1==p)
            {
                flag=1;
                break;
            }
            if (3ll*i*i+3*i+1>p) break;
        }
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

t3

题意有很多模糊的地方，但题目的原意是很简单的。

找出最长的发糖链，也就是最大的最短路径$max(dis[i])$

答案就是$max(dis[i])+m+1$，为什么要加1，因为问的是第几秒开始的时候，所有人都吃完了。。。

数据量很大，要使用SPFA

数据量太大，cin超时，scanf也超时，要用快读。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
const int INF=0x3f3f3f3f;
int n, p, c, m, ans=0;
vector<int> G[maxn];
struct edge{
    int from, to, dist;
    edge(int u, int v, int d):from(u),to(v),dist(d){}
};
vector<edge> E;
queue<int> Q;
int inq[maxn], dis[maxn];
void SPFA(int s){
    memset(dis, 0x3f, sizeof(dis));
    dis[s]=0;
    Q.push(s);
    inq[s]=1;
    while(!Q.empty()){
        int v=Q.front();
        Q.pop();
        inq[v]=0;
        for(int i=0; i<G[v].size(); i++){
            edge & e=E[G[v][i]];
            if(dis[v]+e.dist<dis[e.to]){
                dis[e.to]=dis[v]+e.dist;
                if(!inq[e.to]){
                    Q.push(e.to);
                    inq[e.to]=1;
                }
            } 
        }
    }
}

inline int read(){          //快读
    int s=0,w=1;  
    char ch=getchar();  
    while(ch<='0'||ch>'9'){
        if(ch=='-')
            w=-1;
        ch=getchar();
    }  
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}  

int main(){
    freopen("candy.in", "r", stdin);
    freopen("candy.out", "w", stdout);
    n=read();
    p=read();
    c=read();
    m=read();
    for(int i=0; i<p; i++){
        int u, v;
        u=read();
        v=read();
        E.push_back(edge(u, v, 1));
        G[u].push_back(E.size()-1);
        E.push_back(edge(v, u, 1));
        G[v].push_back(E.size()-1);
    }
    SPFA(c);
    for(int i=1; i<=n; i++)
        if(dis[i]!=INF)
            ans=max(ans, dis[i]);
    ans+=m;
    ans+=1;
    cout<<ans<<endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

快读函数前面加一个修饰符`inline`使得函数称为内联函数，内联函数在预处理时就被替换到代码中，避免了程序在执行过程中大量调用函数时的压栈（保存现场）、弹栈（恢复现场）操作，从而效率极高。C++中引入它的主要原因是用它替代C语言中表达式形式的宏定义。你必须知道的是，并不是所有的函数都可以写成内联函数，定义内联函数是要严格的条件限制的，使用的时候一定要小心！！！请自行百度学习。

t4

第一问，打个表可以看出规律来。这里其实是倍增的思想：只要有1，2，4，8，16，32...，这些数，所有的数都可以通过组合相加得到。（更严谨的证明是，考虑 $a$ 个数的子集有 $2^a$ 个，这 $a$ 个数最多能表示 $2^a$ 个数，这样的思路）

等比数列求和公式 $sum=2^x-1=n$，通过换低公式可得：$n=\frac{log{n+1}}{log2}$，求 $n$ 的时候要注意精度问题！解决方法可以让真数小一些，对结果取整加1：n=int(log(n)/log(2))+1，或者是自己写一个取 $\log$ 的函数。

第二问有两种方法：DFS和DP。

dfs 的话就像这样，你设置状态，表示当前在放第几个、和、最大值，然后记忆化搜索就可以了。数的个数很小，状态数差不多是一千万左右（$10 \times 1000 \times 1000$）

#include <iostream>
#include <cstdio>
using namespace std;
int n, a, v[11000005];
int getLg(int x){
    if(x==1)    return 0;
    return getLg(x>>1)+1;
}
int cnt=0;
int dfs(int x, int s, int l){
    if(x==a+1){
        if(s>=n)    return 1;
        else    return 0;
    }
    int tmp=(x-1)*1002001+s*1001+l;
    if(v[tmp]<0)    return 0;
    if(v[tmp]>0)    return v[tmp];
    cnt++;
    int re=0;
    for(int j=l+1; j<=s+1; j++)
        re += dfs(x+1, s+j, j);
    if(re==0)
        v[tmp] = -1;
    else
        v[tmp] = re;
    return re;
}
int main(){
    cin>>n;
    a = getLg(n) + 1;
    cout<<a<<" "<<dfs(1, 0, 0)<<endl;
    return 0;
}

dfs 的速度更优。如果你是个坚决不写搜索的人的话，用 dp。记 $dp_{i,j,k}$ 表示用前 $i$ 个数，总和是 $j$，最大值是 $k$ 的方案数。状态转移是枚举当前状态和新一个最大数，然后转移到新状态。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n;
long long dp[15][1035][1035];
int getLg(int x){
    if(x==1)    return 0;
    return getLg(x>>1)+1;
}
int main(){
    cin>>n;
    int a=getLg(n)+1;
    dp[1][1][1] = 1;
    for(int i=1; i<=a; i++)
        for(int j=1; j<=n; j++)
            for(int k=1; k<=n; k++)
                if(dp[i][j][k])
                    for(int l=k+1; l<=j+1; l++)//注意这里的新一轮最大数上届。如果你做了lfyzoj#7颓我家财就能想到为什么。简单的说，前面所有的数的和是 j，新一个数如果比 j+1 大，那么 j+1 就拼不出来了，就不合法了。
                        dp[i+1][min(j+l,n)][l] += dp[i][j][k];
    int ans=0;
    for(int i=1; i<=n; i++)
        ans += dp[a][n][i];
    cout<<a<<" "<<ans<<endl;
    return 0;
}

admin的博客

博客

t1

t2

t3

t4

评论

发表评论