第一次CSP模測

第一題

咕咕東的奇遇

咕咕東是個貪玩的孩子，有一天，他從上古遺迹中得到了一個神奇的圓環。這個圓環由字母表組成首尾相接的環，環上有一個指針，最初指向字母a。咕咕東每次可以順時針或者逆時針旋轉一格。例如，a順時針旋轉到z，逆時針旋轉到b。咕咕東手裡有一個字元串，但是他太笨了，是以他來請求你的幫助，問最少需要轉多少次。

Input

輸入隻有一行，是一個字元串。

Output

輸出最少要轉的次數。

Example

• input

  zeus

• output

  18

解題思路

這個題比較簡單，隻需要實作一個判斷正着轉和倒着轉哪個更小的函數即可，倒着轉的時候我們利用的是模運算的思想。

代碼實作

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
int len;
int judge(char a, char b)
{
	int aa = a, bb = b;
	int x = max(a, b) - min(a, b);
	int y = 26 + min(a, b) - max(a, b);
	return x < y ? x : y;
}


int main()
{
	string a;
	cin >> a;
	int x = 'a';
	int sum = 0;
	int index;
	len = a.length();
	//sort(a.begin(),a.end());
	for (int i = 0; i < len; i++)
	{
		int temp1 = judge(x, a[i]);
		x=a[i];
		sum += temp1;
	}
	cout << sum;
}

           

第二題

咕咕東想吃飯

咕咕東考試周開始了，考試周一共有n天。他不想考試周這麼累，于是打算每天都吃頓好的。他決定每天都吃生煎，咕咕東每天需要買 ai個生煎。但是生煎店為了刺激消費，隻有兩種購買方式：①在某一天一次性買兩個生煎。②今天買一個生煎，同時為明天買一個生煎，店家會給一個券，第二天用券來拿。沒有其餘的購買方式，這兩種購買方式可以用無數次,但是咕咕東是個節儉的好孩子，他訓練結束就走了，不允許訓練結束時手裡有券。咕咕東非常有錢，你不需要擔心咕咕東沒錢，但是咕咕東太笨了，他想問你他能否在考試周每天都能恰好買ai個生煎。

請你幫幫他吧！

Input

輸入兩行，第一行輸入一個正整數n(1<=n<=100000)(1<=n<=100000)，表示考試周的天數。

第二行有n個數，第i個數a_i（0<=a_i<=10000）a i

​

（0<=a i <=10000）表示第i天咕咕東要買的生煎的數量。

Output

能夠每天食用a[i]個生煎且n天後無卷剩餘，輸出"YES"，如果不能滿足，輸出“NO”。（輸出不帶引号）

Example

• input1

  4

  1 2 1 2

• output1

  YES

• input2

  3

  1 0 1

• output2

  NO

解題思路

這個題求解的關建在于某一天要吃掉的生煎的數目是否能被2整除，能被2整除則選擇方式一，不能被整除則同時選擇方式一和方式二。比如第一天買了101個生煎，那麼就必須用方式一買100個再用方式二買剩下的一個，第二天就需要判斷前一天是否有券，有則将需要購買的數目-1，計算方式同上，依次類推，判斷最後能否不剩下券即可。

代碼實作

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	int num[n];
	bool flag = 1;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}
	bool pre = 0, cur;
	for (int i = 0; i < n ; i++) {
		if(!num[i]&&pre)
			flag = 0;
		cur = num[i] % 2;
		pre = (!cur&&pre)||(cur&&!pre);
	}
	flag = flag && !pre;
	if (flag)cout << "YES";
	else
		cout << "NO";
	return 0;
}
           

第三題

可怕的宇宙射線

衆所周知，瑞神已經達到了CS大學生的天花闆，但殊不知天外有天，人外有苟。在浩瀚的宇宙中，存在着一種叫做苟狗的生物，這種生物天

生就能達到人類研究所學生的知識水準，并且天生擅長CSP，甚至有全國第一的水準！但最可怕的是，它可以發出宇宙射線！宇宙射線可以摧毀

人的智商，進行降智打擊！

宇宙射線會在無限的二維平面上傳播（可以看做一個二維網格圖），初始方向預設向上。宇宙射線會在發射出一段距離後分裂，向該方向的

左右45°方向分裂出兩條宇宙射線，同時威力不變！宇宙射線會分裂 次，每次分裂後會在分裂方向前進 個機關長度。

現在瑞神要帶着他的小弟們挑戰苟狗，但是瑞神不想讓自己的智商降到普通大學生 那麼菜的水準，是以瑞神來請求你幫他計算出共有多

少個位置會被"降智打擊"

Input

輸入第一行包含一個正整數n(n <= 30),表示宇宙射線會分裂n次

第二行包含n個正整數a1, a2, … , 第i個數a[i];(a[i]<= 5)表示第次分裂的宇宙射線會在它原方向上繼續走多少個機關長度。

Output

輸出一個整數ans，表示宇宙射線的覆寫範圍。

Example

• input

  4

  4 2 2 3

• output

  39

解題思路

這個題乍一看用模拟來做複雜度爆炸，最高會有2^30的複雜度，但是實際上走過的範圍不大，我們隻需要用400×400的數組就可以覆寫平面。我們需要盡可能地剪枝，遞歸時（用的dfs），每次分裂會産生兩個方向，若有一個方向我們已經周遊過，那麼就沒必要再次周遊，我們同時還需要記錄分裂時的資訊：這是第幾次分裂已經分裂的方向，直到達到分裂要求的次數或者四維數組記錄資訊為1.

代碼實作

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

int map[400][400][30][8],vis[400][400],ans, len[30],n;
int step[8][2] = {0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1};
typedef pair<int, int> p;

void dfs(int num , int dir, p point) {
	int x = point.first, y = point.second;
	if (num >= n || map[x][y][num][dir]==1) return ;
	map[x][y][num][dir] = 1;
	for (int i = 0; i < len[num]; i++) {
		x += step[dir][0];
		y += step[dir][1];
		if (!vis[x][y]) vis[x][y] = 1;
	}
	point = make_pair(x, y);
	dfs(num + 1, (dir+1)%8, point);
	dfs(num + 1, (dir+7)%8, point);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> len[i];
	dfs(0, 0,make_pair(200,200));
	for (int i = 0; i < 400; i++)
		for (int j = 0; j < 400; j++)
		{
			if (vis[i][j] == 1) ans++;
		}
	cout << ans << endl;
	return 0;
}
           

賽後總結

CSP模拟賽讓我認識到自己的不足，除了比較簡單的第一題（第一題還想複雜了）做的比較快，其他兩道題目均遇到了思維上的困難，第二題開始沒有看懂題（一直以為是一天買兩個或者買一個生煎，當時腦子已經傻掉了），隻拿到一半分數，補題才ac，第三題做題的時候開始就陷入了一個誤區：認為這個題沒有辦法模拟（複雜度爆炸），然後嘗試用歸納或者别的數學方法來解決這個題目（背離了這個題目原本的意思），後來與大佬讨論才明白dfs剪枝可以搞定這個題。

大概想明白自己馬力為啥這麼低了，做題太少，沒有形成相應的思維。coding能力是程式員核心能力，多做題才能成為一名優秀的程式員2333。