头像

Jerry1973




离线


最近来访(14)
用户头像
墨染樱飞
用户头像
不要问我叫什么
用户头像
hqxx_xxx
用户头像
limie
用户头像
用户头像
maro
用户头像
天使-高某人和彦
用户头像
万花筒写轮眼
用户头像
一只奇怪的小魔女
用户头像
大雪莱
用户头像
沐星不仙了

活动打卡代码 AcWing 96. 奇怪的汉诺塔

Jerry1973
2019-07-03 14:29
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 15;
int d[maxn], f[maxn];
int main()
{
    d[1] = 1, f[1] = 1;
    for (int i = 2; i <= 12; i++)
        d[i] = 1 + 2 * d[i - 1];
    for (int n = 2; n <= 12; n++)
    {
        int ans = 0x3f3f3f3f;
        for (int i = 1; i < n; i++)
            ans = min(ans, 2 * f[i] + d[n - i]);
        f[n] = ans;
    }
    for (int i = 1; i <= 12; i++)
        cout << f[i] << endl;
    return 0;
}


活动打卡代码 AcWing 95. 费解的开关

Jerry1973
2019-07-03 13:53
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 7;
bool Map[maxn][maxn],now[maxn][maxn];
int ans , curans = 0;
int dir[5][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {0, 0}};
void turn(int x, int y)
{
    for (int i = 0; i < 5; i++)
    {
        int nx = x + dir[i][0], ny = y + dir[i][1];
        if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5) 
            now[nx][ny] ^= 1;
    }
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        ans = 0x3f3f3f3f;
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
            {
                char tmp;
                cin>>tmp;
                if (tmp=='1') Map[i][j]=1;
                if (tmp=='0') Map[i][j]=0;
            }
        for (int i = 0; i < 1 << 5; i++) 
        {
            for (int k=0;k<5;k++)
                for (int j=0;j<5;j++)
                    now[k][j]=Map[k][j];
            for (int j = i, pos = 0; j; j >>= 1, pos++)
                if (j & 1)
                {
                    turn(0, pos);
                    curans++;
                }
            for (int j = 1; j < 5; j++) 
                for (int k = 0; k < 5; k++)
                    if (!now[j - 1][k])
                    {
                        turn(j, k);
                        curans++;
                    }
            bool flag = 1;
            for (int j = 0; j < 5; j++)
                if (!now[4][j])
                    flag = 0;
            if (flag)
                ans = min(ans, curans);
            curans = 0;
        }
        if (ans > 6)
            cout << -1 << endl;
        else
            cout << ans << endl;
    }
    return 0;
}



Jerry1973
2019-07-03 10:09
#include <iostream>
#include <vector>
using namespace std;
vector<int> chose;
int n;
void dfs(int dep,int state)
{
    if (dep==n)
    {
        for (auto i:chose)
            cout<<i<<" ";
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if (state>>(i-1)&1) continue;
        chose.push_back(i);
        dfs(dep+1,state|1<<(i-1));
        chose.pop_back();
    }
}
int main()
{
    cin>>n;
    dfs(0,0);
    return 0;
}



Jerry1973
2019-07-03 06:32
#include <iostream>
using namespace std;
int n,m;
void dfs(int dep,int state,int get)
{
    if (get+n-dep<m) return;
    if (get==m)
    {
        for (int i=1;state;state>>=1,i++)
            if (state&1) cout<<i<<" ";
        cout<<endl;
        return;
    }
    dfs(dep+1,state|1<<dep,get+1);
    dfs(dep+1,state,get);
}
int main()
{
    cin>>n>>m;
    dfs(0,0,0);
    return 0;
}



Jerry1973
2019-07-03 03:31
#include <iostream>
using namespace std;
int n;
void dfs(int dep,int state)
{
    if (dep==n)
    {
        for (int i=1;state;state>>=1,i++)
            if (state&1) cout<<i<<" ";
        cout<<endl;
        return;
    }
    dfs(dep+1,state);
    dfs(dep+1,state|1<<dep);
}
int main()
{
    cin>>n;
    dfs(0,0);
    return 0;
}


活动打卡代码 AcWing 90. 64位整数乘法

Jerry1973
2019-07-01 13:33
#include <iostream>
using namespace std;
int main()
{
    long long a, b, p;
    cin >> a >> b >> p;
    long long ans = 0;  //不同于a^b:这里不用先%p是因为就算p=1时ans也为0
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = (ans + a) % p;    //不同于a^b:这里不需要强制类型转换是因为1e8*2<2^63-1(即ans+a最大值在long long范围内)
        a = a * 2 % p;
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 89. a^b

Jerry1973
2019-06-27 15:16

分不清long long 和 int+do while当for用+昏昏欲睡=以下代码

#include <iostream>
using namespace std;
int main()
{
    long long a, b, p, ans;
    cin >> a >> b >> p;
    ans = 1 % p;
    do
    {
        if (b & 1)
        {
            ans *= a;
            ans %= p;
        }
        a *= a;
        a %= p;
    } while (b >>= 1);
    cout << ans << endl;
    return 0;
}

其实原理很简单,正如每个数都有其对应的2进制一样,根据二进制转十进制的方法,很容易发现每个数都可以表示为2的一些次幂之和。利用这一性质对数进行拆分,大整数变成了加法,乘方变成了乘法,乘法又变成了加法,起到类似降级的作用,化繁为简,甚是巧妙。
对书再次研究,深入思考,便得到与书中几乎相同的代码(并木有抄书)

#include <iostream>
using namespace std;
int main()
{
    int a, b, p;
    cin >> a >> b >> p;
    int ans = 1 % p;    //为什么要先%一下呢?考虑b=0,p=0的情况。
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = (long long)ans * a % p;   //为什么不用*=呢?其实我挺想用,像上面:将变量们开成long long就可以了,只是不方便%p。
        a = (long long)a * a % p;
    }
    cout << ans << endl;    //个人认为放在这里%也没有问题。
    return 0;
}

看起来简洁多了。


而这不禁又令人想起了另一道(小学)题目:
找10个数,使得其中某个或某些数之和可以表示出1~1000中所有的数。
答案脱口而出,但为什么不能是3的次幂呢?
二进制数每一位可写作1,0,正好对应每个数取或不取的状态;而换成三进制后,每一位可写作0,1,2,而不存在取2遍的状态。
相信现在你(包括我)一定对2进制有了更深的理解。