题面： http://codeforces.com/contest/779
A. Pupils Redistribution
题意：给定两个group的序列，每个group有n个人，每个人的绩点分别用ai, bi表示。
现要求两个group中相同绩点的人个数相同，你可以任意交换group中的两个人。
问最少需要交换多少次。（绩点范围为1～5）如不能做到则输出-1
解法：模拟
用两个bucket保存两组中不同绩点的人数，如果有任何一个绩点两者的和为奇数则输出-1
由于其中一个组必然有多于平均的绩点，只需要把多于平均的绩点的那部分交换过去即可。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
using namespace std;
int a[10], b[10];
int num[10];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
int t; cin >> t;
a[t]++;
num[t]++;
}
for(int i = 0; i < n; i++)
{
int t; cin >> t;
b[t]++;
num[t]++;
}
for(int i = 1; i <= 5; i++)
{
if(num[i] % 2)
{
cout << -1 << endl;
return 0;
}
}
int cnt = 0;
for(int i = 1; i <= 5; i++)
{
if(2 * a[i] > num[i])
cnt += a[i] - num[i] / 2;
}
cout << cnt << endl;
return 0;
}
B.Weird Rounding
题意：给你一个数n(0 ≤ n ≤ 2 000 000 000)和k，每次可以删除n中的任意一位数，要求10^k能整除n。求最少删除多少位数。输入保证不会存在前导0。
解法：很显而易见的一件事情是从最后一位开始往前找，同时记录0的个数，遇到非零的则记录删除个数++。最后如果0的个数等于k，则输出删除个数。
否则的话，由于题目保证存在答案，只要保留数中的唯一一个0即可。
样例中的100 9 只需要删除1和0就可以。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
using namespace std;
int a[2000], b[2000];
bool vis[2000];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
string n;
int k;
cin >> n >> k;
int len = (int)n.length();
int cnt = 0, del = 0;
for(int i = len - 1; i >= 0; i--)
{
if(n[i] == '0')
cnt++;
else
del++;
if(cnt == k) break;
}
if(cnt == k)
cout << min(del, len - 1) << endl;
else
cout << len - 1 << endl;
return 0;
}
D. Dishonest Sellers
题意：给定商品现在的价格和一周后的价格，要求现在至少买k件商品，问你最少需要花的钱
解法：水题。按前后的价格差排个序，首先把k件物品买了，然后再看看是不是后面有当前更便宜的，加完就可以了。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
using namespace std;
const int maxn = 2e5 + 10;
struct node
{
int a, b, c;
}q[maxn];
bool cmp(const node& x, const node& y)
{
return x.c < y.c;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> q[i].a;
for (int i = 0; i < n; i++)
cin >> q[i].b;
for (int i = 0; i < n; i++)
q[i].c = q[i].a - q[i].b;
sort(q, q + n, cmp);
ll ans = 0;
for(int i = 0; i < k; i++)
ans += q[i].a;
int j = k;
while(q[j].c < 0)
ans += q[j++].a;
for(int i = j; i < n; i++)
ans += q[i].b;
cout << ans << endl;
return 0;
}
D. String Game
题意：给定两个字符串p和t，现在想从p中构造出t来。Nastya会从p中每次移除一个字符。现在问什么时候她不能继续进行，你需要阻止她。输入保证p可以构造出t。
解法：二分答案。
好像就没什么好说的了。判断字符串能不能被构造出来可以用两个指针分别指向两个字符串。同时记录下被删去的每个字符。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
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
bool vis[maxn];
string t, p;
bool C()
{
int i = 0, j = 0;
int len = (int)t.length();
int pl = (int)p.length();
while(j < len && i < pl)
{
if(vis[j]){j++;continue;}
if(t[j] == p[i])
{
j++;i++;
}
else
j++;
}
if(i == pl)return true;
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t >> p;
int len = (int)t.length();
for (int i = 0; i < len; i++)
{
cin >> a[i];
a[i]--;
}
int l = 0, r = len + 1;
for(int i = 0; i < 100; i++)
{
int mid = (l + r) / 2;
memset(vis, 0, sizeof(vis));
for(int i = 0; i < mid; i++)
vis[a[i]] = 1;
if(C())
l = mid;
else
r = mid;
}
cout << l << endl;
return 0;
}
E. Bitwise Formula
题意：给你一些变量，每个变量都是一些二进制串。这些数要不就以01的形式给出。要不就以变量相“与或非”形式给出。在这所有的变量中有一个是未定的用’?’给出。现希望所有的变量和最大和最小时求出‘?’。如果有最大值或者最小值有相同的，则输出最小的’?’
解法：贪心
稍微有些难想的贪心题。考虑位运算的特点，每次运算同一位只会影响同一位的值，所以只需要单独考虑某一位就可以了。单独考虑某一位，取0或者1进行计算，看取0的时候1的数量多还是取1的时候多，分别取0或者1。如果两者一样多，则取0以满足尽可能的小。
然后就是实现的问题了，实现起来还有些麻烦。由于题目中的变量是以字符串的方式给出。所以还需要用一个map存，以知道对应的下标。但如果每次都要查找会超时。。。
所以计算完以后就将下标存储即可。= = 不看别人的代码根本不知道需要这样改orz1
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
using namespace std;
const int maxn = 1e5 + 10;
map<string, int> q;
struct node{
string op;//运算符
string a, b;//a和b的字符串
int pa, pb;//a和b的下标
bool iscal;//是否需要计算（是不是以变量运算的形式给出）
}
int n, m;
int save[maxn];
int cal(int idx, int bit)
{
int cnt = 0;
memset(save, 0, sizeof(save));
for(int i = 0; i < n; i++)
{
if(a[i].iscal) {
save[i] = a[i].a[idx] - '0';
continue;
}
int x, y;
if(a[i].a == "?")
x = bit;
else
x = save[a[i].pa];
if(a[i].b == "?")
y = bit;
else
y = save[a[i].pb];
int res = 0;
if(a[i].op == "XOR")
res = x xor y;
else if(a[i].op == "OR")
res = x or y;
else
res = x and y;
save[i] = res;
if(res)
cnt++;
}
return cnt;
}
char mini[1200], maxi[1200];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("/Users/vector/Desktop/in", "r", stdin);
cin >> n >> m;
cin.get();
for (int i = 0; i < n; i++)
{
string var;
getline(cin, var);
stringstream sin = stringstream(var);
string t;
vector<string> s;
while(sin >> t)
s.push_back(t);
q[s[0]] = i;
a[i].a = s[2];
a[i].iscal = 1;
if(s.size() > 3)
{
a[i].op = s[3];
a[i].pa = q[a[i].a];
a[i].b = s[4];
a[i].pb = q[a[i].b];
a[i].iscal = 0;
}
}
for (int i = 0; i < m; i++)
{
int a = cal(i, 0);
int b = cal(i, 1);
if(a > b)
{
mini[i] = '1';
maxi[i] = '0';
}
else if(a < b)
{
mini[i] = '0';
maxi[i] = '1';
}
else
{
mini[i] = '0';
maxi[i] = '0';
}
}
cout << mini << endl;
cout << maxi << endl;
return 0;
}