【noip模拟赛 sword,zero,2048】 题解

时间:2021-10-15 18:33:24

1、光剑
(sword.pas/c/cpp)

【题目描述】

小林和亮亮各有一把光剑,长度分别为 a 和 b,他们拿光剑进行比试。每一回合,长光剑会砍向短光剑,砍完后,短光剑完好无损,而长光剑则被截成两段,被截去的长度恰好等于短光剑的长度。若两把光剑长度相等,则比试结束。请问小林和亮亮将比试多少回合?

【输入格式】

第一行一个整数 T,表示数据组数。
接下来 T 行每行两个正整数 a,b,表示初始状态光剑的长度。

【输出格式】

每组数据输出一个整数,表示能进行几个回合的比试。

【样例输入】

3
1 8
3 7
6 6

【样例输出】

7
4
0

【数据规模】

对于 40%的数据,0 < a,b <= 1000, 1 <= T <= 20;
对于 100%的数据,0 < a,b <= 10^18,1 <= T <= 1000。

题解:模拟辗转相除。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll x, y, T;
int main()
{
    freopen("sword.in","r",stdin);
    freopen("sword.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>T;
    for(ll a = 1; a <= T; a++)
    {
        ll round = 0, now;
        cin>>x>>y;
        if(x < y) swap(x, y); // x 大   y 小 
        if(x == y) 
        {
            cout<<0<<endl;
            continue;
        }
        while(x % y != 0)
        {
            round += x/y; // x = 7  y = 3
            now = x % y;  // now = 1
            x = y;
            y = now;
        }       
        cout<<round-1+x/y<<endl;
    }
}

2、化零
(zero.pas/c/cpp)

Describe

有5个集合,每个集合N个元素,从每个集合选出一个数,共5个,问是否可以使和为0。

IN put:

第一行一个整数 N,表示集合的大小。

接下来五行每行 N个整数,表示这五个集合内的元素。

OUT put:

如果能找到符合条件的五个数,则输出“YES”,否则输出“NO”。

example:

in
3
1 -2 9
-1 2 1
-3 5 1
-1 7 6
-4 -1 -7
out
YES

数据范围:

N<=20 30%
N<=200 100%

题解:

考虑 N <= 20 直接N^5暴力

对于 N > 20 考虑一种赌博式的想法

如果有合法解的话,不妨设在前两个集合和后三个集合存在相反数

这样我们可以预先处理出N^2 和 N^3 的方案数,再进行组合,看是否有相反数

这时候我们先排序再套个lower_bound就ok了

最差在没有解大概跑了1.11s

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 210;
ll a[maxn], b[maxn], c[maxn], d[maxn], e[maxn], n;
ll ans1[41000], ans2[8000100], cnt1 = 0, cnt2 = 0;
inline ll read()
{
    ll k=0,f=1;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(isdigit(c))
    {
        k=(k<<1)+(k<<3)+c-48;
        c=getchar();
    }
    return k*f;
}
int main()
{
    n = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = 1; i <= n; i++) b[i] = read();
    for(int i = 1; i <= n; i++) c[i] = read();
    for(int i = 1; i <= n; i++) d[i] = read();
    for(int i = 1; i <= n; i++) e[i] = read();
    
    if(n <= 25)
    {
        for(int v = 1; v <= n; v++)
            for(int w = 1; w <= n; w++)
                for(int x = n; x >= 1; x--)
                    for(int y = n; y >= 1; y--)
                        for(int z = n; z >= 1; z--)
                        {
                            if(a[v] + b[w] + c[x] + d[y] + e[z] == 0)
                            {
                                cout<<"YES"<<endl;
                                return 0;
                            }
                        }
        cout<<"NO"<<endl;
        return 0;
    }
    else
    {
        for(int v = 1; v <= n; v++)
            for(int w = 1; w <= n; w++)
                ans1[++cnt1] = a[v]+b[w];
        for(int x = 1; x <= n; x++)
                for(int y = 1; y <= n; y++)
                    for(int z = 1; z <= n; z++)
                    ans2[++cnt2] = -1*(c[x]+d[y]+e[z]);
        sort(ans1+1, ans1+1+cnt1);
        for(int i = 1; i <= cnt2; i++)
            {
                int now = lower_bound(ans1+1, ans1+1+cnt1, ans2[i])-ans1;
                if(ans1[now] == ans2[i])
                {
                    cout<<"YES"<<endl;
                    return 0;
                }
            }
            
        cout<<"NO"<<endl;
        return 0;
    }
}

3、2048
(2048.pas/c/cpp)
【题目描述】
小林和亮亮最近正在重温 2048 这款游戏。由于他们的游戏水平高超,觉得没有什么挑战性,于是决定自己设计一款类似的游戏。他们设计的游戏中,数字排成了一个线性的序列,每次玩家可以将序列中任意两个相同的数 a 合并,成为一个新的数 2*a,当合并出 2048 时游戏即获得胜利。设计完后,他们发现这个游戏比原来的版本更加简单了,于是他们就开始计算,对于一个给定的长度为 n 的序列,它共有多少子序列可以合并出 2048。请给出这个数模 998244353 后的值。

【输入格式】

第一行有一个整数 n。
第二行 n个整数Ai,表示数列中的数。

【输出格式】

一个整数,即为所求的答案。

【样例输入】

2
2048 2048

【样例输出】

3

【数据规模】

对于 40%的数据,n <= 20;
对于 70%的数据,n <= 500;
对于100%的数据,1 <= n <= 100000,1 <= Ai <= 2048。

题解:

组成2048必须是2的幂次方。

不是的统计到cnt,可以直接扔掉了。

设dp[i][j]表示使用前i个数使他们和为j的方案数

ans = dp[n-cnt][2048]*(1<<cnt)

code不是我的= =考试没写出来,现在也没写出来qwq

#include <cstdio>
#include <cstring>
#define MOD 998244353LL
#define F 2100
using namespace std;

typedef long long LL;

int n, x, cnt = 0;
LL a[F], num[F];

void Read(int &x)
{
    x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
}

int main()
{
    freopen("2048.in", "r", stdin);
    freopen("2048.out", "w", stdout);
    
    Read(n);
    memset(num, 0, sizeof(num));
    memset(a, 0, sizeof(a));
    for (int i = 0; i <= 11; i++)
        num[1<<i] = i;
    
    for (int i = 1; i <= n; i++)
    {
        Read(x);
        if (!num[x] && x != 1) { cnt++; continue; }
        
        for (int j = 2048; j >= 1; j--)
            if (a[j])
            {
                if (j + x <= 2048) a[j+x] = (a[j+x] + a[j]) % MOD;
                else a[2048] = (a[2048] + a[j]) % MOD;
            }
        a[x]++;
    }
    
    for (int i = 1; i <= cnt; i++)
        a[2048] = a[2048] * 2LL % MOD;
    
    printf("%d\n", a[2048]);
    
    return 0;
}