2020 7月月赛题解

Tawn 2020-07-04 22:38:05 2020-07-12 14:40:23

2020 7月月赛题解

1001. 如意如意

签到题,直接输出心愿即可。
ps: 注意文件 IO 和头文件。

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
	freopen("hello.out", "w", stdout);
	cout << "TJTJAKAK" << endl;
	return 0;
}

1002. 哈哈哈哈

题目要求输出部分故事。
可以看出该故事是无限循环的,所以我们先找出其最短循环节,然后计算需要输出多少完整的循环体和多长的部循环体,分别采用整除 / 和取余 % 进行计算。

#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
using namespace std;

int main()
{
	freopen("hahahaha.in", "r", stdin);
	freopen("hahahaha.out", "w", stdout);
    string s = "Once upon a time, there was a temple on the mountain. There were a young monk and an old monk in the temple. One day, the old monk told the young monk a story:";
    int n;
    cin >> n;
    int d = n/s.size();
    string res = "";
    for(int i = 0; i < d; i++)
        res += s;
    res += s.substr(0, n%s.size());
    cout << res << endl;
    return 0;
}

1003. 翻翻象棋

思维题,通过观察和手动模拟可以推出:
当两颗棋子的曼哈顿距离 2 0 时为平局,否则 Mike 赢。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int r1, c1, r2, c2;
int main()
{
    freopen("chess.in", "r", stdin);
    freopen("chess.out", "w", stdout);
    cin >> r1 >> c1 >> r2 >> c2;
    if((abs(r1-r2) + abs(c1-c2)) % 2 == 0)
        cout << "DRAW" << endl;
    else cout << "WIN" << endl;
    return 0;
}

1004. 时间换算

模拟题,往后倒推 12h 即可。
注意日和月的变化,如果倒推到 2 月需要检查是否为闰年。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int trans(string s)
{
    int res = 0;
    for(int i = 0; i < s.size(); i++)
        res = res*10 + (s[i]-'0');
    return res;
}

string trans(int x, int l)
{
    string res = "";
    for(int i = 0; i < l; i++)
    {
        res += char(x%10+'0');
        x /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

string tb;
int m2d[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main()
{
    freopen("time.in", "r", stdin);
    freopen("time.out", "w", stdout);
    cin >> tb;
    int y = trans(tb.substr(0, 4));
    int m = trans(tb.substr(4, 2));
    int d = trans(tb.substr(6, 2));
    int h = trans(tb.substr(8, 2));
    
    h -= 12;
    if(h < 0)
    {
        d --;
        h += 24;
        if(d < 1)
        {
            m --;
            if(m < 1)
            {
                y --;
                m += 12;
                d = m2d[m];
            }
            else
            {
                d = m2d[m];
                if((y%400 == 0 || (y%4 == 0 && y%100 != 0)) && m == 2) d++; 
            }
        }
    }
    string tn = trans(y, 4) + trans(m, 2) + trans(d, 2) + trans(h, 2) + tb.substr(10,2);
    cout << tn << endl;
    return 0;
}

1005. 恶龙咆哮I

逆向思维+ BFS
题目要求朋友们到城堡的最短距离,即求从城堡出发到朋友们所在地的最短距离。
因为每次移动为一个单位距离,所以直接以城堡为起点进行 BFS 即可。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 1000 + 10;
typedef pair<int, int> P;

int n, m, sx, sy;
int dis[maxn][maxn];
char g[maxn][maxn];
int fx[] = {0, 0, -1, 1};
int fy[] = {1, -1, 0, 0};

bool check(int x, int y)
{
  if(x < 0 || y < 0 || x >= n || y >= m) return false;
  if(g[x][y] == '#') return false;
  return true;
}

void bfs()
{
  memset(dis, -1, sizeof(dis));
  queue<P> que;
  que.push(P(sx, sy));
  dis[sx][sy] = 0;
  while(!que.empty())
  {
    P p = que.front();
    que.pop();
    for(int i = 0; i < 4; i++)
    {
      int ix = p.first + fx[i];
      int iy = p.second + fy[i];
      if(check(ix, iy) && dis[ix][iy] == -1)
      {
          dis[ix][iy] = dis[p.first][p.second] + 1;
          que.push(P(ix, iy));
      }
    }
  }
}

int main()
{
    freopen("map.in", "r", stdin);
    freopen("map.out", "w", stdout);
    scanf("%d%d", &n, &m);
    getchar();
    for(int i = 0; i < n; i++)
        gets(g[i]);
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        if(g[i][j] == 'C'){sx = i;sy = j;}
    bfs();
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        {
          if(g[i][j] == 'F') printf("%d", dis[i][j]);
          else printf("-1");
          if(j == m-1)  printf("\n");
          else printf(" ");
        }
    return 0;
}

1006. 恶龙咆哮II

贪心,因为攻击力在连击中可以累积,所以需要尽可能的达成连击,且需要尽量将攻击力大的攻击放入尽可能长的连击内。
思路:将攻击力序列从小到到排序,每次从后往前抽取一个子序列构成连击,要求子序列中相邻攻击的攻击力之差大于 G ,直至原序列为空。
实现:利用 multiset 的底层为有序结构的特点,将整个攻击序列放入 multiset 中,然后从后往前利用 upper\_bound 二分查找攻击力组成连击,每找到一个符合条件的攻击力,累计答案并将之从 multiset 中删除。总的时间复杂度为 nlogn

#include <cstdio>
#include <set>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
int n, g;
int main(){
    freopen("dragon.in","r", stdin);
    freopen("dragon.out", "w", stdout);
    scanf("%d%d", &n, &g);
    multiset<ll> st;
    for(int i = 1;i <= n;++i) {
    int x;
    scanf("%d", &x);
    st.insert(-x);
    }
    ll ans=0,num=0,pre=ll(-1e12);
    while(!st.empty()){
        auto it = st.upper_bound(pre + g);
        if(it == st.end()) {
            pre = ll(-1e12);
            num = 0;
        }
        else{
            pre = *it;
            num ++;
            ans += *it*num;
            st.erase(it);
        }
    }
    printf("%lld\n", -ans);
    return 0;
}

Congratulations

共 4 条回复

ckj

前排

maguangxian
[已删除]
maguangxian

后排

1478520

前排兹磁

AMAZE UI
Hello world!