在网上看到一篇较详细的讲解,觉得讲解的非常好!
pow
小文同学刚刚接触了信息学竞赛,有一天她遇到了这样一个题:给定正整数a
和b
,求a
b 的值是多少。a
b即b
个a
相乘的值,例如23
即为3
个2
相乘,结果为2x2x2=8
。
“简单!”小文心想,同时很快就写出了一份程序,可是测试时却出现了错误。
小文很快意识到,她的程序里的变量都是int
类型的。在大多数机器上,int
类型能表示的最大数为231-1,因此只要计算结果超过这个数,她的程序就会出现错误。由于小文刚刚学会编程,她担心使用int
计算会出现问题。因此她希望你在ab的值超过109时,输出一个 -1
进行警示,否则就输出正确的ab的值。
然而小文还是不知道怎么实现这份程序,因此她想请你帮忙。
输入共一行,两个正整数a,b
。
输出共一行,如果a
b的值不超过10
9,则输出ab的值,否则输出 -1
。
输入#1
10 9
输出 #1
1000000000
输入 #2
23333 66666
输出 #2
-1
对于 10%
的数据,保证b=1
。
对于30%
的数据,保证b≤2
。
对于60%
的数据,保证b≤30
,ab≤1018。
对于100%
的数据,保证1≤a,b≤109
。
对于很多普及组学生来说,本题的难度主要来自于对于数据范围的敏感程度。也就是需要学生“掐指一算”没有这个小动作习惯的同学,只能得到60分的暴力分了有这个习惯的同学,只要再“用心一想”,运转一下思维,可以想到满分思路。根据满分思路斟酌的时间不同整个题目耗费时间在10~30分钟之内基本可以完成。另外a
可以=1
是个坑点,可能有同学会因为考虑不周全失分。
60
分思路
对于 60%
的数据,保证 b≤30
,a <10
18。乘方结果在long long int
范围内。因此直接循环b
次算,或者用pow
函数算。但是用pow
函数容易出现浮点误差,建议循环b
次直接算。
#include <iostream>
using namespace std;
#define ll long long int
ll a,b,c = 1000000000;
ll f(ll a, ll b) {
if (a == 1) return 1;
ll ret = 1;
for (int i= 1; i <= b; i ++) {
ret *= a;
}
return ret;
}
int main() {
cin >> a>>b;
if ( f(a, b)>c) {
cout<<-1;
} else {
cout<< f(a, b);
}
return 0;
}
100
分思路
对于 100%
的数据,保证 1<=a,b<=10
9。a
和b
都很大,乘方肯定超过long long int
,因此不能直接算a
。我们可以转换思路,回到乘方的定义,看看几个a
相乘会超过规定的10
9,然后看看b
是否超过这个个数。个数的枚举是否会超时呢 ?让我们精算一下
如果a=1
,那么永远到不了ab, 因此需要特判a=1
如果a=2
,109不超过231-1,因此最多乘30
来次就会到109,不会超时。
如果a>2
,那么次数就更少了,更不会超时了。因此这个枚举是没问题的。
#include <iostream>
using namespace std;
#define ll long long int
ll a, b, c = 1000000000;
ll f(ll a, ll b) {
ll ret = 1;
for (int i= 1; i <= b; i ++) {
ret *= a;
}
return ret;
}
int main() {
cin >> a >> b;
if (a == 1) {
cout << 1;
return 0;
}
ll ji = 1;
int ge = 0;
while (1) {
if (ji * a > c) break;
ji*= a;
ge ++;
}
if (b > ge) {
cout << -1;
} else {
cout << f(a, b);
}
return 0;
}
给定一个正整数k
,有k
次询问,每次给定三个正整数ni,ei,di
,求两个正整数 pi,gi
,使ni=pi x gi、 ei x di=(pi - 1)(gi - 1) + 1
。
第一行一个正整数 k
,表示有 k
次询问。
接下来k
行,第i
行三个正整数 ni,di,ei
。
输出k
行,每行两个正整数 pi,qi
表示答案。
为使输出统一,你应当保证 pi<= qi
。如果无解,请输出 NO
。
输入#1 输出#1
10 2 385
770 77 5 NO
633 1 211 NO
545 1 499 NO
683 3 227 11 78
858 3 257 3 241
723 37 13 2 286
572 26 11 NO
867 17 17 NO
829 3 263 6 88
528 4 109
数据范围
以下记m=n-exd+2
。
保证对于 100%
的数据,1<=k<=105
,对于任意的 1<=i<=k,1<=n
i<=1018,1<=ei X di<=10
18,1<=m<=109。
100
分思路之代数方法3
#include <iostream>
#include <cmath>
using namespace std;
#define ll long long
ll k, n, d, e, m, p, q;
int main() {
cin >> k;
for (ll i= 1; i <= k; i++) {
cin >> n >> d >> e;
m=n-e*d+2;// p+q = m,pxq=n
ll x=m*m-4*n;
ll y = sqrt(x);
if(x == y*y) {
// 有整数解
p=(y+m) / 2;
q=m-p;
cout << min(p,q)<<" "<<max(p,q) << endl;
} else {
// 没有整数解
cout <<"NO" << endl;
}
}
return 0;
}
100
分思路之二分算法当一个长方形的周长一定时,长和宽怎么变化,它的面积最大 ?
4
反映到这个题上来,p
和q
分别相当于长和宽,pq=n
即面积,p+q=m
即周长。我们可以从1
到m/2
来枚举p
(因为p<=q
,所以枚举到m/2
即可)。即从小到大枚举p
,而q
直接用m-p
算出,这样可以让周长保持一定。当从小到大枚举p
的过程中,p
和q
是逐渐接近的因此pq
一定是逐渐变大的,这是一个单调的过程,我们在这个过程中就可以找到满足pq=n
的那个点。
因为是单调的过程,因此我们可以优化“从小到大枚举p
”为“二分枚举p
”。二分的过程中逼近满足pq=n
的那个p
。具体为 :如果当前p
下,pq=p(m-p)>n
,说明面积过大,那么应该让p
和q
远离,即减小P
。如果当前p
下,pq=p(m-p)<n
,说明面积过小,那么应该让p
和q
接近,即增加p
。如果当前p
下,pq=p(m-p)==n
,那么说明找到了p
。
根据刚才的分析,在1
到m/2
的范围内二分枚举p
,算出q=m-p
,再根据p*q
和n
的大小关系,分情况讨论向左还是向右继续枚举p
#include <iostream>
#include <cmath>
using namespace std;
#define ll long long
ll k, n, d, e, m, p, q;
int main() {
cin >> k;
for (ll i = 1; i <= k; i ++) {
cin >> n >> d >> e;
m=n-e*d+2;
// p+q = m, p x q =n
ll ok = 0;
ll l = 1,r = m/2; // 在此范围内二分枚举p
while (l <= r) {
ll p=(l +r) / 2;
ll q = m - p;// 算出q,固定周长m
ll mian = p* q;// 算出面积
if (mian > n) { // 让p和q远离
r=p- 1;
} else if (mian < n) { // 让p和q接近
l= p + 1;
} else { // 找到p*q正好==n的位置
cout << p << " "<< q << endl;
ok = 1;
break;
}
}
if (ok == 0) cout << "NO" << endl;
}
return 0;
}
逻辑表达式是计算机科学中的重要概念和工具,包含逻辑值、逻辑运算、逻辑运算优先级等内容。
在一个逻辑表达式中,元素的值只有两种可能:0(表示假)和1(表示真)
。元素之间有多种可能的逻辑运算,本题中只需考虑如下两种:“与”(符号为&
)和“或"(符号为 |
)。其运算规则如下 :
0 & 0 = 0 & 1 = 1 & 0 = 0,1&1=1
;0|0=0,0 | 1= 1 | 0 = 1 | 1=1
。
在一个逻辑表达式中还可能有括号。规定在运算时,括号内的部分先运算;两种运算并列时,&
运算优先于|
运算;同种运算并列时,从左向右运算。
比如,表达式0 | 1 & 0
的运算顺序等同于0 | ( 1 & 0 )
;表达式0 & 1 & 0 | 1
的运算顺序等同于( ( 0 & 1 ) & 0 ) | 1
。
此外,在 C++
等语言的有些编译器中,对逻辑表达式的计算会采用一种“短路”的策略:在形如 a&b
的逻辑表达式中,会先计算a
部分的值,如果a=0
,那么整个逻辑表达式的值就一定为0
,故无需再计算b
部分的值;同理,在形如alb
的逻辑表达式中,会先计算a
部分的值如果a=1
,那么整个逻辑表达式的值就一定为1
,无需再计算b
部分的值。
现在给你一个逻辑表达式,你需要计算出它的值,并且统计出在计算过程中,两种类型的“短路”各出现了多少次。需要注意的是,如某处“短路”包含在更外层被“短路”的部分内则不被统计,如表达式1 | ( 0 & 1 )
中尽管0&1
是一处“短路”,但由于外层的1 | ( 0 & 1 )
本身就是一处“短路”,无需再计算0 & 1
部分的值,因此不应当把这里的0 & 1
计入一处“短路”。
输入共一行,一个非空字符串`s`表示待计算的逻辑表达式。
输出共两行,第一行输出一个字符0
或1
,表示这个逻辑表达式的值;
第二行输出两个非负整数,分别表示计算上述逻辑表达式的过程中,形如 a&b
和a | b
的“短路"各出现了多少次。
输入#1
输入#2
0 & ( 1 | 0 ) | ( 1 | 1| 1 & 0 )
( 0 | 1 & 0 | 1 | 1 (1 | 1)) & ( 0 & 1 & (1 | 0)|0|0)&0
输出#1 输出#2
1 0
1 2 2 3
设|s|
为字符串s
的长度
对于所有数据,1<=|s|<=10
6。保证s
中仅含有字符0、1、&、|、(、)
且是一个符合规范的逻辑表达式。保证输入字符串的开头、中间和结尾均无额外的空格。保证s
中没有重复的括号嵌套(即没有形如((a))
形式的子串,其中a
是符合规范的逻辑表达式)。
#include <iostream>
#include <cmath>
using namespace std;
string s;
int stk1[1000005],stk2[1000005];//运算符栈和结果栈 (后缀表达式)
struct node {
int v, cntand, cntor;
} stk3[1000005]; // 用来计算后缀表达式
int top1, top2, top3;
int priori(char x) { // 定义优先级
if (x == '&') return 2;
else if (x == '|') return 1;
else if (x =='(') return 0;
}
void makeSuf() { // 生成后缀表达式,即生成stk2数组
for (int i = 0; i < s.size(); i ++) {
if (s[i]=='(') {
stk1[++top1] = s[i];
} else if (s[i] ==')') {
while (top1 > 0) {
if (stk1[top1] =='(') break;
stk2[++top2] = stk1[top1--];
}
top1--; // ( 自己也要出栈
} else if (s[i] =='0' || s[i] =='1') {
stk2[++top2] = s[i];
} else {
while (top1 > 0) {
if (priori( stk1[top1]) >= priori(s[i])) {
stk2[++top2] = stk1[top1--];
} else break;
}
stk1[++top1] = s[i];
}
}
while (top1 > 0)// 残留的运算符出栈
stk2[++top2] = stk1[top1--];
}
void calcSuf() {// 计算后缀表达式
for (int i = 1; i <= top2; i++) {
if (stk2[i] =='0' || stk2[i] =='1') { // 数字
stk3[++top3] = (node) {
stk2[i] -'0',0,0
};
} else if (stk2[i]=='&') { // &操作
node y = stk3[top3--];
node x = stk3[top3--]; // 注意x和y的顺序
if (x.v == 0) { // 短路
stk3[++top3] = (node) {
0,x.cntand+1,x.cntor
};
} else {
stk3[++top3] = (node) {
y.v, x.cntand+y.cntand, x.cntor+y.cntor
};
}
} else if (stk2[i] =='|') {// | 操作
node y = stk3[top3--];
node x = stk3[top3--];
if (x.v == 1) { // 短路
stk3[++top3] = (node) {
1,x.cntand,x.cntor+1
};
} else {
stk3[++top3] = (node) {
y.v, x.cntand+y.cntand, x.cntor+y.cntor
};
}
}
}
cout << stk3[1].v << endl;
cout<< stk3[1].cntand <<" "<<stk3[1].cntor<< endl;
}
int main() {
cin >> s;
makeSuf();// 生成后缀表达式
calcSuf(); //计算后缀表达式
return 0;
}
在一个二维平面内,给定n
个整数点(xi,yi)
,此外你还可以自由添加k
个整数点
你在自由添加k
个点后,还需要从n+k
个点中选出若个整数点并组成一个序列,使得序列中任意相邻两点间的欧几里得距离恰好为1
而且横坐标、纵坐标值均单调不减,即 xi+1-xi=1,yi+1=yi 或 yi+1-yi=1,xi+1=xi 。请给出满足条件的序列的最大长度。
第一行两个正整数n,k
分别表示给定的整点个数、可自由添加的整点个数。
接下来n
行,第i
行两个正整数xi,yi
表示给定的第i
个点的横纵坐标
输出一个整数表示满足要求的序列的最大长度。
输入#1 输入#2
8 2 4 100
3 1 10 10
3 2 15 25
3 3 20 20
3 6 30 30
1 2
2 2
5 5
5 3
输出#1 输出#2
8 103
#include <iostream>
#include <cstring>
using namespace std;
struct _pnt {
int x,y;
} a[1005];
int n,k,ans,anstmp;
int vis[505];
//查找坐标是否存在
int exist(int x,int y) {
for(int i=1; i<=n; i++) {
if( a[i].x==x && a[i].y==y ) {
return i;
}
}
return -1;
}
void go(int i,int cnt) {
if(vis[i])return;
vis[i]=1;
anstmp=max(anstmp,cnt);
int newi=exist( a[i].x+1, a[i].y );
if(newi!=-1) {
go(newi,cnt+1);
}
newi=exist(a[i].x,a[i].y+1 );
if(newi!=-1) {
go(newi,cnt+1);
}
}
int main() {
cin >> n >> k;
for (int i=1; i <= n; i ++) {
cin >> a[i].x >> a[i].y;
}
for(int i=1; i<= n; i++) {
memset(vis,0,sizeof(vis));
anstmp = 0;// 以i号点进行搜索能走的最长路径
go(i,1);// 以i号点为起点进行搜索
ans = max(ans,anstmp); // 所有起点能走的最长路径
}
cout << ans;
return 0;
}
#include <iostream>
#include <cstring>
using namespace std;
struct _pnt {
int x,y;
} a[1005];
int n,k,ans;
int you[105][105];//标记原始点的坐标存不存在
int f[105][105][105]; //dp 数组 当共补了z个点的情况下,到(x,y)点能连成的最多的点的个数
int main() {
cin>>n>>k;
for(int i=1; i<=n; i++) {
cin>>a[i].x>>a[i].y;
}
for(int i=1; i<=n; i++ ) {
you[a[i].x][a[i].y]=1;
}
for(int x=1; x<=100; x++ ) {
for(int y=1; y<=100; y++ ) {
for(int z=0; z<=k; z++ ) {
if( you[x][y] ) {
f[x][y][z]=max( f[x][y-1][z],f[x-1][y][z] )+1;
} else {
if(z>=1) {
f[x][y][z]=max( f[x][y-1][z-1],f[x-1][y][z-1] )+1;
}
}
ans=max(ans,f[x][y][z] );
}
}
}
cout<<ans;
return 0;
}
把40分和60分程序加一起。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct _pnt {
int x,y;
} a[1005];
int n,k,ans;
int f[105][105]; //dp 数组 f[i][z] 当共补了z个点的情况下,
//到第 i 个原始点能连成的最多的点的个数
int dis(int i,int j) { //从 j 到 i 共需要补的点的个数
return abs( a[i].x-a[j].x ) +abs( a[i].y-a[j].y ) -1;
}
bool cmp(_pnt p1,_pnt p2) {
if(p1.x==p2.x) return p1.y<p2.y;
else return p1.x<p2.x;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i ++) {
cin >> a[i].x >> a[i].y;
}
sort(a+1,a+n+1,cmp); // 排序,保证状态转移顺序的无后效性
for (int i = 1; i <= n; i++) {
int x = a[i].x, y = a[i].y;
for (int z = 0; z <= k; z++) {
f[i][z] = 1;
for (int j= 1; j <= n; j++) {
if (i != j && a[j].x <= x && a[j].y <= y) {//保证j在i的左下
int len = dis(i,j); // 从j到i共需要补Len个点
if (z >= len) {
f[i][z] = max(f[i][z],f[j][z - len] + len + 1);
// 多了Len+1个连续的点,+1表示第i个点自己
}
}
}
ans = max(ans,f[i][z] + k - z);// 从i把剩余的k-z个点疯狂延续出去
}
}
cout << ans;
return 0;
}