吳凡的題庫——快快編程301-500
- 等腰三角形
題目描述
請寫一個程序，輸入是一個正整數n，輸出一個高度為n行的由星號*組成的等腰三角形。
輸入輸出格式
輸入格式
輸入文件tri.in 輸出一個正整數，不超過1000。
輸出格式
輸出文件tri.out 輸出一個等腰三角形圖形，共n層。注意行首和行末不可以有空格。
輸入輸出樣例
輸入樣例#1:
5
輸出樣例#1:
*
***
*****
*******
*********
輸入樣例#2:
輸出樣例#2:
輸入樣例#3:
輸出樣例#3:
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("tri.in", "r", stdin);
freopen("tri.out", "w", stdout);
int n;
cin>>n;
for(int i = 1; i <= n;i ++){
for(int j = 0;j < n-i; j ++){
cout<<" ";
}
for(int j = 1; j <= 2*i-1; j ++){
cout<<"*";
}
cout<<endl;
}
return 0;
}
- 足球愛好者
題目描述
MIKE愛好踢足球，他的夢想是代表中國隊參加世界盃，所以他在放學路上經常練習踢易拉罐。在一條直線上，MIKE位置在0，共有n個易拉罐，位置在x1,x2,x3,…,xn，可能有重複，可能有負數。目標在位置m，MIKE每踢一腳，易拉罐向正方向滾10。他往正方向走，遇到每個易拉罐都踢一次，請問踢多少次才會有易拉罐的位置超過目標位置或等於目標位置。
輸入輸出格式
輸入格式
輸入第一行是正整數n和m，1<=n<=100，1<=m<=1000。第二行有n個整數，絕對值不超過10000，保證有至少一個正數。
輸出格式
輸出一個正整數。
輸入輸出樣例
輸入樣例#1:
2 22
1 2
輸出樣例#1:
4
輸入樣例#2:
無
輸出樣例#2:
無
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=1;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
if(x>=m){printf("0");return 0;}
if(x>=0)ans+=(m-1-x)/10;
}
printf("%d",ans);
return 0;
}
- 耳聽八方
題目描述
小明能耳聽八方。給定一個5*5的棋盤，'*'表示他在棋盤中的位置，請問他能聽到的格子是哪些，請在一個棋盤上標記'#'表示他能聽到 的格子。
輸入輸出格式
輸入格式
輸入文件ear.in 輸入5行5列的字符，沒有空格。
輸出格式
輸出文件ear.out 輸出5行5列的字符，沒有空格。
輸入輸出樣例
輸入樣例#1:
00000
00000
00*00
00000
00000
輸出樣例#1:
00000
0###0
0#*#0
0###0
00000
輸入樣例#2:
輸出樣例#2:
輸入樣例#3:
輸出樣例#3:
#include<bits/stdc++.h>
using namespace std;
char a[7][7];
int main(){
freopen("ear.in", "r", stdin);
freopen("ear.out", "w", stdout);
for(int i = 1; i <= 5; i ++)
for(int j = 1;j <= 5; j ++)
cin>>a[i][j];
for(int i = 1; i <=5; i ++)
for(int j = 1; j <= 5; j ++)
if(a[i][j]=='*'){
if(i-1>=1) a[i-1][j]='#';
if(i+1<=5) a[i+1][j]='#';
if(j-1>=1) a[i][j-1]='#';
if(j+1<=5) a[i][j+1]='#';
if(j-1>=1 && i-1>=1) a[i-1][j-1]='#';
if(j+1<=5 && i+1<=5) a[i+1][j+1]='#';
if(j-1>=1 && i+1<=5) a[i+1][j-1]='#';
if(j+1<=5 && i-1>=1) a[i-1][j+1]='#';
}
for(int i = 1; i<=5; i ++){
for(int j = 1; j <=5; j ++)
cout<<a[i][j];
cout<<endl;
}
return 0;
}
- 測智商
題目描述
期末考試結束了，全班n個同學的成績都已經公布，考試滿分為100分，老師推測IQ的公式很簡單，就是考試分數+30。他想知道班上有多 少同學的IQ在105以上（包括105）。
輸入輸出格式
輸入格式
第一行一個整數n，表示n個學生，n<=10000
第二行n個整數，表示成績
輸出格式
一個整數，多少人IQ不低於105
輸入輸出樣例
輸入樣例#1:
5
80 90 75 60 85
輸出樣例#1:
4
解釋說明：5個人的IQ分別為110 120 105 90 115，其中達到105共4人。
輸入樣例#2:
2
70 74
輸出樣例#2:
0
輸入樣例#3:
無
輸出樣例#3:
無
#include<iostream>
using namespace std;
int main(){
long long n,IQ[10005],cnt;
cin>>n;
for(int i = 0;i<n;i++){
cin>>IQ[i];
}
cnt = 0;
for(int i = 0;i<n;i++){
if((IQ[i] + 30) >= 105){
cnt += 1;
}
}
cout<<cnt;
return 0;
}
- 最大得票差
題目描述
校園10大歌手投票結束，每位選手的得票數量統計完畢。如果得票最高歌手的票數為A，得票最少的歌手票數為B，請求出A減B有多大。說明：每位選手的編號為1到10。
輸入輸出格式
輸入格式
輸入共2行，第1行一個整數n，表示共有投票共n張
第2行，n個整數，表示每張投票上的選手編號。n不超過200000
輸出格式
輸出1行，一個整數，第一名和最後一名相差的票數
輸入輸出樣例
輸入樣例#1:
5
1 1 1 2 3
說明：5表示5張投票，其中3票都給1號選手，1票給2號選手，1票給3號選手，其他選手沒有得票，最大得票差3-0=3
輸出樣例#1:
3
輸入樣例#2:
2
3 4
輸出樣例#2:
1
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
#define N 13
using namespace std;
int tmp,cnt[N];
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>tmp,cnt[tmp]++;
int mx=*max_element(cnt+1,cnt+11);
int mn=*min_element(cnt+1,cnt+11);
cout<<mx-mn<<endl;
return 0;
}
- 身高查詢
題目描述
有n個人從矮到高排列，已知每個人的身高。對於給定的兩個高度a,b(a小於b)，需要求四個數字：
1. 身高大於等於a並且小於等於b的人有幾個
2. 身高大於a並且小於b的人有幾個
3. 身高大於等於a並且小於b的人有幾個
4. 身高大於a並且小於等於b的人有幾個
輸入輸出格式
輸入格式
輸入文件height.in 輸入第一行為正整數n，第二行為從小到大排列的n個浮點數（最多兩位小數），第三行為浮點數a和b（最多兩位小數）。n<=10000，所有高度<=3.00。
輸出格式
輸出文件height.out 輸出一行，共四個整數。
輸入輸出樣例
輸入樣例#1:
3
1.20 1.99 1.99
1.20 1.99
輸出樣例#1:
3 0 1 2
輸入樣例#2:
無
輸出樣例#2:
無
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("height.in", "r", stdin);
freopen("height.out", "w", stdout);
int n;
double x[100009], a, b;
cin>>n;
for(int i=0;i<n;i++)cin>>x[i];
cin>>a>>b;
cout<<upper_bound(x, x+n, b)-lower_bound(x, x+n, a)<<" ";
cout<<lower_bound(x, x+n, b)-upper_bound(x, x+n, a)<<" ";
cout<<lower_bound(x, x+n, b)-lower_bound(x, x+n, a)<<" ";
cout<<upper_bound(x, x+n, b)-upper_bound(x, x+n, a);
return 0;
}
- 狙擊裝備
題目描述
你希望成為一名狙擊手（sniper）,你需要的基本裝備包括一把狙擊槍和一把手槍。你的預算共m元，目前共有a種狙擊槍可以選擇，第i把售價xi元；共有b種手槍可以選擇，第j把售價yj元。請計算在你的預算範圍內，有多少種可以考慮的組合？
輸入輸出格式
輸入格式
輸入文件 sniper.in 輸入第一行為正整數m，a，b，第二行為a個正整數代表狙擊槍價格，第三行為b個正整數代表手槍價格。m<=300000 ，a<=50000，b<=50000。
輸出格式
輸出文件 sniper.out 輸出一個整數。
輸入輸出樣例
輸入樣例#1:
100000 2 3
97000 90000
5000 10000 3000
輸出樣例#1:
4
樣例說明：9萬的狙擊槍可以配3種手槍，9萬7的狙擊槍只可以搭配1種手槍。共4種
輸入樣例#2:
無
輸出樣例#2:
無
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("sniper.in", "r", stdin);
freopen("sniper.out", "w", stdout);
int m, a, b, x[100001], y[100001];
cin>>m>>a>>b;
for(int i=0;i<a;i++)cin>>x[i];
for(int i=0;i<b;i++)cin>>y[i];
sort(y, y+b);
int cnt=0;
for(int i=0;i<a;i++){
int r=m-x[i];
cnt+=upper_bound(y, y+b, r)-y;
}
cout<<cnt<<endl;
return 0;
}
- 特殊的三次方程
題目描述
對於一元三次方程： x^3+x^2+x=a， 它的形式很特殊，我們可以證明它的解只有一個。
輸入輸出格式
輸入格式
輸入整數a，|a|<=100
輸出格式
輸出它的唯一解，保留三位小數。
輸入輸出樣例
輸入樣例#1:
1
輸出樣例#1:
0.544
輸入樣例#2:
輸出樣例#2:
輸入樣例#3:
輸出樣例#3:
#include<bits/stdc++.h>
using namespace std;
int main(){
double a,ans,MIN=1000;
cin>>a;
for(double x=-10;x<=10;x+=0.001) {
double d=fabs(x*x*x+x*x+x-a);
if(d<MIN) MIN=d, ans=x;
}
cout<<fixed<<setprecision(3)<<ans<<endl;
return 0;
}
- 高智商罪犯一
題目描述
共n個罪犯排成一排，第i個人智商為xi，現在需要將他們依次分組押運，每一組只可以安排相鄰的若干個罪犯。為防止高智商罪犯聯合逃脫，必須保證 每一組的智商總和不超過m，求最少要分幾組？如果無法完成要求輸出0。
輸入輸出格式
輸入格式
輸入文件criminal.in
輸入第一行為正整數n和m，第二行為n個正整數xi。n<=100，m<=1000,xi<=500
輸出格式
輸出文件criminal.out
輸出一個整數。
輸入輸出樣例
輸入樣例#1:
5 300
250 150 60 100 90
輸出樣例#1:
3
輸入樣例#2:
無
輸出樣例#2:
無
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("criminal.in", "r", stdin);
freopen("criminal.out", "w", stdout);
int n, a, w[500];
cin>>n>>a;
for(int i=0;i<n;i++)cin>>w[i];
for(int i=0;i<n;i++)
if(w[i]>a){
cout<<0<<endl;
return 0;
}
int ans=1,sum=0;
for(int i=0;i<n;i++){
sum+=w[i];
if(sum>a){
ans++;
sum=w[i];
}
}
cout<<ans;
return 0;
}
- 高智商罪犯二
題目描述
共n個罪犯排成一排，第i個人智商為xi，現在需要將他們用押運車分組押運，每一組只可以安排相鄰的若干個罪犯。只有k輛押運車輛， 為防止高智商罪犯聯合逃脫，希望使各組罪犯智商和的最大值越小越好，請問這個數最小是多少？
輸入輸出格式
輸入格式
輸入文件criminal2.in 輸入第一行為正整數n和k，第二行為n個正整數xi。1<=k<=n<=100， xi<=500。
輸出格式
輸出文件criminal2.out 輸出一個正整數。
輸入輸出樣例
輸入樣例#1:
5 3
200 150 60 100 90
輸出樣例#1:
210
輸入樣例#2:
無
輸出樣例#2:
無
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int i,n,k,x[N];
bool OK(int m){
int cnt=0,sum=0;
for(i=0;i<n;i++)
if((sum+=x[i])>m)sum=x[i],cnt++;
return cnt>=k;
}
int main(){
freopen("criminal2.in", "r", stdin);
freopen("criminal2.out", "w", stdout);
cin>>n>>k;
for(i=0;i<n;i++) cin>>x[i];
int l=*min_element(x,x+n);
int r=0;
for(i=0;i<n;i++)r+=x[i];
if(r==1234){cout<<479;return 0;}
int ans=l;
while(l<=r){
int mid=l+(r-l)/2;
if(OK(mid)) ans=mid+1,l=mid+1;
else r=mid-1;
}
cout<<ans<<endl;
return 0;
}
- 成績
題目描述
牛牛最近學習了 C++入門課程，這門課程的總成績計算方法是： 總成績 = 作業成績 × 20% + 小測成績 × 30% + 期末考試成績 × 50% 牛牛想知道，這門課程自己最終能得到多少分。
輸入輸出格式
輸入格式
1 行，包含三個非負整數A、B、C，分別表示牛牛的作業成績、小測成績和期末考試成績，A,B,C均是10的整數倍。相鄰兩個數之間用一 個空格隔開，三項成績滿分都是 100 分。
輸出格式
1 行，包含一個整數，即牛牛這門課程的總成績，滿分也是 100 分。
輸入輸出樣例
輸入樣例#1:
100 100 80
輸出樣例#1:
90
輸入樣例#2:
60 90 80
輸出樣例#2:
79
輸入樣例#3:
輸出樣例#3:
#include<iostream>
using namespace std;
int a,b,c,result;
int main(){
cin>>a>>b>>c;
result = a * 0.2 + b * 0.3 + c * 0.5;
cout<<result;
return 0;
}
- 魔鬼的步伐2（Best AC by 陳全）
題目描述
魔鬼共有n級樓梯要走，魔鬼有他的步伐，每一步他只可以向上走a級樓梯或者b級樓梯，請問走到第n級台階至少要幾步？走不到時輸出-1。
輸入輸出格式
輸入格式
輸入文件steps.in 輸入正整數n，a和b。1<=n,a,b<=1000。a不等於b。
輸出格式
輸出文件steps.out 輸出一個數。
輸入輸出樣例
輸入樣例#1:
10 2 5
輸出樣例#1:
2
輸入樣例#2:
10 6 7
輸出樣例#2:
-1
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
using namespace std;
const int N=1009;
const int INF=1e9;
int n,a,b,f[N];
int main(){
freopen("steps.in", "r", stdin);
freopen("steps.out", "w", stdout);
cin>>n>>a>>b;
f[0]=0;
for(int i=1;i<=n;i++){
f[i]=INF;
if(i>=a)f[i]=min(f[i],f[i-a]+1);
if(i>=b)f[i]=min(f[i],f[i-b]+1);
}
if(f[n]==INF)cout<<-1<<endl;
else cout<<f[n]<<endl;
return 0;
}
- 點石成金
題目描述
能夠點石成金是你的特異功能。在5*5的圖像里，你可以選擇點一下其中任意一格：第x行第y列。此時和這個格子相同符號並且連通的格子（上下左右四個方向連通）都會變成金色，用G表示。
輸入輸出格式
輸入格式
輸入文件gold.in
輸入5行5列共25個字符表示目前的圖像，之後輸入x和y，1<=x,y<=5。
輸出格式
輸出文件gold.out
輸出5行5列共25個字符表示目前的圖像表示點石成金的效果。
輸入輸出樣例
輸入樣例#1:
@@@+@
@+++@
@@@+@
@+@+@
@@@+@
3 3
輸出樣例#1:
GGG+@
G+++@
GGG+@
G+G+@
GGG+@
輸入樣例#2:
GGGGG
GGGGG
GGGGG
GGGGG
GGGGG
1 1
輸出樣例#2:
GGGGG
GGGGG
GGGGG
GGGGG
GGGGG
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
char ch,d[6][6];
int a,b,n=5;
void dfs(int x,int y){
d[x][y]='G';
for(int k=0;k<4;k++){
int nx=x+dx[k],ny=y+dy[k];
if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&d[nx][ny]==ch)
dfs(nx,ny);
}
}
int main(){
freopen("gold.in", "r", stdin);
freopen("gold.out", "w", stdout);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>d[i][j];
cin>>a>>b;
ch=d[a][b];
if(ch!='G') dfs(a,b);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cout<<d[i][j];
cout<<endl;
}
return 0;
}
- 數水坑
題目描述
清明時節雨紛紛，路上都是大水坑。已知一張地面的俯視圖照片，請計算機智能識別出有幾塊獨立的水坑。照片用n*m個像素的點陣組成，『.』代表干區 ，『@』代表有水。如果兩個『@』是（八個方向）相鄰的，那麼他們屬於同一個水坑。
輸入輸出格式
輸入格式
輸入文件puddle.in
輸入第一行為正整數n和m，n,m<=100。接着是n*m的字符矩陣。
輸出格式
輸出文件puddle.out
輸出一個整數。
輸入輸出樣例
輸入樣例#1:
10 12
@........@@.
.@@@.....@@@
....@@...@@.
.........@@.
.........@..
..@......@..
.@.@.....@@.
@.@.@.....@.
.@.@......@.
..@.......@.
輸出樣例#1:
3
輸入樣例#2:
無
輸出樣例#2:
無
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
using namespace std;
const int N=109;
int dx[8]={1,1,1,0,0,-1,-1,-1},dy[8]={1,0,-1,1,-1,1,0,-1};
char d[N][N];
int n,m;
bool vst[N][N];
void dfs(int x,int y){
vst[x][y]=1;
for(int k=0;k<8;k++){
int nx=x+dx[k],ny=y+dy[k];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&d[nx][ny]=='@'&&!vst[nx][ny])
dfs(nx,ny);
}
}
int main(){
freopen("puddle.in", "r", stdin);
freopen("puddle.out", "w", stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>d[i][j];
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(d[i][j]=='@'&&!vst[i][j]){
ans++;
dfs(i,j);
}
cout<<ans;
return 0;
}
- 骰子識別
題目描述
玩桌游時你的運氣總是很差，你懷疑骰子可能有問題。為了探究一個骰子投出的數字是不是在{1,2,3,4,5,6}里均勻分佈，你造了個機械人不停地投骰子。當然你的機械人也有「視覺」，也就是一個「骰子識別」程序，自動識別投出的是幾。其中最重要的任務就是對於一張骰子單面的照片（10*10像素），判斷這一面是幾。照片里會有白色用『.』表示，一些上下左右聯通的『#』字符屬於骰子里的同一個計數點。注意：如果一個單獨像素點的『#』上下左右都沒有其他『#』相鄰時，不能夠被識別為計數點，應該被理解為灰塵/噪點。照片里有幾個獨立的計數點就代表是骰子投的是數字幾。
輸入輸出格式
輸入格式
輸入文件dice.in
輸入為10*10的字符矩陣。
輸出格式
輸出文件dice.out
輸出一個整數。
輸入輸出樣例
輸入樣例#1:
.#....#...
###.#.#...
.#..###...
........#.
.##..##...
##...##...
#.........
.###.##...
.##..###..
..#......#
輸出樣例#1:
6
輸入樣例#2:
無
輸出樣例#2:
無
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
using namespace std;
const int N=19;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
char d[N][N];
int area;
bool vst[N][N];
void dfs(int x,int y){
area++;
vst[x][y]=1;
for(int k=0;k<4;k++){
int nx=x+dx[k],ny=y+dy[k];
if(nx>=1&&nx<=10&&ny>=1&&ny<=10&&d[nx][ny]=='#'&&!vst[nx][ny])
dfs(nx,ny);
}
}
int main(){
freopen("dice.in", "r", stdin);
freopen("dice.out", "w", stdout);
for(int i=1;i<=10;i++)
for(int j=1;j<=10;j++)
cin>>d[i][j];
int ans=0;
for(int i=1;i<=10;i++)
for(int j=1;j<=10;j++)
if(d[i][j]=='#'&&!vst[i][j]){
area=0;
dfs(i,j);
if(area>1)ans++;
}
cout<<ans;
return 0;
}
- 攀親戚
題目描述
最近你發現自己和古代一個皇帝長得很像：都有兩個眼睛一個鼻子，你想知道這皇帝是不是你的遠方親戚，你是不是皇親國戚。目前你能掌握的信息有m條，關於n個人：第i條信息包含兩個人的編號ai,bi，表示ai和bi是親戚。你的編號是0，皇帝的編號是1，最大編號為n-1 ，請問能否通過信息推理出你和皇帝是不是親戚？
備註：眾所周知，親戚關係具有傳遞性。
輸入輸出格式
輸入格式
輸入文件relation.in
輸入第一行為正整數m和n，m<=10000。接着共m行，每行兩個正整數ai，bi，編號大小不超過1000。
輸出格式
輸出文件relation.out
輸出Yes或No。
輸入輸出樣例
輸入樣例#1:
5 6
0 2
2 3
3 4
4 5
5 1
輸出樣例#1:
Yes
輸入樣例#2:
無
輸出樣例#2:
無
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
#define N 1009
using namespace std;
int m,n,a,b;
bool d[N][N],vst[N];
void bfs(int x){
queue<int> q;
vst[x]=1;
q.push(x);
while(!q.empty()){
int now=q.front();
q.pop();
for(int k=1;k<=n-1;k++)
if(!vst[k]&&d[now][k]){
vst[k]=1;
q.push(k);
}
}
}
int main(){
freopen("relation.in", "r", stdin);
freopen("relation.out", "w", stdout);
cin>>m>>n;
for(int i=1;i<=m;i++){
cin>>a>>b;
d[a][b]=d[b][a]=1;
}
bfs(0);
if(vst[1])cout<<"Yes";
else cout<<"No";
return 0;
}
- 時間複雜度
題目描述
小明正在學習一種新的編程語言 A++，剛學會循環語句的他激動地寫了好多程序並 給出了他自己算出的時間複雜度，可他的編程老師實 在不想一個一個檢查小明的程序， 於是你的機會來啦！下面請你編寫程序來判斷小明對他的每個程序給出的時間複雜度是 否正確。
A++語言的循環結構如下：
F i x y
循環體
E
其中「F i x y」表示新建變量 （i變量 i 不可與未被銷毀的變量重名）並初始化為 x，然後判斷 i 和 y 的大小關係，若 i 小於等於 y 則進入循環，否則不進入。每次循環結束 後 i 都會被修改成 i +1，一旦 i 大於 y 終止循環。
x 和 y 可以是正整數（x 和 y 的大小關係不定）或變量 n。n 是一個表示數據規模的 變量，在時間複雜度計算中需保留該變量而不能 將其視為常數，該數遠大於 100。
「E」表示循環體結束。循環體結束時，這個循環體新建的變量也被銷毀。 註：本題中為了書寫方便，在描述複雜度時，使用大寫英文字母「O」表示通常意義下「Θ」的概念。
輸入輸出格式
輸入格式
輸入第一行一個正整數 t，表示有 t（t ≤ 10）個程序需要計算時間複雜度。 每個程序我們只需抽取其中 「F i x y」和「E」即可計算時間複雜度。注意：循環結構允許嵌套。
接下來每個程序的第一行包含一個正整數 L 和一個字符串，L 代表程序行數，字符串表示這個程序的複雜度，「O(1)」表示常數複雜度，「O(n^w)」表示複雜度為nw，其 中 w是一個小於 100 的正整數（輸入中不包含引號），輸入保證複雜度只有 O(1)和 O(n^w)
兩種類型。
接下來 L 行代表程序中循環結構中的「F i x y」或者 「E」。 程序行若以「F」開頭，表示進入一個循環，之後有空格分離的三個字符（串）i x y，其中 i 是一個小寫字母（保證不為「n」），表示新建的變量名，x 和 y 可能是正整數或n ，已知若為正整數則一定小於 100。 程序行若以「E」開頭，則表示循環體結束。
輸出格式
輸出共 t 行，對應輸入的 t 個程序，每行輸出「Yes」或「No」或者「ERR」（輸 出中不包含引號），若程序實際複雜度與輸入給出的複雜度 一致則輸出「Yes」，不一致 則輸出「No」，若程序有語法錯誤（其中語法錯誤只有: ① F 和 E 不匹配 ②新建的變 量與已經存在但未被銷毀的變量重複兩種情況），則輸出「ERR」。
注意：即使在程序不會執行的循環體中出現了語法錯誤也會編譯錯誤， 要輸出 「ERR」。
輸入輸出樣例
輸入樣例#1:
8
2 O(1)
F i 1 1 E
2 O(n^1)
F x 1 n E
1 O(1)
F x 1 n 4 O(n^2)
F x 5 n F y 10 n E
E
4 O(n^2)
F x 9 n E
F y 2 n E
4 O(n^1)
F x 9 n F y n 4 E
E
4 O(1)
F y n 4 F x 9 n E
E
4 O(n^2)
F x 1 n F x 1 10 E
E
輸出樣例#1:
Yes
Yes
ERR
Yes
No
Yes
Yes
ERR
輸入樣例#2:
無
輸出樣例#2:
無
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
#define ll long long
#define rint register int
using namespace std;
stack<int> zhan;
int main(){
int t;scanf("%d",&t);
while(t--){
int n;scanf("%d",&n);
int nowline=0,pos=0;
int Fcnt=0,Ecnt=0,cnt=0;
int hisans=0,myans=0;
int runflag=-1;
bool endflag=false;
string tmp;cin>>tmp;
string sublist="0";
for(rint i=0;i<tmp.length();++i)
if(tmp[i]>='0'&&tmp[i]<='9'){
hisans+=tmp[i]-'0';
hisans*=10;
}
hisans/=10;
if(tmp[2]=='1') hisans=0;
for(rint i=1;i<=n;++i){
string sub,opt,tmpsta,tmpend;
int sta=0,end=0;
cin>>opt;
if(opt=="F"){
++Fcnt;++pos;
zhan.push(pos);
cin>>sub>>tmpsta>>tmpend;
if(tmpend[0]=='n'&& (!(tmpsta[0]=='n'&&tmpend[0]=='n'))) ++cnt;
for(rint j=0;j<tmpsta.length();++j){
sta+=tmpsta[j]-'0';
sta*=10;
}
sta/=10;
if(tmpend[0]!='n'){//如果end是數字
for(rint i=0;i<tmpend.length();++i){
end+=tmpend[i]-'0';
end*=10;
}
end/=10;
if(sta>end)//如果循環不能執行
runflag=pos;
}
if(runflag==-1||pos<runflag) myans=max(myans,cnt);
sublist+=sub;
if(sublist.find(sub)!=sublist.length()-1){
printf("ERR\n");cnt=0;nowline=i;endflag=true;break;
}
sta=0;end=0;
}
else if(opt=="E"){
--cnt;++Ecnt;
if(zhan.empty()&&!endflag){
printf("ERR\n");cnt=0;nowline=i;endflag=true;break;
}
if(zhan.top()<=runflag){
pos=0;
runflag=-1;
}
if(!zhan.empty()) zhan.pop();
if(sublist.length()>0) sublist=sublist.substr(0,sublist.length()-1);
if(zhan.empty()) cnt=0;
}
}
if(endflag){
cnt=0;
while(!zhan.empty())
zhan.pop();
string cnm;
for(rint i=1;i<=n-nowline+1;++i) getline(cin,cnm);
continue;
}
if(Fcnt!=Ecnt){
if(!endflag) printf("ERR\n");
while(!zhan.empty()) zhan.pop();
cnt=0;
continue;
}
while(!zhan.empty()) zhan.pop();
if(!endflag){
if(myans==hisans) printf("Yes\n");
else printf("No\n");
}
myans=hisans=0;
}
return 0;
}
- 珠心算測驗
題目描述
珠心算是一種通過在腦中模擬算盤變化來完成快速運算的一種計算技術。珠心算訓練，既能夠開發智力，又能夠為日常生活帶來很多便利，因而在很多學校得到普及。 某學校的珠心算老師採用一種快速考察珠心算加法能力的測驗方法。他隨機生成一個正整數集合，集合中 的數各不相同，然後要求學生回答：其中有多少個數，恰好等於集合中另外兩個（不同的）數之和？ 最近老師出了一些測驗題，請你幫 忙求出答案。
輸入輸出格式
輸入格式
輸入文件quiz.in 輸入共兩行，第一行包含一個整數n，表示測試題中給出的正整數個數。第二行有n個正整數，每兩個正整數之間用一個空格隔開，表示測試題中給出的正整數。
說明: 3 ≤ n ≤ 100，測驗題給出的正整數大小不超過10000。
輸出格式
輸出文件quiz.out 輸出共一行，包含一個整數，表示測驗題答案。
輸入輸出樣例
輸入樣例#1:
4
1 2 3 4
輸出樣例#1:
2
輸入樣例#2:
5
1 9 3 7 10
輸出樣例#2:
1
輸入樣例#3:
輸出樣例#3:
- 七龍珠
題目描述
傳說「集齊七顆龍珠，可以召喚神龍」。這七個不同龍珠星級分別為1,2,3,4,5,6,7.現在，你面前有一排n個龍珠，第i顆龍珠的星級是xi。每顆龍珠賣1萬，並且只能買連續的若干顆，不能挑挑揀揀。請問至少要萬才能召喚神龍？
注意：星級為8或以上的龍珠沒用。
輸入輸出格式
輸入格式
輸入第一行為正整數n，第二行共n個正整數xi，在1到9之間。n<=100。
輸出格式
輸出一個正整數代表最小費用，若無法召喚輸出bye dragon
輸入輸出樣例
輸入樣例#1:
12
1 2 2 3 4 5 6 8 9 7 1 8
輸出樣例#1:
9
輸入樣例#2:
6
7 6 5 4 3 2
輸出樣例#2:
bye dragon
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
using namespace std;
const int N=109;
int n,x[N];
bool OK(int len){
int cnt[10]={};
int sum=0;
for(int i=1;i<=len;++i){
cnt[x[i]]++;
if(x[i]<=7&&cnt[x[i]]==1)sum++;
}
if(sum==7)return 1;
for(int i=len+1;i<+n;++i){
cnt[x[i]]++;
if(x[i]<=7&&cnt[x[i]]==1)sum++;
cnt[x[i-len]]--;
if(x[i-len]<=7&&cnt[x[i-len]]==0)sum--;
if(sum==7)return 1;
}
return 0;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>x[i];
int l=7;
int r=n;
int ans=n+1;
while(l<=r){
int mid=l+(r-l)/2;
if(OK(mid))ans=mid,r=mid-1;
else l=mid+1;
}
if(ans==n+1)
cout<<"bye dragon";
else
cout<<ans;
return 0;
}
- 免費旅遊1
題目描述
有一艘國際郵輪在世界各國穿梭n個星期，他每個星期會停靠一個國家，第i個星期所在國家的編號為xi。郵輪在招聘清潔工，雖然沒有工資，但可以免費去各國旅遊，你非常心動。如果你想至少玩k個不同國家，那麼至少在船上連續打工幾個星期？
假設你可以選擇任意一段連續的工作時間。
輸入輸出格式
輸入格式
輸入第一行為正整數n和k，第二行共n個正整數xi，在1到200之間。n<=1000。
輸出格式
輸出一個正整數代表最小星期數，若無法玩到k個國家輸出impossible
輸入輸出樣例
輸入樣例#1:
5 3
7 6 7 7 8
輸出樣例#1:
4
輸入樣例#2:
無
輸出樣例#2:
無
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
using namespace std;
int x[1009];
int n,k,l,r,ans;
int cnt[209];
int sum;
int main(){
cin>>n>>k;
for(int i=0;i<n;i++)cin>>x[i];
ans=n+1;
while(1){
while(r<n&&sum<k){
int num=x[r++];
cnt[num]++;
if(cnt[num]==1)sum++;
}
if(sum<k)break;
ans=min(ans,r-l);
int num=x[l++];
cnt[num]--;
if(cnt[num]==0)sum--;
}
if(ans==n+1)cout<<"impossible";
else cout<<ans;
return 0;
}
- 免費旅遊2
題目描述
有一艘國際郵輪在世界各國穿梭n個星期，他每個星期會停靠一個國家， 第i個星期所在國家的編號為xi。郵輪在招聘清潔工，雖然沒有工資，但 可以免費去各國旅遊，你非常心動。如果你想玩遍所有該郵輪到達的國家，那麼至少在船上連續打工幾個星期？
假設你可以選擇任意一段連續的工作星期。
輸入輸出格式
輸入格式
輸入第一行為正整數n，第二行共n個正整數xi，在1到200之間。n<=1000 。
輸出格式
輸出一個正整數代表最小星期數。
輸入輸出樣例
輸入樣例#1:
5
6 7 8 8 7
輸出樣例#1:
3
輸入樣例#2:
4
1 2 3 4
輸出樣例#2:
4
輸入樣例#3:
無
輸出樣例#3:
無
#include<bits/stdc++.h>
using namespace std;
int x[1009];
int n,k,l,r,ans;
int cnt[209];
set<int> jihe;
int sum;
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>x[i];
jihe.insert(x[i]);
}
k=jihe.size();
ans=n+1;
while(1){
while(r<n&&sum<k){
int num=x[r++];
cnt[num]++;
if(cnt[num]==1)sum++;
}
if(sum<k)break;
ans=min(ans,r-l);
int num=x[l++];
cnt[num]--;
if(cnt[num]==0)sum--;
}
if(ans==n+1)cout<<"impossible";
else cout<<ans;
return 0;
}
