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的规律，发现 l o g 2 = 0.693147 log2=0.693147 log2=0.693147, 2 1 = 2 l o g 2 2 , 此 时 为 1 + l n 2 \frac{2}{1}=2^{log_22},此时为1+ln2 12​=2log2​2,此时为1+ln2， 4 1 = 2 l o g 2 4 , 此 时 为 1 + l n 4 \frac{4}{1}=2^{log_24},此时为1+ln4 14​=2log2​4,此时为1+ln4， 8 1 = 2 l o g 2 8 , 1 + l n 8 \frac{8}{1}=2^{log_28},1+ln8 18​=2log2​8,1+ln8， 16 1 4 = 2 l o g 2 16 , 1 + l n 16 \frac{16}{1}^4=2^{log_216},1+ln16 116​4=2log2​16,1+ln16， 7 3 = 2 l o g 2 7 3 , 1 + l n 7 3 \frac{7}{3}=2^{log_2{\frac{7}{3}}},1+ln\frac{7}{3} 37​=2log2​37​,1+ln37​,所以最后答案就变成了 1 + l n L b 1+ln{\frac{L}{b}} 1+lnbL​

2.推式子

设x为0-L的任意一个位置。
当x<=d时， f ( x ) = 0 f(x)=0 f(x)=0
当x>d时， f ( x ) = 1 + ∫ d x f ( t ) d t x = 1 + F ( x ) − F ( d ) x f(x)=1+\frac{\int_{d}^{x}{f(t)dt}}{x}=1+\frac{F(x)-F(d)}{x} f(x)=1+x∫dx​f(t)dt​=1+xF(x)−F(d)​
f ′ ( x ) = x F ′ ( x ) − F ( x ) + F ( d ) x 2 = x f ( x ) − ∫ d x f ( t ) d t x 2 = x f ( x ) + x ( 1 − f ( x ) ) x 2 = 1 x f^{'}(x)=\frac{xF^{'}(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)=x2xF′(x)−F(x)+F(d)​=x2xf(x)−∫dx​f(t)dt​=x2xf(x)+x(1−f(x))​=x1​
所以 f ( x ) = l n ( x ) + C f(x)=ln(x)+C f(x)=ln(x)+C
f ( d ) = l n ( d ) + C = 1 , C = 1 − l n ( d ) f(d)=ln(d)+C=1,C=1-ln(d) f(d)=ln(d)+C=1,C=1−ln(d)
f ( x ) = l n ( x ) − l n ( d ) + 1 = l n ( x d ) + 1 f(x)=ln(x)-ln(d)+1=ln(\frac{x}{d})+1 f(x)=ln(x)−ln(d)+1=ln(dx​)+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