A. AquaMoon and Two Arrays
题意
给一个可操作数组$a$和一个目标数组$b$，每次操作选$a$中两个元素，将其中一个$-1$，另一个$+1$. 但要保证所有元素一直是非负的。问有没有可能把$a$变成$b$。如果可以，输出你的操作步骤。
数据保证$sum\{a\}\leq 100, n\leq 100$，不要你操作次数最少，但要小于$100$次.
分析
既然要小于100次等于还是得控制，这不还是要找最少嘛（恼）
不过也可以$n^3$暴力就是了
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
using namespace std;
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
int a[n], b[n];
int sa = 0, sb = 0;
for(int i = 0; i < n; ++i) cin >> a[i], sa += a[i];
for(int i = 0; i < n; ++i) cin >> b[i], sb += b[i];
if(sa != sb){
cout << -1 << endl;
continue;
}
vector<int> c;
vector<int> d;
int i, j;
while(1){
bool flag = 1;
for(int i = 0; i < n; ++i){
if(a[i] != b[i]){
flag = 0;
break;
}
}
if(flag) break;
for(i = 0; i < n; ++i){
for(j = 0; j < n; ++j){
if(a[i] > b[i] && a[j] < b[j]){
break;
}
}
while(a[i] > b[i] && a[j] < b[j]){
a[i]--, a[j]++;
c.pb(i), d.pb(j);
}
}
}
cout << c.size() << endl;
for(int i = 0; i < c.size(); ++i){
cout << c[i] + 1 << ' ' << d[i] + 1 << endl;
}
}
return 0;
}
|
B. Aquamoon and Stolen String
题意
给出$n$（$n$为奇数）个长度为$m$的串，然后将其中$n-1$个串两两配对，配对的串会随机交换相同位置的字符，给出配对完后被打乱顺序的$n-1$个串，要你找出是哪个串没有配对。
分析
由于不管怎么配对怎么变，每个字符交换后的下标都是不变的，只是变了所在的字符串。
所以用一个二维数组统计，$a[i][j]$表示字符$i$在位置$j$出现过几次。配对后再把出现的字符减去，最后二维数组里留下的那个字符就是未配对字符串的。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 10;
map<char, int> mp[maxn];
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int t;
cin >> t;
while(t--)
{
int n, m;
cin >> n >> m;
for(int i = 0; i < m; ++i) mp[i].clear();
for(int i = 0; i < n; ++i){
string s;
cin >> s;
for(int j = 0; j < m; ++j){
mp[j][s[j]]++;
}
}
for(int i = 0; i < n - 1; ++i){
string s;
cin >> s;
for(int j = 0; j < m; ++j){
mp[j][s[j]]--;
}
}
for(int i = 0; i < m; ++i){
for(auto x : mp[i]){
if(x.second == 1){
cout << x.first;
break;
}
}
}
cout << endl;
}
return 0;
}
|
C. AquaMoon and Strange Sort
题意
给一个长度$n$的数组，要通过相邻数对交换排成不下降序列。问是否可以保证每个数进行交换的次数为偶数。
分析
直接sort得到每个数可以在哪个区间内，如果原来的下标是奇数，就必在区间内占有一个奇数下标；原来是偶数，就必须在区间内占有一个偶数下标。看最后能否容得下即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 10;
struct node
{
int idx, val;
}a[maxn];
bool cmp(const node& x, const node& y)
{
return x.val < y.val;
}
signed main()
{
DDLC_ESCAPE_PLAN_FAILED;
int t;
cin >> t;
while(t--)
{
mem(a);
int n;
cin >> n;
fors(i, 1, n) cin >> a[i].val, a[i].idx = i;
sort(a + 1, a + 1 + n, cmp);
bool flag = 1;
int i = 1;
for(; i <= n; )
{
vector<int> st;
st.pb(a[i].idx);
int org = i;
i++;
while(a[i].val == a[org].val && i <= n) st.pb(a[i++].idx);
int tot = i - org;
int odd, even;
if(!(tot & 1)) odd = even = tot / 2;
else if(org & 1) odd = (tot + 1) / 2, even = tot / 2;
else odd = tot / 2, even = (tot + 1) / 2;
for(auto x : st){
if(x & 1) odd--;
else even--;
}
if(odd < 0 || even < 0){
flag = 0;
break;
}
}
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
|
