2017 ACM-ICPC, Universidad Nacional de Colombia Programming Contest D的解题思路是什么？
- 内容介绍
- 文章标签
- 相关推荐
本文共计580个文字，预计阅读时间需要3分钟。
Alex有两个魔法机器A和B。机器A接收x个硬币后，会给你2x+1个硬币；机器B接收x个硬币后，会给你2x+2个硬币。Alex最初没有硬币，他想要恰好获得n个硬币来买一只新独角兽，但他做不到。
Alex has two magic machines A and B. Machine A will give you 2x + 1 coins if you insert x coins in it, machine B will give you 2x + 2. Alex has no coins and wants to get exactly n coins in order to buy a new unicorn, but he can’t figure out how to do it. Your task is to find a way to use the machines to get exactly n coins.
Input
The input consists of a single line containing n (1 ≤ n ≤ 109).
Output
For each one output a string of A’s and B’s giving the order in which the machines are used.
Examples
Input
7
Output
AAA
Input
10
Output
ABB
额。。。其实很简单的一道题。。
本来打算 dfs 的。。。。
然后T在19个点。
int dfs(int x) {
if (x > n)return 0;
if (x == n)return 1;
if (dfs(2 * x + 1)) {
vis[++tot] = 1;
return 1;
}
if (dfs(2 * x + 2)) {
vis[++tot] = 2;
return 1;
}
return 0;
}
其实分个奇偶就可以了。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 30005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-7
#define pll pair<ll,ll>
ll quickpow(ll a, ll b) {
ll ans = 1;
a = a % mod;
while (b > 0) {
if (b % 2)ans = ans * a;
b = b / 2;
a = a * a;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
int n;
int vis[maxn];
int tot;
void dfs() {
while (n) {
if (n % 2 == 0) {
vis[++tot] = 2;
n = (n - 2) / 2;
}
else {
vis[++tot] = 1;
n = (n - 1) / 2;
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin >> n;
scanf("%d", &n);
dfs();
for (int i = tot; i >= 1; i--) {
if (vis[i] == 1)printf("A");
else if (vis[i] == 2)printf("B");
}
printf("\n");
}
本文共计580个文字，预计阅读时间需要3分钟。
Alex有两个魔法机器A和B。机器A接收x个硬币后，会给你2x+1个硬币；机器B接收x个硬币后，会给你2x+2个硬币。Alex最初没有硬币，他想要恰好获得n个硬币来买一只新独角兽，但他做不到。
Alex has two magic machines A and B. Machine A will give you 2x + 1 coins if you insert x coins in it, machine B will give you 2x + 2. Alex has no coins and wants to get exactly n coins in order to buy a new unicorn, but he can’t figure out how to do it. Your task is to find a way to use the machines to get exactly n coins.
Input
The input consists of a single line containing n (1 ≤ n ≤ 109).
Output
For each one output a string of A’s and B’s giving the order in which the machines are used.
Examples
Input
7
Output
AAA
Input
10
Output
ABB
额。。。其实很简单的一道题。。
本来打算 dfs 的。。。。
然后T在19个点。
int dfs(int x) {
if (x > n)return 0;
if (x == n)return 1;
if (dfs(2 * x + 1)) {
vis[++tot] = 1;
return 1;
}
if (dfs(2 * x + 2)) {
vis[++tot] = 2;
return 1;
}
return 0;
}
其实分个奇偶就可以了。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 30005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-7
#define pll pair<ll,ll>
ll quickpow(ll a, ll b) {
ll ans = 1;
a = a % mod;
while (b > 0) {
if (b % 2)ans = ans * a;
b = b / 2;
a = a * a;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
int n;
int vis[maxn];
int tot;
void dfs() {
while (n) {
if (n % 2 == 0) {
vis[++tot] = 2;
n = (n - 2) / 2;
}
else {
vis[++tot] = 1;
n = (n - 1) / 2;
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin >> n;
scanf("%d", &n);
dfs();
for (int i = tot; i >= 1; i--) {
if (vis[i] == 1)printf("A");
else if (vis[i] == 2)printf("B");
}
printf("\n");
}