投稿
  1. 高性能架构探索首页
  2. C/C++

凉心模拟总结

admin • • C/C++ • 阅读 126

还是自己太菜了，Day1并没有发现这套题需要写读入优化，所以说第一天很凉。

Day 1

\(\color{blue} \text {餐馆（restaurant）}\)

\(\color{blue} \text {【题目描述】}\)

铜企鹅是企鹅餐馆的老板，他正在计划如何使得自己本年度收益增加。

共有 n 种食材，一份食材 i 需要花 ti 小时不间断地进行播种，施肥，直至收获。当然，一份食材 i 是可以直接卖掉得到 wi 块钱的。

招牌菜共有 m 种，一份招牌菜 i 需要消耗一定的食材，花 Ti 小时不间断地来烹饪，叫卖，并最终卖出得到 Wi 块钱。

整个季度换算下来一共有 Tmax 小时可供你使用，铜企鹅需要在这期间赚到最多的钱，这样他才有足够多的钱来 steam 剁手，或者氪金手游。

\(\color{blue} \text {【输入】}\)

第一行一个整数 T，表示数据组数。

令 i 表示为当前数据内行数。

第一行三个整数 n,m,Tmax，含义如题所示。

第二行至第 n+1 行，每行两个整数 ti−1, wi−1，含义如题所示。

第 n+2 行至第 n+m+1 行，每行两个整数 Ti−n−1, Wi−n−2，含义如题所示。

第 n+m+2 行至第 n+2m+1 行，每行 n 个整数，第 j 个数 dj 表示招牌菜 i−n−m−1 需要 dj 个食材 j。

\(\color{blue} \text {【输出】}\)

对于每组数据，输出一行一个整数，表示你所能赚到的最多的钱。

\(\color{blue} \text {【输入样例】}\)

3
1 1 48
2 2000
9 21864 5
4 4 46
17 52
4 36
5 43
16 62
9 31659
1 20431
4 623
1 11961
4 5 3 5
5 4 3 4
3 3 3 3
4 4 5 5
10 0 48
10 41
18 48
2 14
22 65
12 77
7 48
4 85
2 61
24 85
8 34

\(\color{blue} \text {【输出样例】}\)

53728
410
1464

\(\color{blue} \text {【提示】}\)

数据范围

对于 100% 的数据，保证 0<ti,Ti≤Tmax≤5000,0≤wi,Wi≤109，每份招牌菜使用的食材的个数总数不超过 105。

\(\color{blue} \text {【解题思路】}\)

这题认真分析一下就可以发现其实是一个完全背包，然后你就照着完全背包打就可以把这道题打出来了！可是注意卡常！一定要写读入优化！

AC code：

