當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

Codeforces Round #597 (Div. 2) - BenFromHRBUST

發布時間：2024/1/1 编程问答 32 豆豆

生活随笔收集整理的這篇文章主要介紹了 Codeforces Round #597 (Div. 2) - BenFromHRBUST 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

Codeforces Round #597 (Div. 2)

-----比賽傳送門-----

A - Good ol’ Numbers Coloring

Problem Description

Consider the set of all nonnegative integers: 0,1,2,…. Given two integers a and b (1≤a,b≤104). We paint all the numbers in increasing number first we paint 0, then we paint 1, then 2 and so on.
Each number is painted white or black. We paint a number i according to the following rules:
if i=0, it is colored white;
if i≥a and i?a is colored white, i is also colored white;
if i≥b and i?b is colored white, i is also colored white;
if i is still not colored white, it is colored black.
In this way, each nonnegative integer gets one of two colors.
For example, if a=3, b=5, then the colors of the numbers (in the order from 0) are: white (0), black (1), black (2), white (3), black (4), white (5), white (6), black (7), white (8), white (9), …
Note that:
It is possible that there are infinitely many nonnegative integers colored black. For example, if a=10 and b=10, then only 0,10,20,30 and any other nonnegative integers that end in 0 when written in base 10 are white. The other integers are colored black.
It is also possible that there are only finitely many nonnegative integers colored black. For example, when a=1 and b=10, then there is no nonnegative integer colored black at all.
Your task is to determine whether or not the number of nonnegative integers colored black is infinite.
If there are infinitely many nonnegative integers colored black, simply print a line containing “Infinite” (without the quotes). Otherwise, print “Finite” (without the quotes).

Input

The first line of input contains a single integer t (1≤t≤100) — the number of test cases in the input. Then t lines follow, each line contains two space-separated integers a and b (1≤a,b≤10⁴).
##Output
For each test case, print one line containing either “Infinite” or “Finite” (without the quotes). Output is case-insensitive (i.e. “infinite”, “inFiNite” or “finiTE” are all valid answers).

Example

input
4
10 10
1 10
6 9
7 3
output
Infinite
Finite
Infinite
Finite

Code

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--)const int N = 1e5+5; const ll MOD=1e9+7;int main() {int n;cin >> n;while(n--){ll a, b;cin >> a >> b;if(__gcd(a, b) == 1)cout << "Finite" << endl;else cout << "Infinite" << endl;}return 0; }

B - Restricted RPS

Problem Description

Let n be a positive integer. Let a,b,c be nonnegative integers such that a+b+c=n.
Alice and Bob are gonna play rock-paper-scissors n times. Alice knows the sequences of hands that Bob will play. However, Alice has to play rock a times, paper b times, and scissors c times.
Alice wins if she beats Bob in at least ?n/2? (n/2 rounded up to the nearest integer) hands, otherwise Alice loses.
Note that in rock-paper-scissors:
rock beats scissors;
paper beats rock;
scissors beat paper.
The task is, given the sequence of hands that Bob will play, and the numbers a,b,c, determine whether or not Alice can win. And if so, find any possible sequence of hands that Alice can use to win.
If there are multiple answers, print any of them.

Input

The first line contains a single integer t (1≤t≤100) — the number of test cases.
Then, t testcases follow, each consisting of three lines:
The first line contains a single integer n (1≤n≤100).
The second line contains three integers, a,b,c (0≤a,b,c≤n). It is guaranteed that a+b+c=n.
The third line contains a string s of length n. s is made up of only ‘R’, ‘P’, and ‘S’. The i-th character is ‘R’ if for his i-th Bob plays rock, ‘P’ if paper, and ‘S’ if scissors.

Output

For each testcase:
If Alice cannot win, print “NO” (without the quotes).
Otherwise, print “YES” (without the quotes). Also, print a string t of length n made up of only ‘R’, ‘P’, and ‘S’ — a sequence of hands that Alice can use to win. t must contain exactly a 'R’s, b 'P’s, and c 'S’s.
If there are multiple answers, print any of them.
The “YES” / “NO” part of the output is case-insensitive (i.e. “yEs”, “no” or “YEs” are all valid answers). Note that ‘R’, ‘P’ and ‘S’ are case-sensitive.

Example

input
2
3
1 1 1
RPS
3
3 0 0
RPS
output
YES
PSR
NO

Note

