Codeforces Round #851

A. One and Two

题目描述

给定一个序列a中的每个元素都是1或2。找出整数k是否存在，以满足以题目所给条件。

题目分析

1对乘积没有贡献，只需要注意2的个数即可，偶数个2即可满足条件，记录第cnt/2个2的位置输出即可。

code

#includeusing namespace std;const int N = 1e3 + 10;
typedef long long ll;int n, m, k, t;
ll a[N], s[N];void solve()
{cin >> n;for(int i = 1; i <= n; i ++) cin >> a[i];int cnt = 0, k = 0, tem = 0;for(int i = 1; i <= n; i ++)if(a[i] == 2) cnt ++;for(int i = 1; i <= n; i ++){if(a[i] == 2) tem ++;if(tem == cnt / 2){k = i;break;}}if(cnt % 2) puts("-1");else cout << k << "\n";
}int main()
{cin >> t;while(t --) solve();return 0;
}

B. Sum of Two Numbers

题目描述

非负整数a的数字和是其每一位数字数字加起来的结果。找出两个数满足：x+ y = n，且x和y的数字和最多相差1。可以证明，这样和y总是存在的。

题目分析

对于偶数 n 来说，除以2一定可以得到两个相同数字n/2，则一定满足题意。

对于奇数 n 来说，由于c 语言向下取整得特性，除以二我们可以得到(n-1)/2，则剩下一部分为(n+1)/2。正好相差一也可以满足题意。特别的，当个位数数为9时会有特殊的情况，如79，按照以上所说得到的两个数为40和39，不满足要求。

对于上述特殊情况，我们可以采用递归进行处理。我么可以把这一位的9拆分为5和4，再向前递归，若倒数第二位仍然为9此时为满足条件应当拆分成4和5，以保证数字和最多相差一。

code

#includeusing namespace std;int n, m, k, t;int get(int n, bool f)
{if(n % 10 == 9) return get(n / 10, ! f) * 10 + 4 + f;else return n / 2;
}void solve()
{cin >> n;if(n % 10 == 9){int res = get(n, 1);cout << res << " " << n - res << "\n";}else cout << n / 2 << " " << n - (n / 2) << "\n";
}int main()
{cin>>t;while(t--) solve();return 0;
}

C. Matching Numbers

题目大意

给定一个整数n。将整数1到2n配对(即每个整数应该恰好在一对中)，以便每个匹配对的和都是连续且不同的。形式上，让(ai, bi)是你匹配的对，需满足s={a1+b1,a2+b2,…,an+bn}，s[i+1]−s[i]=1。

题目分析

当n为奇数时，可以通过图示方法对应。1~n的前部分数对应n+~2n的后部分数，即可满足；

当n为偶数时，我们可以在奇数成立的情况下加上缺少的数字，可以发现无论怎样调整配队，都会出现不满足条件的配对。

code

#includeusing namespace std;int n, m, k, t;void solve()
{cin >> n;if(n % 2 == 0) puts("NO");else{puts("YES");int r1 = n / 2, r2 = (n + 1) / 2;for(int i = 1; i <= r2; i ++) cout << i << " " << i + r2 + 2 * r1 << "\n";for(int i = r2 + 1; i <= n; i ++) cout << i << " " << i + r1 << "\n";}
}int main()
{cin >> t;while(t --) solve();return 0;
}