T1 遠征 題目 【題目描述】 寒楓將軍將要帶領他的部隊去聖雪山消滅那裡的冰龍。部隊分成了若幹個小隊，屬於同一個小隊的人兵種相同。 寒楓將軍有著傑出的指揮能力，在戰鬥的時候，寒楓將軍能夠讓所有相同兵種的人互相配合，使t個相同兵種的人發揮出t2的戰鬥力； 寒楓將軍還能讓不同兵種的人互相配合，使整個部隊 ...
T1 遠征
題目
【題目描述】
寒楓將軍將要帶領他的部隊去聖雪山消滅那裡的冰龍。部隊分成了若幹個小隊，屬於同一個小隊的人兵種相同。
寒楓將軍有著傑出的指揮能力，在戰鬥的時候，寒楓將軍能夠讓所有相同兵種的人互相配合，使t個相同兵種的人發揮出t2的戰鬥力；
寒楓將軍還能讓不同兵種的人互相配合，使整個部隊的戰鬥力是所有兵種戰鬥力的和。
例如，部隊中有3個小隊，分別是5個人的步兵小隊，3個人的步兵小隊，3個人的騎兵小隊。那麼步兵戰鬥力為64，騎兵戰鬥力為9，部隊總戰鬥力為73。
寒楓將軍需要知道他的部隊的戰鬥力是多少。
【輸入格式】
第一行一個整數n，表示小隊數。接下來n行，第i行有兩個整數ai、bi，表示這個小隊有ai個人，兵種為bi。
【輸出格式】
一行一個整數，部隊的戰鬥力。
【輸入樣例】
3
5 1
3 1
3 2
【輸出樣例】
73
【數據規模】
10%的數據，n=1
30%的數據，n≤1000
另有20%的數據，ai=1
另有30%的數據，bi≤1000
100%的數據，1≤n≤100000，1≤ai≤10000，1≤bi≤1,000,000,000
解析
T1依舊水，蒟蒻仍AC。
將a與b用結構體存儲，再按b從小到大排序，如果i的b等於i-1的b，那就是相同兵種，令t累加上a，
如果不相等，那就是不同兵種，統計一下答案並把t清零，最後不要忘了再統計一次答案。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } struct rec{ int a,b; }ra[100100]; int n; long long ans,t; bool cmp(rec x,rec y) { return x.b<y.b; } int main() { //freopen("expedition.in","r",stdin); //freopen("expedition.out","w",stdout); n=read(); for(int i=1;i<=n;i++) ra[i].a=read(),ra[i].b=read(); sort(ra+1,ra+n+1,cmp); t=ra[1].a; for(int i=2;i<=n;i++) { if(ra[i].b==ra[i-1].b) t+=ra[i].a; else { ans+=t*t; t=ra[i].a; } } ans+=t*t; cout<<ans; return 0; //fclose(stdin); //fclose(stdout); }View Code
T2 密碼
題目
【題目描述】
假髮通過了不懈的努力，得到了將軍家門鎖的密碼（一串小寫英文字母）。但是假髮被十四和猩猩他們盯上了，所以假髮需要把密碼傳遞出去。
因為假髮不想十四他們發現幾松門前貼的小紙條就是將軍家的密碼，所以他加密了密碼（新八：聽起來有點詭異）。加密方法如下：隨機地，在密碼中任意位置插入隨機長度的小寫字元串。
不過，假髮相信銀桑和他那麼多年小學同學，一定能猜中密碼是什麼的（新八：銀桑什麼時候成攮夷志士了！！！）。
可是，寫完了小紙條之後，假髮覺得有點長，就想截去頭和尾各一段（可以為空），讓剩下的中間那一段依然包含真～密碼。想著想著，假髮就想知道有多少種可行方案。
結果在沉迷於稿紙之際，假髮被投進了獄門島（新八：……）。於是，就由你計算了。
【輸入格式】
兩行非空字元串，純小寫英文字母，第一行是加密後的密碼，第二行是原密碼。
第一行長度不超過300000，第二行不超過200。
【輸出格式】
一行，有多少種方案。註意：不剪也是一種方案。
【輸入樣例】
abcabcabc
cba
【輸出樣例】
9
【數據規模】
30%的數據滿足第一行長度不超過1000。
100%的數據滿足第一行長度不超過300000，方案總數不超過10^18。
第二行長度小於213
解析
感謝機房大佬們的教學！
我們設f[i][j](初值為-1)表示加密後密碼的第i位與原密碼的第j位匹配時，加密後密碼與原密碼匹配的第0位數在加密後密碼的位上的左邊共有多少位(從第0位開始)，
很繞對不對(本蒟蒻也看不懂自己在寫什麼)，舉個例子，abcabcabc與cba這個樣例，
f[2][0]=2(加密後密碼第2位與原密碼第0位都是c，匹配，而在原密碼第0位c對應的加密後密碼第2位的前面共有2位)，還是不懂？再多看幾個例子，
f[3][1]=2(加密後密碼第3位是a，而原密碼第1位為b，不匹配，所以還是2)，
f[4][1]=2(加密後密碼第4位與原密碼第1位都是b，匹配)，
f[6][2]=2(加密後密碼第6位與原密碼第2位都是a，匹配，而在原密碼第0位c對應的加密後密碼的第2位的前面共有2位)。如果還不懂的話多看幾遍、多試幾遍。
然後狀態轉移即可，最後答案是所有f[i][原密碼長度-1]+1的和(i從加密後密碼長度-1枚舉到原密碼長度-1)。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int f[300100][220]; string s1,s2; long long ans; int main() { //freopen("substring.in","r",stdin); //freopen("substring.out","w",stdout); memset(f,-1,sizeof(f)); cin>>s1>>s2; for(int i=0;i<s1.size();i++) for(int j=0;j<s2.size();j++) { if(j==0) { if(s1[i]==s2[j]) f[i][0]=i; if(s1[i]!=s2[j]&&i>=1) f[i][0]=f[i-1][0]; } else { if(s1[i]==s2[j]&&i>=1) f[i][j]=f[i-1][j-1]; if(s1[i]!=s2[j]&&i>=1) f[i][j]=f[i-1][j]; } } for(int i=s1.size()-1;i>=s2.size()-1;i--) ans+=f[i][s2.size()-1]+1; cout<<ans; return 0; //fclose(stdin); //fclose(stdout); }View Code
T3 獨立集
題目
【題目描述】
有一天，一個名叫順旺基的程式員從石頭裡誕生了。又有一天，他學會了冒泡排序和獨立集。在一個圖裡，獨立集就是一個點集，滿足任意兩個點之間沒有邊。
於是他就想把這兩個東西結合在一起。眾所周知，獨立集是需要一個圖的。那麼順旺基同學創造了一個演算法，從冒泡排序中產生一個無向圖。
這個演算法不標準的偽代碼如下：
|
Pascal版本 |
C/C++版本 |
|
procedure bubblesortgraph(n, a[]) ： /*輸入：點數n，1到n的全排列a。 輸出：一個點數為n的無向圖G。*/ 創建一個有n個點，0條邊的無向圖G。 repeat swapped = false for i 從 1 到 n-1 ： if a[i] > a[i + 1] ： 在G中連接點a[i]和點a[i + 1] 交換a[i]和a[i + 1] swapped = true until not swapped 輸出圖G。 //結束。 |
void bubblesortgraph(n,a[]) //輸入：點數n，1到n的全排列a //輸出：一個點數為n的無向圖G { 創建一個有n個點，0條邊的無向圖G。 do{ swapped=false for i 從1 到n-1 if(a[i]>a[i+1]) { 在G中連接點a[i]和點a[i+1] 交換a[i]和a[i+1] swapped =true } }while(swapped); 輸出圖G。 } //結束。 |
那麼我們要算出這個無向圖G最大獨立集的大小。但是事情不止於此。順旺基同學有時候心情會不爽，這個時候他就會要求你再回答多一個問題：
最大獨立集可能不是唯一的，但有些點是一定要選的，問哪些點一定會在最大獨立集里。今天恰好他不爽，被他問到的同學就求助於你了。
【輸入格式】
輸入包含兩行，第一行為N，第二行為1到N的一個全排列。
【輸出格式】
輸出包含兩行，第一行輸出最大獨立集的大小，第二行從小到大輸出一定在最大獨立集的點的編號。
【輸入樣例】
3
3 1 2
【輸出樣例】
2
2 3
【數據規模】
30%的數據滿足 N<=16
60%的數據滿足 N<=1,000
100%的數據滿足 N<=100,000
解析
這題有點坑，剛看的時候想都沒想，直接打了模擬，結果GG，後來想想才發現是最長上升子序列。
仔細看冒泡排序的代碼，不難得出，只有兩數為逆序對時才有邊，反之沒邊，即上升子序列，而第一問顯然就是最長上升子序列；
而第二問就可以轉化為必定會在最長上升子序列的元素有哪些，我們可以正著求一遍最長上升子序列，再反向求一遍，
兩個最長上升子序列都有的元素即為答案。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } const int N=100100; int n,a[N],k,maxn,f1[N],f2[N],d[N],b[N]; int main() { //freopen("bubble.in","r",stdin); //freopen("bubble.out","w",stdout); n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) { k=lower_bound(d,d+maxn+1,a[i])-d; maxn=max(maxn,k); f1[i]=k; d[k]=a[i]; } d[0]=0xcfcfcfcf,maxn=0; for(int i=n;i>=1;i--) { k=lower_bound(d,d+maxn+1,-a[i])-d; maxn=max(maxn,k); f2[i]=k; d[k]=-a[i]; } cout<<maxn<<endl; for(int i=1;i<=n;i++) if(f1[i]+f2[i]-1==maxn) b[f1[i]]++; for(int i=1;i<=n;i++) if(f1[i]+f2[i]-1==maxn&&b[f1[i]]==1) cout<<i<<" "; return 0; //fclose(stdin); //fclose(stdout); }View Code
T4 選修課
題目
【題目描述】
溫州中學開放了許多選修課，每節選修課都屬於一種種類。精力旺盛的黃小龍同學想要儘可能多的參加選修課，但是他只能選擇M種種類的課程。
當然，對於他所選的種類，他會去上所有該種類的課。現在他想知道他最多能上幾節選修課，以及上最多選修課的方案數。
兩種方案被認為不同當且僅當一種方案中存在另一種方案所沒有的選修課。
【輸入格式】
第一行一個只由小寫字母組成，長度為N的字元串。表示有N節選修課，以及每節選修課的種類。
【輸出格式】
輸出一行，兩個用空格隔開的正整數，分別表示最多選修課數量和方案數。
【輸入樣例】
abcde
1
【輸出樣例】
1 5
【數據規模】
對於30%的數據，M==1;
對於另外30%的數據，每種種類的選修課最多只有一節;
對於100%的數據1<=M<=26、1<=N<=100000;
解析
驚！某蒟蒻AC了T4！
今天的T4居然挺簡單，有點不可思議。
因為字母總共只有26個，所以我們可以開一個a數組存儲每個字母出現的次數，
再用貪心思想，把a數組從大到小排序，取前m個數累加就是第一問；
第二問得分兩種情況，如果m≥所有字母種類，直接輸出1即可；
如果m＜所有字母種類的話，其實就是在求組合數，舉個例子，
aaaabbbbcccdddeeffz(這些是字母出現次數，別問我為什麼這麼規則，反正只要記錄出現次數就可以了(其實是懶))，
很顯然，a4次，b4次，c3次，d3次，e2次，f2次，z1次。
如果m為1，在a和b兩個中選一個即可，方案數為2；
如果m為2，很顯然，取a和b這兩個出現次數最多的即可，方案數為1,；
如果m為3呢？很顯然，a和b這兩個字母肯定必選，那麼剩下的一個肯定得選c或d，方案數為2，是不是和m為1時類似？
如果m為4，選a，b，c，d，方案數為1；
如果m為5，a，b，c，d，這四個數肯定還是要選，那麼剩下的一個就是e或f，方案數為2；
剩下的以此類推，本蒟蒻便不分別說了。
仔細分析上面的例子，不難發現，在m增加的過程中，我們每次都會選在m較小時所選的數以及剩下的數中最大的，
如果當前有多個最大的，那麼就是在求最大的數的種類數中選擇x個數（x為m剩下的未選擇的次數），這不就是組合數嗎？
思路想通了，代碼也就不難了，具體在操作上面的步驟時，用遞歸就可以了。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } int m,a[27],temp,ans,sum,f[27][27]; string s; bool cmp(int x,int y) { return x>y; } void work(int last,int x) { int num=0; for(int i=last+1;i<=26;i++) { if(a[i]==0) break; if(a[i]==a[last+1]) num++; else break; } if(num>=x)//從num個數中選x個數 { for(int i=1;i<=num;i++) for(int j=0;j<=i;j++) f[i][j]=f[i-1][j]+f[i-1][j-1]; cout<<f[num][x]; } else work(last+num,x-num); } int main() { //freopen("course.in","r",stdin); //freopen("course.out","w",stdout); cin>>s; m=read(); for(int i=0;i<s.size();i++) a[s[i]-'a'+1]++; sort(a+1,a+27,cmp); f[0][0]=1; for(int i=1;i<=26;i++) { if(a[i]==0) break; else sum++; if(temp<m) { ans+=a[i]; temp++; } } cout<<ans<<" "; if(m>=sum) cout<<"1"; else work(0,m); return 0; //fclose(stdin); //fclose(stdout); }View Code
