2009

各大题目传送门

CSP-J 2009 T2 分数线划定

陈室先的总结8.8day4<-其余题目在这里

T2 分数线划定

思路

先算分数线是第几名m=m+m/2（取前150%），然后再按题目进行结构体排序，确定分数线，统计人数，输出分数线和人数，最后输出过线的人的信息

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct P{
	int a,b;
}a[55555];
bool cmp(P a,P b){
	if(a.b!=b.b)return a.b>b.b;
	else return a.a<b.a;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>m;
	m=m+m/2;
	for(int i=1;i<=n;i++)cin>>a[i].a>>a[i].b;
	sort(a+1,a+1+n,cmp);
	int f=a[m].b;
	int g=0;
	for(int i=1;i<=n;i++){
		if(a[i].b>=f)g++;
		else break;
	}
	cout<<f<<' '<<g<<"\n";
	for(int i=1;i<=n;i++){
		if(a[i].b>=f){
			cout<<a[i].a<<' '<<a[i].b<<"\n";
		}
		else break;
	}
}

2012

各大题目传送门

CSP-J 2012 T1 质因数分解

CSP-J 2012 T2 寻宝

CSP-J 2012 T3 摆花

CSP-J 2012 T4 文化之旅

T1质因数分解

思路

直接从1~n直接去试就可以了，如果$n\%i==0$，那么$cout<<n/i;$，至于为什么不要判断质数，那是因为一个合数的因子一定有质数，所以符合条件的质数会比合数先枚举到。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	long long n;
	cin>>n;
	for(int i=2;i<=n;i++){
		if(n%i==0){
			cout<<n/i;
            return 0;
		}	
	}
}

T2 寻宝

思路

这道题目先按正常思路去模拟，注意开个桶记录每层楼梯数，然后取模优化，先用牌子上的数字取模每层楼梯数，如果等于0那么要找每层的楼梯数次，接下来就是一层层的找楼梯

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,lt[10010];
struct P{
	long long h,l;
}a[10010][110];
int main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	cin>>n>>m;
	for(long long i=0;i<n;i++){
		for(long long j=0;j<m;j++){
			cin>>a[i][j].h>>a[i][j].l;
			if(a[i][j].h)lt[i]++;
		}
	}
	long long s=0,mi=20123;
	cin>>k;
	for(long long i=0;i<n;i++){
		long long p=lt[i];
		long long q=a[i][k].l;
		s=(s+q)%mi;
		if(q%p==0)q=p;
		else{
			q%=p;
		}
		long long g=0,ff=k;
		while(1){
			if(a[i][ff].h==1)g++;
			if(g==q)break;
			ff++;
			ff%=m;
		}
		k=ff;
	}
	cout<<s;
}

T3 摆花

思路

多重背包的方案数版，先写成滚动数组，再把状态转移方程改为f[j]+=f[j-k];

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,f[1111],mi=1000007;
int main(){
	cin>>n>>m;
	f[0]=1;
	for(long long i=0;i<n;i++){
		long long a;
		cin>>a;
		for(long long j=m;j>=0;j--){
			for(long long k=1;k<=j&&k<=a;k++){
				f[j]+=f[j-k];
				f[j]%=mi;
			}
		}
	}
	cout<<f[m];
}

错误原因

知道是多重背包的方案数版，但没想出状态转移方程，以后要多积累经验

T4 文化之旅

思路

爆搜加减枝，先倒着搜，然后再加启发式，先求多源最短路（不考虑语言）然后如果发现这个点我现在走的路加最短路线比最小值高就不搜了

代码

#include<bits/stdc++.h>
using namespace std;
int st[111],tt=0,n,k,m,s,t,w[111],p[111][111],d[111][111],mi=0x3f3f3f3f,g[111][111],v[111][111];
void dfs(int g,int l){
	if(l+v[g][s]>=mi)return;
	if(g==s){mi=min(mi,l);return;}
	for(int i=1;i<=n;i++){
		if(d[i][g]<0x3f3f3f3f){
			int wh=w[i];
			int pp=1;
			for(int j=1;j<=tt;j++){
				if(p[st[j]][wh]||wh==st[j]){
					pp=0;
					break;
				}
			}
			if(pp==0)continue;
			
			st[++tt]=wh;
			dfs(i,l+d[i][g]);
			tt--;
		
		}
	}
}
int main(){
	cin>>n>>k>>m>>s>>t;
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			cin>>p[i][j];
		}
	}
	memset(d,0x3f,sizeof d);
	memset(v,0x3f,sizeof v);
	for(int i=1;i<=n;i++)v[i][i]=0;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		d[a][b]=d[b][a]=min(d[a][b],c);
		v[a][b]=v[b][a]=min(d[a][b],c);
	}
	st[w[t]]++;
	for(int k =1;k<=n;k++)
		for(int i=1;i<=n;i++)
			v[i][s] = min(v[i][s], v[i][k] + v[k][s]);
	
	dfs(t,0);
	if(mi==0x3f3f3f3f)cout<<-1;
	else cout<<mi;
}

错误原因

没想到思路，以后台多方面的想思路，也许图论能用搜索写，还要掌握优化