牛客周赛 Round 83

A.和猫猫一起起舞！

思路：遇到‘U’和‘D’，输出‘R’或者‘L’；遇到‘R’和‘L’，输出‘U’或者‘D’.(这题比较简单)

AC代码：

void solve()
{int n, m, k;char ch;cin >> ch;if (ch == 'U' || ch == 'D'){cout << 'L' << endl;}else {cout << 'U' << endl;}
}

 B.冒险猫猫参上！！

思路：被样例误导了wa了一发，发现总共的石子数为3*n，而从1到n来输出只能在时满足，这能通过式子来推出来：

所以得考虑其他办法，这里很容易想到放1、2、1....来间隔放是肯定可以，并且保证不会超过.

AC代码：

void solve()
{int n;cin >> n;for (int i = 0; i<=n; i++){cout << i << " \n"[i==n];}
}

C. 泉神，启动！！！

思路：这里很容易发现为11,101,1001,这样类型的其中第一个1后面的位数为x的位数，这里将x转换成字符串很快能求出其位数。

AC代码：

void solve()
{int n;cin >> n;int num = to_string(n).size();int res = pow(10, num)+1;cout << res << endl;
}

 D.大预言家！！！！

思路：这个图形能看出来是跟正方形有关的，也就是说跟平方数有关，这里列出其平方数的位置观察，这里发现平方数后会向左或者右移动一次，再有两次的移动，所以我们这里只要二分一下平方数，并判断奇偶数来分别讨论一下，我的代码比较复杂，其实应该不用写这么多

AC代码： 

void solve()
{int n, m, k;cin >> n;int l = 0, r = 1e9;while (l+1 < r){int mid = (l+r)/2;if (mid*mid > n) r = mid;else l = mid;}r--;int x, y;if(r % 2 == 0){x = -(r/2)+1, y = -(r/2);if (r*r == n){cout << x << " " << y << endl;return ;}x--;if (r*r+1 == n){cout << x << " " << y << endl;return ;}if (r*r+1+r >= n){y += n-(r*r+1);cout << x << " " << y << endl;return ;}if (r*r+1+2*r >= n){y += r;x += n-(r*r+1+r);cout << x << " " << y << endl;return ;}}else{x = r/2, y = r/2;if (r * r == n){cout << x << " " << y << endl;return ;}x++;if (r*r+1 == n){cout << x << " " << y << endl;return ;}if (r*r+1+r >= n){y -= (n-(r*r+1));cout << x << " " << y << endl;return ;}if (r*r+1+2*r >= n){y -= r;x -= (n-(r*r+1+r));cout << x << " " << y << endl;return ;}}
}

E.全都要！！！！！

思路：能想到用dp，其实认真做一下动态转移即可

AC代码：

void solve()
{int n, m, k;cin >> n >> k;vector<vector<int>> dp(n+1, vector<int>(k+1, -INF));dp[0][0] = 0; // dp[i][j]表示第j步到达i位置的最大值vector<int> val(n+1);for (int i = 1; i<=n; i++) cin >> val[i];int ans = -INF;for (int i = 1; i<=n; i++){for (int j = 1; j<=min(i, k); j++){for (int p = max(0ll, i-6);  p<=i-1; p++){dp[i][j] = max(dp[i][j], dp[p][j-1]+val[i]);}}ans = max(ans, dp[i][k]);}cout << ans << endl;
}

void solve()
{int n, m, k;cin >> n >> k;vector<vector<int>> dp(k+1, vector<int>(n+1, -INF));dp[0][0] = 0;  // dp[i][j]表示第i步到达j位置的最大值vector<int> val(n+1);for (int i = 1; i<=n; i++) cin >> val[i];for (int i = 1; i<=k; i++){for (int j = i; j<=min(i*6, n); j++){for (int s = 1; s <= 6; s++){if (j-s < 0) break;dp[i][j] = max(dp[i][j], dp[i-1][j-s]+val[j]);}}}int ans = -INF;for (int i = 1; i<=n; i++){ans = max(ans, dp[k][i]);}cout << ans << endl;
}

F.水题！！！！！！

思路：因为已经确定为起点，并且对bfs熟悉的同学，应该很任意想到，遇到‘#’只要用优先队列给他排在now+t,然后其他就是模拟的部分，嗯，对，就说这么多，看代码应该能看懂。。其中解释一下结构体内的变量，dep表示为从头开始的时间，state表示是否为向下的水流，其他就是特判之类的细节。。。。这是真水题啊

AC代码：

struct node{int x, y, dep, state;bool operator < (const node& other) const{return dep > other.dep;}
};
void solve()
{int n, m, t;cin >> n >> m >> t;t++;vector<vector<char>> G(n+5, vector<char>(m+5, ' '));pair<int, int> sta;for (int i = 1; i<=n; i++){for (int j = 1; j<=m; j++){cin >> G[i][j];if (G[i][j] == '*') sta = mp(i, j);}} vector<vector<int>> vis(n+5, vector<int>(m+5,0));priority_queue<node> q;q.push({sta.first, sta.second, 0, 1});while (!q.empty()){auto [x, y, dep, state] = q.top();q.pop();if (state != 1)if (vis[x][y]) continue;vis[x][y] = 1;if (G[x][y] == '%'){cout << dep << endl;return ;}if (G[x+1][y] == '#'){if (state && !vis[x+1][y]) q.push({x+1, y, dep+t, 1});if (y+1 <= m && G[x][y+1]!='#') q.push({x, y+1, dep+1, 0});if (y-1 >=1 && G[x][y-1] != '#') q.push({x, y-1, dep+1, 0});}else {if (x+1 <= n) q.push({x+1, y, dep+1, 1});}}cout << -1 << endl;
}