Doki Doki Literature ClubTime Limit: 1 Second Memory Limit: 65536 KB
Doki Doki Literature Club! is a visual novel developed by Team Salvato. The protagonist is invited by his childhood friend, Sayori, to join their high school's literature club. The protagonist then meets the other members of the club: Natsuki, Yuri, and the club president Monika. The protagonist starts to participate in the club's activities such as writing and sharing poetry, and grows close to the four girls. What a lovely story!
A very important feature of the game is its poetry writing mechanism. The player is given a list of various words to select from that will make up his poem. Each girl in the Literature Club has different word preferences, and will be very happy if the player's poem is full of her favorite words.
The poem writing mini-game (from wikipedia)
BaoBao is a big fan of the game and likes Sayori the most, so he decides to write a poem to please Sayori. A poem of words is nothing more than a sequence of strings, and the happiness of Sayori after reading the poem is calculated by the formula
where is the happiness and is Sayori's preference to the word .
Given a list of words and Sayori's preference to each word, please help BaoBao select words from the list and finish the poem with these words to maximize the happiness of Sayori.
Please note that each word can be used at most once!
Input
There are multiple test cases. The first line of input contains an integer (about 100), indicating the number of test cases. For each test case:
The first line contains two integers and (), indicating the number of words and the length of the poem.
For the following lines, the -th line contains a string consisting of lowercased English letters () and an integer (), indicating the -th word and Sayori's preference to this word. It's guaranteed that for all .
Output
For each test case output one line containing an integer and strings separated by one space, indicating the maximum possible happiness and the corresponding poem. If there are multiple poems which can achieve the maximum happiness, print the lexicographically smallest one.
Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!
A sequence of strings is lexicographically smaller than another sequence of strings , if there exists a () such that for all and is lexicographically smaller than .
A string is lexicographically smaller than another string , if there exists a () such that for all and , or for all and .
Sample Input
4
10 8
hello 0
world 0
behind 0
far 1
be 2
spring 10
can 15
comes 20
winter 25
if 200
5 5
collegiate 0
programming -5
zhejiang 10
provincial 5
contest -45
3 2
bcda 1
bcd 1
bbbbb 1
3 2
a 1
aa 1
aaa 1
Sample Output
2018 if winter comes can spring be far behind
15 zhejiang provincial collegiate programming contest
3 bbbbb bcd
3 a aa
仅仅是个sort，读懂题意就可以做了
#include
using namespace std;
const int N=1e5+5;
struct T
{
string s;
int va;
}a[105];
int cmp(T a,T b)
{
return a.va>b.va||a.va==b.va&&a.s } int main() { int T; cin>>T; while(T--) { int n,m; cin>>n>>m; for(int i=0;i sort(a,a+n,cmp); long long sum=0; for(int i=0;i sum+=(m-i)*1LL*a[i].va; cout< for(int i=0;i cout<<"\n"; } return 0; } Lucky 7Time Limit: 1 Second Memory Limit: 65536 KB BaoBao has just found a positive integer sequence of length from his left pocket and another positive integer from his right pocket. As number 7 is BaoBao's favorite number, he considers a positive integer lucky if is divisible by 7. He now wants to select an integer from the sequence such that is lucky. Please tell him if it is possible. Input There are multiple test cases. The first line of the input is an integer (about 100), indicating the number of test cases. For each test case: The first line contains two integers and (), indicating the length of the sequence and the positive integer in BaoBao's right pocket. The second line contains positive integers (), indicating the sequence. Output For each test case output one line. If there exists an integer such that and is lucky, output "Yes" (without quotes), otherwise output "No" (without quotes). Sample Input 4 3 7 4 5 6 3 7 4 7 6 5 2 2 5 2 5 2 4 26 100 1 2 4 Sample Output No Yes Yes Yes Hint For the first sample test case, as 4 + 7 = 11, 5 + 7 = 12 and 6 + 7 = 13 are all not divisible by 7, the answer is "No". For the second sample test case, BaoBao can select a 7 from the sequence to get 7 + 7 = 14. As 14 is divisible by 7, the answer is "Yes". For the third sample test case, BaoBao can select a 5 from the sequence to get 5 + 2 = 7. As 7 is divisible by 7, the answer is "Yes". For the fourth sample test case, BaoBao can select a 100 from the sequence to get 100 + 26 = 126. As 126 is divisible by 7, the answer is "Yes". 加上一个数是不是7的倍数，直接做 #include using namespace std; int main() { int T; cin>>T; while(T--) { int n,b; cin>>n>>b; int f=0; for(int i=0,x;i { cin>>x; if((x+b)%7==0)f=1; } cout<<(f?"Yes":"No")<<"\n"; } return 0; } K Mahjong SortingTime Limit: 1 Second Memory Limit: 65536 KB DreamGrid has just found a set of Mahjong with suited tiles and a White Dragon tile in his pocket. Each suited tile has a suit (Character, Bamboo or Dot) and a rank (ranging from 1 to ), and there is exactly one tile of each rank and suit combination. Character tiles whose rank ranges from 1 to 9 Bamboo tiles whose rank ranges from 1 to 9 Dot tiles whose rank ranges from 1 to 9 White Dragon tile As DreamGrid is bored, he decides to play with these tiles. He first selects one of the suited tiles as the "lucky tile", then he picks tiles from the set of tiles and sorts these tiles with the following rules: The "lucky tile", if contained in the tiles, must be placed in the leftmost position. For two tiles and such that neither of them is the "lucky tile", if is a Character tile and is a Bamboo tile, or is a Character tile and is a Dot tile, or is a Bamboo tile and is a Dot tile, or and have the same suit and the rank of is smaller than the rank of , then must be placed to the left of . White Dragon tile is a special tile. If it's contained in the tiles, it's considered as the original (not-lucky) version of the lucky tile during the sorting. For example, consider the following sorted tiles, where "3 Character" is selected as the lucky tile. White Dragon tile, in this case, is considered to be the original not-lucky version of "3 Character" and should be placed between "2 Character" and "4 Character". As DreamGrid is quite forgetful, he immediately forgets what the lucky tile is after the sorting! Given sorted tiles, please tell DreamGrid the number of possible lucky tiles. Input There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case: The first line contains two integers and (, ), indicating the number of sorted tiles and the maximum rank of suited tiles. For the next lines, the -th line describes the -th sorted tile counting from left to right. The line begins with a capital letter (), indicating the suit of the -th tile: If , then an integer () follows, indicating that it's a Character tile with rank ; If , then an integer () follows, indicating that it's a Bamboo tile with rank ; If , then an integer () follows, indicating that it's a Dot tile with rank ; If , then it's a White Drangon tile. It's guaranteed that there exists at least one possible lucky tile, and the sum of in all test cases doesn't exceed . Output For each test case output one line containing one integer, indicating the number of possible lucky tiles. Sample Input 4 3 9 C 2 W C 4 6 9 C 2 C 7 W B 3 B 4 D 2 3 100 C 2 W C 9 3 9 C 1 B 2 D 3 Sample Output 2 4 7 25 Hint For the first sample, "2 Character" and "3 Character" are possible lucky tiles. For the second sample, "8 Character", "9 Character", "1 Bamboo" and "2 Bamboo" are possible lucky tiles. 自己菜做不出来，要把所有的情况都分析到，我太菜了，这个题不想再做了 #include using namespace std; const int N=1e5+5; int a[N],n,m; int main() { int t; scanf("%d",&t); while(t--) { int f=0,ans; scanf("%d%d",&n,&m); a[n+1]=3*m+1; for(int i=1; i<=n; i++) { getchar(); char c=getchar(); if(c!='W') { scanf("%d",&a[i]); if(c=='B')a[i]+=m; if(c=='D')a[i]+=2*m; } else f=i; } if(n==1)ans=3*m; else { if(f==0) if(a[1]>a[2])ans=1; else ans=3*m-n+1; else { if(f==1)ans=a[2]-1; else { if(a[1]>a[2]&&f!=2)ans=1; else ans=a[f+1]-a[f-1]-(f!=2); } } } cout< } return 0; } D Sequence SwappingTime Limit: 1 Second Memory Limit: 65536 KB BaoBao has just found a strange sequence {<, >, <, >, , <, >} of length in his pocket. As you can see, each element <, > in the sequence is an ordered pair, where the first element in the pair is the left parenthesis '(' or the right parenthesis ')', and the second element in the pair is an integer. As BaoBao is bored, he decides to play with the sequence. At the beginning, BaoBao's score is set to 0. Each time BaoBao can select an integer , swap the -th element and the -th element in the sequence, and increase his score by , if and only if , '(' and ')'. BaoBao is allowed to perform the swapping any number of times (including zero times). What's the maximum possible score BaoBao can get? Input There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case: The first line contains an integer (), indicating the length of the sequence. The second line contains a string () consisting of '(' and ')'. The -th character in the string indicates , of which the meaning is described above. The third line contains integers (). Their meanings are described above. It's guaranteed that the sum of of all test cases will not exceed . Output For each test case output one line containing one integer, indicating the maximum possible score BaoBao can get. Sample Input 4 6 )())() 1 3 5 -1 3 2 6 )())() 1 3 5 -100 3 2 3 ()) 1 -1 -1 3 ()) -1 -1 -1 Sample Output 24 21 0 2 Hint For the first sample test case, the optimal strategy is to select in order. For the second sample test case, the optimal strategy is to select in order. 这个dp就是去找(，找到它最右可以到达的位置 然后你可以找一个这个)前一个）,保证他也最优 #include using namespace std; const int N=1005; typedef long long ll; char s[N]; ll v[N],dp[N][N],sum[N],F[N],nxt[N]; int main() { int t; scanf("%d",&t); while(t--) { int n,f=0,tot=1; scanf("%d%s",&n,s+1); for(int i=1; i<=n; i++)scanf("%lld",&v[i]); for(int i=n; i>0; i--)if(s[i]=='(')F[tot++]=i; for(int i=1; i<=n; i++) sum[i]=sum[i-1]+(s[i]==')'?v[i]:0); memset(nxt,0,sizeof(nxt)); for(int i=1; i<=n; i++) if(s[i]==')') { if(f) nxt[f]=i; f=i; } for(int i=1; i<=n; i++) dp[i][0]=-(1LL<<60); ll ans=0; for(int i=1; i { for(int j=F[i]+1; j<=n; j++) if(s[j]==')') dp[i][j]=v[F[i]]*(sum[j]-sum[F[i]])+dp[i-1][j]; for(int j=n; j>=F[i]; j--) if(s[j]==')') dp[i][j]=max(dp[i][nxt[j]],dp[i][j]); for(int j=F[i]-1; j>=1; j--) if(s[j]==')') dp[i][j]=max(dp[i-1][j],dp[i][nxt[j]]); for(int j=1; j<=n; j++) if(s[j]==')')ans=max(ans,dp[i][j]); } printf("%lld\n",ans); } return 0; } 使用滚动数组优化 #include using namespace std; const int N=1005; typedef long long ll; char s[N]; ll v[N],dp[2][N],sum[N],F[N],nxt[N]; int main() { int t; scanf("%d",&t); while(t--) { int n,f=0,tot=1,cur=0; scanf("%d%s",&n,s+1); for(int i=1; i<=n; i++)scanf("%lld",&v[i]); for(int i=n; i>0; i--)if(s[i]=='(')F[tot++]=i; for(int i=1; i<=n; i++) sum[i]=sum[i-1]+(s[i]==')'?v[i]:0); memset(nxt,0,sizeof(nxt)); for(int i=1; i<=n; i++) if(s[i]==')') { if(f) nxt[f]=i; f=i; } for(int i=1; i<=n; i++) dp[1][i]=dp[0][i]=0; dp[0][0]=dp[1][0]=-(1LL<<60); ll ans=0; for(int i=1; i { for(int j=F[i]+1; j<=n; j++) if(s[j]==')') dp[cur][j]=v[F[i]]*(sum[j]-sum[F[i]])+dp[cur^1][j]; for(int j=n; j>=F[i]; j--) if(s[j]==')') dp[cur][j]=max(dp[cur][nxt[j]],dp[cur][j]); for(int j=F[i]-1; j>=1; j--) if(s[j]==')') dp[cur][j]=max(dp[cur^1][j],dp[cur][nxt[j]]); for(int j=1; j<=n; j++) if(s[j]==')')ans=max(ans,dp[cur][j]); cur^=1; } printf("%lld\n",ans); } return 0; Magic 12 MonthsTime Limit: 1 Second Memory Limit: 65536 KB It's New Year's Eve, and it's also the best time of the year to play the card game Magic 12 Months to pray for good luck of the coming year. BaoBao has just found a deck of standard 52 playing cards (without Jokers) in his pocket and decides to play the game. The rules are as follows: Setup Remove the four 'K's from the 52 cards. Shuffle the remaining 48 cards and divide them face down into 12 piles (4 cards per pile) with equal probability. Gameplay Let . Flip the card on the top of the -th pile, check its rank , and discard the card. If is a number, let ; If , let ; If , let ; If , let . If the -th pile is empty, the game ends; Otherwise go back to step 2.2. When the game ends, having all the 4 cards of rank flipped and discarded indicates that the -th month in the coming year is a lucky month. BaoBao is in the middle of the game and has discarded cards. He wants to know the probability that the -th month of the coming year is a lucky month for all when the game ends. Given these cards, please help him calculate the answer. Input There are multiple test cases. The first line of input contains an integer (about 100) -- the number of test cases. For each test case: The first and only line contains an integer () -- the number of flipped cards, followed by the rank of the cards () separated by a space in the order they are flipped. It's guaranteed that the input describes a valid and possible situation of the game. Output For each test case output one line containing 12 numbers separated by a space, where the -th number indicates the probability that the -th month of the coming year is a lucky month. You should output a probability in its simplest fraction form where and are coprime. Specifically, if the probability equals 0, you should output 0; If the probability equals 1, you should output 1. Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect! Sample Input 3 30 9 Q 10 J Q 10 J 10 J J 8 5 7 6 5 7 6 7 6 6 3 A 2 4 A 2 4 2 4 4 0 7 2 A 3 A 4 A A Sample Output 1 2/3 2/5 1 1/2 1 2/3 2/5 2/5 2/3 1 1/2 1 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1/2 1 0 0 0 0 0 0 0 0 0 0 0 想到了和第一堆有关，但是还没推出来 #include using namespace std; #define dbg(x) cout<<#x<<" = "<< (x)<< endl typedef long long ll; ll C(int n,int m) { if(m>n)return 0; ll ans=1; for(int i=n-m+1; i<=n; i++)ans*=i; for(int i=2; i<=m; i++)ans/=i; return ans; } int a[15]; int main() { int t; cin>>t; while(t--) { for(int i=1; i<=12; i++)a[i]=4; int n; cin>>n; string s; for(int i=0,x; i { cin>>s; if(s=="10")x=10; else if(s=="A")x=1; else if(s=="J")x=11; else if(s=="Q")x=12; else x=s[0]-48; a[x]--; } cout<<1; for(int i=2; i<=12; i++) { //dbg(a[i]); if(!a[i])cout<<" 1"; else if(!a[1])cout<<" 0"; else { int m=48-n; ll B=C(m,a[1])*C(m-a[1],a[i]),A=0; for(int j=a[1]; j<=m; j++)A+=C(j-1,a[1]-1)*C(j-a[1],a[i]); ll d=__gcd(A,B); if(!A)cout<<" 0"; else if(A==B)cout<<" 1"; else cout<<" "<
} } cout<<"\n"; } return 0; }