文章目录
1.寻找道路
洛谷P2296
还是贴个原题吧
原题
思路：搜索，图
其他的可能：宽搜？
我的代码
#include<bits/stdc++.h>
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;
queue<int>q;
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<<dis[x1];
return 0;
}
x1=head[x1];
while(x1!=0){
if(e2[edge[x1].to]==1&&no3[edge[x1].to]==0){
q.push(edge[x1].to);
dis[edge[x1].to]=dis[dian]+1;
}
x1=edge[x1].next;
}
}
cout<<"-1";
return 0;
}
估分：50
实际得分：60
2.国王的游戏
洛谷P1080
原题
思路：贪心，高精度
其他的可能：暴力枚举
我的代码(没高精度版）
#include<bits/stdc++.h>
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<y;
}
long long money[1010];
long long shangjin(int x){
money[x]=1;
for(int i=0;i<x;i++){
money[x]*=stu[i].a;
}
money[x]/=stu[x].b;
}
int n;
int main()
{
cin>>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<<money[n];
return 0;
}
估分：30~60
实际得分：60（不用高精度的数据竟然全过了）
从网上随便贴了一个高精度上去，竟然过了
正解
#include<bits/stdc++.h>
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<y;
}
long long money[1010];
long long shangjin(int x){
money[x]=1;
for(int i=0;i<x;i++){
money[x]*=stu[i].a;
}
money[x]/=stu[x].b;
}
int n,l=1,g[1000005];
void gj1(int x){
for(int i=1;i<=l;++i)
g[i]*=stu[x].a;
for(int i=1;i<=l;i++){
g[i+1]+=(g[i]/10);
g[i]=g[i]%10;
}
l++;
while(g[l]>9){
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<<endl;
}
int main(){
cin>>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<n;i++)
gj1(i);
gj2();
for(int i=l;i>=1;i--)
cout<<g[i];
cout<<endl;
return 0;
}
3.我吃了，没有
4.海底珍珠串
题面（洛谷上无所以贴出）
我真的不玩《塞尔达传说》啊！！！
#include<bits/stdc++.h>
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<<ans;
return 0;
}
贴个30分的贪心；
正解是状压dp，本蒟蒻不会（理直气壮 ）