ITdaan
搜索本文相关内容

2016 Multi-University Training Contest 6题解报告

本文转载自  queuelovestack  查看原文  2016/08/04  1083    博弈/ test/ 快速幂/ 题解/ 组合数/ training/ ACM/ 乘法逆元           

此文章可以使用目录功能哟↑(点击上方[+])

膜拜柱爷,膜拜卿学姐,膜拜廖大爷...

2016 Multi-University Training Contest 6官方题解

链接→2016 Multi-University Training Contest 6

 Problem 1001 A Boring Question

Accept: 0    Submit: 0
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit : 65536/65536 K (Java/Others)

 Problem Description

There are an equation.


We define that . And while.

You have to get the answer for each and that given to you.

For example,if n=1,m=3,

When ;

When;

When;

When;

When;

When;

When;

When.

So the answer is 4.

 Input

The first line of the input contains the only integer T,(1≤T≤10000)

Then lines follow,the i-th line contains two integers n,m,(0≤n≤10^9,2≤m≤10^9)

 Output

For each n and m,output the answer in a single line.

 Sample Input

2
1 2
2 3

 Sample Output

3
13

 Problem Idea

解题思路:

【题意】
给定n,m,求


【类型】
快速幂+乘法逆元+规律 or 公式推导

【分析】
说实话,本着打破沙锅璺到底的原则,着实应该把公式好好推一推

然而,实力羸弱的博主,实在是推不出来,官方题解的推导过程又太过跳跃

没办法,只能通过打表找规律了

在打表之前,我们先了解一波这个公式


观察上式,有没有觉得异常熟悉,没错,其实就是组合公式


然后题目又说当时,

所以我们可将求解的公式转化一波



打表程序如下:

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-8
#define LL long long
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 6;
const int M = 16;
const int inf = 1000000007;
const int mod = 110119;
int dp[N][N];
int c[N][N];
int k[N];
int n,m;
void dfs(int pos,int down)
{
    if(pos>m)
    {
        int q=1;
        for(int i=1;i<m;i++)
            q*=c[k[i+1]][k[i]];
        dp[n][m]+=q;
        return;
    }
    for(int i=down;i<=n;i++)
    {
        k[pos]=i;
        dfs(pos+1,i);
    }
}
int main()
{
    int i,j;
    c[0][0]=1;
    for(i=1;i<N;i++)
    {
        c[i][0]=c[i][i]=1;
        for(j=1;j<i;j++)
            c[i][j]=c[i-1][j-1]+c[i-1][j];
    }
    for(n=0;n<N;n++)
        for(m=2;m<N;m++)
            dfs(1,0);
    for(n=0;n<N;n++)
    {
        for(m=0;m<N;m++)
            printf("%8d",dp[n][m]);
        puts("");
    }
    return 0;
}

可得数据表:

0     0     1     1     1     1
0     0     3     4     5     6
0     0     7    13    21    31
0     0    15    40    85   156
0     0    31   121   341   781
0     0    63   364  1365  3906

由上述数据,猜测公式


因为n比较大,所以可以采取快速幂+乘法逆元的方法求解

【时间复杂度&&优化】
O(logn)

题目链接→HDU 5793 A Boring Question

 Source Code

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-8
#define LL long long
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 10;
const int M = 16;
const int inf = 1000000007;
const int mod = 1000000007;
__int64 Quick_Mod(int a,int b)//快速幂
{
    __int64 res = 1,term = a % mod;
    while(b)
    {
        if(b & 1) res = (res * term) % mod;
        term = (term * term) % mod;
        b >>= 1;
    }
    return res;
}
int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        printf("%I64d\n",((Quick_Mod(m,n+1)-1+mod)*Quick_Mod(m-1,mod-2))%mod);
    }
    return 0;
}

 Problem 1002 A Simple Chess

Accept: 0    Submit: 0
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit : 65536/65536 K (Java/Others)

 Problem Description

There is a n×m board, a chess want to go to the position (n,m) from the position (1,1).

The chess is able to go to position (x2,y2) from the position (x1,y1), only and if only x1,y1,x2,y2 is satisfied that, x2>x1, y2>y1.

Unfortunately, there are some obstacles on the board. And the chess never can stay on the grid where has a obstacle.

I want you to tell me, There are how may ways the chess can achieve its goal.

 Input

The input consists of multiple test cases.

For each test case:

The first line is three integers, n,m,r,(1≤n,m≤10^18,0≤r≤100), denoting the height of the board, the weight of the board, and the number of the obstacles on the board.

Then follow r lines, each lines have two integers, x,y(1≤x≤n,1≤y≤m), denoting the position of the obstacles. please note there aren't never a obstacles at position (1,1).

 Output

