首页 > 编程札记 > 编程

【LGR

阅读：评论：0

【LGR

【LGR-166-Div.4】洛谷入门赛 #17

比赛地址

这次是div4的难度，整体不算是很难，很适合小白玩家

[10 月入门赛-A] 食堂

题目描述

为了给师生提供良好的用餐体验，洛谷小学的食堂坚持现炒、现做每一道菜肴。

洛谷小学一共有 a a a 名老师和 b b b 名学生。食堂的营养师为每位师生的用餐进行配额：

一名学生，一次用餐需要 R R R 克米饭， V V V 克蔬菜， M M M 克肉。
一名老师，一次用餐需要 2 R 2R 2R 克米饭， 3 V 3V 3V 克蔬菜， 3 M 3M 3M 克肉。

洛谷小学的食堂一天需要烹制两餐，分别为中午一餐、晚上一餐。其中，中午的一餐，学生和老师都需要，而晚上的一餐仅有老师需要。

现在请问，洛谷小学的食堂，一天要准备多少克米饭，多少克蔬菜，多少克肉呢？

输入格式

输入一行，五个正整数 a , b , R , V , M a,b,R,V,M a,b,R,V,M，分别表示老师的人数、学生的人数，以及一名学生一次用餐需要的米饭、蔬菜和肉的量。

输出格式

输出一行，三个正整数，分别表示洛谷小学的食堂一天要准备多少克米饭，多少克蔬菜，多少克肉。

样例 #1

样例输入 #1

5 10 200 100 150

样例输出 #1

6000 4000 6000

样例 #2

样例输入 #2

15 120 150 200 180

样例输出 #2

27000 42000 37800

提示

【样例解释】

对于样例 1 1 1，洛谷小学有 5 5 5 个老师和 10 10 10 个学生。每天每个学生吃 1 1 1 餐，每个老师吃 2 2 2 餐，因此：

一个学生一餐吃 200 200 200 克米饭。因此需要准备： 1 × 10 × 200 + 2 × 5 × 400 = 6000 1times 10times 200+2times 5times 400=6000 1×10×200+2×5×400=6000 克米饭。
一个学生一餐吃 100 100 100 克蔬菜。因此需要准备： 1 × 10 × 100 + 2 × 5 × 300 = 4000 1times 10times 100+2times 5times 300=4000 1×10×100+2×5×300=4000 克蔬菜。
一个学生一餐吃 150 150 150 克肉，因此需要准备： 1 × 10 × 150 + 2 × 5 × 450 = 6000 1times 10times 150+2times 5times 450=6000 1×10×150+2×5×450=6000 克肉。

因此，输出 6000 , 4000 , 6000 6000,4000,6000 6000,4000,6000。

【数据范围】

对于所有数据，保证： 1 ≤ a , b , R , V , M ≤ 10000 1leq a,b,R,V,M leq 10000 1≤a,b,R,V,M≤10000。

思路：

基本上就是一个比较简单的模拟，读懂题意就可以做了

代码：

#include<bits/stdc++.h>
using namespace std;
void solve(){int a,b,r,v,m;cin>>a>>b>>r>>v>>m;r=r*b+r*2*a*2;v=v*b+v*3*a*2;m=m*b+m*3*a*2;cout<<r<<" "<<v<<" "<<m<<endl;return ;}
int main(){int t=1;while(t--){solve();} return 0;
}

[10 月入门赛-B] 数学选择题

题目描述

洛谷小学的数学考试由若干道选择题组成。选择题分为三档：简单题、中等题和困难题。每类题目都有评判标准：

简单题：回答正确得 5 5 5 分，回答错误则不得分；
困难题：回答正确得 20 20 20 分，回答错误倒扣 20 20 20 分；

洛谷小学不鼓励学生为了做困难题而忽视基础，因此，如果简单题得到的总分，不超过给定的分值限制 M M M 时，做困难题回答正确不得分，而回答错误一样倒扣 20 20 20 分。同时，为了照顾学生情绪，如果学生所有题累计的得分小于 0 0 0，则按照 0 0 0 分计算。

