2013年"浪潮杯"山东省第四届ACM大学生程序设计竞赛排名：http://acm.upc.edu.cn/ranklist/
一、第J题坑爹大水题，模拟一下就行了
J:Contest Print Server
【题解】：
题目大意：输入 n,s,x,y,mod 分别队伍数n，还有一个s生成函数 s=((s*x)+y)%mod，就是打印机根据要求打印纸张，打印到s时，打印机将重置，生成新的s
【code】：
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std; int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,s,x,y,mod,i,p;
char team[],str[];
int cnt = ;
scanf("%d%d%d%d%d",&n,&s,&x,&y,&mod);
for(i=;i<n;i++)
{
scanf("%s%s%d%s",team,str,&p,str);
while()
{
if(p<=s-cnt)
{
cnt+=p;
printf("%d pages for %s\n",p,team);
break;
}
else
{
printf("%d pages for %s\n",s-cnt,team);
s = ((s*x)+y)%mod;
cnt = ;
}
}
}
putchar();
}
return ;
}
二、第I题概率DP问题
I:The number of steps
【题解】：
1
/ \
2 — 3
/ \ / \
4 — 5 — 6
输入概率：a b c d e 分别表示：
例如：
1
a/ \b 只有左右孩子的就是概率a、b
c — 3
d / \e 有左右孩子并且有左兄弟 概率分别为 c、d、e
— 5 如果只有左兄弟的话概率为 1
只有以上这三种情况：
如果f(i)表示第i步达到目的地的概率的话
结果ans = f(1)*1 + f(2)*2 + f(3)*3 + ....+f(n)*n
【code】：
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std; double dp[][][];
int main()
{
int n;
while(~scanf("%d",&n)&&n)
{
double a,b,c,d,e;
scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e);
memset(dp,,sizeof(dp));
dp[][][] = ;
int i,j,k;
for(k=;k<=(n-)*;k++)
{
for(i=;i<=n;i++)
{
for(j=;j<=i;j++)
{
if(j-<&&i+<=n&&j+<=n)
{
dp[k][i+][j] += dp[k-][i][j]*a;
dp[k][i+][j+] += dp[k-][i][j]*b;
}
else if(j->=&&i+<=n&&j+<=n)
{
dp[k][i][j-] += dp[k-][i][j]*e;
dp[k][i+][j] += dp[k-][i][j]*c;
dp[k][i+][j+] += dp[k-][i][j]*d;
}
else if(j->=&&i==n)
{
dp[k][i][j-] += dp[k-][i][j];
}
}
}
}
double res = ;
for(i=;i<=*(n-);i++)
{
res+=dp[i][n][]*i;
}
printf("%.2lf\n",res);
}
return ;
}
三、第A题，向量旋转
A - Problem A:Rescue The Princess
【题解】：
给你平面上两个点A、B求点C，是的A、B、C逆时针成等边三角形
向量的旋转：
【code1】：
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std; double xx1,yy1,xx2,yy2; int main()
{
int T;
scanf("%d",&T);
while (T--)
{
scanf("%lf%lf%lf%lf",&xx1,&yy1,&xx2,&yy2);
double tx = xx2 - xx1;
double ty = yy2 - yy1; double x = tx*(1.0/2.0) - ty*(sqrt(3.0)/2.0) + xx1;
double y = ty*(1.0/2.0) + tx*(sqrt(3.0)/2.0) + yy1;
printf("(%.2lf,%.2lf)\n",x,y);
}
return ;
}
不会向量旋转，直接解方程方法做：
【code2】:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define exb 1e-6
#define PI acos(-1.0)
using namespace std;
struct node
{
double x,y;
}; double judge(node a ,node b)
{
return (a.x*b.y-a.y*b.x);
} double dist(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
double x1,y1,x2,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
double xx=(x1+x2)/2.0;
double yy=(y1+y2)/2.0;
double dd=dist(x1,y1,x2,y2);
if(fabs(y1-y2)<exb)
{
double yy1=y1+dd*sin(PI/3.0);
double yy2=y1-dd*sin(PI/3.0);
node ab,ac;
ab.x=x2-x1;
ab.y=y2-y1;
ac.x=xx-x1;
ac.y=yy1-y1; if(judge(ab,ac)>)
{
printf("(%.2f,%.2f)\n",xx,yy1);
}
else
{
printf("(%.2f,%.2f)\n",xx,yy2);
}
}
else
{
if(fabs(x1-x2)<exb)
{
double xx1=x1+dd*sin(PI/3.0);
double xx2=x1-dd*sin(PI/3.0);
node ab,ac;
ab.x=x2-x1;
ab.y=y2-y1;
ac.x=xx1-x1;
ac.y=yy-y1;
if(judge(ab,ac)>)
{
printf("(%.2f,%.2f)\n",xx1,yy);
}
else
{
printf("(%.2f,%.2f)\n",xx2,yy);
}
}
else
{
double k=-(x1-x2)/(y1-y2);
double pp=atan(k);
if(pp>PI/2.0)
pp=PI-pp;
k=tan(pp);
double b=yy-(k*xx);
double dd1=dd*sin(PI/3.0);
double xx1=sqrt(dd1*dd1/(k*k+1.0));
double yy1=k*xx1;
double xx2=-sqrt(dd1*dd1/(k*k+1.0));
double yy2=k*xx2;
node ab,ac;
ab.x=x2-x1;
ab.y=y2-y1;
ac.x=xx+xx1-x1;
ac.y=yy+yy1-y1;
if(judge(ab,ac)>)
{
printf("(%.2f,%.2f)\n",xx+xx1,yy+yy1);
}
else
printf("(%.2f,%.2f)\n",xx+xx2,yy+yy2);
}
}
}
return ;
}
四、第B题，听说可以暴力BFS过，我们队用的 强连通分量+缩点重构图+拓扑排序
Problem B:Thrall’s Dream
【题解】:
给定n个点，m条有向边，求解任意两点是否可达。也就是 u->v or v->u 问题
【code】：
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 2005
#define M 10005
using namespace std;
struct edges
{
int u,v,next;
};
edges mye[M];
edges cj[M];
int head[N];
int myhead[N];
int cnt;
int cntcnt;
int cc,gg;
int dfn[N],low[N],Belong[N],Stap[N];
bool ff[N];
int visitNum,ct,Stop;
bool flag[N];
int id[N],od[N];
void addEdge(int x,int y)
{
mye[cnt].u=x;
mye[cnt].v=y;
mye[cnt].next=head[x];
head[x]=cnt++;
} void Add(int x,int y)
{
cj[cntcnt].u=x;
cj[cntcnt].v=y;
cj[cntcnt].next=myhead[x];
myhead[x]=cntcnt++;
} int n,m;
void init()
{
scanf("%d%d",&n,&m);
memset(head,-,sizeof(head));
memset(myhead,-,sizeof(myhead));
cnt=;
cntcnt=;
for(int i=;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
addEdge(x,y);
}
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(Belong,,sizeof(Belong));
memset(Stap,,sizeof(Stap));
memset(flag,false,sizeof(flag));
memset(id,,sizeof(id));
memset(od,,sizeof(od)); } void tarjan(int i)
{
int y;
Stap[++Stop]=i;
flag[i]=true;
dfn[i]=low[i]=++visitNum;
for(int j=head[i];j!=-;j=mye[j].next)
{
y=mye[j].v;
if(!dfn[y])
{
flag[y]=true;
tarjan(y);
low[i]=min(low[i],low[y]);
}
else if(flag[y])
low[i]=min(low[i],dfn[y]);
}
if(low[i]==dfn[i])
{
ct++;
do
{
y=Stap[Stop--];
Belong[y]=ct;
flag[y]=false;
}while(y!=i);
}
} void dfs(int x,int len)
{
if(myhead[x]==- || len>=ct)
{
if(len>gg)
gg=len;
return;
}
for(int i=myhead[x];i!=-;i=cj[i].next)
{
int y=cj[i].v;
if(!ff[y])
{
ff[y]=true;
dfs(y,len+);
ff[y]=false;
}
}
}
void solve()
{
visitNum=ct=Stop=;
for(int i=;i<=n;i++)
{
if(!dfn[i])
tarjan(i);
}
if(ct==)
{
printf("Case %d: Kalimdor is just ahead\n",cc++);
return;
}
for(int i=;i<=n;i++)
{
for(int j=head[i];j!=-;j=mye[j].next)
{
int y=mye[j].v;
int u=Belong[i];
int v=Belong[y];
if(u!=v)
{
od[u]++;
id[v]++;
Add(u,v);
}
}
}
int ans1=,ans2=;
int temp=;
for(int i=;i<=ct;i++)
{
if(od[i]==)
{
ans1++;
}
if(id[i]==)
{
ans2++;
temp=i;
}
}
if(ans1> || ans2>)
{
printf("Case %d: The Burning Shadow consume us all\n",cc++);
return;
}
memset(ff,false,sizeof(ff));
gg=;
dfs(temp,);
if(gg!=ct)
{
printf("Case %d: The Burning Shadow consume us all\n",cc++); }
else
{
printf("Case %d: Kalimdor is just ahead\n",cc++);
}
return;
}
int main()
{
int t;
scanf("%d",&t);
cc=;
while(t--)
{
init();
solve();
}
return ;
}
五、F题
Problem F:Alice and Bob
【题解】：
给出一个多项式：(a0*x^(2^0)+1) * (a1 * x^(2^1)+1)*.......*(an-1 * x^(2^(n-1))+1)
输入P，求X^p 前边的系数。
【code】：
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[];
int main()
{
long long sb,p;
int t;
int n;
int q;
while(scanf("%d",&t)!=EOF)
{
while(t--)
{
scanf("%d",&n);
int i;
for(i=;i<n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&q);
while(q--)
{
scanf("%lld",&p);
long long sb=;
for(i=;i<n&&p!=;i++)
{
if(p%==)
{
sb*=a[i];
sb%=;
}
p/=;
}
if(p==)
printf("%lld\n",sb);
else
printf("0\n");
}
}
}
return ;
}
六：E题
Problem E:Mountain Subsequences
【code】：
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
char sb[];
int dp[];
int ha[];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int i,j,x;
long long max,s;
scanf("%s",sb);
memset(ha,,sizeof(ha));
for(i=;i<n;i++)
{
x=sb[i]-'a';
dp[i]=;
for(j=;j<x;j++)
{
dp[i]+=ha[j];
dp[i]%=;
}
ha[x]+=dp[i]+;
ha[x]%=;
}
/* for(i=n-1;i>=0;i--)
{
printf("%lld ",dp[i]);
}*/
// printf("\n");
max=;
memset(ha,,sizeof(ha));
for(i=n-;i>=;i--)
{
x=sb[i]-'a';
s=;
for(j=;j<x;j++)
{
s+=ha[j];
s%=;
}
ha[x]+=s+;
ha[x]%=;
max+=s*dp[i];
max%=;
// printf("%lld ",s);
}
//printf("\n");
printf("%lld\n",max);
}
return ;
}
七、H题
Problem H:Boring Counting