For each test case,output a single line "Case #x: y", where x is the case number, starting from 1. And y is the answer after module 110119.

 Sample Input

1 1 0
3 3 0
4 4 1
2 1
4 4 1
3 2
7 10 2
1 2
7 1

 Sample Output

Case #1: 1
Case #2: 0
Case #3: 2
Case #4: 1
Case #5: 5

 Problem Idea

解题思路:

【题意】
一个n*m的棋盘,一个棋子想从(1,1)走到(n,n)

棋子每步可从(x1,y1)到达(x2,y2),当且仅当

另外,棋盘上有r处障碍,棋子无法到达障碍处

问棋子从(1,1)到达(n,m)有多少种走法


【类型】
lucas定理求组合数+dp

【分析】
首先我们要确定棋子是怎么走的

由式子,x2>x1,y2>y1可知

方程有两组解,x2=x1+2,y2=y1+1或x2=x1+1,y2=y1+2

即当棋子处于位置(x,y)时,它可以一步到达①(x+1,y+2)或②(x+2,y+1)处

那我们不妨求解一下通式,假设从位置(x1,y1)到(x2,y2)需要①走法走k1步,②走法走k2步

那么可得方程组


求解得


然后,因为从(x1,y1)到(x2,y2)在无障碍的情况下与走法先后无关,只与k1,k2有关

所以从(x1,y1)到(x2,y2)的方法数为或

组合数?还是大组合数,显然,lucas派上用场了

那么,障碍怎么办?比赛的时候想到了容斥,但感觉若r个障碍都可达的话,容斥复杂度还是蛮高的,但是官方题解给的就是容斥

算了,我们还是管自己的方法来解,dp

令dp[i]表示到第i个障碍前面不经过任何障碍的方案数
然后转移的时候算出(1,1)到第i个障碍的方案数
枚举j从1到i-1所有的障碍,减去从(1,1)出发只经由障碍j再到障碍i的方案数
最后将重点(n,m)作为第r+1个障碍
ans就是dp[r+1]
这样复杂度是O(r^2)的

【时间复杂度&&优化】
O(r^2)

