2012 Multi-University Training Contest 10-白红宇

2012 Multi-University Training Contest 10

阅读量：5878 次

发布时间：2019-06-19

本文共 6931 字，大约阅读时间需要 23 分钟。

官方解题报告：

1001 Number Sequence 容斥定理+组合数

hdu

题意：

给你b1,b2,...bn个数，求存在多少个这样的序列a1,a2,a3....an满足a1*a2*a3*a3...an = b1*b2...*bn; ai>1

思路：

首先多谢日华兄热心的给我讲解，现在算是明白点了吧。a1*a2...*an = sum；我们首先将sum的所有质因子分解出来，然后就是将质因子分配到N个ai里面求有多少种可能。

sum = p1^k1*p2^k2*p3^k3*....*pn^kn

首先我们不考虑ai>1.那么我们的结果就是c(n + k1 - 1,k1 - 1)*c(n + k2 - 1,k2 -1)......*c(n + k3 - 1,k3 - 1); (c(n + ki - 1,ki -1)排列里面的挡板法) 只用组合数就可求得，二这里ai>1 也就是说每个ai必须分配到一个素因子，所以我们这里用容斥定理来求，枚举n到0表示a1 - an要分配素因子的位数，当有n位时时我们要求的解，可是这里用上述办法求的话就包含了ai = 1的情况情况，所以我们要去掉多加的。就用容斥定理；

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define ll __int64#define inf 0x7f7f7f7f#define MOD 1000000007ll#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 1000007#define N 1000005#define M 200007using namespace std;int prime[N],idx;int cnt[N],num[N],m;int n;bool hash[maxn];ll c[90][90];void init(){ int i,j; CL(c,0); for (i = 0; i < 90; ++i)//求组合数 c[i][i] = c[i][0] = 1; for (i = 1; i < 90; ++i) { for (j = 1; j < i; ++j) { c[i][j] = (c[i - 1][j] + c[i - 1][j - 1])%MOD; } } //筛选素数 CL(hash,false); idx = 0; for (i = 2; i*i < maxn; ++i) { if (!hash[i]) { for (j = i + i; j < maxn; j += i) { hash[j] = true; } } } for (i = 2; i < maxn; ++i) { if (!hash[i]) prime[idx++] = i; }}void gao(int a)//枚举出sum的质因子即质因子个数{ int i; for (i = 0; i < idx && a != 1; ++i) { while (a % prime[i] == 0) { cnt[i]++; a /= prime[i]; } }}ll cal(int cc){ ll sum = c[n][cc];//首先从n个位置去cc个分配素因子 for (int i = 0; i < m; ++i) { sum *= c[cc + num[i] - 1][cc - 1];//将每个素因子分配 if (sum >= MOD) sum %= MOD; } return sum;}int main(){ //freopen("din.txt","r",stdin); int i,a; init(); while (~scanf("%d",&n)) { CL(cnt,0); for (i = 0; i < n; ++i) { scanf("%d",&a); gao(a); } m = 0; for (i = 0; i < idx; ++i) { if (cnt[i]) num[m++] = cnt[i]; } ll ans = 0; int flag = 1; for (i = n; i >= 0; --i) { //ans += flag*cal(i); if(flag == -1) ans -= cal(i);//容斥处理 else ans += cal(i); ans = (ans%MOD + MOD)%MOD; flag *= -1; } printf("%I64d\n",ans); } return 0;}

1004 hdu 4393 Throw nails

题意：

n名队员参加自行车比赛，在第一秒内每个人都可以行走fi的距离，随后每个人都以各自的速度vi匀速往前前进，在每一秒LZ会扔出一个钉子，是走在最前边的选手爆胎淘汰，问输出选手们被淘汰的顺序，ps：如果行走的距离相同即两人在都以为置时，优先选择标号小的爆胎。

思路：

