文章目錄
- 1：單位變換
- 2：約數個數
- 3：葉節點數
- 4：數字9
- 5：數位遞增的數
- 6：遞增三元組
- 8:長草
- 9:序列計數
1：單位變換
【問題描述】
在計算機存盤中，15.125GB是多少MB？
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
15.125*1024=15488
答案：15488
2：約數個數
【問題描述】
1200000有多少個約數（只計算正約數），
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
#include <bits/stdc++.h>
#include <algorithm>
#define mod 1000000007
#define LL long long
using namespace std;
int a[100005],bi[100005];
int main()
{
int sum = 0;
for(int i = 1; i*i <= 1200000; i++){
if(1200000%i == 0){
sum++;
}
}
cout << sum * 2;
return 0;
}
答案：96
3：葉節點數
【問題描述】
一棵包含有2019個結點的二叉樹，最多包含多少個葉結點？
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
思路：
方法一：
設有n層
總節點數為2^n-1
第i層節點數最多為2^(i-1)
根據這兩個公式就可以算出答案，
方法二：
n=n0+n1+n2，為使葉子節點數（n0）最多，必須n1最小，設為0，而n0=n2+1
得n2=(2019-1)/2=1009
所有n1=1009+1=1010
答案：1010
4：數字9
【問題描述】
在1至2019中，有多少個數的數位中包含數字9？
注意，有的數中的數位中包含多個9，這個數只算一次，例如，1999這個數包含數字9，在計算時只是算一個數，
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
#include <bits/stdc++.h>
#include <algorithm>
#define mod 1000000007
#define LL long long
using namespace std;
bool judge(int x)
{
while(x){
int d = x % 10;
if(d == 9) return true;
x /= 10;
}
return false;
}
int main()
{
int cnt = 0;
for(int i = 1; i <= 2019; i++){
if(judge(i)){
cnt++;
}
}
cout << cnt << endl;
return 0;
}
答案：544
5：數位遞增的數
【問題描述】
一個正整數如果任何一個數位不大于右邊相鄰的數位，則稱為一個數位遞增的數，例如1135是一個數位遞增的數，而1024不是一個數位遞增的數，
給定正整數 n，請問在整數 1 至 n 中有多少個數位遞增的數？
【輸入格式】
輸入的第一行包含一個整數 n，
【輸出格式】
輸出一行包含一個整數，表示答案，
【樣例輸入】
30
【樣例輸出】
26
【評測用例規模與約定】
對于 40% 的評測用例，1 <= n <= 1000，
對于 80% 的評測用例，1 <= n <= 100000，
對于所有評測用例，1 <= n <= 1000000，
#include <bits/stdc++.h>
#include <algorithm>
#define mod 1000000007
#define LL long long
using namespace std;
bool judge(int x)
{
int k1,k2;
if(x >= 1 && x <= 9) return true;
k1 = x % 10;
x /= 10;
while(x){
k2 = x % 10;
if(k1 < k2) return false;
k1 = k2;
x /= 10;
}
return true;
}
int main()
{
int n,cnt = 0;
scanf("%d",&n);
for(int i = 1; i <= n; i++){
if(judge(i)){
cnt++;
}
}
printf("%d\n",cnt);
return 0;
}
6：遞增三元組
【問題描述】
在數列 a[1], a[2], …, a[n] 中，如果對于下標 i, j, k 滿足 0<i<j<k<n+1 且 a[i]<a[j]<a[k]，則稱 a[i], a[j], a[k] 為一組遞增三元組，a[j]為遞增三元組的中心，
給定一個數列，請問數列中有多少個元素可能是遞增三元組的中心，
【輸入格式】
輸入的第一行包含一個整數 n，
第二行包含 n 個整數 a[1], a[2], …, a[n]，相鄰的整數間用空格分隔，表示給定的數列，
【輸出格式】
輸出一行包含一個整數，表示答案，
【樣例輸入】
5
1 2 5 3 5
【樣例輸出】
2
【樣例說明】
a[2] 和 a[4] 可能是三元組的中心，
【評測用例規模與約定】
對于 50% 的評測用例，2 <= n <= 100，0 <= 數列中的數 <= 1000，
對于所有評測用例，2 <= n <= 1000，0 <= 數列中的數 <= 10000，
#include <bits/stdc++.h>
#include <algorithm>
#define mod 1000000007
#define LL long long
using namespace std;
int a[1005];
int main()
{
freopen("In.txt","r",stdin);
freopen("Out.txt","w",stdout);
int n;
while(~scanf("%d",&n)){
int cnt = 0;
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
for(int i = 1; i <= n; i++){
int flag1 = 0,flag2 = 0;
for(int j = 1; j < i; j++){
if(a[j] < a[i]){
flag1 = 1;
break;
}
}
for(int j = i+1; j <= n; j++){
if(a[j] > a[i]){
flag2 = 1;
break;
}
}
if(flag1 + flag2 == 2){
cnt++;
}
}
printf("%d\n",cnt);
}
return 0;
}
8:長草
【問題描述】
小明有一塊空地，他將這塊空地劃分為 n 行 m 列的小塊，每行和每列的長度都為 1，
小明選了其中的一些小塊空地，種上了草，其他小塊仍然保持是空地，
這些草長得很快，每個月，草都會向外長出一些，如果一個小塊種了草，則它將向自己的上、下、左、右四小塊空地擴展，這四小塊空地都將變為有草的小塊，
請告訴小明，k 個月后空地上哪些地方有草，
【輸入格式】
輸入的第一行包含兩個整數 n, m，
接下來 n 行，每行包含 m 個字母，表示初始的空地狀態，字母之間沒有空格，如果為小數點，表示為空地，如果字母為 g，表示種了草，
接下來包含一個整數 k，
【輸出格式】
輸出 n 行，每行包含 m 個字母，表示 k 個月后空地的狀態，如果為小數點，表示為空地，如果字母為 g，表示長了草，
【樣例輸入】
4 5
.g…
…
…g…
…
2
【樣例輸出】
gggg.
gggg.
ggggg
.ggg.
【評測用例規模與約定】
對于 30% 的評測用例，2 <= n, m <= 20，
對于 70% 的評測用例，2 <= n, m <= 100，
對于所有評測用例，2 <= n, m <= 1000，1 <= k <= 1000，
#include <bits/stdc++.h>
#include <algorithm>
#define mod 1000000007
#define LL long long
using namespace std;
struct node{
int x,y;
int l;
node(int a,int b,int k){
x = a;
y = b;
l = k;
}
};
queue<node>q;
int dis[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int vis[1005][1005];
int n,m,d;
bool check(int x,int y)
{
if(x <= 0 || x > n || y < 0 || y >= m) return false;
return true;
}
void bfs()
{
while(!q.empty()){
node s = q.front();
q.pop();
if(s.l >= d) continue;
for(int i = 0; i < 4; i++){
int x = s.x + dis[i][0];
int y = s.y + dis[i][1];
if(check(x,y) && !vis[x][y]){
q.push(node(x,y,s.l+1));
vis[x][y] = 1;
}
}
}
}
int main()
{
char s[1005][1005];
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++){
scanf("%s",&s[i]);
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < m; j++){
if(s[i][j] == 'g'){
q.push(node(i,j,0));
}
}
}
scanf("%d",&d);
bfs();
for(int i = 1; i <= n; i++){
for(int j = 0; j < m; j++){
if(s[i][j] == '.'){
if(vis[i][j])
printf("g");
else printf(".");
}
else printf("g");
}
printf("\n");
}
return 0;
}
9:序列計數
【問題描述】
小明想知道，滿足以下條件的正整數序列的數量：
- 第一項為 n；
- 第二項不超過 n；
- 從第三項開始，每一項小于前兩項的差的絕對值，
請計算，對于給定的 n，有多少種滿足條件的序列，
【輸入格式】
輸入一行包含一個整數 n，
【輸出格式】
輸出一個整數，表示答案，答案可能很大，請輸出答案除以10000的余數，
【樣例輸入】
4
【樣例輸出】
7
【樣例說明】
以下是滿足條件的序列：
4 1
4 1 1
4 1 2
4 2
4 2 1
4 3
4 4
【評測用例規模與約定】
對于 20% 的評測用例，1 <= n <= 5；
對于 50% 的評測用例，1 <= n <= 10；
對于 80% 的評測用例，1 <= n <= 100；
對于所有評測用例，1 <= n <= 1000，
思路:記憶化搜索,O(N^3),會超時,dp[pre][cur], pre表示序列的前一個數,cur表示序列的當前的數,dp[pre][cur]就表示前一個數是pre,當前數是cur的序列有多少個.
#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
int dp[1005][1005];
ll dfs(int pre,int cur)
{
if(dp[pre][cur]) return dp[pre][cur];
ll ans = 1;
for(int i = 1; i < abs(pre-cur); i++){
ans = (ans + dfs(cur,i))%10000;
}
dp[pre][cur] = ans;
return ans % 10000;
}
int main(){
int n;
ll ans = 0;
scanf("%d",&n);
for(int i = 1; i <= n; i++){
ans = (ans + dfs(n,i))%10000;
}
printf("%lld",ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/168957.html
標籤：其他