A. Mathematical Addition
题意:给定两个数字u, v，求满足$\frac{x}{u}+\frac{y}{v}=\frac{x+y}{u+v}$的x, y（$x\neq0,y\neq0$）
思路：两边同时乘以uv(u+v)，化简一下就能得到 $x=-u^2,y=v^2$
代码：
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
| #include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int T; cin>>T;
while(T--)
{
int a, b; cin>>a>>b;
cout<<(ll)-a*a<<" "<<(ll)b*b<<endl;
}
return 0;
}
|
B. Coloring Rectangles
题意：给定一个$nm$的红色矩阵，可以任意划分为大于$11$的小矩阵，然后在每个小矩阵中将一部分格子染为蓝色，使得红蓝相间。求最小蓝色数量。
思路：$13$的两红一蓝是最优的，红蓝比为2:1。所以若能全分为$13$就最优，为$nm/3$，否则为$nm/3+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
41
42
43
44
45
46
47
48
49
50
51
| #include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define sc second
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int T; cin>>T;
while(T--)
{
int n, m; cin>>n>>m;
if(!(n%3) || !(m%3)) cout<<(ll)n*m/3<<endl;
else cout<<(ll)n*m/3+1<<endl;
}
return 0;
}
|
C. Two Arrays
题意：给定两个数组a, b。可以在a数组中选取一段连续的区间，让这个区间的元素都加1。每个元素只能被选择一次。问a数组经过变换后能否和b数组相同。
思路：排个序，比较两个数组对应位置的元素，当他们的差值全部小于等于1就说明可以相同，注意a[i]不能大于b[i] （因为只能a数组元素加1，不能是b数组元素加1，刚开始我这里就wa了）
代码：
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 <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define sc second
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
int a[111], b[111], aa[111], bb[111];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int T; cin>>T;
while(T--)
{
int n; cin>>n;
for(int i = 1; i <= n; i++) cin>>a[i];
for(int i = 1; i <= n; i++) cin>>b[i];
sort(a+1, a+n+1);
sort(b+1, b+n+1);
int flag = 0;
for(int i = 1; i <= n; i++)
{
if(abs(a[i]-b[i]) > 1 || a[i] > b[i])
{
flag = 1;
break;
}
}
cout<<(flag == 0 ? "YES":"NO")<<endl;
}
return 0;
}
|
D. Guess the Permutation
题意：给出数组的长度n，在数组中选择三个位置i , j , k ，翻转数组[ i , j−1 ] , [ j , k ]的元素。每次可以询问一段区间 [l, r] 里逆序对的个数，在最多40次询问里求出i , j , k。（交互题）
思路：二分
！！！！思路一！！！！
确定 i
逆序对数为0的最长区间就是 [1, i ]，可以确定左区间为1，二分找右区间 i，需要$log_2^{1e9}$次（最多30次）
确定 j
先给公式：j = i + (ask(i, n) - ask(i+1, n) + 1)
再证明（举栗子)
假设原数组：1 2 3 4 5 6 7 8
翻转后数组：1 5 4 3 2 7 6 8 ( 所以5的下标为 i, 4的下标为 i+1, 6的下标为 j)
具体看这一段区间：
5 4 3 2 逆序对个数为 6
4 3 2 逆序对个数为 3
可以得到：（ask(i, n) - ask(i+1, n) + 1） = 区间长度
则: j = i + 区间长度
确定k
和确定 j 的道理相同：k = j + ask(j, n) - ask(j+1, n)
（最终一共最多查询34次）
！！！！思路二！！！！
方法和思路一差不多，只是先确定 k， 再确定 j, i 。（i, j, 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
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
| #include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define sc second
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
ll ask(ll l, ll r)
{
ll ans = 0;
cout<<"? "<<l<<" "<<r<<endl;
cout.flush();
cin>>ans;
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int T; cin>>T;
while(T--)
{
ll n; cin>>n;
ll l = 1, r = n, i, j, k;
while(l < r)
{
int mid = (l+r)>>1;
if(ask(1, mid) > 0) r = mid;
else l = mid+1;
}
i = l-1;
j = i + ask(i, n) - ask(i+1, n) + 1;
k = j + ask(j, n) - ask(j+1, n);
cout<<"! "<<i<<" "<<j<<" "<<k<<endl;
cout.flush();
}
return 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
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
| #include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define sc second
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
ll ask(ll l, ll r)
{
ll ans = 0;
cout<<"? "<<l<<" "<<r<<endl;
cout.flush();
cin>>ans;
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int T; cin>>T;
while(T--)
{
ll n; cin>>n;
ll l = 1, r = n, i, j, k;
ll cnt = ask(1, n);
while(l < r)
{
int mid = (l+r)>>1;
if(ask(1, mid) == cnt) r = mid;
else l = mid+1;
}
if(ask(1, l-1) == cnt) k = l-1;
else k = r;
j = k - cnt + ask(1, k-1);
i = j - (ll)sqrt(ask(1, j-1)*2) - 1;
cout<<"! "<<i<<" "<<j<<" "<<k<<endl;
cout.flush();
}
return 0;
}
|