超級密碼
小明今年9歲了，最近迷上了設計密碼！今天，他又設計了一套他認為很復雜的密碼，并且稱之為“超級密碼”. 說實話，這套所謂的“超級密碼”其實并不難：對于一個給定的字符串，你只要提取其中的數字，然后連在一起構成一個整數，再乘以小明的幸運數字513，就是解密后的結果了~比如，字符串“ads2d4,122”，提取后的整數是24122，然后乘以513，就能得到解密后的結果：12374586.注：題目保證解密后的結果在32位無符號整數范圍.
輸入描述
輸入首先包括一個正整數N，表示有N組測試用例. 每組數據占一行，包含一個長度不超過30的字符串.
輸出描述
請根據題目要求輸出解密后的結果，每組數據輸出一行.
樣例輸入
2
ads2d4,122
0023asdf2AA90
樣例輸出
12374586
11947770
思路：提取每一位數字，新答案為舊答案*10+本位數字即可，注意數字范圍。
code：
#include<bits/stdc++.h>
using namespace std;char ch[100];int main()
{int n;cin >> n;while(n--){long long cnt = 0;scanf("%s", ch);int len = strlen(ch);for(int i = 0; i < len; ++i)if(ch[i] >= '0' && ch[i] <= '9')cnt = cnt * 10 + (ch[i] - '0');printf("%lld\n", cnt*513);}return 0;
}考研
題目描述
今天參加比賽的同學，我想以后準備考研的一定有不少.以河北某高校為例， 一共要考4門，分別是：數學（滿分150）、英語（滿分100）、政治（滿分100）、專業課（滿分150）. 不過，你知道考研分數線的這個特點嗎——不僅總分要過分數線，單科也必須過線！ 假設某年度該校研究生錄取的分數線是這樣的：數學和專業課單科分數線是85（含）， 英語和政治單科分數線是55（含），總分分數線是305（含）.并且規定——在單科和總分均過線的前提下， 總分370分（含）以上的是公費生，否則是自費生.現在告訴你一些考生的分數，你能判斷他們的錄取情況嗎？
輸入描述? ?
輸入數據第一行是一個正整數C（C<=100），表示有C組測試用例.
? ?接下來C行，每行4個整數，分別表示一位考生的數學、英語、政治和專業課成績.
輸出描述? ?
輸入數據第一行是一個正整數C（C<=100），表示有C組測試用例
接下來C行，每行4個整數，分別表示一位考生的數學、英語、政治和專業課成績.
樣例輸入
3
100 80 85 120
90 60 65 110
140 50 75 135
樣例輸出
A
B
C思路：直接分類即可。
code：
#include<stdio.h>
int main()
{int n;scanf("%d",&n);while(n--){int a,b,c,d,sum;scanf("%d%d%d%d",&a,&b,&c,&d);sum=a+b+c+d;if((sum>=370)&&(a>=85)&&(b>=55)&&(c>=55)&&(d>=85))printf("A\n");else if((sum>=305)&&(a>=85)&&(b>=55)&&(c>=55)&&(d>=85))printf("B\n");else printf("C\n");}return 0;
}聲之形
題目描述
為了決定去哪個影院看《聲之形》，小S和小T決定拋一次公平的1元硬幣決定最終去哪兒.在以前,他們為了決定去哪個電影院已經拋擲了若干次，其中有a次正面向上和b次反面向上.而且約定了如果正面向上就是小S贏,否則是小T贏.現在告訴你他們以前拋擲的結果，請告訴小S，這次為了看《聲之形》，他如愿去自己想去的電影院的概率是多少.
輸入描述
輸入數據第一行是一個正整數T，保證有T組測試數據，保證.T<=1e3 接下來一共T行，每行有兩個正整數a,b，保證1<=a,b<=2^{60}.保證小S和小T想去的電影院不一致且拋擲結果只會出現正面向上或者反面向上.
輸出描述
輸出一行，表示小S贏的概率，精確到小數點后12位有效數字,你的答案必須和參考答案完全一致才算正確. 每次答案輸出一行.
樣例輸入
1
999 999
樣例輸出
0.500000000000思路：概率肯定為0.5，和之前沒關系。
code：
#include<bits/stdc++.h>
using namespace std;
int main(){int n;int a, b; cin >> n;while(n--){scanf("%d%d", &a, &b);printf("0.500000000000\n");}return 0;
}春游
題目描述
春天來了 大地萬物復蘇 一切都是生機勃勃 門前的這簇綠 和遠處的那一抹紅 都充滿了詩意 是的 春天就是這樣 給人無限的希望 經過了連續多天緊張的訓練，教練決定組織ACM集訓隊的N位同學一起去郊外感受春天的氣息. 為了方便郊游，活動地點提供了 B(≥N) 輛自行車供人租用，現在已知第 i位同學自己攜帶了元，租用第 j 輛自行車的價格為元. 就在大家忙著租車的時候，教練突然提出了一個問題考大家：在允許同學們相互借錢的前提下，你能計算出最多有多少位同學能夠成功租車嗎？
輸入描述
輸入數據第一行是一個正整數T，表示有T組測試數據. 每組數據的第一行包括2個正整數N和B，分別表示學生人數和自行車數量. 每組數據的第二行包含N個正整數Mi，表示N位同學每人攜帶了Mi元. 每組數據的第三行包含B個正整數Cj，表示B輛自行車每輛車的租費. [數據范圍] 1 <= T <= 100 1 <=n<=100, n <= B <= 100 1 <= M[i] <= 1000, 1 <= c[i] <= 1000
輸出描述
請輸出能夠成功租車的最多人數，每組數據輸出一行
樣例輸入
1
4 5
2 1 9 6
3 5 4 7 6樣例輸出
4思路：貪心，把錢集中到一起，優先買小的即可。因為對于當前最便宜的物品，不買肯定虧。
code：
#include<bits/stdc++.h>
using namespace std;
int brr[105];
long long cnt = 0;int main(){int t;int a, b, c;cin >> t;while(t--){cnt = 0;//錢數scanf("%d%d", &a, &b);for(int i = 0; i < a; ++i){scanf("%d", &c);cnt += c;}for(int j = 0; j < b; ++j)scanf("%d", &brr[j]);sort(brr, brr + b);//優先便宜的int tag = 0;for(int i = 0; i < b; ++i){if(cnt < brr[i]) break;//錢不夠cnt -= brr[i];tag++;}if(tag > a)printf("%d\n", a);elseprintf("%d\n", tag);}return 0;
}秋游
題目描述
秋天來了 不必為幾片落葉流淚 也不必為秋風 而輕言感傷 享受秋天吧 享受那秋日陽光 享受菊花黃 享受桂花香 經過了連續多天緊張的第二階段訓練，教練又決定組織ACM集訓隊的N位同學一起去郊游. 為了方便郊游，活動地點提供了 B(≥N) 輛自行車供人租用，現在已知第 i位同學自己攜帶了 Mi 元，租用第 j 輛自行車的價格為 Cj 元. 就在大家忙著租車的時候，丁爸突然提出了一個問題考大家：假如規定每位同學只能用自己攜帶的錢租自行車（即：不允許借別人的錢），并且只允許為自己租車，你能計算出最多有多少位同學能夠成功租車嗎？
輸入描述
輸入數據第一行是一個正整數T，表示有T組測試數據. 每組數據的第一行包括2個正整數N和B，分別表示學生人數和自行車數量. 每組數據的第二行包含N個正整數Mi，表示N位同學每人攜帶了Mi元. 每組數據的第三行包含B個正整數Cj，表示B輛自行車每輛車的租費. [數據范圍] 1 <= T <= 100 1 <=n<=100, n <= B <= 100 1 <= m[i] <= 10001 <= c[i] <= 1000
輸出描述
請輸出能夠成功租車的最多人數，每組數據輸出一行.
樣例輸入
1
4 5
2 1 9 6
3 5 4 7 6樣例輸出
2
思路：和春游的區別就是不能借錢。貪心思路：人和物都升序排序。對于錢最少的人來說，如果能買得起最便宜的物品，就買。買不起，就跳過這個人。
原因如下：
1）這個人買不起最便宜的，肯定也買不起后面的，所以直接放棄這個人。
2）這個人可以買最便宜的，是否讓他買一個更貴的呢？（看起來這樣更賺）
不是的，白扯。
比如它買第n個，那么它后面的n-1個人一定可以買前n-1個車，因為那些人>這個人>那些車
所以老老實實的買最便宜的。
code：
#include<bits/stdc++.h>
using namespace std;
int arr[105];
int brr[105];
long long cnt = 0;
int main(){int t;int a, b, c;cin >> t;while(t--){scanf("%d%d", &a, &b);for(int i = 0; i < a; ++i)scanf("%d", &arr[i]);sort(arr, arr + a);for(int j = 0; j < b; ++j)scanf("%d", &brr[j]);sort(brr, brr + b);int tag = 0;int index1 = 0, index2 = 0;//人，車的下標while(index1 < a && index2 < b){if(arr[index1] >= brr[index2]){index1++;index2++;tag++;} else index1++;}printf("%d\n", tag);}return 0;
}自動簽到機
題目描述
? 今天是報到日，在排了一下午的隊之后，終于輪到了查爾明簽到。
這里使用了一種叫做“自動簽到機”的高科技，在簽到時，選手需要輸入驗證碼來進行確認。這個系統每次會給出T張10*10的黑白圖片，每張的黑色部分形成了“0”、“1”、“8”三個數字中的一種，而且出于人性化設計，它不會讓用戶眼花，不會把數字寫得不規范，也不會在一張圖片中放入兩個以上的數字，更不會去幫用戶治療多年的頸椎病.可是就算這樣，查爾明還是不想去識別，因為他曾經寫過能自動識別驗證碼的程序.不幸的是，當查爾明打開筆記本的時候，卻怎么也找不到那個程序了. 親愛的同學，你能幫助查爾明完成簽到嗎？
輸入描述
輸入文件第一行包含一個正整數T(T≤15)，表示圖片的張數. 接下來T個部分，每個部分是一個10*10的矩陣（不含空格），其中“_”表示白色，“#”表示黑色.
輸出描述
輸出文件包含T行，每行一個整數，其中第i行輸出第i張圖片上的數字.
樣例輸入
1
_____#____
____##____
___#_#____
__#__#____
_____#____
_____#____
_____#____
_____#____
__#######_
__________
樣例輸出
1思路：
判斷0，1，8，觀察可知，1沒有封閉區域，0有一個封閉區域，8有兩個封閉區域。
搜索有幾個區域即可。（不會的看經典例題：八連通）
注意：
數字可能頂住邊界造成假的分割，所以記得在外面加圈。
code：
#include<bits/stdc++.h>
using namespace std;int G[15][15]; //0 ：_ 1： #
int cnt = 0;
int dir[4][2] = {0, -1, 0, 1, 1, 0, -1, 0};struct Node{int x, y;};bool check(int x, int y)
{if(x >= 0 && x < 12 && y >= 0 && y < 12 && G[x][y] == 0) return true;return false;
}void Init(){int c;cnt = 0;memset(G, 0, sizeof G);for(int i = 1; i <= 10; ++i){getchar();for(int j = 1; j <= 10; ++j){scanf("%c", &c);if(c == '#')G[i][j] = 1;}}
}void bfs(int x, int y){cnt++;Node node = {x, y};queue<Node> q;q.push(node);G[x][y] = 1;while(q.size()){Node tmp = q.front();q.pop();int tx = tmp.x;int ty = tmp.y;for(int i = 0; i < 4; ++i){int dx = tx + dir[i][0];int dy = ty + dir[i][1];if(check(dx, dy)){Node dnode = {dx, dy};q.push(dnode);G[dx][dy] = 1;}}}
}int main(){int t;cin >> t;while(t--){Init();for(int i = 0; i < 12; ++i)for(int j = 0; j < 12; ++j)if(G[i][j] == 0)bfs(i, j);if(cnt == 1)printf("1\n");else if(cnt == 2)printf("0\n");else if (cnt == 3)printf("8\n");}return 0;
}奇妙糖果屋
題目描述
奇異王國里有很多奇怪的事物.比如奇怪的人(每個人都擁有一個智慧值)，奇怪的商店… 這不，奇異糖果屋今天開業了，老板在門口拉上了“糖果送送送”的橫幅來吸引顧客. 糖果的具體贈送方案為對于一個智慧值為x的人來說，他所能獲得的糖果數量f(x)滿足如下條件：
- f(0) = 0,
- f(2x) = f(x),
- f(2x+1) = f(2x) + 1, 整天搞怪的小A帶著朋友們聞訊而來，他想出了一個游戲，游戲的規則是這樣的：每個人根據自己的智慧值拿到糖果后互相比較開心值，開心值最大的人即為勝者. 開心值的定義為除了自己以外其他所有人獲得糖果數量的異或值. 但是小A只負責搞怪，目前已知每個人的智力值，聰明的你能否幫助他提前知道誰能獲勝以及這個人的開心值為多少呢？ 每個人按照給定順序從1開始編號.如果有多個人的開心值相等，則編號最小的獲勝.
輸入描述
輸入數據的第一行是一個整數T,表示測試實例的個數，保證T<=100. 每組輸入數據占兩行. 第一行為一個整數n，代表去糖果屋的人數。(1<=n<= 10 5) 第二行為n個整數，代表每個人的智力值 (1<=ai <=10 9 ) 題目保證n>=50000的數據組數不超過10組.
輸出描述
每組數據輸出兩個整數，依次表示獲勝的人的編號以及他所獲得的開心值，中間用空格隔開.每組一行.
樣例輸入
1
2
3 4
樣例輸出
2 2思路：觀察發現，f(x)是x的二進制中1的個數。（很簡單，是奇數就+1，偶數不加，一下就看出來了啊。。。）
算出異或總和tag。異或性質:a ^ b ^ b=a ,對于每個人我們用他的糖果數異或tag即可。
為了要求的順序：自定義排序
code：
#include<bits/stdc++.h>
using namespace std;const int maxn = 100000 + 5;
int arr[maxn];
struct Node{int v;int id;//按規則自定義排序bool operator < (const Node& node) const{if(v != node.v){return v > node.v;} else {return id < node.id;}}
};Node nodes[maxn];int fun(unsigned int x)//1的個數
{int cnt = 0;while(x != 0){if(x & 1)cnt++;x >>= 1;}return cnt;
}int main(){int t;int n, a;cin >> t;while(t--){scanf("%d", &n);for(int i = 0; i < n; ++i){scanf("%d", &a);arr[i] = fun(a);}int tag = arr[0];//算總和for(int i = 1; i < n; ++i){tag ^= arr[i];}for(int i = 0; i < n; ++i){//處理數據arr[i] = tag^arr[i];nodes[i].v = arr[i];nodes[i].id = i+1;}sort(nodes, nodes + n);printf("%d %d\n", nodes[0].id, nodes[0].v);} return 0;
}商品清算
題目描述
查爾明和邁克是好朋友. 每天早晨，查爾明都會去超市購物. 邁克有著敏銳的觀察力，很快就發現了一個有趣的現象：每天查爾明選購的商品的總價格都是奇數！ 商店里共有n種商品，其中第i種商品的價格為v[i].對于每種商品，查爾明每天最多只會購買一件. 每天下午，查爾明都會清算今天花了多少錢，但是他買的東西實在是太多了，他記不清自己到底買了哪些東西，只記得這一天他買了k件商品.于是他只好向口算能力超強的邁克求助，希望他能算出自己最多可能花了多少錢. 邁克的口算只能應付10以內的n和k，所以他把這個任務交給了你.當然，查爾明也有可能記錯k，所以如果不存在任何一種方案，請輸出-1.
輸入描述
輸入文件的第一行包含兩個正整數n(n<=100000)，m(m<=100000)，分別表示商品種數和詢問的個數. 第二行包含n個正整數，依次表示每種商品的價格. 接下來m行每行包含一個整數k，依次表示每個詢問. 對于100%的數據，保證1<=v[i]<=100,000，0<=k<=n.
輸出描述
輸出文件包含m行，每行一個整數，如果有解輸出總價格的最大值，否則輸出-1.保證測試總組數為1組。
樣例輸入
4 3
4 2 1 3
2
3
4樣例輸出
7
9
-1
思路：k個數湊最大奇數，據說有簡單方法，我想的是dp，
思考：
偶數=奇數+奇數，或者偶數+偶數
奇數=奇數+偶數，或者偶數+奇數
設dp[i]為i個數湊最大奇數是多少，思考有哪些情況？
1）i-1個數湊出一個最大的奇數，加上沒選的最大偶數。
2）i-1個數湊出一個最大的偶數，加上沒選的最大奇數。
那很顯然的想到我們要再求一個值，i個數湊最大偶數是多少？
1）i-1個數湊出一個最大的奇數，加上沒選的最大奇數
2）i-1個數湊出一個最大的偶數，加上沒選的最大偶數
很自然的，我們想到把奇數偶數分開存放并且降序排序。并且dp的值不是簡單的一個數，還要記錄做出選擇時，奇數偶數的下標是多少，這樣方便我們確定當前未選中的最大奇數和最大偶數是多少。
code：
解釋一下dp含義：
dp[i][0][0]:i個數湊最大奇數的值
dp[i][0][1]:當前情況的奇數下標
dp[i][0][2]:當前情況的偶數下標
?
dp[i][1][0]:i個數湊最大偶數的值
dp[i][1][1]:當前情況的奇數下標
dp[i][1][2]:當前情況的偶數下標
注意longlong
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
long long arr[100005];
long long brr[100005];
long long dp[100005][2][3];
int main(void)
{int a,b;long long c;scanf("%d%d",&a,&b);int x=0;int y=0;int ans=a;//分別存放并排序while(a--){scanf("%lld",&c);if(c%2==0)brr[y++]=c;else arr[x++]=c;}sort(arr,arr+x,greater<int>());sort(brr,brr+y,greater<int>());//瞎初始化了一波dp[0][0][0]=arr[0];dp[0][0][1]=0;dp[0][0][2]=-1;dp[0][1][0]=brr[0];dp[0][1][1]=-1;dp[0][1][2]=0;if(x==0)dp[0][0][0]=-1;if(y==0)dp[0][1][0]=-1;for(int i=1;i<ans;i++){dp[i][0][0]=-1;dp[i][1][0]=-1;if(dp[i-1][0][0]>=0)//前奇{//奇+偶if(dp[i-1][0][2]<y-1){dp[i][0][0]=dp[i-1][0][0]+brr[dp[i-1][0][2]+1];dp[i][0][1]=dp[i-1][0][1];dp[i][0][2]=dp[i-1][0][2]+1;}//奇+奇if(dp[i-1][0][1]<x-1){dp[i][1][0]=dp[i-1][0][0]+arr[dp[i-1][0][1]+1];dp[i][1][1]=dp[i-1][0][1]+1;dp[i][1][2]=dp[i-1][0][2];}}if(dp[i-1][1][0]>=0 && dp[i-1][1][0]+arr[dp[i-1][1][1]+1]>dp[i][0][0] && dp[i-1][1][1]<x-1){//偶+奇>奇+偶dp[i][0][0]=dp[i-1][1][0]+arr[dp[i-1][1][1]+1];dp[i][0][1]=dp[i-1][1][1]+1;dp[i][0][2]=dp[i-1][1][2];}if(dp[i-1][1][0]>=0 && dp[i-1][1][0]+brr[dp[i-1][1][2]+1]>dp[i][1][0] && dp[i-1][1][2]<y-1){//偶+偶>奇+奇dp[i][1][0]=dp[i-1][1][0]+brr[dp[i-1][1][2]+1];dp[i][1][1]=dp[i-1][1][1];dp[i][1][2]=dp[i-1][1][2]+1;}}for(int i=0;i<b;i++){int kk;scanf("%d",&kk);if(kk>0)printf("%lld\n",dp[kk-1][0][0]);else printf("-1\n");}
}
奇異旅館
題目描述
玩了一天，小A又帶著他的小伙伴們來到了當地的奇異旅館. 這個旅館共有n層，每層分別有ai個床位.由于沒有電梯，大家都希望盡可能住在較低的樓層. 現在小A提出了q個操作，操作分為兩種：
- 從第x層開始向上安置num個小伙伴住宿.
- 詢問前k層一共已經安置的小伙伴數目. 假設一開始每層樓的床位都是未被使用的，且若操作1中x層及以上的房間無法容納所要安置的人，則盡可能多地安置，剩余部分忽略.
輸入描述
輸入數據的第一行是一個整數T,表示測試實例的個數，保證T<=30. 對于每組測試樣例，第一行給出n和q.(1<=n<=100000，1<=q<= 100000) 接下來一行共有n個整數 .(1<=ai<=1e9) 接下來共有q行，每行表示一個操作. 第一種操作的給出形式為：1 x num.(1<=x<=n，1<= num<=1e9) 第二種操作的給出形式為：2 k.(1<= k<=n) 題目保證n>=50000且q>=50000的數據組數不超過5組.
輸出描述
每組樣例中，對于第一種操作，若x層及以上的房間無法容納所要安置的人，輸出“overflow”. 對于第二種操作，輸出所詢問的值. 每個輸出數據占一行，且每組數據后輸出一個空行.
樣例輸入
1
3 5
2 3 5
1 1 4
2 2
1 2 3
2 2
1 3 10
樣例輸出
4
5
overflow暴力肯定gg，但是也沒有多么花里胡哨，就是挺裸的題，具體看代碼。
code：
#include<bits/stdc++.h>
using namespace std;const int maxn = 100000 + 5;
long long crr[maxn];
long long num[maxn];//獲取x最低位1
int lowbit(int x){return x&(-x);
}//單點更新：位置x更新為y
void update(int x, long long y, int n){for(int i = x; i <= n; i+=lowbit(i))crr[i] += y;
}//區間查詢1-x
long long getsum(int x){long long ans = 0;for(int i = x; i > 0; i-=lowbit(i))ans += crr[i];return ans;
}int main(){int T;cin >> T;while(T--){memset(crr, 0, sizeof(crr));int n, m;int a, b;long long c;scanf("%d%d", &n, &m);//輸入每個房間的床數for(int i = 1; i <= n; ++i)scanf("%d", &num[i]);for(int i = 0; i < m; ++i){scanf("%d", &a);if(a == 1){scanf("%d%lld", &b, &c);int j;for(j = b; j <= n; ++j){if(c >= num[j] && num[j] > 0){update(j, num[j], n);c -= num[j];num[j] = 0;}if(c == 0)break;else if (c < num[j]){update(j, c, n);num[j] -= c;c = 0;break;}}if(j == n+1 && c > 0){printf("overflow\n");}}else {scanf("%d", &b);printf("%lld\n", getsum(b));}}cout << endl;}return 0;
}?
?
還有硬核題，本渣不會做了。
--c++，Python版本)
-touch,mkdir,rm,mv,cp,ls,cd,cat)
