2016ICPC沈阳站 [Cloned]

2016ICPC沈阳站 [Cloned]

A-Thickest Burger

题意：

给了你两种肉的厚度，问加三片肉的最大厚度是多少（不允许加三片相同的肉）

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

B-Relative atomic mass

题意：

给了一个字符串，里面只含有H、O、C，计算相对原子质量总和

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
string s;
int t;
int main()
{
   
    scanf("%d",&t);
    while(t--)
    {
   
        cin>>s;
        int res=0;
        for(int i=0;i<s.length();i++)
        {
   
            if(s[i]=='H')res+=1;
            else if(s[i]=='O')res+=16;
            else if(s[i]=='C')res+=12;
        }
        printf("%d\n",res);
    }
    return 0;
}

C-Recursive sequence

题意：

给了a，b分别代表第一头牛和第二头头牛的数量，让你求第n头牛的数。给定的计算公式如下：
$F(i)=2\ast F(i-2)+F(i-1)+i^4$

solution：

一篇大佬写的博客矩阵快速幂
构造矩阵如下：
第一种：
$${\left[\begin{array}{ccccccc}1& 2& 1& 4& 6& 4& 1\\ 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 4& 6& 4& 1\\ 0& 0& 0& 1& 3& 3& 1\\ 0& 0& 0& 0& 1& 2& 1\\ 0& 0& 0& 0& 0& 1& 1\\ 0& 0& 0& 0& 0& 0& 1\end{array}\right]}^{n-2}\times \left[\begin{array}{c}F(2)\\ F(1)\\ 1^4\\ 1^3\\ 1^2\\ 1^1\\ 1^0\end{array}\right]=\left[\begin{array}{c}F(n)\\ F(n-1)\\ (n+1{)}^4\\ (n+1{)}^3\\ (n+1{)}^2\\ (n+1{)}^1\\ (n+1{)}^0\end{array}\right]$$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const ll mod=2147493647;
int n;
ll a,b;
int t;
ll fpow(int ti)
{
   
    ll ttem[7][7];
    ll x[7][7]={
   {
   1,2,1,4,6,4,1},{
   1,0,0,0,0,0,0},{
   0,0,1,4,6,4,1},{
   0,0,0,1,3,3,1},{
   0,0,0,0,1,2,1},{
   0,0,0,0,0,1,1},{
   0,0,0,0,0,0,1}};
    ll tem[7][7]={
   {
   1,0,0,0,0,0,0},{
   0,1,0,0,0,0,0},{
   0,0,1,0,0,0,0},{
   0,0,0,1,0,0,0},{
   0,0,0,0,1,0,0},{
   0,0,0,0,0,1,0},{
   0,0,0,0,0,0,1}};
    while(ti)
    {
   
        if(ti%2)
        {
   
            memset(ttem,0,sizeof(ttem));
            for(int i=0;i<7;i++)
            {
   
                for(int j=0;j<7;j++)
                {
   
                    for(int k=0;k<7;k++)
                        ttem[i][j]=(ttem[i][j]+tem[i][k]*x[k][j])%mod;
                }
            }
            for(int i=0;i<7;i++)
                for(int j=0;j<7;j++)
                tem[i][j]=ttem[i][j];
        }
        ti/=2;
        memset(ttem,0,sizeof(ttem));
        for(int i=0;i<7;i++)
        {
   
            for(int j=0;j<7;j++)
            {
   
                for(int k=0;k<7;k++)
                    ttem[i][j]=(ttem[i][j]+x[i][k]*x[k][j])%mod;
            }
        }
        for(int i=0;i<7;i++)
            for(int j=0;j<7;j++)
            x[i][j]=ttem[i][j];
    }
    ll res=(b*tem[0][0]%mod+a*tem[0][1]%mod+16*tem[0][2]%mod+8*tem[0][3]%mod+4*tem[0][4]%mod+2*tem[0][5]%mod+tem[0][6])%mod;
    return res;
}

int main()
{
   
    scanf("%d",&t);
    while(t--)
    {
   
        scanf("%d%lld%lld",&n,&a,&b);
        if(n==1)printf("%d\n",a);
        else if(n==2)printf("%d\n",b);
        else printf("%lld\n",fpow(n-2));
    }
    return 0;
}

第二种：
$${\left[\begin{array}{ccccccc}1& 2& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 4& 6& 4& 1\\ 0& 0& 0& 1& 3& 3& 1\\ 0& 0& 0& 0& 1& 2& 1\\ 0& 0& 0& 0& 0& 1& 1\\ 0& 0& 0& 0& 0& 0& 1\end{array}\right]}^{n-2}\times \left[\begin{array}{c}F(2)\\ F(1)\\ 3^4\\ 3^3\\ 3^2\\ 3^1\\ 3^0\end{array}\right]=\left[\begin{array}{c}F(n)\\ F(n-1)\\ (n+1{)}^4\\ (n+1{)}^3\\ (n+1{)}^2\\ (n+1{)}^1\\ (n+1{)}^0\end{array}\right]$$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const ll mod=2147493647;
int n;
ll a,b;
int t;
ll fpow(int ti)
{
   
    ll ttem[7][7];
    ll x[7][7]={
   {
   1,2,1,0,0,0,0},{
   1,0,0,0,0,0,0},{
   0,0,1,4,6,4,1},{
   0,0,0,1,3,3,1},{
   0,0,0,0,1,2,1},{
   0,0,0,0,0,1,1},{
   0,0,0,0,0,0,1}};
    ll tem[7][7]={
   {
   1,0,0,0,0,0,0},{
   0,1,0,0,0,0,0},{
   0,0,1,0,0,0,0},{
   0,0,0,1,0,0,0},{
   0,0,0,0,1,0,0},{
   0,0,0,0,0,1,0},{
   0,0,0,0,0,0,1}};
    while(ti)
    {
   
        if(ti%2)
        {
   
            memset(ttem,0,sizeof(ttem));
            for(int i=0;i<7;i++)
            {
   
                for(int j=0;j<7;j++)
                {
   
                    for(int k=0;k<7;k++)
                        ttem[i][j]=(ttem[i][j]+tem[i][k]*x[k][j])%mod;
                }
            }
            for(int i=0;i<7;i++)
                for(int j=0;j<7;j++)
                tem[i][j]=ttem[i][j];
        }
        ti/=2;
        memset(ttem,0,sizeof(ttem));
        for(int i=0;i<7;i++)
        {
   
            for(int j=0;j<7;j++)
            {
   
                for(int k=0;k<7;k++)
                    ttem[i][j]=(ttem[i][j]+x[i][k]*x[k][j])%mod;
            }
        }
        for(int i=0;i<7;i++)
            for(int j=0;j<7;j++)
            x[i][j]=ttem[i][j];
    }
    ll res=(b*tem[0][0]%mod+a*tem[0][1]%mod+81*tem[0][2]%mod+27*tem[0][3]%mod+9*tem[0][4]%mod+3*tem[0][5]%mod+tem[0][6])%mod;
    return res;
}

int main()
{
   
    scanf("%d",&t);
    while(t--)
    {
   
        scanf("%d%lld%lld",&n,&a,&b);
        if(n==1)printf("%d\n",a);
        else if(n==2)printf("%d\n",b);
        else printf("%lld\n",fpow(n-2));
    }
    return 0;
}

D-Winning an Auction

E-Counting Cliques

F-Similar Rotations

G-Do not pour out

H-Guessing the Dice Roll

I-The Elder

J-Query on a graph

K-New Signal Decomposition

L-A Random Turn Connection Game

M-Subsequence