地址：http://www.bnuoj.com/bnuoj/contest_show.php?cid=2648
A题 POJ1845
由于题目很短，所以先做了这道题，本来以为会TLE，结果没T给WA了，后来再看觉得自己想的有些简单，正常做法应该会TLE的。。
百度了一下找到了公式和做法之后A了
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctype.h>
#include<algorithm>
using namespace std;
const int mod=9901;
long long int sum(long long int p,long long int n);
long long int power(long long int p,long long int n);
int main()
{
int a,b,i,k=0;;
int p[10000];
int n[10000];
scanf("%d%d",&a,&b);
for(i=2;i*i<=a;i==2?i++:i+=2)
{
if(a%i==0)
{
p[k]=i;
n[k]=0;
while(!(a%i))
{
n[k]++;
a/=i;
}
k++;
}
}
if(a!=1)
{
p[k]=a;
n[k++]=1;
}
int ans=1;
for(i=0;i<k;i++)
ans=(ans*(sum(p[i],n[i]*b)%mod))%mod;
printf("%d\n",ans);
return 0;
}
long long int sum(long long int p,long long int n)
{
if(n==0) return 1;
if(n%2) return (sum(p,n/2)*(1+power(p,n/2+1)))%mod;
else return (sum(p,n/2-1)*(1+power(p,n/2+1))+power(p,n/2))%mod;
}
long long int power(long long int p,long long int n)
{
long long int sq=1;
while(n>0)
{
if(n%2)
sq=(sq*p)%mod;
n/=2;
p=p*p%mod;
}
return sq;
}
B题 HDU2476
看到题还以为是编辑距离，当时编辑距离没想起来就先放下了，后来发现不是编辑距离 = =、 不过都是dp，重点是状态转移方程，感觉dp好厉害
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctype.h>
#include<algorithm>
using namespace std;
char a1[105],a2[105];
int p[105][105],q[105];
int main()
{
int i,ii,j,k;
while(scanf("%s%s",a1,a2)!=EOF)
{
memset(p,0,sizeof(p));
for(i=0;i<strlen(a1);i++)
{
for(j=i;j<strlen(a1);j++)
p[i][j]=j-i+1;
}
for(ii=0;ii<strlen(a1);ii++)
{
for(i=0;i<strlen(a1)&&i+ii<strlen(a1);i++)
{
j=i+ii;
p[i][j]=p[i+1][j]+1;
for(k=i+1;k<=j;k++)
{
if(a2[k]==a2[i])
p[i][j]=min(p[i][j],p[i+1][k]+p[k+1][j]);
}
}
}
if(a1[0]==a2[0])
q[0]=0;
else
q[0]=1;
for(i=1;i<strlen(a1);i++)
{
q[i]=p[0][i];
if(a1[i]==a2[i])
q[i]=q[i-1];
else
{
int k;
for(k=0;k<i;k++)
q[i]=min(q[i],q[k]+p[k+1][i]);
}
}
printf("%d\n",q[strlen(a1)-1]);
}
return 0;
}
C题 Hdu 1872
这个以前做过，结构体排序。。
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<time.h>
using namespace std;
struct node
{
char name[60];
int score;
int r; //r作为标识符，为之后稳定排序做准备
};
struct node student[305],test[305];
bool cmp(struct node a,struct node b)
{
if(a.score==b.score) return a.r<b.r;
else return a.score>b.score;
}
int main()
{
int n,i,k;
while(scanf("%d",&n)!=EOF)
{
k=1; //k==1是不稳定 k==2是稳定 k==3是error
memset(student,0,sizeof(student));
memset(test,0,sizeof(test));
for(i=0;i<n;i++)
{
scanf("%s%d",&student[i].name,&student[i].score);
student[i].r=i;
}
sort(student,student+n,cmp);
for(i=0;i<n;i++)
{
scanf("%s%d",&test[i].name,&test[i].score);
if(test[i].score>test[i-1].score&&i) k=3;
}
if(k!=3)
{
for(i=0;i<n;i++)
{
if(strcmp(student[i].name,test[i].name)!=0||student[i].score!=test[i].score) break;
}
if(i==n) k=2;
}
if(k==1)
{
printf("Not Stable\n");
for(i=0;i<n;i++)
printf("%s %d\n",student[i].name,student[i].score);
}
else if(k==2)
{
printf("Right\n");
}
else if(k==3)
{
printf("Error\n");
for(i=0;i<n;i++)
printf("%s %d\n",student[i].name,student[i].score);
}
}
return 0;
}
D题 HDU 1896
优先队列的题，做的时候不会。。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
using namespace std;
struct node
{
int pos,dis;
};
struct cmp
{
bool operator () (node a,node b)
{
if(a.pos!=b.pos)
return a.pos>b.pos;
else
return a.dis>b.dis;
}
};
int main()
{
priority_queue<node,vector<node>,cmp> q;
int n,i,t,k;
node p;
scanf("%d",&t);
while(t--)
{
k=1;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&p.pos,&p.dis);
q.push(p);
}
while(!q.empty())
{
p=q.top();
q.pop();
if(k)
{
k=0;
p.pos+=p.dis;
q.push(p);
}
else
k=1;
}
printf("%d\n",p.pos);
}
return 0;
}
E题 POJ2187
凸包问题，忘看了。。先留着
F题 HDU1548
对深搜广搜理解还不够，起初一直在用深搜做，RE了几遍 WA了几遍，原来要用广搜，如果用广搜这题就很好做了
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string.h>
#include<ctype.h>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include <limits.h>
using namespace std;
int p[205],visited[205];
int n,a,b;
int main()
{
int i,k,m;
while(scanf("%d",&n),n)
{
queue<int> q;
scanf("%d%d",&a,&b);
memset(visited,0,sizeof(visited));
for(i=1;i<=n;i++)
scanf("%d",&p[i]);
q.push(a);
visited[a]=1;
k=0;
while(!q.empty())
{
m=q.front();
q.pop();
if(m==b) {k=1;break;}
if(m-p[m]>0&&m-p[m]<=n&&!visited[m-p[m]])
{
visited[m-p[m]]=visited[m]+1;
q.push(m-p[m]);
}
if(m+p[m]>0&&m+p[m]<=n&&!visited[m+p[m]])
{
visited[m+p[m]]=visited[m]+1;
q.push(m+p[m]);
}
}
if(k) printf("%d\n",visited[b]-1);
else printf("-1\n");
}
return 0;
}