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异或一个 2k-1，k可以是任意正整数n+=1
要求两种操作交替使用，问多少次操作才能使n为 2m-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，有如下公式：
即：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
思路
使用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;
}
