- Prob.1 玩具谜题
模拟、、
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct node{
int dir;
char name[15];
}nd[100005];
int p,n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%d %s",&nd[i].dir,nd[i].name);
for(int i=1,a,b;i<=m;i++){
scanf("%d%d",&a,&b);
b%=n;
if(a^nd[p].dir) p+=b;
else p-=b;
p=(p+n)%n;
}
printf("%s",nd[p].name);
return 0;
}
- Prob.2 天天爱跑步
代码：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define MAXN 300005
using namespace std;
struct player{
int s,t,l;
}p[MAXN];
struct edge{
int to,next;
}E[MAXN*2],sE[MAXN],tE[MAXN],lE[MAXN];
int Head[MAXN],sHead[MAXN],tHead[MAXN],lHead[MAXN];
int fa[MAXN],dep[MAXN],tim[MAXN],c1[MAXN],c2[MAXN*2],ans[MAXN];
int Ent=2,sEnt=2,tEnt=2,lEnt=2;;
int n,m;
int find(int u){
if(fa[u]==u) return u;
return fa[u]=find(fa[u]);
}
void add(int u,int v,int &ent,int *head,edge *e){
e[ent]=(edge){v,head[u]};
head[u]=ent++;
}
void Tarjan(int u,int f){
fa[u]=u; dep[u]=dep[f]+1;
for(int i=sHead[u];i;i=sE[i].next){
int j=sE[i].to;
if(!fa[p[j].t]||p[j].l) continue;
int lca=find(p[j].t);
p[j].l=dep[u]+dep[p[j].t]-2*dep[lca];
add(lca,j,lEnt,lHead,lE);
}
for(int i=tHead[u];i;i=tE[i].next){
int j=tE[i].to;
if(!fa[p[j].s]||p[j].s==p[j].t) continue;
int lca=find(p[j].s);
p[j].l=dep[u]+dep[p[j].s]-2*dep[lca];
add(lca,j,lEnt,lHead,lE);
}
for(int i=Head[u];i;i=E[i].next){
int v=E[i].to;
if(v==f) continue;
Tarjan(v,u);
}
fa[u]=f;
}
void dfs(int u,int f){
int bc1=c1[dep[u]+tim[u]];
int bc2=c2[tim[u]-dep[u]+MAXN];
for(int i=sHead[u];i;i=sE[i].next){
c1[dep[u]]++;
}
for(int i=tHead[u];i;i=tE[i].next){
int j=tE[i].to;
c2[p[j].l-dep[u]+MAXN]++;
}
for(int i=Head[u];i;i=E[i].next){
int v=E[i].to;
if(v==f) continue;
dfs(v,u);
}
ans[u]+=c1[dep[u]+tim[u]]-bc1;
ans[u]+=c2[tim[u]-dep[u]+MAXN]-bc2;
for(int i=lHead[u];i;i=lE[i].next){
int j=lE[i].to;
if(dep[p[j].s]-dep[u]==tim[u]) ans[u]--;
c1[dep[p[j].s]]--;
c2[p[j].l-dep[p[j].t]+MAXN]--;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,a,b;i<n;i++){
scanf("%d%d",&a,&b);
add(a,b,Ent,Head,E);
add(b,a,Ent,Head,E);
}
for(int i=1;i<=n;i++) scanf("%d",&tim[i]);
for(int i=1;i<=m;i++){
scanf("%d%d",&p[i].s,&p[i].t);
add(p[i].s,i,sEnt,sHead,sE);
add(p[i].t,i,tEnt,tHead,tE);
}
Tarjan(1,0);
dfs(1,0);
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
Vijos上好像栈空间不够，要RE4组。把栈空间开大了一些，在本机测试NOI官网上的数据是AC了的。
- Prob.3 换教室
dp[i][j][0/1] 当前第i节课，已经申请了j次，当前是否申请的最小疲劳值。
定义出来以后，就比较好转移了。
之前定义错了，搞了好久。
启示：本题虽然是计算期望，但求得是最小期望。
而导致期望有大有小的原因就是我们的申请的位置不同。
即 申请的位置 这是一个决策选择，用dp处理。
而对于已经 申请了的位置，即确定了申请方案后，因为申请是否成功是有概率的，
所以再求出其对应的期望。
所以本题就是dp决策出最优申请方案，再在dp的同时求出对应的期望，用以辅助转移。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;
double g[2005],dp[2005][2005][2],ans;
int c[2005],d[2005];
int dis[305][305];
int N,M,V,E;
void cmin(double &a,double b){
if(a>b) a=b;
}
void readin(){
memset(dis,0x3f,sizeof(dis));
scanf("%d%d%d%d",&N,&M,&V,&E);
for(int i=1;i<=N;i++) scanf("%d",&c[i]);
for(int i=1;i<=N;i++) scanf("%d",&d[i]);
for(int i=1;i<=N;i++) scanf("%lf",&g[i]);
for(int i=1,u,v,w;i<=E;i++){
scanf("%d%d%d",&u,&v,&w);
dis[u][v]=min(dis[u][v],w);
dis[v][u]=min(dis[v][u],w);
}
for(int i=1;i<=V;i++) dis[0][i]=0,dis[i][i]=0;
}
void floyd(){
for(int k=1;k<=V;k++)
for(int i=1;i<=V;i++)
for(int j=1;j<=V;j++){
if(dis[i][k]==INF||dis[j][k]==INF) continue;
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
void DP(){
for(int i=1;i<=N;i++)
for(int j=0;j<=M;j++) dp[i][j][0]=dp[i][j][1]=1e9;
dp[1][0][0]=dp[1][1][1]=0;
for(int i=2;i<=N;i++)
for(int j=0;j<=min(i,M);j++){
//不选择申请
cmin(dp[i][j][0],dp[i-1][j][0]
+dis[c[i-1]][c[i]]);//前面不申请
cmin(dp[i][j][0],dp[i-1][j][1]
+dis[c[i-1]][c[i]]*(1.0-g[i-1])+dis[d[i-1]][c[i]]*g[i-1]);//前面申请
//选择申请
if(!j) continue;
cmin(dp[i][j][1],dp[i-1][j-1][0]
+dis[c[i-1]][c[i]]*(1.0-g[i])+dis[c[i-1]][d[i]]*g[i]);//前面申请
cmin(dp[i][j][1],dp[i-1][j-1][1]
+dis[c[i-1]][c[i]]*(1.0-g[i-1])*(1.0-g[i])
+dis[c[i-1]][d[i]]*(1.0-g[i-1])*g[i]
+dis[d[i-1]][c[i]]*g[i-1]*(1.0-g[i])
+dis[d[i-1]][d[i]]*g[i-1]*g[i]);
}
ans=dp[N][0][0];
for(int i=1;i<=M;i++) cmin(ans,min(dp[N][i][0],dp[N][i][1]));
printf("%.2lf",ans);
}
int main(){
readin();
floyd();
DP();
return 0;
}
- Prob.4 组合数问题
注意到多组输入都是相同的k
所以跑一个2000*2000的组合数递推求法，并对k取模
最后在矩阵合法范围内的0的个数就是答案。 代码：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int dp[2005][2005],s[2005][2005];
int n,m,k,t;
int main(){
scanf("%d%d",&t,&k);
dp[1][1]=1;
for(int i=2;i<=2001;i++)
for(int j=1;j<=i;j++)
dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%k;
for(int i=1;i<=2001;i++)
for(int j=1;j<=2001;j++)
s[i][j]=(j<=i&&dp[i][j]==0)+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
while(t--){
scanf("%d%d",&n,&m);
printf("%d
",s[n+1][m+1]);
}
return 0;
}
- Prob.5 蚯蚓
优先队列维护 50分
然后看了看网上给的正解，原来还可以这么单调啊。
因为割的比例固定，所以：
长的蚯蚓割了形成的前一段长度大于短的蚯蚓割了形成的前一段，
长的蚯蚓割了形成的后一段长度大于短的蚯蚓割了形成的后一段。
维护三个队列（手写）
第一个用来存储初始蚯蚓，按从大到小排好序。
第二个队列用来存储割断的蚯蚓的前一截。 （满足长度单调递减）
第三个队列用来存储割断的蚯蚓的后一截。 （满足长度单调递减）
对于当前取出的长度为x1的蚯蚓，把它割断成为了c1'，c2'，并放在对应的队列后面
x秒后，c1=c1'+x*d(增量) c2=c2'+x*d。
这时再取出的长度为x2+x*d的蚯蚓，把它割断成为了e1，e2,并放在对应的队列后面
那是否c1>e1,c2>e2呢?
考虑c1和e1的大小关系。
c1=q*x1+x*d
e1=q*(x2+x*d)
相减: c1-e1=q(x1-x2)+x*d*(1-q)
因为x1>x2,1>q,所以上式>0
所以满足队列具有单调性。
于是每次取出三个队列队首最大的那个来割。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
double p;
int q[3][10000005],head[3]={1,1,1},tail[3];
int n,m,d,u,v,t,add;
bool cmp(int a,int b){
return a>b;
}
void get(int &mv){
mv=-INF; int mp;
for(register int i=0;i<3;i++)
if(head[i]<=tail[i]&&q[i][head[i]]>mv)
mv=q[i][head[i]],mp=i;
head[mp]++;
}
void print(int val,int i,int lim){
if(i%t) return;
printf("%d",val);
if(i+t<=lim) printf(" ");
}
int main(){
freopen("earthworm.in","r",stdin);
freopen("earthworm.ans","w",stdout);
scanf("%d%d%d%d%d%d",&n,&m,&d,&u,&v,&t);
p=1.0*u/v; tail[0]=n;
for(register int i=1;i<=n;i++) scanf("%d",&q[0][i]);
sort(q[0]+1,q[0]+n+1,cmp);
for(register int i=1,mv;i<=m;i++){
get(mv); mv+=add;
print(mv,i,m);
add+=d;
int a=(int)(p*mv),b=mv-a;
q[1][++tail[1]]=a-add;
q[2][++tail[2]]=b-add;
}
printf("
");
for(register int i=1,mv;i<=n+m;i++){
get(mv); mv+=add;
print(mv,i,m+n);
}
fclose(stdout);
return 0;
}
- Prob.6 愤怒的小鸟
预处理好转移数组（即打某两个猪的同时，最多可以打那些猪）
然后就是状压dp。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#define rint register int
using namespace std;
const double eps=1e-7;
struct pig{
double x,y;
}p[20];
int g[20][20],dp[1<<18];
int n,m,T,all;
int sign(double x){
if(fabs(x)<=eps) return 0;
return x>0?1:-1;
}
void cmin(int &a,int b){
if(a>b) a=b;
}
bool get(int i,int j,double &a,double &b){
static double k11,k12,k13,k21,k22,k23,k;
k11=p[i].x*p[i].x; k12=p[i].x; k13=p[i].y;
k21=p[j].x*p[j].x; k22=p[j].x; k23=p[j].y;
if(!sign(k12-k22)) return 0;
if(!sign(k13/k12-k23/k22)) return 0;
k=k22/k12; a=(k23-k13*k)/(k21-k11*k);
k=k21/k11; b=(k23-k13*k)/(k22-k12*k);
if(sign(a)>0) return 0;
return 1;
}
bool check(int i,double a,double b){
static double x,y;
x=p[i].x; y=p[i].y;
return !sign(a*x*x+b*x-y);
}
int main(){
freopen("angrybirds.in","r",stdin);
freopen("angrybirds.out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m); all=(1<<n)-1;
memset(dp,0x3f,sizeof(dp));
memset(g,0,sizeof(g));
for(rint i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
for(rint i=0;i<n;i++)
for(rint j=0;j<n;j++) if(i!=j){
double a,b;
if(!get(i,j,a,b)) continue;
for(rint k=0;k<n;k++) if(check(k,a,b))
g[i][j]|=(1<<k);
}
dp[0]=0;
for(rint S=0;S<=all;S++)
for(rint i=0;i<n;i++){
if(S&(1<<i)) continue;
cmin(dp[S|(1<<i)],dp[S]+1);
for(rint k=1;k<=n;k++) if(i!=k)
cmin(dp[S|g[i][k]],dp[S]+1);
}
printf("%d
",dp[all]);
}
return 0;
}