ICPC2016 青岛 [Cloned]

ICPC2016 青岛 [Cloned]

A-Relic Discovery

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int n,t;
int a,b;
int res=0;
int main()
{
   
    scanf("%d",&t);
    while(t--)
    {
   
        scanf("%d",&n);
        res=0;
        while(n--)
        {
   
            scanf("%d%d",&a,&b);
            res+=a*b;
        }
        printf("%d\n",res);
    }
    return 0;
}

B-Pocket Cube

题意：

给了一个魔方，魔方每个面有四个小方块。现在给了小方块上的数字，问魔方能否在一次旋转之内复原，即同一个面上的数字都相同。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int a[10][10];
int t;
bool check(int x,int y)
{
   
    int num1=1,num2=1;
    for(int i=1;i<4;i++)
    {
   
        if(a[x][i]==a[x][i-1])num1++;
        if(a[y][i]==a[y][i-1])num2++;
    }
    if(num1!=4||num2!=4)return false;
    int num;
    int sum=0;
    for(int i=0;i<6;i++)
    {
   
        num=1;
        for(int j=1;j<4;j++)
            if(a[i][j]==a[i][j-1])num++;
        sum+=num;
    }
    if(sum==24)return true;
    if(x==0&&y==2)
    {
   
        if(a[1][0]!=a[1][1]||a[1][2]!=a[1][3])return false;
        if(a[3][0]!=a[3][1]||a[3][2]!=a[3][3])return false;
        if(a[4][0]!=a[4][2]||a[4][1]!=a[4][3])return false;
        if(a[5][0]!=a[5][2]||a[5][1]!=a[5][3])return false;
        if(a[1][0]==a[5][1]&&a[5][0]==a[3][0]&&a[3][2]==a[4][0]&&a[4][1]==a[1][2])return true;
        if(a[1][0]==a[4][0]&&a[4][1]==a[3][0]&&a[3][2]==a[5][1]&&a[5][0]==a[1][2])return true;
        return false;
    }
    else if(x==1&&y==3)
    {
   
        if(a[0][0]!=a[0][1]||a[0][2]!=a[0][3])return false;
        if(a[2][0]!=a[2][1]||a[2][2]!=a[2][3])return false;
        if(a[4][0]!=a[4][1]||a[4][2]!=a[4][3])return false;
        if(a[5][0]!=a[5][1]||a[5][2]!=a[5][3])return false;
        if(a[0][0]==a[5][2]&&a[5][0]==a[2][0]&&a[2][2]==a[4][2]&&a[4][0]==a[0][2])return true;
        if(a[0][0]==a[4][2]&&a[4][0]==a[2][0]&&a[2][2]==a[5][2]&&a[5][0]==a[0][2])return true;
        return false;
    }
    else if(x==4&&y==5)
    {
   
        if(a[0][0]!=a[0][2]||a[0][1]!=a[0][3])return false;
        if(a[2][0]!=a[2][2]||a[2][1]!=a[2][3])return false;
        if(a[1][0]!=a[1][2]||a[1][1]!=a[1][3])return false;
        if(a[3][0]!=a[3][2]||a[3][1]!=a[3][3])return false;
        if(a[0][0]==a[1][1]&&a[1][0]==a[2][1]&&a[2][0]==a[3][1]&&a[3][0]==a[0][1])return true;
        if(a[0][0]==a[3][1]&&a[3][0]==a[2][1]&&a[2][0]==a[1][1]&&a[1][0]==a[0][1])return true;
        return false;
    }
}
int main()
{
   
    scanf("%d",&t);
    while(t--)
    {
   
        for(int i=0;i<6;i++)
            for(int j=0;j<4;j++)
            scanf("%d",&a[i][j]);
        if(check(0,2)||check(1,3)||check(4,5))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

C-Pocky

题意：

给了长度为L的pocky，将这个分成两部分，任意长度均有可能，吃掉左半部分，然后再选再吃。直到剩下的部分小于等于b就停止，问吃的次数的期望。

solution：

1.找规律

当L<=d，期望为0
当L>d，通过给定的样例，我们可以知道肯定和2的倍数有关系，并且有个等差0.693147，然后就去找2的规律，发现$log2=0.693147$,$\frac{2}{1}=2^{lo{g}_{2}2},此时为1+ln2$，$\frac{4}{1}=2^{lo{g}_{2}4},此时为1+ln4$，$\frac{8}{1}=2^{lo{g}_{2}8},1+ln8$，${\frac{16}{1}}^4=2^{lo{g}_{2}16},1+ln16$，$\frac{7}{3}=2^{lo{g}_2\frac{7}{3}},1+ln\frac{7}{3}$,所以最后答案就变成了$1+ln\frac{L}{b}$

2.推式子

设x为0-L的任意一个位置。
当x<=d时，$f(x)=0$
当x>d时，$f(x)=1+\frac{{\int }_d^{x}f(t)dt}{x}=1+\frac{F(x)-F(d)}{x}$
$f^{{}^{\prime }}(x)=\frac{x{F}^{{}^{\prime }}(x)-F(x)+F(d)}{x^2}=\frac{xf(x)-{\int }_d^{x}f(t)dt}{x^2}=\frac{xf(x)+x(1-f(x))}{x^2}=\frac{1}{x}$
所以$f(x)=ln(x)+C$
$f(d)=ln(d)+C=1,C=1-ln(d)$
$f(x)=ln(x)-ln(d)+1=ln(\frac{x}{d})+1$

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
double d,L;
int n;
int main()
{
   
    scanf("%d",&n);
    while(n--)
    {
   
        scanf("%lf%lf",&L,&d);
        if(L<=d)
            printf("0.000000\n");
        else
        {
   
            double x=1.0*L/d;
            double res=1+log(x);
            printf("%.6f\n",res);
        }
    }
    return 0;
}

D-Lucky Coins

E-Fibonacci

F-Lambda Calculus

G-Coding Contest

H-Pattern

I-Travel Brochure

J-Cliques

K-Finding Hotels

L-Tower Attack

M-Generator and Monitor