[数据结构与算法]CSP 2017-9

1.打酱油
贪心模拟即可

#include<iostream>
using namespace std;

int main(){
	int n;
	cin>>n;
	int ans=0;
	while(n>=10){
		if(n>=50){
			n-=50;
			ans+=7;
		}else if(n>=30){
			n-=30;
			ans+=4;
		}else if(n>=10){
			n-=10;
			ans++;
		}
	}
	cout<<ans;
}

y总的思路:(不会证明只会用
设用一次性买三瓶的次数为k,则一次性买五瓶的次数为(n-3k)/5
所以总瓶数res=n+k+(n-3k)/52
从0到n/3(向下取整)枚举k,统计最大的总瓶数即可

#include<iostream>
using namespace std;
#define N 1010

int main(){
	int n;
	cin>>n;
	n/=10;
	int res=0;
	for(int k=0;k<=n/3;k++)
	res=max(res,n+k+(n-k*3)/5*2);
	cout<<res<<endl;
 }

2.公共钥匙盒
思路:

1. 把(同一个老师的)取钥匙和还钥匙当做两个分开的操作来看
2. 为取钥匙和还钥匙的操作进行排序,对取钥匙,按照取钥匙的时间进行排序,对于还钥匙,先按照归还时间排序,再按照钥匙编号排序
3. 先用数组模拟取和归还的两种操作,如果超时再考虑用其他数据结构优化
   测试后发现,用数组模拟即可满分通过:

#include<iostream>
#include<algorithm>
using namespace std;
#define N 1010
int n,k;
struct find{
	int t,p;
	bool operator<(const find &f)const{
	return t<f.t;
	}
}finds[N];
struct back{
	int t,p;
	bool operator<(const back &b)const{
	if(t!=b.t) return t<b.t;
	return p<b.p;
	}
}backs[N];
int keys[N];
void get_key(int x){
	for(int i=1;i<=n;i++)
	if(keys[i]==x){
		keys[i]=-1;
		break;
	}	
}
void back_key(int x){
	for(int i=1;i<=n;i++){
		if(keys[i]==-1){
			keys[i]=x;
			break;
		}
	}
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
	keys[i]=i;
}
for(int i=0;i<k;i++){
	int w,s,l;
	cin>>w>>s>>l;
	finds[i].t=s;
	backs[i].t=s+l;
	backs[i].p=finds[i].p=w;
}
sort(backs,backs+k);
sort(finds,finds+k);
int backp=0,findp=0;
for(int t=1;t<=10000+100;t++){
	while(backp<k&&backs[backp].t==t){
		back_key(backs[backp++].p);
	}
	while(findp<k&&finds[findp].t==t){
		get_key(finds[findp++].p); 
	}
}

for(int i=1;i<=n;i++)
	cout<<keys[i]<<" ";
}

3.JSON查询
自己写的:(记得要对拍呀

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
#define N 1010
int n,k;
string read_str(const string &s,int &i){//读出一个变量 
	string res="";
	for(;i<s.length()&&s[i]!='"';i++){
		if(s[i]=='\\') i++;
		res+=s[i];
	}
	return res; 
}

string skip(string &s){ //跳过空格
	string res="";
	for(int i=0;i<s.length();i++){
		if(s[i]==' ') continue ;
		res+=s[i];
	}
	return res;
}

struct jsonObj{
	int type; //0为字符串 1为对象 
	string data;
	map<string,jsonObj *> ch;
	
	jsonObj(const string &data){
	type=0;
	this->data=data;
	}
	
	jsonObj(const string &s,int &i){//从start开始构造json对象 
		type=1;
		i++;
		string name,val;
		while(s[i]!='}'){
		if(s[i]==',') i++;
		i++; //跳过 "
		name=read_str(s,i); //读出变量
		i+=2; //跳过 ":
		if(s[i]=='{'){
			ch[name]=new jsonObj(s,i);
		}else{
		i++;
		val=read_str(s,i);
		i++;
		ch[name]=new jsonObj(val);
		}
		}
		i++;	
	}
	
	string dfs(string &s,int &i){
		if(i>=s.length()){
		if(type) return "OBJECT";
		else return "STRING "+data;	
		}

		string name="";
		while(i<s.length()&&s[i]!='.') name+=s[i++];
		i++;
		if(ch.find(name)!=ch.end()){
			return ch[name]->dfs(s,i);
		}else{
			return "NOTEXIST";
		}
	}
	
	void out(){
		if(type){
			for(map<string,jsonObj *>::iterator it=ch.begin();it!=ch.end();it++)
			{
			cout<<it->first<<":";
			it->second->out();}
		}else{
			cout<<data<<endl;
		}
	}
};	

int main(){
	int n,m;
	cin>>n>>m;
	getchar();
	string s="";
	while(n--){
		string t;
		getline(cin,t);
		s+=t;
	}
	s=skip(s);
	int k=0;
	jsonObj root(s,k);
	while(m--){
		string req;
		cin>>req;
		int p=0;
		cout<<root.dfs(req,p)<<endl;
	}
	
}

y总的:y总的竟然和我的思路和代码都差不多,就不贴了
4.通信网络:
题目抽象后:统计一个图中特殊点的个数,何为特殊点:该点可以从其他点出发到达该点或者从该点出发可以到其他点,全部其他点满足上述任何一个条件则该点为特殊点。
用一个二维数组,vis[i][j]记录可以从i出发到j
知道抽象后的题目再敲出代码不难,难在如何抽象题目,智力不够呀,多向大佬们学习。

#include<iostream>
#include<map>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define N 1010
int a[N][N];
vector<int> G[N];
int n,m;
void dfs(int s,int cur){
	if(a[s][cur]) return ;
	a[s][cur]=1;
	
	for(int i=0;i<G[cur].size();i++)
		dfs(s,G[cur][i]);
}
int main(){
	memset(a,0,sizeof(a));
	cin>>n>>m;
	
	while(m--){
		int a,b;
		cin>>a>>b;
		G[a].push_back(b);
	}
	
	for(int i=1;i<=n;i++){
		dfs(i,i);
	}
	
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
		if(!(a[i][j]||a[j][i])) {
			ans--;
			break;
		}
		ans++;
	}
	
	cout<<ans<<endl;
}