In the first testcase, in the first hand, Alice plays paper and Bob plays rock, so Alice beats Bob. In the second hand, Alice plays scissors and Bob plays paper, so Alice beats Bob. In the third hand, Alice plays rock and Bob plays scissors, so Alice beats Bob. Alice beat Bob 3 times, and 3≥?3/2?=2, so Alice wins.
In the second testcase, the only sequence of hands that Alice can play is “RRR”. Alice beats Bob only in the last hand, so Alice can’t win. 1<?3/2?=2.

Code

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--)const int N = 105; const ll MOD = 1e9+7;char str[N]; char ans[N]; int vis[N];int main() {int T;cin >> T;while(T--){memset(vis,0,sizeof(vis));int n;cin >> n;int a, b, c;cin >> a >> b >> c;scanf("%s",str+1);int win=0;rep(i,1,n){if(str[i]=='R'){if(b>0){b--;ans[i]='P';vis[i]=1;win++;}}else if(str[i]=='P'){if(c>0){c--;ans[i]='S';vis[i]=1;win++;}}else if(str[i]=='S'){if(a>0){a--;ans[i]='R';vis[i]=1;win++;}}}rep(i,1,n){if(vis[i]==1)continue;if(str[i]=='R'){if(a>0){a--;ans[i]='R';vis[i]=1;}}else if(str[i]=='P'){if(b>0){b--;ans[i]='P';vis[i]=1;}}else if(str[i]=='S'){if(c>0){c--;ans[i]='S';vis[i]=1;}}}rep(i,1,n){if(vis[i]==1)continue;if(str[i]=='R'){if(c>0){c--;ans[i]='S';vis[i]=1;}}else if(str[i]=='P'){if(a>0){a--;ans[i]='R';vis[i]=1;}}else if(str[i]=='S'){if(b>0){b--;ans[i]='P';vis[i]=1;}}}ans[n+1]='\0'; // cout<<"DEBUG: "<<sum<<endl;if(!(win>=(n+1)/2))cout << "NO" <<endl;else{cout << "YES" << endl;printf("%s\n",ans+1);}}return 0; }

C - Constanze’s Machine

Problem Description

Constanze is the smartest girl in her village but she has bad eyesight.
One day, she was able to invent an incredible machine! When you pronounce letters, the machine will inscribe them onto a piece of paper. For example, if you pronounce ‘c’, ‘o’, ‘d’, and ‘e’ in that order, then the machine will inscribe “code” onto the paper. Thanks to this machine, she can finally write messages without using her glasses.
However, her dumb friend Akko decided to play a prank on her. Akko tinkered with the machine so that if you pronounce ‘w’, it will inscribe “uu” instead of “w”, and if you pronounce ‘m’, it will inscribe “nn” instead of “m”! Since Constanze had bad eyesight, she was not able to realize what Akko did.
The rest of the letters behave the same as before: if you pronounce any letter besides ‘w’ and ‘m’, the machine will just inscribe it onto a piece of paper.
The next day, I received a letter in my mailbox. I can’t understand it so I think it’s either just some gibberish from Akko, or Constanze made it using her machine. But since I know what Akko did, I can just list down all possible strings that Constanze’s machine would have turned into the message I got and see if anything makes sense.
But I need to know how much paper I will need, and that’s why I’m asking you for help. Tell me the number of strings that Constanze’s machine would’ve turned into the message I got.
But since this number can be quite large, tell me instead its remainder when divided by 109+7.
If there are no strings that Constanze’s machine would’ve turned into the message I got, then print 0.

Input

Input consists of a single line containing a string s (1≤|s|≤105) — the received message. s contains only lowercase Latin letters.

Output

Print a single integer — the number of strings that Constanze’s machine would’ve turned into the message s, modulo 109+7.

Examples

input
ouuokarinn
output
4

input
banana
output
1

input
nnn
output
3

input
amanda
output
0

Note

For the first example, the candidate strings are the following: “ouuokarinn”, “ouuokarim”, “owokarim”, and “owokarinn”.
For the second example, there is only one: “banana”.
For the third example, the candidate strings are the following: “nm”, “mn” and “nnn”.
For the last example, there are no candidate strings that the machine can turn into “amanda”, since the machine won’t inscribe ‘m’.

題意

有一個字符串，里面的w和m均被換成uu和nn。
給定一個被換過的字符串，輸出原串可能的種類數。

思路

找到連續的u或者n，假設有num個，那么這num個字母能構成的種類數為C(num,0)+C(num-1,1)+C(num-2,2)+……+C(num/2,num/2)[解釋：每多一個w或者m就要少一個u或者n，因為兩個u或者n才能構成一個w或者m]，對于每一段連續的num的種類數累乘即可。
后來跟隊友討論的時候才知道，C(num,0)+C(num-1,1)+C(num-2,2)+……+C(num/2,num/2)的答案就是斐波那契的第num項，預處理斐波那契數列即可O(1)知道這個答案。

坑點

計算連續的u或者n的個數的時候要仔細。

Code

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--)const int N = 1e5+5; const ll MOD = 1e9+7;char str[N];const int maxn=1e5+5;int f[maxn],nf[maxn];int pow_(int x,int y) {int ret=1;while (y){if (y&1)ret=1ll*ret*x%MOD;x=1ll*x*x%MOD;y>>=1;}return ret; }void init() {f[0]=nf[0]=1;for (int i=1; i<maxn; i++)f[i]=1ll*f[i-1]*i%MOD;nf[maxn-1]=pow_(f[maxn-1],MOD-2);for (int i=maxn-1; i; i--)nf[i-1]=1ll*nf[i]*i%MOD; }int C(int x,int y)///x is large {return 1ll*f[x]*nf[y]%MOD*nf[x-y]%MOD; }int main() {init();scanf("%s",str+1);int len=strlen(str+1);int flag=1;ll ans=1;int sum=0;int op=-1;rep(i,1,len+1){if(str[i]=='w'||str[i]=='m'){cout<<0<<endl;return 0;}if(str[i]=='n'){if(op==0||op==-1){sum++;}else if(op==1){ll tol=0;rep(i,0,sum/2){tol=(tol+C(sum-i,i))%MOD;}ans=(ans*tol)%MOD;sum=1;}op=0;}else if(str[i]=='u'){if(op==1||op==-1){sum++;}else if(op==0){ll tol=0;rep(i,0,sum/2){tol=(tol+C(sum-i,i))%MOD;}ans=(ans*tol)%MOD;sum=1;}op=1;}else{op=-1;ll tol=0;rep(i,0,sum/2){tol=(tol+C(sum-i,i))%MOD;}ans=(ans*tol)%MOD;sum=0;}}cout<<ans<<endl;return 0; }

D

E - Hyakugoku and Ladders

Problem Description

Hyakugoku has just retired from being the resident deity of the South Black Snail Temple in order to pursue her dream of becoming a cartoonist. She spent six months in that temple just playing “Cat’s Cradle” so now she wants to try a different game — “Snakes and Ladders”. Unfortunately, she already killed all the snakes, so there are only ladders left now.
The game is played on a 10×10 board as follows:
At the beginning of the game, the player is at the bottom left square.
The objective of the game is for the player to reach the Goal (the top left square) by following the path and climbing vertical ladders. Once the player reaches the Goal, the game ends.
The path is as follows: if a square is not the end of its row, it leads to the square next to it along the direction of its row; if a square is the end of its row, it leads to the square above it. The direction of a row is determined as follows: the direction of the bottom row is to the right; the direction of any other row is opposite the direction of the row below it. See Notes section for visualization of path.
During each turn, the player rolls a standard six-sided dice. Suppose that the number shown on the dice is r. If the Goal is less than r squares away on the path, the player doesn’t move (but the turn is performed). Otherwise, the player advances exactly r squares along the path and then stops. If the player stops on a square with the bottom of a ladder, the player chooses whether or not to climb up that ladder. If she chooses not to climb, then she stays in that square for the beginning of the next turn.
Some squares have a ladder in them. Ladders are only placed vertically — each one leads to the same square of some of the upper rows. In order for the player to climb up a ladder, after rolling the dice, she must stop at the square containing the bottom of the ladder. After using the ladder, the player will end up in the square containing the top of the ladder. She cannot leave the ladder in the middle of climbing. And if the square containing the top of the ladder also contains the bottom of another ladder, she is not allowed to use that second ladder.
The numbers on the faces of the dice are 1, 2, 3, 4, 5, and 6, with each number having the same probability of being shown.
Please note that:
it is possible for ladders to overlap, but the player cannot switch to the other ladder while in the middle of climbing the first one;
it is possible for ladders to go straight to the top row, but not any higher;
it is possible for two ladders to lead to the same tile;
it is possible for a ladder to lead to a tile that also has a ladder, but the player will not be able to use that second ladder if she uses the first one;
the player can only climb up ladders, not climb down.
Hyakugoku wants to finish the game as soon as possible. Thus, on each turn she chooses whether to climb the ladder or not optimally. Help her to determine the minimum expected number of turns the game will take.

Input

Input will consist of ten lines. The i-th line will contain 10 non-negative integers hi1,hi2,…,hi10. If hij is 0, then the tile at the i-th row and j-th column has no ladder. Otherwise, the ladder at that tile will have a height of hij, i.e. climbing it will lead to the tile hij rows directly above. It is guaranteed that 0≤hij<i. Also, the first number of the first line and the first number of the last line always contain 0, i.e. the Goal and the starting tile never have ladders.

Output

Print only one line containing a single floating-point number — the minimum expected number of turns Hyakugoku can take to finish the game. Your answer will be considered correct if its absolute or relative error does not exceed 10?6.

Examples

input
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
output
33.0476190476

input

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 3 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 4 0 0 0
0 0 3 0 0 0 0 0 0 0
0 0 4 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 9
output
20.2591405923

input

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 6 6 6 6 6 6 0 0 0
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
output
15.9047592939

Note

A visualization of the path and the board from example 2 is as follows:

The tile with an ‘S’ is the starting tile and the tile with an ‘E’ is the Goal.
For the first example, there are no ladders.
For the second example, the board looks like the one in the right part of the image (the ladders have been colored for clarity).
It is possible for ladders to overlap, as is the case with the red and yellow ladders and green and blue ladders. It is also possible for ladders to go straight to the top, as is the case with the black and blue ladders. However, it is not possible for ladders to go any higher (outside of the board). It is also possible that two ladders lead to the same tile, as is the case with the red and yellow ladders. Also, notice that the red and yellow ladders lead to the tile with the orange ladder. So if the player chooses to climb either of the red and yellow ladders, they will not be able to climb the orange ladder. Finally, notice that the green ladder passes through the starting tile of the blue ladder. The player cannot transfer from the green ladder to the blue ladder while in the middle of climbing the green ladder.

題意

有一個1010的方格，要求按照蛇形從左下角走到左上角。每次走的步數由1~6的骰子決定。
給定一個1010的輸入，某些點上有一個值，那么這個點上有一個梯子，這個點上的值是梯子可以上的高度。（對于走梯子還有其他一些約束，詳情參見原題）
求需要走的次數的期望。

思路

首先我們從終點開始按照路徑給整個圖編號，左上角的點為1，左下角的點為100。
然后從起點向終點DP，dp[1]=0.
當i>6時，我們可以知道轉移方程為。
當2<=i<=6時，我們考慮dp[2]，有5/6的概率原地不動，1/6的概率從1走到2，所以dp[2]可以表示為
類比dp[3],dp[4]……，我們可以總結出轉移方程

然后我們再考慮出現梯子的情況，假設梯子可以傳送到的點為y，如果y<=6，那么不可能出現這個梯子的終點是另一個梯子的起點的情況，所以，dp[i]=dp[y].
如果y>6，那么就不能直接把dp[y]轉移過來，因為dp[y]可能是某個梯子的起始點，而我們不能連續使用兩個梯子，所以我們應該用最普通的轉移方程
從而避免這個梯子的尾是另一個梯子的頭造成的影響。
將走梯子和不走梯子的兩個dp值取一個最小值即為當前出現梯子的點的dp值。
dp[100]即為題中要求的值。

坑點

需要分類考慮x<=6和x>6的情況。
對圖的編號和梯子所到達的地方的編號不能弄錯。

Code

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--)const int N=12;int mp[N][N]; int lad[N*N]; double dp[N*N+5];int main() {rep(i,1,10){rep(j,1,10){scanf("%d",&mp[i][j]);}}for(int i=1; i<=10; i+=2){rep(j,1,10){if(mp[i][j]>=i){mp[i][j]=i-1;}if(mp[i][j]!=0){lad[(i-1)*10+j]=(i-1)*10+j;lad[(i-1)*10+j]-=j+(mp[i][j]-1)*10-1;if(mp[i][j]%2==0){lad[(i-1)*10+j]-=(10-j)+1;}else{lad[(i-1)*10+j]-=j;}}}i++;per(j,10,1){if(mp[i][j]>=i){mp[i][j]=i-1;}if(mp[i][j]!=0){lad[(i-1)*10+(10-j)+1]=((i-1)*10+(10-j)+1);lad[(i-1)*10+(10-j)+1]-=(mp[i][j]-1)*10+(10-j);if(mp[i][j]%2==0){lad[(i-1)*10+(10-j)+1]-=j;}else{lad[(i-1)*10+(10-j)+1]-=(10-j)+1;}}}i--;}dp[1]=0;rep(i,2,6){rep(j,1,i-1){dp[i]+=(dp[i-j]+1.0);}dp[i]=(dp[i]/6.0+(7.0-i)/6.0)/(1-(7.0-i)/6.0);}rep(i,7,100){rep(j,1,6){dp[i]+=dp[i-j]+1.0;}dp[i]/=6.0;if(lad[i]!=0){if(lad[i]<=6){dp[i]=min(dp[i],dp[lad[i]]);}else{double dpp=0;rep(j,1,6){dpp+=dp[lad[i]-j]+1.0;}dpp/=6.0;dp[i]=min(dp[i],dpp);}}}printf("%.10f\n",dp[100]);return 0; }

