哇，这道题原来这么写，谢谢！我懂了！

登录
注册
UOJ Logo zhouzixuan的博客
zhouzixuan
日志
关于我
UOJ

搜索
vijos <夜夜的模拟赛之十三岁的梦想> 总结
2015-10-04 22:20:47 By zhouzixuan
【写在前面】：
说实话，打的很不爽
如果说没想出来就算了，被卡精度什么的从来没有想过
暴力写错自己弱...说到底还是自己太渣
如果这样去考noip，就真要跟oi说再见了
貌似很多人看不懂题解？确实，这题解是有些简单了
我建议出题人可以放出数据和标程供打架参考（当然这只是个人口胡辣...
下面进入正题，希望对一些同学有帮助
T1：夜夜的NOIP之旅：

【题目大意】：
求1!+2!+...+n!对m取模后的答案
n<=10^18 m<=1000000
【题目解法】：
很显然如果i>=m，那么i!一定是m的倍数，那么模m就等于0
所以令n=min(n,m)，暴力即可
当然你可以打表找规律，会发现如果某一次得到i!=0那么以后的阶乘模m都等于0
然后复杂度就是O(M)
T2：夜夜的数据加强

【题目大意】：
a[i]=X%i X=(X*A+B)%C
给出n个a[i]和C，求出所有合法的X A B是的可以生成给定的a[i]
C<=400 N<=10^5
【题目解法】：
至今没有看懂题解在说什么...
我们可以考虑乱搞
首先当N<=C是考虑暴力枚举X A B，然后判断复杂度O(C^3*N)勉强卡过
然后我们发现当i>=C时，a[i]=X%i中的%i是废的，因为C<=i，所以X%C的值已经小于i了，所以我们可以发现对于i>C，其实a[i]就是X的值（不需要模i），所以后面的其实是固定的，即我们不用先枚举X，直接枚举A B，然后判断C~N是否符合要求，如果满足再枚举X，判断前C位是否满足。当然这也是变相暴力辣，不过由于在很多情况下某些A B已经不合法了，所以就不用枚举不必要的X了，这样时间会快一点，大概是O(C^2*N)的复杂度
然后还是TLE了一个点...
T3：夜夜的旅游计划

【题目大意】：
给出N个点M条边的无向图
每个点等概率向相邻的点走，每条边有一个时间权值
求1-n的期望时间
【题目解法】：
很裸的高斯消元辣
我们令f[i]表示i-n的期望时间，显然f[n]=0
那么(f[i]+a[i][j])/outo[i]->f[j]，其中outo[i]是i的度，即i有多少个选择
然后由于有环所以就是一堆方程辣，直接暴力高斯消元就好了
然而没这么简单，因为他有自环，比如
2 2
1 1 1
1 2 1
这个数据如果直接做的话outo[1]=3，因为1 1 1这条边会对outo[1]贡献为2，但实际上只有1，因此连边的时候特判一下
然而没这么简单，因为此题卡精度，好吧，把答案加上1e-5
然后没这么简单，最后一个点还是过不去，认了...难道真要写long double
T4：夜夜的花裙子

【题目大意】：

现在给定N根火柴棒，有多少合法的"A-B=C"可以用恰好N根火柴棒摆出来呢？
【题目解法】：
首先N=N-3辣
然后我们考虑dp，首先要明确我们可以枚举所有A+B=C，这与题目是等价的
令f[i][0/1][0/1][0/1]表示用了i根火柴，从低到高考虑，第一个数是否结束，第二个数是否结束，第三个数是否有进位
明确进位顶多进一位，因此最高位只能是0/1
我们考虑如果两个数都结束，显然pass掉
如果两个数都没结束，显然枚举两个数的最高位，然后考虑是否进位
如果两个数一个没结束，我们枚举那个数的最高位，然后考虑进位
答案就是f[n][1][1][0]+f[n][1][1][1]，因为最后最后可以进位也可以不进位
终于写完了，下面放代码

