UOJ Logo admin的博客

博客

LFYZ2018May题解

2018-05-19 12:08:14 By admin

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$,问题转为求解一元二次方程

接下来可以有三种方法:

  1. 可以确定 $a$ 的范围不会超过 $\sqrt p$,因为 $T$ 在100以内,枚举所有可能的 $a$ 即可。$O(N)$

  2. 使用求根公式计算 $a$,不过要进行精度验证。$O(1)$

  3. 可以确定 $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;
}

评论

lris
t2有另解 容易证明p为立方数的充要条件为p-1可被三整除,且商为两个连续自然数的乘积,等价于此商的四倍加一为完全平方数
lris
另外本oj上t3我没有快读但可以过,用bfs求最大深度加上m即可

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。