F - Daniel and Spring Cleaning

Problem Description

While doing some spring cleaning, Daniel found an old calculator that he loves so much. However, it seems like it is broken. When he tries to compute 1+3 using the calculator, he gets 2 instead of 4. But when he tries computing 1+4, he gets the correct answer, 5. Puzzled by this mystery, he opened up his calculator and found the answer to the riddle: the full adders became half adders!
So, when he tries to compute the sum a+b using the calculator, he instead gets the xorsum a⊕b (read the definition by the link: https://en.wikipedia.org/wiki/Exclusive_or).
As he saw earlier, the calculator sometimes gives the correct answer. And so, he wonders, given integers l and r, how many pairs of integers (a,b) satisfy the following conditions:
a+b=a⊕b
l≤a≤r
l≤b≤r
However, Daniel the Barman is going to the bar and will return in two hours. He tells you to solve the problem before he returns, or else you will have to enjoy being blocked.

Input

The first line contains a single integer t (1≤t≤100) — the number of testcases.
Then, t lines follow, each containing two space-separated integers l and r (0≤l≤r≤109).

Output

Print t integers, the i-th integer should be the answer to the i-th testcase.

Example

input
3
1 4
323 323
1 1000000
output
8
0
3439863766

Note

a⊕b denotes the bitwise XOR of a and b.
For the first testcase, the pairs are: (1,2), (1,4), (2,1), (2,4), (3,4), (4,1), (4,2), and (4,3).

題意

給定一個[l, r]區間，問這個區間內有多少對滿足l + r = l ^ r。

思路

l + r = l ^ r等價于l & r =0.
記函數fun(l, r)表示[l, r)內滿足題意的對數。
記函數gun(x, n)表示y屬于[1, n)滿足x + y = x ^ y的y的個數。
當l==0時，fun(0, r)=2*r-1+fun(1, r). 2*r-1表示的是0與[0, r)內所有數都滿足題意，由于0與0計算了兩次，所以減掉一次。再加上fun(1, r)即為fun(0, r)的答案。
當l%2==0&&r%2==0時，fun(l, r)=3*fun(l/2, r/2)。由于l, r是由l/2, r/2左移一位得到，若x & y = 0，其左移一位也滿足條件，因為左移后的xx和yy最后一位為0，所以可以任意選一個數將其最后一位改為1也符合題意。所以答案是3倍的fun(l/2, r/2)。

現在考慮l 或者 r為奇數的情況。
我們考慮把l和r都調整為偶數。
我們可以知道，當l為奇數時，fun(l, r)-f(l+1, r) = 2*(gun(l, r)-gun(l, r))。
當r為奇數時，fun(l, r)-fun(l, r-1)=2*(gun(r-1, r)-gun(r-1, l))
然后再加上調整為偶數之后的fun()函數答案即可。

然后考慮gun(x, n)函數的求解。
我們考慮x和n的二進制位，我們先找到n的最后一個二進制位為1的位置。將這一位變為0，此時該位后面包括該位都為0，如果此時x&n==0，那么說明該位之前的所有位滿足條件，所以該位之后的所有位的貢獻為2^zeros,zeros表示該位后面對于x的0的個數。這樣保證了所有記錄的值不超過n。
然后再找下一個n的二進制位位1的位置。累加貢獻即可。

坑點

想不到，而且細節比較多。

Code

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--)ll gun(ll x,ll n) {ll ans=0;ll cnt=0;for(ll i=1;i<=n;i<<=1){if(n&i){n^=i;if(!(x&n)) ans+=(1<<cnt);}if(!(x&i))cnt++;}return ans; }ll fun(ll l,ll r) {if(l==r)return 0;if(l==0)return 2*r-1+fun(1,r);ll ans=0;if(l&1){ans+=2*(gun(l,r)-gun(l,l));l++;}if(r&1){ans+=2*(gun(r-1,r)-gun(r-1,l));r--;}return ans+3*fun(l/2,r/2); }int main() {int T;scanf("%d",&T);while(T--){ll l,r;scanf("%I64d%I64d",&l,&r);printf("%I64d\n",fun(l,r+1));}return 0; }

總結

以上是生活随笔為你收集整理的Codeforces Round #597 (Div. 2) - BenFromHRBUST的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： Android NFC标签写入网址，感应
下一篇： Wacom数位板在Mac 10.15以上