A. Neko Finds Grapes

题意

给定两行数，用第二行的数加上第一行的数，每个数只能用一次，求出相加之和最多有多少个奇数

关键词

贪心

思路

用一行奇数加上另外一行的偶数

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 200005
#define MAXM 200
#define MAXK 10000010
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)

//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

int n, m;
int a[MAXN], b[MAXN];
int a1=0,a2=0;
int b1=0,b2=0;

int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
        if(a[i]%2)
            a1++;
    }
    for (int i = 0; i < m; ++i)
    {
        cin>>b[i];
        if(b[i]%2)
            b1++;
    }
    a2 = n-a1;
    b2 = m-b1;
    int ans = min(a1,b2) + min(a2, b1);
    cout<<ans<<endl;
#ifdef FILE_IN
    fclose(stdin);
#endif
    return 0;
}

B. Neko Performs Cat Furrier Transform

题意

给定一个数n，定义2种操作：

n异或一个 2^k-1，k可以是任意正整数

n+=1

要求两种操作交替使用，问多少次操作才能使n为 2^m-1,m可以是任意整数。
并要求输出每次第一种操作的k。

关键词

位运算、模拟

思路

直接按要求模拟即可。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 1000006
#define MAXM 200
#define MAXK 10000010
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)

//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

bool vis[MAXN];

int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC
    int x;
    cin>>x;
    int ans = 0;
    vector<int> op;
    int t = 0;
    while(((int)(log2(x+1))) != log2(x+1))
    {
        ans++;
        if(t)
        {
            x = x + 1;
        } else
        {
            int y = x;
            int id = 0;
            int cnt = 0;
            while(y)
            {

                if((y&1) == 0)
                    id= cnt;
                y = y >>1;
                cnt++;
            }
            x ^= (1<<(id+1))-1;

            op.pb(id+1);
        }
        t  = 1-t;

    }

    cout<<ans<<endl;
    for (int i = 0; i < op.size(); ++i)
    {
        if(i)
            cout<<" ";
        cout<<op[i];
    }
    cout<<endl;


#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

C. Neko does Maths

题意

给定两个整数a和b，要求输出能使lcm(a+k,b+k)最小的正整数k。

关键词

数论、gcd、lcm

思路

枚举b-a的因子，维护lcm最小值。
假设a>b，有如下公式：

$lcm(a+k, b+k)=\frac{(a+k)*(b+k)}{gcd(a+k, b+k)} = \frac{(a+k)*(b+k)}{\color{red}{gcd(a-b, b+k)}}$
即：gcd(a+k, b+k)一定为a-b的一个因子，通过枚举这个因子，来找到使lcm(a+k, b+k)最小的k即可。
需要注意的是，这里并不能说保证分母gcd(a-b, b+k)最大，就能得到lcm(a+k, b+k)的最小值。会WA。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 1000006
#define MAXM 200
#define MAXK 10000010
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)

//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

ll a, b;
ll ans = 0;
ll Lcm;

void update (ll i)
{
    ll k = i - b % i;
    ll lc = (a + k) * (b + k) / i;
    if (lc < Lcm)
    {
        Lcm = lc;
        ans = k;
    }
}

int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC

    cin >> a >> b;
    if (a < b)
        swap(a, b);
    ll c = a - b;
    Lcm = a * b;

    if (c == 0 || a % b == 0 || b % c == 0)
        ans = 0;
    else
        for (ll i = 1; i * i <= c; ++i)
        {
            if (c % i == 0)
            {
                update(i);
                update(c / i);
            }
        }

    cout << ans << endl;


#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

D. Neko and Aki's Prank

题意

给一个长度为2n的括号序列（左括号和右括号各为n个），画出前缀树后，求最大匹配。

关键词

思路

使用dp[i][j]表示还剩i个左括号j个右括号没使用时，从初始状态(n,n)到当前状态匹配的数量。
通过分析前缀树可知，每种状态，能通过dp[i+1][j]、dp[i][j+1]这2种状态转移过来。即通过增加一个左括号或右括号转移过来。
并且一个合法的括号序列，显然是在任何状态都满足j>=i，即已经使用的右括号数量一定小于等于左括号数量。不然就会出现"(()))"这种，后序无论如何都是不合法的情况。

前缀树和状态表格

图的匹配要求一个点不能连两条匹配的边。如图，(2,2)状态只有一条匹配中的边，这条边相邻的节点就不能再有匹配中的边。
也就是，状态每转移2次，第二次状态的点就可以有一条匹配中的边。再形象点，就是图中每隔一层，就会出现一次匹配的边。
显然，每转移两次，(i+j)的奇偶性就不会改变，所以，当奇偶性为某一个值时，其结果就会加1。状态一共有n*(n-1)个，所以(i+j)的奇偶性无论为0还是1时让结果加1，应该都是可以的。
由状态的定义可知，在当前状态无法使结果加一时，dp[i][j]=dp[i+1][j]+dp[i][j+1]
最终的状态转移方程：dp[i][j] = dp[i+1][j] + dp[i][j+1] + (i+j)%2。dp[0][0]就是结果的解。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 1006
#define MAXM 200
#define MAXK 10000010
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
#define MSET(arr, v) memset((arr),(v),sizeof(arr))
#define SCAND(n) scanf("%d", &n)
#define PRINTD(n) printf("%d", n)

//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

int n;
ll dp[MAXN][MAXN];

int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC

    MSET(dp, 0);
    SCAND(n);
    for (int i = n; i >= 0; --i)
    {
        for (int j = i; j >= 0; --j)
        {
            dp[i][j] = (dp[i + 1][j] + dp[i][j + 1] + (i + j) % 2) % MOD;
        }
    }


    cout << dp[0][0] << endl;


#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

Codeforces Round #554 (Div. 2)

A. Neko Finds Grapes

题意

关键词

思路

代码

B. Neko Performs Cat Furrier Transform

题意

关键词

思路

代码

C. Neko does Maths

题意

关键词

思路

代码

D. Neko and Aki's Prank

题意

关键词

思路

代码