總結
雖然是網路賽，但這是我們這支新組的隊伍第一次一起打比賽，感覺配合上還是十分生疏，尤其是讀題上，B題足足花了五十分鐘才讀明白到底是什么意思（離譜），
開局三個人一起看了一眼A，題目很短基本上幾秒鐘就看懂什么意思，然后一個隊友開始想A，我看了一眼榜，發現有個隊伍17秒秒殺了B（更離譜了），發現這題真長的離譜，然后我叫另外一個隊友研究這道題到底啥意思，中間把A切了，于是就變成了我們三個一起研究這題啥意思，，終于在五十分鐘的時候終于看懂了（英語不行是這樣的），在紙上模擬了幾種情況，發現大部分情況都只輸出2就行了，然后我上機把這題切了，
這時我們看了一眼榜，D做出來的很多，E和I也有很多做出來的，于是我們開始同時看D和E（后悔沒看I這道模擬），D是一道概率dp，我前幾天剛剛做了一道幾乎一毛一樣的題，于是我在紙上開始推式子，讓隊友繼續看題，后來不知道怎么回事，可能是我腦殘了，我自己把自己否了，覺得這道題不可能dp推出來（賽后再看，和我之前做的那道題真的一模一樣，就是題面不一樣），于是就想用二維陣列模擬期望，于是直到最后我都沒能做出來，，
隊友看出E是區間dp，可惜我們沒有一個人能把這個區間dp寫出來，只能怪我們做題太少了吧
最后二題結束，雖然學長安慰我們說還行，但是還有一點不甘心的吧，感覺確實可以四題甚至五題的，
題解
- A Easy Equation
- B XTL's Chessboard
- D Pokemon Ultra Sun
- E Eat Walnuts
- I Character Wheels
A Easy Equation
題目鏈接
題目
You are given four positive integers 𝑥, 𝑦, 𝑧, 𝑘, please help little M calculate the number of equations 𝑥 + 𝑦 + 𝑧 = 𝑘 when 0 ≤ 𝑥 ≤ 𝑎, 0 ≤ 𝑦 ≤ 𝑏, 0 ≤ 𝑧 ≤ 𝑐, 0 ≤ 𝑘 ≤ 𝑑
輸入描述:
Four integers 𝑎, 𝑏, 𝑐, 𝑑 (0 ≤ 𝑎, 𝑏, 𝑐, 𝑑 ≤106)
輸出描述:
One integer the number of equations.
It is guaranteed that all the answers fit 64-bit integer.
題意
給出四個整數a,b,c,d，求滿足 𝑥 + 𝑦 + 𝑧 = 𝑘 且 0 ≤ 𝑥 ≤ 𝑎, 0 ≤ 𝑦 ≤ 𝑏, 0 ≤ 𝑧 ≤ 𝑐, 0 ≤ 𝑘 ≤ 𝑑 的整數解的數量
思路
這題是我OB的，大體思路就是把式子變形成𝑦 + 𝑧 = 𝑘 - 𝑥，然后列舉𝑘 - 𝑥的所有可能性和每個可能性有多少種情況，再看左面有多少種可能，相乘再相加就得到答案
代碼
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(void) {
ll a,b,c,d,k,x,y,z;
cin >> a >> b >> c >> d;
ll sum = 0ll;
for(ll i = 0; i <= d; i++) {
if(i > b + c)continue;
sum += min(min(i, c) - max(0ll, i - b) + 1, min(i, b) - max(0ll, i - c) + 1) * min(a + 1ll, d + 1ll - i);
}
cout << sum << '\n';
return 0;
}
B XTL’s Chessboard
題目鏈接
題目
Xutianli is a perfectionist, who only owns “Good Chessboard”.
A well-known definition to the Good Chessboard is that there exists two integers u,v which satisfies ux+vy=1+u+v, with the given length x and width y.
Once Zjx came to XTL’s home and brought a small ball. This ball was originally used to hit XTL, because he always touches fish under the pan pond every day（touch fish means dereliction of duty）. However, seeing that XTL had really worked conscientiously and enthusiastically, Zjx felt very guilty and gave the ball to XTL as a gift.
After that is a boring time of two boys. XTL design a game based on his “Good Chessboard” Prescribed procedure is as follows.
On the rectangular chessboard composed of squares of X * Y, select a left or bottom grid as the starting grid, and then place a ball in the center of the grid. The diameter of the ball is the length of the side of a grid on the chessboard. Push the ball up 45 degrees to make it roll on the chessboard. When the ball touches the edge of the board, it will bounce back. The rebound rule is: the rebounding route is perpendicular to the original route, just as the reflection of light on a plane mirror. If the ball attaches the corner, it will roll back according to the original route. The ball moves on the chessboard from the starting grid (if the starting grid is in the upper left or lower right corner, it will rebound immediately at the beginning) until it returns to the starting grid.
XTL will take a piece of his cherished chessboard from his storeroom, place the ball, and kick it obliquely up 45 degrees to let Zjx count the number of grids the ball has passed through for odd number of times and tell XTL the answer after the ball stops moving.
Zjx dislikes the game as boring. He wants to do some homework about the Lie Algebroid connection, to discuss some properties about commutative group, to find out some new Mathematical technique in order to improve the effectiveness and robustness of traditional algorithms, and finally send several SCI articles randomly for the sake of postgraduate recommendation.
Smart as you, can you tell him the solution OF this extremely depressing Question?
輸入描述:
The input consists of a single test case specified with two lines. The first line contains four integers x, y, a and b, where x is the length of the chessboard, y is the width of chessboard, a,b is the coordinate of the starting grids(x，y>=2，x*y<=1000000000)
輸出描述:
The output consists of a single integer, representing the number of grids the ball has passed through for odd number of times.
題意
給出n * m的棋盤和小球初始坐標（a，b），小球只能斜向45°移動，碰到邊界會鏡面反彈，碰到角落會原路反彈，問小球經過的路徑會有多少個格子經過了奇數次，
思路
在紙上稍微畫一下就會發現大部分情況都會碰到角落然后原路回傳，這樣除了起點和角落的格子，其他格子都經過偶數次（去一次和回來一次）除了在正方形棋盤和幾個正方形連接在一起棋盤（這些棋盤會共用連接的一條邊，因此n和m滿足n=（k - 1）*（m - 1）+ m的情況時就是這種情況，其中k是正方形的個數，除了棋盤滿足以外，還要特判小球是否是從角落出發），直接輸出2就可以了，
代碼
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(void) {
int x,y,a,b;
cin >> x >> y >> a >> b;
int n = x, m = y;
if(x > y)swap(x, y);
if((y - x) % (x - 1) == 0) {
if((a == 1 && b == 1) || (a == 1 && b == m) || (a == n && b == m) || (a == n && b == 1)) {
cout << 2 << '\n';
}else {
int num = (y - x) / (x - 1) + 1;
cout << num * (x * 2 - 3) + 2 - num << '\n';
}
}else {
cout << 2 << '\n';
}
}
D Pokemon Ultra Sun
題目鏈接
題目
Two pokemons are in a battle.One is our and another is the opposite’s.
Our pokemon is in confusion and the opposite’s pokemon is frozen.
Once per turn , the opposite’s pokemon does nothing and our pokemon gives w damages to the opposite’s pokemon with a probability of P while gives w damages to itself with a probability of 1 ? P.
Our pokemon has hp1 health points and the opposite’s pokemon has hp2 health points.
If one pokemon’s health points are zero or below zero, the game is over.
Your task is to calculate the expected number of turn.
輸入描述:
The ?rst line is an integer T(T ≤ 8) , the number of test cases.
For each test case, the ?rst line contains three integers hp1, hp2, w(1 ≤ hp1, hp2, w ≤ 3000), representing our pokemon’s health points, the opposite’s health points and damage. The second line contains a real number P(0 < P < 1). which is described above.
輸出描述:
For each test case, print the expected number of turn rounding to 6 digits after decimal in one line.
題意
給出a，b兩個正整數，每回合有p的概率將b減去w，1-p的概率將a減去w，當a或b小于等于0時游戲結束，詢問游戲結束回合數的數學期望，
思路
概率dp，dp[i][j]表示a為i且b為j時的游戲結束數學期望
dp[i][j] = 1 + p * dp[i][j - w] + (1 - p) * dp[i - w][j]
代碼
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int MAXN = 2e5 + 5;
int t, n, m, k, flag = 1;
double dp[3005][3005];
int main(void) {
IO;
cin >> t;
while(t--) {
memset(dp, 0, sizeof(dp));
int hp1, hp2, w;
double p;
cin >> hp1 >> hp2 >> w >> p;
for(int i = 1; i <= hp1; i++) {
for(int j = 1; j <= hp2; j++) {
dp[i][j] = p * dp[i][max(0, j - w)] + (1 - p) * dp[max(0, i - w)][j] + 1;
}
}
printf("%.6lf\n", dp[hp1][hp2]);
}
}
E Eat Walnuts
題目鏈接
題目
As we all know, in the ACM ICPC held in 2017, the organizer of Xinjiang University presented a box of walnuts to each coach. Our coach is happy to share with the team members except Mr.Watermelon. He is going to test Mr.Watermelon with a game when Mr.Watermelon want to eat some walnuts.
He put some walnuts in a row and let Mr.Watermelon pick one of them. And this walnut is not the ?rst or last in the queue. The price Mr.Watermelon need to pay is : the walnut, the walnut in front of the walnut, and the walnut behind the walnut , the square of the sum of the size of these three walnuts.
For example, now there is a row of walnuts in front of Mr.Watermelon. Their size is: 3 1 50 20 15. If this time Mr.Watermelon picked the third walnut. He needs to pay (1 + 50 + 20) ? (1 + 50 + 20) = 5041.
After a walnut is taken away, it will leave the queue. Then Mr.Watermelon picks a walnut again until only two walnuts remain in the queue.
Mr.Watermelon wants to know what the minimum price he will pay when he takes walnuts until there are only two walnuts in the queue. But he needs more time to spend with his girlfriend. So he ask you to help him calculate this problem.
輸入描述:
Input contains multiple test cases.The ?rst line of each test case contains a integer n(3 ≤ n ≤ 100), the number of walnuts at the beginning. The second line contains n positive integers separated by spaces, representing the size of each walnut. Each positive integer does not exceed 1,000.
For 50% of the testcases, n ≤ 50.
For 90% of the testcases, n ≤ 90.
For 100% of the testcases, n ≤ 100.
The number of the testcases does not exceed 1000.
輸出描述:
For each test case, print a integer–the minimum price Mr.Watermelon will pay.
題意
有n個數字的序列a，每次能從a2到an-1選擇一個數字ai消去，消去的花費是(ai-1+ai+ai+1)2,問直到序列只有兩個數字的最低花費總和
思路
區間dp，dp[i][j]表示將i到j的序列全部消去需要的最低花費
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] +(ai+ak+aj)2)
代碼
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x7fffffff
const int MAXN = 2e5 + 5;
int t, n;
ll dp[105][105];
ll a[105];
ll x(ll p) {return p * p;}
int main(void) {
IO;
while(cin >> n) {
for(int i = 1; i <= n; i++) cin >> a[i];
for(int len = 3; len <= n; len++) {
for(int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
dp[i][j] = inf;
for(int k = i + 1; k < j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + x(a[i] + a[j] + a[k]));
}
}
cout << dp[1][n] << '\n';
}
}
I Character Wheels
題目鏈接
題目
鏈接：https://ac.nowcoder.com/acm/contest/8688/I
來源：牛客網
You are given one n \times nn×n character wheels, and it is guaranteed that n is even. Please implement these following operations:
Clockwise/Counter-clockwise rotate the x-th wheel y(1≤y≤109 ) times. Rotating one time means rotatting 90 degrees. The instruction is L/R x y, R indicates rotating clockwise and L indicates rotating counter-clockwise. For example, R 1 3 means rotate the 1-st wheel 3 times clockwise.
Print all the wheels, the instruction is P.
輸入描述:
First line contains one integer 𝑛 ( 4 ≤ 𝑛 ≤ 50), indicates the size of the wheels.
Then followed the wheels.
After that, one line contains one integer 𝑚 ( 1 ≤ 𝑚 ≤ 100), indicates the number ofoperations.
Then followed 𝑚 lines, one line one instruction.
it is guaranteed that at least there is one P instruction and the wheels only contain lowercase letters.
輸出描述:
If the instruction is P, then print all the wheels.
題意
給一個n*n的矩陣，從外到內每一圈編號1~n/2，R就是向右轉，L就是向左轉，將第x圈旋轉y次，每次九十度，輸入P列印當前矩陣
思路
模擬即可
代碼
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int MAXN = 2e5 + 5;
int t, n, m, k, flag = 1;
char mp[55][55];
int main(void) {
IO;
cin >> n;
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> mp[i][j];
cin >> t;
while(t--) {
char op;
cin >> op;
if(op != 'P') {
int x, y;
cin >> x >> y;
char now[1000];
int num = 0, nowx = x, nowy = x;
while(nowy + nowx <= n + 1) {
now[++num] = mp[nowx][nowy];
nowy++;
}
nowy--;
while(nowx < nowy) {
nowx++;
now[++num] = mp[nowx][nowy];
}
while(nowy + nowx > n + 1) {
nowy--;
now[++num] = mp[nowx][nowy];
}
while(nowx > nowy + 1) {
nowx--;
now[++num] = mp[nowx][nowy];
}
nowx--;
y = y % 4;
if(op == 'L') {
k = (y * (n - x * 2 + 1)) % num + 1;
}else {
k = (-y * (n - x * 2 + 1)) % num + num + 1;
}
while(nowy + nowx <= n + 1) {
mp[nowx][nowy] = now[k];
nowy++;
k = k % num + 1;
}
nowy--;
while(nowx < nowy) {
nowx++;
mp[nowx][nowy] = now[k];
k = k % num + 1;
}
while(nowy + nowx > n + 1) {
nowy--;
mp[nowx][nowy] = now[k];
k = k % num + 1;
}
while(nowx > nowy) {
nowx--;
mp[nowx][nowy] = now[k];
k = k % num + 1;
}
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j <= n; j++)
// cout << mp[i][j];
// cout << '\n';
// }
// for(int i = 1; i <= num; i++) cout << now[i];cout << '\n';
}else {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++)
cout << mp[i][j];
cout << '\n';
}
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/201608.html
標籤：其他