RC-u1 亞運獎牌榜

題目鏈接：PTA | 程序設計類實驗輔助教學平臺 (pintia.cn)

題目：

2022 年第 19 屆亞運會即將在杭州召開，杭州已經做好準備歡迎全亞洲的觀眾一同參與亞運盛會了！

你正在開發一款跟亞運獎牌計算相關的 App。給定兩個國家的獲獎情況，你的任務是計算這兩個國家/地區的獎牌情況，并確定哪個國家/地區要排在獎牌榜的前面。

輸入格式:

輸入第一行是一個正整數?N?(1≤N≤1000)，表示總共有?N?條獲獎記錄。

接下來的每一行都是形如以下的一條記錄：

Ci?,Pi?

其中?Ci?=0,1，0 表示是第一個國家/地區，1 表示是第二個國家/地區；Pi?=1,2,3，1 表示金牌，2 表示銀牌，3 表示銅牌。

輸出格式:

首先輸出兩行，第一行是第一個國家/地區的金牌、銀牌、銅牌獲得數，用空格隔開；第二行是第二個國家/地區的獎牌獲獎情況，要求與格式同第一個國家/地區。

最后一行，如果是第一個國家/地區排在前面，輸出?The first win!，否則輸出?The second win!。

排在前面的定義是：先比較金牌數，金牌數較大的排在前面；如金牌數相等，比較銀牌數，銀牌數較大的在前面；如金牌銀牌數都相等，則比較銅牌數，銅牌數較大的在前面。

保證數據不存在獎牌數完全相同的情況。

樣例輸入：

15
0 1
0 2
0 3
0 1
0 1
0 2
0 3
1 3
1 3
1 3
1 3
1 2
1 1
1 1
1 1

樣例輸出：

3 2 2
3 1 4
The first win!

分析：這是一道小型模擬題，先讀入兩個國家的金銀銅牌情況，然后按照題意中所描述的那樣進行比較即可，細節見代碼：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
int main()
{int n;cin>>n;int a[2][5]={0};for(int i=1;i<=n;i++){int c,p;cin>>c>>p;a[c][p]++;}for(int i=0;i<=1;i++){for(int j=1;j<=3;j++){printf("%d",a[i][j]);if(j!=3) printf(" ");}puts("");}for(int i=1;i<=3;i++){if(a[0][i]!=a[1][i]){if(a[0][i]>a[1][i])printf("The first win!");elseprintf("The second win!");break;}}return 0;
}

RC-u2 出院

題目鏈接：PTA | 程序設計類實驗輔助教學平臺 (pintia.cn)

題目：

A：最近出了一個飲料營養等級你們知道嗎？例如無糖的飲料是 A 級，可樂是 D 級……

B：那……無糖可樂是什么級別？

C：AD 級吧。

A：出院！

B：出什么院，你也給我進去！

以上是某群中一段有趣的對話。請你按照里面的邏輯，在已知某些飲料的等級的情況下，給飲料定級。定級的方法是：

• 如果是已知等級的飲料，直接輸出等級；
• 對于一個新飲料的名字，你需要將名字拆成兩個已知等級的部分，然后輸出這個級別。例如：Diet是A，Coke是D，那么DietCoke就是AD；
• 如果新飲料無法拆解或者有多種拆解方法，統一定為 D 級。

輸入格式:

輸入第一行是兩個正整數?N,M?(1≤N,M≤100)，表示已知的飲料有?N?種，需要定級的飲料有?M?種。

接下來首先是?N?行，每行是一個字符串和一個字符，表示一種飲料的名字和對應的等級，等級只有?A,B,C,D?四種。

然后是?M?行，每行是一個字符串，表示需要定級的飲料的名字。

所有飲料名字只包含有大小寫字母，長度不超過 30，給定擁有等級的飲料的名字不會重復。

輸出格式:

對于每一個需要定級的飲料，輸出定好的定級。

樣例輸入：

