每日三百行代码 第十七天
#include<stdio.h>
#include<math.h>
int main(){
int n;
double m;
scanf("%d",&n);
if(n==1){
m=5.00;
}else{
m=5.0*pow(1.05,n-1);
}
printf("%.2lf",m);
}
#include <stdio.h>
int main()
{
printf("______ _ _ _ _ _ _ \n");
printf("| ___ \\ | | | | | | | | | | |\n");
printf("| |_/ /___ __| | | |__ | | ___ ___ __| | ___ ___| | |\n");
printf("| // _ \\/ _` | | '_ \\| |/ _ \\ / _ \\ / _` | / __/ _ \\ | |\n");
printf("| |\\ \\ __/ (_| | | |_) | | (_) | (_) | (_| | | (_| __/ | |\n");
printf("\\_| \\_\\___|\\__,_| |_.__/|_|\\___/ \\___/ \\__,_| \\___\\___|_|_|\n");
}
#include<stdio.h>
int flag=0;
void fun(int gold,int npc_1,int npc_2){
if(npc_1>0){
fun(gold-1,npc_1-1,npc_2);
}
if(npc_2>0){
fun(gold*2,npc_1,npc_2-1);
}
if(gold==1&&npc_1==1&&npc_2==0){
flag++;
return;
}
}
int main(){
int npc_1,npc_2;
scanf("%d %d",&npc_1,&npc_2);
fun(2,npc_1,npc_2);
printf("%d",flag);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
while (n--){
vector<int> v;
int temp;
cin>>temp;
v.push_back(temp);
while(cin.get()!='\n'){
cin>>temp;
v.push_back(temp);
}
sort(v.begin(),v.end());
cout<<v.back()<< ' ' <<v.front()<<endl;
}
return 0;
}
#include<stdio.h>
#include<string.h>
int main(){
int n,len;
char s[1001];
scanf("%d",&n);
getchar();
gets(s);
len=strlen(s);
n=n%len;
for(int i=len-n;i<len;i++){
printf("%c",s[i]);
}
for(int i=0;i<len-n;i++){
printf("%c",s[i]);
}
return 0;
}
#include<stdio.h>
int main(){
int n;
scanf("%d",&n);
printf("%.1lf%%",(5000.0/n)*100.0);
}
#include<stdio.h>
int main(){
int num[9][9]={
0};
int flag=1,sum=0;
int h,l;
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
scanf("%d",&num[i][j]);
if(num[i][j]==0){
h=i;
l=j;
}
}
}
for(int i=0;i<9;i++){
for(int j=1;j<9;j++){
if(num[h][j]==num[h][i]&&i!=j){
flag=0;
}
}
}
for(int i=0;i<9;i++){
for(int j=1;j<9;j++){
if(num[j][l]==num[i][l]&&i!=j){
flag=0;
}
}
}
for(int i=0;i<9;i++){
for(int j=1;j<9;j++){
for(int k=0;k<9;k++){
if(num[i][j]==num[i][k]&&j!=k){
flag=0;
}
}
}
}
for(int i=0;i<9;i++){
sum=sum+num[i][l];
}
if(flag==1){
printf("%d",45-sum);
}else{
printf("NO");
}
return 0;
}
本题要求找到对于每一个数组值，向后查找，如果遇到大于自身值的数组值，对应答案为向后的距离，如果不存在
则为0。
暴力查找只能通过部分测试点，因此解法可用二分查找或单调栈。
单调栈可保证栈中存放的值始终为当前所遍历到的最大值，从而避免无效查询，时间复杂度为O(n)。
本题给出单调栈的参考代码。
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main()
{
int len;
cin >> len;
vector<int> v(len);
vector<int> res(len, 0);
stack<int> st;
for (int i = 0; i < len; i++)
cin >> v[i];
for (int i = 0; i < len; ++i)
{
while (!st.empty() && v[i] > v[st.top()])
{
auto t = st.top();
st.pop();
res[t] = i - t;
}
st.push(i);
}
for (auto i : res)
cout << i << ' ';
return 0;
}
#include<iostream>
#include<cstdio>
using namespace std;
int hp, att;
int ghp = 100, gatt = 10;
double rnd(int hp, int ghp, int t) {
if (t == 0) //勇者
{
if (att >= ghp)
return 1;
else
return 0.05 + 0.95 * rnd(hp, ghp - att, 1);
} else {
double rtn = 0;
rtn += 0.2 * rnd(hp, ghp, 0);
if (gatt < hp)
rtn += 0.8 * rnd(hp - gatt, ghp, 0);
return rtn;
}
}
int main() {
cin >> hp >> att;
att += 5;
printf("%.2lf", rnd(hp, ghp, 0));
return 0;
}
蒙特卡洛算法（百分百超时）：
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX 1000000000
int game(int hp, int attack) {
int npcHp = hp, npcAttack = 5 + attack;
int pokemonHp = 100, pokemonAttack = 10;
while (1) {
pokemonHp -= npcAttack;
if (pokemonHp <= 0)
return 1;
if (rand() % 5)
return 1;
if (rand() % 20)
continue;
npcHp -= pokemonAttack;
if (npcHp <= 0)
return 0;
}
}
int main() {
srand((unsigned) time(NULL));
int hp, attack;
int res = 0;
scanf("%d %d", &hp, &attack);
for (int i = 0; i < MAX; ++i)
res += game(hp, attack);
printf("%.2lf", res * 1.0 / MAX);
return 0;
}
#include<iostream>
#include<queue>
using namespace std;
int mat[100][100];
bool vis[100][100];
struct node {
int x, y, dis;
node() = default;
node(int x, int y, int dis) : x(x), y(y), dis(dis) {
}
};
void bfs()
{
bool visS = false;
node beg = node(1, 1, 0);
queue<node> que;
que.push(beg);
vis[beg.x][beg.y] = true;
while (!que.empty()) {
node now = que.front();
que.pop();
if (now.x + 1 >= 1 && now.x + 1 <= 10 && now.y >= 1 && now.y <= 10
&& !vis[now.x + 1][now.y] && mat[now.x + 1][now.y] != 1) {
if (mat[now.x + 1][now.y] == 2)
visS = true;
if (mat[now.x + 1][now.y] == 3) {
if (visS)
cout << "S ";
else
cout << "R ";
cout << now.dis + 1;
}
que.push(node(now.x + 1, now.y, now.dis + 1));
vis[now.x + 1][now.y] = true;
}
if (now.x - 1 >= 1 && now.x - 1 <= 10 && now.y >= 1 && now.y <= 10
&& !vis[now.x - 1][now.y] && mat[now.x - 1][now.y] != 1) {
if (mat[now.x - 1][now.y] == 2)
visS = true;
if (mat[now.x - 1][now.y] == 3) {
if (visS)
cout << "S ";
else
cout << "R ";
cout << now.dis + 1;
}
que.push(node(now.x - 1, now.y, now.dis + 1));
vis[now.x - 1][now.y] = true;
}
if (now.x >= 1 && now.x <= 10 && now.y + 1 >= 1 && now.y + 1 <= 10
&& !vis[now.x][now.y + 1] && mat[now.x][now.y + 1] != 1) {
if (mat[now.x][now.y + 1] == 2)
visS = true;
if (mat[now.x][now.y + 1] == 3) {
if (visS)
cout << "S ";
else
cout << "R ";
cout << now.dis + 1;
}
que.push(node(now.x, now.y + 1, now.dis + 1));
vis[now.x][now.y + 1] = true;
}
if (now.x >= 1 && now.x <= 10 && now.y - 1 >= 1 && now.y - 1 <= 10
&& !vis[now.x][now.y - 1] && mat[now.x][now.y - 1] != 1) {
if (mat[now.x][now.y - 1] == 2)
visS = true;
if (mat[now.x][now.y - 1] == 3) {
if (visS)
cout << "S ";
else
cout << "R ";
cout << now.dis + 1;
}
que.push(node(now.x, now.y - 1, now.dis + 1));
vis[now.x][now.y - 1] = true;
}
}
}
int main()
{
int n = 10;
char ch;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> ch;
if (ch == 'X')
mat[i][j] = 1;
else if (ch == 'S')
mat[i][j] = 2;
else if (ch == 'R')
mat[i][j] = 3;
}
cin.ignore();
}
bfs();
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> map;
int n, m, ans = 0;
void dfs(int r, int c) {
if (r < 0 || r >= n || c < 0 || c >= m || map[r][c] == 0) return;
map[r][c] = 0;
int di[4] = {
0, 0, 1, -1};
int dj[4] = {
1, -1, 0, 0};
for (int i = 0; i < 4; i++)
dfs(r + di[i], c + dj[i]);
}
int main() {
cin >> n >> m;
map = vector<vector<int>>(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; ++j)
cin >> map[i][j];
for (int r = 0; r < n; ++r)
for (int c = 0; c < m; ++c)
if (map[r][c] != 0) {
++ans;
dfs(r, c);
}
cout << ans;
return 0;
}
#include<iostream>
#include<algorithm>
using namespace std;
int x;
int arr[100], b[100];
int sum;
int main()
{
cin >> x;
for (int i = 1; i <= 7; i++)
cin >> arr[i];
//计算在不释放技能的前提下拥有多少奖励
for (int i = 1; i <= 7; i++) {
cin >> b[i];
if (b[i])
sum += arr[i];
}
//以下计算释放技能产生的收益
int maxx = 0;
for (int i = 1; i <= 7 - x + 1; i++) {
int tmp = 0;
for (int j = i; j < i + x; j++)
if (!b[j])
tmp += arr[j];
if (tmp > maxx)
maxx = tmp;
}
cout << sum + maxx;
return 0;
}
#include<iostream>
#include<set>
#include<algorithm>
#define N 10000
using namespace std;
string sub, str;
int dp[N][N];
int main()
{
cin >> str >> sub;
if (sub[0] == str[0])
dp[0][0] = 1;
for (int j = 1; j < str.length(); j++)
if (sub[0] == str[j])
dp[0][j] = dp[0][j - 1] + 1;
else
dp[0][j] = dp[0][j - 1];
for (int i = 1; i < sub.length(); i++)
for (int j = 1; j < str.length(); j++) {
if (sub[i] == str[j])
dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
else
dp[i][j] = dp[i][j - 1];
}
cout << dp[sub.length() - 1][str.length() - 1];
return 0;
}
#include<iostream>
#include<cstdio>
#define rep(i, a, b) for(long long i=a;i<=b;i++)
using namespace std;
typedef long long ll;
ll n, m, s, t, dif[300050];
ll get(ll x)
{
if (x > 0) return -x * s;
else return -x * t;
}
int main()
{
scanf("%lld %lld% lld% lld", &n, &m, &s, &t);
ll v, w = 0, ans = 0;
rep(i, 0, n) {
scanf("%lld", &v);
if (i != 0) {
dif[i - 1] = v - w;
ans += get(dif[i - 1]);
}
w = v;
}
rep(i, 1, m) {
ll a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);
ans -= get(dif[a - 1]);
dif[a - 1] += c;
ans += get(dif[a - 1]);
if (b != n) {
ans -= get(dif[b]);
dif[b] -= c;
ans += get(dif[b]);
}
printf("%lld\n", ans);
}
return 0;
}
#include<iostream>
#include<algorithm>
using namespace std;
int t;
int dp[1000000];
int n = 100000;
int main()
{
for (int i = 1; i <= n; i++)
dp[i] = 0x7fffffff; //0x7fffffff等价INT_MAX
dp[1] = 1;
for (int i = 1; i <= n; i++) {
dp[i + 1] = min(dp[i + 1], dp[i] + 1);
dp[i * 2] = min(dp[i * 2], dp[i] + 1);
dp[i * 3] = min(dp[i * 3], dp[i] + 1);
}
cin >> t;
while (t--) {
int x;
cin >> x;
cout << dp[x] << endl;
}
return 0;
}
京公网安备 11010502036488号