现在给定试卷中简单题的题数 a a a，困难题的题数 b b b，以及小 A 做对的简单题的题数 c c c，困难题的题数 d d d，以及给定的分值限制 M M M。问，小 A 最终能获得几分。

输入格式

输入一行，五个正整数 a , b , c , d , M a,b,c,d,M a,b,c,d,M，分别表示试卷中简单题的题数、困难题的题数、小 A 做对的简单题的题数、小 A 做对的困难题的题数以及给定的分值限制。

输出格式

输出一行一个整数，表示小 A 最终能获得几分。

样例 #1

样例输入 #1

10 5 7 4 30

样例输出 #1

样例 #2

样例输入 #2

10 5 7 4 40

样例输出 #2

样例 #3

样例输入 #3

10 5 7 1 40

样例输出 #3

提示

【样例解释】

对于样例 1 1 1，小 A 做对了 7 7 7 道简单题获得了 35 35 35 分，超过了给定的 30 30 30 分限制，因此会正常计算困难题的得分。小 A 做对了 4 4 4 个困难题获得 80 80 80 分，但是错了一道要倒扣 20 20 20 分，因此合计为 35 + 80 − 20 = 95 35+80-20=95 35+80−20=95 分。
对于样例 2 2 2，小 A 做对了 7 7 7 道简单题获得了 35 35 35 分，并未超过给定的阈值 40 40 40，因此只计算做错困难题的倒扣分，合计为 35 − 20 = 15 35-20=15 35−20=15 分。
对于样例 3 3 3，与样例 2 2 2 一样，只计算做错困难题的倒扣分。小 A 只做对了 1 1 1 个困难题，要倒扣 80 80 80 分。此时小 A 累计的得分小于 0 0 0，则按照 0 0 0 分作为最后的分值。

【数据范围】

对于所有数据，保证： 1 ≤ a , b , c , d ≤ 100 1 leq a,b,c,d leq 100 1≤a,b,c,d≤100， 1 ≤ c ≤ a 1 leq c leq a 1≤c≤a， 1 ≤ d ≤ b 1 leq d leq b 1≤d≤b， 1 ≤ M ≤ 500 1 leq M leq 500 1≤M≤500。

思路：

也是一个比较简单的模拟，理清楚思路即可顺利解决

代码：

