1.MM的数学作业
【题目大意】
今天，MM在上数学课，数学课的主题是函数。讲完以后老师留了一个家庭作业，让同学们回家思考。题目如下：
定义一个函数，F(x)表示x转成二进制后，二进制中“1”的个数。比如F(279)=5,因为(279)10=( 100010111)2，其中有5个“1”。
现在有一个序列，已知X0 = 0，Xi=F(Xi-1)*A+B。老师的问题是求这个序列第K个是多少。
【输入格式】
输入3个整数，A，B，K，定义如上所述。
【输出格式】
输出只有一行，序列的第K个的值。
【样例输入】
1
7
2
【样例输出】
10
【数据范围】
0<=A,B<= 1,000,000
30% 数据1<=K<=1,000,000
100% 数据1<=K<=1,000,000,000
题解：
考虑到f函数的值非常少，而且这个数的大小只和f有关，所以
可以记录一下循环节，节约时间
代码：
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int a[],A,B,n;
int f(int x)
{
int num=;
while (x)
{
if (x%)num++;
x/=;
}
return num;
}
int main()
{
freopen("homework.in","r",stdin);
freopen("homework.out","w",stdout);
scanf("%d%d%d",&A,&B,&n);
int now=;
for (int i=;i<=n;i++)
{
now=f(now)*A+B;
if (a[now])
{
int p=now;
for (int j=;j<=(n-i)%(i-a[now]);j++)p=f(p)*A+B;
printf("%d\n",p);
return ;
}
a[now]=i;
}
printf("%d\n",now);
}
2.香蕉树
【题目大意】
MM家的后院种了一棵香蕉树，由于树上的香蕉过多，导致整棵树不漂亮了，所以她需要通过摘香蕉来修整这棵树。但是，如果她摘了过多的香蕉就会使，整棵树太稀疏，不够饱满，所以她最多只能摘M个香蕉。香蕉是长在树枝上的，切每条树枝上至少保留Ci个。MM希望摘完香蕉后，使得根到最沉的叶子最轻。轻重的衡量就是，根到某个叶子路径上还剩下的香蕉总数。树根为1号点。
【输入格式】
第一行两个整数N,M，表示树的节点个数，她最多能摘的香蕉个数。
接下来N-1行，每行四个整数Xi，Yi，Pi，Ci，表示第i个树枝连接的两个端点 ，以及这条树枝上的香蕉总数和至少应该保留的香蕉数。
【输出格式】
输出只有一行，表示根到最沉的叶子最轻是多少。
【样例输入】
3 200
1 2 200 100
2 3 450 250
【样例输出】
450
【数据范围】
1<=N<=100000
0<=M<=1000000
0<=Pi,Ci<=10000
题解：
二分答案，贪心。
首先肯定是能往上就往上
而且叶子节点最后的重量肯定是最大的
那么将叶子节点的重量排序，然后看看它的祖先是不是被之前覆盖过
覆盖过就可以节约了
代码：
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int n,m,x,y,u,v,ne[N],fi[N],zz[N],sl[N],ql[N],can[N],zhong[N];
int fa[N],num,ye[N],flag[N],f[N][];
void jb(int x,int y,int u,int v)
{
ne[++num]=fi[x];
fi[x]=num;
zz[num]=y;
sl[num]=u;
ql[num]=v;
}
void dfs(int x,int y,int z,int s)
{
fa[x]=y;
zhong[x]=z;
can[x]=s;
for (int i=fi[x];i;i=ne[i])
if (y!=zz[i])dfs(zz[i],x,z+sl[i],s+ql[i]);
if (!ne[fi[x]]&&zz[fi[x]]==y)ye[++num]=x;
}
int find(int x)
{
for (int j=;j>=;j--)
if (!flag[f[x][j]])x=f[x][j];
if (!flag[x])x=f[x][];
return x;
}
bool cmp(int x,int y)
{
return zhong[x]>zhong[y];
}
int pd(int x)
{
int p=;
memset(flag,,sizeof flag);
flag[]=flag[]=;
for (int i=;i<=num;i++)
{
if (zhong[ye[i]]<=x)return ;
if (zhong[ye[i]]-can[ye[i]]>x)return ;
int l=find(ye[i]);
if (can[l]<zhong[ye[i]]-x)p=p-can[l]+zhong[ye[i]]-x;
if (p>m)return ;
l=ye[i];
while (l!=)
{
if (flag[l])break;
flag[l]=;
l=fa[l];
}
}
return ;
}
int main()
{
freopen("banana.in","r",stdin);
freopen("banana.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=;i<n;i++)
{
scanf("%d%d%d%d",&x,&y,&u,&v);
jb(x,y,u,u-v);
jb(y,x,u,u-v);
}
num=;
dfs(,,,);
sort(ye+,ye+num+,cmp);
for (int i=;i<=n;i++)f[i][]=fa[i];
for (int i=;i<;i++)
for (int j=;j<=n;j++)
f[j][i]=f[f[j][i-]][i-];
int l=,r=1e9;
while (l<r)
{
int mid=(l+r)/;
if (!pd(mid))l=mid+;
else r=mid;
}
printf("%d",l);
}
3.迷路
【问题描述】
Amber在有向图中迷路了。
该有向图有 N 个节点，Amber从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。
现在给出该有向图，你能告诉Amber总共有多少种不同的路径吗？
注意：Amber不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。
【输入格式】
输入文件road.in第一行包含两个整数，N T。
接下来有 N 行，每行一个长度为 N 的字符串。
第i行第j列为'0'表示从节点i到节点j没有边。
为'1'到'9'表示从节点i到节点j需要耗费的时间。
【输出格式】
输出文件road.out包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以2009的余数。
【输入样例一】
2 2
11
00
【输出样例一】
1
【样例解释一】
0->0->1
【输入样例二】
5 30
12045
07105
47805
12024
12345
【输出样例二】
852
【数据规模和约定】
30%的数据，满足 2 <= N <= 5 ； 1 <= T <= 30 。
100%的数据，满足 2 <= N <= 10 ； 1 <= T <= 1000000000 。
题解：
看到那么大的T，一看就是矩阵
构造（9*n）*（9*n）的矩阵
快速幂T次
矩阵构造看代码。。。
代码：
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
const int M=;
char s[N];
int T,a[N][N],n;
struct zz
{
int a[N*N][N*N];
}x;
zz cf(zz x,zz y)
{
zz z;
memset(z.a,,sizeof z.a);
for (int i=;i<=*n;i++)
for (int j=;j<=*n;j++)
for (int k=;k<=*n;k++)
(z.a[i][j]+=(x.a[i][k]*y.a[k][j]))%=M;
return z;
}
void gouzao()
{
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
if (a[i][j]!=-)x.a[i][(a[i][j]-)*n+j]=;
for (int i=n+;i<=*n;i++)
x.a[i][i-n]=;
}
void ksm(int k)
{
zz y;
memset(y.a,,sizeof y.a);
for (int i=;i<=*n;i++)y.a[i][i]=;
for (;k;k/=,x=cf(x,x))
if (k%)y=cf(y,x);
x=y;
}
int main()
{
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
scanf("%d%d",&n,&T);
for (int i=;i<=n;i++)
{
scanf("%s",s+);
for (int j=;j<=n;j++)
if (s[j]!='')
a[i][j]=s[j]-;
else a[i][j]=-;
}
gouzao();
ksm(T);
printf("%d",x.a[][n]);
}