在网上看到一篇较详细的讲解，觉得讲解的非常好！
第一题：乘方pow
题目描述
小文同学刚刚接触了信息学竞赛，有一天她遇到了这样一个题：给定正整数a和b，求ab 的值是多少。ab即b个a相乘的值，例如23即为3个2相乘，结果为2x2x2=8。
“简单!”小文心想，同时很快就写出了一份程序，可是测试时却出现了错误。
小文很快意识到，她的程序里的变量都是int 类型的。在大多数机器上，int类型能表示的最大数为231-1，因此只要计算结果超过这个数，她的程序就会出现错误。由于小文刚刚学会编程，她担心使用int计算会出现问题。因此她希望你在ab的值超过109时，输出一个 -1进行警示，否则就输出正确的ab的值。
然而小文还是不知道怎么实现这份程序，因此她想请你帮忙。
输入格式
输入共一行，两个正整数a，b。
输出格式
输出共一行，如果ab的值不超过109，则输出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 <1018。乘方结果在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<=109。a和b都很大，乘方肯定超过long long int，因此不能直接算a。我们可以转换思路，回到乘方的定义，看看几个a相乘会超过规定的109，然后看看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;
}
第二题 ：解密 decode
题目描述
给定一个正整数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<=ni<=1018，1<=ei X di<=1018，1<=m<=109。
100分思路之代数方法
3
代码语言：javascript复制#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;
}
第三题逻辑表达式expr
题目描述
逻辑表达式是计算机科学中的重要概念和工具，包含逻辑值、逻辑运算、逻辑运算优先级等内容。
在一个逻辑表达式中，元素的值只有两种可能: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|<=106。保证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;
}
第四题上升点列point
题目描述
在一个二维平面内，给定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
40分程序
代码语言：javascript复制#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;
}
60分程序
代码语言：javascript复制#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;
}
70分程序
把40分和60分程序加一起。
100分程序
代码语言：javascript复制#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;
}
