CSP 2016-4

1.折點計數
O(n) 模擬即可

#include<iostream>
using namespace std;
#define N 1010
int a[N];
int main(){
	int n;
	cin>>n;
	
	int ans=0;
	for(int i=0;i<n;i++)
	cin>>a[i];
	
	for(int i=1;i<n-1;i++){
		if(a[i-1]>a[i]&&a[i]<a[i+1]||a[i-1]<a[i]&&a[i]>a[i+1])
		ans++;
	}
	
	cout<<ans<<endl;
	
}

2.俄羅斯方塊
思路:
用兩個二維陣列,g和s,g代表當前狀態,s代表上一個狀態;
每次處理時,先將g copy 到 s,同時把g中的下落方塊記為空,然后用s的值去更新g的值,若g中被更新的值為1,則代表觸底,答案就產生了
處理細節:
1.輸入p的左端l時,將l–,因為陣列以0作為開始,l以 1 作為開始
2.處理底部時,將底部全部置為1,即可不用處理越界的情況
3.將下落的方塊記為2
思考:要根據資料規模來設計演算法,又好敲,又不超時的演算法明顯是最優的,在運行時間充分的情況下,沒必要設計最快速的演算法， 還是要多多做題,多學模板才能玩出騷套路呀(●’?’●)

#include<iostream>
#include<vector>
using namespace std;
int g[20][20],s[20][20]; //G代表畫布
int p[4][4]; //代表掉落塊 
bool draw(){
	//g為當前畫布,s為下一時刻畫布
	// 1.先將g的狀態copy到s
	// 2.遍歷g,找到數值為2的點,記為0
	// 3.遍歷s,找到2的點,更新g 
	// 4.若g中被更新位置為1,則代表觸底,回傳false
	for(int i=0;i<15;i++)
		for(int j=0;j<10;j++){
			s[i][j]=g[i][j];
			if(g[i][j]==2) g[i][j]=0;
		}
	for(int i=14;i>=0;--i)
		for(int j=0;j<10;j++){
			if(s[i][j]==2){
				if(g[i+1][j]==1) return false;
				g[i+1][j]=2;
			}
		}
	return true; 
}
int main(){
	for(int i=0;i<15;i++)
		for(int j=0;j<10;j++)
			cin>>g[i][j];
	
	for(int i=0;i<10;i++) g[15][i]=1;//將畫布的"地板"設定為1
	
	for(int i=0;i<4;i++)
	for(int j=0;j<4;j++)
		cin>>p[i][j];
		
	int l;
	cin>>l;	//l表示的是4X4的方塊的最左端一列在15*10的方塊中是第幾列的 
	l--; 
	
	
	for(int i=0;i<4;i++)
	for(int j=l;j<l+4;j++){
		g[i][j]=(p[i][j-l]?2:0);
	}
	
	while(draw()) ;
	
	for(int i=0;i<15;i++)
	{
		for(int j=0;j<10;j++)
			cout<<(s[i][j]!=0)<<" ";
			cout<<endl;
	}
}

3.路徑決議:
題目的坑:

• 輸入有空行(代表無輸入,既當前路徑),所以要用getline處理
  自己寫的:

#include<iostream>
#include<vector>
#include<string>
#include<map>
using namespace std;
int n;
vector<string> cur;
vector<string> ans;
void init(){
	cin>>n;
	string now;
	cin>>now;
	for(int i=0;i<now.length();){
		int j=i+1;
		while(j<now.length()&&now[j]!='/') j++;
		string nxt=now.substr(i+1,j-i-1);
		i=j;
		if(nxt==""||nxt==".") continue;
		if(nxt=="..") {
		if(cur.size())
		cur.pop_back();
		}
		else cur.push_back(nxt);
	}
}

void solve(string path){
	int i=0;
	if(path.length()&&path[0]=='/'){
	i++,ans.clear();	}
	else ans=vector<string> (cur.begin(),cur.end());
		for(;i<path.length();){
		int j=i;
		while(j<path.length()&&path[j]!='/') j++;
		string nxt=path.substr(i,j-i);
		i=j+1;
		if(nxt==""||nxt==".") continue;
		if(nxt=="..") {
		if(ans.size())	
		ans.pop_back();
		}
		else ans.push_back(nxt);
	}
	if(!ans.size()) {cout<<"/"<<endl;return ;}
	for(int i=0;i<ans.size();i++)
	cout<<"/"<<ans[i];
	cout<<endl;
}

int main(){
	init();
	getchar();
	while(n--){
		string path;
		getline(cin,path);
		solve(path);
	}
}

y總的代碼:
y總代碼和我一樣的思路,就不自己敲了(●’?’●)

4.游戲
分析題目: 與傳統廣搜不同的地方在于,該廣搜多了一個在原地等待的選項(普通廣搜只是朝著四個方向搜),如果不加vis陣列(在該題中是cnt)來優化的話會超時,考慮如何加vis陣列， 因為有在原地等待的選項,如果vis只有true和false兩個取值是不可以的,因為他無法表示在原地等待這種狀態,因此用另一個陣列cnt,表示當前在該點的個數,保證該值永遠為1,若大于1則continue即可,若小于1則向該點轉移即可

#include<iostream>
#include<queue>
#include<set>
#define N 110
using namespace std;
struct node{
	int s,e; //該點危險的起始時間,左閉右閉區間 
	int cnt;
	node(){
		s=e=-1;
		cnt=0;
	}
};
node a[N][N];
struct qnode{
	int t;
	int x,y;
	bool operator<(const qnode &q)const{
	if(x!=q.x) return x<q.x;
	return y<q.y;
	}
};
set<qnode> hasnow;
int n,m,t;
int dir[4][2]={0,1,0,-1,-1,0,1,0};
int main(){
	cin>>n>>m>>t;
	while(t--){
		int r,c,aa,b;
		cin>>r>>c>>aa>>b;
		a[r][c].s=aa;
		a[r][c].e=b;
	}
	queue<qnode> q;
	q.push((qnode){0,1,1});
	while(q.size()){
		qnode top=q.front();
		a[top.x][top.y].cnt--;
		q.pop();
		
		if(top.x<=0||top.x>n||top.y<=0||top.y>m) continue;
		if(a[top.x][top.y].s<=top.t&&a[top.x][top.y].e>=top.t||a[top.x][top.y].cnt>=1) continue;
		
		if(top.x==n&&top.y==m) {cout<<top.t; return 0;}
		
		for(int i=0;i<4;i++)
		q.push((qnode){top.t+1,top.x+dir[i][0],top.y+dir[i][1]}),a[top.x+dir[i][0]][top.y+dir[i][1]].cnt++;
	}
}

y總的思路:
將地圖視作三維n*m*t(t最大取值為201,因此開一個110110201的陣列即可)
將不可到達點視為墻,反之則為空地
第k維的地圖的分布情況完全取決于輸入資料,
則把問題轉化為了三維的bfs問題
佇列求解即可
5.