文章目录
- 总括
- 一、寻找道路
- 二、国王游戏
- 三、书柜的尺寸
- 四、海底珍珠串
总括
题数：4
时间：4h
得分：290
一、寻找道路
P2296 寻找道路
来源：洛谷（NOIP2014 提高组）
算法：图论，搜索，模拟水题
得分：100
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,ss,ee;
bool p1[10005],p2[10005];
int head1[200005],nxt1[200005],ver1[200005],tot1=0;
int head2[200005],nxt2[200005],ver2[200005],tot2=0;
queue<int> w;
int dis[10005];
void add1(int x,int y){
ver1[++tot1]=y,nxt1[tot1]=head1[x],head1[x]=tot1;
}
void add2(int x,int y){
ver2[++tot2]=y,nxt2[tot2]=head2[x],head2[x]=tot2;
}
int main(){
scanf("%d%d",&n,&m);
memset(p1,0,sizeof(p1));
memset(p2,0,sizeof(p2));
memset(dis,0,sizeof(dis));
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
add1(x,y);
add2(y,x);
}
scanf("%d%d",&ss,&ee);
w.push(ee);
p2[ee]=1;
while(!w.empty()){
int temp=w.front();
w.pop();
for(int i=head2[temp];i;i=nxt2[i]){
int y=ver2[i];
if(!p2[y]){
p2[y]=1;
w.push(y);
}
}
}
if(p2[ss]==0){
cout<<-1;
return 0;
}
for(int i=1;i<=n;i++){
if(p2[i]==1){
p1[i]=1;
for(int j=head1[i];j;j=nxt1[j]){
int y=ver1[j];
if(p2[y]==0){
p1[i]=0;
break;
}
}
}
}
if(p1[ss]==0){
cout<<-1;
return 0;
}
dis[ss]=1,w.push(ss);
while(!w.empty()){
int temp=w.front();
w.pop();
if(temp==ee){
cout<<dis[ee]-1;
return 0;
}
for(int i=head1[temp];i;i=nxt1[i]){
int y=ver1[i];
if(p1[y]&&dis[y]==0){
dis[y]=dis[temp]+1;
w.push(y);
}
}
}
cout<<-1;
return 0;
}
反思：水就是水！！！
二、国王游戏
P1080 国王游戏
来源：洛谷（NOIP2012 提高组）
算法：高精度，贪心，数学
得分：60
代码：
#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
int a;
int b;
int c;
int d;
int e;
}m[1010];
bool cmp(node x,node y){
return x.c<y.c;
}
long long ans=-1;
int main(){
scanf("%d",&n);
for(int i=0;i<=n;i++){
scanf("%d%d",&m[i].a,&m[i].b);
m[i].c=m[i].a*m[i].b;
m[i].d=0;
m[i].e=1;
}
sort(m+1,m+1+n,cmp);
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
int t1=m[j].a/m[i].b,t2=m[j].a%m[i].b;
m[i].d=m[i].d*t1*m[i].b+m[i].d*t2+m[i].e*t1;
m[i].e=m[i].e*t2;
m[i].d+=m[i].e/m[i].b;
m[i].e%=m[i].b;
}
if(ans==-1||ans<m[i].d) ans=m[i].d;
}
cout<<ans;
return 0;
}
正解：
#include <bits/stdc++.h>
using namespace std;
int now[20010],sum[20010],ans[20010],add[20010];
struct Node {
int a;
int b;
long long a_b;
}node[1010];
int read() {
int ans=0,flag=1;
char ch=getchar();
while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
if(ch=='-') flag=-1,ch=getchar();
while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
return ans*flag;
}
void times(int x) {
memset(add,0,sizeof(add));
for(int i=1;i<=ans[0];i++) {
ans[i]=ans[i]*x;
add[i+1]+=ans[i]/10;
ans[i]%=10;
}
for(int i=1;i<=ans[0]+4;i++) {
ans[i]+=add[i];
if(ans[i]>=10) {
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
if(ans[i]!=0) {
ans[0]=max(ans[0],i);
}
}
return ;
}
int divition(int x) {
memset(add,0,sizeof(add));
int q=0;
for(int i=ans[0];i>=1;i--) {
q*=10;
q+=ans[i];
add[i]=q/x;
if(add[0]==0 && add[i]!=0) {
add[0]=i;
}
q%=x;
}
return 0;
}
bool compare() {
if(sum[0]==add[0]) {
for(int i=add[0];i>=1;i--) {
if(add[i]>sum[i]) return 1;
if(add[i]<sum[i]) return 0;
}
}
if(add[0]>sum[0]) return 1;
if(add[0]<sum[0]) return 0;
}
void cp () {
memset(sum,0,sizeof(sum));
for(int i=add[0];i>=0;i--) {
sum[i]=add[i];
}
return ;
}
bool cmp(Node a,Node b) {
return a.a_b<b.a_b;
}
int main() {
int n=read();
for(int i=0;i<=n;i++) {
node[i].a=read(),node[i].b=read();
node[i].a_b=node[i].a*node[i].b;
}
sort(node+1,node+n+1,cmp);
ans[0]=1,ans[1]=1;
for(int i=1;i<=n;i++) {
times(node[i-1].a);
divition(node[i].b);
if(compare()) {
cp();
}
}
for(int i=sum[0];i>=1;i--)
printf("%d",sum[i]);
return 0;
}
反思：正常算法白嫖60分不成问题，满分需要高精度，有时间再写！！！
三、书柜的尺寸
P2160 书柜的尺寸
来源：洛谷（SHOI2007 省选）
算法：动态规划，排序，滚动数组
得分：100
代码：
#include<bits/stdc++.h>
using namespace std;
struct node{
int h;
int t;
}a[80];
int n,sum[80],f[2][2105][2105];
bool cmp(node x,node y){
return x.h>y.h;
}
int main(){
long long ans=1<<30;
scanf("%d",&n);
sum[0]=0;
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].h,&a[i].t);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i].t;
memset(f,0x3f,sizeof(f));
f[0][0][0]=0;
int now,pre;
for (int i=1;i<=n;i++){
now=i&1;pre=now^1;
memset(f[now],0x3f,sizeof(f[now]));
for (int j=0;j<=sum[i];j++){
for (int k=0;k<=sum[i];k++){
if (f[pre][j][k]!=0x3f){
if(j==0)
f[now][j+a[i].t][k]=min(f[now][j+a[i].t][k],f[pre][j][k]+a[i].h);
else
f[now][j+a[i].t][k]=min(f[now][j+a[i].t][k],f[pre][j][k]);
if(k==0)
f[now][j][k+a[i].t]=min(f[now][j][k+a[i].t],f[pre][j][k]+a[i].h);
else
f[now][j][k+a[i].t]=min(f[now][j][k+a[i].t],f[pre][j][k]);
if(sum[i-1]-j-k==0)
f[now][j][k]=min(f[now][j][k],f[pre][j][k]+a[i].h);
else
f[now][j][k]=min(f[now][j][k],f[pre][j][k]);
}
}
}
}
for(int i=1;i<=sum[n];i++)
for(int j=1;j<=sum[n];j++)
if(sum[n]-i-j)
ans=min(ans,(long long)max(max(i,j),sum[n]-i-j)*(long long)f[now][i][j]);
cout<<ans;
return 0;
}
反思：没什么
四、海底珍珠串
来源：大师兄原创题
算法：模拟，贪心
得分：
代码：
#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;
}
反思：