5 6
Diet A
LowSugarTea B
Milk C
Coke D
Water A
DietCoke
Pepsi
Milk
CokeWater
GoodMilk
dietCoke

樣例輸出：

AD
D
C
DA
D
D

分析：這個就是一個字符串處理的問題，我們用map<string,string>來存儲飲料的等級，然后對于每一個新型飲料，我們首先判斷其是否出現過，如果出現過就直接輸出其等級，如果沒有出現過，枚舉每個位置分成兩個字符串，然后分別看兩個字符串的等級是否出現過，如果出現過就記錄下來，如果有多種劃分方式就直接定為D級就可以。最后再將這個新型飲料的級別記錄一下即可，細節見代碼：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1003;
map<string,string> mp;
int main()
{int n,m;cin>>n>>m;string s1,s2;for(int i=1;i<=n;i++){cin>>s1>>s2;mp[s1]=s2;}for(int i=1;i<=m;i++){string s;cin>>s;if(mp.count(s)){cout<<mp[s]<<endl;continue;}string ans="";for(int j=1;j<s.size();j++){s1=s.substr(0,j);s2=s.substr(j,s.size()-j);if(mp.count(s1)&&mp.count(s2)){if(ans.size()){ans="D";break;}else{ans=mp[s1]+mp[s2];}}}if(ans.size()==0) ans="D";cout<<ans<<endl;}return 0;
}

RC-u3 骰子游戲

題目鏈接：PTA | 程序設計類實驗輔助教學平臺 (pintia.cn)

題目：

在某個游戲中有一個骰子游戲。在游戲中，你需要投擲 5 個標準六面骰子（骰子為一個正方體，6 個面上分別有1、2、3、4、5、6中的一個數字，骰子的質量均勻），投出的點數根據組合會獲得一個“獲勝等級”。獲勝等級從高到低如下：

• 五個同點數 - 五個骰子顯示相同的點數
• 四個同點數 - 四個骰子顯示相同的點數
• 葫蘆 - 一對和一個三個同點數（如1、1、3、3、3）
• 六高順子 - 投出的點數為 2、3、4、5、6
• 五高順子 - 投出的點數為 1、2、3、4、5
• 三個同點數 - 三個骰子顯示相同的點數（如1、1、1、2、3）
• 兩對 - 投出的點數中有兩對是相同的（如 1、1、2、2、3）
• 一對 - 投出的點數有一對是相同的（如 1、1、2、3、4）
• 無 - 除去以上的其他情況

給定你已經投出的一次結果，現在假設你可以選擇任意個骰子重投一次，請問怎么樣操作，才能最大化在重骰后獲得更好的獲勝等級的概率呢？

注意：更好的獲勝等級需要嚴格地比當前的獲勝等級更好，例如 1、1、2、2、3 如果重骰后變為 1、1、3、3、4 并不比當前的獲勝等級更好。

輸入格式:

輸入第一行是一個正整數?T?(1≤T≤10)，表示接下來有多少組數據。
每組數據只有一行 5 個數字，表示第一次投出的 5 個骰子的點數。

輸出格式:

對于每組數據輸出三個整數，其中第一個整數為為了獲得最大的概率需要重新骰幾個骰子，后面的兩個整數為重骰骰子后概率的最簡分數，其中第二個整數為分子，第三個整數為分母。如果分子為 0，分母為 1。

如果有多種獲得最大概率的情況，取重骰的骰子數最少的方案。

樣例輸入：

3
1 1 2 2 3
1 1 2 3 4
1 1 1 2 3

樣例輸出：

3 4 9
3 13 18
2 4 9

