ブルーブリッジカップ校内模擬試合

45738 ワード

ブルーブリッジカップ校内模擬試合
  • A約
  • Bメモリ
  • C桁は9
  • である.
  • Dツリーのリーフノード
  • E文字列
  • F配列
  • G逆シーケンス
  • H bfs
  • I数列
  • Jパーティー
  • A約数
    1200,000は何個の約数がありますか(正の約数だけを計算します).
    #include
    using namespace std;
    
    int main(){
    	int ans = 0 ,i,n=1200000;
    	for( i=1;i*i<n;++i){
    		if(n%i==0)ans+=2;
    	}
    	if(i*i==n)ans+=1;
    	printf("%d",ans);//96
    }
    

    Bメモリ
    コンピュータのストレージの中で、15.125 GBは何MBですか?
    #include
    using namespace std;
    
    int main(){
    	double d = 15.125;
    	printf("%.2lf",d*1024);//15488
    }
    

    C桁は9
    1から2019の中で、何個の数の桁に数字9が含まれていますか?注意、ある数の中の数位には複数の9が含まれており、この数は一度だけ計算されます.例えば、1999という数は数字9を含み、計算では1つの数にすぎない.
    #include
    using namespace std;
    
    int main(){
    	int n=2019,ans=0,f,j;
    	for(int i=9;i<=n;++i){
    		f=0;
            j=i;
    		while(j){
    			if(j%10==9){
    				f=1;
    				break;
    			}
    			j/=10;
    		}
    		if(f)ans++;
    	}
    	printf("%d",ans);//544
    }
    

    Dツリーのリーフノード
    2019個のノードを含む木で、最大何個の葉ノードが含まれていますか?
    n 0 = n 2 + 1 n_0=n_2+1 n 0=n 2+1なのでn 0=[n/2](上向きに整列)=1010 n_0=[n/2](上向き整列)=1010 n 0=[n/2](上向き整列)=1010一般的なmフォークツリーn 0=1+Σi=2 m(i−1)n i n_0=1+\sum\limits_{i=2}^{m}(i-1)n_i n0​=1+i=2∑m​(i−1)ni​, m a x ( n 0 ) = 1 + n m ∗ ( m − 1 ) ⇒ n 0 = 2018 max(n_0)=1+n_m*(m-1)\Rightarrow n_0=2018 max(n0​)=1+nm​∗(m−1)⇒n0​=2018
    E文字列
    #include
    using namespace std;
    string s;
    int i=0;
    
    /**
     * @brief             a, e, i, o, u
    */
    bool judeg(char c){
    	return c=='a'||c=='e'||c=='i'||c=='o'||c=='u';
    }
    
    /**
     * @brief         
    */
    int f1(){
    	int ans=0;
    	for(;i<s.size();++i)if(judeg(s[i])==false)ans++; else break;
    	return ans;
    }
    
    /**
     * @brief         
    */
    int f2(){
    	int ans=0;
    	for(;i<s.size();++i)if(judeg(s[i])==true)ans++; else break;
    	return ans;
    }
    
    int main(){
    	cin>>s;
    	if(f1()>0&&f2()>0&&f1()>0&&f2()>0&&i==s.size())printf("yes
    "
    ); else printf("no
    "
    );// }

    F配列
    数列a[1],a[2],...,a[n]では,下付きi,j,kが0を満たすために1つの数列が与えられる場合,数列にどれだけの要素が増分三元群の中心である可能性があるかを尋ねる.(n<1000)
    #include
    using namespace std;
    const int N = 1e3+3;
    int n;
    int a[N];
    
    /**
     * @brief    a[N]    [b,n)    
    */
    int Max(int b){
    	int ans = a[b];
    	for(int i=b;i<n;++i)if(a[i]>ans)ans=a[i];
    	return ans;
    }
    
    int main(){
    	scanf("%d",&n);
    	for(int i=0;i<n;++i)scanf("%d",&a[i]);
    	int Min=a[0],ans=0;
    	for(int i=1;i<n-1;++i){
    		if(Min<a[i]&&a[i]<Max(i+1))ans++;
    		if(Min>a[i])a[i]=Min;
    	}
    	printf("%d
    "
    ,ans); }

    O(n)最適化
    #include
    using namespace std;
    const int N = 1e3+3;
    int n;
    int a[N];
    int leftMin[N];//leftMin[i]=min(a[0]~a[i])
    int rightMax[N];//rightMax[i]=max(a[i]~a[n-1])
    //        leftMin[i]int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i)scanf("%d",&a[i]);
    leftMin[0]=a[0];
    rightMax[n-1]=a[n-1];
    for(int i=1;i<n-1;++i)leftMin[i]=min(leftMin[i-1],a[i]);
    for(int i=n-2;i>0;--i)rightMax[i]=max(rightMax[i+1],a[i]);
    int ans=0;
    for(int i=1;i<n-1;++i)if(a[i]>leftMin[i]&&a[i]<rightMax[i])ans++;
    printf("%d",ans);   
    }

    G逆序数
    正の整数のいずれかの数が右隣の数よりも大きくない場合、1つの数の増加数と呼ばれ、例えば1135は1つの数の増加数であり、1024は1つの数の増加数ではない.正の整数nを与えて、整数の1からnの中で何個の数桁の増加する数がありますか?
    #include
    using namespace std;
    
    int a[10],m;
    
    /**
     * @brief        d                    。
    */
    bool judge(int d){
    	m = 0;
    	while(d){
    		a[m++]=d%10;
    		d/=10;
    	}
    	for(int i=m-1;i>0;--i){
    		if(a[i]>a[i-1])return false;
    	}
    	return true;
    }
    
    int main(){
    	int n,ans=0;
    	scanf("%d",&n);
    	for(int i=1;i<=n;++i){
    		if(judge(i))ans++;
    	}
    	printf("%d
    "
    ,ans); return 0; }

    H bfs
    明ちゃんは空き地を持っていて、彼はこの空き地をn行m列の小さな塊に分けて、各行と各列の長さはすべて1です.明ちゃんはその中のいくつかの小さな空き地を選んで、草を植えて、他の小さな塊は依然として空き地を維持しています.これらの草は成長が速く、毎月、草は外に少し生えています.もし小さな塊が草を植えたら、自分の上、下、左、右の4つの小さな空き地に広がり、この4つの小さな空き地は草のある小さな塊になります.明ちゃんに、kヶ月後の空き地に草があるところを教えてください.
    #include
    using namespace std;
    const int N = 1e3+3;
    int n,m,k;
    char g[N][N];
    int pos[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//    
    struct Node
    {
    	int x,y;
    	Node(int x,int y):x(x),y(y){}
    	Node(){}
    };
    
    queue<Node> pre;//    
    queue<Node> _next;//    
    
    void bfs(){
    	int xx,yy;
    	Node node; 
    	for(int i=0;i<k;++i){
    		
    		while(!pre.empty()){
    			node=pre.front();
    			pre.pop();
    			for(int j=0;j<4;++j){
    				xx = node.x+pos[j][0];
    				yy = node.y+pos[j][1];
    				if(xx>=0&&xx<n&&yy>=0&&yy<=m&&g[xx][yy]=='.'){
    					g[xx][yy]='g';
    					_next.push(Node(xx,yy));
    				}
    			}
    		}
    		while(!_next.empty()){
    			pre.push(_next.front());
    			_next.pop();
    		}
    	}
    }
    
    int main(){
    	std::ios::sync_with_stdio(false);
    	cin.tie(0);//       
    	cin>>n>>m;
    	for(int i=0;i<n;++i){
    		for(int j=0;j<m;++j){
    			cin>>g[i][j];
    			if(g[i][j]=='g')pre.push(Node(i,j));
    		}
    	}
    	cin>>k;
    	bfs();
    	for(int i=0;i<n;++i){
    		for(int j=0;j<m;++j)cout<<g[i][j];
    		cout<<"
    "
    ; } return 0; }

    I数列
    明ちゃんは、以下の条件を満たす正の整数シーケンスの数を知りたいです:1.第1項はnである.  2. 第2項はnを超えない.  3. 3番目の項目から、各項目は前の2つの項目の差の絶対値より小さい.与えられたnに対して、条件を満たすシーケンスがどれだけあるかを計算してください.出力答えを10000の余数で割った.  1 <= n <= 1000
    #include
    using namespace std;
    
    
    /*
     1.      n;
     2.        n;
     3.       ,              
    */
    
    int ans=0;
    const int MOD =1e4;
    void mod(int &d){
    	if(d>MOD)d-=MOD;
    }
    
    //          
    void recursion(int a,int b){
    	int z = abs(a-b);
    	ans++;mod(ans);
    	for(int i=1;i<z;++i){
    		recursion(b,i);
    	}
    }
    
    int main(){
    	int n;
    	scanf("%d",&n);
    	for(int i=1;i<=n;++i)recursion(4,i);
    	printf("%d
    "
    ,ans); }

    Jパーティー
    明ちゃんはパーティーを組織して、全部でnつの番組を用意しました.そしてパーティーの時間は限られていて、彼は最終的にその中のm番組を選ぶしかありません.このn番组は明ちゃんが想定した顺番で与えられたもので、顺番は変えられない.明ちゃんは、観客の夜の好きさと前のいくつかの番組の美しさには非常に大きな関係があることを発見しました.彼は選んだ最初の番組ができるだけきれいになることを望んでいます.その前提の下で、2番目の番組ができるだけきれいになることを望んでいます.明ちゃんは各番組にきれいな値を定義しました.明ちゃんがm番組を選んで、彼の要求を満たすのを助けてください.1<=n<=100000,0<=番組の見栄え<=100000.