2021 10 05 模拟赛

• 1.寻找道路
• 2.国王的游戏
• 3.我吃了，没有
• 4.海底珍珠串
• • 题面（洛谷上无所以贴出）

洛谷P2296
还是贴个原题吧
原题

思路：搜索，图

其他的可能：宽搜？

我的代码

#include
using namespace std;
struct node{
	int to,next;
}edge[200005];
node edge2[200005];
int s,t,n,m,e1[10005],e2[10005],head[10005],cnt,dis[10005];
int no1[10005],no2[10005],no3[10005];
int head2[10005],cnt2=0;
void cun(int x,int y){
	cnt++;
	edge[cnt].next=head[x];
	head[x]=cnt;
	edge[cnt].to=y;
}
void cun2(int x,int y){
	cnt2++;
	edge2[cnt2].next=head2[x];
	head2[x]=cnt2;
	edge2[cnt2].to=y;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(x==y)continue;
		cun(x,y);
		cun2(y,x);
	}
	cin>>s>>t;
	queueq;
	q.push(t);
	while(!q.empty()){
		int x1=q.front();
		q.pop();
		e1[x1]=1;no1[x1]=1;
		x1=head2[x1];
		while(x1!=0){
			if(no1[edge2[x1].to]==0)
				q.push(edge2[x1].to);
			x1=edge2[x1].next;
		}
	}
	for(int i=1;i<=n;i++){
		int x1=head[i],ok=0;
		while(x1!=0){
			if(e1[edge[x1].to]==0){
				ok=1;
				break;
			}
			x1=edge[x1].next;
		}
		if(ok==0)e2[i]=1;
	}
	q.push(s);dis[s]=0;
	while(!q.empty()){
		int x1=q.front();
		q.pop();
		no3[x1]=1;
		int dian=x1;
		if(x1==t){
			cout< 
估分：50
 实际得分：60
 
2.国王的游戏 
洛谷P1080
 原题
 
思路：贪心，高精度
 其他的可能：暴力枚举
 
我的代码(没高精度版）
 
#include
using namespace std;
struct per{
    int a,b;
}stu[10005];
bool cmp(per a,per b){
    int x=a.a*a.b;
    int y=b.a*b.b;
    return x>n;
    for(int i=0;i<=n;++i)
    {
        cin>>stu[i].a>>stu[i].b;
    }
    sort(stu+1,stu+n+1,cmp);
    for(int i=1;i<=n;i++){
    	shangjin(i);
	}
    //sort(money+1,money+1+n);
	cout< 
估分：30~60
 实际得分：60（不用高精度的数据竟然全过了）
 
从网上随便贴了一个高精度上去，竟然过了
 
正解
 
#include
using namespace std;
struct per{
    int a,b;
}stu[10005];
bool cmp(per a,per b){
    int x=a.a*a.b;
    int y=b.a*b.b;
    return x9){
        g[l+1]+=(g[l]/10);
        g[l]=g[l]%10;
        l++;
    }
    if(g[l]==0)l--;
}
void gj2(){
    for(int i=l;i>=1;i--){
        g[i-1]+=((g[i]%stu[n].b)*10);
        g[i]/=stu[n].b;
    }
    while(g[l]==0)
		l--;
    if(l==0)
        cout<<1<>n;
    for(int i=0;i<=n;++i){
        cin>>stu[i].a>>stu[i].b;
    }
    sort(stu+1,stu+n+1,cmp);
    g[1]=stu[0].a;
    for(int i=1;i=1;i--)
	cout< 
3.我吃了，没有 
4.海底珍珠串 
题面（洛谷上无所以贴出） 
我真的不玩《塞尔达传说》啊！！！
 
 
 
 
#include
using namespace std;
int n,a[200005],ans=0;
int b[30],ous,even,f,e;
char s;
void repe(int fir){
	memset(b,0,sizeof(b));
	even=0,ous=n-fir+1;
	for(int i=fir;i<=n;i++){
		b[a[i]]++;
		if(b[a[i]]%2==0) even--,ous++;
		else even++,ous--;
	}
}
int main(){
	scanf("%d",&n);
	ous=n;
	s=getchar();
	for(int i=1;i<=n;i++){
		s=getchar();
		a[i]=s-'a'+1;
		b[a[i]]++;
		if(b[a[i]]%2==0) even--,ous++;
		else even++,ous--;
	}
	s=getchar();
	f=1,e=n;
	while(f<=n){
		if(f>e){
			f++;
			e=n;
			ans++;
			repe(f);
			continue;
		}
		if(even==1||even==0){
			f=e+1;
			e=n;
			repe(f);
			ans++;
		}
		else{
			if(b[a[e]]%2==0) ous--,even++;
			else ous++,even--;
			b[a[e]]--;
			e--;
		}
	}
	cout< 
贴个30分的贪心；
 正解是状压dp，本蒟蒻不会（理直气壮 ）