分析：這個題目由于情況數不多，直接手算各種情況即可。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10;
int a[10],cnt[10],m[10];
int main()
{int n,t;cin>>n;for(int i=0;i<n;i++){memset(cnt,0,sizeof cnt);memset(m,0,sizeof m);for(int j=1;j<=5;j++){cin>>t;cnt[t]++;}for(int j=1;j<=6;j++)m[cnt[j]]++;if(m[5]==1) cout<<0<<" "<<0<<" "<<1;else if(m[4]==1) cout<<1<<" "<<1<<" "<<6;else if(m[3]==1&&m[2]==1) cout<<2<<" "<<11<<" "<<36;else if(m[1]==5&&cnt[1]==0) cout<<4<<" "<<19<<" "<<324;else if(m[1]==5&&cnt[6]==0) cout<<1<<" "<<1<<" "<<6;else if(m[3]==1&&m[1]==2) cout<<2<<" "<<4<<" "<<9;else if(m[2]==2) cout<<3<<" "<<4<<" "<<9;else if(m[2]==1&&m[1]==3) cout<<3<<" "<<13<<" "<<18;else cout<<2<<" "<<17<<" "<<18;if(i!=n-1) puts("");}return 0;
}

RC-u4 相對論大師

題目鏈接：PTA | 程序設計類實驗輔助教學平臺 (pintia.cn)

題目：

在某個直播間里，觀眾常常會發送類似這樣的彈幕：

魚越大，魚刺越大；魚刺越大，肉越少；肉越少，魚越小；所以魚越大，魚越小

這樣通過一連串推導得出一個搞笑的結論的彈幕發送者被稱為“相對論大師”。

現在給定一系列已有的推論，請你從給定的推論中挑選一些，組成一條類似于上面的彈幕，成為一名“相對論大師”。

輸入格式:

