8.22 NOIP 模拟题
编译命令 g++ -o * *.cpp
gcc -o * *.c
fpc *.pas
编译器版本 g++/gcc 4.9.
fpc 2.6.
评测环境 位 Linux, .3GHZ CPU
评测软件 Lemon
评测方式 忽略行末空格和回车
特别注意：c/c++ 选手使用 printf 输出 位整数请使用%lld
注意事项
A 债务
文件名 输入文件 输出文件 时空限制
debt.pas/c/cpp debt.in debt.out 1s 128MB
题目描述
小 G 有一群好朋友，他们经常互相借钱。假如说有三个好朋友 A，B，C。A
欠 B 20 元，B 欠 C 20 元，总债务规模为 20+20=40 元。小 G 是个追求简约的人，
他觉得这样的债务太繁杂了。他认为，上面的债务可以完全等价为 A 欠 C 20 元，
B 既不欠别人，别人也不欠他。这样总债务规模就压缩到了 20 元。
现在给定 n 个人和 m 条债务关系。小 G 想找到一种新的债务方案，使得每个
人欠钱的总数不变，或被欠钱的总数不变（但是对象可以发生变化） ，并且使得总
债务规模最小。
输入格式
输入文件第一行两个数字 n,m，含义如题目所述。
接下来 m 行，每行三个数字 a i ,b i ,c i ，表示 a i 欠 b i 的钱数为 c i 。
注意，数据中关于某两个人 A 和 B 的债务信息可能出现多次，将其累加即可。
如”A 欠 B 20 元”、”A 欠 B 30 元”、”B 欠 A 10 元”，其等价为”A 欠 B 40 元”。
输出格式
输出文件共一行，输出最小的总债务规模。
样例输入 1
5 3
1 2 10
2 3 1
2 4 1
2
样例输出 1
10
样例输入 2
4 3
1 2 1
2 3 1
3 1 1
样例输出 2
0
数据范围
对于 30% 的数据，1 ≤ n ≤ 10，1 ≤ m ≤ 10。
对于 60% 的数据，1 ≤ n ≤ 100, 1 ≤ m ≤ 10 4 。
对于 80% 的数据，1 ≤ n ≤ 10 4 ，1 ≤ m ≤ 10 4 。
对于 100% 的数据，1 ≤ n ≤ 10 6 ，1 ≤ m ≤ 10 6 。
对于所有的数据，保证 1 ≤ a i ,b i ≤ n,0 < c i ≤ 100。
#include<iostream>
#include<cstdio>
#include<cstring> #define N 1000007 using namespace std;
int val[N];
int x,y,z,n,m,ans; inline int read()
{
int x=,f=;char c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} int main()
{
freopen("debt.in","r",stdin);
freopen("debt.out","w",stdout);
n=read(),m=read();
for(int i=;i<=m;i++)
{
x=read();y=read();z=read();
val[y]+=z;val[x]-=z;
}
for(int i=;i<=n;i++)
if(val[i]<) ans+=-val[i];
printf("%d\n",ans);
fclose(stdin);fclose(stdout);
return ;
}
B 排列
文件名 输入文件 输出文件 时空限制
perm.pas/c/cpp perm.in perm.out 1s 128MB
题目描述
小 G 喜欢玩排列。现在他手头有两个 n 的排列。n 的排列是由 0,1,2,...,n−1
这 n 的数字组成的。对于一个排列 p，Order(p) 表示 p 是字典序第 Order(p) 小的
排列（从 0 开始计数） 。对于小于 n! 的非负数 x，Perm(x) 表示字典序第 x 小的
排列。
现在，小 G 想求一下他手头两个排列的和。两个排列 p 和 q 的和为 sum =
Perm((Order(p) + Order(q))%n!)。
输入格式
输入文件第一行一个数字 n，含义如题。
接下来两行，每行 n 个用空格隔开的数字，表示小 G 手头的两个排列。
输出格式
输出一行 n 个数字，用空格隔开，表示两个排列的和。
样例输入 1
2
0 1
1 0
样例输出 1
1 0
4
样例输入 2
3
1 2 0
2 1 0
样例输出 2
1 0 2
数据范围
1、2、3、4 测试点，1 ≤ n ≤ 10。
5、6、7 测试点，1 ≤ n ≤ 5000，保证第二个排列的 Order ≤ 10 5 。
8、9、10 测试点，1 ≤ n ≤ 5000。
/*
可以看出Order perm 互为反函数
康托展开：
一个序列的排名(从0开始计数) = Rank[n]*(n-1)!+Rank[n-1]*(n-2)!+….
其中Rank[n]表示n位置上的数字在a[1]~a[n]中的排行，并且从0开始计数。 先求出两个序列的康托展开式，相加
但是显然阶乘爆掉
于是我们只加rank数组
如果rank[i]这一位大于等于i，就按i进制进位
证明：
……rank[i] * (i - 1) ! + rank[i + 1] * i !……
若rank[i] > i 那么可分解为
rank[i]%i * (i - 1)! + rank[i]/i * i! + rank[i + 1]*i!
所以进位显然
mod n!的话，只需要忽略rank[i + 1]即可
可以从n往前找，p从-1向上累计，遇到没有用过的p就标记为用过，同时rank[n]--
因为num[i + 1..n]求出后能得知num[i]能选哪一些数 也就是num[1...i]有哪一些数 从小到大枚举到对应排名即可
*/
#include<iostream>
#include<cstdio>
#include<cstring> #define N 6010
#define inf 0x3f3f3f3f using namespace std;
int num1[N],num2[N],rank[N],rank2[N];
int n,b[N]; int main()
{
freopen("perm.in","r",stdin);
freopen("perm.out","w",stdout);
scanf("%d",&n);
for(int i=n;i>;i--) scanf("%d",&num1[i]);
for(int i=n;i>;i--) scanf("%d",&num2[i]);
int p;
for(int i=;i<=n;i++)
{
p=;
for(int j=;j<i;j++) if(num1[j]<num1[i]) ++p;
rank[i]+=p;
p=;
for(int j=;j<i;j++) if(num2[j]<num2[i]) ++p;
rank2[i]+=p;
rank[i]+=rank2[i];
rank[i+]+=rank[i]/i;
rank[i]%=i;
} rank[n]%=n;
for(int i=n;i>=;i--)
{
p=-;
while(rank[i]>=)
{
++p;
if(!b[p]) --rank[i];
}b[p]=;
printf("%d ",p);
}return ;
}
C 剪树枝
文件名 输入文件 输出文件 时空限制
tree.pas/c/cpp tree.in tree.out 1s 128MB
题目描述
rzyz 有一棵苹果树。苹果树有 n 个节点（也就是苹果） ，n − 1 条边（也就是
树枝） 。调皮的小 G 爬到苹果树上。他发现这棵苹果树上的苹果有两种：一种是黑
苹果，一种是红苹果。小 G 想要剪掉 k 条树枝，将整棵树分成 k + 1 个部分。他
想要保证每个部分里面有且仅有一个黑苹果。请问他一共有多少种剪树枝的方案？
输入格式
第一行一个数字 n，表示苹果树的节点（苹果）个数。
第二行一共 n − 1 个数字 p 0 ,p 1 ,p 2 ,p 3 ,...,p n−2 ，p i 表示第 i + 1 个节点和 p i 节
点之间有一条边。注意，点的编号是 0 到 n − 1。
第三行一共 n 个数字 x 0 ,x 1 ,x 2 ,x 3 ,...,x n−1 。如果 x i 是 1，表示 i 号节点是黑
苹果；如果 x i 是 0，表示 i 号节点是红苹果。
输出格式
输出一个数字，表示总方案数。 答案对 10 9 + 7 取模。
样例输入 1
3
0 0
0 1 1
样例输出 1
2
6
样例输入 2
6
0 1 1 0 4
1 1 0 0 1 0
样例输出 2
1
样例输入 3
10
0 1 2 1 4 4 4 0 8
0 0 0 1 0 1 1 0 0 1
样例输出 3
27
数据范围
对于 30% 的数据，1 ≤ n ≤ 10。
对于 60% 的数据，1 ≤ n ≤ 100。
对于 80% 的数据，1 ≤ n ≤ 1000。
对于 100% 的数据，1 ≤ n ≤ 10 5 。
对于所有数据点，都有 0 ≤ p i ≤ n − 1，x i = 0 或 x i = 1。
特别地，60% 中、80% 中、100% 中各有一个点，树的形态是一条链。
/*
一道比价杂乱的树形dp，但貌似很经典。
f[i][0][0]代表第i个点是否砍掉，以它为根的子树中有没有黑点。
转移的时候判断当前点是黑是红
黑点：f[u][1][0]=0;f[u][0][0]=0;（这两种情况不成立，不管砍不砍以它为根的子树中一定有黑点）
f[u][1][1]=f[v][1][1]+f[v][0][0]的乘积（它被砍了子树中只能有它一个黑点，
所以儿子中要么没有黑点[0][0]要么有黑点被砍了[1][1]）
f[u][0][1]不知道暂时赋值为f[u][1][1]
白点：f[u][1][0]这种情况对答案没有贡献设为0，因为它为白点子树仍为白点都不能割；
f[u][0][0]=f[v][1][1]+f[v][0][0]的乘积
（它的子树中没有黑点，儿子中要么没有黑点[0][0]要么有黑点被砍了[1][1]）
f[u][1][1]=∑f[x][0][1]*（f[v][1][1]+f[v][0][0]），它为白以它为根的子树中有且只有一个黑点，
则只有一个黑点儿子不被砍，其余儿子中要么没有黑点[0][0]要么有黑点被砍了[1][1]
最后答案为f[0][0][1]
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib> #define mod 1000000007
#define N 100005 using namespace std;
long long f[N][][];
int tot,n;
int head[N],col[N],son[N];
struct node
{
int to,next;
}e[N<<]; inline int read()
{
int x=,f=;char c=getchar();
while(c>''||c<''){if(c=='=')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} inline void add(int u,int v)
{
e[++tot].to=v;e[tot].next=head[u];head[u]=tot;
} void dfs(int u,int v)
{
for(int i=head[u];~i;i=e[i].next)
{
if(e[i].to==v) continue;
dfs(e[i].to,u);
son[u]=;
}
} void dp(int u,int v)
{
if(!son[u])
{
if(col[u])
{
f[u][][]=;f[u][][]=;
f[u][][]=;f[u][][]=;
}
else
{
f[u][][]=;f[u][][]=;
f[u][][]=;f[u][][]=;
}return;
}
for(int i=head[u];~i;i=e[i].next)
{
if(e[i].to==v) continue;
dp(e[i].to,u);
}
if(col[u])
{
f[u][][]=;f[u][][]=;
long long sum=;
for(int i=head[u];~i;i=e[i].next)
{
int t=e[i].to;
if(t==v)continue;
sum=sum*(f[t][][]+f[t][][])%mod;
}
f[u][][]+=sum;f[u][][]+=sum;
}
else
{
f[u][][]=;
long long sum=;
for(int i=head[u];~i;i=e[i].next)
{
int t=e[i].to;
if(t==v)continue;
sum=sum*(f[t][][]+f[t][][])%mod;
}
f[u][][]+=sum;
long long ans=;sum=;
for(int i=head[u];~i;i=e[i].next,sum=)
{
if(e[i].to==v)continue;
int tmp=f[e[i].to][][];
if(!tmp)continue;
for(int j=head[u];~j;j=e[j].next)
{
int t=e[j].to;
if(t==v || j==i) continue;
sum=sum*(f[t][][]+f[t][][])%mod;
}
ans=(ans+tmp*sum)%mod;
}
f[u][][]=ans%mod;f[u][][]=ans%mod;
}
} int main()
{
// freopen("tree.in","r",stdin);
// freopen("tree.out","w",stdout);
/* 手动扩栈
int size = 256 << 16; // 256MB
char *p = (char*)malloc(size) + size;
__asm__("movl %0, %%esp\n" :: "r"(p));
*/
memset(head,-,sizeof head);
n=read();int x;
for(int i=;i<n-;i++)
{
x=read();
add(x,i+);add(i+,x);
}
for(int i=;i<n;i++) col[i]=read();
dfs(,-);dp(,-);
cout<<f[][][]%mod;
return ;
}
++
T2没想出来。
嗯没错，T3暴力挂了，水了30分链一分没得，这让大数据结构如此擅长水链分的我特别桑心了，，，，，，
唉，愁得我......T3还是没耐心写暴力吧(想到80分暴力貌似不对，写了也不一定调出来)，还是太弱了，myj大佬都开始挨个刷bzoj了.....不怂就是干！晚上吧全排列写5边！！！(被stl坑了一把)。
T3正解一晚上没懂，上午半上午才又找了一个看懂了，唉......
我就不信这个邪......
conclusion