#include<bits/stdc++.h>
using namespace std;
void solve(){int a,b,c,d,m;cin>>a>>b>>c>>d>>m;// int ans=0;int res=c*5;if(res<=m){res-=(b-d)*20;if(res<=0){cout<<0<<endl;return ;}else{cout<<res<<endl;return ;}}else{res+=d*20-(b-d)*20;if(res<=0){cout<<0<<endl;return ;}else{cout<<res<<endl;return ;}}}
int main(){int t=1;while(t--){solve();}return 0;}

[10 月入门赛-C] 风球

题目背景

与中国大陆不同，当台风即将来袭时，香港天文台将会根据情况发布 1 , 3 , 8 , 9 , 10 1,3,8,9,10 1,3,8,9,10 五个等级的热带气旋警告信号。数字越大，代表台风影响越严重。当发布 8 8 8 号烈风信号时，香港就会停课停工。下图为香港天文台的 10 10 10 号飓风信号：

题目描述

香港天文台选定了 8 8 8 个气象站。在台风影响期间，香港天文台会根据这些气象站的风速观测数据决定发布哪一个等级的预警。

因为已经受到台风影响，因此必然会发布 1 1 1 号戒备信号；
若有 4 4 4 个气象站的持续风力达到或超过 41 41 41 千米/小时，则发布 3 3 3 号强风信号；
若有 4 4 4 个气象站的持续风力达到或超过 63 63 63 千米/小时，则发布 8 8 8 号烈风信号；
若有 1 1 1 个气象站的持续风力达到或超过 118 118 118 千米/小时，则发布 10 10 10 号飓风信号；
多个条件同时满足，则发布其中最高等级的信号。

现在给定这些气象站的风力数据，请计算出香港天文台应当发布什么警告信号。

输入格式

输入共一行，用空格隔开的 8 8 8 个正整数，表示这 8 8 8 个气象站的风速观测数据。

输出格式

输出一行一个正整数，表示应当发布哪一个等级的警告信号。

样例 #1

样例输入 #1

126 75 94 57 53 81 50 48

样例输出 #1

样例 #2

样例输入 #2

76 40 49 36 26 42 27 26

样例输出 #2

样例 #3

样例输入 #3

99 83 96 54 63 59 45 55

样例输出 #3

提示

【样例解释】

第一组样例中，第一个气象观测站观测到了超过 118 118 118 千米/小时的风速，因此应当发布 10 10 10 号飓风信号。此为 2023 年超强台风苏拉影响香港的真实风速数据。

第二组样例中，只有 3 3 3 个气象观测站的持续风力达到或超过 41 41 41 千米/小时，因此只符合 1 1 1 号戒备信号的标准。此为 2023 年强台风小犬影响香港的真实风速数据。

第三组样例中，恰好有 4 4 4 个（第 1 , 2 , 3 , 5 1,2,3,5 1,2,3,5 个）气象观测站的持续风力达到或超过 63 63 63 千米/小时，因此符合 8 8 8 号烈风信号的标准。此为 2008 年台风鹦鹉登陆香港的真实风速数据。

【数据范围】

对于所有风速观测数据 x x x，满足 1 ≤ x ≤ 300 1 leq x leq 300 1≤x≤300。

思路：

这也是模拟题，只要不满足那三种情况直接输出1就好了

代码：

#include<bits/stdc++.h>
using namespace std;
void solve(){int ans1,ans2,ans3;ans1=ans2=ans3=0;for(int i=1;i<=8;i++){int a;cin>>a;if(a>=41){ans1++;}if(a>=63){ans2++;}if(a>=118){ans3++;}}if(ans3>=1){cout<<10<<endl;return ;}if(ans2>=4){cout<<8<<endl;return ;}if(ans1>=4){cout<<3<<endl;return ;}else{cout<<1<<endl;return ;}
}
int main(){int t=1;while(t--){solve();}return 0;
}

[10 月入门赛-D] 画图练习

题目描述

为了培养学生的兴趣，洛谷小学的信息课上会教学生使用绘板软件，让学生在电脑上自由创作图画。

小 A 非常喜欢字符画。他打算在课上创作一幅自己的字符画。他的字符画一共有 n n n 行，绘画规则如下：

第 i i i 行的非空格的字符有 i 2 i^2 i2 个；
第 i i i 行以大写的第 i i i 个英语字母开头。每一列用其前一非空格列的字母的下一个填充。特别地，Z 的下一个字母是 A。
如果当前列数加上当前本应填充的字母的 ASCII 码不为质数，则跳过该列（用空格填充），直到列数加上本应填充的字母的 ASCII 码为质数为止。

请绘画出小 A 的字符画。

输入格式

输入一个正整数 n n n，表示这是一个 n n n 行的字符画。

输出格式

输出 n n n 行字符，表示这是小 A 创作的字符画。

样例 #1

样例输入 #1

样例输出 #1

A
B  CD    ECD    E  F    G      H  IJ  K

样例 #2

样例输入 #2

样例输出 #2

A
B  CD    ECD    E  F    G      H  IJ  KDE    F  G    H      I  JK  LM  N            O  P    QR        SEF    G  H    I      J  KL  MN  O            P  Q    RS        TU    V    W  X    Y    Z  A    B  C
FG    H  I    J      K  LM  NO  P            Q  R    ST        UV    W    X  Y    ZAB    C    D  E    F    GH        IJ  KL          M          N  O

提示

【样例解释】

对于样例 1 1 1：

第一行应当以第一个大写字母，即 A 开头。但是 A 的 ASCII 码是 65 65 65，加上列数 1 1 1，为 66 66 66，其并不是质数（ 66 = 2 × 3 × 11 66=2times 3times 11 66=2×3×11），因此第一列为空。而第二列， 65 + 2 = 67 65+2=67 65+2=67，为质数，因此在第二列输出 A。此时已经输出了 1 2 1^2 12 个字母，故换行。
第二行应当以第二个大写字母，即 B 开头。B 的 ASCII 码是 66 66 66，加上列数 1 1 1，为 67 67 67，为质数。因此第一列就输出 B。随后应当输出下一个英语字母 C。C 的 ASCII 码为 67 67 67，加上列数 2 2 2，为 69 = 3 × 23 69=3times 23 69=3×23，不为质数，用空格跳过。而直到第四列， 67 + 4 = 71 67+4=71 67+4=71 为质数，因此在第四列输出 C。同理，在第五列输出 D，在第 10 10 10 列输出 E。

对于样例 2 2 2：

该样例的第五第六行体现了 Z 的下一个字母是 A。

【数据范围】

对于所有数据， 1 ≤ n ≤ 26 1leq nleq 26 1≤n≤26。

思路：

简单的模拟，记住Z后面还是A就好了，也就是说需要做一个取模运算,一开始我以为是两个数互质，没有读懂题，后来才发现是两个数的和是质数。

代码：

#include<bits/stdc++.h>
using namespace std;
bool prime(int x){if(x==1||x==0){return 0;}for(int i=2;i<=sqrt(x);i++){if(x%i==0){return 0;}}return 1;}
void solve(){int n;cin>>n;for(int i=1;i<=n;i++){char a='A'+(i-1)%26;int k=1;for(int j=1;j<=i*i;){if(prime(a+k)==1){cout<<a;if(a=='Z'){a='A';}else{a++;} // if(a=='Z')j++;}else{cout<<" ";}k++;}cout<<endl;}return ;}
int main(){int t=1;while(t--){solve();}return 0;
}

[语言月赛 202311] 基因

题目描述

有一个长度为 n n n 的字符串 S S S。其只包含有大写字母。

小 A 将 S S S 进行翻转后，得到另一个字符串 S ′ S' S′。两个字符串 S S S 与 S ′ S' S′ 对应配对。例如说，对于 S = A T C G T S=tt{ATCGT} S=ATCGT，则有 S ′ = T G C T A S'=tt{TGCTA} S′=TGCTA， S S S 与 S ′ S' S′ 进行配对。

对于两个字符串 S , S ′ S,S' S,S′ 的第 i i i（ 1 ≤ i ≤ n 1 leq i leq n 1≤i≤n）个字母，配对规则如下：

定义 A tt A A 与 T tt T T， C tt C C 与 G tt G G 为可以配对的字母。
如果 S i S_i Si 与 S i ′ S_i' Si′ 为可以配对的字母，那么该字符串的稳定性增加 i i i。
如果 S i S_i Si 或者 S i ′ S_i' Si′ 中任意一方出现非 A , T , C , G tt A,tt T,tt C,tt G A,T,C,G 的字母，则整个字符串的稳定性将直接为 0 0 0。

现在给定 T T T 个字符串 S S S，对每一个字符串，询问若用其翻转再进行配对，其稳定性将如何。

输入格式

第一行输入一个正整数 T T T，表示给定多少个字符串。对于每一个字符串：

第一行输入一个正整数 n n n，表示字符串的长度；
第二行输入一个字符串 S S S，表示该字符串。

输出格式

对于每个字符串，输出一行一个整数，表示若用其翻转再进行配对，其稳定性将如何。

样例 #1

样例输入 #1

3
5
ATCGT
6
ACATGT
5
ATCGU

样例输出 #1

6
21
0

提示

【样例解释】

对于第一个字符串， S = A T C G T S=tt{red{A}TCGblue{T}} S=ATCGT， S ′ = T G C T A S'=tt{red{T}GCTblue{A}} S′=TGCTA。标红色的一组与蓝色的一组为可以配对的字母。它们分别是 S S S 的第 1 1 1 个字母和第 5 5 5 个字母，因此稳定性是 1 + 5 = 6 1+5=6 1+5=6。
对于第二个字符串， S = A C A T G T S=tt{red{A}blue{C}red{A}blue{T}red{G}blue{T}} S=ACATGT， S ′ = T G T A C A S'=tt{red{T}blue{G}red{T}blue{A}red{C}blue{A}} S′=TGTACA，每个对应位置上的字母都可以配对，因此稳定性是 1 + 2 + 3 + ⋯ + 6 = 21 1+2+3+dots+6=21 1+2+3+⋯+6=21
对于第三条字符串，出现了非 A , T , C , G tt A,tt T,tt C,tt G A,T,C,G 的字母 U tt U U，因此稳定性为 0 0 0。

【数据范围】

对于所有数据，保证： 1 ≤ T ≤ 5 1leq Tleq 5 1≤T≤5， 1 ≤ n ≤ 1 0 5 1leq nleq 10^5 1≤n≤105， S S S 中出现的所有字母保证为大写英语字母。

思路：

可以考虑使用map对字符进行一下哈希，这样我们就可以保证其有对应关系，我们可以使用字符串反转函数进行反转，之前一直没注意本题的数据范围大小是需要开long long的

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;void solve(){int n=0;// mp['A']=mp['T']=1;// mp['C']=mp['G']=2;std::map<char, int> mp;cin>>n;string s="";cin>>s;s=" "+s;n+=1;// cout<<s<<endl;mp['A']=mp['T']=1;mp['C']=mp['G']=2;ll res=0;for(int i=1;i<n;i++){if(s[i]!='A'&&s[i]!='T'&&s[i]!='C'&&s[i]!='G'){cout<<0<<endl;return ;}}string s1=s;// cout<<s1<<endl;// cout<<s<<endl;reverse(s.begin(),s.end());// cout<<s<<endl;s=" "+s;for(int i=1;i<n;i++){if(mp[s[i]]==mp[s1[i]]&&s[i]!=s1[i]){// cout<<i<<endl;res+=i;}}cout<<res<<endl;return ;
}
int main(){int t=1;cin>>t;while(t--){solve();}return 0;}

[语言月赛 202311] 式神考核

题目背景

作为隙间妖怪的式神的式神，橙自然需要接受蓝的考核。源于八云紫的严格要求被蓝带给了橙喵。橙喵在考核中不仅要接受精神的摧残，也要经历肉体的考验，以此得到启发，成为动物妖怪中首屈一指的存在。

题目描述

蓝给橙喵的考核题一共有 n n n 道，总分为 1 0 7 10^7 107 分，每道题的分值为 1 0 7 n dfrac {10^7} n n107。根据橙喵的完成情况，蓝可能会给出满分、给出一半的分数或不得分。另外，在所有获得满分的题目中，有一部分橙喵完成得特别好，因此蓝给她加上了每道题 1 1 1 分的附加分。由于橙喵得到的分数可能是个小数，因此蓝决定将分数下取整得到最后的总分。

在橙喵完成了所有的考核之后，蓝给出了未得到满分的题目数量 m m m 和加上附加分的总分 s s s。蓝希望橙喵告诉她，每种得分的题目分别有几道。

橙喵被难住了，因此找到了你，希望你写一个程序帮帮她。
可以证明的是，在这样的规则和数据范围下，答案是唯一的。

输入格式

一行三个整数 n n n， s s s， m m m。

输出格式

蓝希望你按照 pA(+B) fC lD 的格式给出可能的答案，其中 A , B , C , D A,B,C,D A,B,C,D 均为整数， A A A 为所有得满分的题目总数， B B B 为获得附加分的题目数量， C C C 为获得一半分的题目数量， D D D 为不得分的题目数量。保证有一个可行解。

样例 #1

样例输入 #1

1475 9909870 16

样例输出 #1

p1459(+1396) f5 l11

提示

【样例解释】

一共有 1475 1475 1475 道试题，其中 1459 1459 1459 题得到了满分，且 1396 1396 1396 题得到了额外的 1 1 1 分； 5 5 5 题得到了一半的分数， 11 11 11 题未得分。可知得分为：

1 0 7 1475 × 1459 + 1396 + 1 2 × 1 0 7 1475 × 5 = 9909870.576271 dfrac{10^7}{1475}times 1459+1396+dfrac{1}{2}times dfrac{10^7}{1475}times 5=9909870.576271 1475107×1459+1396+21×1475107×5=9909870.576271，下取整为 9909870 9909870 9909870。

【数据范围】

对于 100 % 100% 100% 的数据，保证 1 ≤ m ≤ n ≤ 2221 1 le m le n le 2221 1≤m≤n≤2221， 1 ≤ s ≤ 1 0 7 + n 1 le s le 10^7+n 1≤s≤107+n。

代码：

#include<bits/stdc++.h>
using namespace std;
void solve(){int n,s,m;cin>>n>>s>>m;int a,b,c,d;double ans=1.0*10000000/n;double ans1=ans*(n-m);for(int i=0;i<=m;i++){double res=ans1+1.0/2*ans*i;if(floor(res)<=s&&s<=floor(res+(n-m))){cout<<"p"<<n-m<<"(+"<<ceil(s-res)<<") f"<<i<<" l"<<m-i<<endl;return ;}}a=n-m;}
int main(){int t=1;while(t--){solve();}return 0;}

[语言月赛 202311] 表格处理

题目描述

小 A 有一张 2 × n 2times n 2×n 行， 2 × m 2times m 2×m 列的表格。表格上每一行、每一列都有一个正整数。他将对表格先进行一次合并操作，再进行一次转置操作。

对于一个 2 × n 2times n 2×n 行， 2 × m 2times m 2×m 列的表格 A A A，进行一次合并操作得到一个 n n n 行 m m m 列的表格 A ′ A' A′ 的流程为：

将奇数列的每个数加上其右侧相邻的数，之后删除所有的偶数列，给每一列重新编号为第 1 , 2 , 3 , … , m 1,2,3,dots,m 1,2,3,…,m 列；
将奇数行的每个数加上其下侧相邻的数，之后删除所有的偶数行，给每一行重新编号为第 1 , 2 , 3 , … , n 1,2,3,dots,n 1,2,3,…,n 行；

对于一个 n n n 行 m m m 列的表格 A A A，进行一次转置操作得到一个 m m m 行 n n n 列的表格 A T A^T AT 的流程为：

对于所有的 i , j i,j i,j，令 A i , j T = A j , i A^T_{i,j}=A_{j,i} Ai,jT=Aj,i；

小 A 想要知道经过这样两次操作后表格会是什么样的。请输出该表格。

本题的输入输出规模较大，特别是对使用 Java/Python 等非传统语言的选手，请使用相对快速的输入输出方式。

输入格式

第一行输入两个正整数 n n n 和 m m m。

第二行到第 2 × n + 1 2times n+1 2×n+1 行，每行输入 2 × m 2times m 2×m 个正整数，表示表格上每一行每一列的值。

输出格式

输出一个 m m m 行 n n n 列的表格，表示经过两次操作后表格会是什么样的。同一行内的正整数之间用空格隔开。

样例 #1

样例输入 #1

样例输出 #1

18 18
19 13

样例 #2

样例输入 #2

3 3
6 2 3 5 3 2
1 3 1 4 5 2
7 8 7 8 5 6
2 8 3 6 4 8
9 2 1 8 7 5
4 2 4 3 5 1

样例输出 #2

12 25 17
13 24 16
12 23 18

提示

【样例解释】

对于样例一给出的表格，其是经过这些变换得到的：

[ 2 7 1 8 1 8 2 8 3 1 4 1 5 9 2 6 ] 删除列 → [ 9 9 9 10 4 5 14 8 ] 删除行 → [ 18 19 18 13 ] 转置 → [ 18 18 19 13 ] begin{bmatrix}2 & 7 & 1 & 8 \ 1 & 8 & 2 & 8 \ 3 & 1 & 4 & 1 \ 5 & 9 & 2 & 6 end{bmatrix} underrightarrow{删除列} begin{bmatrix} 9 & 9 \ 9 & 10 \4 & 5 \ 14 & 8 \end{bmatrix} underrightarrow{删除行} begin{bmatrix} 18 & 19 \ 18 & 13end{bmatrix} underrightarrow{转置} begin{bmatrix} 18 & 18 \19 & 13end{bmatrix} 2135781912428816 删除列 9941491058 删除行[18181913] 转置[18191813]

【数据范围】

对于所有数据，保证： 1 ≤ n , m ≤ 1000 1 leq n,m leq 1000 1≤n,m≤1000， 1 ≤ a i ≤ 1 0 6 1 leq a_i leq 10^6 1≤ai≤106。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int a[N][N];
int b[N][N];void solve(){int n,m;cin>>n>>m;for(int i=1;i<=2*n;i++){for(int j=1;j<=2*m;j++){cin>>a[i][j];}}for(int i=1;i<=2*n;i+=2){for(int j=1;j<=2*m;j+=2){b[i/2+1][j/2+1]=a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1];   }}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){cout<<b[j][i]<<" ";}cout<<endl;}
}
int main(){int t=1;while(t--){solve();}return 0;}

[语言月赛 202311] 方程求解

题目描述

小 A 有 n n n 个关于 x x x 的方程，第 i i i 个方程形如 a i x i + b i = c i a_ix_i+b_i=c_i aixi+bi=ci。方程的解 x x x 均为正整数，例如下面几个方程都是符合要求的方程：

2x+4=10
-3x+13=10
4x-8=16

其中，第一组方程的解为 x 1 = 3 x_1=3 x1=3，第二组方程的解为 x 2 = 1 x_2=1 x2=1，第三组方程的解为 x 3 = 6 x_3=6 x3=6。

小 A 想要知道，给定 L , R L,R L,R，在 L ≤ x ≤ R Lleq xleq R L≤x≤R 的范围内，有多少个正整数 x x x 满足 x x x 是其中至少一个方程的解。为了防止你欺骗他，他会询问你 Q Q Q 次。

输入格式

第一行输入两个正整数 n , Q n,Q n,Q，分别表示小 A 有的方程数，以及小 A 想要向你询问的次数。

第二行开始，往下 n n n 行，每行一个字符串，描述一个方程。

第 ( n + 2 ) (n+2) (n+2) 行开始，往下 Q Q Q 行，每行两个正整数 L , R L,R L,R，表示一次询问，即给定 L , R L,R L,R，询问在 L ≤ x ≤ R Lleq xleq R L≤x≤R 的范围内，有多少个正整数 x x x 满足 x x x 是其中至少一个方程的解。

输出格式

对于每次询问，输出一行一个整数，表示有多少个在 L ≤ x ≤ R Lleq xleq R L≤x≤R 的范围内的正整数 x x x，满足 x x x 是其中至少一个方程的解。

样例 #1

样例输入 #1

3 4
2x+4=10
-3x+13=10
4x-8=16
1 6
1 8
3 6
4 5

样例输出 #1

样例 #2

样例输入 #2

5 3
5x-2=13
8x+5=45
4x-12=8
-2x+10=4
3x-7=2
1 3
1 5
3 5

样例输出 #2

1
2
2

提示

【样例解释】

对于第一组样例，即为题目中的举例。三组方程的解分别为 x 1 = 3 , x 2 = 1 , x 3 = 6 x_1=3,x_2=1,x_3=6 x1=3,x2=1,x3=6。则：

对于 1 ≤ x ≤ 6 1leq xleq 6 1≤x≤6 的范围，有 3 3 3 个 x x x 的取值（ x = 1 , 3 , 6 x=1,3,6 x=1,3,6）是其中至少一个方程的解；
对于 1 ≤ x ≤ 8 1leq xleq 8 1≤x≤8 的范围，同上所述；
对于 3 ≤ x ≤ 6 3leq xleq 6 3≤x≤6 的范围，有 2 2 2 个 x x x 的取值（ x = 3 , 6 x=3,6 x=3,6）是其中至少一个方程的解；
对于 4 ≤ x ≤ 5 4leq xleq 5 4≤x≤5 的范围，不存在一个 x x x 是其中至少一个方程的解；
因此分别输出 3 , 3 , 2 , 0 3,3,2,0 3,3,2,0。

对于第二组样例，五组方程的解分别为 x 1 = 3 , x 2 = 5 , x 3 = 5 , x 4 = 3 , x 5 = 3 x_1=3,x_2=5,x_3=5,x_4=3,x_5=3 x1=3,x2=5,x3=5,x4=3,x5=3。则：

对于 1 ≤ x ≤ 3 1leq xleq 3 1≤x≤3 的范围，只有 x = 3 x=3 x=3 满足是其中至少一个方程的解；
对于 1 ≤ x ≤ 5 1leq xleq 5 1≤x≤5 的范围，有 2 2 2 个 x x x 的取值（ x = 3 , 5 x=3,5 x=3,5）是其中至少一个方程的解；
对于 3 ≤ x ≤ 5 3leq xleq 5 3≤x≤5 的范围，有 2 2 2 个 x x x 的取值（ x = 3 , 5 x=3,5 x=3,5）是其中至少一个方程的解；
因此分别输出 1 , 2 , 2 1,2,2 1,2,2。

【数据范围】

数据保证， 1 ≤ n , Q ≤ 1000 1leq n,Qleq 1000 1≤n,Q≤1000，方程中 a i , b i , c i a_i,b_i,c_i ai,bi,ci 满足 1 ≤ ∣ a i ∣ , ∣ b i ∣ , ∣ c i ∣ ≤ 2000 1 leq |a_i|,|b_i|,|c_i| leq 2000 1≤∣ai∣,∣bi∣,∣ci∣≤2000，每一组方程的解 x i x_i xi 必定为正整数。询问时的 L , R L,R L,R 满足 1 ≤ L ≤ R ≤ 1000 1leq Lleq Rleq 1000 1≤L≤R≤1000。

本题前八个测试点每个测试点 8 分，后四个测试点每个测试点 9 分。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
//int cnt[N];
int a1[N];void solve(){int a,b,c;// char d;int n,m;set<int> s;s.clear();cin>>n>>m;for(int i=1;i<=n;i++){scanf("%dx%d=%d",&a,&b,&c);int x=(c-b)/a;// cnt[x]++;// a[i]=x;s.insert(x);}int l=0;for (auto iter = s.begin(); iter != s.end(); ++iter) {
//    	cout << *iter << endl;a1[l++]= *iter;}a1[l++]=0x3f3f3f;a1[l++]=-0x3f3f3f;sort(a1,a1+l);while(m--){int l1,r1;// int ans=0;cin>>l1>>r1;auto lt=lower_bound(a1,a1+l,l1);auto rt=upper_bound(a1,a1+l,r1);cout<<rt-lt<<endl;}//	while(m--){
//		int l,r,ans=0;
//		cin>>l>>r;
//		for(int i=l;i<=r;i++){
//			if(cnt[i]>0){
//				ans++;
//			}
//		}
//		cout<<ans<<endl;
//		
//	}
}
int main(){int t=1;while(t--){solve();}return 0;}

本文发布于:2024-01-29 00:21:21，感谢您对本站的认可！

本文链接：https://www.4u4v.net/it/170645888411365.html

上一篇：html 表格间隙颜色,javascript实现Table间隔色以及选择高亮(和动态切换数据)的方法...

下一篇：2023华数杯A 题隔热材料的结构优化控制研究(思路+代码+论文,会及时更新优化,已更新两次)

标签：LGR

留言与评论（共有 0 条评论）