輸入第一行是一個正整數?N?(1≤N≤1000），表示總共有多少條推論。

接下來的?N?行，每行有兩對四個元素，形如下：

A 0 B 1
每對元素表示一個論點：第一個是一個長度不大于 5 的、只包含大小寫字母的字符串，稱為論點的核心；第二個數字固定為 0 或者 1，代表論點核心的方向屬性。為簡單理解，你可以將 0 理解為正面方向，1 理解為負面方向。例如：

YuCi 0 Rou 1

就可以理解為魚刺大，肉少?。

于是一行中的兩個論點就形成一條推論，表示第一個核心某個方向的屬性能推出第二個核心的某個方向的屬性，即魚刺越大，肉越少。

輸出格式:

按照彈幕格式輸出一行，例如：

Yu 0 YuCi 0 YuCi 0 Rou 1 Rou 1 Yu 1 = Yu 0 Yu 1

具體格式要求為：在一行中輸出從起始論點到最終論點的所有推論，論點格式與輸入相同，論點間以1個空格分隔。隨后輸出等號（等號前后均有1個空格），最后是相互矛盾的起始和終止論點。

如果有多種方案，選擇使用推論最少的；推論條數相同的輸出任意一種方案均可。

在方案中每條推論僅可使用一次。保證有解，且給定的推論中沒有相同的推論。

樣例輸入：

5
Yu 0 Yuci 0
Rou 1 Yu 1
Yuci 0 Rou 1
Yuci 0 Gutou 0
Gutou 0 Rou 0

樣例輸出：

Yu 0 Yuci 0 Yuci 0 Rou 1 Rou 1 Yu 1 = Yu 0 Yu 1

分析：看一眼數據范圍，只有1000，我們可以暴力來做這道題目，首先對于一個新物種，比如說A，那么我們可以將A 0設置為0節點，A 1設置為1節點，接下來又來一個B，那么就將B 0設置為2節點，B 1設置為3節點，以此類推。這樣我們就可以把所有的關系用節點和邊來表示了，那么現在問題就轉化為求0和1，或者2和3，或者4和5，^……,或2*k和2*k+1這樣的節點之間的距離，求一個最小值，在過程中記錄一下路徑，按照題目中要求的方式進行輸出即可。細節見代碼：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e4+10;
bool vis[N];
vector<int> p[N];
unordered_map<string,int>mp;
unordered_map<int,string>mpp;
int pre[N];
vector<int> bfs(int s,int e)
{pre[s]=-1;pre[e]=-1;queue<int> q;q.push(s);memset(vis,false,sizeof vis);vis[s]=true;while(!q.empty()){int x=q.front();if(x==e) break;q.pop();for(int i=0;i<p[x].size();i++){if(vis[p[x][i]]) continue;vis[p[x][i]]=true;q.push(p[x][i]);pre[p[x][i]]=x;}}vector<int> t;if(pre[e]==-1) return t;while(e!=s){t.push_back(e);e=pre[e];}t.push_back(s);reverse(t.begin(),t.end());return t;
}
int main()
{int n;cin>>n;int idx=0;for(int i=1;i<=n;i++){string s1,s2,id1,id2;cin>>s1>>id1>>s2>>id2;if(!mp.count(s1+" 0")){mpp[idx]=s1+" 0";mp[s1+" 0"]=idx++;mpp[idx]=s1+" 1";mp[s1+" 1"]=idx++;}if(!mp.count(s2+" 0")){mpp[idx]=s2+" 0";mp[s2+" 0"]=idx++;mpp[idx]=s2+" 1";mp[s2+" 1"]=idx++;}s1+=" "+id1;s2+=" "+id2;p[mp[s1]].push_back(mp[s2]);}vector<int> ans(2002);for(int i=0;i<idx;i+=2){vector<int> s1=bfs(i,i+1);vector<int> s2=bfs(i+1,i);if(ans.size()>s1.size()&&s1.size()>0)ans=s1;if(ans.size()>s2.size()&&s2.size()>0)ans=s2;}for(int i=0;i<ans.size()-1;i++)cout<<mpp[ans[i]]<<" "<<mpp[ans[i+1]]<<" ";printf("= ");cout<<mpp[ans[0]]<<" "<<mpp[ans[ans.size()-1]];return 0;
}

RC-u5 相對成功與相對失敗

題目鏈接：PTA | 程序設計類實驗輔助教學平臺 (pintia.cn)

題目：

注意：題面內容表達純屬娛樂，與現實無關！

網上常有人說：看 XX 只能度過一個相對成功/失敗的人生。不妨假設把這個句式套用在“參加睿抗比賽“以及“玩手機游戲”上，那么有：

• “參加睿抗比賽”必然比“不參加睿抗比賽”要成功；
• “玩手機游戲“必然比“不玩手機游戲”要失敗。

現在有?N?個人，已知這些人自己填寫的是否參加了睿抗比賽以及是否玩手機游戲的情況，以及他們實際上的成功程度的排序順序，請問最少有多少人在填寫情況時說謊了？

輸入格式:

輸出第一行為一個正整數?T?(1≤T≤5)，表示數據組數。

每組數據第一行是一個正整數?N?(1≤N≤105)，表示總共的人數。

接下來的?N?行，第?i?行有兩個數字?Ai?,Bi?，表示第?i?位參賽選手是否參加了睿抗比賽以及是否玩手機游戲，0?為沒有參加/沒有玩，1?為參加了/玩了。

最后一行有?N?個數，為一個選手編號?1?到?N?的排列，表示選手成功程度的排序。排序順序從最成功到最失敗。

選手編號從?1?開始。

輸出格式:

對于每組數據，輸出一個整數，表示最少的說謊人數。

樣例輸入：

3
5
1 0
1 0
0 0
0 0
0 1
1 2 3 4 5
5
1 0
1 0
0 0
0 0
0 1
5 4 3 2 1
5
1 0
0 1
0 0
0 1
1 1
4 2 1 3 5

樣例輸出：

0
3
2

分析：首先需要注意的一點：題目中第三個樣例好像有些問題，但是主辦方尚未聲明，故下面做法僅為我理解基礎上的做法。針對第三個樣例題目中給出的解釋是2和4兩個人說謊，那么也就是說1，3，5三個人可以同時說真話，但是3屬于不打比賽不打游戲的人，但是5屬于既打比賽又打游戲的，但是題目中指出打比賽肯定比不打比賽優秀，打游戲肯定比不打游戲更失敗，所以我覺得兩個人之間類似于那種拓撲關系，是無法確定誰更優秀的，顯然矛盾，所以我的觀點就是這兩個人無法同時說真話，所以我給出的答案是3.接下來給出我的做法：

先給出狀態表示：

f[i][0][0]代表以到i個人結束時，最后一個人不參加睿抗比賽也不玩手機游戲的人的情況下最多說真話的人數?
f[i][0][1]代表以到i個人結束時，最后一個人不參加睿抗比賽但玩手機游戲的人的情況下最多說真話的人數?
f[i][1][0]代表以到i個人結束時，最后一個人參加睿抗比賽但不玩手機游戲的人的情況下最多說真話的人數?
f[i][1][1]代表以到i個人結束時，最后一個人參加睿抗比賽也玩手機游戲的人的情況下最多說真話的人數?

至于狀態轉移，首先是有f[i][j][k]=f[i-1][j][k],這是沒有疑問的，接下來就對j和k的四種情況展開討論。

j=0,k=0,這個人既不打睿抗比賽，也不玩手機游戲，則比他成功的人一定不玩手機游戲?

j=0,k=1,這個人不打睿抗比賽，但玩手機游戲，則比他成功的人可能是任何情況

j=1,k=0,這個人打睿抗比賽，但不玩手機游戲，則比他成功的人一定是打睿抗比賽而且不玩手機游戲的

j=1,k=1,這個人打睿抗比賽，玩手機游戲，則比他成功的人一定打睿抗比賽

有了這個狀態轉移方法后代碼就很簡單了，最后只需要求出前n個人四種情況下說真話的人數的最大值mx即可，那么答案就是n-mx。細節見代碼：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10;
int f[N][2][2],a[N],b[N],c[N];
/*
f[i][0][0]代表以到i個人結束時，最后一個人不參加睿抗比賽也不玩手機游戲的人的情況下最多說真話的人數 
f[i][0][1]代表以到i個人結束時，最后一個人不參加睿抗比賽但玩手機游戲的人的情況下最多說真話的人數 
f[i][1][0]代表以到i個人結束時，最后一個人參加睿抗比賽但不玩手機游戲的人的情況下最多說真話的人數 
f[i][1][1]代表以到i個人結束時，最后一個人參加睿抗比賽也玩手機游戲的人的情況下最多說真話的人數 
*/int main()
{int T;cin>>T;while(T--){int n; scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);for(int i=1;i<=n;i++)scanf("%d",&c[i]);for(int i=1;i<=n;i++){f[i][0][0]=f[i-1][0][0];f[i][0][1]=f[i-1][0][1];f[i][1][0]=f[i-1][1][0];f[i][1][1]=f[i-1][1][1];if(a[c[i]]==0&&b[c[i]]==0)//這個人既不打睿抗比賽，也不玩手機游戲，則比他成功的人一定不玩手機游戲 f[i][0][0]=1+max(f[i-1][0][0],f[i-1][1][0]);else if(a[c[i]]==0&&b[c[i]]==1)//這個人不打睿抗比賽，但玩手機游戲，則比他成功的人可能是任何情況 f[i][0][1]=1+max(max(f[i-1][0][0],f[i-1][1][0]),max(f[i-1][0][1],f[i-1][1][1]));else if(a[c[i]]==1&&b[c[i]]==0)//這個人打睿抗比賽，但不玩手機游戲，則比他成功的人一定是打睿抗比賽而且不玩手機游戲的 f[i][1][0]=1+f[i-1][1][0];else//這個人打睿抗比賽，玩手機游戲，則比他成功的人一定打睿抗比賽 f[i][1][1]=1+max(f[i-1][1][0],f[i-1][1][1]);}int mx=max(max(f[n][0][0],f[n][0][1]),max(f[n][1][0],f[n][1][1]));printf("%d\n",n-mx);}return 0;
}