2018第二届河北省大学生程序设计竞赛题解
icebound的賬單
?
題目描述
icebound從小就有記賬的習慣。又到了月末icebound統計資金狀況的時候。icebound每個月除了不停的揮霍以外，有時他會良心發現，勤工儉學，因此會有一些微薄的收入。然而icebound數學不好，需要你來幫助他統計他本月的資金狀況。
你將會得到一份icebound的賬單，一共有 n? 行整數，其中正數表示icebound打工掙來的收入，負數表示icebound消費的支出。數據保證不會出現 0? 。
如果icebound本月總收入大于總支出，請你輸出“icebound is happy.”；如果本月總收入等于總支出，請你輸出“icebound is ok."；如果總收入小于總支出，請你輸出"icebound is sad."。
輸入描述
第一行，有一個正整數nn，代表賬單有nn行。
接下來有nn行，每行一個整數，第i+1i+1行整數a_iai?。
1 \leq n \leq 10001≤n≤1000，\left| a_i \right|\leq 1000∣ai?∣≤1000,?a_i \neq 0ai?≠0
輸出描述
輸出一行。如果icebound本月總收入大于總支出，請你輸出“icebound is happy.”；如果本月總收入等于總支出，請你輸出“icebound is ok."；如果總收入小于總支出，請你輸出"icebound is sad."。
樣例輸入
2 100 -100樣例輸出
icebound is ok.思路：簡單分類不解釋
#include<bits/stdc++.h> using namespace std; long long sum = 0;int main() {int n,k;cin >> n;while(n--){scanf("%d", &k);sum += k;}if(sum > 0)cout << "icebound is happy." << endl;else if (sum < 0)cout << "icebound is sad." << endl;elsecout << "icebound is ok." << endl;return 0; }520
題目描述
“又到了五月了呢”，icebound望著五月的天空，眼角流出了淚痕。那一年，icebound還是一個懵懂的少年。那一年，她還是一個青澀純真的少女。在那一次偶然的相遇之中，他們之間擦出了愛情的火花。他們歡笑著，奔跑著，他們展望著美好的未來，向往著幸福的明天。她像 icebound 心海中的燈塔，像icebound 頭頂上的星辰，即使在海里浮沉，即使在夜里摸爬，心中也不會感到迷茫，感到陰寒。他們努力，奮進，向著六月的那一站前行。可是，美好總是短暫的。那海上的燈塔不再發出溫情的光亮，那天空中的星辰不再綻放出溫柔的色彩。那一站，到達了，icebound 得到了終點，但icebound 永遠失去了她，也失去了他的心。
”侯門一入深似海，從此蕭郎是路人“
今天是2018年5月20日，又是一年的520。這一天，icebound不小心讀到上面的詩，icebound沉思著，回想起與她曾經的快樂時光，icebound留下了nn滴眼淚。icebound的每滴眼淚都帶有太多的傷感之情了，以至于每滴眼淚都會感染到其他的生物，使得許多生物都一起掉下了眼淚。kk通過觀察得知，當icebound流出nn滴眼淚時，所有生物產生的眼淚總數為2^n。現在，kk需要你幫助他寫一個程序，計算當icebound流出nn滴眼淚時，所有生物產生的眼淚總數PP，對?2018052020180520?取模。
輸入描述
一個正整數nn，代表icebound留下眼淚的個數。1 \leq n \leq 2 \times 10^91≤n≤2×109
輸出描述
一個正整數PP，代表所有生物產生的眼淚總數，對?2018052020180520?取模。
樣例輸入
1樣例輸出
2思路：n太大，寫一個快速冪
#include <bits/stdc++.h> using namespace std; long long int mi(long long int a,long long int b,long long int m) {long long int ans=1;a=a%m;while(b!=0){if(b&1)ans=ans*a%m;b >>= 1;a=a*a%m;}return ans%m; } int main() {int n;cin>>n;int sum = mi(2,n,20180520)%20180520;cout<<sum;return 0; }神殿
題目描述
icebound通過勤工儉學，攢了一小筆錢，于是他決定出國旅游。這天，icebound走進了一個神秘的神殿。神殿由八位守護者守衛，總共由6464個門組成，每一道門后都有一個迷宮，迷宮的大小均為100 \times 100100×100。icebound在迷宮中總共耗時TT小時，消耗食物KK公斤。歷經千辛萬苦之后，icebound終于穿越了迷宮，到達了神殿的中心。神殿的中心有一個寶箱。寶箱上顯示有兩個正整數ll和rr。icebound苦思冥想，終于發現一些打開寶箱的線索。你需要找到一個數PP，它具有一個美妙的性質：它是[l,r][l,r]中所有數的二進制表示里，11的個數最多的一個數。如果你發現了這個美妙的數字，你就可以打開寶箱，獲得巨額財富。
比如[4,8][4,8]中：
4: 0100 5: 0101 6: 0110 7: 0111 8: 1000二進制表示中11的個數最多的數是77，它含有33個11。
輸入描述
輸入一行，兩個正整數：ll和rr，用空格隔開，代表神殿中寶箱上顯示的數。
1 \leq T < 2^{31}1≤T<231,
1 \leq K \leq 10^51≤K≤105,
1 \leq l \leq r \leq 2 \times 10^{9}1≤l≤r≤2×109
輸出描述
一個十進制數P，代表滿足條件的解。如果有多個P滿足條件，輸出最小的P。
樣例輸入
4 8樣例輸出
7思路：
求區間內二進數中1最多的那個數是多少。
求不超過r的位或和。
比如：
0 1 1
1 0 0
----------
1 1 1
有一個1就為1
#include<bits/stdc++.h> using namespace std; int main() {long long l,r,i;scanf("%lld %lld",&l,&r);for(i=l;i<=r;i++)if((i|i+1)>r)break;printf("%lld",i); }Mex Query
題目描述
Give?nn?non-negative integers, please find the least non-negative integer that doesn’t occur in the?nn?numbers.
輸入描述
The first line is an integer?TT, representing the number of test cases.
For each test case:
The first line of each test case is an integer?nn.
The second line of each test case are?nn?non-negative integers?a_iai?.
T \leq 10T≤10
n \leq 2 \times 10^5n≤2×105
0 \leq a_i < 2^{31}0≤ai?<231
輸出描述
or each test case, output a line with the answer.
樣例輸入
2 4 4 0 1 3 2 1 1樣例輸出
2 0思路：找出序列里第一個沒有出現過的數，排序，然后本數減前一個數大于一，就說明相差大于一，就找到了那個確實的數了。
#include<bits/stdc++.h> using namespace std; int arr[200005]; int main(){int t，k;cin >> t;while(t--){int n;scanf("%d", &n);for(int i = 1; i <= n; ++i)scanf("%d", &arr[i]);sort(arr+1, arr+n+1);arr[0] = -1;for(int i = 1; i < n; ++i){if(arr[i] - arr[i-1] > 1){printf("%d\n", arr[i-1]+1);break;}}}return 0; }icebound的商店
題目描述
icebound在得到神殿的寶藏之后，開了一家神秘的商店。你來到了商店，發現慷慨的icebound搞了TT次促銷活動。在每次促銷活動中，icebound都會想出一個他喜歡的數字，如果你買的商品的總價剛好等于icebound喜歡的數字，那么你就可以免費得到這些商品。
icebound的商店里一共有?1515?件商品，商品的價格和這家商店一樣神秘，第一件商品的價格是?11?元，第二件商品的價格是?22元，設第nn件商品的價格為w_nwn?元，則：w_n = w_{n-1} + w_{n-2} (3 \leq n \leq 15)wn?=wn?1?+wn?2?(3≤n≤15)。
如果在某次活動中icebound喜歡的數字是?44，那么共有?44?種購買方案：
1. 買 4個 第一種商品 2. 買 2個 第一種商品 和 1個 第二種商品 3. 買 2個 第二種商品 4. 買 1個 第一種商品 和 1個 第三種商品請你算出共有多少種方案可以免費購物，方案數對10000000091000000009(=10^9+9=109+9)取模。
輸入描述
第一行給出一個整數TT，表示icebound搞了TT次活動。
接下來的TT行每行給出一個正整數xx，表示在這次活動中icebound喜歡的數字。
1 \leq T \leq 30001≤T≤3000
1 \leq x \leq 30001≤x≤3000
輸出描述
輸出TT行，每行輸出一個正整數。
第ii行的正整數表示在第ii次活動中免費購物的方案數，方案數對10000000091000000009(=10^9+9=109+9)取模。
樣例輸入
3 5 20 30樣例輸出
6 134 509思路：動態規劃，背包求方法數的變形，物品為斐波那契數列前幾項，先求出來。然后轉移方程為dp[j]=(dp[j]+dp[j-fib[i]])%MOD
（總結的技巧，一般把式子的max變為sum即可。）
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e6; const int MOD = 1e9 + 9; int fib[50]; int dp[3005]; inline void init() //前15項商品 {fib[1] = 1, fib[2] = 2;for(int i = 3; i <= 15; ++i) fib[i] = fib[i - 1] + fib[i - 2]; } int main() {init();int T, x;scanf("%d", &T);while(T--) {scanf("%d", &x);memset(dp, 0, sizeof dp);dp[0] = 1;for(int i = 1; i <= 15; ++i)for(int j = fib[i]; j <= x; ++j)dp[j] = (dp[j] + dp[j - fib[i]]) % MOD;//情況求和printf("%d\n", dp[x] % MOD);}return 0; }跑圖
題目描述
跑圖是RPG游戲中很煩躁的事情。玩家需要跑到距離他最近的傳送點的位置。現在給你一張N \times MN×M的方格圖，每個方格中數值00表示為平地，數值11表示為傳送點，你的任務是輸出一張N \times MN×M的矩陣，Matrix_{xy}Matrixxy?表示從(x,y)(x,y)到距離它最近的傳送點的距離。 這里的距離是曼哈頓距離，(x_1,y_1) \rightarrow(x_2,y_2)(x1?,y1?)→(x2?,y2?)?的距離為|x_1-x_2|+|y_1-y_2|∣x1??x2?∣+∣y1??y2?∣。
輸入描述
第一行，有兩個數n,mn,m。接下來nn行，每行mm個數。
數據保證至少有一個傳送點。
1 \leq n \leq 5001≤n≤500，1 \leq m \leq 5001≤m≤500
輸出描述
nn行，每行mm個數，表示某個點到離它最近的傳送點的距離。
樣例輸入
2 3 0 0 0 1 0 1樣例輸出
1 2 1 0 1 0思路：直接把傳送點的位置放進一個隊列里然后跑BFS即可，每個點只需要被訪問一次，到傳送點的的距離也都是最近的
#include <bits/stdc++.h> using namespace std;const int inf = 0x3f3f3f3f; const int maxn = 500 + 5; int arr[maxn][maxn]; int vis[maxn][maxn]; int dir[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1}; int dis[maxn][maxn]; int n, m; struct Node{int x, y, dis; };bool check(int x, int y){if(x >= 0 && x < n && y >= 0 && y < m){return true;}return false; }int main(){int k;cin >> n >> m;memset(dis, inf, sizeof dis);queue<Node> q;for(int i = 0; i < n; ++i){for(int j = 0; j < m; ++j){scanf("%d", &k);arr[i][j] = k;if(k == 1){Node node = {i, j, 0};q.push(node);dis[i][j] = 0;}}}while(q.size()){Node tmp = q.front();q.pop();int tx = tmp.x;int ty = tmp.y;int ts = tmp.dis;for(int i = 0; i < 4; ++i){if(check(tx+dir[i][0], ty+dir[i][1])){int dx = tx + dir[i][0];int dy = ty + dir[i][1];if(dis[dx][dy] > ts + 1){dis[dx][dy] = ts + 1;Node t = {dx, dy, ts+1};q.push(t);}}}}for(int i = 0; i < n; ++i){for(int j = 0; j < m-1; ++j){printf("%d ", dis[i][j]);}printf("%d\n", dis[i][m-1]);}return 0; }K Multiple Longest Commom Subsequence
題目描述
KK has two sequences,?AA?and?BB, and wants to find the?kk?multiple longest common subsequence.A sequence?SS?is a?kkmultiple common subsequence of?AA?and?BB?if and only if it satisfies the following conditions:
SS?is a subsequence of?AA?and is a subsequence of?BB. (A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.)
The length of?SS?is?t\times kt×k?where?tt?is a nonnegative integer. The first element of?SS?is?S[1]S[1]. If we divide the sequence into?tt?groups with the?iith group containing?S[(i - 1) \times k + j] (1 \leq j \leq k)S[(i?1)×k+j](1≤j≤k), for every element?gg, it shares the same value with other elements that are in the same group which?gg?belongs to.
For example,?[1, 1, 2, 2][1,1,2,2]?is a double common subsequence of?[1, 2, 3, 1, 2, 3, 2][1,2,3,1,2,3,2]?and?[1, 3, 1, 2, 2][1,3,1,2,2]. KK wants to know the maximum length of such sequence.
輸入描述
The first line is an integer?TT, denoting the number of test cases.
For each test case, the first line are three integers?kk?,?nn,?mm, denoting the kind of subsequence, the length of?AA?and the length of?BB.
The second line are?nn?integers?A_1 \sim A_nA1?～An?, representing the elements of?AA.
The third line are?mm?integers?B_1 \sim B_mB1?～Bm?, representing the elements of?BB.
1 \leq T \leq 101≤T≤10?,?1\leq k, n, m \leq 10^31≤k,n,m≤103,?1\leq A_i, B_i \leq 10^31≤Ai?,Bi?≤103.
輸出描述
For each test case, output a line with the maximum length of?kk?multiple common subsequence.
樣例輸入
3 1 4 5 1 2 3 4 4 1 3 2 4 2 8 7 1 1 2 2 3 3 4 4 1 2 3 1 2 3 3 3 9 9 1 1 1 2 2 2 3 3 3 1 2 3 1 2 3 1 2 3樣例輸出
3 4 3題意：最長公共子序列，要求序列每個元素重復k次，比如1122重復兩次，111222重復三次。
輸入兩個字符串和k，輸出長度。
最長公共子序列的一個變形。。。
動態規劃。設dp[i][j]表示a串處理到i位置，b串處理到j位置的答案。預處理出從a串i位置向前數，第k個與i位置數
字相同的位置p[i]，用相同方式處理出B串的q[i]。
則轉移方程為dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-p[i]][j-q[j]]+k),其中第三種轉移必須在a[i]=b[j]而且p,q都存在的情況下轉移。
?
Nim Game
總感覺復制到這里符號就不對了，原題網址：http://newoj.acmclub.cn/problems/2013
題目描述
Description
Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap?[From Wikipedia, the free encyclopedia].?The goal of the game is to avoid being the player who doesn’t have any object to remove. The player who remove the last project is the winner.
Now KK and TT are playing Nim game with the optimal strategy. There are?nn?heaps of stones. The number of stones in?ii?-th heap is?a_iai?. They play this game?mm?times, and KK is the player making the first move. During the?ii?-th time they play the game on the heaps whose index in interval?[l_i,r_i][li?,ri?]. KK wants to know whether he has a winning strategy or not.
輸入描述
Input
The input consists of several test cases. The first line of the input gives the number of test cases,?T(1\le T\le 10^3)T(1≤T≤103).
For test case, the first line contains two integers?n(1\le n\le 10^6)n(1≤n≤106)?and?m(1\le m\le 10^6)m(1≤m≤106), representing the number of heap of stones and the game times.
The second line contains?nn?positive integers?a_1,a_2,\cdots,a_n(1\le a_i\le 10^9)a1?,a2?,?,an?(1≤ai?≤109), representing The number of stones in?ii-th heap.
In the next?mm?lines, each line contains two integers?l_i,r_ili?,ri?, which means the?$i: KaTeX parse error: $ within math mode$th game is played on the interval?[l_i,r_i][li?,ri?].
It’s guaranteed that?\sum n\le 2\times 10^6∑n≤2×106?and?\sum m\le 2\times 10^6∑m≤2×106．
輸出描述
Output
For each test case, let?f_ifi??represents the answer of the?ii?th game.
If KK has a winning strategy in the?ii?th game then?f_i=1fi?=1, otherwise?f_i=0fi?=0. Please output?\sum f_i*2^{m-i}\ mod\ 10^9+7∑fi??2m?i?mod?109+7，in which?1\le i\le m1≤i≤m．
樣例輸入
3 2 1 1 1 1 2 2 1 1 2 1 2 3 2 1 2 2 1 2 2 3樣例輸出
0 1 2思路：
和普通Nim游戲不同在于每一次會給出對應的堆區間
比如現在有5堆，每一堆個數分別為1 2 3 4 5，選擇1 3，代表選擇1 2 3這三堆為本輪的堆數
測試這區間的堆數的異或值是否為0，如果為0，必敗，否則必勝
需要記錄一個前綴異或和數組優化時間
每次給出[l,r]，只需要pre[r]^pre[l-1]即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e6; const int MOD = 1e9 + 7; int arr[N + 5]; ll pre[N + 5]; ll powmod(ll a, ll b) {ll res=1;a %= MOD;while(b){if(b & 1) res = res * a % MOD;a=a * a % MOD;b >>= 1;}return res; } int main(void) {int T, n, m, l, r;scanf("%d", &T);while(T--) {pre[0] = 0;scanf("%d %d", &n, &m);for(int i = 1; i <= n; ++i) {scanf("%d", arr + i);pre[i] = pre[i - 1] ^ arr[i]; //記錄異或前綴和}ll sum = 0;for(int i = 1; i <= m; ++i) {scanf("%d %d", &l, &r);if(pre[r] ^ pre[l - 1]) {//一個數如果異或兩次等于沒有異或過，比如1^2^3^2=1^3sum += powmod(2, m - i);sum %= MOD; //記得取模}}printf("%lld\n", sum % MOD);}return 0; }注：這個題是看yzx大佬思路的。
剩下的暫時不會做啦。。。。
?
總結
以上是生活随笔為你收集整理的2018第二届河北省大学生程序设计竞赛题解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： leetcode538 把二叉搜索树转换
- 下一篇： leetcode119. 杨辉三角 II