题目链接→HDU 5794 A Simple Chess

 Source Code

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-8
#define LL long long
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 105;
const int M = 16;
const int inf = 1000000007;
const int mod = 110119;
struct node
{
    __int64 x,y;
}s[N];
bool cmp(node x,node y)
{
    if(x.x!=y.x)
        return x.x<y.x;
    return x.y<y.y;
}
__int64 fac[mod+100],dp[N];
void init()//阶乘预处理
{
    fac[0]=1;
    for(int i=1;i<=mod;i++)
        fac[i]=i*fac[i-1]%mod;
}
__int64 pow_mod(__int64 a,__int64 b)
{
    __int64 s=1;
    a=a%mod;
    while(b)
    {
        if(b&1)
            s=s*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return s;
}
__int64 C(int n,int m)
{
    if(m>n)
        return 0;
    return  fac[n]*pow_mod(fac[m]*fac[n-m]%mod,mod-2)%mod;
}
__int64 Lucas(__int64 n,__int64 m)
{
    if(m==0)
        return 1;
    return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}
__int64 cal(int i,int j)
{
    __int64 r=s[j].x-s[i].x,c=s[j].y-s[i].y;
    __int64 k1=2*r-c,k2=2*c-r;
    if(k1<0||k2<0||k1%3||k2%3)
        return 0;
    k1/=3;k2/=3;
    return Lucas(k1+k2,k1);
}
bool judge(int i,int j)
{
    if(s[i].x<s[j].x||s[i].y<s[j].y)
        return false;
    return true;
}
int main()
{
    __int64 n,m;
    int r,i,j,p=1;
    init();
    while(~scanf("%I64d%I64d%d",&n,&m,&r))
    {
        for(i=1;i<=r;i++)
            scanf("%I64d%I64d",&s[i].x,&s[i].y);
        s[0].x=1;s[0].y=1;
        s[++r].x=n;s[r].y=m;
        sort(s+1,s+r+1,cmp);
        for(i=1;i<=r;i++)
        {
            dp[i]=cal(0,i);
            for(j=1;j<i;j++)
                if(judge(i,j))
                    dp[i]=(dp[i]+mod-cal(j,i)*dp[j]%mod)%mod;
        }
        printf("Case #%d: %I64d\n",p++,dp[r]);
    }
    return 0;
}

 Problem 1003 A Simple Nim

Accept: 0    Submit: 0
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit : 65536/65536 K (Java/Others)

 Problem Description

Two players take turns picking candies from n heaps,the player who picks the last one will win the game.On each turn they can pick any number of candies which come from the same heap(picking no candy is not allowed).To make the game more interesting,players can separate one heap into three smaller heaps(no empty heaps)instead of the picking operation.Please find out which player will win the game if each of them never make mistakes.

 Input

Intput contains multiple test cases. The first line is an integer 1≤T≤100, the number of test cases. Each case begins with an integer n, indicating the number of the heaps, the next line contains N integers s[0],s[1],....,s[n−1], representing heaps with s[0],s[1],...,s[n−1] objects respectively.(1≤n≤10^6,1≤s[i]≤10^9)


 Output

For each test case,output a line whick contains either"First player wins."or"Second player wins".

 Sample Input

2
2
4 4
3
1 2 4

 Sample Output

Second player wins.
First player wins.

 Problem Idea

解题思路:

【题意】
两位玩家(First player and Second player)轮流从n堆糖果中取糖果,规则:

First player先手,可从其中一堆取任意颗,不能不取;或将该堆分为三堆非零堆,谁先取完谁赢

给你n堆糖果每堆的糖果数,问谁会赢


【类型】
博弈(打表找规律)

【分析】
显然,对于博弈题,无非几种情况

要么就是常见的几种已知博弈,要么就是sg函数强解,要么就是打表找规律

此题数据范围显然是不能sg函数强解,那我们就打表找规律

在这之前,我们先回忆一下尼姆博弈

基本的尼姆博弈无非就是各堆的sg值异或,而尼姆博弈的sg[x]值是其本身x

那我们此题要做的就是求出这个sg[x]值的规律

那我们打表打出0~99的sg值

打表程序如下:

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-8
#define LL long long
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 100;
const int M = 16;
const int inf = 1000000007;
const int mod = 110119;
int sg[N];
bool v[N];
int mex(int x)
{
    int i,j;
    memset(v,false,sizeof(v));
    //取任意颗
    for(i=x-1;i>=0;i--)
        v[sg[i]]=true;
    //分三堆
    if(x>=3)
        for(i=1;i<x;i++)//第一堆
            for(j=1;j<x;j++)//第二堆
                if(x-i-j>0)//第三堆
                    v[sg[i]^sg[j]^sg[x-i-j]]=true;
    for(i=0;i<N;i++)
        if(!v[i])
            return i;
}
void table()
{
    int i,j;
    for(i=1;i<N;i++)
        sg[i]=mex(i);
    for(i=0;i<25;i++)
    {
        for(j=0;j<4;j++)
            printf("sg[%2d]=%2d ",i*4+j,sg[i*4+j]);
        puts("");
    }
}
int main()
{
    table();
    return 0;
}
由上述程序可得数据表:

sg[ 0]= 0 sg[ 1]= 1 sg[ 2]= 2 sg[ 3]= 3
sg[ 4]= 4 sg[ 5]= 5 sg[ 6]= 6 sg[ 7]= 8
sg[ 8]= 7 sg[ 9]= 9 sg[10]=10 sg[11]=11
sg[12]=12 sg[13]=13 sg[14]=14 sg[15]=16
sg[16]=15 sg[17]=17 sg[18]=18 sg[19]=19
sg[20]=20 sg[21]=21 sg[22]=22 sg[23]=24
sg[24]=23 sg[25]=25 sg[26]=26 sg[27]=27
sg[28]=28 sg[29]=29 sg[30]=30 sg[31]=32
sg[32]=31 sg[33]=33 sg[34]=34 sg[35]=35
sg[36]=36 sg[37]=37 sg[38]=38 sg[39]=40
sg[40]=39 sg[41]=41 sg[42]=42 sg[43]=43
sg[44]=44 sg[45]=45 sg[46]=46 sg[47]=48
sg[48]=47 sg[49]=49 sg[50]=50 sg[51]=51
sg[52]=52 sg[53]=53 sg[54]=54 sg[55]=56
sg[56]=55 sg[57]=57 sg[58]=58 sg[59]=59
sg[60]=60 sg[61]=61 sg[62]=62 sg[63]=64
sg[64]=63 sg[65]=65 sg[66]=66 sg[67]=67
sg[68]=68 sg[69]=69 sg[70]=70 sg[71]=72
sg[72]=71 sg[73]=73 sg[74]=74 sg[75]=75
sg[76]=76 sg[77]=77 sg[78]=78 sg[79]=80
sg[80]=79 sg[81]=81 sg[82]=82 sg[83]=83
sg[84]=84 sg[85]=85 sg[86]=86 sg[87]=88
sg[88]=87 sg[89]=89 sg[90]=90 sg[91]=91
sg[92]=92 sg[93]=93 sg[94]=94 sg[95]=96
sg[96]=95 sg[97]=97 sg[98]=98 sg[99]=99

观察上述数据,可以发现

当x=8k+7时,sg[x]=8k+8
当x=8k+8时,sg[x]=8k+7
其余时候sg[x]=x;(k>=0)

那问题就解决了,对于输入的每堆糖果数s[i],它的sg值可由上述3种情况确认,确认之后求一下异或,若为0,后手胜;否则,先手胜

【时间复杂度&&优化】
O(n)

题目链接→HDU 5795 A Simple Nim

 Source Code

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-8
#define LL long long
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 10;
const int M = 16;
const int inf = 1000000007;
const int mod = 1000000007;
int main()
{
    int t,n,i,s,ans;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d",&s);
            if(s%8==0)
                s--;
            else if(s%8==7)
                s++;
            ans^=s;
        }
        if(!ans)
            puts("Second player wins.");
        else
            puts("First player wins.");
    }
    return 0;
}

 Problem 1010 Windows 10