#include<bits/stdc++.h>
#define LL long long
#define N 2010
using namespace std;
LL n,m,T,lim;
LL tim1[N*3],w1[N*3],bag[N*3],tim2[N];
inline char gc() {
  static char buf[1 << 18], *fs, *ft;
  return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
inline void read(LL &aa) {
  register int k = 0, f = 1;
  register char c = gc();
  for (; !isdigit(c); c = gc()) if (c == '-') f = -1;
  for (; isdigit(c); c = gc()) k = (k << 3) + (k << 1) + (c - '0');
  aa=k * f;
}
void check1();
void init()
{
    memset(bag,0,sizeof(bag));
//  scanf("%lld%lld%lld",&n,&m,&lim);
    read(n);read(m);read(lim);
    for(int i=1;i<=n;++i) read(tim1[i]),read(w1[i]);//scanf("%lld%lld",&tim1[i],&w1[i]);
    if(m==0)
    {
        check1();
    }
    else
    {
        for(int i=1;i<=m;++i) read(tim2[i]),read(w1[i+n]);//scanf("%lld%lld",&tim2[i],&w1[i+n]);
        LL a;
        for(int i=1;i<=m;++i) 
        {
            tim1[i+n]=tim2[i];
            for(int j=1;j<=n;++j)
            read(a)/*scanf("%lld",&a)*/,tim1[i+n]+=a*tim1[j];
        }
        check1();
    }
}
int main()
{
    //freopen("restaurant.in","r",stdin);freopen("restaurant.out","w",stdout);
    read(T);
    for(int i=1;i<=T;++i) init();
    //fclose(stdin);fclose(stdout);
    return 0;
}
void check1()
{
    for(int i=1;i<=n+m;++i)
    {
        for(int j=0;j<=lim;++j)
        {
            if((j==0||bag[j])&&j+tim1[i]<=lim)
            bag[j+tim1[i]]=max(bag[j+tim1[i]],bag[j]+w1[i]);
        }
    }
    LL maxx=0;
    for(int i=1;i<=lim;++i) maxx=max(maxx,bag[i]);printf("%lld\n",maxx);
}
/* 
1
1 1 48
2 2000
9 21864
5
*/

\(\color{blue} \text {烯烃 (olefin)}\)

\(\color{blue} \text {【题目描述】}\)

银企鹅非常擅长化学。有一天他在试图命名一个巨大的单烯烃分子的时候，想到了一个问题。

给你一棵树，一些边有标记，对于每条有标记的边，在树中找到包含这条边的一条最长链，并输出长度。

\(\color{blue} \text {【输入】}\)

第一行一个整数 id 表示测试点的编号。

多组数据，第二行一个整数 T 表示数据组数。

对于每组数据，第一行两个整数 n, m 表示节点的个数，和被标记的边的个数。

我们规定 1 是根，第二行 n−1 个整数给出 2 ∼ n 父亲的编号，保证fai<i。

第三行 m 个整数范围在 [2, n] 表示哪个点的父边被标记过。

\(\color{blue} \text {【输出】}\)

对于每组数据输出一行 m 个整数，必须与输入的边顺序一致，给出的是在这条边必选的情况下树中最长链的长度。

\(\color{blue} \text {【输入样例】}\)

0
1
10 3
1 2 3 1 4 6 7 3 8
10 7 9

\(\color{blue} \text {【输出样例】}\)

8 8 6

\(\color{blue} \text {【提示】}\)

1e5

\(\color{blue} \text {【解题思路】}\)

这道题一看就是一个非常明显的一个树上DP，只要我们能够注意到一个细节就是，节点编号从小到大的顺序就是从根节点到叶节点的顺序就可以了，这样可以节省一些代码，我们正序跑就是从根跑到叶节点，反过来就是从叶节点跑到根节点。

d1记录从叶节点到当前节点的最长距离，d2记录次长距离，u记录可行的第二长的路径，然后我们这样思考完了以后这道题相应的也就做出来了。

为什么我们要记录可行的第二长路径，是因为我们有可能最长路径会和第二长路径部分重合，然后求出来的最长路就不满足要求！

AC code：

/*
    Name: olefin
    Copyright: lv
    Author:Mudrobot
    Date: 2018/10/10 17:03:44
    Description: tree dp
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define N 100005
using namespace std;
/*inline char gc() {
  static char buf[1<<18],*fs,*ft;
  return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
inline void read(int &aa) {
  register int k=0,f=1;
  register char c=gc();
  for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
  for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
  aa=k * f;
}
inline void out(int x){if(x>9)out(x/10);putchar(x%10+'0');}
int id,T,n,m,fa[N],d1[N],d2[N],u[N],x;
inline void clean()
{
    memset(fa,0,sizeof(fa));memset(d1,0,sizeof(d1));
    memset(d2,0,sizeof(d2));memset(u,0,sizeof(u));
}
int main()
{
    //freopen(".in", "r", stdin);freopen(".out", "w", stdout);
    read(id);read(T);
    while(T--)
    {
        clean();read(n);read(m);
        for(int i=2;i<=n;++i) read(fa[i]);
        for(int i=n;i>=1;--i) 
        if(d1[i]+1>=d1[fa[i]]) d2[fa[i]]=d1[fa[i]],d1[fa[i]]=d1[i]+1;
        else if(d1[i]+1>d2[fa[i]])d2[fa[i]]=d1[i]+1;
        for(int i=2;i<=n;++i)
        if(d1[fa[i]]==d1[i]+1) u[i]=max(u[fa[i]]+1,d2[fa[i]]+1);
        else u[i]=max(u[fa[i]]+1,d1[fa[i]]+1);
        for(int i=1;i<=m;++i) {read(x);out(d1[x]+u[x]);if(i!=m)printf(" ");}
        if(m!=0)printf("\n");
    }
    //fclose(stdin);fclose(stdout);
    return 0;
}
/*

*/

T3好像有一点超纲，所以这里并没有做。

Day 2

\(\color{blue} \text {锻造}\)

\(\color{blue} \text {【题目描述】}\)

勇者虽然武力值很高，但在经历了多次战斗后，发现怪物越来越难打，

于是开始思考是不是自己平时锻炼没到位，于是苦练一个月后发现……自

己连一个史莱姆都打不过了。

勇者的精灵路由器告诉勇者其实是他自己的武器不好，并把他指引到

了锻造厂。

“欢迎啊，老朋友。”

一阵寒暄过后，厂长带他们参观了厂子四周，并给他们讲锻造的流程。

“我们这里的武器分成若干的等级，等级越高武器就越厉害，并且对每

一等级的武器都有两种属性值 b 和 c，但是我们初始只能花 a 个金币来生

产 1 把 0 级剑……”

“所以你们厂子怎么这么垃圾啊，不能一下子就造出来 999 级的武器

吗？”勇者不耐烦的打断了厂长的话。

“别着急，还没开始讲锻造呢……那我们举例你手中有一把 x 级武器和

一把 y 级武器 (y = max(x − 1, 0))，我们令锻造附加值 k = min(cx, by)，则

你有 k

cx 的概率将两把武器融合成一把 x + 1 级的武器。”

“……但是，锻造不是一帆风顺的，你同样有 1 −

k

cx 的概率将两把武器

融合成一把 max(x − 1, 0) 级的武器……”

勇者听完后暗暗思忖，他知道厂长一定又想借此机会坑骗他的零花钱，

于是求助这个村最聪明的智者——你，来告诉他，想要强化出一把 n 级的

武器，其期望花费为多少？

由于勇者不精通高精度小数，所以你只需要将答案对 998244353(7 ×

17 × 2

23 + 1，一个质数 ) 取模即可。

\(\color{blue} \text {【输入】}\)

第一行两个整数 n, a，含义如题所示。

为了避免输入量过大，第二行五个整数 bx, by, cx, cy, p，按照下列代码

来生成 b 和 c 数组。

b[0]=by+1;c[0]=cy+1;

for(int i=1;i

b[i]=((long long)b[i-1]*bx+by)%p+1;

c[i]=((long long)c[i-1]*cx+cy)%p+1;

}

\(\color{blue} \text {【输出】}\)

输出一行一个整数，表示期望花费。

\(\color{blue} \text {【输入样例】}\)

10 2
2 33 6 66 2333333

\(\color{blue} \text {【输出样例】}\)

976750710

\(\color{blue} \text {【提示】}\)

无

\(\color{blue} \text {【解题思路】}\)

摘自TTL

【解题思路】
不难得出这道题需要dp；
但怎么避免后效性？我们发现对于一次失败的操作，会产生一个\(i-1\)级的武器，是不是相当于\(i-1\)的武器有无数个，那么期望花费则只与\(i\)有关，转移方程就是\(f[i]=(\frac{1}{p})f[i-1]+f[i-2]\),p表示\(i-1\)制造成功的概率，以为有\(\frac{1}{p}\)所以我们需要求逆元，线性递推逆元；

#include<bits/stdc++.h>
using namespace std;
int dp[10000010],ny[10000010];
int b[10000010],c[10000010];
const int mod=998244353;
int n,a,bx,by,cx,cy,p;
void init() { 
    ny[0]=ny[1]=1;
    for(register int i=2;i<=10000000;++i) { 
        ny[i]=(long long)ny[mod%i]*(mod-(mod/i))%mod;
    } 
    return;
} 

void make() { 
    b[0]=by+1;c[0]=cy+1;
    for(int i=1;i<n;i++) { 
        b[i]=((long long)b[i-1]*bx+by)%p+1;
        c[i]=((long long)c[i-1]*cx+cy)%p+1;
    } 
    return;
} 

int main() { 
    cin>>n>>a;
    cin>>bx>>by>>cx>>cy>>p;
    init();
    make();
    dp[0]=a;
    //dp[1]=1ll*(1ll*c[0]*ny[min(b[0],c[0])]%mod+1)*dp[0]%mod;
    register int k;
    for(int i=1;i<=n;++i) { 
        k=min(c[i-1],b[max(0,i-2)]);
        dp[i]=(1ll*(1ll*(1ll*c[i-1]*ny[k]%mod)*dp[i-1]%mod)+dp[max(i-2,0)])%mod;
    } 
    cout<<dp[n];
    return 0;
}

\(\color{blue} \text {整除}\)

\(\color{blue} \text {【题目描述】}\)

整除符号为 |，d|n 在计算机语言中可被描述为 n%d == 0。

现有一算式 n|x

m − x，给定 n，m，求 [1, n] 以内 x 解的个数。

解可能很大，输出取模 998244353。

\(\color{blue} \text {【输入】}\)

其中 n 的给定方式是由 c 个不超过 t 的质数的乘积给出的，c 和 t 的

范围会在数据范围中给出。

第一行一个 id 表示这个数据点的标号。

多组数据，其中第二行一个整数 T 表示数据组数。

对于每一组数据：

第一行两个整数 c 和 m。

第二行 c 个整数，这些整数都是质数，且两两不同，他们的乘积即为

n。

由于你可以通过输入求出 t，输入不再给出。

\(\color{blue} \text {【输出】}\)

对于每组数据输出一行，表示解的个数。

\(\color{blue} \text {【输入样例】}\)

0
1
2 3
2 3

\(\color{blue} \text {【输出样例】}\)

6

\(\color{blue} \text {【提示】}\)

无

\(\color{blue} \text {【解题思路】}\)

这道题要用到一些神奇的数学方法，主要是积性筛（实现方法和线性筛素数是一样的，相信大家认真阅读一下代码是可以看懂的，最后答案借助CRT乘一下就好了！）

AC code：

/*
    Name: division 
    Copyright: ssy
    Author: Mudrobot
    Date: 2018/10/11 20:59:16
    Description: exgcd CRT
*/
#include<bits/stdc++.h>
#define gc() getchar()//caution!!!
#define LL long long
#define MOD 998244353
#define N 10004
using namespace std;
/*inline char gc() {
  static char buf[1<<18],*fs,*ft;
  return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}*/
template<class T>
inline void read(T &aa) {
  register int k=0,f=1;
  register char c=gc();
  for (;!isdigit(c);c=gc()) if(c=='-')f=-1;
  for (;isdigit(c);c=gc()) k=(k<<3)+(k<<1)+(c-'0');
  aa=k*f;
}
template<class T>
inline void out(T x){if(x>9)out(x/10);putchar(x%10+'0');}
int id,T,c,m,ksm[N],zs[N];
bool mark[N];
int fpow(int x,int k,int p){int v=1;
    while(k){
        if(k&1)v=v*x%p;
        k>>=1,x=x*x%p;
    }return v;
}//BY Lys
int calc(int p)
{
    int ans=2,cnt=0;//因为一定有自身和1
    memset(mark,false,sizeof(mark));
    for(int i=2;i<=10000;++i)//注意题目要求范围 
    {
        if(!mark[i])zs[++cnt]=i,ksm[i]=fpow(i,m,p);
        for(int j=1;j<=cnt&&i*zs[j]<=10000;++j)
        {
            mark[i*zs[j]]=true;
            ksm[i*zs[j]]=ksm[i]*ksm[zs[j]]%p;
            if(!i%zs[j])break;//防止重复！ 
        }
        if(ksm[i]%p==i) ans++;
    }
    return ans;
}
int main()
{
    //freopen(".in", "r", stdin);freopen(".out", "w", stdout);
    read(id);read(T);
    for(int u=1;u<=T;++u) 
    {
        int ans=1;read(c);read(m);
        for(int i=1;i<=c;++i)
        {
            int a;read(a);
            ans=((LL)ans*calc(a))%MOD;
        }
        out(ans);putchar('\n');
    }
    //fclose(stdin);fclose(stdout);
    return 0;
}
/*
0
1
2 3
2 3
*/

本人太菜 T3出来！

原文链接: https://www.cnblogs.com/mudrobot/p/13329044.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    凉心模拟总结

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/367809

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午5:59
下一篇 2023年3月2日 下午6:00

相关推荐