T1
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
long long n,m,ans;
inline long long getint()
{
long long x=0; char c=getchar(); bool flag=false;
while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
if (c=='-') flag=true,c=getchar();
while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
if (flag) return -x; else return x;
}
void init()
{
n=getint(); m=getint(); ans=0;
}
void solve()
{
n=min(n,m); long long base=1;
for (int i=1; i<=n; i++)
{
base=base*(long long)i%m;
ans=(ans+base)%m;
}
printf("%I64d\n",ans);
}
int main()
{
init();
solve();
return 0;
}
T2

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100005;
struct node {int X,A,B;} Ans[N];
int n,fa[N],ans; long long m;
inline long long getint()
{
long long x=0; char c=getchar(); bool flag=false;
while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
if (c=='-') flag=true,c=getchar();
while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
if (flag) return -x; else return x;
}
void init()
{
n=getint()-1; m=getint();
for (int i=1; i<=n; i++) fa[i]=getint();
}
inline bool cmp(const node &a,const node &b)
{
if ((a.X==b.X)&&(a.A==b.A)) return a.B<b.B;
else if (a.X==b.X) return a.A<b.A;
else return a.X<b.X;
}
void solve()
{
for (int i=1; i<=n; i++) if ((fa[i]>=i)||(fa[i]>=m)) {printf("Unsuccessful Hack Attempt\n"); return;}
if (n<=m)
{
for (int X=0; X<m; X++)
for (int A=0; A<m; A++)
for (long long B=0; B<m; B++)
{
long long base=X; bool flag=true;
for (int i=1; i<=n; i++)
{
if (base%i!=fa[i]) {flag=false; break;}
base=(base*A+B)%m;
}
if (flag) Ans[++ans].X=X,Ans[ans].A=A,Ans[ans].B=B;
}
}
else
{
for (int A=0; A<m; A++)
for (long long B=0; B<m; B++)
{
long long base=fa[m]; bool flag=true;
for (int i=m+1; i<=n; i++)
{
base=(base*A+B)%m;
if (base%i!=fa[i]) {flag=false; break;}
}
if (!flag) continue;
for (int X=0; X<m; X++)
{
base=X; flag=true;
for (int i=1; i<=m; i++)
{
if (base%i!=fa[i]) {flag=false; break;}
base=(base*A+B)%m;
}
if (flag) Ans[++ans].X=X,Ans[ans].A=A,Ans[ans].B=B;
}
}
}
if (ans==0) {printf("Unsuccessful Hack Attempt\n"); return;}
sort(Ans+1,Ans+ans+1,cmp);
for (int i=1; i<=ans; i++) printf("%d %d %d\n",Ans[i].X,Ans[i].A,Ans[i].B);
}
int main()
{
init();
solve();
return 0;
}
T3

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=205;
const int M=N*N;
const double zero=1e-9;
struct edge {int x,y;} b[M];
int n,m; double a[N][N],ans[N],into[N],sum[N];
inline long long getint()
{
long long x=0; char c=getchar(); bool flag=false;
while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
if (c=='-') flag=true,c=getchar();
while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
if (flag) return -x; else return x;
}
void init()
{
n=getint(); m=getint();
for (int i=1; i<=n; i++) a[i][i]=1.0;
for (int i=1; i<=m; i++)
{
int x=getint(),y=getint(),z=getint();
into[x]++; if (x!=y) into[y]++;
sum[x]+=z; if (x!=y) sum[y]+=z;
b[i].x=x; b[i].y=y;
}
for (int i=1; i<=m; i++)
{
int x=b[i].x,y=b[i].y;
a[x][y]-=1.0/into[x];
if (x!=y) a[y][x]-=1.0/into[y];
}
for (int i=1; i<=n-1; i++) a[i][n+1]=sum[i]/into[i];
for (int i=1; i<=n+1; i++) a[n][i]=0; a[n][n]=1.0; a[n][n+1]=0;
}
void Debug()
{
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n+1; j++) printf("%.5f ",a[i][j]);
printf("\n");
}
printf("\n");
}
void solve()
{
//Debug();
int line=1;
for (int i=1; i<=n; i++,line++)
{
int maxline=line;
for (int j=line+1; j<=n; j++) if (fabs(a[j][i])>fabs(a[maxline][i])) maxline=j;
for (int j=1; j<=n+1; j++) swap(a[line][j],a[maxline][j]);
if (fabs(a[line][i])<zero) {line--; continue;}
for (int j=i+1; j<=n+1; j++) a[line][j]/=a[line][i]; a[line][i]=1.0;
for (int j=line+1; j<=n; j++)
{
for (int k=i+1; k<=n+1; k++) a[j][k]-=a[line][k]*a[j][i];
a[j][i]=0.0;
}
//Debug();
}
for (int i=n-1; i>=1; i--)
{
double nowans=a[i][n+1];
for (int j=i+1; j<=n; j++) nowans-=a[i][j]*ans[j];
ans[i]=nowans/a[i][i];
}
//Debug();
printf("%.1f\n",ans[1]+1e-5);
}
int main()
{
init();
solve();
return 0;
}
T4

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=505;
const int num[]={6,2,5,5,4,5,6,3,7,6,8,4,7,7,6,7,8,5,9,8};
int n,f[N][2][2][2],cases,casesth,ans; long long maxmod;
inline long long getint()
{
long long x=0; char c=getchar(); bool flag=false;
while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
if (c=='-') flag=true,c=getchar();
while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
if (flag) return -x; else return x;
}
void init()
{
n=getint()-3; maxmod=getint(); casesth++;
memset(f,0,sizeof(f)); f[0][0][0][0]=1;
}
inline void updata(int &a,int b)
{
long long New=((long long)a+(long long)b);
if (New>maxmod) New-=maxmod; a=New;
}
void solve()
{
for (int i=0; i<n; i++)
for (int j=0; j<=1; j++)
for (int k=0; k<=1; k++)
for (int t=0; t<=1; t++)
{
if (f[i][j][k][t]==0) continue;
if ((j==1)&&(k==1)) continue;
if ((j==1)||(k==1))
{
for (int now=0; now<=9; now++)
{
int ii=i+num[now]+num[now+t]-num[t]*t;
int tt=(now+t>=10); if (ii>n) continue;
updata(f[ii][j][k][tt],f[i][j][k][t]);
if (now!=0) updata(f[ii][1][1][tt],f[i][j][k][t]);
}
}
else
{
for (int now1=0; now1<=9; now1++)
for (int now2=0; now2<=9; now2++)
{
int ii=i+num[now1]+num[now2]+num[now1+now2+t]-num[t]*t;
int tt=(now1+now2+t>=10); if (ii>n) continue;
updata(f[ii][j][k][tt],f[i][j][k][t]);
if (now1!=0) updata(f[ii][1][k][tt],f[i][j][k][t]);
if (now2!=0) updata(f[ii][j][1][tt],f[i][j][k][t]);
if ((now1!=0)&&(now2!=0)) updata(f[ii][1][1][tt],f[i][j][k][t]);
}
}
}
ans=0; updata(ans,f[n][1][1][0]); updata(ans,f[n][1][1][1]);
printf("Case #%d: %d\n",casesth,ans%maxmod);
}
int main()
{
cases=getint();
while (cases--)
{
init();
solve();
}
return 0;
}
总结 vijos 好评差评[+2]
评论
avatar
ahdoc好评差评[0]
第三题。既然每一行中每一项都要除以into[x]，为何你不每一项都乘上into[x]?
之后所有系数都是整数了，这样精度就足够了。
对于整系数的方程组，甚至可以用 辗转相减 去消元。
2015-10-05 23:20:54回复
评论回复
zhouzixuan：貌似就是因为一开始乘上into[x]导致过程量爆了double，然后WA剩20了...
2015-10-05 23:39:02回复
zhouzixuan：回复 @zhouzixuan：不介意的话，能不能发一份代码到我的邮箱研究研究
2015-10-05 23:51:06回复
zhouzixuan：不介意的话，能不能发一份代码到我的邮箱研究研究
2015-10-05 23:51:19回复
发表评论
可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

内容
提交
中文 English

Universal Online Judge|鄂ICP备14016048号
Server time: 2015-10-06 17:09:12

快去学markdown orz

TMD麻烦你把全部全选（Ctrl+A）然后再按Tab键再发
不然这个东西看的强迫症好烦
例如
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{

int a,b;
scanf("%d%d",&a,&b);
printf("%d",a+b);
return 0;
}
A+B问题