Accept: 0    Submit: 0
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit : 65536/65536 K (Java/Others)

 Problem Description

Long long ago, there was an old monk living on the top of a mountain. Recently, our old monk found the operating system of his computer was updating to windows 10 automatically and he even can't just stop it !!

With a peaceful heart, the old monk gradually accepted this reality because his favorite comic LoveLive doesn't depend on the OS. Today, like the past day, he opens bilibili and wants to watch it again. But he observes that the voice of his computer can be represented as dB and always be integer. 

Because he is old, he always needs 1 second to press a button. He found that if he wants to take up the voice, he only can add 1 dB in each second by pressing the up button. But when he wants to take down the voice, he can press the down button, and if the last second he presses the down button and the voice decrease x dB, then in this second, it will decrease 2 * x dB. But if the last second he chooses to have a rest or press the up button, in this second he can only decrease the voice by 1 dB.

Now, he wonders the minimal seconds he should take to adjust the voice from p dB to q dB. Please be careful, because of some strange reasons, the voice of his computer can larger than any dB but can't be less than 0 dB.

 Input

First line contains a number T (1≤T≤300000),cases number.

Next T line,each line contains two numbers p and q (0≤p,q≤10^9)


 Output

The minimal seconds he should take

 Sample Input

2
1 5
7 3

 Sample Output

4
4

 Problem Idea

解题思路:

【题意】
给你两个数p,q,问最少需要多少秒,p能转化为q

操作有如下几类:

①p->p(不操作,休息)

②p->p+1(即p的值每秒增加1)

③p->p-x(即p的值每秒减少x,一开始x=1,如果上一秒减少x,那么这一秒可以减少2x,但是一旦出现上一秒为增加操作或是不操作,那么这一秒x重新从1开始计算)


【类型】
贪心+dfs

【分析】
显然,当q>=p时,为了最少时间内使p->q

肯定不会执行①操作,然后增加只能是1点1点增加,所以最少需要时间无疑为q-p;

当q<p时,这种情况就要分类讨论了,为了缩短时间,肯定要尽可能连续地减少,这样可以增大x

那要连续减少到什么程度呢?肯定要最接近q,但还是有两种情况:

一种是比q小,另一种是比q大

当比q小时,那此只能每秒+1加至q,但别忘了,在之前过程中,如果出现休息操作的话,我们完全可以换成加1操作,使得此过程时间可以少一些

另外需要注意的是若持续减少到比q小的这个数是负数,直接用0代替,因为分贝不可能为负

至于比q大的这种情况,当然就是最初p->q的一个子问题了,dfs一下就可以了

因为连续减少时,x->2x,累计值是二进制数的全1串

如第1秒减少1,第2秒减少2,第3秒减少4,3秒累计,所以我们可以用简便代替

【时间复杂度&&优化】
O(logn)

题目链接→HDU 5802 Windows 10

 Source Code

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 100005;
const int M = 16;
const int inf = 1000000007;
const int mod = 110119;
int dfs(int p,int q,int c)
{
    int k=1;
    while(p-(1<<k)+1>q)
        k++;
    if(p-(1<<k)+1==q)
        return k;
    return k+min(max(0,q-max(p-(1<<k)+1,0)-c),dfs(p-(1<<(k-1))+1,q,c+1));
}
int main()
{
    int t,p,q;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&p,&q);
        if(q>=p)
            printf("%d\n",q-p);
        else
            printf("%d\n",dfs(p,q,0));
    }
    return 0;
}
菜鸟成长记

智能推荐

注意！

本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。



猜您在找
2016 Multi-University Training Contest 8题解报告 2016 Multi-University Training Contest 2题解报告 2016 Multi-University Training Contest 5题解报告 2016 Multi-University Training Contest 9题解报告 2016 Multi-University Training Contest 1题解报告
 
© 2014-2019 ITdaan.com 粤ICP备14056181号  

赞助商广告