比赛时，只想到了O(N^2)的解法，这样肯定会超时，想了很长时间还是没有想到哎思路啊.这里关键在于速度速度最大才能达到100我们只需要开一个优先队列数组q[1..100]每次在这些优先队列里面取出f最大的，因为属于同样队列的速度肯定相同所以F大的肯定排在前边，然后就是取最值的问题了，时间复杂度为O（N*100）.这里真的很巧妙就是没想出来。。

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define ll long long#define inf 0x7f7f7f7f#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 50004#define N 107#define M 200007using namespace std;struct node{ int f,v; int pos; friend bool operator < (const node &a,const node &b) { if (a.f != b.f) return a.f < b.f; else return a.pos > b.pos; }}tp;priority_queue
                
                 q[N];int main(){ //freopen("din.txt","r",stdin); int t,cas = 1; int n,i,j; scanf("%d",&t); while (t--) { printf("Case #%d:\n",cas++); scanf("%d",&n); for (i = 1; i <= 100; ++i) { while (!q[i].empty()) q[i].pop(); } for (i = 1; i <= n; ++i) { scanf("%d%d",&tp.f,&tp.v); tp.pos = i; q[tp.v].push(tp); } int tmp1,tmp2; int MIN; for (i = 0; i < n; ++i) { MIN = -inf; for (j = 1; j <= 100; ++j) { if (!q[j].empty()) { tp = q[j].top(); if (MIN < i*j + tp.f) { MIN = i*j + tp.f; tmp1 = j; tmp2 = tp.pos; } else if (MIN == i*j + tp.f && tmp2 > tp.pos)//注意这里距离相同时，取pos最小的 { tmp1 = j; tmp2 = tp.pos; } } } q[tmp1].pop(); if (i != n - 1) printf("%d ",tmp2); else printf("%d\n",tmp2); } } return 0;}

1005 hdu 4394

题意：

M²%10^x=N (x=0,1,2,3....) 给你N求最小的非负整数M。。。

思路：

这里N到了10^9次方，计算几个式子可以发现，对于b为数的平方，他的平方后的数的后b为也就由它确定了，我们由N去枚举找M，最高只要枚举到第九位也就可以了。

23*23 = 329 123*123 = 15129 3123*3123 = 9753129 观察他们就会发现。

View Code

#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)using namespace std;ll len[] = {
    1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000ll};int ans;int getlen(int x){    int i;    for (i = 0; ; ++i)    if (len[i] > x) return i;}void dfs(int x,int l,int xx,int maxL){    int i;    if (l == maxL)    {        if (ans > x) ans = x;        return ;    }    for (i = 0; i < 10; ++i)    {        ll tmp = len[l]*i + x;        if ((tmp*tmp)%len[l + 1] == xx%len[l + 1])//满足继续枚举        dfs(tmp,l + 1,xx,maxL);    }}int main(){    int t,n;    scanf("%d",&t);    while (t--)    {        ans = inf;        scanf("%d",&n);        int maxL = getlen(n);        dfs(0,0,n,maxL);        if (ans == inf) printf("None\n");        else printf("%d\n",ans);    }}

1007 hdu 4396 More lumber is required

思路：二维SPFA:

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define maxn 50004#define N 5007#define M 200007#define K 507#define ll long long#define inf 0x7f7f7f7f#define MOD 100000007#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)using namespace std;int dis[N][55];struct node{ int v; int w; int next;}g[M];struct mode{ int pos; int k;}tp;int head[N],ct;int n,m,S,T,ki;bool vt[N][55];void init(){ ct = 0; CL(head,-1); CL(vt,false);}void add(int u,int v,int w){ g[ct].v = v; g[ct].w = w; g[ct].next = head[u]; head[u] = ct++;}void spfa(){ int i,j; for (i = 0; i <= n; ++i) { for (j = 0; j <= ki; ++j) { dis[i][j] = inf; } } dis[S][0] = 0; tp.k = 0; tp.pos = S; queue
                
                 q; q.push(tp); vt[S][0] = true; while (!q.empty()) { mode cur = q.front(); q.pop(); int u = cur.pos; vt[u][cur.k] = false; for (i = head[u]; i != -1; i = g[i].next) { int v = g[i].v; int k = cur.k; int w = g[i].w; int tmp = k + 1; if (tmp > ki) tmp = ki; if(dis[v][tmp] > dis[u][k] + w) { dis[v][tmp] = dis[u][k] + w; if (!vt[v][tmp]) { vt[v][tmp] = true; tp.k = tmp; tp.pos = v; q.push(tp); } } } }}int main(){ //freopen("din.txt","r",stdin); int i,u,v,w; while (~scanf("%d%d",&n,&m)) { init(); for (i = 0; i < m; ++i) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } scanf("%d%d%d",&S,&T,&ki); if (ki%10 == 0) ki /= 10; else ki = ki/10 + 1; spfa(); if (dis[T][ki] == inf) puts("-1"); else printf("%d\n",dis[T][ki]); } return 0;}

转载地址：http://vzcix.baihongyu.com/

你可能感兴趣的文章