第一題 乘方
【題目描述】
小文同學剛剛接觸了信息學競賽，有一天她遇到了這樣一個題：給定正整數(shù)
a 和
b
，求
a
b 的值是多少。
a
b 即
b 個
a 相乘的值，例如 23 即為 3 個 2 相乘，結果為 2
× 2
× 2 = 8。
“簡單！”小文心想，同時很快就寫出了一份程序，可是測試時卻出現(xiàn)了錯誤。
小文很快意識到，她的程序里的變量都是 int 類型的。在大多數(shù)機器上，int 類型
能表示的最大數(shù)為 2 31
? 1 ，因此只要計算結果超過這個數(shù)，她的程序就會出現(xiàn)錯誤。
由于小文剛剛學會編程，她擔心使用 int 計算會出現(xiàn)問題。因此她希望你在
a
b 的
值超過 109 時，輸出一個 ‐1 進行警示，否則就輸出正確的
a
b 的值。
然而小文還是不知道怎么實現(xiàn)這份程序，因此她想請你幫忙。
?
【輸入格式】
從文件
pow.in 中讀入數(shù)據(jù)。
輸入共一行，兩個正整數(shù)
a, b 。
【輸出格式】
輸出到文件
pow.out 中。
輸出共一行，如果
a
b 的值不超過 109 ，則輸出
a
b 的值，否則輸出 ‐1 。
【樣例 1 輸入】
?10 9
【樣例 1 輸出】
?1000000000
【樣例 2 輸入】
?23333 66666
【樣例 2 輸出】
?‐1
解題流程
1. 開a，b變量+輸入
*特殊情況：如果a等于1直接輸出1
2. 開變量n，每次循環(huán)里會增加一次a
3. for循環(huán)0～b-1次循環(huán)求冪
? ? ? ? n求冪，每次乘a
? ? ? ? 判斷最新的數(shù)字是否大于10^9
? ? ? ? ? ? ? ? 是：輸出-1，結束運行
? ? ? ? ? ? ? ? 否：繼續(xù)for循環(huán)
4. 輸出最終答案n
注意事項
1. 兩個變量記得開ll或者ull 都行 反正int過不了
2. 場上freopen的文件名別寫錯?
3. 想我這種手敲了10^9的數(shù)清楚幾個0
4. n變量初始值為1
代碼
#include<bits/stdc++.h>
using namespace std;
int main(){
long long a,b,n=1;
cin>>a>>b;
if(a==1){
cout<<"1";
return 0;
}
else{
for(long long i=0;i<b;i++){
n*=a;
if(n>1000000000){
cout<<"-1";
return 0;
}
}
}
cout<<n;
return 0;
}第二題 解密
【題目描述】
給定一個正整數(shù)
k，有
k 次詢問，每次給定三個正整數(shù)
n
i
, e
i
, d
i，求兩個正整數(shù)
p
i
, q
i，
使
n
i =
p
i
×
q
i
, e
i
×
d
i = (
p
i
? 1)(
q
i
? 1) + 1。
【輸入格式】
從文件
decode.in 中讀入數(shù)據(jù)。
第一行一個正整數(shù)
k，表示有
k 次詢問。
接下來
k 行，第
i 行三個正整數(shù)
n
i
, d
i
, e
i。
【輸出格式】
輸出到文件
decode.out 中。
輸出
k 行，每行兩個正整數(shù)
p
i
, q
i 表示答案。
為使輸出統(tǒng)一，你應當保證
p
i
≤
q
i。
如果無解，請輸出 NO。?
【樣例 1 輸入】
?10
?770 77 5
?633 1 211
?545 1 499
?683 3 227
?858 3 257
?723 37 13
?572 26 11
?867 17 17
?829 3 263?
?528 4 109
【樣例 1 輸出】
?2 385
?NO
?NO
?NO
?11 78
?3 241
?2 286
?NO
?NO
?6 88
解題思路
簡單來說，就是求一元二次方程然后帶進代碼里求值就可以了（排除特殊NO情況）！?。。?！看到k , n , e , d 的范圍就知道要推公式，數(shù)據(jù)范圍提示很明顯的了。所以m是怎么來的呢？ 很簡單 如果距離事1，就輸出NO，同樣如果x小于0也會輸出NO。接下來用一般的方法就行了
解題流程
1. 分兩個函數(shù)（方便看）先分read和主函數(shù)
2. 帶入read函數(shù)，判斷數(shù)字和符號
3. 把NO的情況單獨分出來（m如果距離是1，x<0）
4. 帶入一元二次公式 求p，q
5. 輸出
代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
inline ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}
return x*f;
}
int main(){
int k=read();
while(k--)
{
ll n=read(),d=read(),e=read();
ll x=e*d-n-2;
x=-x;
double s=sqrt(x*x-4*n);
if(x<0||x*x-4*n<0||s!=int(s))
{
printf("NO\n");
continue;
}
int ss=s;
if((-x-ss)&1||(-x+ss)&1)
{
printf("NO\n");
return 0;
}
int yy=(-x-ss)/(-2),xx=(-x+ss)/(-2);
if(xx<=0||yy<=0)
{
printf("NO\n");
return 0;
}
printf("%d %d\n",xx,yy);
}
return 0;
}第三題 邏輯表達式
【題目描述】
邏輯表達式是計算機科學中的重要概念和工具，包含邏輯值、邏輯運算、邏輯運算
優(yōu)先級等內容。
在一個邏輯表達式中，元素的值只有兩種可能：
0
（表示假）和
1
（表示真）。元素
之間有多種可能的邏輯運算，本題中只需考慮如下兩種：“與”（符號為
&
）和“或”（符
號為
|
）。其運算規(guī)則如下：
0
&
0 = 0
&
1 = 1
&
0 = 0
，
1
&
1 = 1
；
0
|
0 = 0
，
0
|
1 = 1
|
0 = 1
|
1 = 1
。
在一個邏輯表達式中還可能有括號。規(guī)定在運算時，括號內的部分先運算；兩種運
算并列時，
&
運算優(yōu)先于
|
運算；同種運算并列時，從左向右運算。
比如，表達式
0|1&0
的運算順序等同于
0|(1&0)
；表達式
0&1&0|1
的運算順序等
同于
((0&1)&0)|1
。
此外，在
C++
等語言的有些編譯器中，對邏輯表達式的計算會采用一種“短路”
的策略。：在形如
a&b
的邏輯表達式中，會先計算
a
部分的值，如果
a
= 0
，那么整個
邏輯表達式的值就一定為
0
，故無需再計算
b
部分的值；同理，在形如
a|b
的邏輯表達
式中，會先計算
a
部分的值，如果
a
= 1
，那么整個邏輯表達式的值就一定為
1
，無需
再計算
b
部分的值。
現(xiàn)在給你一個邏輯表達式，你需要計算出它的值，并且統(tǒng)計出在計算過程中，兩種
類型的“短路”各出現(xiàn)了多少次。需要注意的是，如果某處“短路”包含在更外層被“短
路”的部分內則不被統(tǒng)計，如表達式
1|(0&1)
中，盡管
0&1
是一處“短路”，但由于外
層的
1|(0&1)
本身就是一處“短路”，無需再計算
0&1
部分的值，因此不應當把這里的
0&1
計入一處“短路”。
【輸入格式】
從文件
expr.in
中讀入數(shù)據(jù)。
輸入共一行，一個非空字符串
s
表示待計算的邏輯表達式。
【輸出格式】
輸出到文件
expr.out
中。
輸出共兩行，第一行輸出一個字符
0
或
1
，表示這個邏輯表達式的值；第二行輸
出兩個非負整數(shù)，分別表示計算上述邏輯表達式的過程中，形如
a&b
和
a|b
的“短路”
各出現(xiàn)了多少次。
解題思路
直接開數(shù)組，分calc和build函數(shù)分別為運算，和判斷符號的函數(shù)。用布爾類的函數(shù)dfs返回每個值，分別是 ( 和 |? 和 &。到時候帶入build和calc所以調用dfs函數(shù)的數(shù)里面就是build。dfs(build())
解題流程
1. 分4個函數(shù) calc做運算 build判斷01和符號 dfs（布爾）做符號判斷的根本 和主函數(shù)
2. 輸入字符串
3. 拆分成op和num 逐個運算
4. 計算“短路”情況“?
5. 兩個結果輸出
代碼
#include <bits/stdc++.h>
using namespace std;
int n,ch[1000010][2],root,num[1000010],op[1000010],pri[1<<10],topn,topo;
char s[1000010];
void calc(){
int u=op[topo];
ch[u][0]=num[topn-1],ch[u][1]=num[topn];
topo--,topn-=2,num[++topn]=u;
}
int build(){
topn=0,topo=0;
s[0]='(',s[n+1]=')';
for(int i=0;i<=n+1;i++){
if(s[i]=='0'||s[i]=='1') num[++topn]=i;
else if(s[i]=='(') op[++topo]=i;
else if(s[i]=='&'||s[i]=='|'){
while(topo&&pri[s[op[topo]]]<pri[s[i]]) calc();
op[++topo]=i;
}else if(s[i]==')'){
while(topo&&pri[s[op[topo]]]<pri[s[i]]) calc();
topo--;
}
}
return num[topn];
}
int cnt1,cnt0;
bool dfs(int u){
if(s[u]=='0') return 0;
if(s[u]=='1') return 1;
if(s[u]=='&'){
if(!dfs(ch[u][1])) return cnt0++,0;
return dfs(ch[u][0]);
}
if(s[u]=='|'){
if(dfs(ch[u][1])) return cnt1++,1;
return dfs(ch[u][0]);
}
return -1;
}
int main(){
scanf("%s",s+1),n=strlen(s+1);
pri['(']=1e9,pri['|']=1,pri['&']=0,pri[')']=1e9-1;
reverse(s+1,s+n+1);
for(int i=1;i<=n;i++){
if(s[i]=='(') s[i]=')';
else if(s[i]==')') s[i]='(';
}
printf("%d\n",dfs(build()));
printf("%d %d\n",cnt0,cnt1);
return 0;
} 第四題 上升點列
【題目描述】
在一個二維平面內，給定
n
個整數(shù)點
(
x
i
, y
i
)
，此外你還可以自由添加
k
個整數(shù)點。
你在自由添加
k
個點后，還需要從
n
+
k
個點中選出若干個整數(shù)點并組成一個序列，使
得序列中任意相鄰兩點間的歐幾里得距離恰好為
1
而且橫坐標、縱坐標值均單調不減，
即
x
i
+1
?
x
i
= 1
, y
i
+1
=
y
i
或
y
i
+1
?
y
i
= 1
, x
i
+1
=
x
i
。請給出滿足條件的序列的最大長
度。
【輸入格式】
從文件
point.in
中讀入數(shù)據(jù)。
第一行兩個正整數(shù)
n, k
分別表示給定的整點個數(shù)、可自由添加的整點個數(shù)。
接下來
n
行，第
i
行兩個正整數(shù)
x
i
, y
i
表示給定的第
i
個點的橫縱坐標。
【輸出格式】
輸出到文件
point.out
中。
輸出一個整數(shù)表示滿足要求的序列的最大長度。
【樣例
1
輸入】
?
8 2
?
3 1
?
3 2
?
3 3
?
3 6
?
1 2
?
2 2
?
5 5
?
5 3
【樣例
1
輸出】
?
8
解題思路
狀態(tài)dp題，但是要分別xy點轉移方程。先看n , k 的范圍，顯然可在O ( n 2 k ) 復雜度解決。狀態(tài)怎么找呢？看答案的轉移需要哪些條件，其轉移與序列最后一個點的坐標和添加點的個數(shù)有關。
解題流程
1. 分布爾函數(shù)cmp 和豬函數(shù)main。cmp創(chuàng)建數(shù)軸上的點Node，主函數(shù)運行
2. 輸入nk和所有點文章來源：http://www.zghlxwxcb.cn/news/detail-471569.html
3. 判斷絕對值，輸出ans+k的值文章來源地址http://www.zghlxwxcb.cn/news/detail-471569.html
代碼
#include<bits/stdc++.h>
using namespace std ;
const int Max = 5e2 + 10 , TIL = ( 1 << 28 ) ;
struct Node { int X , Y ; } T[Max] ;
int F[Max][Max] , Con[Max][Max] ;
int N , K ;
bool CMP( Node A , Node B ) {
if( A.X == B.X ) return A.Y < B.Y ;
else return A.X < B.X ;
}
int Ans ;
int main( ) {
scanf("%d%d" , &N , &K ) ;
for(int i = 1 ; i <= N ; i ++ ) scanf("%d%d" , &T[i].X , &T[i].Y ) , Con[i][0] = 0 ;
sort( T + 1 , T + N + 1 , CMP ) ;
for(int i = 1 ; i <= N ; i ++ ) for(int l = 1 ; l <= N ; l ++ )
Con[i][l] = abs( T[i].X - T[l].X ) + abs( T[i].Y - T[l].Y ) - 1 ;
for(int i = 1 ; i <= N ; i ++ ) F[i][0] = 1 ;
for(int P = false ; P <= K ; P ++ ) for(int i = 2 ; i <= N ; i ++ ) for(int l = 0 ; l <= i - 1 ; l ++ )
if( Con[i][l] <= P && T[l].X <= T[i].X && T[l].Y <= T[i].Y ) F[i][P] = max( F[i][P] , F[l][P - Con[i][l]] + 1 ) ;
for(int i = 1 ; i <= N ; i ++ ) for(int P = false ; P <= K ; P ++ ) Ans = max( Ans , F[i][P] ) ;
printf("%d\n" , Ans + K ) ;
return false ;
}到了這里，關于2022 CSP-J 復賽題解的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
